# Customizing ML Predictions for Online Algorithms

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

## 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 (most cited first, 12 of 12)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Addressing the Loss-Metric Mismatch with Adaptive Loss Alignment](https://mlsanity.com/paper/1905.05895/) (2019)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [Minimax Lower Bounds for Cost Sensitive Classification](https://mlsanity.com/paper/1805.07723/) (2018)

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

- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [A Survey of Machine Learning-Based Ride-Hailing Planning](https://mlsanity.com/paper/2303.14646/) (2023)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [Online TSP with Predictions](https://mlsanity.com/paper/2206.15364/) (2022)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)
- [MAC Advice for Facility Location Mechanism Design](https://mlsanity.com/paper/2403.12181/) (2024)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio](https://mlsanity.com/paper/2601.06813/) (2026)

## 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.