On Tradeoffs in Learning-Augmented Algorithms
Ziyad Benomar, Vianney Perchet · 2025
Read On Tradeoffs in Learning-Augmented Algorithms by Ziyad Benomar, Vianney Perchet (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12770.txt.
Introduction
Ziyad Benomar and Vianney Perchet examine the tangled tradeoffs inside learning-augmented algorithms, in a 2025 paper. Such algorithms take advice from predictions that may be wrong, and designers judge them on consistency when the advice is good, robustness when it is bad, and smoothness in between. When the prediction error's distribution is known, strong average performance joins the wish list.
Earlier work chased the best balance of consistency and robustness for single problems, sometimes quietly sacrificing smoothness. The authors show some problems force several tradeoffs at once, among all four virtues. No single tuning wins everywhere: designers must choose which virtue to favor. The paper maps where those hard choices are unavoidable.
Catalog record
| CREATOR | Ziyad Benomar, Vianney Perchet |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-12770
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Tradeoffs in Learning-Augmented Algorithms Ziyad Benomar, Vianney Perchet Abstract The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these 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 demonstrate that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance. 1 Introduction Many decision-making problems under uncertainty are commonly studied using competitive analysis. In this context, the performance of online algorithms, operating under uncertainty, is compared to that of the optimal offline algorithm, which has full knowledge of the problem instance. While competitive analysis provides a rigorous method for evaluating online algorithms, it is often overly pessimistic. In real-world scenarios, decision-makers can have some prior knowledge, though possibly imperfect, about the complete problem instance. For example, predictions of unknown variables might be obtained via machine learning models, or an expert might provide advice on the best course of action. This more realistic setting was formalized by Lykouris and Vassilvtiskii (2018) and Purohit et al. (2018) leading to the development of what is now known as learning-augmented algorithms. In this paradigm, the algorithm receives predictions about the current problem instance, but without any guarantees on their accuracy, and must satisfy three main properties: • Consistency: perform almost as well as the optimal offline algorithm if the predictions are perfect. • Robustness: maintain a performance level close to the worst-case scenario without predictions when the predictions are arbitrarily bad. • Smoothness: the performance should degrade gracefully as the prediction error increases. Consistency, robustness, and brittleness. Consider a minimization problem under uncertainty, and let ALG be an algorithm augmented with a prediction y of an unknown parameter x . The input of the algorithm can contain parameters other than x , but for simplicity, we denote by \textsf{ALG}(x,y) the value of the objective function achieved by ALG , and \textsf{OPT}(x) the value of the optimal offline algorithm. The consistency c and robustness r of ALG are defined as c=\sup_{x}\frac{\textsf{ALG}(x,x)}{\textsf{OPT}(x)}\,\qquad\text{and}\qquad r=\sup_{x,y}\frac{\textsf{ALG}(x,y)}{\textsf{OPT}(x)}\;. Consistency is the worst-case ratio when the prediction is perfectly accurate, i.e. y=x , while robustness is the worst-case ratio with adversarial prediction. Most research on learning-augmented algorithms focuses on achieving good tradeoffs between consistency and robustness. Some studies also establish algorithms with Pareto-optimal tradeoffs, i.e. no algorithm can have simultaneously better consistency and better robustness. However, the proposed algorithms in such studies sometimes lack smoothness. Specifically, their worst-case performance can degrade abruptly, moving from the consistency bound when the predictions are perfect to the robustness bound even with an arbitrarily small error in the prediction. Following the terminology of ( Angelopoulos et al., 2024a ) , we say that such an algorithm is brittle. Definition 1.1 (Brittleness) . an algorithm ALG with robustness r is brittle if \forall\varepsilon>0:\sup_{x,y:\;|x-y|\leq\varepsilon x}\frac{\textsf{ALG}(x,y)}{\textsf{OPT}(x)}=r\;. In real-world scenarios, predictions are rarely perfect. As a result, the only reliable guarantee for brittle algorithms is the robustness bound, which is at best equivalent to the worst-case bound without predictions. This greatly limits the practical usefulness of these algorithms. In the case of the one-way trading problem, Angelopoulos et al. (2024a) demonstrated in a very recent work that any algorithm achieving a Pareto-optimal tradeoff between consistency and robustness is brittle. This finding implies that, in some problems, achieving smoothness requires deviating from the Pareto-optimal tradeoff between consistency and robustness. Average-case performance. In the context of learning-augmented algorithms, the consistency, robustness, and smoothness of an algorithm represent worst-case guarantees with respect to the prediction error. On the other hand, there are numerous scenarios where the decision-maker might know some information about the distribution of the prediction, which motivates the design of algorithms with good average performance ( Dütting et al., 2021 ; Gupta et al., 2022 ; Benomar and Perchet, 2023 ; Henzinger et al., 2023 ; Cohen-Addad et al., 2024 ) . Nevertheless, while achieving a balance between worst-case and average-case performance has been widely studied in various fields of algorithm design and machine learning ( Szirmay-Kalos and Márton, 1998 ; Witt, 2005 ; Peikert and Rosen, 2007 ; Antunes and Fortnow, 2009 ; Chuangpishit et al., 2018 ; Rice et al., 2021 ; Robey et al., 2022 ) , this aspect has not yet been investigated in the context of learning-augmented algorithms for the prediction error. 1.1 Contributions In this work, we explore various tradeoffs that arise in the design and analysis of learning-augmented algorithms. While existing literature has primarily focused on the tradeoff between consistency and robustness, our investigation centers on the tradeoffs between consistency and smoothness, as well as the relationships between the standard criteria for learning-augmented algorithms—namely consistency, robustness, and smoothness—and their average performance under stochastic assumptions regarding predictions. We begin by examining the line search problem , revisiting the algorithm proposed by Angelopoulos et al. (2019) . This algorithm achieves a Pareto-optimal tradeoff between consistency and robustness among deterministic algorithms, but we demonstrate that it is inherently brittle. We show that this brittleness can be mitigated by introducing randomness into the predictions used by the algorithm. The variance of this randomization is quantified by a parameter \rho\geq 0 . Our analysis reveals that tuning this parameter leads to opposing effects on the consistency and smoothness of the algorithm, thus yielding a tradeoff between these two criteria. Next, we apply a similar approach to the one-max search problem . We examine the Pareto-optimal algorithm introduced by Sun et al. (2021) , and we show its brittleness. Furthermore, we demonstrate how randomization can be used to guarantee smoothness at the cost of consistency. Once again, the resulting tradeoff is governed by a parameter \rho\geq 0 . Finally, we address the ski-rental problem , proposing an algorithm that generalizes that of Purohit et al. (2018) . Through a tight analysis of its performance, we prove that the Pareto-optimal tradeoff between consistency and robustness can be achieved with different levels of smoothness. However, we show that striving for optimal smoothness degrades the average-case performance of the algorithm, assuming that the prediction induces the correct decision (renting or buying at time 0 ) with a probability Q\in[\tfrac{1}{2},1] . In this context, a parameter \rho\in[0,1] can be utilized to tune the levels of smoothness and average-case performance, all while maintaining fixed levels of consistency and robustness. Additionally, we conduct numerical experiments for the three problems studied in the paper, highlighting the various tradeoffs demonstrated in our analysis. 1.2 Related work Learning-augmented algorithms. The design of learning-augmented algorithms ( Lykouris and Vassilvtiskii, 2018 ; Purohit et al., 2018 ) relies on using machine-learned advice to go beyond worst-case limitations. These algorithms operate under the assumption that the decision-maker has access to noisy predictions about certain problem parameters. The goal of learning-augmented algorithms is to improve performance if the predictions are accurate, while also ensuring robustness in the face of incorrect or adversarial predictions. Many fundamental algorithmic problems were studied in this setting, such as ski rental (