# Algorithms with Calibrated Machine Learning Predictions

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

## Key facts

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

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (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)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Distribution-free calibration guarantees for histogram binning without sample splitting](https://mlsanity.com/paper/2105.04656/) (2021)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Contract Scheduling with Distributional and Multiple Advice](https://mlsanity.com/paper/2404.12485/) (2024)
- [Calibration of Neural Networks](https://mlsanity.com/paper/2303.10761/) (2023)
- [Scheduling with Predictions](https://mlsanity.com/paper/2212.10433/) (2022)

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

- [The Alpha Illusion: Reported Alpha from LLM Trading Agents Should Not Be Treated as Deployment Evidence](https://mlsanity.com/paper/2605.16895/) (2026)
- [Ski Rental with Distributional Predictions of Unknown Quality](https://mlsanity.com/paper/2602.21104/) (2026)
- [Aligning Data-Driven Predictors with Allocation: A Decision-Focused Approach to Survival Analysis](https://mlsanity.com/paper/2606.02671/) (2026)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Auditability and the Landscape of Distance to Multicalibration](https://mlsanity.com/paper/2509.16930/) (2025)
- [Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors](https://mlsanity.com/paper/2509.26511/) (2025)
- [Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio](https://mlsanity.com/paper/2601.06813/) (2026)

## Abstract (arXiv)

The field of algorithms with predictions incorporates machine learning advice in the design of online algorithms to improve real-world performance. A central consideration is the extent to which predictions can be trusted -- while existing approaches often require users to specify an aggregate trust level, modern machine learning models can provide estimates of prediction-level uncertainty. In this paper, we propose calibration as a principled and practical tool to bridge this gap, demonstrating the benefits of calibrated advice through two case studies: the ski rental and online job scheduling problems. For ski rental, we design an algorithm that achieves near-optimal prediction-dependent performance and prove that, in high-variance settings, calibrated advice offers more effective guidance than alternative methods for uncertainty quantification. For job scheduling, we demonstrate that using a calibrated predictor leads to significant performance improvements over existing methods. Evaluations on real-world data validate our theoretical findings, highlighting the practical impact of calibration for algorithms with predictions.