Algorithms with Calibrated Machine Learning Predictions
This work addresses the challenge of effectively using uncertain predictions in online algorithms for problems like resource allocation and scheduling, offering a practical solution with incremental improvements over prior methods.
The paper tackles the problem of incorporating uncertain machine learning predictions into online algorithms by proposing calibration as a tool to bridge the gap between aggregate trust levels and prediction-level uncertainty. It demonstrates benefits through case studies on ski rental and job scheduling, showing near-optimal performance and significant improvements over existing methods, with evaluations on real-world data validating the findings.
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.