# Prediction-Specific Design of Learning-Augmented Algorithms

arXiv: https://arxiv.org/abs/2510.14887 · HTML: https://mlsanity.com/paper/2510.14887/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 12 references that are in the map.
- First posted on arXiv 16 Oct 2025.

## Builds on (most cited first, 7 of 7)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting](https://mlsanity.com/paper/2303.17551/) (2023)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search](https://mlsanity.com/paper/2502.05720/) (2025)

## Abstract (arXiv)

Algorithms with predictions has 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.