On Tradeoffs in Learning-Augmented Algorithms

Ziyad Benomar, Vianney Perchet
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:802-810, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v258-benomar25a, 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}, pages = {802--810}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/benomar25a/benomar25a.pdf}, url = {https://proceedings.mlr.press/v258/benomar25a.html}, 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.} }
Endnote
%0 Conference Paper %T On Tradeoffs in Learning-Augmented Algorithms %A Ziyad Benomar %A Vianney Perchet %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-benomar25a %I PMLR %P 802--810 %U https://proceedings.mlr.press/v258/benomar25a.html %V 258 %X 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.
APA
Benomar, Z. & Perchet, V.. (2025). On Tradeoffs in Learning-Augmented Algorithms. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:802-810 Available from https://proceedings.mlr.press/v258/benomar25a.html.

Related Material