On Tradeoffs in Learning-Augmented Algorithms
This work addresses the design of learning-augmented algorithms for scenarios with potentially inaccurate predictions, but it appears incremental as it builds on prior efforts to achieve Pareto-optimal tradeoffs.
The paper investigates the tradeoffs in learning-augmented algorithms, showing that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance, without providing specific numerical results.
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. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance.