[2502.02861] Algorithms with Calibrated Machine Learning Predictions

Statistics > Machine Learning arXiv:2502.02861 (stat) [Submitted on 5 Feb 2025 (v1), last revised 25 Mar 2026 (this version, v4)] Title:Algorithms with Calibrated Machine Learning Predictions Authors:Judy Hanwen Shen, Ellen Vitercik, Anders Wikum View a PDF of the paper titled Algorithms with Calibrated Machine Learning Predictions, by Judy Hanwen Shen and 2 other authors View PDF HTML (experimental) Abstract: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 pra...