mlsanityData to 14 Oct 2026

Customizing ML Predictions for Online Algorithms

arXiv 2205.08715 ↗First posted 18 May 2022cs.LG cs.DScited by 21

Not on the map. Why?

Abstract (arXiv)

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Builds on 12 of its 35 references that are in the map. First posted on arXiv 18 May 2022.

Builds on

12 of 35 references.

References · 12

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  3. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  4. 2015A PAC Approach to Application-Specific Algorithm Selectioncited by 58
  5. 2015The Sample Complexity of Revenue Maximizationcited by 48
  6. 2019Scheduling with Predictions and the Price of Mispredictioncited by 47
  7. 2019Addressing the Loss-Metric Mismatch with Adaptive Loss Alignmentcited by 33
  8. 2020Online Algorithms for Weighted Paging with Predictionscited by 29
  9. 2016Learning Simple Auctionscited by 23
  10. 2017Revenue Optimization with Approximate Bid Predictionscited by 21
  11. 2015The Limitations of Optimization from Samplescited by 13
  12. 2018Minimax Lower Bounds for Cost Sensitive Classificationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 6; 2024: 7; 2025: 4; 2026: 1.

21 papers.

Sort:

  1. 2022Algorithms with Prediction Portfolioscited by 19
  2. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  3. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  4. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  5. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  6. 2024Learning-Augmented Priority Queuescited by 7
  7. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  8. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  9. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  10. 2023Online Dynamic Acknowledgement with Learned Predictionscited by 5
  11. 2024Learning-Augmented Search Data Structurescited by 4
  12. 2024Learning-Based Algorithms for Graph Searching Problemscited by 4
9 more
  1. 2023A Survey of Machine Learning-Based Ride-Hailing Planningcited by 3
  2. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  3. 2025Learning-Augmented Online Bipartite Matching in the Random Arrival Order Modelcited by 2
  4. 2022Online TSP with Predictionscited by 1
  5. 2023Online Resource Allocation: Bandits feedback and Advice on Time-varying Demandscited by 1
  6. 2024MAC Advice for Facility Location Mechanism Designcited by 0
  7. 2025On multiagent online problems with predictionscited by 0
  8. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  9. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0