mlsanityData to 7 Oct 2026

On Tradeoffs in Learning-Augmented Algorithms

arXiv 2501.12770 ↗First posted 22 Jan 2025cs.DS cs.AI cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

25 of 41 references.

References · 25

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  4. 2020Online metric algorithms with untrusted predictionscited by 74
  5. 2024Improving Online Algorithms via ML Predictionscited by 65
  6. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  7. 2019Online Computation with Untrusted Advicecited by 42
  8. 2020Secretaries with Advicecited by 41
  9. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 36
  10. 2022Learning Augmented Binary Search Treescited by 31
  11. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  12. 2021Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problemscited by 19
13 more
  1. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  2. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  3. 2022Paging with Succinct Predictionscited by 10
  4. 2023On the Complexity of Algorithms with Predictions for Dynamic Graph Problemscited by 9
  5. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  6. 2020Online Search With a Hintcited by 7
  7. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  8. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  9. 2024Learning-Augmented Priority Queuescited by 7
  10. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  11. 2024Robust Learning-Augmented Dictionariescited by 6
  12. 2024Max-Cut with ε-Accurate Predictionscited by 4
  13. 2024Search Games with Predictionscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  2. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  3. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  4. 2025Privacy-Preserving Learning-Augmented Data Structurescited by 0
  5. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0
  6. 2026Near-Optimal Reinforcement Learning with Multi-Step Transition Lookaheadcited by 0
  7. 2026Augmented Hypothesis Testing with Persona-Based LLM Simulationscited by 0