Prediction-Specific Design of Learning-Augmented Algorithms
Open Access
- 26 March 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 10 (1) , 1-57
Abstract
Algorithms with predictions have emerged as a powerful framework to combine the robustness of traditional online algorithms with the data-driven performance benefits of machine-learned (ML) predictions. However, most existing approaches in this paradigm are overly conservative, as they do not leverage problem structure to optimize performance in a prediction-specific manner. In this paper, we show that such prediction-specific performance criteria can enable significant performance improvements over the coarser notions of consistency and robustness considered in prior work. Specifically, we propose a notion of strongly-optimal algorithms with predictions, which obtain Pareto optimality not just in the worst-case tradeoff between robustness and consistency, but also in the prediction-specific tradeoff between these metrics. We develop a general bi-level optimization framework that enables systematically designing strongly-optimal algorithms in a wide variety of problem settings, and we propose explicit strongly-optimal algorithms for several classic online problems: deterministic and randomized ski rental, and one-max search. Our analysis reveals new structural insights into how predictions can be optimally integrated into online algorithms by leveraging a prediction-specific design. To validate the benefits of our proposed framework, we empirically evaluate our algorithms in case studies on problems including dynamic power management and volatility-based index trading. Our results demonstrate that prediction-specific, strongly-optimal algorithms can significantly improve performance across a variety of online decision-making settings.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Controlling Tail Risk in Online Ski-Rental2024
- Robustness and Consistency in Linear Quadratic Control with Untrusted PredictionsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022
- Competitive Caching with Machine Learned AdviceJournal of the ACM, 2021
- Online Peak-Aware Energy Scheduling with Untrusted Advice2021
- I/O Characteristics of Smartphone Applications and Their Implications for eMMC Design2015
- The multi-shop ski rental problem2014
- Online Optimization with Uncertain InformationACM Transactions on Algorithms, 2012
- Optimal Search and One-Way Trading Online AlgorithmsAlgorithmica, 2001
- Nonclairvoyant schedulingTheoretical Computer Science, 1994
- Competitive snoopy cachingAlgorithmica, 1988