Provably Calibrated Regression Under Distribution Drift
Authors: Shengjia Zhao
YUSUKE TASHIRO
Danny Tse
Stefano Ermon
Venue: ICLR 2022 Submitted (2022)
Keywords: calibration
online prediction
distribution shift
uncertainty quantification

Abstract: Accurate uncertainty quantification is a key building block of trustworthy machine learning systems. Uncertainty is typically represented by probability distributions over the possible outcomes, and these probabilities should be calibrated, \textit{e.g}. the 90\% credible interval should contain the true outcome 90\% of the times. In the online prediction setup, existing conformal methods can provably achieve calibration assuming no distribution shift; however, the assumption is difficult to verify, and unlikely to hold in many applications such as time series prediction. Inspired by control theory, we propose a prediction algorithm that guarantees calibration even under distribution shift, and achieves strong performance on metrics such as sharpness and proper scores. We compare our method with baselines on 19 time-series and regression datasets, and our method achieves approximately 2x reduction in calibration error, comparable sharpness, and improved downstream decision utility. 

Under review as a conference paper at ICLR 2022
PROVABLY CALIBRATED REGRESSION UNDER DIS- TRIBUTION DRIFT
Anonymous authors Paper under double-blind review
ABSTRACT
Accurate uncertainty quantification is key building block of trustworthy machine learning systems. Uncertainty is typically represented by probability distributions over the possible outcomes, and these probabilities should be calibrated, e.g. the 90% credible interval should contain the true outcome 90% of the times. In the online prediction setup, existing conformal methods can provably achieve calibra- tion assuming no distribution shift; however, the assumption is difficult to verify. and unlikely to hold in many applications such as time series prediction. Inspired by control theory, we propose a prediction algorithm that guarantees calibration even under distribution shift, and achieves strong performance on metrics such sharpness and proper scores. We compare method with baselines on 19 time-series and regression datasets, and our method achieves approximately 2x reduction in calibration error, comparable sharpness, and improved downstream decision utility.
INTRODUCTION
Accurate uncertainty quantification is crucial for machine learning predictions used high-stakes decision making. Typically, uncertainty is represented by probability distributions over the possible outcomes, and these probabilities should be calibrated. In the regression setup, for example, the true label should be below the predicted 95% quantile for 95% of the samples (Gneiting et al.) 2007). Calibration can convey confidence to decision makers because extreme values (e.g. true label above 95% quantile) are guaranteed to be rare. In addition to calibration, these probabilities should be sharp (i.e. concentrated and have low variance). Sharp probabilities are useful to decision makers because they informative.
data is i...d, then recalibration Kuleshov et al. 2018) and conformal prediction (Vovk al. 2020)
algorithms can achieve low calibration eтror and good sharpness in the regression setup. However, the i.i.d. assumption is unlikely to hold in most time-series prediction tasks. Under distribution drift, it is possible to adapt regret minimization algorithms (Cesa- (Cesa-Bianchi Bianchi & Lugosi| 2006 Kuleshov & Ermon 2017) to achieve calibration. However, regret minimization calibration algorithms are designed for the asymptotic regime, and empirically show that they effective only with large sample size, and have very poor calibration and sharpness with short time series (c.g. 50 samples), limiting their practical utility.
Our goal is to design an algorithm to achieve good calibration and sharpness in the online regres- sion setup even for short time series. We start with an existing prediction algorithm that has good calibration and sharpness for i.i.d. data (such as conformal prediction), and track the empirical fre- quency that the labels are below e.g. the 75% quantile. below 75%, we move future predictions up more labels are below the prediction; vice versa. We design very efficient adjustment method that can guarantee near perfect calibration with only tens of samples. We call this the "basic" prediction algorithm shown in Figure (upper right).
the empirical frequency is significantly
Our main technical contribution is an improved algorithm that addresses two short-comings of the "basic" algorithm without breaking guaranteed calibration. First, the predictions should be feasible, e.g. the 75% quantile should never be smaller than the 25% quantile. The basic algorithm might violate this requirement because adjust each quantile separately with constraint their rela- tion. Second, the predictions should be stable if the distribution drift stops; empirically instability harms sharpness and proper scores. Our improved algorithm is based analogy between the

---

Under review as a conference paper at ICLR 2022
Origina Prediction
Basic Algorichm
predicted 25% quantile quantile
label val up
true 25% quantile
true 75% quantile
observed label
40
50
20
40
stop
time stop
Basic Feasibility Constraint
Basic + Feasibility Constraint + PID Control
label valuee
0-
10
20
30
40
50
0
10
20 30 40
50
60
stop
time
Figure An illustrative example of our algorithm. The z-axis is the time step (for the online prediction setup), and the y-axis is the prediction. We look at the 75% and the 25% quantile of the prediction. The purple markers are the true labels. The true label initially drawn from Uniform[-2, 2] but drifts to Uniform[-5, -I]. Upper Left: The original predictions that is not calibrated because distribution drifted time step 5. Upper Right: The "basic" algorithm: we move the quantiles up down to achieve calibration. However, the prediction is sometimes infeasible (e.g. the 25% quantile is above the 75% quantile at time step 43) and oscillates even when distribution drift stops. Lower Left: We add feasibility constraints. The quantiles calibrated and feasible. Lower Right: We use PID control to stabilize the predictions. The quantiles are calibrated, feasible and do not oscillate. The predictions adapts very quickly in response new distribution within tens of samples.
prediction task and mechanical system. We encode the feasibility constraints the feasible states of a mechanical system, and use propotiinall-nteeraa integral-derivative (PID) control (Minorsky 1922) to stabilize the system. Our final algorithm makes predictions that satisfy all three desirable properties: provable calibration, feasibility, and stability (Figure I bottom right).
We test our algorithm on two real world time series datasets (stock earnings and COVID cases) and a large benchmark of 17 common regression datasets. We reduce calibration error by approximately 2x compared too all baselines, while achieving comparable or better sharpness. We also simulate COVID response decisions based on predictions on the COVID dataset, and observe improved deci- sion loss compared to baselines during periods of distribution drift (e.g. when case numbers surge).
PROBLEM SETUP AND BACKGROUND
We consider regression problems. Let X E X denote the input feature and Y denote the label. We assume that the label is bounded by B, ie. Y cannot take any value outside [-B, B3 for some pre-specified B= > O.
We consider quantile predictions with set of K equally spaced quantiles 0 < 01 < < ak < 1. For example, when K 9 we choose a₁ = 10%, Q2 = 20%.... .ag = 90%. A quantile prediction is a vector of K numbers (denoted by Z) where Z& should ideally predict the ay-th quantile of the label Y|X conditioned on the input feature X. We say quantile prediction is feasible, Yx < Yk+1, Vk, i.e. a lower quantile is always smaller than a higher quantile. In the limit of infinitely many quantiles K + co, quantile prediction is equivalent to probability distribution, however, for technical reasons that will become evident later, we only consider finitely many quantiles in this paper.
Our setup is an online prediction setup, where the forecaster sequentially makes the predictions. Consider COVID prediction example: at time the forecaster observes some features X (such as current vaccination rate) and makes a prediction Z' about next week's 's case number. After the forecaster makes a prediction, the true case number yt is revealed; then we move to time step
2

---

Under review as a conference paper at ICLR 2022
t +++ and repeat this process. Following standard terminology will use "nature" to refer to the process that generates the features X and the true label Y². Our setup is formalized by the following interaction between forecaster and nature: for 1,2, ... ,T
Nature reveals feature X
2. Forecaster makes a quantile prediction Zt E R where Z is the 04-th quantile.
3. Nature reveals label Y E E 13]
We call finite sequence of interactions a transcript, i.. a sequence X VY,Y".... ,X,, z", YY. forecasting algorithm yb is a function that maps a transcript and a new feature to a prediction:
+ x 2 y
Xt-1 z- y X Z'.
Y We will consider two types of assumptions on nature. We say that nature is i..dd vt, X are drawn from some i..dd random variable (but make assumption on the probability law this random variable). We say that nature is causal if nature chooses Xx, Y without depending on the future. Specifically, X Y can only depend on the variables that precede it in the transcript (i.e. X can depend on X=, .... an extremely weak assumption. For example, nature can even adversarially choose the label y to increase prediction error after observing the forecaster's prediction 2²,
yt-1 '²,...
and Y can only depend on X1 .'.... yt-1, X', Z²). Causal is
2.1 CALIBRATION AND ACHIEVING CALIBRATION WITH CONFORMAL METHODS
A natural property that we can request (probabilistic) calibration (Gneiting et al. 2007 Kuleshov eet al. 2018). Intuitively, Ak. the label Y should be below the predicted ag-th quantile for an Og proportion of the samples. Formally, given transcript of any length, consider the empirical frequency that the label y is below the predicted quantile Z up to time T (for any T that's ss less than the length of transcript)
F
Σ IIY'' ISIST
S z.).
(2)
Ideally, the label Y should be below the -u- quantile exactly T many times, i.e., Vk, Ff /T ag. Achieving this perfectly is difficult, so we define an approximation. For any function b N + + say that transcript is b-calibrated if Ak 1, K, VT' 1F /T axl 6(T).
Correspondingly, a forecasting strategy is calibrated if the resulting transcript is calibrated:
Definition 1. For any function b N- + Rt, forecasting algorithm và is b-calibrated under i.i.d. (or causal) assumptions if for any nature's 's strategy that is i...d. (or causal), the resulting transcript is b-calibrated almost surely.
Conformal Calibration Conformal calibration Vovk et al. 2020) is a forecasting algorithm based on conformal prediction ideas (Vovk et al., 2005 Shafer & Vovk 2008). It is wrapper algorithm that transforms a initial predictor (such as an off-the-shelf predictor) into new predictions that are provably calibrated under i.i.d. assumptions. Conformal calibration is based on the following intu- ition: for example, if 75% of past labels are below the initial prediction's 's mean, then we can use the initial prediction's mean as the 75%-quamtil prediction in the future. More generally, we identify a statistic of the initial prediction, such that a -y-ooopottion of the past labels are below that statistic. We use this statistic as the ay- quantile of the future prediction.
If the data is i.i.d., conformal calibration is very useful algorithm. This is because it has extremely strong calibration properties (Proven in Proposition of (Vovk et al.) 20200) where the random variables I[Y < Z 1, ... is a sequence of i.i.d. Bernoulli random variables with mean og- This is impressive because even if we have access to the oracle forecaster (i.e. YŁ is equal to the true conditional -y quantile of Y "Xx), we cannot achieve better calibration - I(Y < Z is also sequence of i.i.d. Bernoulli random variables with mean ag. Empirically, conformal prediction also has very good sharpness if the initial prediction function is reasonable (Burnaev & Vovk 2014).
A minor property (but needed for proofs) is that the predictions should bounded in [-B, B). Con- formal calibration satisfies this property when t > K, i.c. there are more samples than predicted quantiles. To bypass this limitation, we can initialize the conformal calibration algorithm with at least K offline samples. Alternatively, if we know B in advance, can clip the prediction by B.
3

---

Under review as a conference paper at ICLR 2022
3 CALIBRATION UNDER DISTRIBUTION DRIFT
This section introduces our algorithm that guarantees calibration even when nature is not i..d. We start from basic algorithm in Section 3.1 and discuss its shortcomings. Then we move on to more advanced algorithms in Section 3.2 and 3.3 to address the shortcomings.
3.1 A BASIC CALIBRATED PREDICTION ALGORITHM
Conformal calibration achieves good calibration and sharpness when nature is i.i.d. When unsure if nature is i.i.d., our basic idea is to use conformal calibration until it has failed to achieve calibration. Specifically, when nature is i.i.d., T(Y < Z is sequence of Bernoulli random variables, so F is the sum of these Bernoulli random variables (i.e. a binomial). We use (T) to denote the confidence interval of a binomial distribution. i.c. Pr[FT] /T a = bT) We fix some small 8 (such as 0.05) and if under the conformal calibration algorithm / /T & ag + bg (T), we know (with 0.95 confidence) that nature is not i..dd so we will make adjustments to salvage calibration.
6.
From a high level, F > agt + (t)t implies that the true label below the eg-th quantile too often, our prediction 7 has been too large and we should reduce it; vice versa; There some design freedom in choosing how much to reduce or increase the prediction. We choose an adjust- ment that grows exponentially with larger calibration error. The reason for this choice is to make very large adjustments when the calibration error is large, so we can tightly bound the calibration error. Formally, let 2 denote the initial prediction generated by the conformal calibration prediction algorithm, the prediction of our algorithm Y is given by
F 7 agl ag
1tt -,+1 Ett,, where E
-1
F < < bg(t)t
(3)
otherwise
Intuitively, if F is within the correct range we make no adjustments (i.e. - = - when F falls outside the correct range, we make aggressive adjustments that increase exponentially with how much it falls outside the correct range. 3 > 0 is a hyper-parameter that controls how large the adjustments are (we will show Section 3.4 that these syper-parameters are easy to choose). Note that Ex is for the (t + 1)-th time step (instead of t). This is because any adjustments can only depend on past information, so we will only have access to F% at the (I + 1)-th time step. The following theorem shows that such adjustments indeed guarantee calibration.
Theorem 1. Let 2% be generated by any forecasting algorithm and bounded in [-B, B), for any 8 > 0, the prediction algorithm defined by Eq. 30 b-calibrated where b(T) = bj (T) log 1og(2++))+
BT
Note that the guarantee of Theorem 1 does require that conformal calibration generate the ini- tial prediction Zt. The use of conformal calibration is motivated by its strong empirical perfor- mance (Vovk et al. 2020) when the data is i..d. or close to i.i.d. (which is further supported by our experiments).
The calibration guarantee is strong because under conformal calibration with i.i.d. data (or the or- acle forecaster) we can expect see (T') calibration error (with probability); without i.i.d. assumptions, our algorithm can ensure that the calibration error only increases by Ollog B TT). No- tably, the calibration eтrоr scales logarithmically with the assumed upper bound log B, so choosing a loose bound B does not significantly degrade the guarantee.
The basic idea has two shortcomings illustrated in Figure that we will address in the next sections. First, in a feasible quantile prediction, the 75% quantile should never be smaller than the 25% quan- tile, but our adjustments might violate this requirement because we adjust each quantile separately with constraint. Second, the basic idea might lead to oscillation and instability. Intuitively, when the empirical frequency is incorrect, we make adjustments to correct it, but once the empirical fre- quency improves, reduce the adjustments, which will cause the empirical frequency to become incorrect again, leading to oscillation. Empirically instability can hurt performance metrics such as sharpness.
4

---

Under review as a conference paper at ICLR 2022
3.2 IMPROVING THE BASIC ALGORITHM TO ENSURE FEASIBILITY
In this section, we address the feasibility problem. We first define some convenient notation shorthand. For our prediction Z", we denote the distance between (neighboring) quantiles as A 7 Z for k- = 0,... K. We can make similar definition for the initial predic- tion A2 1 Zz. Under these new definitions, requiring feasibility equivalent to requiring positive distance between neighhoring quantiles, i.e. A77 > 0, vk.
The main challenge is that the basic adjustment algorithm Eq. might not satisfy this new require- ment, so we need to find a compromise. We draw inspiration from mechanical system illustrated in Figure where we imagine that our prediction quantiles -i. Z are sequence of points in space. We imagine that each requirement (satisfying (3.(3) or feasibility constraint) can be thought of "force" that "push" the quantiles to satisfy the requirement. These forces will contend with each other (because the requirements are conflicting). so the equilibrium of these forces is the natural compromise between the conflicting requirements.
Specifically, to enforce the requirement that the interval size A AZ cannot be close to 0 or negative, design a force that pushes the interval to be larger whenever it is small. Intuitively, we can think of this as inserting a "spring" (illustrated in Figure 2 into the interval. The spring will resist being compressed, and exert opposing force whenever the interval becomes small. The smaller the interval, the more compressed the spring will be, so the larger the opposing force; in the limit where the interval size tends to 0, the opposing force will tend to co. This prevents the interval size from going to zero (or negative) and ensures feasibility.
We add another desiderata: no force is generated only when the interval size A equals the initial prediction's 's size A A. Intuitively, we want to use the initial conformal prediction as much as possi- ble (which we argued in Section 3.1 is desirable). This can be achieved by imaging that the spring has initial length A A and resists both compressing and stretching.
a2f
42
arror
DE
0
20
10
60
80
100
time step
Figure 2: Left: An illustration for Section 3.2 where we draw analogy to a mechanical system. We attach a "spring" between neighboring quantiles that resists being compressed stretched. The final prediction Z is the equilibrium state of this mechanical system. This is the natural way to compute the compromise of several conflicting requirements. Right: Illustration of the effect of PID in Section 3.3 Here we plot the error F &gt when the initial prediction systematically under- predicts. P corresponds to the basic algorithm, and the error oscillates around O. PI corresponds to adding an integral term, and the error converges to O. PID adds an additional derivative term, which reduces overshoot and improves convergence.
To ensure that prediction exceeds the bounds [-B, B), also create additional quantiles 0o = O and - 1, and define Zo = - B and Zx+1 +B, so that assuming feasibility we will always have Z1 > Zo B and Zx < ZK-1 B. We formalize the above intuition as the following list of forces on each quantile:
1. Forces from miscalibration Ej defined by Eq. 3h and deviation from initial prediction D : z Z If we only have these two forces, we recover the basic algorithm. This is because if we solve the equilibrium state of the system D + E O, we get Z 2 + E which is exactly (3.
2. Force from the spring in the interval above A = (A AZ AZ//AZ)) where is a hyper-parameter (we will show in Section 3.4 that setting these parameters easy). Intuitively, if the interval above is larger than its initial size (i.e. A > AZ) then the
5

---

Under review as a conference paper at ICLR 2022
spring "stretches" which generates upward force A 0; conversely if the interval above smaller than its initial size (i.e. AZ) < AZZ) then the spring above "compresses" which generates a downward force Ag < O. If the interval has the same size, then no force is generated because A
3. Force from the spring in the interval below B :-
AZ -
We define the final prediction E as the solution the following equilibrium equations (i.e. all forces sum to 0 for all the quantiles)
E Dj + A B 0,
(4)
The resulting forecasting algorithm is provided as Algorithm
Algorithm Basic + Feasibility Forecasting Algorithm
1: For each & = 1,..,,,,......... K, initialize F = 0
2: for 6= 1, 2, ... do
3: Observe X and use initial prediction algorithm (e.g. conformal calibration) to predict 2'.
4: For each k = ... K, compute F according to E3.
5: Use a physics simulation to find Z that solves Eq. given Z' and Ej. output Z
6: Observe the true label y For each = 1, ...., K, set Fg = Fk + T( < %
7: end for
We will show that Algorithm Srooitthmaacheeverr Tachieves calibration except when the "like- lihood" is exponentially high (which is also very desirable). Specifically, we define notion similar to likelihood
Calibration Properties
L(Z', - =
( AZz for the that satisfies Y [Z] Z
oxx)/
(5)
small interval (i.e. AZ₁ small), In the limit of infinitely many quantiles K + co, the quantile prediction becomes equivalent to probability distribution, and (5. becomes the likelihood of the probability distribution.
Intuitively, L(Z Y!) is large the true label yt belongs
Theorem (Simplified). Under the same condition Theorem L for any > 2/B, Algorithm 7 is
b-calibrated where b OKK/VT e)T) on any transcript such that Vl, I[Z Y*) s @lc)
Theorem is simplified version of the full theorem (we replace all the constants with asymptotics). For non-asymptotic version and proof see Appendix A Intuitively, for any transcript generated by Algorithm [] if the "likelihood" never exponentially high, then the transcript is OK/VVT)- calibrated (e will be bounded constant). When T is large, the calibration error will also go 0 at rate of O11/VT). On the other hand, if the likelihood is exponentially large, we are "almost" perfectly predicting the label, so there is little uncertainty. Uncertainty quantification metrics such as calibration become less relevant.
3.3 IMPROVING STABILITY WITH PID CONTROL
Finally we address the stability problem. As we argued, the key problem is the constant need to increase or decrease the adjustment E++1 based on whether the empirical frequency Fý is different from agt. Our key insight is to think of this problem as a control problem: we would like Fş to match out and the eтror is measured by E (which we want to bring close to 0), so we can use control algorithms to stabilize the system. We show (heuristically) that a very popular control algorithm called cepportional-ineegra---deee
(PID) is well suited for the task.
Our new algorithm replaces F. in line 4 of Algorithm with the weighted sum of three terms: proportional Ei = Ei. integral E, = Ei- ET and derivative E = E - E The proportional term Ege is the same as Eq. 3 so if we only have the proportional term we would reduce to Algorithm | The integral term E is key to addressing the stability problem because it does not decrease even when the E goes to 0, so it applies a permaneett adjustment when distribution drifts. The intuition of the integral term is demonstrated in Figure 2 Using the integral term is prone

---

Under review as a conference paper at ICLR 2022
to well known problem called overshoot. Intuitively, the integral term will increase until Ej; goes to O, at which point the (permanent) adjustment might already be too large. The standard method
to reduce overshoot is to a derivative term E (Minorsky 1922), and we illustrate its effect in Figure The overall adjustment equal to
(6) where kpp kg 2 are the hyper-parameters (again, we will show in Section 3.4 that choosing these hypee-parameters is not difficult). We also clip the integral and derivative terms to be within [-B, B, B] to ensure Corollary [ even in the worst case scenario. For any real data in our experiments, the clipping never took effectt
ETID- = EpEp + CLIP (k, + kg
We show that applying PID control does not break the calibration guarantee in Theorem 2
Corollary 1 (Simplfied). Under the same condition as Theorem 2 for any kpp ki, ka 2 0, Algo- rithm 7 with E replaced by EiIDD-k in Eq. 6 is b-calibrated where b = OKK V + c/T) on any
transcript such that Vt, L(Z', Y S (())
A non-asymptotic version is also available in the appendix. With PID control Corollary is es- sentially identical to Theorem [ (in fact exactly the same for the simplified asymptotic version). Therefore, PID improves stability without degrading the calibration guarantees.
3.4 HYPPER-PARAMER PARAMETER SELECTION
Our algorithm consists of titioner. Specifically, the syper-parameters are B, 5 in E). which specify how large is the ad- justment Ef; the "elastic coefficient" in the definition of A and Bj, and the PID coefficients kp. ki kd-
which on first sight, seem difficult to choose for a prac-
Fortunately, we show that our algorithm is very robust to hyper- parameter choices. In fact, we tune these parameters
few simple synthetic examples (similar to Figure and fix them throughout all the experiments on real data. We show (in Figure 7 in the appendix) that even if we were to finetune these hyper-parameted specifically for each dataset, would only marginal improve- ments compared to using fixed typer-parameterr Therefore, any practitioner can simply use the fixed typer--arameters that we recommend, and generally do not have to worry about tuning them in practice.
4 RELATED WORK
In the regression setup, there are several notions of calibration. The most common one (which is studied in our paper) is probabilistic calibration (Gneiting et al. 2007 Kuleshov al., 2018 Vovk et al. 2020 Other notions include marginal calibration (Gneiting et al.) 2007), individual calibration (hho al. 2020). distribution calibration (Song et al. 2019), threshold calibration. etc. Though not considered in our paper, calibration has also been extensively studied in the classification setup, calibration has been studied under (Brier) 1950 Murphy| 1973 Dawid 1984 Cesa-Bianch &
Lugosi 2006 Platt et al., 1999 Zadrozny & Elkan
2001] Niculescu-Mizz & Caruanal [2055
Guo et al., 2017 Lakshminarayanan et 2017). There are also other notions of calibration such
as multi-cliibraiion JHöbert-Johnson et al. 2018), decision calibration (Zhao et al. 2021). classwise
calibration (Kull et al. 2019), etc.
Many applications only require confidence interval. For confidence intervals notion very similar calibration is coverage, i.e. the label should belong to the interval with high probability. Con- formal prediction methods are the gold standard for predicting intervals with high coverage. (Vovk
et al. 2005 Shafer & Vovk 2008 [Papadopoulos 2008 Romano et al. 2019).
The above research primarily focus on the i.i.d. setup (or exchangeable setup). while many real world data are not i.i.d. In the online setup with distribution shift, regret minimization algorithms can guarantee asymptotic calibration (Cesa-Bianchi & Lugosi 2006 Kuleshov & Ermon 2017) for classification. For conformal prediction, when the likelihood ratio of the distribution shift is known, Tibshirani et al.) (219)) still guarantee coverage. A concurrent work (Gibbs & Candès 2021) can guarantee asymptotic coverage for conformal confidence intervals. Our work differs in that we focus on calibration, and solve additional feasibility and stability challenges.

---

Under review as a conference paper at ICLR 2022
15
25% quantile 75% quantile
quartlees
0.75
1.00
teler vell ie
15
75% quantile
25% quantile
1.0
0.8
40
observed label
10
observed label
0.6
0.50
labe:
5-
0.25
0.2
0
0.00
0.0
15
20
30
0.0
0.5
1.0
15
23 time step
30
0.0
0.3
1.3
time step
target quentiles
target quentiles
Figure 3: Example predictions on the stock prediction dataset (for Amazon). Left is conformal calibration only, and right conformal calibration + our method. We plot both the sequence of pre- dictions, and the reliability diagram (i.e. the relationship between target frequency ag and empirical frequency FK (T). Amazon growth has been faster than expected by analysts at times (such as steps 21-26, or 30-33), conformal calibration failed to capture this, while method rapidly adapted to this distribution shift within a few time steps.
original
conformal
regret
10
10
00
08
00
0.0
8tual
06
04
0.6
02
00
00
00
00
0.0
0.5
0.5
075
1000
0.0
0.25
0.50
075
100
0.00
0.25
0.0
075
1.00
000
025
050
075
100
target
brreet
target
target
Figure 4: Reliability diagram for different methods on stock prediction. Each blue line is the reli- ability diagram for a single stock. The yellow shaded area is the 99% confidence interval for the reliability diagram of an oracle predictor (i.e. it is og (T) for d 0.01). From left to right we use original predictions, conformal calibration, our method, and an regret minimization baseline. Our method achieves achieves the best calibration. Even though the regret minimization baseline can also guarantee calibration asymptotically, for short data sequences the calibration is incorrect.
EXPERIMENTS
This experiment aims show real time series data and standard regression benchmarks that our algorithm achieves strong calibration, sharpness and proper scores.
Datasets We two time series prediction tasks (stock and COVID) and regression benchmark with 17 datasets. For times series we start from expert predictions (such as from stock analysts or COVID forecasting teams), apply our algorithm to adjust the output of conformal calibration. For the regression benchmark we split each dataset into train and test. We the training set learn prediction function offline, and assume that the test data are available sequentially online. For each dataset we add the following types of drifts; linear shift: add constant bias to the label that increases over time; cycle: add bias to the labels that moves up down repeatedly; scale shift: multiple the label by constant that increases with time; jump: add constant bias at some Vt to for some time step to. More details about the datasets are provided in appendix.
conformal calibration to transform the expert predictions, and finally
Performance Metries error (uoo et al. 2017) Lece = K Σx F T. Pinball loss We use the average pinball loss (aka.
CCaiibration loss We use notion similar to the expected calibration
hinge loss) Cpinbal (Y, R En a.RRLU(ZZ Yx) (1 (1-aa ag ReLU 22. The pinball loss is a proper score, i.c. the oracle quantile prediction minimizes the expected pinball loss. Sharpness
We use the average interval size measure the sharpness Laharpuess (Z) * E. IZ, Zk-
We compare three baselines. original is the original expert predictions. We use kernel density estimation (Van Kerm 2003) to transform the expert predictions into probability; con- formal is conformal calibration only (without Algorithm []]: regret an adaptation of the regret minimization algorithm in (Kuleshov & Ermon 2017) (details in the appendix).
Baselines:
8

---

Under review as a conference paper at ICLR 2022
Avg Decision Loss
0.00
W
-0.05
conformal
ours
-0.10
2020-11-07
2021-02-20 2021-06-05
conformal / ours instead of the original expert predictions for a COVID response decision task. The shaded area is standard deviation computed by bootstrap sampling geographical locations, and the dashed line the total case number. Both conformal / ours reduce decision loss (so all curves are below 0), but our method reduces loss more compared conformal when distribution changes drastically, i.e. when case numbers spike.
Figure 5: The decision loss reduction if
pinball
calibration (ece)
sharpness
orig.
conf.
ours
regret
orig
cont.
ours
regret
ong.
conl.
ours
regret
stock
0.052
0.045
0.046
0.145
0.243
0.089
0.051
0.151
0.140
0.196
0.198
0,422
COVID
0.231
0.181
0.181
0.264
0.152
0.054
0.042
0.079
0.893
1.122
1.085
0.952
Bench-shift
2.540
0.921
0.299
0.505
0.494
0.436
0.149
0.232
0.676
2.842
1.737
2.768
Bench-scale
2.848
2.111
2.062
2.191
0.249
0.110
0.049
0.058
0.676
7.722
9.139
10.90
Bench-jump
1.396
0.777
0.533
0.762
0.286
0.201
0.073
0.172
0.676
2.164
1.972
2.637
Bench-cycle
0.924
0.697
0.496
0.714
0.220
0.165
0.047
0.146
0.676
2.595
2.775
3.045
Table I: Performance comparison ours and several other alternatives on time series datasets and regression benchmarks. Our method (ours) achieves far better ECE than other methods. For pinball loss our method is on-par or better than baselines. The original prediction (orig.) is sharp. but the prediction incorrect (the calibration and pinball loss are poor), hence sharpness is not meaningful. If we exclude (orig.), then our method achieves better or on-par sharpness than any other baseline. Regret minimization (regret) has poor performance on stock and COVID (with 50 samples per data sequence) and better performance on UCI (around 100 samples per data sequence) but still much worse than ours.
Qualitative Results In Figure Figure 8 (in the Appendix) we plot some example prediction sequences and reliability diagrams. Our algorithm is able adjusts the predictions up or down to ensure calibration, and does not hurt sharpness (compared to conformal calibration only) when there is distribution drift. In Figure we plot the reliability diagram for the stock dataset. Our method is always calibrated (i.e. within the tolerance shaded in yellow), conformal calibration uncalibrated (without the tolerance) for about 10% of the samples, while the regret minimization baseline is generally uncalibrated (because all time series are very short with around 50 samples).
Quantitative Results In Table [ we show the performance of our algorithm compared to several baselines. Our method achieves the best calibration error (ece) by far, and comparable better pinball loss compared to baselines. Even though the original prediction achieves the best sharpness overall, the pinball loss and calibration error of the original prediction are so large, that sharpness is meaningless. If we exclude the original prediction, then method also achieves comparable or better sharpness than other methods that have reasonable calibration.
Downstream Task For COVID we simulate a response strategy (i.e. whether to close businesses) based on forecasted cases. We use the median of the prediction to select the best action. For details see Appendix C.T The results are shown in Figure 5 Both conformal calibration and our method improves decision loss compared to using the original prediction; our method has an edge when the distribution changes rapidly, c.g. when cases surge.
CONCLUSION
This paper introduces a novel type of online algorithms to ensure calibration, where we start with an algorithm that guarantees calibration in the i.i.d. setup, and make modifications whenever it fails to achieve calibration. Future work can explore its application to other calibration definitions or more generally, other online learning problems.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM 2019.
SIGKDD international conference on knowledge discovery & data mining, pp.
Glenn W Brier. Verilication forecasts expressed in terms of probability, Monthly weather review, 78(1):1-3, 1950.
Evgeny Burnaev and Vladimir Vovk. Efficiency of conformalized ridge regression. In Conference on Learning Theory, pp. 605-622. PMLR, 2014.
Nicolo Cesa-Bianche and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
A Philip Dawid. Present position and potential developments: Some personal views statistical theory the prequential approach. Journal of the Royal Statistical Society: Series A (General), 147(2): 278-290 1984.
Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift. arXiv preprint arXiv:2106.0011 70,70, 2021.
Tilmann Gneiting, Fadoua Balabdaoui, and Adrian Raftery. Probabilistic forecasts, calibration and sharpness. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(2): 243-268, 2007.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pp. 1321-1330. PMIR, 2017.
Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cal- ibration for the coomputaionally-ddeniffaab masses. In International Conference on Machine Learning, pp. 1939-1948. PMLR, 2018.
Volodymyr Kuleshov and Stefano Ermon. Estimating uncertainty online against adversary. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In International Conference on Machine Learning, pp. 2796-2804. PMLR, 2018.
Meelis Kull, Miquel Perello-Nicto Markus Kängsepp. Hao Song, Peter Flach, et al. Beyond temper- ature scaling: Obtaining well rell-calibrated multiclass probabilities with dirichlet calibration. arXiv preprint arXiv: 12656, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predic- tive uncertainty estimation using deep ensembles. Advances in neural information processing systems, pp. 6402-6413, 2017.
Nicolas Minorsky. Directional stability of automatically steered bodies. Journal of the American Society Naval Engineers, 34(2):280-309, 1922.
Allan Murphy. A new vector partition of the probability score. Journal of applied Meteorology, 12(4):595-60)) 1973.
Alexandru Viculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised leam- ing. In Proceedings of the 22nd international conference on Machine learning, pp. 625-632. ACM, 2005.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. INTECH Open Access Publisher Rijeka, 2008
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
10

---

Under review as a conference paper at ICLR 2022
Evan L Ray, Nutcha Wattanachit, Jarad Niemi, Abdul Hannan Kanji, Katie House, Estee Y Cramer, Johannes Bracher, Andrew Zheng. Teresa K Yamana, Xinyue Xiong, et al. Ensemble forecasts of coronavirus disease 2019 (covid- 19) in the us. MedRXiv, 2020.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad-
vances in Neural Information Processing Systems, 32:3543-3553, 2019.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9Mar))331 4211, 2008.
Hao Song, Tom Diethe, Meelis Kull, and Peter Flach. Distribution calibration for regression. In International Conference Machine Learning, pp. 5897-5906. PMLR, 2019.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel J Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. arXiv preprint arXiv:1904.66019 2019.
Philippe Van Kerm. Adaptive kernel density estimation. The Stata Journal, 3(2):148-13) 156, 2003.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world.
Springer Science Business Media, 2005.
Vladimir Vovk, Ivan Petej, Paolo Toccaceli, Alexander Gammerman, Erast Ahlberg, and Lars Carls- son. Conformal calibrators. In Conformal and Probabilistic Prediction and Applications, pp- 84-99, PMLR, 2020.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In Ieml, volume 1, pp. 609-616. Citeseer, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. In Proceedings of the eighth ACM SIGKDD international conference Knowl- edge discovery and data mining, pp. 694-699. 699. ACM, 2002.
Shengjia Zhao, Tengyu Ma, and Stefano Ermon. Individual calibration with randomized forecasting. arXiv preprini arXiv:2006. 2022200066.288 10288, 2020.
Shengjia Zhao, Michael P Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. Calibrating predic- tions to decisions: A novel approach to multi-class calibration. arXiv preprint arXiv:2107.05719, 2021.

---

Under review as a conference paper at ICLR 2022
A PROOFS
Theorem 1. Let z be generated by any forecasting algorithm and bounded in I-B. B), for any
8 > 0, the prediction algorithm defined by Eq. is b-calibrated where b(T)) (T) log 1og (2 1)++
! We prove that at any time i we cannot have | - d. > (1) + log(1 + / + 1. This equivalent two statements that we prove separately by induction
Proof of Theorem
Fx 2 out (t) log(1 + +2B)/8- -1
(7)
F - out + (t( + log(1 +B))
(8)
To prove Eq.77 suppose at time we have F 2 agt - (t(() -log(1 + 2B)BB - 1, then there are two situations:
Case 1. F 2 agt (t) - log(1 + 2B)/B, then we naturally have
F1+1
2 F 2 out - (C) log(1 + 2B)/3 > au + bz + log(1 + 2B)/B -
(9)
Case 2. Fg < aagl- bb(() - log(1 + 2B) then by Eq. 3 we have
E > 1 2B - 1 2B
By the boundedness assumption,
z++1 S B E++1 < 71+1 + E y
so we must have Fx = F + 1, so
F = Ft + act t- (t) - log( + +B)BBB > ax +1) (t) log(1 + 2B)/3
(10)
Similarly prove Eq, 8) suppose at time we have F < axt (t) + log(1 + 2B)/3 + then at time f + 1 we must have
Ftt
log(1 2B)/3 +1
(11)
Theorem 2. Suppose the initial predictions are feasible (i.e. 2% 2t Ex+1 Vl, k). For some 2/3,
Algorithm 7 b-calibrated where b(T) (TKb3(T) + Ke/T, 0) on any transcript that satisfies
Vt T, L (Yt zt) S 21]( (e -.B)),
Proof of Theorem
2 We first sketch our proof strategy. The proof will follow steps:
1. We prove that if an interval contained the label too often, there will be large force difference
E Ej.
2. We prove that if there is large force difference, then the interval will be small.
If at time an interval contains the label N times too often, at some previous time step 1' S f, must have contained the label N times too often and contained the label once again. However, at the interval must have been small, hence the likelihood of the label must be large. Therefore, unless the likelihood is large, interval contain the label too often.
First we show a simple Lemma based on boundedness assumptions. This Lemma a simple conse- quence of the boundedness Y, - B, YK+1 B. We do not this Lemma directly but it will be used in the proof of the other Lemmas.
Lemma 1. Vt, Vk 0, K A B, ~BB DBI B
The following Lemma shows that intuitively, the ground truth label belongs to an interval too often, then there F must be significantly less than F.
12

---

Under review as a conference paper at ICLR 2022
Lemma 2. For any 2/3. F FX Aagt + (t) + then Ex-l Ex <c
Next we show that if the forces E is significantly smaller than Eg then intuitively, this difference in force will "compress" the interval, making it small.
Lemma 3. For any I. 0, if F F < we have A
L-4B 2n
Based on these lemmas we can complete the proof. Suppose some k E E...., and c > 2 we have k+1 F = Aay! + (1) + c, then consider last time that the label belongs to the interval, ie. we want to find the largest l' L such that z' &YE' Y YE+1). For l' we have
F('-1 Ff'-1 R+1
F - F -
(12)
> Dayl (1) + cc-1
(13)
Dayl' (L' + (c+ (1)) 265((')
(14)
2 Da&t' 26g(())(c+1 +c-1
(15)
Where the last inequality is because b3 is monotonically non-decreasing in t. Therefore by Lemma we have
E Ex < 0cc-11/)
(16)
So by Lemma we conclude
AZK AY e/(e-1)/2 -BB
(17)
2n
which implies whenever ((c-1)/2 > 4B, or c > 2 llog(4B)/5
AYE 2nA (e 9/c-1)/2 4B) 2nB(E ((c-1)/2 -4B) Bn A(c-1)/2 4B) (18)
Hence. by the definition of the "likelihood"
L(Y" z")
a++1 akk
(60-1)/22 4B) (K + ((((11))/2 -411)24BB) 4B) (19)
2nB
In other words, unless Et such that T(Y ,2)) 2n](K (e0(c-1)/2 4B), cannot have F Pt Aoul + (1) + c.
Finally we connect the bound on Fi41 F2. with the quantile calibration error.
Lemma 4, For any > 0, if E K, F - Fk v Aag + b, then
max axt Kb
(20)
So combined we have if vt. L(Y", Z²) S 2B(K+1) (elc- 1)/2 - 4B), then
max F aut & 2Kb + Ke
(21)
Finally we prove the lemmas used in this theorem.
Proof of Lemma
2 Suppose Fi - FV. = Aa&t + (t) + c We first use simple algebraic trans- formation to get
( 0k4 - (F) agt) = c (t)
(22)
For notation simplicity denote the first term LHS
Flo1 actit and second term 2b (t) c
F out, simplify the equation
First we consider the scenario where the interval is not the first interval an, On or the last interval OK, 0K++1 1, in other words, consider the situation where & E [1, K 1). There three different
13

---

Under review as a conference paper at ICLR 2022
possible situations: u 2 0, and 0, < 0 and < 00 < 0. Note that never have u 0, 2 0. We separately consider the three situations.
1. If 0, 0 then
E++1 1++1
F k
- ((m-))(()) + - + 1)
(-e
(23)
(((-b)(())) + (vVD)(())) I (lt+)()())
(24)
where the final inequality achieves equality when c- 2b)((), 0
If 0, <
then
F F = _ ((u-b(())) + (e -00((+))(()) -1)
(25)
= ((o+b)(()) +2 -2 +
(26)
where the final inequality achieves equality when u = (c + 2b;(1))/2, -(c+ 22)(()))
3. If u < 0, < 0 then
E+il Ext (e (c- 1) (e ((v+b 1)
(27)
=0-0tu+0)(0)) - (v)b) < - -
(28)
where the final inequality achieves equality when u = 0, = - - -t)
Next we consider the situation where k 0. In this case Fo agt 0 by assumption. So
E = = - (b)g))())))))))))))))))))))))))) (x))))()) + -e e (()+ +
(29)
Next we consider the situation where k = K. Similar to the previous argument, = 0 by assump- tion,
= -- -
1) 1 ((c+b(())
(30)
Combined have Vk, we take the maximum of the lower bounds and have
E - E max + 2, (z())))(1))
(31)
Since 2/8 we can further simplify this expression by observing -2/ + < Bc/2 and
1 (()+ < de < Be/2 so we have
E k+1 E max( 2c 3c/2 + ( < B012
(32)
Proof of Lemma Observe the equilibrium equation D2 BB A Eg and DE+1 B
Agt1 + Fx+1 = 0: by Lemma 1
A < B, > <B B
so consequently we have
A Bk+1 DK+1 + Ext1 + Bx+1
DD Ex As < <-L+43
By the definition of A and Bx+1 we have
AY
2n
<-L+4B
<
(33)
AZr
AY
which implics that
7
L -
4B
AYK
L - 4B
(34)
AYE
2n
A
2n
14

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 4 We prove the contra- posiitvv statement of the Lemma. If max; |F% -2at $ Kb violated, there must be one of two situations:
1. there exists some k such that F aut 2 Kb then
Kb S F ogt
Fo + out
F 0, aut 0
(35)
Σ
FFj FJ-1) - -aa -
Telescope
(36)
0SiSk
$ (h:
1)
max F3j FJ-1) -(a; - -tj-1)t
(37)
jsk
2. there exists some & such that F aut b then
Kb < - F + ard F aK-
Fk+1 l,ak+l==
(38)
Σ (Fj - P) )-1) (a: (kj (3-1))
Telescope
(39)
+
< (K + 1 k)
max F3 イーー1) - (a, - -)
(40)
j2k
In both cases, there must be some j such that
(F) - F 1)-1) - At
(41)
Corollary 1. Suppose the initial predictions are feasible (i.e. 2 < Z
: Vt, k). For some c
2/3, the prediction algorithm in Scction 3.3 is b-calibrated where b(T) = 2K + any transcript that Vt, L(Y*, Z²)= I 2n1((+1) (e 1)/2 -B).
Proof of Corollary 7 To prove this corollary we only have to modify Lemma 2 and the rest of the proof follows as Theorem
Lemma 5. For any 28, Ff F/ = Aogt + (b) + then Et+1 Be/2 +2B.
F+++1
PID- PIDD
Lemma 5 holds because EPID differs from Et by at most B, so
F F++1
P
Fl+1 F++1 2B < Bc/2 2B
(42)
k
B ADDITIONAL EXPERIMENT RESULTS
B. HYPER-PARAMETER TUNING
We tune hyper-parameters parameters that minimize a weighted combination of the expected calibration error (ece) and the pinball loss.
(Wixx) = Wmix + (1- - "mixx Cpinballl
(43)
where Wmix weight coefficient we choose to be 0.4. We use Optuna (Akiba et al. 2019) seek promising syper-paramete candidates. We try 100 hyper-parameter candidates and pick the best hyper-parameter that minimizes the loss function Lmix(Wmix)
As we mentioned in Section 3.4 of task follows:
we use simple synthetic tasks for tuning. We first define the label
=²= bc' c' N(O, 1,.., T)
(44)
15

---

Under review as a conference paper at ICLR 2022
weight (Wmix)
0.0
0.2
0.4
0.6
0.8
1.0
pinball
0.155
0.155
0.159
0.155
0.166
0.178
calibration
0.021
0.015
0.009
0.022
0.007
0.008
sharpness
0.811
0.826
0.859
0.812
0.921 0.972
Table 2:
Comparison of performance metrics between weight Wmix
regression benchmark data
test on stock
covid
0.17
0.11
0.16
0.10
text
0.09
test
0.08
0.15
0.14
0.06
0.07
0.04
0.12
0.14
0.16
0.12
0.14
0.16
0.12
0.14
0.16
train loss
train loss
train loss
Figure 6: Comparison of loss values between synthetic data and other datasets, where each point corresponds to a syper-paramettr candidate which is obtained during hyper-paramete search. The x-axis and y-axis show loss values on synthetic dataset and other datasets, respectively. The perfor- mance simple synthetic data is highly correlated with the performance real data.
where coefficients a and b are sampled by a ~ (O, 1) and ~ U(O, 1). We also set predictions 2' F=+ where F is the cumulative distribution function of standard Normal distribution.
After tuning, evaluate the best hyper-parameters for each Wmix other synthetic tasks. Ta- ble compare performance metrics between different Wmixx Large Wmix leads to small calibra- tion loss values and large pinball loss/sharpness values. We adopt Wmix 0.4 since the hyper- parameter provides good calibration and pinball values. The obtained hyper-parameee values are 0.47, 8 = 0.16, ka 0.08, kp 1.00, = 0.96. As for h;, we assume k; depends on quantile level l as follows:
k = ks (k), - mii) | 2(k - 1)/(K-)XX) - 1)1,
K.
(45)
The obtained blyper-paraeene are ki,max 0.09, Ri,min 0.04.
Next we verify that our algorithm is robust to performance of hyper-parameter synthetic sequences and real data. They are highly correlated, which indicates that hyper-parameter that do well on synthetic sequences also perform well on real data.
choice. In Figure 6 we compare the
Finally, we demonstrate that the adopted hyper-parameter in the paper works well compared to "optimal" hyper-parameters for each dataset. Concretely, we tune hyper-parameter regression benchmark datasets with distribution drifts, and compare the tuned mended ones (which are tuned on synthetic sequences). Figure 77 that tuning on each dataset separately (which is only possible for off-line data) only improves performance marginally com- pared to using fixed hyper-paree syper-parameters. This suggests that the recommended hyper-parametc is reasonable choice in variety of cases.
and the recom-
B.2 VISUALIZATIONS OF PREDICTIONS ON VARIOUS DATASETS
In addition to Figure Section we visualize additional example predictions on COVID and re- gression benchmark datasets. Figure shows example predictions on the COVID prediction dataset, and Figure 9 shows example predictions on regression benchmark datasets with distribution drifts. Our method adapts to distribution drifts.
16

---

Under review as a conference paper at ICLR 2022
linear shift
scale shift
conformal
0.12
0.4
regret
0.10
ours
0.3
(adopted)
0.06
0.04
0.4
0.6
0.8
2.10
2.15
jump
cycle
0.20
0.15
0.15
0.10
0.10
0.05
0.05
0.4
0.6
0.7
0.8
0.4
0.5
0.6
0.7
Figure 7: Evaluating the robustness hyper-parameter choice. The r-axis and y-axis shows the pinball loss and ece, respectively. The star is the hyper-parameter we fix throughout the experiments. The red crosses are the hyper-parameters that are optimized on regression benchmark datasets for each distribution drift type respectively. Each red cross in figure corresponds to different weight Wmixx Even though optimizing syper-parametery for each dataset separately can further improve performance, the improvement is minor.
10
25% quantile 75% quantile
quantiles
1.00
10
25% quantile 75% quantile
actuel quantles
1.0
0.8
0.75
abbel veluee
observed label
abserved
0.6
0.50
0.25
0.2
0.00
0.0
20
0.0
30
40
0.0
0.5
Lime Slep
Largel quentiles
Lime slep
Largel quentiles
Figure& 8: Example predictions on the COVID prediction dataset. Left is conformal calibration only, and right conformal calibration + our method. We plot both the sequence of predictions, and the reliability diagram (i.e. the relationship between target frequency 0g and empirical frequency F /T).
17

---

Under review as a conference paper at ICLR 2022
12.5
25% quantile
10.0
75% quantile
label valuue
label
0.4
0.5
0.00
0.75
1.00
time step
target
1.0
quantile
30
75% quantile
0.8
label value
true labe!
20
actual
0.6
10
0
3030000000 90000/-30- 3000000000000 Je "36-0
X0000
0.0
80
0.00
0.25
050
0.75
1.00
step
target
1.0
10.0
25% quantile
75% quantile
label value
7.5
0.2
0.0
NXX volk So
0.00
075
time step
target
25% quantile
75% quantile
0.8
labe! value
true label
W0t
actual
0.6
0.0
40
60
80
0.00
0.25
0.0
0.75
1.00
time step
target
Figure 9: Example predictions on regression benchmark datasets with distribution drifts. From top to bottom, apply 'linear shift', 'saale shift', 'jump', and 'cycle'. respectively. We plot both the sequence predictions, and the reliability diagram (i.e. the relationship between target frequency og and empirical frequency F IT).
18

---

Under review as a conference paper at ICLR 2022
C EXPERIMENT DETAILS
Stock Dataset For stock we predict quarterly earnings per share (EPS) for S&P 500 stocks from 2010/01 to 2021/03. We analyst earnings forecasts provided by I/B/E/S the original predic- tion. To remove stocks with low quality data, we apply the following filtering rule for each stock.
1. exclude analyst forecasts whose missing rates are over 20%
2. if the number of analysts is less than five, remove the stock
3. if all remaining analysts do not predict earnings least quarter, remove the stock
By the above procedure, 279 stocks are selected from 500 stocks in S&P 500. The average number of analysts per stocks is 9.3 and each time series length is 45 data points.
COVID dataset For COVID we predict COVID cases for the next week. We use expert forecasts from the COVID forecast hub (Ray et al. 2020). Because the data is heavy tailed, we transform all forecasts and labels by 7 + log(1 + Z) and predict the transformed label. We select the teams and locations that do not have missing predictions during the period between Aug 2020 and Aug 2021 (6 teams) as the original prediction, and randomly sample 100 locations. The time series length is 56 data points (so approximately one year data).
Regression Benchmarks We use the following UCI datasets: blog, boston, concrete, crime, energy-efficiency. fhcomment-l, fbcomment-2, forest-fires, mpg, naval, power-plant, protein, su- perconductivity, wine, and yacht. In addition UCI datasets also common regression datasets in the uncertainty quantification literature, which are kin8nm and medical-expendittre. We use 100 samples for each test dataset, i.e., the length 100.
Distribution drifts
For the regression benchmarks we consider four types of artificial distribution drifts. The definition of the distribution drift is given by
linear shift: add linear drifts to the labels, i.e., Y Y + St
scale shift: change the scales of the labels, i.e., y = Y1(1 BV()
jump: jump the mean at the halfway point, i.e., y = Y (1 < T/2), y Y 4 (12 T/2)
cycle: add fluctuations to the labels, i.e., y = Y sin((21
In the experiments, we set coefficient 3 = =0.1, 1.0, for linear shift, scale shift, jump, and cycle, respectively.
C.I DOWNSTREAM TASK DETAILS
COVID Decision Making We consider the following simple decision loss: for each county, there are four tiers of response 0,1,2,3. higher tier response needed whenever there are more fore- casted cases. Let denote the response, and denote the (log) cases, we choose the loss function as the sum of COVID losses and shut-down losses, respectively defined as
a
a
0
COVID loss
0
0
0
0
4 4<250
1
0
6 < 8
3
2
0
0
2> 8
6
5
3
0
Shutdown loss
0
0.3
0.7
1.0
C.2 ONLINE LEARNING BASELINE
We adopt Algorithm in Kuleshov & Ermon 2017) based on internal regret minimization, use exactly the same algorithm except that (Kuleshov & Ermon 2017) minimizes the L2 loss or Brier loss (which are proper scoring rules for the conditional expectation), while minimize the
19

---

Under review as a conference paper at ICLR 2022
pinball loss (which is the proper scoring rule for quantiles). In addition, separately calibrate the different quantiles Y1.... YK (i.c. for each it we run a separate instance of modified Algorithm in (Kuleshov & Ermon 2017)).
The original procedure (Kuleshov & Ermon 2017) can guarantee calibration in the binary classifi- cation setting: give intuition why modification can guarantee calibration in the regression setting. we first bin the possible regression outputs into . equal sized bins B = y0
= B. As notation convenience, denote the center of each bin as ymn Vm fym-1
2
Consider the 04-th quantile, goal is to minimize the interval regret under the pinball loss, define by Ve E BB
R Rinterval =
(c, z²) -inf) Σ T(Y = Cinbball (y, 2t)
Intuitively, among the time that the true label equals there that achieves lower pinball loss, Because pinball loss is proper scoring rule, Rinterval = 0 implies that e is the ou-quantile of {Z' Y c). i.e. for this subset of samples, the true label Zt is below the prediction Y for ar proportion of times. This is exactly the definition of calibration. To implement the algorithm realistically, we have to choose a suitable binning strategy, as well internal regret minimization algorithm. We use the same choice as the experiments in (Kuleshov & Ermon 2017). Note that to choose the binning strategy we have to know the lower bound and upper bound of the data. We give the bascline an unfair advantage by choosing the lower bound as the lowest value the data, and the upper bound as the highest value the data (up to a 10% margin).
better alternative prediction
20


Reviews:
[{"review_id": "iy11MAPo0p", "reviewer": "Reviewer_3r9U", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper mainly focuses on the online setting with distribution drifts. \n* For calibration, the conformal learning is used which is not new. \n* For distribution drifts, the PID control is introduced with theoretical guarantee. \n* The major concern lies in the experimental part. This paper considers four types of drifts but the the drift data are synthetic. Is there any real applications that needs distribution drifts?\n* For baselines, is there any online variants of the existing methods? Although the current calibration/Bayesian methods are not directly available for distribution drifts, there should be some prompt apply and variants of these existing methods that need to be added as baselines. ", "summary_of_the_paper": "This paper proposes a online regression calibration method using conformal and control theories. Theoretical and experimental results are provided.", "summary_of_the_review": "This paper considers an new but important branch of truthworthy regression/forecasting, online learning with distribution drifts. The draft is clearly written but some concerns lie in the novelty and experimental setting.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Tnovew-hpbn", "reviewer": "Reviewer_DfEt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "While the authors try to explain intuition through several analogies from physics and dynamical systems, the paper is still sometimes hard to follow. I was wondering whether the authors could comment on the following questions:\n\n--- The paper heavily refers to conformal calibrators. In the current form, it seems to be a bit hand-wavy, so a slightly more detailed description of the procedure (either in the main paper or in the Appendix) would be helpful to the reader.\n\n--- The confidence interval (CI) statement at the beginning of section 3.1 seems to be a bit odd as usually CIs are constructed for unknown parameters, while here it is used for testing for the i.i.d. assumption (a side note: presumably $\\geq$ sign should be used in place of equality). Continuing on the same part, shouldn't one look at confidence sequences instead of confidence intervals for the sample average of Bernoulli trials? That is, confidence intervals usually require pre-specified sample size to be valid (and thus are not fully applicable to sequential settings), while confidence sequences yield guarantees that are time-uniform, and thus allow for data-adaptive collection settings.\n\n--- in the proof, it seems to be used that $b_\\delta^*(t+1)>b_\\delta^*(t)$, which is not discussed. Is it indeed the case? In general, slightly more details for this proof are needed (including the base case for the induction and more elaboration on omitted steps)\n\n--- Solving the equilibrium equations (as in eq. 4). How is it done exactly? A bit of guidance on algorithmic aspects, computational complexities etc. could be helpful.\n\n--- A side note about some typos: a) before stating equation (3), it is mentioned that eq. 3 states a prediction for $Y^t_k$. Shouldn't it be $Y^{t+1 }_k$? Similarly, just formally, shouldn't $Z^{t+1 }_k$ also be clipped in $[-B,B]$? b) A general suggestion could be to move the related work section to an earlier part of the paper for better readability.", "summary_of_the_paper": "For real-world applications where ML models are used, quantifying predictive uncertainty is an essential task as, for example, in safety-critical applications misclassification might have disastrous consequences. On the theory side, the analysis is typically performed under the i.i.d. assumption which could be unsatisfactory as deployed models inevitably encounter changes in the data generating distribution and/or certain dependencies that invalidate the results established for the i.i.d. setting. Focusing on regression, the authors design an adaptive (to distribution shifts) procedure that satisfies a certain calibration guarantee. The authors study the empirical performance of the proposed procedure on a collection of time-series and regression datasets.", "summary_of_the_review": "Lowering the score is mainly motivated by the issues that are discussed in the main review. Unless resolved, the general recommendation for the current work is that it is below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RXzD3q9XmTn", "reviewer": "Reviewer_Lt92", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper investigates the problem of calibrating regression outputs with a distribution drift setting. Given that existing regression calibration methods relies on the i.i.d samples to estimate the empirical quantiles, it is interesting to see how the authors would tackle the more complicated problem of a non-iid data source. \n\nThe author first introduced an easier requirement of online quantile calibration, where the calibration error can be accepted up to a given function $b(T)$ at time step $T$. While the author initially suggested the function $b$ can be arbitrary, it later shows that the function needs to be specified for the proposed calibration method.\n\nThe proposed solution is then based on an online adjustment scheme. While the intuition is straightforward (change the prediction value if it is outside of the current confidence interval), it is unclear whether the authors pick this particular exponential form to adjust the predicted quantile value. The adjustment scale is about $1$ and an exp term and not about the original scale of $Y$.\n\nLater in theorem 1, the authors show that the previous methods can achieve the so-called b-calibration if the function $b$ is given in a particular form. Again, here the author didn't elaborate regarding the choice of $b$, and it is likely that it needs to be selected according to eq.3 (or vice versa) to ensure the theorem stands.\n\nAs the algorithms only work on each quantile, the authors later provide an adjustment method to ensure all the quantiles are monotonic and another PID-control based approach to improve the stability of quantiles. \n\nExperiments are mainly conducted against the standard conformal calibration approach, and some improvements can be observed.", "summary_of_the_paper": "This paper considers the problem of calibrating quantiles outputted by a regression model. The data is assumed to draw from a non-iid source (e.g. time series with distribution shift).\nThe paper proposes a method that adjusts the output quantiles to be better calibrated for a less-restricted definition of b-calibrated.\nSome further methods are also proposed to ensure the quantiles are monotonic and stable.\nExperiments are conducted to compare the proposed method with uncalibrated models and conformal predictions.", "summary_of_the_review": "While this paper is working on a very attractive problem and provides a working solution, some technical decisions require further elaboration to make the paper technically stronger. \n1. The choice of the $b$ function and adjustment in eq.3 needs to be further discussed. Otherwise, Theorem 1 seems to be solving a self-defined problem.\n2. While the methods used to ensure monotonicity and stability seems to work well in the current experiments, it is unclear whether it will require such complicated steps to solve the issue. I wonder if a regularisation term plus isotonic regression on the $Z^t_{k}$ would also solve the problem while always ensuring monotonicity. \n3. Improve model under distribution-shift is a well-established domain, I wonder if other reviewers with a stronger background in out-of-distribution prediction could enlighten if there are any good baseline to compare.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FFF1JCsornH", "reviewer": "Reviewer_Kb8i", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "**Strengths**\n1. calibration for online regression is an important problem and well-motivated.\n2. The proposed algorithm is well-supported by theory. \n\n**Concerns**\n1. It is counter-intuitive that applying PID control does not break the calibration guarantee for any PID parameters; in control theory, given a plant (or model dynamics), only a few combinations of PID parameters can make the system stable. However, Corollary 1 states that the proposed algorithm is b-calibration for all PID parameters, which may need additional explanation. Could you clarify this?\n2. I think the modeling choice (3) implicitly makes some assumptions on the underlying distribution drift, which is also assumptions on the theorems and corollary. In particular, (3) adjusts calibration values made by the iid algorithm (e.g., conformal calibration) with exponential models; this implies that the distribution shift may not be significant. Are you making assumptions on distribution drift? If so, could you clarify the underlying assumption on (3)?\n3. Related to the above two points, it's not easy to believe that hyper-parameter tuning is easy; in particular, PID parameter tuning is generally known to be difficult without knowing model dynamics. I guess the reason that the hyper-parameter tuning is easy can be implicit assumptions on the distribution drift, but it's unclear as it is written now. Could you discuss convincing reasons that the tuning is easy (in particular the PID parameters)?\n4. The connection between theory and empirical results is loose; is the proposed algorithm empirically b-calibrated? If so, could you add empirical results/evidences?\n5. I believe that well-known and acceptable regression calibration approaches under iid (in particular [R1]) need to be compared; even though this paper address online regression, it's necessary to compare with the well-known and acceptable iid regression calibration algorithms to show the efficacy of the proposed approach under distribution drift (along with conformal calibration). \n6. I think ablation study makes this paper stronger; could you add this (e.g., by adding \"Basic + Feasibility\" algorithm performance)?\n7. other comments:\n* \"transforms a initial predictor\" -> \"transforms an initial predictor\"\n* What are \"Bench-shift\" and others? They are not defined. \n\n[R1] https://arxiv.org/abs/1807.00263", "summary_of_the_paper": "This paper consider calibrated online regression; to attack this problem, this paper proposes a new calibration algorithm (i.e., adjusting conformal calibration for distribution drift by ensuring feasibility and improving stability) and proves the proposed algorithm is \"b-calibrated\" (as defined in the paper). The proposed approach is evaluated two time series data (i.e., stock and COVID) and 17 regression datasets, and demonstrated that it outperforms three baselines in terms of two calibration metrics (i.e, pinball and ECE).", "summary_of_the_review": "I think this paper considers an interesting and important problem; the proposed approach is novel, but it not well justified in theoretically and empirically as mentioned in the main review. I'm willing to adjust my understanding and score as well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an important problem of quantifying uncertainty (as measure by calibration) of predictions made by an ML algorithm in the presence of distribution drift. However, all reviewers point out a slew of concerns that went un-rebutted by the authors. The reviewers concurred that the paper deserved to be rejected at the current stage, and I concur. I recommend that the authors take the critical and constructive feedback into account to improve the paper and perhaps resubmit to a different venue in 2022.
Decision: Reject