mlsanityData to 7 Oct 2026

Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms

arXiv 2010.11443 ↗First posted 22 Oct 2020cs.LG cs.DScited by 64

Not on the map. Why?

Abstract (arXiv)

We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust, meaning that the algorithm performs well when predictions are accurate and maintains worst-case guarantees. Such algorithms have been studied in a recent line of works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary. In this paper, we provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.

Key facts. Cited by 64 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 10; 2023: 10; 2024: 14; 2025: 14; 2026: 9.

64 papers.

Sort:

By area:

  1. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  2. 2022Online Algorithms with Multiple Predictionscited by 22
  3. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  4. 2021Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problemscited by 19
  5. 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
  6. 2022Algorithms with Prediction Portfolioscited by 19
  7. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  8. 2021Can Q-Learning be Improved with Advice?cited by 13
  9. 2021Online Bin Packing with Predictionscited by 11
  10. 2022Learning-Augmented Algorithms for Online Linear and Semidefinite Programmingcited by 11
  11. 2021Double Coverage with Machine-Learned Advicecited by 10
  12. 2022Smoothed Online Optimization with Unreliable Predictionscited by 10
38 more
  1. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  2. 2024Algorithm Configuration for Structured Pfaffian Settingscited by 10
  3. 2025Robustness and Cybersecurity in the EU Artificial Intelligence Actcited by 10
  4. 2022Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Marketscited by 9
  5. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  6. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  7. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  8. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  9. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  10. 2023Online Ad Allocation with Predictionscited by 7
  11. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  12. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  13. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  14. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  15. 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
  16. 2022Equipping Black-Box Policies with Model-Based Advice for Stable Nonlinear Controlcited by 5
  17. 2023Learning for Edge-Weighted Online Bipartite Matching with Robustness Guaranteescited by 5
  18. 2024Online Classification with Predictionscited by 5
  19. 2024Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problemscited by 5
  20. 2023The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformationscited by 4
  21. 2024Learning-Augmented Search Data Structurescited by 4
  22. 2024Chasing Convex Functions with Long-term Constraintscited by 4
  23. 2024Learning-Based Algorithms for Graph Searching Problemscited by 4
  24. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  25. 2023Robust Learning for Smoothed Online Convex Optimization with Feedback Delaycited by 3
  26. 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3
  27. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  28. 2021Online Search With Best-Price and Query-Based Predictionscited by 2
  29. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  30. 2025Learning-Augmented Online Bipartite Matching in the Random Arrival Order Modelcited by 2
  31. 2026The Secretary Problem with Predictions and a Chosen Ordercited by 2
  32. 2022Online TSP with Predictionscited by 1
  33. 2023Learning-Augmented Decentralized Online Convex Optimization in Networkscited by 1
  34. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  35. 2025Learning-Augmented Algorithms for Boolean Satisfiabilitycited by 1
  36. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  37. 2024Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Healthcited by 0
  38. 2024Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraintscited by 0

50 most cited of 64 All 64 (JSON)