Algorithms with Calibrated Machine Learning Predictions

In recent years, advances in machine learning (ML) models have inspired researchers to revisit the design of classic online algorithms, incorporating insights from ML-based advice to improve decision-making in real-world environments. This research area, termed algorithms with predictions, seeks to design algorithms that are both robust to worst-case inputs and achieve performance that improves with prediction accuracy (a desideratum termed consistency) (Lykouris and Vassilvitskii, 2018). Many prediction-aided algorithms have been developed for online decision-making tasks ranging from rent-or-buy problems like ski rental (Purohit et al., 2018; Anand et al., 2020; Sun et al., 2024) to sequencing problems like job scheduling (Cho et al., 2022). Algorithms in this framework often rely on global uncertainty parameters intended to summarize the trustworthiness of all of the model's predictions, with extreme settings indicating that predictions are either all perfect or all uninformative (e.g., Mahdian et al., 2007; Lykouris and Vassilvitskii, 2018; Purohit et al., 2018; Rohatgi, 2020; Wei and Zhang, 2020; Antoniadis et al., 2020). However, ML models often produce local, input-specific uncertainty estimates, exposing a disconnect between theory and practice.