Risk Control for Online Learning Models
Authors: Shai Feldman
Liran Ringel
Stephen Bates
Yaniv Romano
Venue: Submitted to ICLR 2023 (2023)
Keywords: Conformal Prediction
Uncertainty Quantification
Time Series
Online Learning

Abstract: To provide rigorous uncertainty quantification for online learning models, we develop a framework for constructing uncertainty sets that provably control risk---such as coverage of confidence intervals, false negative rate, or F1 score---in the online setting. This extends conformal prediction to apply to a larger class of online learning problems. Our method guarantees risk control at any user-specified level even when the underlying data distribution shifts drastically, even adversarially, over time in an unknown fashion.
The technique we propose is highly flexible as it can be applied with any base online learning algorithm (e.g., a deep neural network trained online), requiring minimal implementation effort and essentially zero additional computational cost.
We further extend our approach to control multiple risks simultaneously, so the prediction sets we generate are valid for all given risks.
To demonstrate the utility of our method, we conduct experiments on real-world tabular time-series data sets showing that the proposed method rigorously controls various natural risks. 
Furthermore, we show how to construct valid intervals for an online image-depth estimation problem that previous sequential calibration schemes cannot handle.

Under review as a conference paper at ICLR 2023
RISK CONTROL FOR ONLINE LEARNING MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
To provide rigorous uncertainty quantification for online learning models, we develop framework for constructing uncertainty sets that provably control risk- such as coverage of confidence intervals, false negative rate, or F1 score-in the online setting. This extends conformal prediction to apply to larger class of online learning problems. Our method guarantees risk control at any user- specified level even when the underlying data distribution shifts drastically, even adversarially, over time in an unknown fashion. The technique we propose is highly flexible as it can be applied with any base online learning algorithm (e.g., a deep neural network trained online), requiring minimal implementation effort and essentially zero additional computational cost. We further extend our approach to control multiple risks simultaneously, so the prediction sets we generate are valid for all given risks. To demonstrate the utility of our method, we conduct experiments on real-world tabular time-series data sets showing that the proposed method rigorously controls various natural risks. Furthermore, we show how to construct valid intervals for online image- estimation problem that previous sequential calibration schemes cannot handle.
INTRODUCTION
To confidently deploy learning models in high-stakes applications, we need both high predictive accuracy and reliable safeguards to handle unanticipated changes in the underlying data-generating process. Reasonable accuracy on a fixed validation is not enough, raised by Sullivan (2015); we must also quantify uncertainty to correctly handle hard input points and take into account shifting distributions. For example, consider the application of autonomous driving, where we have a real-ting real-time view of the surroundings of the car. To successfully operate such an autonomous system, we should measure the distance between the car and close-by objects, e.g., via sensor that outputs depth image whose pixels represent the distance of the objects in the scene from the camera. Figure la displays a colored image of road and Figure 1b presents its corresponding depth map. Since high-resolution depth measurements often require longer acquisition time compared to capturing a colored image, there were developed online estimation models to predict the depth map from a given RGB image (Patil et al., 2020; Zhang al., 2020). The goal of these methods is to artificially speed-up depth sensing acquisition time. However, making decisions solely based on an estimate of the depth map is insufficient as the predictive model may not be accurate enough. Furthermore, the distribution can vary greatly and drastically over time, rendering the online model to output highly inaccurate and unreliable predictions. In these situations, it is necessary to design a predictive system that reflects the range of plausible outcomes, reporting the uncertainty in the prediction. To this end, we encode uncertainty in a rigorous manner via prediction intervals/sets that augment point predictions and have long-range error control. In the autonomous driving example, the uncertainty in the depth map estimate is represented by depth-val valued uncertainty intervals. In this paper, we introduce a novel calibration framework that can wrap any online learning algorithm (e.g., an LSTM model trained online) to construct prediction sets with guaranteed validity.
Formally, suppose an online learning setting where we are given data stream ((,,, Y:) HeN in sequential fashion, where X, E X' is a feature vector and Y, E )/ is a target variable. In singlc-output regression settings y = IR, while in classification tasks y is finite set of all class labels. The input X₁ is commonly a feature vector, i.e., X IP, although it may take different forms, as in the depth sensing task, where X, E R MxN33 is RGB image and Y, E R MxN is the ground truth depth. Consider loss function L(Y,, (X.)) E R that measures the error of the estimated prediction

---

Under review as a conference paper at ICLR 2023
set (X,) S with respect to the true outcome Y. Importantly, each time step E N, given all samples previously observed {(X,, i= along with the test feature vector Xt, goal is to construct prediction set Cx(),) guaranteed attain any user-specified risk level r:
T 1(V. ((,))
R(C)
lim T E
For instance, natural choice for the loss L in the depth sensing task is the image miscoverage loss:
MN Limage miscovernge (Y,, O(X.) 1 (m,, n.) Ymmin & Cmm.n (Xi)
In words, Limage miscoverage (Y, ((X)) is the ratio of pixels that were miscovered by the intervals Cm,, where (mz n. is the pixel's location. Hence, the resulting risk for the loss in (2) measures the average image miscoverage rate across the prediction sets {C,(X,) and
20% is possible choice for the desired miscoverage frequency. Another example of a loss function that is attractive in multi-label classification problems is the false negative proportion whose corresponding risk is the false negative rate.
In this work, introduce rolling risk control (Roll moolling RC): the first calibration procedure form prediction sets in online settings that achieve any pre-specified risk level in the sense of (1) without making any assumptions
the data distribution, as guaranteed by Theorem 1. We accomplish this by utilizing the mathematical foundations of adaptive conformal inference (ACI) (Gibbs & Candes, 2021) which is groundbreaking conformal calibration scheme that constructs prediction arbitrary time-varying data distribution. The uncertainty sets generated by ACI are guaranteed to have valid long-range coverage, being a special case of (1) with the choice of the 0-1 loss (indicator function) defined in Section 2. Importantly, one cannot simply plug an arbitrary loss function into ACI and achieve risk control. The reason is that ACI works with conformity scores-a measure of goodness-of-fit-tee that only relevant to the 0-1 loss, but do not exist in the general risk-controlling setting. Therefore, our Ro ling RC broadens the set problems that ACI can tackle, allowing the analyst to control arbitrary loss. Furthermore, the technique guaranteed to control multiple risks, and thus constructs sets that are valid for all given risks over long-range windows in time. Additionally, the proposed online calibration scheme is lightweight and can be integrated with any online learning model, with essentially zero added complexity. Lastly, in Section 3.2.1 carefully investigated design choices of method adapt quickly distributional shifts. Indeed, the experiments conducted on real benchmark data sets, presented in Section 4, demonstrate that sophisticated designed choices lead improved performance.
for any
proposed in Section 3.3 is
II
80
60
40
20
Input Frame
(b) Ground Truth Depth
60
40
20
(c) Estimated Depth
(d) Uncertainty Size
Figure 1: Online depth estimation. The input frame, ground truth depth map, estimated depth image, and interval's ' size time step 8020. All values are meter units.
2

---

Under review as a conference paper at ICLR 2023
1.1 UNCERTAINTY QUANTIFICATION FOR ONLINE DEPTH ESTIMATION
Recall the online depth sensing problem, where our goal is to construct a prediction interval CX,, C for each pixel (m, n) that contains the ground truth depth Y.m. 80% frequency. That is, we aim at controlling the image miscoverage loss (2) at level r = 20%. To accomplish this, we apply our Ro Rolling ling RC framework using a neural network model for depth estimation; in Ap- pendix C.2.4 give more information regarding the online training scheme and the implementation details. At a high level, we fit (offline) an initial predictive model on the first 6000 samples to obtain reasonable predictive system. Next, passing time step 6001, we proceed by training the model in an online fashion while applying our calibration procedure, and then measure the performance on the data points corresponding to time steps 8001 to 10000.
Figure Ic shows the estimated depth image generated by the base model and Figure 1 displays the size of the prediction interval of each pixel at timestamp / 8020. These figures suggest that the calibrated uncertainty intervals properly reflect the ground truth depth. Furthermore, Figure presents the image coverage rate and average length across the test timestamps. revealing that the proposed method accurately controls the risk with an average image coverage rate of 80%.
100
Average Length
60
Coverage
75
20
8000
8500
9000
9500
10000
8000
8500
9000 Time
9500
10000
Time
Figure 2: The coverage rate and average interval length (in meters) over each image in the test quence achieved by the proposed uncertainty quantification method. The average coverage is 80.00% and the average length is 18.04 meters.
BACKGROUND
Conformal inference (Angelopoulos Bates, 2021; Vovk al., 2005) a generic approach for constructing prediction sets in regression classification tasks that attain any pre-specified coverage rate, under the assumption that the training and testing points are i.i.d., or exchangeable. One example of such method is Split conformal prediction (Lei al., 2018; Papadopoulos et al., 2008). In nutshell, the idea is to split the observed labeled data into training and calibration sets, fit a model on the training set, and evaluate the model's goodness-ot of-ss---fffff ff-fit on the reserved holdout calibration points. Under the i.i.d assumption stated above, the prediction sets produced by split conformal prediction guaranteed to have the following coverage property: (X, Y) is a fresh data point and a is pre-specified miscoverage rate.
E[ (Y $ C(X)H 2 a, where
While coverage rate is an important property, in real-worie applications, is often desired control metrics other than the binary loss 1(Y & C(X) that defines the coverage requirement. Such losses include the Fl-score or the false negative rate, where the latter is attractive for data with high-dimensional Y as in image segmentation tasks or image recovery applications. Indeed, there have been developed extensions of the conformal approach that go beyond the 0-1 loss, rigorously controlling more general loss functions (Angelopoulos et al., 2021 2022a; Bates et al., 2021). Analogously to split conformal prediction, these methods provide risk-controlling guarantee that holds under the i.i.d. assumption. In particular, such guarantees do not hold for time-varying data with arbitrary distributional shifts, as the i.i.d. assumption would not hold anymore.
Since the i.i.d assumption of the conformal approach is often violated in real-world applications, there have been developed extensions to conformal inference that impose relaxed notions of exchangeability (Cauchois al., 2020: Chernozhukov et al., 2018: Stankeviciute et al., 2021; Tibshirani et al., 2019; Xu & Xie, 2021a;b) Such methods, however, are not guaranteed to construct prediction sets with a valid coverage rate for general time-series data with arbitrary distributional shifts. By contrast, ACT
3

---

Under review as a conference paper at ICLR 2023
(Gibbs & Candes, 2021) generates uncertainty sets that are guaranteed to achieve user-specified level of the 0-1 loss:
1 Y Cx()),
(Y, C(X,)) - (003))))=Lxeeeee) ((necrx)) - (0, otherwise.
(3)
A recent work by Gibbs & Candès (2022) proposes a more sophisticated approach to track past coverage rates better adapt distributional shifts. In general, this line of research based on a common, simple idea-if the past coverage rate is too high, we shorten the intervals, and if it is too low, we widen them. In this paper, we also rely on the above update rule, however, guarantee the control of general risk, standing in contrast with ACI that controls only the binary loss in (3). Therefore, our approach is the first online calibration scheme that can control risks other than the coverage frequency.
PROPOSED METHOD
3.1 GENERAL FORMULATION
We now turn present Rollinn ling RC-a general framework for uncertainty quantification in an online learning setting, which satisfies the risk requirement in (1). Towards that end, we define a set construction function
((xx))=((x,,00)
E E
that gets as an input (i) the test Xt, (ii) a fitted model M, trained on all data {Xrr, Y Yo up to time f. and (iii) a calibration parameter 8,, and returns a prediction set. Above, 2n is the power set of y. For instance, in the depth prediction task in Section 1.1, f constructs prediction interval for each pixel in the image, as visualized in Figure 1d. The model M,(X,) is used to form a prediction for Yt given the current feature vector X₁; we will provide soon concrete formulations for the set constructing function f as well as examples for M. The calibration parameter 0g E R controls the size of the prediction set generated by f: larger 6g leads to larger sets, and smaller 63 leads to smaller sets. Under the assumption that larger sets produce lower loss, O, allows us to control the risk over long-range windows in time: by increasing (resp. decreasing) Og over time we increase (resp. decrease) the empirical risk. Once Y, is revealed to us, we tune 0, according to the following rule:
Oz+1 02 +
(5)
This update rule is exactly that of ACT (Gibbs & Candès, 2022), extended to our more general setting. Above, 4 = L(Y,, C(X))) is the loss at time t, and 7 > 0 is a fixed step size, e.g., 0.05. In Appendix C.3.3 we study the effect of y on the resulted sets and provide suggestion for properly setting it. The pre-defined constant is the desired risk level, specified by the user, e.g., 0.2 for the image miscoverage loss in (2). Lastly,
obtain new predictive model M by updating the previous M2 with the new labeled pair (X,, Yi), e.g., by applying a single gradient step to reduce any given predictive loss function. For convenience, the Rolling RC procedure is summarized in Algorithm 1. The validity of our proposal is given below, whose proof is deferred to Appendix A. In Appendix A.2 we introduce a more general theorem that extends the domain of Ó₂ beyond the power set n
Theorem 1. Suppose that f (X, MI) 2 is an interval/set constructing function. In addition, suppose that there exist constants m and M such that for all x E X. E y and M E M. for all 8 m. Further suppose that the loss is bounded and satisfies L(y,3) < and L(y. 0) > r. Consider the following series of calibrated intervals: {C)(X: where (,(X,) is defined according (4), Then, the calibrated intervals satisfy the risk requirement in (1).
fa O.M for all 8 > M, f(X, M)
Crucially, this theorem states that the risk-control guarantee of Rolling RC holds for any distri- bution (Px,,t Jt, any set-valued function f. and any sequence of online-updated predictive models {Mc.).. The requirements for Theorem 1 to hold are (i) the function f must yield the empty set for small enough 0 and the full label space for large enough 0; and (ii) the loss is smaller than the desired level r for the full label set y and exceeds r for the empty set. Also, note that the step size ry and the bounds m, M must be fixed in order control the risk.
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Rolling RC
Input:
Data ((x,, K.) X x V. given as a stream, desired risk level r IR, a step size 7 > a set constructing function f (X, IR, Ml) - 2 and an online learning model M.
Process:
Initialize 8U
2: for = 1.... T do
3: Construct prediction set for the new point N₂: Cx())) f(X,,
4: Obtain Y,
5: Compute 4 - L(Y,, (X.)).
6: Update 02+1 = 0: + 7/ -r).
7: Fit the model Mr on (X,, Yt) and obtain the updated model MM+1
8: end for
Output:
Uncertainty sets (x,) for each time step & E (1....})
Observe that our method is immune to over-fitting by design even though we use the same data point twice: the evaluation of 0, is conducted by using the predictions produced by an "old" model, before updating it with the new labeled point. We also note that the proof of Theorem 1 gives finite-sample bounds for how close the realized risk is to the desired level; the empirical risk falls within C/T + 4 BB) is a known constant; Appendix A.1
factor of the desired level r, where C' (M for details. Furthermore, our new formulation unlocks new design possibilities: we can define any prediction set function f while guaranteeing the validity of its output by calibrating any parameter 0,, This parameter can affect / in a highly non-linear fashion to attain the most informative (i.e., small) prediction sets. Of course, the performance of the proposed scheme is influenced by the design of f. which is the primary focus of the next sections.
3.2 ROLLING RC FOR REGRESSION
In this section, we focus on 1-dimensional response variable Y and aim to control the 0-1 loss in (3). Note that in Section 4.1.3 we will also deal with I-dimensional responses but show how to control a more sophisticated notion of error for which the loss is defined on the iime-horioo,, and in Appendix B we provide concrete scheme for handling multi-dimensional Y.
Suppose we are interested in constructing prediction intervals with 1 - a coverage frequency, using a quantile regression model Mr that produces estimates for the a/2 and 1 - a/2 conditional quantiles of the distribution of Y, X,, We denote these estimates as M,(X,, a/2) and M,(X,, aa2)), respectively, which be obtained by fitting L.STM model that minimizes the pinball loss; Appendix 1.1.2 for further details. The guiding principle here is that a model that perfectly estimates the conditional quantiles will form tight intervals with valid risk, attaining 1 coverage level. In practice, however, the model M, may not be accurate, and thus may result in invalid coverage; this is especially true for data with frequent time-varye varying distributional shifts. Consequently, to ensure valid coverage control, we apply Rollin Ling RC. Taking inspiration from the method of conformalized quantile regression (CQR) (Romano et al., 2019), we use the following interval construction function:
(6) Above, the interval endpoints are obtained by augmenting the lower and upper estimates of the conditional quantiles by an additive calibration term ()))). The role of 0g is the same as before: the larger 6, the wider the resulting interval is. Here, however, we introduce an additional stretching function that can scale O, non-linearly, providing us the ability to adapt more quickly to severe distributional shifts. We now present and review three design options for the stretching function sp
f(X,, Mc) = [M, a/2) ((,)), M, - a/2) + ((,))
3.2.1 STRETCHING FUNCTIONS FOR FASTER ADAPTATION
None. The first and perhaps most natural choice is ((x) x, which does not stretch the scale of the interval's adjustment factor. While this is the most simple choice, it might be sub-optimal when an aggressive and fast calibration is required. To see this, recall (5), and observe that the step size
5

---

Under review as a conference paper at ICLR 2023
used update 8g must be fixed throughout the entire process. As result, the calibration parameter 8, might be updated too slowly, resulting in an unnecessary delay in the interval's s adjustment.
The exponential stretching function, defined as p(x) = - for x > 0 and for x S O, updates the calibration adjustment factor with exponential rate: (x)) = = even though the step size for 0₂ is fixed. In other words, it updates (0(O) gently when the calibration is mild (sp(0,) is close to 0), and faster as the calibration more aggressive (pp(0)) is away from zero).
Exponential.
(p(x)) 6 -
Error adaptive. The following stretching function updates 6r more rapidly when the loss of the previous data point 4-1 1 is farther from the desired risk Furthermore, makes larger updates when Y; is far from the interval's boundaries. More formally, denote the CQR non-conformity score (Romano et al., 2019) by
St = max max Y, Y, - -a/2)]
which measures the signed distance of Y, from its closest boundary. Next, define
PPr (0) 0 Ar Amm where X, A.mer clip( A
greure -5 exp {gluxs 1 (e-1--l) r|}
glom, ghighh)
where gloss, greare ,low and ghigh are hyperparameters. The clipping function clip(æ, m, M) max (mmi M) }, m is applied to restrain the effect of an outlier Y, that far from the boundaries.
This discussion above sheds light on the great flexibility of Ro 1 ling RC: we can accurately find the correct adjustment to the uncertainty set while being adaptive to rapid distributional shifts in the data. Furthermore, Theorem guarantees the risk validity regardless of the choice of the stretching function. In Appendix D.I.1 we propose an additional stretching function and compare all proposed stretching functions. This analysis indicates that the 'error adaptive' stretching is the best choice.
3.3 CONTROLLING MULTIPLE RISKS
In this section, we show how to control more than one risk and construct intervals that are valid for all given risks. To motivate the need for such multiple risks controlling guarantee it may be best to consider the depth estimation example from Section 1.1. Here, we may wish to control not only the coverage of the entire depth image, as in Section 1.1, but also the frequency at which the coverage at the center of the image falls below a certain threshold. This design choice meets reality since the coverage at the center falls below 60% in more than 17% of the time-steps, presented in Figure 10 in Appendix D.2. This figure also indicates that controlling the center coverage does not control the center failure loss. Concretely, formulate the center failure loss
Tecenter failure (Y,, C(X,)) =
(m,, n)) E center Y,m." E C (X,) S 60%
center
We define the center of an image as the middlemost 50x50 grid of pixels. Controlling the center failure loss at level 10% ensures that more than 60% of the center will be covered for 90% of the images.
More generally, suppose we given is arbitrary loss functions {Li) and aim to control their corresponding risks, each at level r'. In this setting, the set constructing function J(() gets as an input the test X,, the fitted model Mr, and calibration vector Q R& and returns prediction set
C,(,,) f(x. f( 2
Similarly to the single risk-com controonto formulation described in Section 3.1, 6, controls the size of the generated set: by increasing the coordinates in O, we encourage the construction of larger sets with lower risks, and we tune it likewise:
8/11 = 8 2 21) -r)),
where 1; = LY,., (x))) and '" > 0, 1,..., L is the corresponding step size. We now show that this procedure is guaranteed to produce uncertainty sets with valid risks.

---

Under review as a conference paper at ICLR 2023
Theorem 2. Suppose that f (X, R, - 2 is interval/set centtruttinnguuccti In addition,
suppose that there exist constants {M') such that for all X and M, f M. = = if M for some E {1,...}. Further suppose that the losses are bounded and satisfy (y < for every y E Y and i E [1....}. Consider the following series of calibrated intervals: (C,(),
where (x(X,) is defined according (8). Then, the calibrated intervals attain valid risk:
Vi (1.....k) k} 3D s.t
T LYY, 40Y, S T
1
D'
7-200
If further assume that the risks multiple risks control, as stated next.
synchronized with each other, can achieve exact
Theorem 3. Suppose that f is an interval/set constructing function and {L' are loss functions Ji=1 such that s(X, MM) as in Theorem Further suppose that there exist constants {m" {m²)izz
if O' <. m for some i E }1...k} and that the losses satisfy L' L' 0) > r² for every E y and i {1....k). Then, the intervals achieve the exact risk:
T Σ L(Y,, Cx,,)) T-+00 T
E E (l,...,k: ((()
lim
The proofs of the theoretical results are given in Appendix A. In words, Theorem 2 guarantees the validity of the risks, while Theorem 3 guarantees that all risks are exactly controlled by assuming that during the calibration process there are no two coordinates in 6, such that the first too low (requires widening the interval), and the other is too high (requires shrinking the interval). Lastly, we note that this section we presented one implementation Roll Ling RC to control multiple risks, although other approaches may be valid well, e.g., techniques with calibration parameters that independent of the number of risks.
4 EXPERIMENTS
4.1 SINGLE RESPONSE: CONTROLLING A SINGLE RISK IN REGRESSION TASKS
In this section, we study the effectiveness of our proposed calibration scheme for time series data with 1 1-dimensional response variables. Towards that end, we describe two performance metrics that we will use in the following numerical simulations to assess conditional/local coverage rate.
4.1.1 TIME-SERIES CONDITIONAL COVERAGE METRICS
MC: The miscoverage counter counts how many miscoverage events happened in a row until time
[MC,11+ +1, Y, & ((,))
MC, (0,
otherwise
where MC2- = 0. Similarly the coverage metric, MC, = 0 timestamps for which Y, C,(X)). By contrast, when Y, & (x,)). the value of MC, is the length of the sequence of previous miscoverage events. Therefore, we can apply Rollis illlnng RC to control the MC level and prevent long sequences of failures. Interestingly, controlling the miscoverage counter immediately grants control over the standard coverage metric, as stated next.
Proposition 1. If the MC risk is at most a, then the miscoverage risk is at most a.
In Appendix A.5 we provide the proof of this proposition and in Section E.2 we explain how to choose the nominal MC level to achieve given coverage rate 1 a. In nutshell, argue that model that has access to the true conditional quantiles attains an MC of a/ (1 a). Therefore, in our experiments seek to form the tightest intervals with MC risk controlled at this level.
MSL: As implied by its name, the metric miscoverage streak length evaluates the average length of miscoverage streaks of the constructed prediction intervals. In contrast MC, which is defined
7

---

Under review as a conference paper at ICLR 2023
single timestamp, the MSL is defined over sequence of uncertainty sets (Ci(X))) S _ and
response variables (Y) (Y))=1, C as:
MSL =
Σ TET
minfi:
Yete E Ce+e(Xe4a) or Ti}.
7
where I is set containing the starting times of all miscoverage streaks. The formal description is given in Appendix E.1, where we also show that an ideal model that has access to the true conditional quantiles attains MSL of 1/(1 a). Therefore, we seek to produce the narrowest intervals having an MSL close to this value.
4.1.2 CONTROLLING THE BINARY Loss
In this section, we focus on the more standard long-range coverage loss as in ACI (Gibbs Candes, 2021). We test the performance of Rolling RC on five real-world benchmark data sets with I-dimensional Y: Power, Energy, Traffic, Wind, and Prices. We commence by fitting an initial quantile regression model on the first 5000 data points, to obtain reasonable predictive system. Then, passing time step 5001, we start applying the calibration procedure while continuing to the model in an online fashion; we keep doing until reaching time step 20000. Lastly, measure the performance of the deployed calibration method on data points corresponding to time steps 8001 to 20000. In all experiments, an online fashion, minimizing the pinball loss to estimate the 0.05 and 0.95 conditional quantiles of Y, Xę; these estimates are used construct prediction intervals with target 90% coverage rate. We calibrate the intervals according to (6) and examine two options for the stretching function: (i) no stretching, and (ii) 'error adaptive' stretching, described in Section 3.2.1. Appendix C.1.1 provides more details regarding the data sets and this experimental setup.
fit an L.TTM predictive model (Hochreiter & Schmidhuber, 1997) in
Stretching
energy
energy
energy
None
traffic
Error
traffic
traffic
Dataset
Datasec Daiaa
Dataset
prices
prices
prices
power
power
power
wind
wind
wind
89.75 90.00 90.25 Coverage
1.1
1.2 MSL
1.3
0.9
1.0
Average Length (scaled)
Figure 3: Perforrance of Rolling RC on real data sets, aiming control the coverage rate at level 1 - a = 90%. The length of the prediction intervals scaled per data set by the average length of the constructed intervals. Results evaluated on 20 random initializations of the predictive model.
Figure 3 summarizes the performance metrics presented in Section 4.1.1, showing that both stretching methods attain the desired coverage level; this is guaranteed by Theorem 1. Additionally, this figure indicates that Rolling RC with the 'error adaptive" stretching constructs narrower intervals with better conditional coverage compared to Rolling RC applied without stretching, indicated by the MSL metric. Appendix D.1 we compare Rolling RC to a calibration-set-baae and evaluate the methods using another metric for evaluating conditional coverage for time-series data. These experiments show that constructing uncertainty sets using the conformity scores of a calibration set performs worse than Rolling RC with without stretching.
method
4.1.3 CONTROLLING MISCOVERAGE COUNTER
Figure 4c shows that Rolling llllnng RC applied on the real data sets with the goal of controlling the long-range coverage at level a = 90% achieves MC risk that is higher than a/(1 a) = 1/9. Following the discussion in Section 4.1.1, this indicates that the constructed intervals tend to miscover one or more response variables in consecutive data points. To alleviate this, we repeat the same experiment in Section 4.1.2, but apply Rolling RC to control the MC at level 1/9. The results are summarized in Figure 4, revealing that (i) the MC risk rigorously controlled even though is defined over the time horizon, and (ii) by controlling the MC risk we also achieve valid coverage rate.
8

---

Under review as a conference paper at ICLR 2023
Stretching None Error
energy
energy
energy
traffic
traffic
traffic
Dataset
Dataset
Dataset
prices
prices
prices
power
power
power
wind
wind
wind
0.11
0.12
0.13
90
91
0.11
0.12
0.13
Miscoverage Counter
Coverage
Miscoverage Counter
(a) MC calibration
(b) MC calibration
(c) Miscoverage calibration
Figure 4: Performance of Rolling RC real data In (a) and (b) aim control the
risk at level = a/(1 a) 1/9. In (c) we aim to control the coverage at level - = 90%.
Other details are as in Figure 3.
4.2 HIGH DIMENSIONAL RESPONSE: CONTROLLING MULTIPLE RISKS
In this section, we analyze Rollin Rolling RC for multiple risks in the depth prediction setting. In particular, follow the protocol described in Section 1.1 and apply the multiple risks controlling method from Section 3.3 to control the image miscoverage rate defined in (2) at level 20% and the center failure rate from (7) level 10%. We construct the intervals according (9) from Appendix B, using exponential stretching where the vector 0, is aggregated into a scalar by taking the maximal coordinate this vector. We repeat this experiment for 10 trials. In Appendix C.2 we provide the full details about this experimental setup.
Figure 5 displays the results of Rolling RC obtained by controlling (i) only the image miscoverage loss, and (ii) both the image miscoverage loss and the center failure loss. As portrayed, when Rolling RC set to control only the image miscoverage risk, violates the center failure loss; the center coverage falls below 60% for 17% of the time-steps. However, when applying Rol 1 ling RC to control the two risks, it achieves both a valid image coverage rate, of approximately 85.6%, and valid center failure rate, of 9.9%. This is not surprise, it is guaranteed by Theorem 2.
Image Coverage
90
Average age Length
30
20
Failure
15
80
single risk
multippe risks
single risk
multiple risks
single risk
multiple risks
Rolling RC
Rolling RC
Rolling RC
Figure 5: Performance of Rolling applied control only the 'image coverage' (single risk) or both 'image coverage' and 'center failure' (multiple risks).
CONCLUSION
In this paper, introduced Rolling RC, novel method for quantifying prediction uncertainty for any time-series data using any online learning model. Our proposal is guaranteed to achieve any desired level of risk (1) without making assumptions the data, and can be applied for broad class of tasks, such as regression, classification, image-to-image regression, and more. Furthermore, in Section 3.3 we extended Rol ling RC to provably control multiple risks, that the uncertainty sets it constructs are valid for all given risks. One limitation of our method is the reliance on fixed step size % used to tune the raw risk level; improper choice of this parameter may introduce undesired delays in adapting to distributional shifts. Therefore, it is of great interest to develop procedure that would automatically choose 7, e.g., by borrowing ideas from (Gibbs & Candès, 2022; Zaffran et al., 2022). Meanwhile, we suggested way to overcome this limitation using stretching function s. which leads to improved performance, as indicated by the experiments.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
While valid calibration is an important step toward making learning systems safer, fairer, and more robust, we emphasize that calibration not a panacea and one must always treat data with care- especially when data-driven predictions are used for high-stakes decisions. In particular, the flexibility of our proposed method is mixed blessing, in that the system builder has the ability and responsibility to make important design choices. These choices can have important consequences, be treated with care. We offer initial guidelines herein, acknowledging that of course, they do not anticipate the consequences in all possible use cases. Nonetheless, highlight that uncertainty quantification an important component to designing learning systems to have a positive impact in the real world, where the data are complex and distributions are continually shifting. Our work makes one step toward this goal.
they must
For reproducibility, our code carrying out the experiments herein is included as Supplementary Material with this submission.
REFERENCES
Anastasios Angelopoulos, Stephen Bates, Emmanuel Candès, Michael Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint, 2021a.
arXiv:2110.01052.
Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint wwXiv:2208.02814 2022a.
Anastasios N Angelopoulos, Amit Pal Kohli, Stephen Bates, Michael Jordan, Jitendra Malik, Thayer Alshaabi, Srigokul Upadhyayula, and Yaniv Romano. Image-to- mmage-to-image to-iitggeeeeaaae regression with distribution- free uncertainty quantification and applications in imaging. In International Conference on Machine Learning, pp. 717-730. PMLR, 2022b.
Anastasios Nikolas Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-fiee uncertainty quantification. arXiv preprint, 2021. urXiv:2107.07511
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021b.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael I. Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM, 68(6), September 2021.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint arXiv:2008.cm 20Xx:2000..44667 2020.
Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22
(81):1-42, 2021.
Victor Chernozhukov, Kaspar Wüthrich, and Zhu Yinchu. Exact and robust conformal inference methods for predictive machine learning with dependent data. In Conference On Learning Theory, pp. 732-749. PMLR, 2018
Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Academy of Sciences, 118(48), 2021.
Youngseog Chung, Willie Neiswanger, Ian Char, and Jeff Schneider. Beyond pinball loss: Quantile methods for calibrated uncertainty quantification. A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Energy. Appliances energy prediction. setps://archive. ics www. wtt.eeedmmm/daaasseeeeeee Appl: i ances teeeeeeeeeeeeyeeeeeeeee ion. Accessed: April, 2021.
10

---

Under review as a conference paper at ICLR 2023
Shai Feldman, Stephen Bates, and Yaniv Romano. Improving conditional coverage via orthogonal quantile regression. In A. Beygelzimer, Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun. Vision meets robotics: The kitti dataset. International Journal of Robotics Research (IJRR), 2013.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. In
A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Isaac Gibbs and Emmanuel Candès. Conformal inference for online prediction with arbitrary distribution shifts. arXiv preprint arXiv:2208. 08401, 2022.
Sepp Hochreiter and Jürgen Schmidhuber, Long short-term memory. Neural computation, 9:1735-80, 12 1997.
Rafael Izbicki, Gilson Shimizu, and Rafael Stern. Flexible distribution-fiee conditional predictive bands using density estimators. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp- 3068-3077. PMLR, 26-28 Aug 2020.
Yichen Jía and Jong-Hyeon Jeong. Deep learning for quantile regression under right censoring: DeepQuantreg. Comput. Stat. Data Anal., 165(C), jan 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015.
Roger Koenker and Gilbert Bassett. Regression quantiles. Econometrica, 46(1):33-50, 1978.
Roger Koenker and Kevin Hallock. Quantile regression. Journal of Economic Perspectives, 15(4): 143-156, December 2001.
Jing Lei, Max G Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-fre predictive inference for regression. Journal of the American Statistical Association, 113(523): 1094-1111, 2018.
Anat Levin, Dani Lischinski, and Yair Weiss. Colorization using optimization. In ACM SIG- GRAPH 2004 Papers, SIGGRAPH '04, pp. 689-694, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 978 9781450378239.
Zhenyu Li, Zehui Chen, Xianming Liu, and Junjun Jiang. Depthformer: Exploiting long-range correlation and local information for accurate monocular depth estimation. arXiv preprint 1rXiv:2203.14211 2022a.
Zhenyu Li, Xuyang Wang, Xianming Liu, and Junjun Jiang. Binsformer: Revisiting adaptive bins for monocular depth estimation. arXiv preprint arXiv:2204.00987, 2022b.
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. Journal of Machine Leurning Research, 23(54):1-9, 2022.
Nicolai Meinshausen. Quantile regression forests. J. Mach. Learn, Res., 7:983-999, December 2006.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. Tapio Elomaa, Heikki Mannila, and Hannu Toivonen (eds.), Machine Learning: ECML 2002, pp. 345-356, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. ISBN 978-3-540-36755-0.
Harris Papadopoulos. Alex Gammerman, and Volodya Vovk. Normalized nonconformity measures for regression conformal prediction. In Proceedings of the IASTED International Conference on Artificial Intelligence and Applications (AIA 2008), pp. 64 69, 2008
11

---

Under review as a conference paper at ICLR 2023
Youngsuk Park. Danielle Maddix Robinson, Yuyang (Bernie) Wang, and Jan Gasthaus. Learning quantile function without quantile crossing for distribution-free time series forecasting, ICML 2021 Workshop on Distribution-Fii Uncertainty Quantification, 2021.
Vaishakh Patil, Wouter Van Gansbeke, Dengxin Dai, and Luc Van Gool. Don't forget the past: Recurrent depth estimation from monocular video. IEEE Robotics and Automation Letters, 5(4): 0813-6820) 2020.
Power. Power consumption of tetouan city.
https://archive ics uci sedumml. Accessed: April, 2021.
datasets/Ponee potpee/ee-cooommmmttooooooeeeeee
Prices. French electricity spot prices.
https://githuub.ccommmaaasa meweriieeeeeeeeeeeeeeeee oolllo/mmai httpb/bbbmmai/ddtaarrrtttt ces/
Adapti
Prices_2016 9_extract..... csv. Accessed: April, 2021.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Advances in Neural Information Processing Systems, volume 32, 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage.
In Advances in Neural Information Processing Systems, volume 33, pp. 3581-3591, 2020.
Mattco Sesia and Yaniv Romano. Conformal prediction using conditional histograms. A. Beygelz- imer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Kamile Stankeviciute, Ahmed M Alaa, and Mihaela van der Schaar. Conformal time-series forecasting. Advances in Neural Information Processing Systems, 34, 2021.
Timothy John Sullivan. Introduction uncertainty quantification, volume 63. Springer, 2015,
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
Traffic. Metro interstate traffic volume. https: arrhive..eeeeeeeee iec.ccc... .uc..uiii... edd.mm/dataseets hwtprooonnnessttttt-aaaff------e
Accessed: April, 2021.
Jonas Uhrig, Nick Schneider, Lukas Schneider, Uwe Franke, Thomas Brox, and Andreas Geiger.
Sparsity invariant cnns. In International Conference on 3D Vision (3DV), 2017.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, 2005.
Wind. Wind power in germany. wi wind-power. Accessed: April, 2021.
Chen Xu and Yao Xie. Conformal prediction interval for dynamic time-series. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11559-11569, PMLR, 18-24 2021a.
Chen Xu and Yao Xie. Conformal prediction interval for dynamic time-series. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11559-11569 PMLR, 18-24 Jul 2021b.
Wei Yin, Jianming Zhang, Oliver Wang, Simon Niklaus, Long Mai, Simon Chen, and Chunhua Shen. Learning to recover 3d scene shape from single image. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2021.
Weihao Yuan, Xiaodong Gu, Zuozhuo Dai, Siyu Zhu, and Ping Tan. New crfs: Neural window fully-connected erfs for monocular depth estimation. arXiv preprint wwXiiv2203.01500 2022.
Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In International Conference on Machine Learning, pp. PMLR, 2022.
12

---

Under review as a conference paper at ICLR 2023
Zhenyu Zhang, Stephane Lathuiliere, Elisa Ricci, Nicu Sebe, Yan Yan, and Jian Yang. Online depth learning against forgetting in monocular videos. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 2020.
13

---

Under review as a conference paper at ICLR 2023
Appendices
A THEORETICAL RESULTS
A. PROOF OF THEOREM 1
The proof of Theorem is based on that of Proposition 4.1 (Gibbs & Candes, 2021). While the proof is similar, our work greatly enlarges the scope of the result.
We begin by showing that Og is bounded throughout the entire calibration process. For this purpose, we assume that the loss satisfies that for all y y and C E 2 L(y, C) E [-B, B) where B > 0 is real number.
Lemma 1, Under the assumptions of Theorem for all E N, 0, E [m - ,2B, M + +22B).
M + By (the complementary case is similar). Further assume that for all t' < t: By I M + 2BB. Since 4,r [- B, B), we get that:
Proof. Assume for the sake of contradiction that there exists E N such that
01-1 0, 7(4 -) 2 0, - 2yB > + - 2y = M.
Therefore, 0 M. Since L(y
= < M, we get that 4 < r. As result: 8: - 704 rr) < 8 M +2B.
Which contradiction to our assumption.
Next, we prove Theorem 1.
Proof. By applying Lemma we get that 0g E [m - 72B, M + +2B) for all f E N. Denote m' >2B, and M' = M ,2B. We follow the proof of (Gibbs & Candes, 2021, Proposition 4.1) and expand the recursion defined in (5):
T Σ
[m',M') 3 0T+1 = +
71e - r).
t=1
By rearranging this we get that:
m' 01
T
0r+1 - 01
M' 01
(le r)
T7
T
T7
T7
1=1
Therefore:
T
max {0] - m', M2 01}
Σ
(4 -
T
Ty
t=1
Lastly, the definition of the loss, 4 = L(Y,, (x)))), gives us the risk statement in (1).
Notice that the above proof additionally implies samile bound for the deviation of the empirical risk from the desired level. In particular, the average loss is within C/T factor of where C (M' m²) m/')/7 = (M m BB/y. This bound deterministic, not probabilistic. Thus, even for the most erratic input sequences, the method has average loss very close to the nominal level.
A.2 GENERAL VERSION OF THEOREM
In this section, provide general statement with more abstract notations of Theorem 1. The following notations extend our proposal to a broader class of problems, so that could be applied for larger set of tasks, such multi-label classification. Here, assume that the function generates variables in y' and that the loss function is defined L (),3')) R. Furthermore, we assume that there exist a minimal value y' y' and maximal value y y' for which L(y Y') > r and L(y.V') < r. In the main text, we set y' = -² y = 0 and y = y. We now show that the risk is controlled the desired level even under this general setting.
14

---

Under review as a conference paper at ICLR 2023
Theorem 4. Suppose that f (X + y' is an interval/set constructing function. In addition, suppose that there exist constants m and M such that for all a E X, y E y and M E M, f(x,0,M) = Y for all > M, f(x,(,(XXx)) M, = y for all < m. Further suppose that the loss is Consider the following series of calibrated
bounded and satisfies Y < and Y' intervals: {C)(X:) where (()),) is defined according (4). Then, the calibrated intervals satisfy the risk requirement in (1).
Proof. The proof is similar to the one of Theorem and hence omitted.
A.3 PROOF OF THEOREM 2
The proof of Theorem is similar to the proof of Theorem We assume that all losses {T,) are bounded in the interval [-B, B), as in Section A.1, and begin by showing that all coordinates in A. are upper bounded.
Lemma 2. Under the assumptions of Theorem for all E N and i E
of S M + 22B.
Proof. Assume for the sake of contradiction that there exist t N and {l,..., k} such that
8; > M + ByB. Further assume that for all t' < t: 82- S M ByB. Since 11 r E [- B, B), get that:
0- = - 71h (1) 2 2 B > M + B BB = M.
Therefore, 0-11 M. Since (y, [(x,0, =)) rd for 0- > M, get that 13 r As result:
L = + ( -) ~ - M +BB.
Which contradiction to our assumption.
Next, we prove Theorem
Proof. By applying Lemma 2 get that Ø M + +2B for all t E N and E (1,-..,)). Denote M' = MM + 2BB. We expand the recursion defined in (5):
o 0i
Σ 74 - r²) S M'.
By rearranging this we get that:
Σ4
4
1
r²)
0 T+1 0
M' - 0
T
T
Ty
T
Therefore:
T
M' L
Σ
r +
Thy
t=1
Lastly, by the definition of the loss, Ii = (Ye, (x,)) and by setting D M'
we get the
statement in Theorem
A.4 PROOF OF THBOREMS 3
The proof of Theorem is similar to the proof of Theorem 2. We assume that all losses [L,)in bounded in the interval B, B), as Section A.1, and begin by showing that all coordinates in 0, are lower bounded.
Lemma 3. Under the assumptions of Theorem 3, for all E N and (1,-.,, k), 0 m 72B
15

---

Under review as a conference paper at ICLR 2023
Proof. Assume for the sake of contradiction that there exist t N and {1,..., k) such that L m B, Further assume that for all t' < <:: <t: m 2B Since 1 r [-B, B), get
that:
0--1 714 r²) o 2y m 1- 2
Therefore, li-1 < m. Since L' I (X, = y) > r³ for 0 < m, we get that 12 > r', As
result:
0 = - -r) > Gi > m 22
Which contradiction to our assumption.
Next, prove Theorem 3.
Proof. By applying Lemma 2 and Lemma we get that 0j [m -2B, M + + for all e N and E (1,...,k) k). Denote m' = -22B and M' = M + 22B. We expand the recursion defindd in (5):
[m', MM 0 fi
20, - r'). Σ
t=l
By rearranging this we get that:
m'
0
1
07 0
M' Li
Σ
(4
r²)
Ty
T
Ty
Ty
t=1
Therefore:
T
max 10)
m', M
01}
Σ (1) - -r)
T
Ty
1=1
Lastly, the definition of the loss, 1 = L',Y,, (X.)), gives us the statement Theorem
A.S PROOF OF PROPOSITION
Proof. 1 C(()))) s MC, for any E N. Therefore:
lim T-+00
Σ
MC,
lim T-000
E1e,, 10% & (.(.))) Sa
T
B UNCERTAINTY QUANTIFICATION IN ONLINE IMAGE-TO-IMAGE REGRESSION PROBLEMS
B. GENERAL FORMULATION
Recall the depth estimation problem from Section 1.1, where we construct per-pixel prediction intervals by online processing an incoming video stream. In what follows, we discuss such image-to- image regression problems more generally, providing a scheme to construct and calibrate pixel-valued intervals. Consider a rumning model My(X.) that maps the input image X, to a point prediction of Y,, and wish to control the image misocverage loss Limage miscoverage from (2). We take inspiration from Angelopoulos et al. (2022b) and form the prediction intervals around each pixel (m, n) of the estimated image M,
CAn. (X,) = mm" " (X,, lr, M.) = [M. - X. (M.).
+ ARa TL (X+)). (9)
Above, 1mh (X,) and (X,) represent the uncertainty in the lower and upper directions, respec- tively. That is, large value of 1.t m.. (,,"(X,)) (X₂) indicates that the pixel has a high uncertainty in the upper direction. Similarly. a large value of fi." (Xx) indicates that the pixel has high uncertainty in the lower direction. natural choice for the lower and upper uncertainty measures is a model estimating 17 (X.) = - M (Xt)). We
the absolute residual error pir-pi given by u,
16

---

Under review as a conference paper at ICLR 2023
provide more sophisticated examples for such uncertainty functions in Section B.2. The parameter A = ((t)) E in (9) stretches the calibration parameter 0,, which we update according to (5). Importantly, this procedure is instantiation of Rolling RC and thus attains the correct image coverage, as guaranteed by Theorem 1. This is also validated in the experiment from Section 1.1.
B.2 UNCERTAINTY QUANTIFICATION HEURISTICS
In this section, we present possible choices for the uncertainty heuristics for the interval constructing function given in (9).
B.2.1 BASELINE CONSTANT
The most naive choice for uncertainty heuristic is outputting a constant value for every m, n, X: (X) = um. (X) = In other words, the set constructing function defined as:
(X, 0r M.) [M (X,) >e. MM (X,) ) Ar]-
M.
This approach has two main limitations: (i) the calibrated intervals are symmetric, having the same uncertainty size in both the upper and lower directions, and (ii) all the pixel-valuee intervals have the same length. These limitations lead unnecessarily wide intervals that are less informative. We show how to overcome these limitations with the methods presented hereafter.
B.2.2 MAGNITUDE OF THE RESIDUAL
The residual magnitude heuristic was introduced by Angelopoulos et al. (2022b) as a simple uncer- tainty quantification technique. Here, mmx((X) um= (X) = pm, (1) an estimate for the residual [M***((X) ym,. and it is formulated as an online learning model fitted to minimize the squared residual loss, given by (f(x) - [Mm.n (x) - y1)². An ideal model that minimizes this loss function outputs the exact residual: f(xx) = IM (Ix y/ and thus achieves 100% coverage rate for À 1. In practice, however, the fitted model i may not be accurate and thus we apply Roll Rolling RC, to ensure valid risk control. Observe that. unlike the constant heuristic, here, each pixel is assigned different uncertainty size. Nevertheless, both techniques produce symmetric prediction intervals.
B.2.3 PREVIOUS RESIDUALS
In contrast to the residual's s magnitude heuristic, here, we take advantage of the online setting in which the data set is received as stream, and the past residuals estimate the current We define the positive and negative residuals at time as:
Tτ = M (X,) m,
mm++ max {r. 0}.
ri mmn max {-r m.n ,0..
The uncertainty heuristic in the lower (upper) direction is formulated as the average of the positive (negative) residual in the previous time-steps:
1
mm (Xi)
mmn+
Tt
P
F=t-p
(10)
1-1
4 (X,) =
m,n
''=t-p
In our experiments, set the sliding window's size to p 5.
B.2.4 CORRECTING PIXELS DISPLACEMENTS WITH IMAGE REGISTRATION
The 'previous residuals' method suffers from the following crucial limitation. Objects in the response image may appear in different positions across time, so that an object that lies in pixel (m, n) at frame might appear in different pixel time f e.g., (m + 7, n 11). For example, in
17

---

Under review as a conference paper at ICLR 2023
depth prediction example the camera and the depth sensor move during the online process, objects change their locations and do not remain in fixed pixel between consecutive frames. Therefore. to obtain accurate residual estimates it is better to correct for the displacement of pixels in consecutive frames. For this purpose, we apply an image registration algorithm before evaluating the residuals. In particular, use optical flow (OF) to register the estimated depth images and the ground truth depth maps. Suppose that OF (imı, im2) receives two images as an input and returns the result of the registration of the first image im; to the second one im2. We recursively define optical flow on sequence as:
OF
OF (im1, im
OF (imi, {im, )==2) = OF O (OF im2), {ime)
Then, we register the previous estimated depth images and ground truth depth maps
M (Xt-i) = OF OF (M(x, (M(X) (M(x)++)))==)).
- OF (Y (Y-0))=1):
In plain words, register each image using the next ones in the sequence. We define the registered residuals as:
Ft M - Y reg
F/ max (1( m. 0}, Fmn.n max -- 0}.
Then, we compute the average residual, as in (10):
1
Cm (X,,
Ft m
p P'=t-p
" (X,) 1
Σ mmn
p
Pーtーp
This displacement consideration indeed improves the performance, as indicated by the experiments in Section D.2.
C EXPERIMENTAL SETUP
C.I SINGLE-OUTPUN TASKS
C.I.1 THE QUANTILE REGRESSION MODEL'S ARCHITECTURE
The neural network architecture is composed of four parts: an MLP, an LSTM, and another two MLPs. To estimate the uncertainty Y, Xx, we first map the previous k samples {(X,,,, Y,- 1 through the first MLP, denoted as fi,
W fi Vt-
where we set l to 3 in our experiments. The outputs are then forwarded through the LSTM network, denoted as fz:
(w = fa fa((wt
Note that since f2 an LSTT model, w²_; used to compute w The output w²_1 of the LSTM model, being aggregation of the previous & samples, is fed, together with (X,, 6, T), to the second MLP model, denoted as fa:
" = Sa(w Xt).
Lastly, we pass wi through the third MI.. denoted by f4, with one hidden layer that contains 32 neurons:
q. (X,) (w)
The networks contain dropout layers with parameter equal to 0.1. The model's optimizer is Adam (Kingma & Ba, 2015) and the batch size is 512, i.e., the model is fitted on the most recent 512 samples in each time step. Before forwarding the input to the model, the feature vectors and response variables were normalized to have unit variance and zero mean using the first 8000 samples of the data stream.
18

---

Under review as a conference paper at ICLR 2023
C.1.2 TRAINING THE QUANTILE REGRESSION MODEL
Estimating the conditional quantile function can be done, for example, by minimizing the pinball loss in lieu of the standard mean squared error loss used in classic regression; see (Izbicki et al., 2020; Jia & Jeong, 2022: Koenker & Bassett, 1978; Koenker & Hallock, 2001; Meinshausen, 2006).
Specifically, in our experiments with time-series data we minimize the objective function:
min M.
Pa/2
a/2)) + +1 (1- Mc(Xr, a/2)))
where
aay 1) Pa Pa(V. (1- y) otherwise.
リー
the pinball loss. Since the data points arrive sequentially, we formulate M, as an LSTM model and minimize the above cost function in online fashion follows. Given a la- beled test point (Xe, Yt). we (i) compute the pinball loss both for the lower and upper quantiles, i... (Y,, (M... o22)) and P1-a/2(Y,, M,,,,
a/2)), respectively; and (ii) update the parameters of the LSTM model Mr by applying a few gradient steps with ADAM optimizer. More details on the network architecture are given Appendix C.I.1.
C.1.3 HYPER-PARAMETERS TUNING
For both real and synthetic data sets, we examined all combinations of the raw model's 's hyperparame- ters (with no calibration applied) on one initialization of the model, and chose the setting in which the model attained the smallest pinball loss, evaluated on the validation set, indexed by 6001 8000. The combinations we tested are presented in Table 1. Some of the configurations required more than 1 11GB of memory train the model, we did not consider them in experiments. The chosen configuration was later used for choosing the calibration's 's learning rate y, as explained next. We note that using the validation set to tune the hyperparameters and the choice of the stretching function is a heuristic. Yet, we found this rule of thumb to work well empirically, as visualized in Figure 7 in Appendix D.1.1. Of course, there are situations where this approach would not be most effective since the data is not i.i.d., but we believe it is a sensible suggestion. Another advantage of tuning the hyperparameters this way is that it facilitates the comparison between the different methods since they all follow the same automatic tuning approach.
The updating rates we tested are: 7 E {0.025, 0.03, 0.05, 0.09, 0.1, 0.15, 0.35). We chose y that attained the smallest pinball loss, evaluated on points 5001 - 8000.
In Appendix C.4 we explain how we chose the hyper-parameters for the stretching functions.
C.2 THE DEPTH PREDICTION SETUP
C.2.1 DATA SET AND AUGMENTATIONS
We used the KITTI data set which contains pairs of colored (RGB) image (Geiger et al., 2013) and a latent ground truth depth map (Uhrig et al., 2017). We filled the missing depth values with the colorization algorithm developed by Levin et al. (2004). Then, we scaled the depth values to the range [0,10], We augmented the images according to the following protocol. Images and depths used for training the model were resized using one of the following ratios [0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3. 1.4, 1.5], chosen with equal probability, cropped randomly and re-scaled to 448 x 448, and then flipped horizontally with a 50% chance. Images and depths used for testing and updating the calibration model were resized with a ratio of 0.5 and re-scaled to 448 x 448. In both cases, we augmented the colors of the RGB image and blurred it, as described in (Yin et al., 2021). Notice that the augmentations are deterministic during inference and random during training. Therefore, the augmentations are chosen randomly in each trial. The main purpose of these augmentations is to improve the model's 's training.
C.2.2 THE DEPTH PREDICTION MODEL.
The base prediction model M we used is LeReS (Yin et al., 2021) with ResNeXt101 backbone initialized with the pre-trained network from https: oudstoo. aaporraarnnnn aarnet. edu. attp.uuupluu
19

---

Under review as a conference paper at ICLR 2023
8/LTIUF4vZVHHCAALL This pre-trained network was not fitted the KITTI data set used in our experiments. We fitted the model offline on the first 6000 samples for 60 epochs, to obtain a reasonable predictive system. Then, passing time step 6001 we start training the model in an online fashion while applying the calibration procedure. Lastly, we measure the performance of the deployed calibration method on data points corresponding to time steps 8001 to 10000.
C.2.3 TRAINING THE UNCERTAINTY QUANTIHICATION MODELS
For each uncertainty quantification model presented in Section B.2, we used pre-trained LeReS (Yin et al., 2021) network as the base network architecture and initialized the last two components of the network with random weights. We simultaneously trained the uncertainty quantification model and the LeReS depth model on the first 6000 samples for 60 epochs, and in an online fashion at timestamps 6001 to 10000, mentioned in Section C.2.2.
C.2.4 DEPTH EXAMPLE SETUP
In this section, we describe the setup we used for the depth experiment presented in Section 1.1 in the main text. As explained in Section C.2.2, we used LeReS (Yin et al., 2021) as the base depth prediction model. The model's predictions were calibrated by our Ro 1 ing RC, with the design choice for f given in Section 9. The uncertainty heuristics we used in this experiment are the previous residuals with registration, as described in Section B.2.4, with a sliding window of size p = 5. We used scikit- image's implementation of optical flow. We set the parameter "num iter" to and the "num haan__arp" to 1, to reduce the computational complexity. The figures are taken from one trial of the experiment, for which the random seed value was set to The only hyper- papee--arrmeter we tuned in this experiment is the calibration's 's learning rate which we tuned in the following way. We applied Rol 1 ing RC with the following learning rates: y E {0.001, 0.005, 0.01, 0.05, 0.1, 0.2, 0.5, 1,2, 10} and chose the y that achieved the narrowest intervals among those with coverage greater than 79.9% on the validation set. The validation samples are those that correspond to timestamps 7001 to 8000. The value that was finally chosen is 7 0.2.
C.2.5 MULTIPLE RISKS CONTROLLING SETUP
In this section, we describe the setup we used for the multiple risks controlling experiment presented in Section 4.2. We followed the experimental protocol described in Section C.2.4 except for the tuning of y. When Rolling RC is applied to control multiple risks, the learning rate y is vector, so examine all possible choices of 2², 2² E {0.00001, 0.0001, 0.001, 0.005, 0.01, 0.1, 0.5, 2}. We chose the vector y that achieved the narrowest intervals among those with coverage greater than 79.9% and center failure rate lower than 11%, evaluated on the validation samples, corresponding to timestamps 7001 8000. In this experiment, we set X in (9) to be the maximal value in the vector 0. That is, we used the 'max aggregation' described in Section D.3.
C.2.6 IMPLEMENTATIO DETAILS
In this section, we describe the technical details of implementing the depth prediction model and the uncertainty quantification heuristics. Popular depth prediction models estimate the depth up to an unknown scale and shift (Li et al., 2022a;b; Yuan al., 2022). That is, an ideal model M satisfies that for every X, E X there exist px, σx E R such that:
o o.M((X)) + μ4 = Y.
We correct the model's outputs to actual depth estimates in the following way. First, we assume that we are given the ground truth depth of a small set of pixels. Then, we use this information to estimate the scale and shift: when X, is revealed, we uniformly choose 200 pixels of and assume that their depth is given along with X₁. Next, we obtain the learning model's 's output M(X,) and apply least squares polynomial fitting to compute the estimated scale ü. and shift o, Finally, we produce the following depth estimate:
= o + fr.
(11)
Throughout this paper, consider the quantity in (11) the output of the depth model M.
We utilize the sparse ground truth depth map to correct the estimates of the uncertainty heuristics as well. Recall that the residual heuristic from Section B.2.2 produces an estimate f(X,) for the residual
20

---

Under review as a conference paper at ICLR 2023
[M**."(X)) Yrl, where (X2) is the scaled model's prediction. We compute the scale and shift for the residual's 's prediction via polynomial fitting, and output the scaled residual, as in (11). Similarly, correct the previous residuals heuristic defined in Section B.2.3 by re-scaling the positive and negative residuals.
Another important technical detail is dealing with invalid pixels. Invalid pixels pixels with depth that is too small (below 10-$), or pixels that are padded to the image. We do not consider these pixels for updating the calibration scheme or for evaluating the methods' performance. For instance, the image coverage rate is practically the coverage rate over all valid pixels in a given image.
Lastly, throughout the depth prediction experiments we used the following formulation of the exponential stretching function for Rolling RC:
1,
0.1,
0.1 0.1,
+1,
0.1.
Notice that this stretching function is the identity function around 0, and therefore it updates (p({)) gently when the calibration is mild (9, is close to 0), and faster (exponentially) the calibration is more aggressive (0g is away from zero).
C.3
THE CALIBRATION'S HYPERPARAMETERS
C.3.1 THE BOUNDS m, M
the lower and upper bounds-m and M are predefined constants serve as safeguards against extreme situations where the data change adversarially over time. In such extreme cases, these bounds allow controlling the coverage: once exceeds the upper bound we return the infinite interval (the full label space) and once it exceeds the lower bound label space, we can guarantee to control the risk at any user-specified level, as the full label space expect
return the empty set. By outputting the full
is assumed to attain loss lower than the nominal level. In practice, however, we do reasonable predictive model to reach the safeguard induced by m and M. In fact, in our experiments, we set m 9999,, and M 9999 to be extremely large values relative to the scale of Y. and the coverage we obtained is exactly 90%.
For classification problems, we can set the bounds to be (0. 1), similarly to ACI. For regression problems, it depends on the interval constructing function f. If the intervals are constructed in the quantile scale, according to Section of the main text, we can set the bounds to be (0, 1) since is bounded in this range, as in ACI. If the intervals are constructed in the Y scale, according to Section 3.2 of the main text, we can set them to be 100 times the difference between the lowest and highest values of the response variables in the training data.
C.3.2 THE INITIAL VALUE OF
The recommended way to set the initial value of A depends on the design of the interval constructing function f: for example, for the interval constructing function Y scale, presented Section 3.2 in the main text, we set the initial 0 to zero as this is the right choice for model that correctly estimates the conditional quantiles. If the model is inaccurate, will be updated over time, in a way that guarantees that the desired long-range coverage will be achieved.
C.3.3 THE LEARNING RATE
Y
In this section, we analyze the effect of the learning rate y on the performance of the calibration scheme. Figure 6 presents the results of our Roll 1 inn RC with linear stretching function applied with different step-size on the synthetic data described in Section C.6.1 of the main manuscript. We choose the linear stretching instead of the exponential one to better isolate the effect of on the performance. Following that figure, observe that by increasing ? we increase the adaptivity of the method to changes in the distribution of the data, as indicated by the MSL L. Recall that (i) the lower the MSL the smaller the average streak of miscoverage events; and (ii) the MSL for the ideal model is 1.11. On the other hand, the improvement in MSL comes at the cost of increasing the intervals' lengths: observe how the largest y results in too conservative intervals, their MSL is equal to I.
21

---

Under review as a conference paper at ICLR 2023
To set proper value for y in regression problems, suggest evaluating the pinball loss of the calibrated intervals, using a validation set. With this approach, one can choose the value of y that yields the smallest loss. We note that our method is guaranteed attain valid coverage for any choice of 7, so the trade-off here is between the intervals' lengths and faster adaptivity to distributional shifts.
90.2
150
90.0
125
30.8
length
89.6
89.4
75
89.2
50
89.0
68.8
00001
y00.0
y-b.1
y-0.15
y-0.2
0-0.3
y=0001
y-0.025
v-0.05
y-0.1
y=0.15
y=02 y-0.35
15
0
y= y=0.05
y=0.2
y=
Figure 6: Rolling RC with linear stretching applied to control the 0-1 loss at level r = 10% with different learning rates on the synthetic described in Section C.6.1.
C.4 THE PARRA-PRRR FOR THE STRETCHING FUNCTIONS
The 'score adaptive" function has three syper-parametter and the 'error adaptive" has four. Choos- ing them wisely greatly affects the performance the method. To do so, we used SMAC3 (Lindauer et al., 2022), which is a pyyer-parameee of grcore E [0.01, 0.4], gloss E (0.1 0.2] that minimizes the pinball loss (or be exact, the average of the pinball losses of the 0.95 and 0.05 quantiles), with runcount-limit of 40. We chose 3low ghigh to be Ameany + Amean (respectively) where:
tuning library written in python. We let it find a combination
Σ Irc-Y. EEI..
mean
Ival
where Tual are indices 5001 8000. The rationale behind this choice is that we want the clipping to be on the scale of an average change the intervals' lengths.
C.5 MACHINE'S S SPEC
The resources used for the experiments are:
CPU: Intel(R) Xeon(R) E5-2650 v4.
GPU: Nvidia titanx, 1080ti, 2080ti.
OS: Ubuntu 18.04.
C.6 DATA SETS DETAILS
C.6.1 SYNTHETIC DATA SET
In this section, we define a synthetic data set that we use our ablation study. First, we define group indication vector, denoted gr:
g 1 m1
2
3ma
22

---

Under review as a conference paper at ICLR 2023
Table 1: Hyperparameters tested for each data
Parameter
Options
f1 LSTM input layers
[32], [32, 64), [32, 64, 128]
f2 -LSTM layers
[64], [128]
f3 -LSTM output layers
[32], [64, 32]
learning rate
10-4, 10
where w" is a vector of the number w repeated n times, is a concatenation of two vectors, m, (500, 102) and ((,, o²) is the normal distribution with mean μi and variance a². In words, each group lasts for approximately 500 time steps, and the vector is concatenation of the group's indexes. The generation of the feature vectors and the response variable is done in the following way:
8 Uniform (0, 1)".
3
8
1
(20 10), = mod 2, otherwise,
(1,
X, Uniform(O. 1)
6t ~ (O, 1),
Y, Y2-1 +
Xel 22in Et),
where Uniform(a, b) is uniform distribution on the interval (a, b).
C.6.2 REAL DATA SETS
In addition the features given in the raw data set, added for each sample the day, month, year, hours, minutes, and the day of the week. Table 2 presents the number of samples in each data set, the number of samples we used in the quantile regression experiments 4.2. and the dimension of the feature vector.
Table 2: Information about the real data sets.
Data Set
Total Number of Samples
Number Used Samples
Feature Dimension
power (Power)
52416
20000
11
energy (Energy)
19735
20000
33
traffic (Traflic)
48204
wind (Wind)
385565
20000
prices (Prices)
34895
20000
61
D ADDITIONAL EXPERIMENTS
D.1 SINGLE RESPONSE QUANTILE REGRESSION
D.1.1 ABLATION STUDY ON THE STRETCHING FUNCTION
In this section, we evaluate Rolling RC in the regression setting for different stretching functions. We follow the procedure described in Section 3.2 and use the following stretching functions:
None.
(<x)
23

---

Under review as a conference paper at ICLR 2023
Exponential.
c 1, -0-=
x > 0, x S
(0())
+
Score adaptive. The following stretching function makes a larger update to O, the farther the test Y, from the interval's boundaries. This is in contrast with the exponential function described above, which does not take into account the quality of the constructed interval. More formally, denote the CQR non-conformity score (Romano al., 2019) by
(M. a/2) - Y,, Y,
a/2)),
which measures the signed distance of Y, from the its closest boundary. Next, define
P 8 X At where X X clip(A ggsore -1-1. 3 ghigh)
where groure glow and ghigh are hyperparameters. Similarly to the 'error adaptive' stretching function presented in Section 3.2.1, the clipping function is used restrain the effect of an outlier Y2 that is far from the boundaries.
Error adaptive. By adding awareness of previous points' loss the 'score adaptive' stretching, we forge a stretching function that is aware of both the error margin and the constructed intervals' loss:
(0) 0 A.mor where xemrr clip (
greone 8t-1 exp {gloss |fe-1 r33,, ghigh).
Figure 7 displays the performance of Ro Rolling ling RC aiming control coverage rate at level - 90% with the stretching functions described above, and Figure 8 presents the results of Ro in RC applied control the MC risk at level a/(1 a) = 1/9. Following these figures, we see that Rolling RC with each stretching function performs well on most of the metrics on most of the data sets.
Although the 'no stretching' and the 'exponential stretching' functions converge faster to the desired risk level, it is clear from the results that the 'score adaptive' and the 'error adaptive' stretching functions construct narrower intervals. Moreover, the 'error adaptive' approach is superior in several terms:
It constructs the shortest intervals.
It achieves MST that is closer to the ideal level 1.111... which means that consecutive miscoverage events are less likely to occur (see Appendix E.1).
It achieves MC that closer to the desired level 0.111... when aiming to control the coverage rate, and its coverage rate is closer to 90% when aiming to control the MC risk level, which is a desired outcome (see Appendix E.2).
Rolling RC with "error adaptive' stretching performs similarly to the competitive stretch- ings in terms of ACoverage.
D.1.2 CONSTRUCTING UNCERTAINTY SETS WITH A CALIBRATION SET
In this section, we analyze an instantiation of ACI (Gibbs & Candes, 2021), which refer as falibration with cal 1 that constructs uncertainty sets with a controlled miscoverage rate using a calibration set. is more out-of-the-box because it allows the user to take any conformal score function from the conformal prediction literature get confidence set function f. Many conformal scores have been developed and extensively studied, so this approach directly inherits all of the progress made this topic. calibrat ion with cal uses calibration points, but does not hold out large block. Rather, previous points are simultancously used both for calibration and model fitting.
Turning to the details, denote by ((,, Y2 E RR a non- non-conformity score function that takes input the model's prediction (X,) at time and the corresponding label Y,, and returns a measure for the model's goodness-of-fit or prediction error. Here, the convention is that smaller scores imply better fit. For instance, adopting the same notations from (6), the quantile regression
24

---

Under review as a conference paper at ICLR 2023
Miscoverage Counter
No streching
90.2
Exponential streching
Coverage
0.13
Score adaptive streching
Error adaptive streching
0.12
90.0
0.11
energy
traffic
prices
power
wind
energy
traffic
prices Dataset
power
wind
Dataset
Average Length (scaled)
1.1
1.0
ACoverage
1.0
0.5
0.9
energy
traffic
prices Dataset
power
wind
energy traffic
prices Dataset
power wind
1.3
1.2
energy traffic prices power
wind
Dataset
Figure 7: Performance of Rollls folling ling RC on real data sets, aiming to control the coverage rate at level 1 a 90%. The length of the prediction intervals is scaled per data by the average length of the constructed intervals, Results are evaluated on 20 random initializations of the predictive model. The ACoverage metric is scaled between 100.
score presented in (Romano et al., 2019) are given by S(M+(X.)) Y,) = max mX.. Y, M, a//)). Next, define the prediction set constructing function in (4) as: f(X,, Bc, M,) e ) ((M, v) Q1+o,
(12)
where Scal (S(M Yv) 11= n. n....., non-conformity scores. The function Q1+9, (Seai) returns the (1 + 0.)-th empirical quantile of the Here, -1 <
is set containing the most
scores in Seal, being the [[1 + (n)(n 1)] largest element in that calibration parameter we tune recursively. as in (5). The reason for having the negative sign, is to form larger prediction sets as increases. In plain words, f (12) returns all the candidate target values y for the test label, whose score S(M, y) is smaller than (1 + 0₂) x 100% of the scores Sea. which are evaluated on truly labeled historical data S(Mr (X.), Yr.. ). such, the size of the set in (12) gets smaller (larger) as 1 + 0, gets smaller (larger).
is the
For reference, ca iibiaiitooo on with ca 1 procedure is summarized in Algorithm The reason for this method's name is to emphasize that now calibration scores to formulate the prediction set function f. In fact, the coverage guarantee of calibration with cal follows directly from Theorem for [X,, Mc) defined in (12).
We run Rolling RC with either 'error adaptive' stretching and without stretching, as described in Section 3.2. and calibration with cal, presented in Algorithm 2 on the real data sets detailed in Appendix C.6.2. Figure summarizes the results, showing that methods attain the desired coverage level; this is guaranteed by Theorem 1. This figure also shows that Rol 1 nn RC
25

---

Under review as a conference paper at ICLR 2023
Miscoverage Counter
92
0.1200
No streching
Coverage
0.1175
Exponential streching
Score adaptive streching
91
0.1150
Error adaptive streching
0.1125
90
0.1100
energy traffic
prices Dataset
power
wind
energy
traffic
prices Dataset
power
wind
Average Length (scaled)
2.0
1.2
&Coverage
1.5
1.0
1.0
0.5
0.8
energy
traffic
prices Dataset
power
wind
energy traffic
prices Dataset
power
wind
1.4
1.3
MSL
1.2
1.1
energy traffic prices power
wind
Dataset
Figure 8: Performance of Rolling RC real data sets, where aim control the MC risk at level a-((1 - a) 1/9. The length the prediction intervals is scaled per data set by the average length of the constructed intervals. Results evaluated 20 random initializations of the predictive model. The Acoverage metric is sealed between 0 to 100.
with 'error adaptive' stretching constructs the narrowest intervals while attaining the best conditional coverage metrics. Furthermore, one can that even without stretching, Rolling RC performs better than ca iibbrationn with cal, as indicated by the intervals' lengths and the conditional coverage metrics.
D.2 UNCERTAINTY QUANTIFICATION FOR ONLINE DEPTH ESTIMATION
In this section we analyze the performance of the uncertainty quantification heuristics described in Section 3. We follow the experimental protocol explained in Section C.2.4, and display the results in Figure 10. This figure shows that all heuristics attain the nominal image coverage level, as guaranteed by Theorem 1. Furthermore, the figure suggests that estimating the current residual with the five most recent ones outperforms the baseline constant technique, while estimating the residual with neural network, does not, indicated by the average length and center coverage metrics. We propose two possible explanations for this phenomenon. First, since the residual model's architecture huge, it may require further offline fitting, 60 epochs on 6000 samples, while the base depth prediction model, LeReS Yin et al. (2021), was trained over 300k samples. Second, since one can extract depth estimate from residual estimate, the problem of estimating the residual r is equivalent to estimating the depth:
larger data set. For comparison,
trained it for
= M(X.).
26

---

Under review as a conference paper at ICLR 2023
Algorithm 2 calibration with cal
Input:
Data ((X,, Y.))=1 C x V given as stream, miscoverage level a E (0, 1), a score function S. a calibration set size step size > 0, and an online learning model M.
Process:
Initialize ag = a and a of the previous conformity scores: Seat 0.
2: fort = ..... I' do
3:
Construct a prediction set for the new point Xy:
CNC (X,) = tu E V S(M,(X)),)) S &Qi-a,
4: Obtain Y,
5:
Compute the current conformity score: 8, ((),
6: Add the current conformity score to the set: Scal = Seal U {
7:
Remove the oldest calibration point from the set: Scal Scal {
8: Compute err, 1(Y; & Cy (X,)).
9:
Update 0t++1 Oe + ( emr.)-
Fit the model Mr on (X,, Yj) and obtain the updated model M
11: end for
Output:
Uncertainty sets CTe(()) for each time step t E {1,
Therefore, the fact that estimating a depth map is extremely difficult, as explained in Section C.2.6, turns the task of estimating the residual be difficult as well. As a consequence, the residual estimates may be inaccurate.
D.3 MULTIPLE RISKS CONTROL: ANALYZING THE AGGREGATION FUNCTIONS
In this section we examine two options for aggregating the vector L, into scalar through Ae:
Mean. Ameum 1 (v)))) + (())). Taking the average of the entries compromises between the different risks and results in intervals that are not too conservative and not too liberal.
Max. Xmax max (+((),, (Q))). Since the maximal coordinate corresponds the most conser- vative loss, the constructed intervals may be too conservative.
The third possible aggregation the minimum function A min(0,) that consistently follows the minimal entry in i, Since the minimal coordinate in 6, corresponds to the most liberal loss, this approach is likely to result intervals that are too liberal, as ignores the conservative losses. Therefore, we do not examine this aggregation in our experiments.
We follow the experimental setup described in Section 4.2 and display in Figure 11 the performance of the mean and max aggregation for Q. This figure shows that the two methods perform similarly, and using mean aggregation leads slightly narrower intervals compared the mean aggregation approach.
E TIME-SERIEE CONDITIONAL COVERAGE METRICS
E AVERAGE MISCOVERAGE STREAK LENGTH
Following Section 4.1.1, recall that the miscoverage streak length of series of intervals (Čx(X.)) defined as:
Z Σ minfi: Yot E Ce+e(Xeti) ort Ti
1
MSL
where I is set containing the starting times of all miscoverage streaks:
= {1 { Ti):Ti): (1 (1=11 To or Y E Co-1((x-1)) and Y, & C.(X))
27

---

Under review as a conference paper at ICLR 2023
Miscoverage Counter
With cal
0.20
Coverage
90.2
Without no stretching
Error adaptive streching
90.0
0.15
89.8
0.10
energy
traffic
prices Dataset
power
wind
energy
traffic
prices
power
wind
Dataset
Average Length (scaled)
1.1
1.0
A Coverage
1.0
0.5
0.9
energy
traffic
prices Dataset
power
wind
energy traffic
prices Dataset
power
wind
2.00
1.75
MSL
1.50
1.25
1.00
energy traffic
prices Dataset
power
wind
Figure 9: Performance of calibration with cal (Algorithm 2) (blue), Rolling RC with- out stretching (orange), and Rolling RC with 'error adaptive" stretching (green). Results are evaluated on 20 random initializations of the predictive model. The ACoverage metric is scaled between 100.
Above, (To, Ti] is the set all integers between To and Ti.
To clarify this definition of the MSL, we now analyze the MSL in two concrete examples. Denote by "I" a coverage event by "0" miscoverage event, and consider a sequence 15 observations. method that results in the following coverage sequence:
1, 1, 0, 0,0, 1, 1,1,
has an MSL = (2 + 1)/2 1.5, and coverage 12/15 = 80%. By contrast, method that results in the following sequence
1,1,1,1, 1,,1,,,,,
has the same average coverage 80% but much larger MSL = 3/1 = 3. This emphasizes the role of MSL: while the two methods cover the response in 12 out of 15 events, the second is inferior as it has, on average, longer streaks of miscoverage events.
We now compute the MSL of intervals constructed by the true conditional quantiles (C(X))) By construction, these intervals satisfy:
PYY, E C(X)) X, xx)
Therefore, Z, minfi: Me+s E O(X++) or Tj a geometric random variable with success probability The average miscoverage streak length of the true quantiles is the mean of Z.
28

---

Under review as a conference paper at ICLR 2023
40
Image Coverage
Average Length
35
80.00
79.98
25
20
79.96
const.
resid.
prev. resid. flow prev. resid.
const
resid.
prev. resid. flow prev. resid.
Uncertainty Quentification Heuristic
Uncertainty Quantification Heuristic
80
Center Average Length
24
Center Coverage
75
22
20
70
18
65
prev. prev.
resid. flow
Uncortainty Quantification Houristic
Uncertainty Quantification Heuristic
40
Center
20
const.
resid. prev. resid. flow prev. resid.
Uncertainty Quantification Heuristic
Figure 10: Performance of Rolling RC applied to control the image coverage rate with the following uncertainty quantification heuristics that are described in Section B.2: 'constant value" (blue), 'magnitude of the residual' (orange), 'previous residuals' (green) and 'previous residuals with optical flow registration' (red). All methods use the exponential stretching function introduced in Section 3.2.1.
Image Coverage
Awerage aage Length
30
Calibration method
20
stretching
25
85
max aggregation
15
mean aggregetion
Center
10
single risk
multiple
single
multipla ricks
single risk
multiple risks
Rolling
Rolling AC
Rolling RC
Figure 11: Performance of Rolling RC applied to control both 'image miscoverage' and 'center
failure' risks. All methods use the exponential stretching function introduced Section 3.2.1.
which is:
MSL
1.111.
0=0.1
Therefore, having MSL 1 not necessarily equivalent to optimal conditional coverage, as indicates for undesired anti-correlation hetween two consecutive time steps: after miscoverage event follows coverage event with probability one. Consequently, we would desire have MSL I-a' which is the MSL attained by the conditional quantiles.
E.2 THE MISCOVERAGE COUNTER
How should one choose the risk level for the MC risk? If we aim at 1 a 90% coverage, argue that the right choice is = a/(1 a) = 1/9. To see this, suppose we have an ideal model conditional on f. In this case, the coverage events are i.i.d.
that attains perfect coverage rate realizations of Bernoulli experiments and so MC acts as a geometric random variable that counts the number of failures until reaching success, where the success probability is 1 a. Hence, define the MC risk level r to be the expected value of such geometric random variable, which is a/(1 - a). By Proposition we know that we control MC at level 1/9, the coverage will be
29

---

Under review as a conference paper at ICLR 2023
at least - 88.8%% where an ideal model will reach exact 90% coverage. This stands in striking contrast with a method that only controls the coverage metric, as the constructed prediction intervals may result in large MC risk.
Note that Theorem assumes that the loss is bounded, while MC is not bounded. To guarantee that the following loss instead:
Bolling RC will converge the desired risk level of MC, MC' = min {MC, B) for some large B E N. In the experiments, however, we used the regular MC as we observed that its value does not get too high in practice.
E.3 ACOVERAGE
The time-series data sets we use in the experiments in Section 4.1.2 include the day of the week as an element the feature vector. Therefore, we assess the violation of day-stratified coverage (Feldman et al., 2021; Zaffran et al., 2022), as proxy for conditional coverage. That is, we measure the average deviation of the coverage on each day of the week from the nominal coverage level. Formally, given their ACoverage defined as:
a series of intervals
ACoverage
Σ
1
Σ \x,E),(x)) IED:
D.
(E.1.2.....7
where D; is a set of samples that belong to the i-th day of the week. Since lower value of this metric indicates for a better conditional coverage, we desire to have a minimal ACoverage.
F CALIBRATING ON THE QUANTILE SCALE IN REGRESSION TASKS
As an alternative for (6), where the calibration coefficient ((0,) is added each of the interval endpoints, one can modify the interval's length by tuning the raw miscoverage level T = ((.)) requested from the model:
([X,,0,,M,, = (M,, T/2), Mi 1 Tr/2)].
This formulation is inspired by the work of (Chernozhukov et al., 2021) )) that suggested tuning the nominal miscoverage level т. based on calibration set. contrast to (6), where we estimate only the lower a 2 and upper 1 - a/2 conditional quantiles, here, we need to estimate all the quantiles simultaneously. To accomplish this, one can apply the methods proposed in (Chung et al., 2021; Park et al., 2021; Sesia & Romano, 2021). Turning to the choice of the stretching function yo: the straightforward option is to set ((0) -T, where 0, is bounded in the range: -1 S 0, S 0. The reason for having the negative sign in yp, is to form larger prediction sets (resulted by smaller values of r) as increases.
G CONSTRUCTING PREDICTION SETS FOR CLASSIFICATION TASKS
Consider multi-class classification problem, where the target variable is discrete and unordered y E y = {1, ..., K}. Suppose we are handed a classifier that estimates the conditional probability of Py,px. (Y,
X, 2)) for each class y, i.e., MM(X,, v) [0, and Eyey Mc(X., With this in place, we follow (Papadopoulos et al., 2002) and define the prediction set constructing function as:
(1, where one can choose sp(2) xx for instance. While this procedure is guaranteed to attain the pre-specified risk level r, according to Theorem 1, the function f in (13) may have unbalanced coverage across different sub- popplatiiolonsss in the data (Angelopoulos et al., 2021b: Cauchois et al., 2021). To overcome this, we recommend using the function f presented next, which is capable of constructing prediction sets that better adapt to the underlying uncertainty. The idea, inspired by the work of (Angelopoulos et al., 202 lb; Romano et al., 2020), is to initialize an empty prediction set and add class labels to it, ordered by scores produced by the model. We keep adding class labels until the total score exceeds 1 Formally, the confidence set function is defined as:
{y M. 2 p(0)),,
(13)
f(Xi,0,, {II,..., Jk}, where k = inf k:
Xe:>(MM (Mc,Xx, (,),,,,))) T1) pp(1)
30

---

Under review as a conference paper at ICLR 2023
and π is the permutation of (1,2....K) sorted by the scores {M, y) t E )) from the highest to lowest. As for the stretching function yp, we recommend using ((x)) = 2.
31


Reviews:
[{"review_id": "p8dnDphYMh_", "reviewer": "Reviewer_Kmvq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "The authors propose an online conformal risk control method based on ACI, allowing to control multiple risks irrespective of underlying distribution shifts.", "summary_of_the_review": "I am not fully convinced that this paper is ready to be published. This is mainly due to a combination of two factors: the story of online (multiple) risk control being diluted by “other things” (stretching functions, the depth estimation application which seems to be key, experiments where I could as well use standard ACI, etc.); and a bit of ambiguity in terms of what the contributions over ACI are (proofs seem to be applicable directly, not a lot of discussion of the theorems etc.). I feel the authors have to decide what kind of paper they want to write and present this in a coherent way, highlighting the corresponding contributions.", "strength_and_weaknesses": "Strengths:\n- Clear and concise abstract and introduction and early problem statement with initial practical example.\n- Simple method for controlling multiple risks irrespective of distribution shift.\n- Experiments to compare to ACI and practical experiments for image depth prediction.\n\nWeaknesses:\n- No separate discussion of related work even though there si quite some work on risk control on conformal prediction for time-series going on.\n- In terms of writing, there are also too many references to the appendix in my opinion. This distracts from the main paper. If something is important enough to be discussed in the main paper, please do include at least the gist of it. But, e.g., referring to finite sample bounds and then not providing the exact bounds in the main paper is hindering the reading flow. Many other examples can be found (properly setting \\gamma, handling multi-dimensional Y, additional stretching function). I am aware that not everything fits the main paper, but as reader it is difficult to actually decide what is important to read or not.\n- Method can be seen as an incremental generalization of ACI, this also concerns the theoretical contributions. Looking at the theorems and their proofs, these seem to follow the ACI paper to most extent – at least I could not spot any difficulties where proofs needed to change or adapt.\n- The additional “stretching” functions seem a bit misplaced in the paper. I’d rather have the proofs or more intuition about \\gamma, handling multi-dimensional Y, etc. in the main paper). These stretching functions seem more like a “trick” or so – maybe similar to changing conformity scores in conformal prediction.\n- Also, regarding the adaptive stretching function, the implications of using examples for this on the guarantee is unclear. This essentially changes the \\theta based on the previous examples. But as \\theta is already calibrated based on example t – 1, shouldn’t this affect the proof/guarantee somehow?\n- In controlling more risks, can I use a single calibration parameter instead of one for each risk? The experiments note that the maximum is used, but in practice I might have parameters independent of the number of risks.\n- Proposition 1 seems rather straight-forward, I do not see the need to explicitly highlight this – also considering the proof in the appendix.\n- Section A.2 seems just not necessary. I mean the proof is omitted anyway. So why not just have only the more general statement in the main paper with the same/full proof, or just omit it?\n- In the experiments, a clear ACI (or even split conformal risk baseline) is missing. As Figure 3 is about coverage, ACI is applicable and should, in my opinion, reduce to ACI – or am I wrong? To be honest, I am not interested in ablating the stretching functions (this is not what the paper is about). So, having proper baselines, maybe showing the time series or having a trivial split baseline seems more interesting.\n- Regarding the experiment sin 4.1.3, I am not sure what the takeaway is. I mean for me it seems that this is an empirical strategy to get control over the miscoverage counter. But the method itself cannot provide a guarantee on this, right? Because the guarantee is on losses defined per example.\n- The experiments in 4.2 are clearly the main focus of this paper, also given the ages of appendix on this problem and the introductory example. Given that the method is very similar to ACI, I could imagine this paper to put more focus on this paper and concentrate on an audience interested in depth estimation instead of mainly focusing on the guarantees. Currently, the paper is a bit split – regarding reading flow etc. it is hard to really have a consistent story (risk control, stretching functions, depth estimation).\n- No conclusion in the end, the paper ends very abruptly.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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": "l49vziE-is", "reviewer": "Reviewer_sghz", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "Uncertainty quantification is necessary in high-stakes applications, where both high predictive accuracy and reliable safeguards to handle unanticipated changes in data generation. This paper addresses the uncertainty quantification in online settings based on recent advances in adaptive conformal prediction. The proposed approach, called Rolling RC, updates a prediction set as data arrive sequentially, while achieving a desired coverage. The proposed approach is evaluated on five real-world datasets for one-dimensional response and one depth prediction dataset for high-dimensional response, showing that the proposed approach roughly achieves the desired coverage. The claimed contributions include (1) validity on the risk of constructed prediction sets, (2) compatibility with online learning methods, and (3) fast reaction to distribution shift. ", "summary_of_the_review": "I think this paper attacks an interesting online conformal prediction by extending ACI for risk controlling, but currently, weaknesses overweigh strengths. So, I lean to rejection, but willing to adjust my understanding. \n\n\n==== post rebuttal\n\nThanks for the response. My main concern was addressed so I raised my score. The following includes remaining minor concerns. \n\n* I agree that online depth estimation is one showcase of online risk controlling, but I'm still not well-motivated whether we need UQ in online depth estimation as I initially mentioned. I hope someone else come up with a cool application of risk controlling Rolling-RC\n* In comparison to ACI, I initially expected that ACI and Rolling-RC would have similar performance in the standard coverage rate (i.e., the binary loss), but it is not as shown in Figure 9. It would be interesting to discuss the performance difference (e.g., “calibration with cal” is sensitive to the calibration set size). \n", "strength_and_weaknesses": "**Strengths**:\n* Rolling RC is simpler than ACI\n* Rolling RC can control any risk, which is novel in online settings\n\n**Weaknesses**:\n* **W1**. Depth estimation use-case is not convincing\n* **W2**. The claimed contributions are weak.\n* **W3**. The convergence bound is not convincing (in an adversarial sequence)\n* **W4**. Weak or no comparison in related work or results\n\n**Discussion**\n\n**W1**. In Section 1.1, the paper introduces online depth estimation as a motivational example for justifying risk controlling. Here, the paper considers (I guess) depth measurements from accurate sensors (e.g., Lidar) as the ground truth depth, and claimed the necessity for uncertainty quantification for speed-up depth sensing. I think this may be a good example, but there are many missing pieces. First, I’m not sure if there are actual benefits in speed-up by using depth estimation via RGB instead of Lidar. In close range, Lidar can collect accurate depth very quickly, but for far objects, anyway we don’t need accurate depth, for example, in self-driving scenarios. Secondly, this motivation example uses the sensor measurements from an accurate sensor as ground truth, but it is unrealistic. For example, Lidar can be very noisy or wrong in snowy weather or puddles in the ground. So, it provides wrong labels to online learning algorithms. At least these two points undermine the justification on the necessity of risk controlling in online settings. Could you refine the motivation example more?\n\n**W2**. The paper claims three contributions: (1) validity on the risk of constructed prediction sets, (2) compatibility with online learning methods, and (3) fast reaction to distribution shift. \n\nFor the risk validity, it is novel in online settings (considering risk controlling is possible under iid), but I’m not convinced why we need risk controlling as mentioned in W1. \n\nFor the second contribution, I think this holds for any conformal approaches, including ACI; I don’t think this is a unique contribution of this paper.  \n\nFor the fast reaction to the distribution shift, I feel that this is a bit contradictory. The paper proposes several interesting stretch functions to reduce prediction set size, while maintaining a desired coverage. But, choosing a stretch function is equivalent to hyperparameter tuning. Meaning that, a good stretch function depends on the property of a data sequence, but simultaneously online algorithms, including Rolling RC, want to work for any distributions. I think I mainly get this impression on the way of choosing hyperparameters of this paper, i.e., hold out an initial subsequence in the entire sequence and test on the later subsequence. This hold-out-first-sequence approach does not make sense in distribution shift, as the initial subsequence cannot represent the later sequence. Could you justify this tuning approach? \n\n\n**W3**. I was trying to understand the convergence bound in the last equation of Theorem 1 proof. Mainly, I was curious about why this deterministic algorithm could work in adversarial settings; recall that traditional online learning algorithms are randomized such that an adversary could not entirely fool the algorithms (or need a realisability assumption, e.g., for the perceptron algorithm). \n\nTo make the analysis simple, let m=0, M=1, \\gamma=1, \\theta_1=0, risk is the indicator loss, and r=0.1. Then, this convergence bound means the absolute difference of the average coverage rate and a desired coverage rate r is bounded by 1/T. By setting T = 10, this means after 10 time steps, the average coverage rate is at most 0.2 for any sequences. So, an adversary can choose an odd-subsequence (i.e., data arrive in odd time) such that a prediction set makes an error. Then, the \\theta changes as follows: \n\nt=1: 0 -> 0.9, \nt=2: 0.9 -> 0.8, \nt=3: 0.8 -> 1,\nt=4: 1 -> 0.9,\nt=5: 0.9 -> 1,\n…\nAs can be seen, at the odd time, \\theta is not one, the adversary can generate a datum to make an error. This means the average coverage rate is 0.5, which is larger than the bound by theorem. Could you correct my understanding? If not, what are additional assumptions to achieve the desired coverage rate?\n\n**W4**. The risk controlling aspect is new in online learning, but I’m not sure why we cannot use the risk controlling idea along with ACI? As mentioned, ACI updates the coverage rate, while Rolling RC updates the threshold directly. What is the reason that we cannot control risk in ACI? If that’s possible, what’s the benefit of using risk controlling in threshold update? This may be justified empirically. \n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6cmnRyZc-DP", "reviewer": "Reviewer_EbJN", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "In this paper, the authors presented a simple, intuitive, and effective method for quantifying uncertainty for online learning models. The proposed framework provides uncertainty sets that provably control risk, applies to any base online learning algorithm, any user-specified level, and works with non-stationary distributions. The paper presents both empirical and theoretical results that demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "I enjoy reading this paper and find the results interesting.", "strength_and_weaknesses": "Strength:\n\n1. The proposed method is simple, intuitive, and effective. It has the flexibility to be applied to many different base online learning algorithms with easy implementation.\n\n2. The proposed method can control multiple tasks and provide valid intervals for all requirements over long-range windows in time.\n\n3. Rolling RC is also able to adapt to shifting distributions quickly. The authors also designed several stretching functions for faster adaptation. Their effectiveness is also empirically verified.\n\nQuestions and weaknesses:\n\n1. In section 3.2, the authors applied \"Rolling RC\" to the regression problem by combining the proposed framework with quantile regression. I would assume the proposed framework can also be applied to standard linear regression (i.e., the M_t being the standard linear regression model, instead of a quantile regression model). Is this understanding correct?\n\n2. It seems that the definition of $MC_t$ on page 7 does not match the explanation below. The current definition seems to say $MC_t$ is simply the cumulative miscoverage counter, instead of a counter of \"miscoverage events happened in a row\".\n\n3. For the experiments in Fig 3, it seems the coverage of energy, traffic, and prices are below 90% when using the \"Error\" stretching function. How to interpret this result? \n\n4. How to interpret the additional assumption in Thm 3 (as compared to Thm 2)? Why does this new assumption represent that \"the risks are more synchronized with each other\"?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "4WmF9Uy4G5L", "reviewer": "Reviewer_9cEN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper proposes a framework to construct uncertainty sets in the online setting to control the risk of the coverage, false negative rate, or F1 score. The propose method has theoretical guarantee for risk control at the user specified level for different underlying data like distribution shifts over time in an unknown manner. It is also extended to control multiple risks simultaneously and experiments show the proposed method rigorously controls various natural risks. \n", "summary_of_the_review": "I think the problem the paper is trying to solve is very interesting and meaningful. The paper is well-written and easy to read, which is good for the readers to learn the main points of the paper. Although the theoretical results look stronger than previous work in the online learning setting, the technics it uses are very incremental and would not provide much insights for the potential readers.", "strength_and_weaknesses": "Strength:\n  1. The framework for constructing uncertainty sets has theoretical guarantee on the risk control, which is also extended to control multiple risks simultaneously.\n  2. The theoretical result is applicable even when the underlying data has drastic distribution shifts over time in an unknown manner.\n\nWeakness:\n  The results are very incremental to the previous works such as Gibbs & Candes, 2021 for the theoretical findings and Angelopoulos et al., 2021a; 2022a; Bates et al.,2021 for the different control metrics extension besides coverage rate", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject