Algorithms with Calibrated Machine Learning Predictions
Authors: Judy Hanwen Shen
Ellen Vitercik
Anders Wikum
Venue: ICML 2025 spotlightposter (2025)
Keywords: calibration
algorithms with predictions
uncertainty quantification
ski rental
job scheduling
Primary area: theory
TL;DR: Algorithms with predictions does not assume anything about the quality of ML advice, but calibration guarantees are easy to achieve and enable the design of online algorithms with strong average performance.

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 practical impact of calibration for algorithms with predictions.

Algorithms with Calibrated Machine Learning Predictions
Judy Hanwen Shen'
Ellen Vitercik 12
Anders Wikum 2
Abstract
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),
The field of algorithms with predictions incorpo- rates machine learning advice in the design of online algorithms improve real-world perfor- mance. A central consideration is the extent to which predictions can be trusted-whil existing approaches often require users to specify an aggre- gate trust level, modern machine learning models can provide estimates of prediction-leve uncer- tainty. In this paper, we propose calibration as principled and practical tool to bridge this gap. demonstrating the benefits of calibrated advice through two case studies: the ski rental and on- line job scheduling problems. For ski rental, we design an algorithm that achieves near- optrmmp mediction-dependenn 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 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.
This framework often produces a family of algorithms in- dexed by a single parameter intended to reflect the global reliability of the ML advice. Extreme settings of this param- eter yield algorithms that make decisions if the predic- tions are either all perfect or all uninformative (e.g.. Mah- dian et al., 2007; Lykouris & Vassilvitskii, 2018; Purohit et al., 2018; Rohatgi. 2020; Wei & Zhang, 2020; Antoniadis et al., 2020). In contrast, ML models often produce local, prediction-specific uncertainty estimates, exposing a discon- nect between theory and practice. For instance, many neural networks provide calibrated probabilities or confidence in- tervals for each data point.
In this paper, we demonstrate that calibration can serve as a powerful tool to bridge this gap. An ML predictor is said to calibrated the probabilities it assigns to events match their observed frequencies; when the model outputs a high probability, the event indeed likely, and when assigns a low probability, the event rarely occurs. Calibrated predic- tors convey their uncertainty each prediction, allowing decision- makers to safely rely on the model's 's advice, and eliminating the need for ad-hoc reliability estimates. More- over, calibrating an ML model can easily be accomplished using popular methods (c.g. Platt Scaling (Platt et al., 1999) or Histogram Binning (Zadrozny Elkan, 2001)) that re- duce overconfidence (Vasilev & D' y'yaoooov, 2023).
1. Introduction
In recent years, advances in machine learning (ML) mod- els have inspired researchers to revisit the design of classic online algorithms, incorporating insights from ML-based advice to improve decision-makinn in real-world environ- ments. This research area, termed algorithms with predic- tions, seeks design algorithms that are both robust to worst-case inputs and achieve performance that improves with prediction accuracy (a desideratum termed consistency) (Lykouris& & Vassilvitskii, 2018). Many Marning-augmentte
Although are the first to study calibration for algorithms with predictions, Sun et al. (2024) proposed using confor- mal prediction in this setting- common tool in uncertainty quantification (Vovk et al., 2005; Shafer & Vovk, 2008). Conformal predictions provide instance-specific confidence intervals that cover the target with high probability. While these approaches are orthogonal, we prove that calibration can offer key advantages over conformal prediction, espe- cially when the predicted quantities have high variance. In extreme cases, conformal intervals can become too wide to be informative: for binary predictions, a conformal ap- proach returns {0, 13 unless the true label nearly certain to be 1. In contrast, calibration still conveys information that aids decision-making
'Department of Computer Science, Stanford University, Stan- ford, CA, USA DDepartment of Management Science Engineer- ing, Stanford University, Stanford, CA, USA. Correspondence to: Anders Wikum <wikum sddu..
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Algorithms with Calibrated Machine Learning Predictions
1.1. Our contributions
(2022) for a survey). Much of the research provides a pa- rameterized family of algorithms with assumption on the reliability of predictions (e.g., Lykouris & Vassilvitskii, 2018; Purohit et al., 2018; Wei & Zhang, 2020). Subse- quent work has studied more practical settings, such as assuming access to ML predictors learned from samples (Anand et al., 2020), with probabilistic correctness guaran- tees (Gupta et al., 2022), with a known confusion matrix (Cho et al., 2022), or that provide distributional predictions (Dinitz et al., 2024; Angelopoulos et al., 2024; Lin et al., 2022; Diakonikolas et al., 2021). While conceptually re- lated, these papers do not study uncertainty quantification.
We demonstrate the benefit of using calibrated predictors through two case studies: the ski rental and online job scheduling problems. Theoretically, we develop and give performance guarantees for algorithms that incorporate cali- brated predictions. We validate our theoretical findings with strong empirical results on real-world data, highlighting the practical benefits of our approach.
Ski rental. The ski rental problem serves as a prototypical example of broad family of online rent-or-buy buy problems, where one must choose between an inexpensive, short-term option (renting) and more costly, long-term option (buy- ing). In this problem, a skier will ski for an unknown number of days and, each day, must decide to either rent skis or pay one-time cost to buy them. Generalizations of the ski rental problem have informed a broad array of practical applica- tions in networking (Karlin et al., 2001), caching (Karlin al., 1988), and cloud computing (Khanafer al., 2013).
Recently, Sun et al. (2024) proposed a framework for quan- tifying prediction-level uncertainty based on conformal pre- diction. We show that calibration can offer key advantages over conformal prediction in this context, particularly when predicted quantíties exhibit high variance.
Calibration for decision-making A recent line of work examines calibration as a tool for downstream decision- making. Gopalan et al. (2023) show that a multi-calibrated predictor can be used to optimize any convex, Lipschitz loss function of an action and binary label. Zhao et al. (2021) adapt the required calibration guarantees specific offline decision- maainn tasks, while Noarov et al. (2023) extend this algorithmic framework to the online adversarial setting, Though closely related to our work, these results do not extend to the (often unwieldy) loss functions encountered in competitive analysis.
We design online algorithm for ski rental that incorpo- rates predictions from a calibrated predictor. We prove that our algorithm achieves optimal expected prediction-level performance for general distributions over instances and cal- ibrated predictors. At a distribution level, its performance degrades smoothly as a function of the mean-squared error and calibration error of the predictor. Moreover, we demon- strate that calibrated predictions can be more informative than the conformal predictions of Sun et al. (2024) when the distribution over instances has high variance that is not explained by features, leading to better performance.
2. Preliminaries
Scheduling. We next study online scheduling in a setting where each job has an urgency level, but only a machine- learned estimate of that urgency is available. This frame- work is motivated by scenarios such as medical diagnosties, where machine-learning tools can flag potentially urgent cases but cannot fully replace human experts.
For clarity, we follow the convention that capital letters (e.g.. X) denote random variables and lowercase letters denote realizations of random variables (e.g., the event f(X) = v).
algorithm design. With each algo- rithmic task, we associate a set I of possible instances, a set X' of features for those instances, and a joint distribution D over X x I. Given target function T I - y that provides information about each instance, we assume access to a predictor f X + Z 2 y that has been trained to predict the target over DD. Let R(f)) denote the range of f.
We demonstrate that using a calibrated predictor provides significantly better guarantees than prior work (Cho et al., 2022), which approached this problem by ordering jobs based on the outputs of a binary predictor. We identify that this method implicitly relies on crude form of calibration that assigns only two distinct values, resulting in many ties that must be broken randomly. In contrast, we prove that properly calibrated predictor with finer-grained confidence levels provides a more nuanced job ordering, rigorously quantifying the resulting performance gains.
If A(v, i) is the cost incurred by algorithm A with prediction f(X) = on instance i E I, and OPT(i) is that of the offline optimal solution, the goal is to minimize either the expected competitive ratio (CR)
A(J(X), 1)]
1.2. Related work
(X.I)>D
OPT(I)
Algorithms with predictions. There has been significant recent interest in integrating ML advice into the design of online algorithms (see, e.g., Mitzenmacher & Vassilvitskii
or the expected additive regret E depending on context. Both measure the performance of A relative to OPT over D. The former consistent with
-
2

---

Algorithms with Calibrated Machine Learning Predictions
prior work training predictors from samples for algo- rithms with predictions (Anand et al., 2020), while the latter is commonly used to quantify suboptimality in learning- augmented scheduling (Lindermayr & Megow, 2022; Im et al., 2023). When 'D and f are clear from context, we refer to these quantities as [[C and [[)(, respectively.
Algorithm As..
input: prediction s(X) = v, max calibration error a if 0
I 1=30 then
Rent for days before buying.
else
Rent for by /L=tto
days before buying.
v+a
end if
Calibration. An ML model is said to be calibrated if its predictions are, average, correct. Formally,
Definition 2.1. A predictor f X + 2 with target T I-y is calibrated over D if
Predictions. Let X' be set of skier features, I R20 be the set of possible days skied, and 'D be an unknown distribution over feature/duration pairs X x R20. Motivated by the form of the optimal offline algorithm, we analyze a calibrated predictor f X - [0. 1] for the target T(2) = 11 (s>a)) indicating if the skier will ski for more than à days. For (X, 2) D, a prediction of f(X) f(X) 0) means Z b (respectively, Z S b) with high certainty.
(T)) f(X) f(x). (X.1)~D
E
When -= = {0. 1). the equivalent condition (I( = 11 f(X) = fX) requires that f(X) is a reliable probabilistic estimate of the event (T(T)= 13.
(respectively,
classic result from the literature on probabilistic forecast- ing states that calibrated predictions are the global minimiz- of proper loss functions (DeGroot & Fienberg, 1983). However, achieving perfect calibration is difficult in practice. As result, post-hoc calibration methods aim to minimize calibration error, such as the max calibration error, which measures the largest deviation from perfect calibration for any prediction.
Learning-augmentt ski rental. A deterministic algorithm Ag for ski rental takes as input prediction f(X) e and returns recommendation: "rent skis for k(v) days before buying." The cost of following this policy when skiing for 2 days is
Definition 2.2. The max calibration error of predictor f + Z with target T I + y over D is
Ac(u,2) = [(())+ +b
if k(v)
if S k(v)
max I0- - ((T()) f(X) = u||-
VER())
We aim to select k: : [0, 1] + RR to minimize ((CR((A))
Given any black box ML model and sufficient data, these methods yield new predictor with a desired level of cali- bration error with high probability.
3.2. Ski rental with calibrated predictions
In Algorithm I, we introduce a deterministic policy for ski rental based on calibrated predictions. To avoid following bad advice. the algorithm defaults to a worst-case strategy of renting for b days unless sufficiently confident that the skier will ski for at least b days. In this second case, the al- gorithm smoothly interpolates between strategy that rents for b b a)/a days and one that rents for by b/a((1 + a) days, where a E [o, 1] is a bound on local calibration error that hedges against greedily following predictions.
3. Ski Rental
In this section, we analyze calibration as tool for uncer- tainty quantification in the classic online ski rental problem. All omitted proofs in this section are in Appendix A.
3.1. Setup
Problem. A skier plans to ski for an unknown number of days Z E N and has two options: buy skis at one-time cost of b E N dollars or rent them for 1 dollar per day. The goal is to determine how many days to rent before buying, minimizing the total cost. If Z z were known a priori, the optimal policy would rent for b days when buy immediately otherwise, costing min(2,b) b). Without knowledge of z, competitive ratios of 2 (Karlin et al., 1988) and T (Karlin et al., 1994) are tight for deterministic and random strategies, respectively. For convenience, we study a continuous variant of this problem where Z, b, l E R>0 as in prior work (Anand et al., 2020; Sun et al., 2024).
Theorem 3.1. Given a predictor f with mean-squared er- for 1i and max calibration error a, Algorithm achieves E|CR( )] < 1+2a+ + min [X]] + a, 2. 3a
As the predictor becomes more accurate (i.e., both and decrease), the algorithm's 's expected CR approaches 1. The rest of this subsection will build to a proof of Theorem 3.1.
b and
Prediction-level analysis. We begin by upper bounding
E(CR(AA) f(X) = v). Let B, = {x) = 8} be the event that f predicts v E R(f) and C (7 > b} be the
3

---

Algorithms with Calibrated Machine Learning Predictions
Evaluating the right-hand-side of Equation (2) at k. (t) gives
Table Objective values for fixed prediction f(X) = n1 z days skied, and renting for k(e) days.
1 + 2a + (w + a))
if S e S 4+33a
5
CONDITION
OPT(2)
Ae(u,z)
1 ++ + 2
+2 (u +a) 2 +
if 1+
< v S 1.
i v miv( b}
(1) k(t) <
M() +
The fact that + a S 2v - a) 8 a) for
(in) b<zs k(v)
[0. 4+30 and 0 ++ a > 2 (u aa a) [4+30 completes the proof.
for v
(iv) 2 > max, bj
k(()) +
Moreover, no deterministic Garning-auggment algorithm for ski rental can outperform Algorithm 1 for general distri- butions D and calibrated predictors f. The construction is non-trivial, so we refer the reader to the proof in Appendix A.
event that the number of days skied is more than b. Then
E(CR(A.) B+] = E(CR(A:) BN, C) Pr|[|| Bel (1) + E E(CR(At)
Be, C9 Pr[C By]-
Lemma 3.2 bounds each of the quantities from Equation (1). Lemma 3.2. Given a predictor f with max calibration error a, for all C E R(f).
Theorem 3.4. For all renting strategies k : [0, 1] - R.,
predictions e E [0, 1] and e > 0, there exists a distribution Dí and a calibrated predictor f such that
1. Pr[C f(X) = t] uuta
B(CR(AN) | f(X) = e) 2 1 1 min { u,, 2 e(1 - -)}
2. Pr[C"| [x(x) = S a
3. E(CR(AA)] | BB, C7 1 b
k(w)
Global analysis. In extracting a global bound from the conditional guarantee in Theorem 3.3, encounter term (J(X) + a1 f(X) + a) that is an upper bound on the variance of the conditional distribution [(226) f(X).
8-1 (a())))))) 4. E(CR(Ax) | BB, CO < 1 +
k(v)
Lemma 3.5 relates this quantity to error statistics of f.
Proof sketch. (1) and (2) follow from the fact that f predicts 1e with max calibration error a. Under C {2 2 b}, one of conditions (iii) or (iv) from Table 3 hold. In either case, (v, ()) < 1 +
Lemma 3.5. f X - 10, 1] has mean-squared error 1
and max calibration error a, then
k(e). Under C one of for (i). For (ii).
b
([((X)(-((X))) S $1+
conditions (i) or (ii) hold. CR(As)
(v, Z)
k(v) +
b- (((C))<))
OZ S
=+
Finally, we prove this section's 's main theorem.
k(U)
k(v)
Proof of Theorem 3.1. By the tower property of conditional expectation, E(CR(Ax,) = B[E(CR(AA.) s(X)]] Ap- plying Theorem 3.3 yields
Applying all four bounds to Equation (1) yields
E|CR(A)) f(x) u| s (u (u+a)k(v)
E (CR((A.)) )] < + 20x
(R(0)<6) (1- (1-u+ai) a)6
1 2a
E min ax, 2UX
b
k(v)
The renting strategy h: (v) from Algorithm is the mini- mizer of the upper bound in Equation (2).
Recall that (fmin(X,YY) < min(E[X], for ran- dom variables X, Furthermore, the function h(y) = / Vi++ + a) y y a) is concave over the unit interval, so by Jensen's 's inequality
Theorem 3.3. Given predictor f with max calibration error a, for any prediction v E R(f), Algorithm achieves
ECC((A,.) (8(X)= = =
E min 2V
<
1 + 2a + minfu + a. 2/ + a)(1 v v a)).
min Finally, observe that
+a)]
Proof sketch. Given prediction [(X) = v, Algorithm rents for (v) days where
if0 < v < 4+30
(f(x) - f(X) +a) ((x)(1-(xx)) 2a.
k. (v) = by
1-
if 4+30 < < 1.
We apply Lemma 3.5 to bound (I)(()(1
- -((x))
4

---

Algorithms with Calibrated Machine Learning Predictions
3.3. Comparison to previous work
Algorithm (Sun et al., 2024) Optimal ski rental with conformal predictions
Consistency and robustness. It is well known that for À (0, 1), any (1 + -)coosiist algorithm for deter- ministic ski rental must be at least (1 ))robut (Wei & Zhang, 2020; Angelopoulos et al., 2020; Gollapudi & Panigrahi, 2019). While Algorithm 1 is subject to this trade-off in the worst case, calibration provides sufficient information to hedge against adversarial inputs in expecta- tion, leading to substantial improvements in average-case performance. Indeed, it can be seen from the bound in Theo- rem 3.3 that Algorithm I is 1-consistent and always satisfies ((C,(Ar,))) ) I 1.8 when advice is calibrated (a- 0). An analysis similar to that of Theorem 15 in Anand et al. (2020) shows that Algorithm is g(a) rrobust, where
input: interval prediction [c, u] (XP,(X)
if l < 6 then
Rent for days
else if 6 < L S u then
Rent for b- min{ v5/1 8,1 1) days
else
if [(6, 8) 2 and + b then Rent for b days
else if ((,, E) S 5 then
Rent for l. min 65/0611111111 6), } days
else
Rent for u days end if
g(a)= 1
a 1/3
end if
if 2 1/3
8 + (1-5)6
t + 2/
5(1-6)6
if E [0, 848 if 8 E
== ((6,E)
is a decreasing function of a. This is because Algorithm executes a worst-case 2-competitive strategy when a 2 1/3 and never buys skis before day by
1 1 8
L E4b 1
a otherwise.
I+a
must output an interval [e, u] containing both 21 and 22- Moreover, ((d, () 2 2 and 8 + " > 2 by construction.
We note that one can run the same algorithm using an ar- max calibration error to achieve an improved robustness level g(a'). As seen from the bounds in Theorem 3.3 and Theorem 3.1, this adjustment will come at the cost of expected performance, highlighting the tradeoff between average and worst-case performance.
tificial upper bound a'
Theorem 3.7. For all E 1/2], all instantiations A of Algorithm 2 using PIPs with uncertainty 8 < and all distributions from Lemma 3.6, if f is a predictor with mean- squared error and max calibration error a satisfying 2a + 2/4 + 3a < a, then E(CR(Ax. < ((CR(A)].
Uncertainty quantification. We are not the first to ex- plore uncertainty quantified predictions for ski rental. Sun et al. (2024) take an orthogonal approach based on confor- mal prediction. Their method, Algorithm 2, assumes access to probabilistic interval predictor PIPs : X + P[0,, 1)). PIP; outputs an interval [e, u] = (XP containing the true number of days skied Z E [e, u] with probability at least 1 1 J. Interval predictions are especially useful when the uncertainty& d and interval width u are both small.
Proof sketch. For the distributions in Lemma 3.6, the num- ber of days skied is greater than b with probability a. Thus, the expected competitive ratio of the break-even strategy is E[CR(A)]
2 (1 a) 1 1+ The result follows from the bound on E ECCR( (C.....)) given in Theorem 3.1.
4. Online Job Scheduling
In this section, we explore the role of calibration in a model for scheduling with predictions first proposed by Cho et al. (2022) to direct human review of MI.-flagged abnormalities in diagnostic radiology. Omitted proofs from this section can be found in Appendix B.
However, features become less informative, the width of prediction intervals must increase to maintain the same confidence level. This can result in intervals that are too wide to provide meaningful insight into the true number of days skied. Lemma 3.6 and Theorem 3.7 demonstrate that there are infinite families of distributions for which calibrated predictions are more informative than conformal predictions for ski rental.
4.1. Setup
Problem. There is a single machine (lab tech) that needs to process n jobs (diagnostic images), each requiring one unit of processing time. Job i has some unknown prior- ity yi (0.1) that is independently high (vi = 1) with probability p and low (ys = 0) with probability 1 - p. Al- though job priorities are unknown a priori, the priority y is revealed after completing some fixed fraction @ E (0, 1) of job i. Upon learning yi, a scheduling algorithm can choose
Lemma 3.6. For all E [0,1/2], there exists an infinite family of input distributions for which Algorithm 2 de- faults to a worst-case break-even strategy for all interval predictors PIP5 with uncertainty& < a.
Proof sketch. The construction places mass 1 - a on some day 21 S and mass a on 22 2 2b. Any PIP, with 8 < a
5

---

Algorithms with Calibrated Machine Learning Predictions
complete job or switch new job and "store" job for completion a later time. The goal is to schedule the n jobs in way that minimizes the weighted sum of completion times Ei=1 C₃ wy, where C is the completion time of job i, and wi > wp > O are costs associated with delaying a job of each priority for one unit of time. In hindsight, it is optimal to schedule jobs in decreasing order of priority.
Algorithm 3 3-threshold rule
input: Probabilities {pi 1p4)==1 that each job is high priortti
Define n1 = i[ : Pi > (81
Order probabilities P(1) ...2 P(n)
Run jobs J(.) -((n) preemptively, in order
Complete remaining jobs non non-premmptively. in order
ML predictions. Based on the assumption that the n jobs to be scheduled are iid, let X' 23 be set of job features, I {0, 13" be the set of possible priorities, and D Dj be an unknown joint distribution over feature/priority pairs. The prediction task for this problem involves training a predictor ʃ whose target is the true priority of each job T(T)- = y. This amounts to training a I-dimensional pre- dictor f Ny + Z that acts on the n jobs independently: [(x) = (J(X))...., ((X.))
f(X) E and true job priorities Vi,
A(T. 5) - OPT(3)
(3)
= =ww L(.. 17) + Aww M( (ū. 5) + (wi wn) V),
where L(ë, ÿ). M ( 3)) and ( y) count occurrences of (1), (2), and (3), respectively (see Table 2 for details).
4.2. Scheduling with calibrated predictions
Learning-augmenter scheduling. Cho et al. (2022) in- troduce threshold-based scheduling rule informed by prob- abilities p; that job i is high priority based on identifying features (Algorithm 3). Their algorithm switches between two extremes- a preemptive policy that starts a new job whenever the current job is revealed to be low priority, and non-preemptive policy that completes any job once it is begun- besun-based on the threshold parameter
Calibration and job sequencing. To build intuition for why finer-grained calibrated predictors sequence jobs more accurately, we begin by observing that Algorithm 3 orders jobs with the same probability p: randomly. Given cali- brated predictor f. consider the coarse calibrated predictor
f'(x) [[J(X) f(X) > 8] if f(x) 3 ((X)) [[((() f(x) S (] if f(x) S 8
W1
W1 wo
obtained by averaging the predictions of f above and below the threshold 3. Whereas |R(()) may be large, f' is only capable of outputting [R(*)] = 2 values. As a result, when ordering jobs with features X1...., X, according dictions from f', all jobs with f(X)= > B will be sequenced before jobs with f(X) S B, but the ordering of jobs within these bins will be random. In contrast, predictions from f provide a more informative ordering of jobs (Figure 1). Note, however, that f = f' when ʃ has no variance in its predictions above or below the threshold B. We demon- strate in Theorem 4.3 that this intuition holds in general: improvements scale with the granularity of predictions.
In detail, jobs are opened in decreasing order of ps. Jobs with pt >> 33 are processed preemptively, and the remaining jobs are processed non- non-reemptively.
pre-
A auggin-ed algorithm A for job scheduling deter- mines the probabilities p from MI advice. Cho et al. (2022) assume access to a binary predictor fo : No - {0, 13 of job priority and study the case where p; = Pr[Y, = 1 fo(X))] These probabilities can be computed using Bayes' rule, and because fo is binary, this procedure effectively assigns each job one of two probabilities. Although not explicitly dis- cussed by Cho et al. (2022), this amounts to basic form of post-hoc calibration. In contrast,
results extend arbi- trary calibrated predictors f Xy > [0, 1]-a more general framework that calls for new mathematical techniques- allowing us to significantly improve upon their results. In this setting, AA takes the predictions fXX = ö as input and executes Algorithm with probabilities pt = J.
6
5
4
2
S(X)
((X)
5
3
To quantify the optimality gap of A, Cho et al. (2022) note that compared to OPT, Algorithm 3 incurs (1) cost of own for each inversion, or pair of jobs whose true priorities yi are out of order, and (2) a cost of Own for each pair of low priority jobs encountered when acting preemptively. When acting non-nreeen ponn-reemptiill, Algorithm incurs (3) cost of w1 - we for each inversion. Thus, for fixed predictions
Figure I. Job sequencing under fine- fine-erained (above) and coarse (helow) calibrated predictors. For six example jobs, predicted prohabilities p: are marked with x, and numbered boxes give the order of jobs according to each predictor.
6

---

Algorithms with Calibrated Machine Learning Predictions
Table 2. Quantities of interest in leariin--uggmetted scheduling for fixed predictions f(X) and job priorities
Quantity
Description
Relevant setting
A1 = [i: 5 >
3H
Number of jobs likely to be high priority.
L(G,0)- Σ
Σ
Number of inversions among jobs likely to be high priority.
Preemptive
1
g( Σ
Number of low-priority job pairs among jobs likely to be high priority.
Preemptive
j-1+1
N(A,0)) = Σ
Σ =1
(0==) - ((
Number of inversions among job pairs where at least one is likely to be low priority.
Non-preemptive
Performance analysis. Building off of Equation (3), we bound the expected competitive ratio E[CR(A)] by bounding each of [[L(f((X) Y),, ([MM(((X). Y)], and ([)()(X), Y)). The dependence on the ordering of pre- dictions from ff in these random counts means our analysis heavily involves functions of order statistics. For example, considering the shared summand of L(-) and N-).,
This result is sufficient to compute the expectation of (.) exactly. For the other counts, the analysis is more technical as 9(z y) (1 z)y is not symmetric. Lemma 4.2 charac- terizes the relationship between the ordered and unordered expectations for the function g(z, y) = (1 -ryy-
Lemma 4.2. Let XI...., Xn. be iid samples from a dis- tribution over the unit interval [0, 1] with order statistics
(()) 2 2 ((m)- Then,
E 1 1) 1 (8))=1) [x())
(PilTe = =0 =(l ()) Pr(P) 0
E
(1- (1-X(0)- X(i s
-1 (1))(())))(()))
(1 1 x.) .x) x3]
(")
= =))
E
Σ i1i==44
Var(X,))
for the function (zz 3) = (1 z)y. Similarly, the analysis for the summand of (-) yields g (X))) ((G))) for g y) = (1 - 21 - y). Based on this, our high-level strategy is to relate "ordered" expectations of the form
Proof sketch. By Lemma 4.1 with g(x, v) = xy..
"
n
n
n Σ X, X,
Σ
X X
Σ
j=it1
Σ Σ
s ()) j1j=
can be removed from both sides. Then, we apply Lemma 4.1 with g 3) min(x, y) to simplify the left-hand-side.
E
Σ ΣΣ X = Σ
to their "unordered" counterparts
min X())
1=1 1=
E
Σ Σ ,((()), i=1 j=141
Σ
min [X, X²).
1=1 j=++
Finally, we show that EE X - min (X, Z Var(X,). Note that E(X1] E(min X1 X221
which are simple to compute. Lemma 4.1 shows that the ordered and unordered expectations are, in fact, equivalent when the function g satisfies g(x, u) = x(y.x).
=
= E X X2| since
0
if X1 < X₂ X1 X2-
Lemma 4.1. Let XI,..., Xn be iid random variables with order statistics X(1) 2 2 X(n). For any symmetric
X1 min minn(X1,X22]
[X] - Xxel
function R x R + R.
Finally, E E - X21 2 E X1 - X2 2Vr
a
n
Σ Σ 1
g( (1) x = ΣΣ Σ 9(X,, X,). (0);
With careful conditioning to deal with random summation bounds, we apply Lemma 4.2 to bound the expectations of
i=1j=it

---

Algorithms with Calibrated Machine Learning Predictions
L(.) and N-), giving this section's main theorem. Of note, Theorem 4.3 says that the expected number of inversions of high and low priority jobs decreases with predictor granular- ity, measured by K1 and K2. For the method from Cho et al. (2022), K1 = R2 = O and the inequalities hold with equality.
ALG
1.9
Conformal
1.8
Binary
mB Breekeven
ETALGIOPT]
1.7
Calibrated
1.6
1.5
Theorem 4.3. Let f be calibrated, with Pr[f(X) > 8 = 0] = 6o, Pr(f(X) S 3 Y 1| ED,
1.4
1.3
12
K1 = (x) > (/r(ff(f(X) f(X) > 3), and
1.1
K2 Pr(f(X) s 8| Var(f(X) f(X) s 3).
14
16
Breakeven paint (minutes)
Then
Figure 2. Comparison of E[ALG/OPT] for algorithms aided by predictions from a small MLP with two hidden layers of size 8 and 2. Algorithm (CALIBRATED) performs best on average.
1. E(T(((X)))) ())(( p) + t0)ec - K1)
2. []] (1)0--))1-pp))))1))1 (0(1-p))c3 2)PEd
3. B[N(F(X), f (p(1 p) -1) K2) K2)
to ride for longer than the break-even point of minutes, it is cheaper to buy a day pass than to pay by trip duration." We use single-ride durations to approximate the rent vs. buy trade-off for a spectrum of break-even points b. The distribution over ride durations can be seen in Appendix C.
Remark 4.4. A(f(X),-) OPT(.) = 0 when co 61 = 0,
and A inherits the robustness guarantees of Cho et al. (2022) when and are large.
An analogous result holds under the weaker assumption that monotonically calibrated. That is, the empirical frequen- cies Pr[y [(X) are non-decreasing in the prediction f(X). This property holds trivially for calibrated predictors, but zero calibration error is not required. In fact, many cali- bration approaches used in practice (e.g. Platt scaling (Platt et al., 1999) and isotonic regression (Zadrozny & Elkan, 2001)) produce a monotonically calibrated predictor with non-zero calibration error. See Appendix B for details.
We analyze the impact of advice from multiple predictor families, including XGBoost, logistic regression, and small multi-layer perceptrons (MLP). Each predictor has access to available ride features: start time, start location, user age, user gender, user membership, and approximate end station latitude. While these features are not extremely in- formative, most predictor families are able to achieve AUC and accuracy above 0.8 for b >>>>> 6. Figure 2 summarizes the expected competitive ratios achieved by our method from Al- gorithm (CALIBRATED) and baselines from previous work when given advice from a small neural network. Baselines include the worst-case optimal deterministic algorithm that rents for b minutes (Karlin et al., 1988) (BREAKEVEN), the black-box binary predictor ski-rental algorithm by Anand et al. (2020) (BINARY), and the PIP algorithm described in Algorithm 2 (Sun et al., 2024) (CONFORMAL). Though each algorithm is aided by predictors from the same family, the actual advice may differ. For example, CONFORMAL assumes access to a regressor that predicts ride duration directly. While performance is distribution distribution-dependeett we see that our calibration approach often leads to the most cost-effective rent/buy policy in this scenario.
5. Experiments
We now evaluate our algorithms on two real-world datasets, demonstrating the utility of using calibrated predictions. See Appendix for additional details about our datasets and model training, as well broader collection of results for different ML models and parameter settings.'
5.1. Ski rental: Citi Bike rentals
To model the rent-or-buy scenario in the ski rental prob- lem, we use publicly available Citi Bike usage data.?. ? This dataset has been used for forecasting (Wang, 2016), system balancing (O' Mahony& & Shmoys, 2015), and transportation policy (Lei & Ozbay, 2021), but to the best of our knowl- edge, this is its first use for ski rental. In this context, a Citi Bike user can choose one of two options: pay by ride dura- tion (rent) or purchase day pass (buy). If the user plans
5.2. Scheduling: sepsis triage
We use real-world dataset for sepsis prediction validate our theory results for scheduling with calibrated predictions. Sepsis is a life-threatening response to infection that typi- cally appears after hospital admission (Singer et al., 2016).
'Code and data available here: heyyjudes/al a ga- cal i-pred
comm
"The day pass is designed to be more economical for multiple unlocks of bike (e.g., as 66 minutes for unlock). However, ride data is anonymous, so we cannot track daily usage.
*Monthly usage data is publicly available at https:// citi besibikenng kenyc. com/ /sssssysemmmoo data.
8

---

Algorithms with Calibrated Machine Learning Predictions
For ski rental, deriving performance guarantees in terms of binary cross entropy and focusing less rigid calibration measures (e.g. expected calibration error) offer to further close the gap between theory and practice. More broadly, we believe calibration-based approaches offer broad potential for designing online decision-making algorithms beyond these two case studies, particularly in scenarios that require balancing worst-case robustness with reliable per-instance predictions.
Predictor
0.1
Callbrated
0.3
Binary
0.5
E[ALG - OPT]
5
Impact Statement
W. Wi/W/a ratio
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Figure 3. Comparison of E[ALG- OPT] (normalized) achieved by Algorithm for naively calibrated and histogram-binned predictors under varying delay costs wu; wi and information barrier 0.
Many works have studied using machine learning to predict the onset of sepsis, as every hour of delayed treatment is associated with a 4-8% increase in mortality (Kumar et al., 2006; Reyna et al., 2020); existing works aim to better pre- dict sepsis treat high-priority patients earlier. Replicating results from Chicco & Jurman (2020) we train binary predictor for sepsis onset using logistic regression on dataset of 1 10,204 hospital admissions. The base predictor achieves an AUC of 0.86 using age, sex, and septic episodes as features. We then calibrate this predictor using both the naive method from Cho et al. (2022) (BINARY) and more nuanced histogram calibration (Zadrozny & Elkan, 2001) (CALIBRATED). Figure 3 shows the expected competitive ratio (normalized by the number of jobs = 100) achieved by Algorithm& 3 when provided advice from each of these predictors for varying delay costs wI, W0 and information barrier 0. We see that the more nuanced predictions consis- tently result in schedules with smaller delay costs.
A Acknowledgments
This work was supported in part by NSF grant CCF- 2338226, the Simons Foundation Collaboration on the The- ory of Algorithmic Fairness, and a National Defense Science & Engineering Graduate (NDSEG) fellowship. We thank Bailey Flanigan for stimulating early discussions that in- spired us to pursue this research direction, and Ziv Scully for a technical insight in the proof of Lemma 4.2.
References
Anand, K., Ge, R., and Panigrahi. D. Customizing ML pre- dictions for online algorithms. In International Confer- ence on Machine Learning (ICML), pp. 303-313, 2020.
Angelopoulos, S., Dürr, C., Jin, S., Kamali, S., and Renault, M. Online computation with untrusted advice. In Innova- tions in Theoretical Computer Science (ITCS), 2020.
6. Conclusion
Angelopoulos, S., Bienkowski, M., Dürr, C., and Simon, Contract scheduling with distributional and multiple advice. In Proceedings of the International Joint Confer- ence Artificial Intelligence (IJCAI), 2024.
In this paper, we demonstrated that calibration is powerful tool for algorithms with predictions in settings where per- formance is measured over a distribution and probabilistic estimates of a binary target enable good decisions. In par- ticular, calibration bridges the gap between traditional the- oretical whhho treat all predictions equally reliable-and modern ML methodologies that offer fine- grained, instance-specific uncertainty quantification. We focused on the ski rental and online scheduling problems, developing online algorithms that exploit calibration guaran- tees to achieve strong average-case performance. For both problems, we highlighted settings where our algorithms out- perform existing approaches and supported these findings with empirical evidence real- world datasets.
Antoniadis, A., Gouleakis, T., Kleer, P., and Kolev, P. Secre- tary and online matching problems with machine learned advice. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Chicco, D. and Jurman, G. Survival prediction of patients with sepsis from age, sex, and septic episode number alone. Scientific reports, 10(1):17156, 2020.
Cho, W.-H., Henderson, S., and Shmoys, D. Scheduling with predictions. arXiv preprint arXiv:2212.10433,, 2022.
DeGroot, M. H. and Fienberg, S. E. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society, Series (The Statistician), 32(1):12-22, 1983.
This work exposes a number of directions for future research.

---

Algorithms with Calibrated Machine Learning Predictions
Diakonikolas, I., Kontonis, V., Tzamos. C., Vakilian, A., and Zarifis, N. Learning online algorithms with distributional advice. In International Conference on Machine Learning (ICML), pp. 2687-2690 2021.
Lei, Y. and Ozbay, K. A robust analysis of the impacts of the stay-at-home policy on taxi and Citi Bike usage: A case study of Manhattan. Transport Policy, 110:487-498, 2021.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., Niaparast, A., and Vassilvitskii,, S. Binary search with distributional predictions. In Conference Neural Information Pro- cessing Systems (NeurIPS), 2024.
Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Ma- chine Learning (ICML), 2022.
Lindermayr, A. and Megow, N. Permutation predictions for non-clairvoyant scheduling. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 357-368, 2022.
Gollapudi, S. and Panigrahi, D. Online algorithms for rent- or-buy with expert advice. In International Conference on Machine Learning (ICML), 2019.
Gopalan, P., Hu, L., Kim, M. P., Reingold, O., and Wieder, U. Loss minimization through the lens of outcome indis- tinguishability. In Innovations in Theoretical Computer Science (ITCS), 2023.
Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. In International Conference on Machine Learning (ICML), 2018.
Mahdian, M., Nazerzadeh, H., and Saberi, A. Allocating online advertisement space with unreliable estimates. In ACM Conference on Economics and Computation (EC), pp. 288-294, 2007.
Gupta, A., Panigrahi, D., Subercaseaux, B., and Sun, K. Augmenting online algorithmss with e-accurate predic- tions. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Communications of the ACM, 65(7):33-35, 2022.
Gupta, C. and Ramdas, A. Distribution-fiee calibration guar- antees for histogram binning without sample splitting. In International Conference on Machine Learning (ICML), 2021.
Noarov, G., Ramalingam, R., Roth, A., and Xie, S. High- dimensional prediction for sequential decision making. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
Im, S., Kumar, R., Qaem, M. M., and Purohit, M. Non- clairvoyant scheduling with predictions. In ACM Sym- posium on Parallelism in Algorithms and Architectures (SPAA), 2023.
O' O'Mahony, E. and Shmoys, D. tion for (Citi) bike sharing. In Proceedings of the AAAI conference on artificial intelligence, volume 29, 2015.
Data analysis and optimiza-
Karlin, A. R., Manasse, M. S., Rudolph, L., and Sleator, D. D. Competitive snoopy caching. Algorithmica, 3(1-4), 79-119, 1988.
Platt, J. et al. Probabilistic outputs for support vector ma- chines and comparisons to regularized likelihood meth- ods. Advances in large margin classifiers, 10(3):61-74, 1999.
Karlin, A. R., Manasse, M. S., McGeoch, L. A., and Owicki, S. Competitive randomized algorithms for nonuniform problems. Algorithmica, 116))5522-57, 1994.
Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via MI predictions. In Conference on Neural Information Processing Systems (NeurIPS), pp. 9661 9670, 2018
Karlin, A. R., Kenyon, C., and Randall, D. Dynamic TCP acknowledgement and other stories about e/(e-l). In Proceedings of the Annual Symposium on Theory of Com- puting (STOC), pp. 502-509, 2001.
Reyna, M. A., Josef, C. S., Jeter, R., Shashikumar, S. P., Westover, M. B., Nemati, S., Clifford, G. D., and Sharma, A. Early prediction of sepsis from clinical data: the phys- ionet/computing in cardiology challenge 2019. Critiiall care medicine, 48(2):210-217, 2020.
Khanafer, A., Kodialam, M., and Puttaswamy, K. P. The con- strained ski-rental problem and its application to online cloud cost optimization. In Proceedings IEEE INFO- COM, pp. 1492-1500. IEBE, 2013.
Kumar, A., Roberts, D., Wood, K. E., Light, B., Parrillo, J. E.. Sharma, S., Suppes, R., Feinstein, D., Zanotti, S., Taiberg, I.,, et al. Duration of hypotension before ini- tiation of effective antimicrobial therapy is the critical determinant of survival in human septic shock. Crttical care medicine, 34(6):159-1156 2006.
Rohatgi, D. Near-optimal bounds for online caching with machine learned advice. In Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA), 2020.
Shafer, G. and Vovk. V. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
10

---

Algorithms with Calibrated Machine Learning Predictions
Singer, M., Deutschman, C. S., Seymour, C. W., Shankar- Hari, M., Annane, D., Bauer, M., Bellomo, R., Bernard, G. R., Chiche, J.-D., Coopersmith, C. M., et al. The third international consensus definitions for sepsis and septic shock (sepsis-3). Jama, 810880000--810 2016.
Sun, B., Huang, J., Christianson, N., Hajiesmaili, M., Wierman, A., and Boutaba, R. Online algorithms with uncertainty-quaatt quanttifiid predictions. In International Con- ference on Machine Learning (ICML), 2024.
Vasilev, R. and D' yakonov, A. Calibration of neural net- works. arXiv preprint arXiv:2303.10761, 2023.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in random world, volume 29. Springer, 2005.
Wang, W. Forecasting Bike Rental Demand Using New York Citi Bike Data. PhD thesis, Technological University Dublin, 2016.
Wei, A. and Zhang, F. Optimal robustness-consisee trade-offs for baaming-augmenter online algorithms. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Zadrozny, B. and Elkan, C. Obtaining calibrated probability estimates from decision trees and naive bayesian classi- fiers. In International Conference on Machine Learning (ICML), pp. 609-616, 2001.
Zhao, S., Kim, M. P., Sahoo, R., Ma, T., and Ermon, S. Calibrating predictions to decisions: A novel approach to multi-class calibration. In Conference on Neural Infor- mation Processing Systems (NeurIPS), 2021.

---

Algorithms with Calibrated Machine Learning Predictions
A. Ski Rental Proofs
Lemma 3.2. Given predictor f with max calibration error o, for v E R(f),
I. Pr[C [ = t| v0
2. Pr[C" [(X) = v) S -
3. E(CR(As)) Bo, C 5 1 b
k(w)
4. E(CR(A)) Beg [²] _ + bi (e(mes))
k(v)
Proof. Recall that B& (f(x)) f is the event that f predicts R(f), and C {2 6} is the event that the true number of days skied is at least b. Because is predictor of the indicator function lc with max calibration error
Pr[C B.] Pr Z f = 2) a. Suta
and
Pr(C') | = P
b f(x) = =1 -1-
This establishes (1) and (2). In the remainder of the proof we will reference the costs from conditions (t)-(tu) in Table 3.
(3) E(CR(AA)) B,, CJ S + k(e) Under the event C (Z b), one conditions (iii) or (iv) must hold. The bound tight when condition (iv) holds. Under condition (iit), must be that Z S k(v),
ALG(A&, ((X), Z) k(U)
S + k(v)
OP)(Z)
b
(4) B(CR(AA)] Be, C9 5 (M00<0) k(O)
Under the event C (Z < b), one of conditions (t) (ii) hold. The bound is trivial under condition (t). Under condition (it), because k(v) < Z and Z < b. ALG(AR, f(X), OPT(Z)
k(D) + k(v) +6
1 [((())0)) k(v)
k(v)
Theorem 3.3. Given a predictor I with max calibration error a, for any prediction v E R(f), Algorithm achieves
E,C((A.)) ( u)
1 + 2a + min a a, (b
Proof. Let B, = {S(X) = 0) be the event that f predicts v E R(f), and let = (2 > b} be the event that the true number of days skied is at least By the law of total expectation and Lemma 3.2,
E(CR(As) B₂] = Pr[C B.] E(CR(As)
C. + Pr(C" Bb] (()R((()(AA)) | C", B.]
< (v a
k(v) 1
+ - -
(1 1 1 k(o)
b
b
(o + k:)(())
(1-u+a)u
= + 2o +
+ (M())<))))
k(v)
Finding the number of days to rent skis that minimizes this upper bound on competitive ratio amounts to solving two convex optimization problems - one for the case k(v) < b, and a second for ki(v) 2 - then taking the minimizing solution.
(v + a)l (1 + a)b
(u aae
(a) Minimize
+ 2a
(b) Minimize
1 2a +
b
s.t. <b
S.t.
{>
12

---

Algorithms with Calibrated Machine Learning Predictions
Note first that (b) has optimal solution (. b. The Lagrangian of (a) is
a)+
b + (1 - -1-u+ai adb
(((,)1,d2)= = 2a +
+ +all 6) Aze
with KKT optimality conditions
U + a
U--+oo
+ \1 X2 =0
f
8 b
- 5 0 X1 Ao 2 0
A1 b) = 0
22 ()
We'll proceed by finding solutions to this system equations via case analysis.
1. X + 0. Then, é = 0 and A = 0 by complementary slackness. But at least one of the stationarity or dual feasibility constraints are violated, since
v + a (1 - u a X2.
b
2
2. A2 0 and A1 * 0. Then, é= b by complementary slackness. Stationarity and dual feasibility are satisfied only when
0 S S 0.5, since in this case
v + a
1 1
~1 S0. O.
b
b
3. A2 0 and Å = 0. Then, the first constraint gives that
(1- (1-0
a
Recall that 0 S é < 6, so this constraint is only satisfied when 0.5 S S and l = by I-uto
0.5, it must be the that (,) b if 0 U 0.5. When 0.5 1, the optimal solution to (a) is l, bv 1-v+a and the optimal solution to (b) is l, b.
Because l. b is the optimal solution to both (a) and (b) when 0
v+a
The value the former 1 1 2a + 2 + a)(1 + a), while the value of the latter is + 2a + v + a. Taking the argmin yields
[b
if < 1+3a
(x)
bb/
1-v+0 v+a
if 1+3a < v < 1,
which is exactly Algorithm 1 and achieves competitive ratio of
E(CR(A..) v| s 1 2a + min(u (v
Theorem 3.4. For all renting strategies le [0, R4,, predictions [0, and e > O, there exists a distribution D and calibrated predictor f such that
IE (R(As) f(X) = o] 2 1 min (,,2/e(1 u(1 -0)
13

---

Algorithms with Calibrated Machine Learning Predictions
Table Objective values fixed prediction f(X) = v, = days skied, and renting for k(()) days.
CONDITION
OPT(2) e,,
(i) < min(k(v), 6}
2 k(v) + k(v) +
(i) k(e) < 2 b
(ii) b b< k(o)
(iv) = max(k(() b}
Proof. Let e e [0, 1] and > The calibrated predictor f will deterministically output v, while the distribution D5 will depend on whether algorithm A& buys before or after day b.
Case 1: k(v) b. Define distribution D where in fraction of the data the true number of days skied is b b+ e', and in a 1 fraction the number of days skied is = k(e) + c', where e' is sufficiently small that
and 2 vve(1 (01--)) v) (1-5)
2ve'
k()) + + b
22 - v)
6
b t
By construction, condition (ii) from Table 3 is satisfied when k(v) < b < b+ é' with
ALG(AAR, v, v,=)),o((3))) = k(v) +
b+c = 1 k(v) -
b+
Similarly, condition (ii) holds when k(o) < === k(v) + b with
k(v) +
b b- k(0) +e¹
o, 0, (O)P((()
=1
k(w) +
By the law of total expectation,
B[CR(As)) = (1+ k(v)
+ e' )
+ +(1 +1--o). (1+
v)
b b-é'
k(v) +c
1 f - 6'
+ + -) (1 (1+ e+c
b-c
2 min 220
v.
b + e
Some basic calculus yields l, =
1- (b ed)(b= e¹) - e'. and evaluating the lower bound at e" gives 0
2ve' b+c' + +2 o(1 /2/00110 v) 1(10 (1-
B[CR(AA)]
+2
21+2 0(1 v) -c
Case 2: k(v) 2 b.
Define a distribution D, where in a v fraction of the data the true number of days skied is z k(v) + and 1 fraction the number of days skied is b Condition (tv) is satisfied when b & k(v) < k(v) with ALG(A v, OO)()) = 1+ k(e) Condition (i) is satisfied when 2 = b-e S k(v) with u, 1. By the law of total expectation,
E [CR(AN) - (1+ k(U)
+(1 v)
20-2+ (1 v)
=1
14

---

Algorithms with Calibrated Machine Learning Predictions
In both cases, f is calibrated with respect D since Pr[z b f(X) v) Moreover, because the cases exhaustive, at least of the corresponding lower bounds must hold. It follows immediately that
E(CR(AA) f(X) =] 2 1+ min {o. 2, - -
Lemma 3.5. Iff X + [0, has mean-squared error vn and max calibration error then
Blf(x) ((x))((-((())) s
Proof. We have from the law of total expectation that
(L(z>6) f(x))=
n
(x
Σ E
(1(226) - -)² s(x) = =u] Pr(s(()= = =
.ER(S)
Σ vER())
(E (226)) |XXX= o 2v [2200 [S(X) o| + 0²) (r( v).
Applying the definition of the local calibration error Cres
Σ
(E [[226]] I(X) 2u [1 1S(X) u| 0²) (X)) =
WE R(f)
Σ vER(f)
(0- av) - -20( an) + x²) Pr (r( v)
Σ vER(F)
(u(1 - v) + (2u - 1)ax) (x) = v)
(1-(X))(1((x)) +
Σ (2v 1)a, Pr Pr(f((X) v].
HER(J)
The observation that (2v 1)a. 2 aaal gives the result.
Theorem 3.1. Given predictor with mean-squared error and max calibration error a, Algorithm I achieves ((CR(AAR)) < 20 + min {X[ + 20,2v1 30).
Proof. This result follows from Theorem 3.3, Lemma 3.5, and application of Jensen's 's inequality. To begin,
E|CR(Ar.) [EECCR(A,.) f(X)]]
(Tower property)
+ < ++ 2a min +(]((X)+aa225)) (iae[V/Flstt ((f(X) f(x) +
1 2a min + (V
(Theorem 3.3)
with the final line following from the fact that E[min(X, Y)] min E() for random variables X, Next, we argue from basic composition rules that the function g / (y + a1 - y + a:) concave for y [0, 1]. The concavity of g over its domain follows from the facts that (1) the V- function is concave and increasing in its argument and (2)
(y + a)(1 y + a) is concave. Moreover, g is well-defined for all y [0, 1]. With concavity established, an application of Jensen's inequality yields
E(CR(A, 5 + 2a + min [E(((X) a. 2 +a]
15

---

Algorithms with Calibrated Machine Learning Predictions
To finish the proof, will bound the term within the square root using Lemma 3.5. Notice that
f(x) + = f(X) f(X)) a
S)(X( -(()) 2a.
Finally,
C(R((As.) S + 20 min { [[(( + (.2
S +1+ 2a min
E [f()) a. 2
(Lemma 3.5)
Lemma 3.6. For all [021 there exists an infinite family of input distributions for which Algorithm 2 defaults to worst-case break-even strategy for all interval predictors PIP; with uncertainty ó
Proof. L E [0, 1/2] and consider distribution that, for each unique feature vector X, has true number of days skied that is either S with probability 1
2 2b with probability a. By construction, any interval prediction (X)) = [e, u] with 8 < min 1 - a} must satisfy that S 21 and 2 This means b E [e, u]. so Algorithm 2 makes a determination of which day to buy based on the relative values of (6,, f). 5 + 5. and 2. In particular, the algorithm follows the break-even strategy of buying on day when ((6, 2 and + E 2 2.
is clear that +
IV
22 2 2. Next, recall the definition of ((6, E).
8 + (1 1 5) + - 6)b/6 if [0, 644
C( =
1 11
i 1847 1]
When d > L.
6F7. we see that ((,,6) 1 + 2 3. To handle the case where ô <
f 6F2.
we will show that
f(6,x) 6 + (1 8) + 2/ 6(1 8)x 2
for all x 2 2 and 8 E 1/2]. Plugging in - > 2 and noting that ô .ー7 < 0.5 implies the desired bound. Toward that end, notice that f(ō, æ) is increasing in æ, and so for all x > 2 have that
f(6,z) 2 f(, 2 - 6 2 - 6).
All that is left is to show that 2 -
8) 8)2 1222 6. This is straightforward: for d E [0, 1/2).
2 2/ 21
and multiplying through by v8 gives the desired inequality. In summary, we' ve shown that b E [e, u], ((5, 2) 2 and 8 + u 2 for the family of distributions described above. For this particular case, Algorithm 2 rents for b days.
Theorem 3.7. For all a [0, 1/2), all instantiations A of Algorithm using PIPs with uncertainty 5 a, and all distributions from Lemma 3.6, is predictor with mean-squared error n and max calibration error satisfying 20: + 2/n + 30 a, then ((CR(Ae.)) < E(C)(A)).
Proof. a E [0, 1/2 and consider any distribution from the infinite family given in Lemma 3.6. In particular, in any of these distributions, the number of days skied is greater than b with probability Therefore, the expected competitive ratio of the break-even strategy that rents for b days before buying is
IE (CCR(A)) = a 2 (1 aa) +
The result follows from the bound on E(CR(Ar.) from Theorem 3.1.
16

---

Algorithms with Calibrated Machine Learning Predictions
B. Scheduling Proofs
Lemma 4.1. Let XI...., Xu be iid random variables with order statistics ((1) 2 ... 2 (()) For any symmetric function
R X R.
(() x()) Σ Σ Xy).
1m2+11
i= 1=2+1
Proof. Beginning with the facts that
(X (6))
ΣΣ5 XX), and Σ (X(i), X() = Σ X(X;,
i=1==1
;=
follows from the symmetry of g that
Σ (X)0))))) #1
Σ
g( (())
Σ g(x X(1))
1
9 (X,
Σ gx(X
2
i=1
Σ
Σ
X))
Lemma 4.2. Let X1,... Xn be iid samples from distribution over the unit interval [0, 1] with order statistics X(1) 2
2 X(n)- Then,
E
(1- (1- X() X(I
11+1
E
Σ Σ (1 - X1) X3
n2
Var Var(X)).
2
=1j=
Proof. We'll begin by removing shared term from both sides of the inequality. Notice that
ΣΣ
X X
X,X,
Elj=++1
i=1
j=it1
by Lemma 4.1 with g(2,8) zy. So, is sufficient to show that
n1 Var(X,).
E
X
E
Σ
(
>
By linearity of expectation, the first on the left-hand side is equal to (3) E[X1]. The random variables the second term are not identically distributed, however, different approach is required. We will use trick express the in terms of the symmetric function g(z,y) = min(x; v), which allows us to remove the dependency order statistics using Lemma 4.1.
Σ
X
Σ
min ( X()}
(X() 2 X since i < ;)
j=i=l
im1 j +1
min,X,,X,L
(Lemma 4.1 with g(r, y) = min(x,
1=1 -1j=
17

---

Algorithms with Calibrated Machine Learning Predictions
Thus, the second term the RHS equal min X1, X2)). All that is left is show that
B
[1
B min { X1, X 2 Var(X1).
Toward that end, can write
0
if S X2
X1 min(X1, X2)
|X X2l
i > X2:
so B[X]]
[[min(XX,, X23]
B [
X2/. Finally, using the fact that [X X21 [o, 1] are iid, we have
1
B|x, X2| 2 2 E((X, - X2)²
2
[X] - 2X + X3]
1
2 22.2 (E{{}]] - E(x,1²)
Var(X1).
Theorem 4.3. Let f be calibrated, with Pr[f(X) > 8 Y = = = =4
S =
Pr[f(X) Var((()( [(()) > >)) and
K2 Pr(f(X) s $/2 Var(f(X)) [f(X) s B).
Then
1. E[I(((}) 8)] (2( p)]1 ca)c -k1)
2. [M] (0]1-p)eed
3. E[N(F(X) F)] ())
(p(1 - p))o(1 - -1) K2) K2)
Proof. We relax the calibration assumption and only assume that f is monotonically calibrated, a weaker condition that the empirical frequencies Z = Pr(Y
f(X)] are non-decreasing the prediction f(X). Given jobs to schedule with features X = (Xi...., X,.) and the predictions ʃ(X) = (J(X)),.... f(X,)), let nı Ki : f(X;) > /831 be
random variable that counts the number of samples from f with prediction larger than 3, and define random variables Z; Pr[y, [(x))] which give empirical frequencies. We'll begin by computing expectations conditioned on n1
before taking outer expectation.
((((((),)))
ml
E
B
BLL(((()
m
(Tower property)
11
E
E
Pi 1186,)=1 1(x))
n1
(Definition of X)
T
Pr(y = ((x Pr(Vos =1 =1)((x)))
(Independence)
72
Σ (1- Z6)) mm
j=it1
Performing the same computation for counts M(.) and N(.) yields
([M((()) Y) mil
Σ (1-Z4)) --))))) (1- ZG)) n
J=++1
18

---

Algorithms with Calibrated Machine Learning Predictions
and
11
n
E| (((((()) m== = E
Σ
Σ
(1- (3)) 2 m
+ E
Σ
Σ (1 j=++1
2(0) (,0) m
i=1
1= +1
1=
At this point, we can compute the conditional expectation of M() directly. By Lemma 4.1 with g(x, (1 x) y).
m1 Σ
E
(1- (L-
(( (1) lm1 m
-++1
R1
E
(1- (1 2z) m
(Lemma 4.1)
1=+11
m1
E Pr(y = 0 [(x)) 18(X) > }3²
(Independence)
2
n1
Pr|Y = -01 > Bp
(Tower property)
2
11 eg(1 - p)} Pr(f(X) 3/2
(Bayes' rule)
2
The same technique cannot be used to evaluate the expectations of L(-) and N(-)) because the function g(x, y) = (1 - 1)y not symmetric. Instead, we will provide upper bounds on conditional expectations using Lemma 4.2, then evaluate the unordered results as before. For the conditional expectation of L(-), have
(1 ((0) ZG) n1
n1
n1 (m)) Var 1f(x) > B)
$ E
(1- 2i) -3 |m1
(Lemma 4.2)
j=1+1
n1
Pr(y 01 -((((x) > B = [((X) > 3 Var(Z (a((21((X)= > 8))
2
n1
(p(L- () Var(Z f(X) > 3)
2
Pr(f(X) B|
Similarly for the conditional expectation of the second term N(.),
Σ Σ (1
(1-Z(1) Z n4
j=i+1
n Σ
nn m
E
Σ (1 Z 2, n1
Var(Z (fX) $B
(Lemma 4.2)
2
j=nt+ j=i+1
n n- n1
Pr|Y 0 f(x) 58) Pr(Y = 1 f(X) = 3] Var(z Var(Z11(X) ( E3)
2
n n1
(p( -0) Var f(X)= < 9)
2
Pr(f(X)= < 3)
For the first term of (N). we simply apply the rearrangement inequality in lieu Lemma 4.2 for unordering, Note that the sum has the form Σ, a: b. where a; (1 Z()) and Σj ZG)- The sequence {a, 1n is non-decreasing as
19

---

Algorithms with Calibrated Machine Learning Predictions
result of the monotonic calibration of J. and {b is non-increasing. Thus,
A 12
A1
Σ
(1 (1- (0) n
(1- Z, n1
J=
j=
n1 n1) Pr[Y 01 f(X) > 3] -r = f(X) S
r p)6160
=n ni) Pr[S(X) > 3] Pr(S(X)
Next, we take an outer expectation to remove the dependency on n1. Recall that ny follows Binomial(n,, (rnlf 8]) distribution, can easily verify that
1. ( (5) Pr(f(X)= > 87²
2. (l((("""""" (5) (1 Pr[ > 8)2 (5) Pr(j(X)= s $
3. Enni(n - m1)] = 2(2) Px(f(XX) > B] Pr(f(X) s 3).
follows immediately that
Y) m1]]]
2 (7) ( [(1
n1
(pl) - p) 61 61)60 Var(Z 8))
S
Pr[f(X) B12
= ()) (0(1 - () =I)EE0 K5
{[M(((X), ()] = (f(X), m1]]
<6(1 - 0)
=E Pr(f(X) > 8|3
n1 (1) (1 0)2E8
(( B 8) mil
n -
p)(1 (10-p)(1(aa))) co)c - Var f(X) s 20)]
E
Pr(f(X) s 3/2
p( (1-Pl p(1-)) n2 (n n1) Pr(f(X) Pr( s [
+
ng
(pl1 p) - -coc (cc)cc 2p(1 -)c R2
2
(pll p) co)cc K22
2
where
= Pr(f(X)) > 8/2 (Z fx() > 3) and K2 = Pr(f(X) - 3 -ar22 f(X) S $).
The observation that Z f(X) when ff is calibrated gives the result from the main body.
C. Experimental Details
C.1. Ski-Rental: CitiBike
Our experiments with CitiBike use ridership duration data from June 2015. Although summer months have slightly longer rides, the overall shape of the distributions similar across months (i.e. left-skewed distribution). Figure illustrates the
20

---

Algorithms with Calibrated Machine Learning Predictions
Distribution of target values for CitiBike dataset June 2015 (25th, 75th) quantiles
Count
5
10
15
20
25
30
Ride Duration (minutes)
Figure 4. Distribution of ride times and quantiles in minutes, most rides are under 900 minutes.
Accuracy and AUC of Predictors by Feature Information (b#600)
Accurscy
AUC
0.4
info
Info
none
none
partal
parsal
0.0
0.0
Classiferr
Classifier
Figure 5. Predictor accuracy with different features around final docking station, no information, partial information (approximate latitude), and information (approximate latitude and longitude).
distribution of scores. This indicates that using this dataset for ski rental, the breakeven strategy will be better as increases since most of the rides will be less than b. This an empirical consideration of running these algorithms that prior works do not consider. Thus, we select values of b between 200 and 1000 reasonable interval for comparison.
Feature Selection The original CitiBike features include per-trip features including user type, start and end times, location, station, gender, and birth year of the rider. We tested predictors with three types of feature: no information about final destination, partial information about final destination (end latitude only), and rich information about final destination (end longitude and latitude). Even with rich information, the best accuracy of the model's we consider are around 80% accuracy. This is because there are many factors affecting the ride duration. However with no information about the final destination, many of our models were close to random and thus do not serve as good predictor (Figure 5),
Model Selection We tested a variety of models for both classification (e.g. linear regression, gradient boosting, XGBoost, k-Nearest Neighbors, Random Forest and a 2-layered Neural Network) and regression (e.g. Linear Regression, Bayesian Ridge Regression, XGBoost Regression, SGD Regressor, and Elastic Net, and 2-layered Neural Network). ended up choosing three representative predictors of different model classes: regression, boosting. and neural networks. To fairly compare regression with classification choose similar model classes: (Linear Regression, Logistic Regression), (XGBoost, XGBoost Regression), and two-layer neural networks.
Calibration
To calibrate out-of-the box model, we tested histogram calibration (Zadrozny & Elkan, 2001), binned calibration (Gupta & Ramdas, 2021), and Platt scaling (Platt et al., 1999). While results from histogram and bin calibration
21

---

Algorithms with Calibrated Machine Learning Predictions
:[ALG/OPT) for Gitikie Ride Duration Rent))) chXG8 reg (no info)
#[ALGIOP(] for GRiBkee Ride Duration (5k) Rentag cIXXS5 mggX0BB gportal info)
4EALG/OP) for GRB Rite Duration (5k: Rental)
clxXS mgg otch intoo
ALG
ALG
Contoral
Corformal
Bisery
1.8
ETALGIOPT
brated
EIALGIOP1)
Collrated
FTALGIOPT]
1.6
1.4
1.6
1.4
12
Breakeven point (minutes]
Breakoven point (mitutos)
Breakevon point (minutos)
(a) No info about ride end station
(b) Partial info (approx end latitude)
(c) Rich info (approx end long. and lat.)
Figure 6. XGBoost predictors generally enable the calibrated predictor algorithm do better than other baselines.
C/OPT ke fide Dunation (Stk-endee) riggR info)
ETALGIOPT]] for CHiBke Ride Duniion (SNi-Rental) df rigi (pwrlil info)
ZEALG/OPTT C&B Dunation (Sk--Re dfiL rigi (fihh ido)
2.0
ALG
Conformll
ALG
Confomal
1.9
ALC
Contorna
Bisay
Brary
Bray
Broanivven
Broakuzon
Bruskover
STALCIOPTI
Cal Brine
E|ALGIOPT]
Callorated
1.6
1.6
1.5
1.3
12
1.2
1.2
14
16
Breokvwnn (minutee)
Breskewen point (minstww))
Braniowen (minudedl)
(a) No info about ride end station
(b) Partial info (approx end latitude)
(c) Rich info (approx end long. and lat.)
Figure 7. Linear regression and logistic regression remains similar to break even stretegy regardless of the features used.
:EALG/OPTI Duration (ent)))
FAALGIOPT] for CHBike Duration (9K) Rental)
#TALG/OFT] Duration Rantal)
dttNNN rog.NN Info)
rog.NN portallins)
dit.NN rog/NN yich
ALB
Contormal
Conform
Conterne
1.8
Bineyy
1.8
Btrayy
1.8
Brer
Breasoven
Braskeven
Breakowen
Cul bradue
Caloruled
[ALGORT]
Cal culbroodd
16
3.6
1.6
1.4
1.4
1.4
1.2
1.2
1.1
50
12
14
16
10
12
14
16
10
12
Braakovan point (minnttos)
Breakeven point (minnttss)
Breaksvon point (minudes)
(a) No info about ride end station
(b) Partial info (approx end latitude)
(c) Rich info (approx end long. and lat.)
Figure 8. Neural network predictors generally enable calibrated predictor algorithm to do better than other bascline when there are informative features
22

---

Algorithms with Calibrated Machine Learning Predictions
F[ALG OPT] for Sepsia Scheduling(LR)
ZIALG OPT] for Sepais Scheduling(NN)
FTALG OPT] for Sepeis Scheduling(XGB)
Predector Callbrattdd
Phecictor
Prediddr
0.1
0.1
Callbrot Brattd
0.1
Collbrated
0.3
Birary
0.5
Binary
ETALG OPT1
ETALO
2
5
6
7
2
At//alo ratlo
Layllds 1890
0r/ rao
(a) Logistic Regression
(b) Layer Neural Network
(c) XGBoost
Figure 9. Comparison of different base models. As 0 increases the perforance of the calibrated preditctor becomes more similar to the binary predictor.
were similar, Platt scaling often produced calibrated probabilities within a very small interval. Though it is implemented in our code, we did not use it. A key intervention we make for calibration is to calibrate according to balanced classes in the validation set when the label distribution is highly skewed. This approach ensures that probabilities are not artificially skewed due class imbalance.
Regression For regression model as fair comparison, we assume that the regression model also only has access the 0/1 labels of the binary predictor for each b. To use convert the output conformal intervals to be used in the algorithm from Sun et al. (2024), we multiply the 0/1 intervals by b.
C.2. Scheduling: Sepsis Triage
Dataset We use dataset for sepsis prediction: 'Sepsis Survival Minimal Clinical Records'. This dataset contains three characteristics: age, sex, and number of sepsis episodes. The target variable for prediction is patient mortality.
Additional Models We also include results for additional base models: 2 layer perception (Figure 9b) and XGBoost
(Figure 9c)
'https://archive ics. ies. usi wtw../.i.eee//aatteeeee////e /ttp////////seeeee wwwnimalmmmmmmmmmmmmmmmmmmmmmmam Hel in ca +records
23


Reviews:
[{"review_id": "i766PBnFQu", "reviewer": "Reviewer_v9Cf", "summary": "The paper initiates the study of the effect of calibration in algorithms with predictions through two case studies:\n1. Ski Rental: The authors design an algorithm that achieves optimal prediction-dependent performance, bounding the expected performance using both the squared error and the calibration error. They proved that calibrated predictions can outperform the conformal prediction method for infinitely many instances.\n2. Online Job Scheduling: They prove that a properly calibrated predictor with finer-grained confidence levels yields better performance bounds than prior work.\nThe theoretical findings are supported by experiments on real-world datasets, showing that the proposed algorithms leveraging calibrated predictions outperform the baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**“Does the calibration-based algorithm outperform the conformal prediction method for ski rental?”**\nWe 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.\n\n**“Lines 347-348 column 2: what does it mean that the bound is tight?”**\nThank you for pointing out this imprecise wording. It will be replaced by “the inequalities hold with equality.”\n\n**“Why and when is calibration beneficial for algorithms with predictions?”**\nThis 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.\n\nTo 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.\n\n**“Can experiments vary calibration error while controlling for squared loss?”**\nBecause 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.", "claims_and_evidence": "Most of the claims in the paper are convincing, but I have two concerns:\n1. Clarification on Line 347-348 (Right-Hand Side): When you state that the bound is \"tight,\" does this mean that there is a matching lower bound, or does it imply that the upper bound is optimal? A clearer explanation of what \"tight\" means in this context would be helpful.\n2. Comparison with Conformal Prediction Methods: The claim that \"there exist infinitely many families of distributions where calibrated predictions outperform conformal prediction methods\" does not necessarily mean superiority. To make a stronger argument, you would need to show that the inverse does not hold—i.e., that there are no such infinite families where conformal prediction consistently outperforms calibrated predictions. Additionally, since the bound includes the squared loss, it is unclear whether calibration itself is responsible for the improved performance. A predictor with high squared error, even if well-calibrated, might still yield a poor bound. Authors might need to be careful to make a strong claim.", "methods_and_evaluation_criteria": "Yes, in theory, the expected competitive ratio is the most common objective and evaluation criterion for these types of algorithms. Additionally, the chosen dataset is appropriate and aligns well with the study's objectives.", "theoretical_claims": "I checked the proofs in Section 3 and they seem to be correct. For Section 4, I briefly reviewed the proofs but did not check the details in depth.", "experimental_designs_or_analyses": "The experimental design appears to be valid and well-structured. However, based on the figures, I am not fully convinced that the algorithm with calibrated predictors consistently outperforms the conformal prediction baseline.", "relation_to_broader_scientific_literature": "The paper initiate the study of calibrated predictors for algorithms with predictions, and provided interesting theoretical analysis for two case studies.", "essential_references_not_discussed": "To the best of my knowledge, the paper appropriately cites all essential related works.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is innovative, being the first to study the effect of calibration in algorithms with predictions. The proposed algorithms and analysis are novel and interesting.  \n2. The writing is clear and well-structured.  \n\nWeaknesses: \n1. The techniques and results for the two case studies feel somewhat disconnected. It remains unclear, at a high level, why and when calibration is beneficial for algorithms with predictions. A more detailed explanation and discussion would strengthen the paper.  \n2. The experimental results are not entirely convincing. As mentioned earlier, it is unclear whether the algorithm with calibrated predictors consistently outperforms the conformal prediction baseline. Additionally, it would be valuable to include experiments that vary the calibration error (while controlling for squared loss, if possible) to empirically demonstrate how calibration affects performance.", "other_comments_or_suggestions": "1. Line 779: Did you define K_1(f,D) in the paper?", "questions_for_authors": "Could you clarify the conclusion that the calibration-based algorithm outperforms the conformal prediction method? The theoretical results suggest that the conformal prediction approach fails in certain cases, but this does not necessarily imply that the calibration-based method is strictly superior in general. Could you provide additional theoretical justification to support this claim?\n\nAdditionally, I would appreciate further clarification on the concerns raised earlier.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1KAeS9Cyg", "reviewer": "Reviewer_Buyh", "summary": "The paper introduces a novel idea of leveraging calibrated predictors to design learning-augmented algorithms. Instead of proving consistency, robustness, and smoothness guarantees, which are worst-case guarantees, the authors derive bounds that depend on the predictor's maximum calibration error. They apply this approach to the ski-rental problem and a variant of the single-machine scheduling problem where all the jobs have unit sizes but different priorities. They also support their theoretical findings with extensive experiments (in Section 5 and Appendix C).\n\n## update after rebuttal\nThe authors addressed most of my major concerns and questions during the rebuttal period. I am now convinced that the paper, after including the improvements discussed with the authors during rebuttal, would make a nice contribution to the literature of learning-augmented algorithms, and I have increased my score accordingly.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Motivation of the setting.**\nWe believe the reviewer’s concerns stem from a misunderstanding of our motivation for calibrated predictions:\n- 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.\"\n- 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. \n \n\n**Essential references.**\nWe 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.\n\nRegarding 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.\n\n**Performance measures.**\nWe strongly disagree that our performance measures are inadequate.\n- 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.\n- 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.\nWe will add this context to the third paragraph of Section 2.\n\n**Robustness.**\nWe 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. \n\n**“How are MSE and CE related, and can both be 0?”**\nA 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.\n\n**“Why MSE and not binary cross entropy (BCE)?”**\nWe 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.\n\n**“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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I read the proofs in the main paper (first 8 pages) and checked their correctness. I did not read the proofs in the appendices, but the proof sketches explained in the paper seem correct and convincing.", "experimental_designs_or_analyses": "The experiments are well explained and their results are sound.", "relation_to_broader_scientific_literature": "The paper contributes to the literature on learning-augmented algorithms. Instead of assuming that the predictions given to the algorithms can be arbitrary, the authors propose to leverage predictors with bounded calibration errors to prove new bounds, that improve upon prior works in some settings.", "essential_references_not_discussed": "The setting studied in this paper appears related to algorithms with distributional predictions, where predictions correspond to probability distributions rather than specific realizations. However, the paper does not reference or compare with this line of work. Relevant papers include:\n- \"Binary Search with Distributional Predictions\" (Dinitz et al., 2024)\n- \"Contract Scheduling with Distributional and Multiple Advice\" (Angelopoulos, 2024)\n- \"Learning-Augmented Binary Search Trees\" (Lin et al., 2022)\n\nAdditionally, in Section 3.3, the discussion on the tradeoff between worst-case guarantees (consistency/robustness) and the average performance is related to the paper \"On Tradeoffs in Learning-Augmented Algorithms\" (Benomar et al., 2025), which considers, for the ski-rental problem, a predictor of the form **1**$(z > b)$ that is accurate with probability q and studies trade-offs between consistency, robustness, smoothness, and the average-case performance of the algorithm.", "other_strengths_and_weaknesses": "The idea of using the calibration of the predictor to improve the bounds of learning-augmented algorithms is interesting and might inspire future work. However, unfortunately, the paper has many weaknesses, some of which can easily be addressed but others raise more serious concerns\n\n**Inaccurate claims for motivating the setting:**\n- The abstract mentions that the framework of learning-augmented algorithms \"often\nassumes uniform reliability across all predictions\". This is inaccurate, or at least not clearly stated. The theoretical framework of learning-augmented algorithms makes no assumptions on the reliability of the predictions, and this is why its objective is to prove consistency and also robustness guarantees.\n- (First page, first paragraph of the right column) The authors claim that most prior work focuses on extreme settings where predictions are either entirely accurate or completely uninformative. This is again not true. Most prior work also examines how algorithm performance scales with the sum of all errors, providing bounds that hold even when predictions are imperfect (smoothness). These results allow for performance guarantees when some predictions are accurate while others are not, and induce such bounds when the problem variables and predictions are stochastic.\n\n**Unconventional/Inadequate notation and terminology**.        \n- The competitive ratio, as defined in the paper, is instance-dependent (it depends on the distribution D), whereas the standard definition refers to the worst-case ratio over all possible instances.\n- The \"additive competitive ratio\" introduced in the paper is also instance-dependent and **is not even a ratio**. Calling it a competitive ratio is very inadequate and misleading. Moreover, it is not a suitable performance measure for the online scheduling problem (discussed further later).\n- The notation ALG(A,I) to denote the output of algorithm A on instance I is unconventional. The standard notation would simply be A(I) (or ALG(I) if the algorithm is denoted ALG), as used for the optimal offline algorithm, denoted OPT(I), not ALG(OPT, I).\n- The paper consistently uses the term \"prediction-aided algorithms\" instead of the standard term \"learning-augmented algorithms\".\n\n**Inadequate performance measure: \"additive competitive ratio\"**.    \nIn the online scheduling problem, what the authors refer to as a \"competitive ratio\" is actually a regret term E[ALG - OPT]. This terminology is very inadequate and misleading.      \nStandard performance evaluation for online algorithms typically uses the competitive ratio, defined as the worst-case ratio ALG/OPT, which provides a scale and size-independent comparison to the optimal solution.     \nIt serves as a multiplicative approximation factor to the optimal solution. This is a standard approach in broader fields of algorithm design, where attaining optimal performance is either impossible or complex, and the aim becomes instead to have algorithms approximating the optimal output up to a multiplicative factor (NP-hard problems, heuristic algorithms,...).     \n\nRegret terms like E[ALG - OPT] are more common in online learning, where the goal is to analyze the rate at which ALG/OPT approaches 1. A more relevant regret measure in online algorithms would be E[ALG - CR * OPT].        \nPrior work on online scheduling in the learning-augmented setting (e.g., Cho et al., cited in the paper) evaluates algorithms using the standard competitive ratio. \n\nThe paper’s use of regret makes it difficult to compare results with existing literature and raises concerns about the relevance of the findings since regret analysis is not adapted for the considered setting.\n\n**No robustness**\n- The setting of the paper can be viewed as the standard learning-augmented setting with a different error measure, which is a combination of the calibration error and the instance-wise prediction error ($\\eta$ in ski-rental). While their algorithms for both ski-rental and scheduling are 1-consistent, the authors do not prove any robustness bounds on their performance, that hold independently of the error (i.e. even if the error is arbitrarily large).", "other_comments_or_suggestions": "Minor comment:\n- L 144 (right column): $k$ is introduced but it is not yet defined at this point.", "questions_for_authors": "- For the ski-rental problem, the paper considers a binary target variable and derives bounds based on the mean squared error (MSE) of the predictor $f$. However, in binary classification, binary cross-entropy is the default error measure and is commonly used for training calibrated classifiers. Can the authors justify why MSE is an appropriate choice in this context? \n- MSE and calibration errors are presented as unrelated error measures. Are there any correlations/bounds between them? Are there any existing classifiers that minimize both the MSE and the max-calibration error? (i.e. is it indeed possible to have both $\\alpha$ and $\\eta$ close to 0)\n- In Section 3.3., it is mentioned that the bound of Theorem 3.3 shows that the algorithm always has an expected competitive ratio of at most 1.8 when the classifier is calibrated. If the classifier is calibrated, i.e. $\\alpha = 0$, then the bound becomes $1 + \\min(\\mathbb{E}[f(X)], 2\\sqrt{\\eta})$. Could the authors explain why this is always less than 1.8?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d1WiqJ6eQc", "reviewer": "Reviewer_wjo6", "summary": "The paper studies how calibrated machine learning predictions can improve online algorithms. The paper focuses on two settings: the ski rental problem and online job scheduling. \n\nIn the ski rental problem, the predictions is about whether the skier will ski for more than a given threshold $b$ days using a calibrated binary predictor $f(X)$ where a calibrated $f(X)\\in[0, 1]$ prediction means that it matches the actual likelihood of skiing more than $b$ days. The calibration error is the max calibration error, which measures the largest deviation from perfect calibration for any prediction.\n\nIn job scheduling, the model predicts the priority of each job using a calibrated probability score rather than a binary label, which allows for a finer-grained job ordering. Jobs are then scheduled using a threshold-based rule. In this setting, the authors consider the predictors to be perfectly calibrated.\n\nIn both settings, the authors show that the algorithm performance can be improved using calibrated predictors.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**“Do the job scheduling results generalize to predictors with non-zero calibration error?”**\nYes, 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.\n\nThanks 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.\n\n**“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)?”**\nDesigning 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.\nNonetheless, 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper may relates to broader literature in AI-assisted decision-making where AI provides predictions for decision-making tasks.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I like the idea of bringing the calibration to ensure the trustworthy property of provided predictions to the decision-makers. Unlike prior work that assumes global uncertainty of predictions, this approach uses instance-specific calibrated predictions, which can lead to more refined decision-making in the considered both ski rental and job scheduling problems. The authors also run a some experiments and it is good to see that the results indeed matches the theoretical findings.\n\nPerhaps one of the weakness is the calibration metric considered in the paper. In the ski rent problem, the paper considers the max calibration error (i.e., a worst-case perspective), which sounds a bit weird to me, especially given that the authors have already assumed the underlying uncertainty is from distribution. One natural metric here should be expected calibration error, right?\n\nAlso, in the job schedule problem, the authors consider perfectly calibrated predictions, which is strong assumption. Could the results be generalized to a setting with predictors that may have certain calibration error here?", "other_comments_or_suggestions": "See above", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NThzZiUwfx", "reviewer": "Reviewer_eD7y", "summary": "This paper introduces calibration as a tool to enhance learning-augmented algorithms, focusing on two problems: ski rental and online job scheduling. The authors propose algorithms that leverage calibrated predictions to achieve instance-specific competitive ratios, theoretically and empirically outperforming methods like conformal prediction. Experiments on real-world datasets (Citi Bike rentals and sepsis triage) validate their approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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!\n\n**“The expected performance bound for ski rental scales with max calibration error, which can be large, so the algorithm is non-robust.”**\nWe 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.\n\n**“The results for job scheduling rely on an IID assumption that may not hold in reality”**\nThough 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.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem.", "theoretical_claims": "I checked the correctness of some claims but didn't go through all the proofs. The proofs that I have checked are reasonable and sound.", "experimental_designs_or_analyses": "I only made a quick pass on experimental designs, and it looks reasonable. Note that the main contribution of this paper is theoretical.", "relation_to_broader_scientific_literature": "The key contribution of this paper is a new concept of the learning-augmented algorithm, i.e., using calibration to enhance the prediction. This is new and does not exist in the literature.", "essential_references_not_discussed": "All necessary related works are discussed in the submission.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a new concept (i.e., calibrated prediction) for learning-augmented algorithms; this bridges the gap between global uncertainty assumptions in learning-augmented algorithms and modern ML models with local uncertainty estimates. Calibration is framed as a practical, instance-specific alternative to conformal prediction. This concept looks more practical compared to the existing prediction concepts.\n2. From the theoretical view: for ski rental, the proposed algorithm achieves an expected competitive ratio bounded by calibration error and mean-squared error (Theorem 3.1). The authors also provide the lower bound (Theorem 3.4) shows near-optimality. For job Scheduling: By analyzing finer-grained calibrated predictors, the paper demonstrates reduced inversion costs (Theorem 4.3), improving upon prior work that relied on binary predictions.\n3. This paper also includes the experimental results. They did experiments on real data (Citi Bike and sepsis) to demonstrate performance gains, linking theory to real-world applications.\n\nWeakness:\n\nThere are some weaknesses in the results that were obtained. For ski rental, the ratio of the proposed algorithm (theorem 3.3.) is related to alpha, which is the calibrated error. This makes the algorithm lose its robustness. In the worst case, alpha can be very large. As the authors show in the lower bound theorem (theorem 3.4), the lower bound does not rely on alpha. For job scheduling, the obtained results rely on the iid assumption for features; this may not be true in reality.\n\n\nOverall, although there are some weaknesses in the paper, I am still happy to see this paper in the proceeding since the paper proposes a new concept in learning-augmented algorithms, which might lead to some future works. Besides this, I also think that the theoretical understanding of this calibrated prediction concept would have a positive impact on reality. Thus, I recommend the acceptance.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces calibrated predictions as a refined way to incorporate machine learning predictions into classical online algorithms, studied through two canonical problems: ski rental and single-machine scheduling. By focusing on calibration, the paper aims to provide instance-specific performance guarantees, thereby moving beyond global, worst-case error assumptions typically used in learning-augmented algorithms. The authors prove that when the maximum calibration error is sufficiently small, their algorithms achieve performance bounds that can, in certain instances, improve upon methods based on conformal prediction or classical global-error metrics. Extensive theoretical analysis and real-data experiments illustrate the practical potential of leveraging calibration in online decision-making.

After careful deliberation, the consensus is to accept this paper. The reviewers found the idea of leveraging calibration in learning-augmented algorithms to be both novel and practically relevant, addressing gaps in current approaches that rely on globally bounded errors. The authors’ detailed rebuttal and discussion resolved most concerns, especially around worst-case performance and the scope of the scheduling results. Collectively, the reviewers felt that the paper’s contributions, both conceptual and theoretical, justify publication at ICML.
Decision: Accept (spotlight poster)