More Like this

1. Online Peak-Aware Energy Scheduling with Untrusted Advice

   Lee, Russell; Maghakian, Jessica; Hajiesmaili, Mohammad H; and Ramesh Sitaraman, Jian Li; Liu, Zhenhua (June 2021, Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy))

   null (Ed.)

   This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: textit{robustness} that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and textit{consistency} for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform algorithms optimized for worst-case and fully data-driven algorithms. 

   more » « less
2. Online Peak-Aware Energy Scheduling with Untrusted Advice

   https://doi.org/10.1145/3447555.3464860  

   Lee, Russell; Maghakian, Jessica; Hajiesmaili, Mohammad; Li, Jian; Sitaraman, Ramesh; Liu, Zhenhua (June 2021, ACM Future Energy Systems Conference (e-Energy ’21))

   null (Ed.)

   This paper studies the online energy scheduling problem in a hy- brid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the pro- posed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimal- ity of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal de- terministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform worst-case optimized algorithms and fully data-driven algorithms. 

   more » « less
3. Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems

   Bo Sun, Russell Lee (January 2021, Advances in Neural Information Processing Systems 34 (NeurIPS 2021))

   This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion. 

   more » « less
4. Online Matching with General Arrivals

   Gamlath, Buddhima; Kapralov, Michael; Maggiori, Andreas; Svensson, Ola; Wajc, David (October 2019, IEEE Symposium on Foundations of Computer Science)

   The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging, and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. For edge arrivals, randomization does not help | no randomized algorithm is better than 1/2 competitive. For general vertex arrivals, randomization helps | there exists a randomized (1/2+ Ω(1))-competitive online matching algorithm. 

   more » « less
5. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

   Nicolas Christianson, Junxuan Shen (April 2023, roceedings of The 26th International Conference on Artificial Intelligence and Statistics)

   We examine the problem of designing learning-augmented algorithms for metrical task systems (MTS) that exploit machine-learned advice while maintaining rigorous, worst-case guarantees on performance. We propose an algorithm, DART, that achieves this dual objective, providing cost within a multiplicative factor (1+ϵ) of the machine-learned advice (i.e., consistency) while ensuring cost within a multiplicative factor 2O(1/ϵ) of a baseline robust algorithm (i.e., robustness) for any ϵ>0 . We show that this exponential tradeoff between consistency and robustness is unavoidable in general, but that in important subclasses of MTS, such as when the metric space has bounded diameter and in the k -server problem, our algorithm achieves improved, polynomial tradeoffs between consistency and robustness. 

   more » « less