# On Tradeoffs in Learning-Augmented Algorithms

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 41 references that are in the map.
- First posted on arXiv 22 Jan 2025.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [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)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Online Search With a Hint](https://mlsanity.com/paper/2008.13729/) (2020)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [On Preemption and Learning in Stochastic Scheduling](https://mlsanity.com/paper/2205.15695/) (2022)
- [Robust Learning-Augmented Dictionaries](https://mlsanity.com/paper/2402.09687/) (2024)
- [Max-Cut with ε-Accurate Predictions](https://mlsanity.com/paper/2402.18263/) (2024)
- [Search Games with Predictions](https://mlsanity.com/paper/2401.01149/) (2024)

## Built on by (most cited first, 7 of 7)

- [Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search](https://mlsanity.com/paper/2502.05720/) (2025)
- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.17701/) (2025)
- [Privacy-Preserving Learning-Augmented Data Structures](https://mlsanity.com/paper/2510.00165/) (2025)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)
- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)
- [Augmented Hypothesis Testing with Persona-Based LLM Simulations](https://mlsanity.com/paper/2609.24629/) (2026)

## Abstract (arXiv)

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.