Algorithms with Calibrated Machine Learning Predictions

We’re glad that the reviewer shares our excitement about calibration as a novel and practical prediction concept for algorithms with predictions with lots of theoretical potential!

“The expected performance bound for ski rental scales with max calibration error, which can be large, so the algorithm is non-robust.” We thank the reviewer for the opportunity to clarify this point — while our global (Theorem 3.1) and prediction-level (Theorem 3.3) performance bounds degrade with larger calibration error, we note that the expected competitive ratio of our algorithm for ski rental will never exceed 3. This fact is not immediately obvious, and we will add an explanation to our discussion on worst-case expected performance in line 211 of Section 3.3 to help contextualize the 1.8 bound when calibration error is zero. The idea is that when the max calibration error is larger than ⅓, the algorithm executes a worst-case renting strategy that is 2-competitive. For max calibration error of at most ⅓, the bound from Theorem 3.3 can be no larger than 3.

“The results for job scheduling rely on an IID assumption that may not hold in reality” Though prior work in ML-augmented scheduling (Cho et al., 2022) also assumes independence for the sake of simplifying the prediction task, we agree that features are likely to exhibit some level of correlation in real-world job scheduling contexts. The difficulty of the prediction task grows exponentially in the number of jobs when arbitrary correlations are allowed, but we see allowing for limited correlations as an interesting direction for future work to continue narrowing the gap between theory and practice.

We appreciate the reviewer’s feedback and are glad that they value our high-level goal of using calibration as a tool to ensure the trustworthiness of predictions provided to decision makers.

“Do the job scheduling results generalize to predictors with non-zero calibration error?” Yes, our results extend beyond perfectly calibrated predictors. We presented our results in terms of perfectly calibrated predictions to highlight the intuition that finer-grained predictions reduce sequencing errors, but they generalize to any predictions that are monotonically calibrated. Monotonic calibration is the weaker condition that the empirical frequencies $\Pr(Y=1 \mid f(X))$ are non-decreasing in the prediction $f(X)$. This property holds trivially for perfectly calibrated predictors, but zero calibration error is not required. In fact, many calibration approaches used in practice (e.g. Platt scaling (Platt 1999) and isotonic regression (Zadrozny and Elkan 2002; 2003)) fit a monotonic function to data of the form $(f(X), \Pr(Y=1 \mid f(X))$, leading to a monotonically-calibrated predictor with non-zero calibration error.

Thanks for pointing out that the statement of Theorem 4.3 appears brittle due to the assumption on perfect calibration. We’ll add a note that the result generalizes to predictors with non-zero calibration error and include full details for the more general case in the appendix.

“For ski rental, is an average error metric like expected calibration error (ECE) more thematically appropriate than a worst-case metric like max-calibration error (MCE)?” Designing an algorithm that relies on ECE instead of MCE is an interesting direction for future work, and we will add it as an open question to Section 6. We suspect a global performance bound similar to Theorem 3.1 may still be recoverable in that setting. To the reviewer’s point, when MCE is significantly larger than ECE, Algorithm 1 makes conservative decisions, which suggests room for improvement. The fundamental challenge is that under ECE, prediction-specific performance bounds like those from Theorem 3.3 would only hold for predictions which are not “too miscalibrated,” rather than for all predictions. Nonetheless, MCE aligns with our goal of providing prediction-specific performance guarantees based on practical error metrics. Importantly, MCE is only worst-case with respect to the finite set of predictor outputs and not the distribution over instances. This means that MCE can be estimated from data, allowing for practical, data-driven guarantees.

We sincerely thank the reviewer for their detailed feedback. However, we believe there may have been a significant misunderstanding regarding key aspects of our paper. Below, we address each concern in detail and respectfully ask that the reviewer reconsider their evaluation based on these clarifications and feedback from other reviewers.

Motivation of the setting. We believe the reviewer’s concerns stem from a misunderstanding of our motivation for calibrated predictions:

• When stating that learning-augmented algorithms “often assume uniform reliability across all predictions” in the abstract, our intention was to highlight a reliance on global parameters that reflect a user's trust in the predictions in aggregate (e.g., often denoted $\lambda \in [0,1]$ in prior work, with $\lambda = 1$ indicating no trust and $\lambda = 0$ full trust). Our approach uses prediction-level uncertainty from calibration to eliminate the need for parameter tuning. We will revise line 015 of the abstract accordingly. Reviewer eD7y recognized this distinction, stating "this paper bridges the gap between global uncertainty assumptions in learning-augmented algorithms and modern ML models with local uncertainty estimates."
• The reference to “extreme settings” on page 1 was meant only to illustrate the endpoints of the global uncertainty parameter, not to imply that existing work studies these extremes. We will clarify this in line 015, column 2 to avoid ambiguity.

Essential references. We appreciate the reviewer’s insightful connection to distributional predictions. We will cite the suggested references (and “Learning Online Algorithms with Distribution Advice” (Diakonikolas et al., 2021)) in Section 2.1, noting that they are conceptually related but do not study uncertainty quantification.

Regarding the concurrent work (posted on arXiv on 1/22/25) by Benomar et al. (2025), their approach gives average-case bounds for ski rental assuming access to a predictor that correctly guesses $I(Z > b)$ with known probability for any input. This type of assumption — often called “conditional coverage” in the ML literature (see, e.g., “Distribution-free Prediction Bands for Nonparametric Regression” (Lei and Wasserman 2012)) — enables better bounds, but is much stronger than our calibration assumptions.

Performance measures. We strongly disagree that our performance measures are inadequate.

• As Reviewer v9Cf stated, “in theory, the expected competitive ratio is the most common objective and evaluation criterion for these types of algorithms,” supporting our methodology. Indeed, the expected competitive ratio we employ has precedent in sample-based learning-augmented algorithms (e.g., Diakonikolas et al., 2021; Anand et al., 2022), which align closely with our approach.
• We will update our terminology from “additive competitive ratio” to “regret,” as suggested. Many prior works on learning-augmented scheduling algorithms employ regret, with results given as explicit additive bounds (e.g., “Learning-Augmented Algorithms with Explicit Predictors” (Elias et al., 2024); “Non-clairvoyant Scheduling with Predictions (Im et al., 2023)), or later converted to competitive ratios (e.g., “Permutation Predictions for Non-Clairvoyant Scheduling” (Lindermayr and Megow 2022). Though Cho et al. (2022) follow the second approach, bounding expected regret is a core component of their analysis. We will add this context to the third paragraph of Section 2.

Robustness. We agree that our paper differs from traditional robustness analyses. Our primary objective is bounding expected performance degradation based on calibration error (CE), which captures robustness in our distributional setting. We will clarify this after the definition of CE in Section 2. Please see the responses to Reviewers wjo6 and eD7y for discussion on performance guarantees when CE may be large.

“How are MSE and CE related, and can both be 0?” A classic result from “On Subjective Probability Forecasting” (Saunders 1963) decomposes MSE into a sum of non-negative refinement and calibration terms. This means $MSE=0$ implies $CE=0$. We will note this after the definition of CE in Section 2.

“Why MSE and not binary cross entropy (BCE)?” We use MSE because its refinement term arises naturally in our analysis, and its calibration term is a standard error measure. While a similar decomposition holds for BCE, its refinement and calibration terms are not well-suited to our setting. We thank the reviewer for highlighting this mismatch between the error metrics used to train an ML model vs provide performance guarantees; it is a gap that remains between theory and practice, and an interesting question for future work that we will add to Section 6.

“Why is the expected CR at most 1.8 when CE is zero?” When $\alpha=0$, the prediction-level upper bound from Theorem 3.3 achieves a maximum value of 1.8 at $v=0.8$. We will add this brief explanation to Section 3.3.

We thank the reviewer for their thoughtful feedback! We’re encouraged that they find our application of calibration to algorithms with predictions innovative, and our algorithms and analysis novel and interesting. In addition to the modifications detailed below, we will correct the typo on line 776 for the camera-ready version of the paper.

“Does the calibration-based algorithm outperform the conformal prediction method for ski rental?” We see the calibration-based and conformal prediction-based algorithms as two orthogonal approaches with neither being strictly superior. We solely aim to point out (e.g. in lines 42 column 2, 78 column 1, 244 column 1, and Theorem 3.7) that calibration offers advantages in situations where conformal predictors struggle: (1) when only binary targets are available for training an ML model, or (2) there is high variance in the target that is unexplained by the features. In general, the better method will depend both on the underlying ML model and the distribution over features and instances. This can be seen in the ablations for different models in the appendix, and we will modify the conclusion from lines 427-428 column 1 to better communicate this fact.

“Lines 347-348 column 2: what does it mean that the bound is tight?” Thank you for pointing out this imprecise wording. It will be replaced by “the inequalities hold with equality.”

“Why and when is calibration beneficial for algorithms with predictions?” This is a great question. Calibration is beneficial for algorithms with predictions in settings where (1) the goal is good performance over a distribution of instances, (2) there is a binary quantity of interest that is predictable, and (3) probabilistic estimates of this quantity are sufficient to make good decisions. Both case studies we consider fall under this framework. In ski rental, we provide a principled approach for decision making given a probabilistic estimate of whether a skier will ski for at least b days. For job scheduling, there is an optimal scheduling strategy based on the probabilities that each job is high priority.

To see why calibration is beneficial, notice that in a Bayesian sense, the best possible probabilistic estimate of a binary quantity $Y$ given any (potentially untrusted) prediction $f(X)$ of $Y$ is $\Pr(Y=1 \mid f(X))$. Computing these probabilities corresponds exactly to calibrating the original predictor $f$ over the input distribution, but this post-hoc correction is not always possible (for example, if the decision-maker does not have access to the full ML model and data). As a result, (approximate) calibration is a precondition for the decision-maker being able to generate reliable probabilistic estimates of the quantity of interest. If there are no calibration guarantees, we enter the classic realm of algorithms-with-predictions, where algorithms need to be robust against arbitrarily error-prone predictions. This is the reason calibrated predictions are often referred to as “trustworthy.” We agree that a discussion of this kind in Section 6 will help to unify and strengthen the paper, and we thank the reviewer for this recommendation.

“Can experiments vary calibration error while controlling for squared loss?” Because calibration error is an additive component of the mean-squared error — see the response to Reviewer Buyh on their relationship for more details — varying calibration error necessarily changes the mean-squared error. This makes it difficult to design an experiment, such as the one that was suggested, that isolates the effects of calibration error vs overall predictor efficacy.