On Tradeoffs in Learning-Augmented Algorithms
Abstract
The field of learning-augmented algorithms has gained significant attention in recent years. Using potentially inaccurate predictions, these algorithms must exhibit three key properties: consistency, robustness, and smoothness. In scenarios with stochastic predictions, a strong average-case performance is required. Typically, the design of such algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. In this paper, we explore the tradeoffs between all the mentioned criteria and show how they can be balanced.
Cite
Text
Benomar and Perchet. "On Tradeoffs in Learning-Augmented Algorithms." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Benomar and Perchet. "On Tradeoffs in Learning-Augmented Algorithms." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/benomar2025aistats-tradeoffs/)BibTeX
@inproceedings{benomar2025aistats-tradeoffs,
title = {{On Tradeoffs in Learning-Augmented Algorithms}},
author = {Benomar, Ziyad and Perchet, Vianney},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {802-810},
volume = {258},
url = {https://mlanthology.org/aistats/2025/benomar2025aistats-tradeoffs/}
}