Achieving Risk Control in Online Learning Settings
Authors: Shai Feldman
Liran Ringel
Stephen Bates
Yaniv Romano
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (11/2023)
Achieving Risk Control in Online Learning Settings
Shai Feldman
shai,feldman Cere:ddmaaancc..ccccoooooooo www.wion..........
Deportment of Computer Science Technion, Israel
Liran Ringel
tirovringel@es..cchhiio...cc
Department of Computer Science Technion, Israel
Stephen Bates
hewpeeebbbbes@@sseeeeeeeeee edu
Deportments of Statistics and of EECS UC Berkeley
Yaniv Romano
gromanno@tecrrion..cc
Deportments of Electrical and Computer Engineering Computer Science Technion, Israel
Reviewed on OpenReview: https: // openreview. formm? 5d=5Y040hvoJu
Abstract
To provide rigorous uncertainty quantification for online learning models, we develop framework for constructing uncertainty sets that provably control risk-such 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 al 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 fiexible as can be applied with any base online learning algorithm (e-g., a deep neural network trained online), requiring minimal implementation effort and essentially additional computational cost. We further extend our approach to control multiple risks simultaneously, the prediction sets generate are valid for all given risks. To demonstrate the utility of our method, we conduct experiments on real-worls tabular timo-scries 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.
1 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 lata-generating process. Reasonable accuracy on fixed validation set is not enough, as 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 have real-time view of the surrondingg of the car. To successfully operate such autonomous system, should measure the distance between the car and close-by objects, e.g., via a 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 a 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 predict the depth map from a given RGB image (Patil al., 2020; Zhang et al., 2020). The goal of these methods is artificially speed-up depth sensing acquisition time. However, making decisions solely based estimate of the depth map

---

Published in Transactions on Machine Learning Research (11/2023)
is insufficient as the predictive model may not be accurate enough. Furthermore, the distribution 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/sela that augment point predictions and have a long-range error control. In the autonomous driving example, the uncertainty the depth map estimate represented by depth-valued uncertainty intervals. In this paper, we introduce novel calibration framework that can wrap any online learning algorithm (e.g., LSTM model trained online) to construct prediction sets with guaranteed validity.
Formally, suppose an online learning sctting where are given data stream {(x, HEN in a sequential fashion, where X, E X' is a feature vector and Y, E 3 is larget variable. In single-outppt regression settings y= R, while in classification tasks y is a finite set all class labels. The input X, is commonly a feature vector, i.c., X' = IR, although it may take different forms, as in the depth sensing task, where X, E MxNx3 is an RGB image and Y RMX is the ground truth depth. Consider a loss function L(Y,, (x))) (hat measures the error of the estimated prediction set (x,) S with respect to the true outcome Y,-
Importantly, at each time step t N, given all samples previously observed {(X,, Yi) along with the test feature vector Xt, our goal is to construct prediction set Cx(X)) guaranteed to attain any user-specified risk level r:
R(C)
lim T-x0 T
(xx,)) =I
(1)
For instance, natural choice for the loss L in the depth sensing task is the image miscoverage loss:
Limage miscoverage (Y,, C(X,)) MN (m, Y! )m,)(..)
(2)
In words, Limage miscoverage (Y,, (X.)) is the ratio of pixels that were miscovered by the intervals Emm.n (X,), where (m, 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 r 20% is a possible choice for the desired miscoverage frequency. Another example of a loss function that is attractive in multi- classification problems is the false negative proportion whose corresponding risk is the false negative rate.
80
60
(a) Input Frame
(b) Cround Truth Depth
30
60
20
40
10
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 at time step = 8020. All values are in meter units.
2

---

Published in Transactions on Machine Learning Research (11/2023)
In this work, we introduce rolling risk control (Rolling 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 on the data distribution, as guaranteed by Theorem 3.1. We accomplish this by utilizing the mathematical foundations of adaptive conformal inference (ACI) (Gibbs & Candes, 2021) which is a groundbreaking conformal calibration scheme that constructs prediction sets for any 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 Importantly, one cannot simply plug arbitrary loss function into ACI and achieve risk control. The reason is that ACI works with conformity scores-a measure of goodness-offit-thal are only relevant to the 0-1 loss, but do not exist in the general risk-controlling setting. Therefore, our Rolling RC broadens the set of problems that ACI can lackle, allowing the analyst to control an arbitrary loss. Furthermore, the technique we propose in Section 3.3 is 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 schome is lightweight and can be integrated with any online learning model, with essentially zero added complexity. Lastly, in Section 3.2.1 we carefully investigated the design choices of our method to adapt quickly to distributional shifts. Indeed, the experiments conducted on real benchmark data sets, presented in Section 4, demonstrate that sophisticated designed choices lead to improved performance.
1.1 A Motivating Example: Uncertainty Quantification for Online Depth Estimation
Recall the online depth sensing problem, where our goal is to construct a prediction interval (X,) C R for each pixel (m, n) that contains the ground truth depth Y at 80% frequency. That is, we aim at controlling the image miscoverage loss (2) at level 20%. To accomplish this, we apply our Rolling framework using neural network model for depth estimation; in Appendíx C.2.4 give more information regarding the online training scheme and the implementation details.
Figure 1c shows the estimated depth image generated by the base model and Figure 1d 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 2 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%. Software implementing the proposed framework and reproducing our experiments is available at https: //gith/ cwtp./.ccc/aaaaa 128/rrc.
100
60
Average Length
Coverage
75
40-
50
20
25
8000
8500
9000
9500
10000
8000
8500
9000
9500
10000
Time
Time
Figure 2: The coverage rate and average interval length (in meters) over each image the test sequence achieved by the proposed uncertainty quantification method. The average coverage is 80.00% and the average length is 18.04 meters.
2 Background
Conformal inference (Vovk et al., 2005; Angelopoulos & Bates, 2021) is a generic approach for constructing prediction sets regression or classification tasks that attain any pro-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 (Papadopoulos et al., 2008; Tei et al., 2018). In nutshell, the idea is to split the
3

---

Published in Transactions on Machine Learning Research (11/2023)
observed labeled data into training and calibration sets, fit model on the training set, and evaluate the model's goodness-of-fit on the reserved holdout calibration points. Under the iidd assumption stated above, the prediction sets produced by split conformal prediction are guaranteed to have the following coverage property: 1 1- E & C(X) 2 1 1-a, a, where (X,Y) is a fresh data point and a is a pre-specified miscoverage rale.
While coverage rate is an important property, in real-world applications, it is often desired to control metrics other than the binary loss 1(Y & C(X)) that defines the coverage requirement. Such losses include the Fi-score 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., 2021a; Bates et al., 2021; Angelopoulos et al., 2022a). Analogously to split conformal prediction, these methods provide a rist-controlling guarantee that holds under the i.i.d. assumption. In particular, such guarantees do not hold for timo-varying data with arbitrary distributional shifts, as the i.i.d. assumption would not hold anymore.
Since the i.id 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. For instance, the proposal of Chernozhukov et al. (2018) assumes a block structure among dependent samples. In (Cauchois et al., 2020; Tibshirani et al., 2019), it is assumed that there is a single distributional shift between the training and test data, which poses a significant constraint when applying these methods for time-series data, Furthermore, Xu & Xie (2021) proposed a protstrap-assed technique that achieves marginal coverage with finite data under some assumptions on the predictions' error. Lastly; Stankeviciute et al. (2021) developed multi-step ahead predictor with coverage guarantees across the prediction horizon relying a weaker notion of exchangeability. 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, ACI (Gibbs & Candes, 2021) generates uncortainty sets that are guaranteed to achieve a user-specified level of the 0-1 loss:
[1,
Ye $ C(X,),
La (Yr, 11 [xx4C1(X0) = 0. otherwise.
A recent work by Gibbs & Candès (2022) proposes a more sophisticated approach to track past coverage rates to better adapt to distributional shifts. In general, this line of research is 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 a 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.
3 Proposed Method
3.1 General formulation
We now turn to present Rolling RC-a general framework for uncertainty quantification in an online learning setting, which satisfies the risk requirement. in (1). Towards that end, we define set construction function
(x,,,) f(,,, E 2
(4)
that gets as an input (i) the test X,, (ii) fitted model M, trained on all data (Xe,YeH up to time t, and (iii) a calibration parameter Oz, and returns prediction set. Above, 2 is the power set of y. The model Mr(X,) is used to form prediction for Y; given the current feature vector Xy; we will provide soon concrete formulations for the set constructing function f as well as examples for M. The calibration parameter O2 E R controls the size of the prediction set generated by f: larger 8g leads to larger sets, and smaller 9 leads to smaller sets. Under the assumption that larger sets produce a lower loss, 0, allows us to control the risk over long-range windows in time: by increasing (resp. decreasing) 0, over time we increase (resp. decrease) the empirical risk. Once Y, is revealed to us, we tune 0, according to the following rule:
0 0, 71+ r)-
(5)
4

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 1 Rolling RC
Input:
Data N.) S [Xx]] v, given as stream, desired risk level E IR, a step size y > 0, set constructing function f M,) + 2 and an online learning model M.
Process:
1: Initialize 0n = 0.
2: for t= L...., do
3: Construct a prediction set for the new point Xx: Cx(x)) f(,c,
Obtain Y.
Compute 4 I(Y,, (x))))
6: Update lc+1- 01 + 7(4 r).
7: Fit the model M, on (X,, Y,) and obtain the updated model Me+1
8: end for
Output:
Uncertainty sets (x,) for each time step t E {I....T}
This update rule is exactly that of ACI (Gibbs & Candès, 2022), extended to more general setting, Above, 4 = L(Y,, ((X))) is the loss at time t, and > 0 is fixed step size, e.g., 0.05. In Appendix C.3.3 we study the effect of y on the resulted sets and provide a suggestion for properly setting it. The pre-defined constant r is the dosired risk level, specified by the user, c.g., 0.1 for the false negative proportion loss or the miscovcrage loss. Lastly, we obtain new predictive model MM+1 by updating the previous M, with the new labeled pair (X,, Yo), 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.1. In Appendix A.2 we introduce a more general theorem that extends the domain of Õ, beyond the power set 2
Thcorem 3.1. Suppose that
2 is interval/str sett constructing function. In addition, suppose that there erist conslands and M such that for all E X, y E and M E MI, fxx 0,M) = for all 0 > M, f(X,0, M, = 0 for all 0 < m. Further suppose that the loss is bounded and salisfies L(y. < and L(y. 0) > т. Consider the series of calibrated intervals: {Ce(X,) where Co(X,) )) is defined according to (4). Then, the calibrated intervals satisfy the risk requirement in (1). Furthermore, the empirical risk falls within a C/T factor of the desired level r, where C = (M m + 4 BB) is a known conslant and > is the mazimal absolute loss.
R.R.MM)
Crucially, this theorem states that the risk-control guarantce of Rolling RC holds for any distribution (tx any sel-valued function f, and any sequence of online-updated predictive models {Mc}r. The requirements for Theorem 3.1 hold are (i) the function 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 dosired level r for the full label set ) and exceeds r for the empty set. Also, note that the step size y and the bounds m, M must be fixed in order to control the risk.
Observe that our method is immune to over-fitting by design even though we use the same data point twice: the evaluation 6, is conducted by using the predictions produced by an "old" model, before updating it with the new labeled point. Furthermore, notice that our calibration scheme lightweight as the computational complexity required for updating the calibration parameter 0 is negligible compared to invoking and fitting the model M. Also, the online fit of the model in Line 7 is optional and recommended to adapt faster to distributional shifts, though it could be omitted be performed in lightweight manner to reduce the computational cost. Importantly, the guarantecs we provide hold no matter if the model is trained offline or updated online. Moreover, our new formulation unlocks new design possibilities: we can define any prediction set function ff while guaranteeing the validity of its output by calibrating any parameter 6,, This parameter can affect f in highly non-linear fashion to attain the most informative (i.c., small) prodiction sets. Specifically, we scale with a stretching function & (c.g., an exponential function) and construct a prediction set using (0) instead of 0. Of course, the performance of the proposed scheme is influenced by
5

---

Published in Transactions on Machine Learning Research (11/2023)
the design of f. which is the primary focus of the next sections. Interestingly, the experiments in Section 4 show that powerful stretching functions lead to improved performance.
3.2 Rolling RC for Regression: Stretching and Interval Constructing Functions
In this section, we focus 1-dimensional response variable Y and aim to control the 0-1 loss in (3). To accomplish this, we present specific choices for the stretching and interval constructing functions that result in narrower intervals. Note that in Section 4.1.4 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 time horizon. Furthermore, in Appendix we provide a concrete scheme for handling a multi-dimensional Y.
Suppose we are interested in constructing prediction intervals with 1 a coverage frequency, using quantile regression model Mr that produces estimates for the a/2 and 1 a/2 conditional quantiles of the distribution of Y, Xt. We denote these estimates as MM(XX,, a/2) and M, obtained by fitting an LSTM model that minimizes the pinball loss; see Appendix C.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 1-d a 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-varying distributional shifts. Consequently, to ensure valid coverage control, we apply Rolling RC. Taking inspiration from the method of conformalized quantile regression (CQR) (Romano et al., 2019), we use the following interval construction function:
a/2), respectively, which can be
0(, 0r =
- -(0)) ((.)).
(6)
Above, the interval endpoints are obtained by augmenting the lower and upper estimates of the conditional quantiles by additive calibration term (0t)). The role of 0, is the same before: the larger 9,, the wider the resulting interval is. The calibration parameter is further scaled by the stretching function which provides the ability to adapt more quickly to distributional shifts. While the long-range risk control achieved by Rolling RC is unaffected by distributional shifts, as Theorem 3.1 states, powerful stretching functions can be applied to improve the statistical efficiency or lead to better risk control small windows of time. We now present and review three design options for the stretching function s.
3.2.1 Stretching Functions for Faster Adaptation
None. The first and perhaps most natural choice is p(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 7 used to update A must be fixed throughout the entire process. As a result, the calibration parameter 0, might be updated too slowly, resulting in an unnecessary delay in the interval's adjustment.
Exponential. The exponential stretching function, defined as spx) = - for x > 0 and p(xx) = - + +1 for x S O, updates the calibration adjustment, factor with an exponential rate: ('(x) = e", even though the step size for O₂ is fixed. In other words, it updates (0,)) gently when the calibration is mild (sp(0) is close to 0), and faster as the calibration more aggressive (vp(0:) is away from zero).
Error adaptive. The following stretching function updates O, more rapidly when the loss of the previous data point ε is farther from the desired risk Furthermore, it makes larger updates when Y, is far from the interval's boundaries. More formally, denote the CQR non-conformily score (Romano et al., 2019) by
si = max (XX, - Y, Y: M,(X, - a/2)].
which measures the signed distance of Y, from its closest boundary. Next, define
(0) = 0 + _amor where Xorror = clip(Aer - geeore St-1 exp [ggnes - -r()).
Above, clip(z) max (min (z. gmax], },
"mmxx,pmmnn gming is clipping function applied to restrain the effect of an outlier Yt that is far from the boundaries, and, gloss, gecore Blow, ghigh are hyperparameters.
6

---

Published in Transactions on Machine Learning Research (11/2023)
The discussion above sheds light on the great flexibility of Rolling RC: can accurately find the correct adjustment to the uncertainty set while being adaptive to rapid distributional shifts in the data. Furthermore, Theorem 3.1 guarantees the risk validity regardless of the choice of the stretching function. In Appendix D.1.1 we propose an additional stretching function and compare all proposed stretching functions. This analysis indicates that. the 'error adaptive' stretching the best choice.
3.3 Controlling Multiple Risks
In this section, we show how to control more than risk and construct intervals that are valid for all given risks. To motivate the need for such a 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 certain threshold. This design choice meets reality since the coverage at the center falls below 60% in more than 19% of the timestamps, as presented in Figure 6 in Section 4.2.1. This figure also indicates that controlling the image coverage does not control the center failure loss. Concretely, formulate the center failure loss
Loenter failure (Y,, C(Xi)) = o{ |eeneer [(m, n.) E center: Y,m.. C (m,)"(X,)) S 60%
We define the center of an image as the middlemost 50x50 grid of pixels. Controlling the center failure loss at level r r= 10% ensures that more than 60% of the center will be covered for 90% of the images.
More generally, suppose we are given k arbitrary loss functions {Li]ez and aim control their corresponding risks, each at level r'. In this setting, the set constructing function f(-) gets input the test X,, the fitted model Mr, and a calibration vector 0, E RR,, and returns prediction set
((X,, ((. 2²
Similarly to the single risk-contron controlling formulation described in Section 3.1, f controls the size the generated set: by increasing the coordinates in l we encourage the construction of larger sets with lower risks, and we tune it likewise:
l l + +1
where 1 L,(Y,, (X.)) and z > 0, = I...., L the corresponding step size. We now show that this procedure is guaranteed to produce uncertainty sets with valid risks.
Theorem 3.2. Suppose that f : (X, R, M) + 2 is an intervul/sel constructing function. In addition, suppose that there exist constants [M such that for all X and M, M.) y if 6¹ M for some i k1. Further suppose that the losses are bounded and satisfy L'y, < r² for every y y and E (1, Consider the following series of calibrated intervals: {C((X,))Ex where C,(),) is defined according to (8). Then, the calibrated intervals allain valid risk:
We (1...... 3D E R
s.t
Σ T
1 (.,%C.(())) S
D
T-x
If we further assume that the risks are more synchronized with cach other, we can achieve an exact multiple risks control, as stated next.
Theorem 3.3. Suppose that is an interval/set constructing function and (L' are loss functions as in Theorem 3.2. Further suppose that there exist constants {m'} such that f(X,0, M) = if m' for some i E [1,..k} and that the losses satisfy L' L' 0) > r² for every y E and i E {1...k). Then, the intervals achieve the exact risk:
T L,(Y,,;((X,) -
Vi (1,..,k) k} :(())
= Jim T- T
7

---

Published in Transactions on Machine Learning Research (11/2023)
The proofs of the theoretical results are given in Appendix A. In words, Theorem 3.2 guarantees that Rolling RC can always conservatively control multiple risks. However, obtaining an exact control over multiple risks is not necessarily possible. One extreme example of that is controlling the miscoverage rate at level 0% and the average length at level O, which is impossible. Nonetheless, Thcorem 3.3 states that Rolling RC exactly controls multiple risks when during the calibration process, there are no two coordinates in l such that the first too low (requires widening the interval), and the other is too high (requires shrinking the interval). In other words, multiple risk control is obtained when the risks do not come at the expense of each other, meaning that changing risk does not affect the other ones. Lastly, we note that in this section we presented one implementation of Rolling RC to control multiple risks, although other approaches may be valid as well, e.g,, techniques with calibration parameters that are independent of the number of risks.
4 Experiments
4.1 Single Response:
Controlling Single Risk in Regression Tasks
In this section, we study the effectiveness of our proposed calibration scheme for time series data with 1-dimensional response variables. Towards that end, we describe two performance metrics that we will use in the following numerical simulations to assess conditional/lut /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 t:
MC MMC,1++ 1, Y, & (x(,,) otherwise
MC,
0,
where MCn =0 0. Similarly to the coverage metric, MC, 0 at timestamps for which Y, E (X,).. By contrast, when Y, & (X,), the value of MC, is the length of the sequence of previous miscoverage events. Therefore, we can apply Rolling RC to control the MC level and prevent long sequences of failures. Interestingly, controlling the miscoverage counter immediately grants a control over the standard coverage metric, as stated next.
Proposition 4.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 a given coverage rate - a. In a nutshell, we argue that a model that has access to the true conditional quantiles attains an MC ar(1 - at). Therefore, our experiments we seek to form the tightest intervals with an 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 to MC, which is defined on single timestamp, the MSL is defined over a sequence of uncertainty sets {Cr(X,))TTT Ti S 2d and response variables (X1) Y as:
MSL : П
Σ KEZ
minfi: Ye4s E Crts(Xe4i) or orl= 7Ti
where I is a set containing the starting times all miscoverage streaks. The formal description is given in Appendix E.1, where we also show that an ideal model that uses the true conditional quantiles achieves an MSL of 1/(1 - a). Therefore, we aim 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 a 1-dimensional Y: Power, Energy, Traffic, Wind, and Prices. We commence by fitting an initial quantile regression model on the first 12000 data points, to obtain reasonable predictive system. Then, passing time step 12001, we start applying the calibration procedure while continuing to fit. the model in an online fashion. Next, we
8

---

Published in Transactions on Machine Learning Research (11/2023)
choose the calibration's hyperparameters based the validation set, indexed by 12001-16000. Lastly, we measure the performance of the deployed calibration method data points corresponding to time steps 16001 to 20000. In all experiments, we fit an LSTM predictive model (Hochreiter & Schmidhuber, 1997) in an online fashion, minimizing the pinball loss to estimate the 0.05 and 0.95 conditional quantiles of Y; Xx; these estimates are used to construct prediction intervals with larget 90% coverage rate. We calibrate the intervals according (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. Figure 3 summarizes the performance metrics presented in Section
energy
energy
energy
traffic-
traffic
traffic
Dataset
Dataset
Dataset
prices
prices
prices
Method
power
power
power
RRC
wind
RRC (Error)
wind
wind
89.0
89.5 Coverage
90.0
90.5
1.0
1.2
1.0
1.2
1.4
1.6
Average length (scaled)
MSL
Figure 3: Performance of Rolling RC without stretching (orange) and with 'error adaptive' stretching (blue) real data sets, aiming to control the coverage rate at level 1 - 90%. The length of the prediction intervals is scaled per data set by the average length of the constructed intervals. Results are evaluated on 20 random initializations of the predictive model.
4.1.1, showing that both stretching methods attain the desired coverage level; this is guaranteed by Theorem 3.1. Additionally, this figure reveals 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.
4.1.3 Comparing Rolling RC to Baselines
In this section, we consider two baselines for constructing uncertainty sets: the naive, uncalibrated outputs of the learning model, and an instantiation of ACI (Gibbs & Candes, 2021), which we refer to as calibration with cal. It constructs uncertainty sets with controlled miscoverage rate using calibration points, but does not hold out a large block. Rather, previous points are simultaneously used both for calibration and model fitting. We run an uncalibrated online learning model, Rolling RC with 'error adaptive' stretching, as described Section 3.2.1, and calibration with cal as defined in Appendix D.1.2. Figure 4 shows that Rolling RC constructs narrower intervals than calibration with cal while attaining the best conditional coverage metrics. Additionally, this figure reveals that Rolling RC and calibration with cal achieve the nominal coverage level, as guaranteed by Theorem 3.1, while the naive approach does not. In light of the poor performance of the baselines, indicated by all metrics, omit their analysis from the subsequent experiments. Lastly, in Appendix D.1.2 we assess the methods using another metric for evaluating conditional coverage for time-series data.
4.1.4 Controlling Miscoverage Counter
Figure 5 shows that Rolling RC applied on the real data sets with the goal of controlling the
coverage at level - 90% achieves MC risk that is higher than a/(1 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 r = 1/9. The results are summarized Figure 5, revealing that (i) the risk rigorously controlled even though it defined over the time horizon, and (ii) by controlling the MC risk we also achieve valid coverage rate.
9

---

Published in Transactions on Machine Learning Research (11/2023)
Average length (scaled)
90
1.4
Coverage
85
1.2
Method
Naive
1.0
ACI
75
RRC (Error)
0.8
energy
traffic
prices Dataset
power
wind
energy
traffic
prices
power
wind
Dataset
Miscoverage counter
0.6
2.0
0.4
MSL
1.5
0.2
1.0
energy
traffic
prices
power
wind
energy
traffic
prices
power
wind
Dataset
Dataset
Figure 4: Performance of the uncalibrated outputs (green), calibration with cal (Algorithm 2) (red), and Rolling RC with 'error adaptive' stretching (blue). All methods are applied to control the coverage rate at level = 90%.
energy
Method
energy
energy
RRC
traffic
RRC (Error)
traffic
traffic
Dataset
Datasel
Dataset
prices
prices
prices
power
power
power
wind
wind
wind
0.125 0.150 0.175 0.200 Miscoverage counter
88
90
92
94
0.10
0.15
0.20
Coverage
Miscoverage counter
(a) MC calibration
(b) MC calibration
(c) Miscoverage calibration
Figure 5: Performance of Rolling RC without stretching (orange) and with ferror adaptive' stretching (blue) on real data sets. (a) and (b) we aim to control the MC risk at level r = ax(1 - a) 1/9. In (c) we aim to control the coverage level a 90%. Other details are as in Figure
4.2 High Dimensional Response: Online Depth Estimation
In this section, we analyze Rolling for a single risk or multiple risks controlling, but first, provide details about the experimental setup. We apply Rolling RC on the KITTI benchmark (Geiger al., 2013) in which the task is to estimate depth map given an RGB image. We use pre-trained LeReS (Yin et al., 2021) model with ResNeXt101 backbone the base prediction model. We fit this model offline on the first 6000 samples for 60 epochs, to obtain reasonable model. Then, passing time step 6001 we start training the model in an online fashion while applying the calibration procedure. We choose the hyperparameter configuration based on the validation set, indexed by 6001 to 8000. Lastly, we measure the performance on data points corresponding to time steps 8001 10000. We construct the intervals according (9) from Appendix B, using exponential stretching. We repeat each experiment for 10 trials. In Appendix C.2 we provide the full details about this experimental setup.
10

---

Published in Transactions on Machine Learning Research (11/2023)
4.2.1 Controlling Single Risk
In this section, we evaluate the results of Rolling RC applied to control only the 'image miscoverage' risk (2) at level 20%. Figure 6 displays the performance of our proposal, revealing that Rolling RC attains the nominal risk level, as guaranteed by Theorem 3.1. Nevertheless, when Rolling RC is applied to control only the image miscoverage risk, constructs prediction sets that suffer from high center failure rate. We overcome this limitation by controlling multiple risks, as presented next.
20.0
Image coverage
86
Average length
32
Center failure rate
17.5
30
84
15.0
28
12.5
82
26
10.0
80
RRC
RRC (multi)
RRC
RRC (multi)
RRC
RRC (multi)
Method
Method
Method
Figure 6: Performance of Rolling RC applied to control only the 'image coverage' (single risk) both 'image coverage' and 'center failure' (multiple risks).
4.2.2 Controlling Multiple Risks
In this section, we analyze Rolling RC for multiple risks in the depth prediction setting. In particular, we 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 rale from (7) at level 10%. As portrayed in Figure 6, when Rolling RC set to control only the image miscoverage risk, violates the center failure loss; the center coverage falls below 60% for 19% of the time-steps. However, when applying Rolling achieves both valid image coverage rate, of approximately 86%, and valid center failure rate, of 9.9%. This is not surprise, as it is guaranteed by Theorem 3.2.
control the two risks, it
5 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 on the data, and can be applied for a broad class of tasks, such as regression, classification, image-to-image regression, and more. Furthermore, Rolling RC to provably control multiple risks, so that the uncertainty sets constructs are valid for all given risks. One limitation of our method is the reliance on fixed step size 7 used to tune the raw risk level; improper choice of this hyperparameter may introduce undesired delays in adapting distributional shifts. Therefore, it is of great interest to develop procedure that would automatically tune the calibration hyperparameters 'on the fly' to attain improved performance, e.g., by borrowing ideas from (Zaffran et al., 2022; Gibbs & Candès, 2022). Meanwhile, we suggested way to overcome this limitation using stretching function, which leads to improved performance, as indicated by the experiments. Lastly, it must be exciting to explore the impact the stretching function on the performance of the algorithm.
Scction 3.3 we extended
Acknowledgments
Y.R., L.R., and S.F. were supported by the ISRAEL SCIENCE FOUNDATION (grant No. 729/21). Y.R. also thanks the Career Advancement Fellowship, Technion, for providing research support. S.F. thanks Idan Aviv for insightful discussions regarding depth estimation. S.B. thanks Isaac Gibbs for comments on an early version of this manuscript.
11

---

Published in Transactions on Machine Learning Research (11/2023)
References
Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, Michael I. Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint, 2021a. arXiv:211001102..
Anastasios N Angelopoulss, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXic:2208.0 02814, 2022a.
Anastasios N Angelopoulos, Amit Pal Kohli, Stephen Bates, Michael Jordan, Jitendra Malik, Thayer Alshaabi, Srigokul Upadhyayula, and Yaniv Romano. Image-to-image 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-free uncertainly quantification. arXiv preprint, 2021. arXiv:2107.07511.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference Learning Representations, 2021b.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael I. Jordan. Distribution-free risk-controlling prediction sels. Journal of the ACM, 68(6), September 2021. ISSN 0004-5411.
Maxime Cauchois, Suyash Gupta, Almu Ali, and John C Duchi. Robust validation: Confident predictions even when distributions shift. arx preprint Xiv:20008 04267, 2020.
Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validatod confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 2281)): 2021.
Victor Chernozhukov, Kaspar Wüthrich, and Zhu Yinchu. Fxact 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, lan Char, and Jeff Schneider. Beyond pinball loss: Quantile methods for calibrated uncertainty quantification. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neurul Information Processing Systems, 2021.
Energy. Appliances energy prediction. prediction. Accessed: April, 2021.
Shai Feldman, Stephen Bates, and Yaniv Romano. Improving conditional coverage via orthogonal quantile regression. In A. Beygelzimer, Y. 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 Vanghan (eds.), Advances in Neural Information Processing Systems, 2021.
Isaac Gibbs and Emmanuel Candès. Conformal inference for online prediction with arbitrary distribution shifts. arx preprini orx::22008.08. 2022.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9:1735 80, 12 1997.
12

---

Published in Transactions on Machine Learning Research (11/2023)
Rafael Izbicki, Gilson Shimizu, and Rafacl Stern. Flexible distribution-free conditional predictive bands using density estimators. In Proceedings of the Twenly Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 3068 3077. PMLR, 26 28 Aug 2020.
Yichen Jia and Jong-Hyeon Jeong. Deep learning for quantile regression under right censoring: DeepQuantreg. Comput. Stat. Data Anal., 165(C), jan 2022.
Jae-Il Jung and Yo-Sung Ho. Depth map estimation from single-view image using object classification based on bayesian learning. In 2010 3DTV-Conferece: The True Vision Capture, Transmission and Display of 3D Video, pp. 1-4, 2010. doi:
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. ISSN 00129682, 14680262.
Roger Koenker and Kevin F. Hallock. Quantile regression. Journal of Economic Perspectives, 15(4):143-156, December 2001. doi: 10.1257/jep.15...11
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statisticol Association, 113(623).1094-1111 2018.
Anal Levin, Dani Lischinski, and Yair Weiss. Colorization using optimization. In ACM SIGGRAPH 2004 Papers, SIGGRAPH '04, pp. 689 694, New York, NY, USA, 2004. Association for Computing Machinery.
Zhenyu Li, Zehui Chen, Xianming Liu, and Junjun Jiang. Depthformer: Exploiting long-range correlation and local information for accurate monocular depth estimation. arXiv preprint arXiv:2203. 14211, 2022a.
Zhenyu Li, Xuyang Wang, Xianming Liu, and Junjun Jiang. Binsformer: Revisiting adaptive bins for monocular depth estimation. arXiv preprint 2XXi:2204.00966 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 Learning Research, (3(5)): 2022.
Nicolai Meinshausen. Quantile regression forests. J. Mach. Learn. Res., 7:983 -999, December 2006. ISSN 1532-4435.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hanmu Toivonen (eds.). Machine Learning: ECML 2002, pp. 345-3033 356,,,6,555 Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. ISBN 978-3-540-36655-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 (ATA 2008), pp. 64-69, 2008
Youngsuk Park, Danielle Maddix Robinson, Yuyang (Bernie) Wang, and Jan Gasthaus. Learning quantile function without quantile crossing for distribution-free time series forecasting. In ICML 2021 Workshop Distribution-Free 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, (14))6813-6820 2020.
Power. Power consumption of tetouan city. https://archive.. htt.://www...............eaaaaaa consumptiorroo---Tettooaattiii Accessed: April, 2021.
Prices.
French electricity spot prices.
cav. Accessed: April, 2021.
13

---

Published in Transactions on Machine Learning Research (11/2023)
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.
Matteo Sesia and Yaniv Romano. Conformal prediction using conditional histograms. In A. Beygelzimer, 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 to 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.
ics uci. Traffic. Metro interstate traffic volume. https://archii: http://aarrrcoo..........eoaa/// wat..a/aaa//aatttteet/totoooaaaa TraffictVolume. 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. Algorithmiic Learning in Random World. Springer, 2005. doi: 10.1007/b106715
Wind. Wind power in germany. http::/www...ngge..ccoo///ttttt/ 2021.
Accessed: April,
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 2021.
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 Computer Vision and Pattern Recognition, pp. 204-213, 2021.
Weihao Yuan, Xiaodong Gu, Zuozhuo Dai, Siyu Zhu, and Ping Tan. New crfs: Neural window fully-connected crfs for monocular depth estimation. arXiv preprint Xrxw:22203.0153 2022.
Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Diculoveut. Adaptive conformal predictions for time series. International Conference on Machine Learning, pp. 25834 25866. PMLR, 2022.
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 IFFE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4494 4503, 2020.
14

---

Published in Transactions on Machine Learning Research (11/2023)
A Theoretical Results
A.1 Proof of Theorem 3.1
The proof of Theorem 3.1 is based on that of Proposition 4.1 in (Gibbs & Candes, 2021). While the proof is similar, our work greatly enlarges the scope of the result.
We begin by showing that 0g is bounded throughout the entire calibration process. For this purpose, we real number.
assume that the loss satisfies that for all y E y and C E CE2: L(y. C) E [-B, where Lemma A.1. Under the assumplions of Theorem 3.1, for all & N, Og [m - 72B, M + +2BB..
Proof. Assume for the sake of contradiction that there exists f such that 0, M+2yB (the complementary case is similar). Further assume that for all t' 0e S M + 2yB. Since 4, E [-B, BJ, we get that:
0 = 7(4 - r) 2 0, By M + 2y By M.
Therefore, 81-13 M. Since Lyy, f(X,0, 0, =)) < for 0 M, we get that 4 < r. As result:
0: = 0.1 744 - r) 0,- - M +2BB.
Which is a contradiction to our assumption.
Next, we prove Theorem 3.1.
Proof. By applying Lemma A.1 we get that 0s E Mm + +2B) for a N. Denote m' m 22B, and M' M + +BB. We follow the proof of Proposition 4.1 in Gibbs & Candes (2021) and expand the recursion defined in (5):
[m 0r+1 =0 + Σ
7(4 r)).
1=1
By rearranging this we get that:
m' 81
T
Brt1 A1
M'
<
Σ
(4 r)
TTy
T 1=1
T'y
T'y
Therefore:
max (01 m', M' 01}
(1
r)
<
T
T7
Lastly, the definition of the loss, 4 = L(Y,, (x(X))), gives us the risk statement in (1).
Notice that the above proof additionally implies finite-sample bound for the deviation of the empirical risk from the desired level. In particular, the average loss within a C/T factor of r, where C = (M' mmm/"" = (M - m + 4 1144--B11 BBy/,. This bound is deterministic, not probabilistic, Thus, even for the most erratic input sequences, the method has an average loss very close the nominal level.
A.2 General Version of Theorem 3.1
In this section, we provide a general statement with more abstract notations of Theorem 3.1. The following notations extend our proposal to a broader class of problems, so that it could be applied for a larger of tasks, such multi-label classification. Here, we assume that the function f generates variables in y and that the loss function is defined L 3') R. Furthermore, value y' E y and maximal value y' y for which L(y, v') and L(y,y') In the main text, we set v 2², y' and y = We now show that the risk is controlled at the desired level even under this general setting.
assume that there exist minimal
15

---

Published in Transactions on Machine Learning Research (11/2023)
Theorem A.2. Suppose that f (X,R,M) - V is interval/set constructing function. In addition, suppose. that there erist constants m and M such that for all E X, y E E and M E M, f(x M.) = y for all 0 > M, [(x, (,,,0,()) M,M) for all 0 < m. Further suppose that the loss is bounded and satisfies Lyy, <r and L(y.Y y > Consider the following series of calibrated intervals: {Cc(X)) ) where (x2x) is defined according to (4). Then, the calibrated intervals satisfy the risk requirement in (1).
Proof. The proof is similar to the one Theorem 3.1 and hence omitted.
A.3 Proof of Theorem 3.2
The proof of Theorem 3.2 is similar to the proof of Theorem 3.1. We assume that all losses {L,)_ are bounded in the interval [-B, BJ, as in Section A.I, and begin by showing that all coordinates in 0 are upper bounded.
Lemma A.3. Under the assumptions of Theorem 3.2, for all t E N and i E {I, kJ, 0 S M + +2BB.
Proof. Assume for the sake of contradiction that there exist Further assume that for all 1' 1: Ci. M BB Since 1 r² E [-B,, BJ, we get that:
and E (1,...,k) k) such that 0 M + B
-= - r²) 2 e B M B 2 Mr.
Therefore, 0:-1 M Since (y f(X, M) = < rt for 0³ M', we get that & < r'. As result:
a : +0 r) < Φ: s M + 7BB.
Which is contradiction to assumption.
Next, we prove Theorem 3.2.
Proof. By applying Lemma A.3 we get that Ø < M + +BB for all N and i kl. Denote
M M + +BB. We expand the recursion defined in (5):
0 = fi
Σ r0h r²) S M². 1=1
By rearranging this we get that:
1 T
0T+1
0
M 0
+
Σ
-
T
TT
T
-=1
t=1
Therefore:
1
M
0
-
Th
Lastly, by the definition of the loss, 1 LtYY, (x.))) and by setting D M=-0; we gel the slatement in Theorem 3.2.
A.4 Proof of Theorem 3.3
The proof of Theorem 3.3 is similar the proof of Theorem 3.2. We assume that all losses (Li}k are bounded in the interval [-B, B), in Scction A.1, and begin by showing that all coordinates in 0, are lower bounded.
Lemma A.4. Under the assumptions of Theorem 3.3, for all & N and E (1,.... k), 0 2 m 72B.
16

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. Assume for the sake of contradiction that there exist t N and E {1,..., k) such that of < m² B2
Further assume that for all 1' < 1: Oi 2 m² ByB. Since I1 r² [- B, B], we get that:
0- 0 - -(; - r²) 0 + BB m 2B + 2y = =m'.
Therefore, li-1 m'. Since L' f(x,(xX.MMM. >) > rf for 0' < m we get that li > r², As result:
- 7(h r) > 81,1 m 2B
Which is contradiction to assumption.
Next, we prove Theorem 3.3.
Proof. By applying Lemma A.3 and Lemma A.4 get that Of Im [m'--225 -,2B, M + for all & and E k). Denote m² m 22B and M M + 72B. We expand the recursion defined (5):
T
[m', M' 0z 0++1
Li
70 Σ
-r)).
t=1
By rearranging this we get that:
m
8
1
T
07 0
M - 0
(4
rd)
Ty
T
T7
Tr
1=1
Therefore:
T
max L0i
m²
M
0%)
Σ
(1)
x²)
Tr
1=1
Lastly, the definition of the loss, 12 = L' LY,,,, Cx(X))), gives us the statement in Thcorem 3.3.
A.5 Proof of Proposition 4.1
Proof. 11Y, & ((()))) < MC, for any / E N. Therefore:
lim T
MC: <
lim T
1(Y, & C.(X.)) a
1=1
t=1
Uncertainty Quantification in Online Image-to-Image Regression Problems
B.1 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 generally, providing scheme construct and calibrate pixel-valued intervals. Consider rumning model Mc(X,) that maps the input image X, to point prediction of Y,, and we wish to control the image misoeverage 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 Mr(X,) as
(X,) = pm.n (X,, M.) = [M (X,) ArTTh (X.), (X,) + deu m.n (X,))
(9)
Above, 2TTh" (X₂) and un mn. (X,) represent the uncertainty the lower and upper directions, respectively. That is, large value of tmm (X,) indicates that the pixel has high uncertainty in the upper direction. Similarly, large value of u. (X,"((,)) indicates that the pixel has high uncertainty in the lower direction. A
17

---

Published in Transactions on Machine Learning Research (11/2023)
natural choice for the lower and upper uncertainty measures is model estimating the absolute residual error per-pixel, given by W; ", (X,) (X+) = |Y, -,,"""-M,""""" (X))l We provide more sophisticated examples for such uncertainty functions in Section B.2. The parameter A = (0+) E R in (9) stretches the calibration parameter 8,, which we update according to (5). Importantly, this procodure is an instantiation of Rolling and thus attains the correct image coverage, as guaranteed by Theorem 3.1. This also validated in the experiment from Section 1.1.
B.2
Uncertainty Quantification Heuristics
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 an uncertainty heuristic is outputting constant value for every m, n, X: mm, (X) u " = In other words, the set constructing function is defined as:
(m, M.) = (MAMMM))-MMM""C
de. M, (X.) + Au].
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-valued intervals have the same length. These limitations lead to 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 uncertainty quantification technique. Here, Im""(X) umn. "x""(()=== pm.." (x) is an estimate for the residual [M (X) yman and it is formulated
online learning model fitted to minimize the squared residual loss, given by (f(x) - [M"..((a (x) =3) An ideal model that minimizes this loss function outputs the exact residual: [MM))
yl and thus achieves 100% coverage rate for X =. In practice however, the fitted model i may not be accurate and thus we apply Rolling RC, to ensure valid risk control. Observe that, unlike the constant heuristic, here, each pixel is assigned a different uncertainty size. Nevertheless, both techniques produce symmetric prediction intervals.
B.2.3 Previous Residuals
In contrast to the residual's magnitude heuristic, here, we take advantage of the online setting in which the data set is received as stream, and use the past residuals to estimate the current one. We define the positive and negative residuals at time t as:
mh -Mm.(XX Y.
p mmnt max (r.m... 0},
T mn max {-r m.n .0].
The uncertainty heuristic in the lower (upper) direction formulated as the average of the positive (negative) residual in the previous p time-steps:
m_n (X,)
1
Σ
m.
Tt
P F=t-p
(10)
"
(X,) p ''=-pp
m.n
In experiments, set the sliding window's size to p 5.
18

---

Published in Transactions on Machine Learning Research (11/2023)
B.2.4 Correcting Pixels Displacements With Image Registration
The 'previous residuals' method suffers from the following crucial limitation. Objects in the response image Y may appear different positions across time, so that an object that lies in pixel (m, at frame might appear a different pixel time + 1, e.g., (m 7, 11). For example, our depth prediction example the camera and the depth sensor move during the online process, so objects change their locations and do not remain in fixed pixel between consecutive frames. Therefore, to obtain more accurate residual est.imates it is better to correct for the displacement of pixels in consecutive frames. For this purpose, we apply image registration algorithm before evaluating the residuals. In particular, we use optical flow (OF) to register the intimated depth images and the ground truth depth maps. Suppose that OF(im1, im2) receives two images as an input and returns the result the registration of the first image im, to the second one im2. We recursively define optical flow on a sequence as:
OF (im1, 0) im
OF (imi, {im, (im;) " im2), {im, Hi=s).
Then, we register the previous estimated depth images and ground truth depth maps
M = 0F (M(Xi-i), (M(( (M(X) y = 00 (Y,-i, (1-
In plain words, we register each image using the next ones in the sequence. We define the registered residuals as:
Ft = T==M (X,) Y
- m. max {,t m. 0},
p-n.- max - 0).
Then, we compute the average residual, as in (10):
Cm (Xt)
1
Σ
m,n+
Tt
p ヒーtーp
1
m. U
(X,)
Σ mma
p P=t-p
This displacement consideration indeed improves the performance, as indicated by the experiments in Section D.2.
C Experimental Setup
C.1
Single-Output Tasks
C.1.1 The Quantile Regression Model's Architecture
The neural network architecture is composed of four parts: MLP, an LSTM, and another two MLPs. To estimate the uncertainty of Y, X,, we first map the previous k samples {(Xe-i, Yos, T) through the first MLP, denoted as fi,
i wL_ f1
where we set ls to 3 in our experiments. as fz:
The outputs are then forwarded through the LSTM network, denoted
(wi.)/1 =[a((W(-)tn)))
19

---

Published in Transactions on Machine Learning Research (11/2023)
Note that since fo is LSTM model, - is used to compute wi- The last output wi-1 of the LSTM model, being an aggregation of the previous & samples, is fed, together with (X,,)), to the second MT.P model, denoted as f3:
- = fs(wğ
Lastly, we pass w through the third MLP, denoted by fa, with one hidden layer that contains 32 neurons:
(x,, fa(w), r).
The networks contain dropout layers with a 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 imput 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.
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 (Koenker & Bassett, 1978; Izbicki et al., 2020; Meinshausen, 2006; Jia & Jeong, 2022; Koenker & Hallock, 2001). Specifically, in our experiments with time-scries data we minimize the objective function:
min M. Paj2 Pole(Ye, + m--o//(Ye
where
a(y - 0) y 1-ン>0. (1 a1 v) otherwise.
Palv.0)
is the pinball loss. Since the data points arrive sequentially, formulate M, an LSTM model and minimize the above cost function in an online fashion follows. Given new labeled test point (X,, Yi), we (i) compute the pinball loss both for the lower and upper quantiles, i.e., Pa/2 Da/2(Yi, (,,, and Pi-a/2(Y,, Mr(x,, - a/2)), respectively; and (ii) update the parameters of the LSTM model Me by applying a few gradient steps with ADAM optimizer. Appendix C.1.1 provides more details on the network architecture.
C.1.3 Hyperparameters Tuning
For both real and synthetic data sets, we examined all combinations of the raw model's hyperparameters (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 12001-16000. The combinations we lested are presented in Table 1. Some of the configurations required more than 11GB of memory to train the model, so we did not consider them in our experiments. The chosen configuration was later used for choosing the calibration's 's learning rate 7: 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, visualized in Figure 8 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 for the calibration schemes are E {0.005, 0.01, 0.05, 0.2,0. 0.5, 1,2, 10). The calibrations' hyperparameter configurations were tuned using SMAC3 library (Lindauer al., 2022), with 'n trials' parameter set to 50, follows. First, for ACI and Rolling RC applied to control the miscoverage loss considered only the hyperparameters that attained coverage rate that is close to the nominal level by at most to 0.005. Among those configurations, we chose the one that minimized the following objective:
(1 msl 1/(1 - -a)l) length.
20

---

Published in Transactions on Machine Learning Research (11/2023)
Above, msl is the average miscoverage streak length, formally defined in E.1, a is the nominal miscoverage level, and length is the average interval length, evaluated on the validation set. For Rolling RC applied to control the miscoverage counter loss, we chose the hyperparameters that achieved the narrowest intervals with a miscoverage counter which is close to the nominal lovel by up to 0.005. In Appendix C.4 we describe the hyperparameters examined for the stretching functions.
Table 1: Hyperparameters tested for the learning model
Paramoter
Options
fi LSTM input layers [32], [32, 64], [32, 64, 128]
f2 -LSTM layers
[64], [128]
fs -LSTM output layers
[32], [64, 32]
learning rate
10-4, 5 10
C.2 The Depth Prediction Setup
C.2.1 Data Set and Augmentations
We used the KITTI data set which contains pairs of a colored (RGB) image (Geiger 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. both cases, we augmented the colors of the RGB image and blurred il, as described in (Yin et al., 2021). Notice that the augmentations are deterministic during inference and random during training. Therefore, the augmentations augmentations is to improve the model's training.
chosen randomly in cach trial. The main purpose of these
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://cloudstet pre-trained network was not fitted on the KITTI data set used in our experiments. We fitted the model offline on the first 6000 samples for 60 epochs, to obtain reasonable model. Then, passing time step 6001 we start training the model in an online fashion while applying the calibration procedure. Next, we used the validation set, indexed by 6001 to 8000 to set the hyperparameter configuration. Lastly, we measure the performance of the deployed calibration method on data points corresponding to time steps 8001 to 10000.
aarnet. edu. au/pLueE///1TTJBBAVVGH...S This
C.2.3 Training The Uncertainty Quantification Models
For each uncertainty quantification model presented in Section B.2, we used a 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 an online fashion at timestamps 6001 10000, as mentioned in Section C.2.2.
C.2.4 Depth Example Setup
In this section, we describe the sctup 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 al., 2021) as the base depth prediction model. The model's predictions were calibrated by Rolling RC, with the design choice for given in Section 9. The
21

---

Published in Transactions on Machine Learning Research (11/2023)
uncertainty heuristics 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-inage's implementation of optical flow. We set the parameter 'num iter' to 2 and the "num _aapp'_rrp'pp 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 0. The only hyper-parameter we tuned in this experiment is the calibration's 's learning rate y which we tuned Appendix C.1.3. Specifically, we examined
the following way. We tuned the learning rate 7 as explained the following learning rates: y E {0.005, 0.01, 0.05, 0.1, 0.2, 0.5, 1, 10} and chose the y that achieved the narrowest intervals among those with coverage close to 80% by at most 0.2% the validation set. The validation samples correspond to timestamps 6001 to 8000.
C.2.5 Calibration Setup
In this section, provide more details about the setup used in the online depth estimation experiment presented in Section 4.2. We followed the experimental protocol described in Section C.2.4 except for the tuning of 7. When Rolling RC is applied to control multiple risks, the learning rate I is a vector, so examine all possible choices of 7-.2² E {0.005, 0.01, 0.05, 0.1, 0.2, 0.5, 2, 10), using the SMAC3 library (Lindauer et al., 2022). For single risk controlling, we chose the configuration that attained the smallest intervals out of those with an image coverage rale that is close to the nominal level by up to 0.2%. For multiple risks controlling, we chose the hyperparameters that achieved the narrowest intervals among those with coverage greater than 79.8% and center failure rate lower than 11%. These calculations were evaluated on the validation samples that correspond to timestamps 6001 8000. In this experiment, we A in (9) to be the maximal value in the vector f.- That is, we used the 'max aggregation' described in Section D.3.1.
C.2.6 Implementation 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 unknown scale and shift (Li et al., 2022b; Yuan et al., 2022; Li et al., 2022a). That is, an ideal model M satisfies that for every X, E X' there exist px, E R such that:
o.M(Xx) + pe Yy.
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 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 it and assume that their depth is given along with X,. Next, we obtain the learning model's output M(X,) and apply least squares polynomial fitting to compute the estimated scale füe and shift â. Finally, we produce the following depth estimate:
= Gx + P..
(11)
Throughout this paper, we consider the quantity in (11) as the output of the depth model M.
We utilize the sparse ground truth depth map to correct the estimates of the uncortainty houristics as well. Recall that the residual heuristic from Section B.2.2 produces an estimate f(X,) for the residual [Mm.((x)) - Yil, where M(X)) is the scaled model's prediction. We compute the scale and shift for the residual's prediction via polynomial fitting, and output the scaled residual, as in (11). Similarly, we 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 are pixels with depth that is too small (below 10-3), 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 given image.
22

---

Published in Transactions on Machine Learning Research (11/2023)
Lastly, throughout the depth prediction experiments we used the following formulation of the exponential stretching function for Rolling RC:
E - 1,
x > 0.1,
(x)
I
0.. 1 r 0.1,
+1,
x < 0.1.
Notice that this stretching function is the identity function around 0, and therefore it updates pp(() gently when the calibration is mild (6, is close to 0), and faster (exponentially) as the calibration is more aggressive (0, 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 excceds the lower bound we return the empty set. By outputting the full label space, we can guarantee control the risk any user-specified level, as the full label space is assumed to altain loss lower than the nominal level. In practice, however, we do not expect 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 10, similarly to ACI. For regression problems, it depends on the interval constructing function f. 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 0 is bounded in this range, in ACI. If the intervals are constructed in the Y scale, according to Section 3.2 of the main text, we 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 0
The recommended way to set the initial value of 0 depends on the design of the interval constructing function f: for example, for the interval constructing function in Y scale, presented in Section 3.2 in the main text, we set the initial f to zero as this is the right choice for model that correctly estimates the conditional quantiles. If the model is inaccurate, 0 will be updated over time, in way that guarantees that the desired long-range coverage will be achieved.
C.3.3 The Learning Rate 7
In this section, we analyze the effect of the learning rate on the performance of the calibration scheme. Figure 7 presents the results of our Rolling RC with a linear stretching function applied with different step-size y 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 7 on the performance. Following that figure, obscrve that by increasing y we incrcase the adaptivity of the mothod to changes the distribution of the data, indicated by the MSL. Recall that (i) the lower the MSL the smaller the average streak of miscoverage events; and (ii) the MSL for the ideal model is s 1.11. On the other hand, the improvement in MSL comes at the cost of increasing the intervals' lengths: observe how the largest results in too conservative intervals, as their MSL is equal to 1.
To set a proper value for y in regression problems, we suggest evaluating the pinball loss of the calibrated intervals, using a validation set. With this approach, one can choose the value of y that yiclds the smallest. loss. We note that our method is guaranteed to attain valid coverage for any choice of ?, so the trade-off here is between the intervals' lengths and faster adaptivity to distributional shifts.
23

---

Published in Transactions on Machine Learning Research (11/2023)
90.4
90.2
150
90.0
125
89.8
length
100
89.6
89.2
89.0
y=0.01
y-0.025
y-0.05
y-0.1
y-0.15
Y-0.2
y-0.35
y=0.01
y=0.025
y=0.05
y=0.1
y=
y=0.2
v=0.35
1.3
1.2
1.1
1.0
y=0.01
y=0.025
y=0.05
y=0.1
y=0.15
y=
0=3.
Figure 7: Rolling RC with linear stretching applicd to control the 0-1 loss at level 10% with different learning rates on the synthelic described in Section C.6.1.
C.4 The Hyperparameters for the Stretching Functions
As explained in Section C.1.3, we used SMAC3 library (Lindauer et al., 2022) to set the hyperparameter configuration. The hyperparameter values we examine for the 'score adaptive' and the 'crror adaptive' stretchings are summarized in Table 2.
Table 2: Hyperparameters tested for the stretching function
Parameter
Options
gacore
[0.01, 2]
gloss
[0.01, 2]
glow
[-1,0]
ghigh
[0,1]
exponential stretching base
[0, e,
C.5
Machine's Spec
The resources used for the experiments are:
CPU: Intel(R) Xeo E5-2650
GPU: Nvidia titanx, 1080ti, 2080ti.
OS: Ubuntu 18.04.
24

---

Published in Transactions on Machine Learning Research (11/2023)
C.6
Data Sets Details
C.6.1
Synthetic Data Set
In this section, we define a synthetic data set that we use in our ablation study, First, we define a group indication vector, denoted as gr:
mi 2 3ma 4T
where w is a vector the number w repeated n times, is a concatenation of two vectors, m, ~ (500, 10?) and N(H, o²) the normal distribution with mean and variance o². In words, each group lasts for approximately 500 time sleps, and the vector concalenation 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)",
B,
8.
44 ((20,,0),,
9t = mod 2, otherwise,
1.
Xe ~ (0, 1),
8t ~ 1)0,
Y 2 Yi-1+ wg. Xi 22nn Et);
where Uniform(a, b) is a uniform distribution on the interval (a, b).
C.6.2 Real Data Sets
In addition to the features given in the raw data set, we added for each sample the day, month, year, hours, minutes, and the day of the week. Table 3 presents the number of samples in each data set, the number of samples used in the quantile regression experiments 4.1.2, and the dimension of the feature vector.
Table 3: Information about the real data sets.
Data Set
Total Number Samples
Number of Used Samples
Feature Dimension
power (Power)
52416
20000
11
energy (Energy)
19735
19735
33
traffic (Traffic)
48204
20000
wind (Wind)
385565
20000
6
prices (Prices)
34895
20000
D Additional Experiments
D.1
Single Response Quantile Regression
D.1.1
Ablation Study on the Stretching Function
In this section, 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)
(x))
25

---

Published in Transactions on Machine Learning Research (11/2023)
Exponential.
E - 1, I x> 0, -e- +
1, I S
Score adaptive. The following stretching function makes larger update to 0, 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 et al., 2019) by
max (ax Y,,Y, M,,,, a/2)))
which measures the signed distance of Y, from the its closest boundary. Next, define
Pt
Soore (0) 4 (x)
(0) + A where Apcore clip(>;-r gacore St- glow ghigh).
where gecore Blow and ghigh are hyperparameters. Similarly to the 'error adaptive' stretching function presented in Section 3.2.1, the clipping function used to restrain the effect of an outlier Y, that far from the boundaries.
Error adaptive. By adding awareness previous points' loss to the 'score adaptive' stretching, we forge a stretching function that aware of both the error margin and the constructed intervals' loss:
(0) = (0) Aerror where Xerror clip(A gscore 8t-1 1.1-00 eep (gloss 1 - r13 glow ghigh).
The idea behind the 'error adaptive" stretching is to take into account also the quality the interval: an interval with a good (poor) quality requires a moderate (aggressive) adjustment. Here, the interval quality is quantified using its non-conformity score and the error margin. This way, intervals with high score score/error /error are updated quickly, which leads to faster adaptation to distributional shifts. Furthermore, the parameter À is clipped to prevent extreme corrections to (0)).
Figure 8 displays the performance of Rolling RC aiming to control coverage rate at level 1 - = 90% with the stretching functions described above, and Figure 9 presents the results of Rolling RC applied to control the MC risk at level a/(1 a) = 1/9. Following these figures, we can 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.
Tt achieves MSL 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 the desired level 0.111... when aiming 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 F.2).
Rolling RC with 'error adaptive' stretching performs similarly to the competitive stretchings in terms of ACoverage.
D.1.2 Constructing Uncertainty Sets With Calibration Set
In this section, we analyze a vanilla instantiation of ACI (Gibbs & Candes, 2021), which we refer as calibration with cal that constructs uncertainty sets with a controlled miscoverage rate using a calibration set. It is more out-of-the-box because it allows the user to take any conformal score function from the
26

---

Published in Transactions on Machine Learning Research (11/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
power
wind
Dataset
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
MSL
1.2
1.1
energy traffic
prices power Dataset
wind
Figure 8: Performance of Rolling 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 set 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 0 to 100.
27

---

Published in Transactions on Machine Learning Research (11/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
power
wind
Dataset
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
Σ
1.2
1.1
energy traffic prices power wind Dataset
Figure 9: Performance of Rolling RC on real data sets, where we aim to control the MC risk at level a<(1 a) = 1/9. The length of the prediction intervals is scaled per data set 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 0 to 100.
28

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm calibration with cal
Input:
Data {(X,, 1))T S X'X, given as a stream, miscoverage level a E (0, 1), score function S, calibration set size 02, a step size y > O, and an online learning model M.
Process:
1: Initialize ag = a and a set of the previous conformity scores: Seal = 0.
2: for t I..,, do
Construct a prediction set for the new point X₁:
Che (X.) -y) ((M(()))))) & (Scaa()
4:
Obtain Y,
Compute the current conformity score: 8 = ((M, Vt). Add the current conformity score the set: Seal Seal { Remove the oldest calibration point from the set: Scal Scal 1 Compute err, 1(2 & (()(),)
8:
9:
Update 0++1 = O4 + 7(a err.).
10: Fit the model M2 on (Xe, Yi) and obtain the updated model Me+1-
11: end for
Output:
Uncertainty sets (X,) for each time step E TT.
conformal prediction literature to get confidence set function f. Many conformal scores have been developed and extensively studied, so this approach directly inherits all of the progress made on this topic. calibration with cal uses calibration points, but does not hold out a large block. Rather, previous points are simultaneously used both for calibration and model fitting.
Turning to the details, denote by (X,), Y2) the model's prediction Mr.).) time and the corresponding label Y,, and returns 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 score presented in (Romano et al., 2019) are given by (X,) Y2) max(M,(X,, - Y,, M,,M,,,1111 ac/2)). Next, define the prediction set constructing function in (4) as:
non-conformity score function that takes as an input
f(X,, 8,, M,) ty E V S(M, v) Q1+0, (Sca)))
(12)
where Scal = (X(), Yx) .,, 1} is a set containing the n most recent non-conformity scores. The function Q1+0, (Saa)) returns the (1 + 0,)-th empirical quantile of the scores in Seal, being the [(1 + (n)(n + 1)] largest element in that set. Here, -1 < O: I 0 is the calibration parameter we tune recursively, in (5). The reason for having the negative sign, is to form larger prediction sets O increases. In plain words, f in (12) returns all the candidate target values y for the test label, whose score S(MM((X)).) is smaller than (1 + 0z) x 100% of the scores in Stal, which are evaluated on truly labeled historical data (XM) As such, the size of the set in (12) gets smaller (larger) as 1 + 02 gets smaller (larger).
For reference, calibration with cal procedure is summarized Algorithm 2. The reason for this method's name is to emphasize that we now use calibration scores to formulate the prediction set function f. In fact, the coverage guarantee of calibration with cal follows directly from Theorem 3.1 for s(Xe, Mc) defined in (12).
We run an uncalibrated learning model, Rolling RC with 'crror adaptive' stretching, as described in Section 3.2.1, and calibration with cal, as presented in Algorithm 2 on the real data sets detailed in Appendix C.6.2. Figure 10 summarizes the results, showing that Rolling RC and calibration with cal attain the desired coverage level, as guarantcod by Thcorem 3.1, while the naive approach does not. This figure also shows that Rolling RC with 'error adaptive' stretching constructs the narrowest intervals with the best conditional coverage metrics.
29

---

Published in Transactions on Machine Learning Research (11/2023)
90
Miscoverage counter
0.6
Coverage
85
Method
0.4
80
Naive
ACI
75
0.2
RRC (Error)
energy
traffic
prices Dataset
power
wind
energy
traffic
prices Dataset
power
wind
Average length (scaled)
1.4
ACoverage
4
1.2
1.0
0.8
energy
traffic
prices Dataset
power
wind
energy
traffic
prices Dataset
power
wind
2.0
MSL
1.5
1.0
energy
traffic
prices Dataset
power
wind
Figure 10: Performance of the uncalibrated outputs Naive (green), calibration with cal (Algorithm 2) (red), and Rolling RC with 'error adaplive' stretching (blue). All methods are applied to control the coverage rate at level a = 90% Results are evaluated on 20 random initializations of the predictive model. The ACoverage metric is scaled between to 100.
30

---

Published in Transactions on Machine Learning Research (11/2023)
80
Image coverage
Average length
90
Method
60
RRC
85
RRC (multi)
40
80
20
const.
resid.
flow prev. resid.
const.
resid. flow prev. resid.
Uncertainty Quantification Heuristic
Uncertainty Quantification Heuristic
Center coverage
85
Center length
35
80
30
75
25
70
20
const.
resid. Uncertainty Quantification Heuristic
flow prev. resid.
const.
resid.
flow prev. resid.
Uncertainty Quantification Heuristic
Center failure rate
30
20
10
const. resid. flow prev. resid.
Uncertainty Quantification Heuristic
Figure 11: Performance of Rolling RC applied to control only the 'image miscoverage' risk (orange) or both 'image miscoverage' and 'center failure' risks (blue). The underlying uncertainty quantification heuristics are: 'constant value' (const.), 'magnitude of the residual' (resid.), and 'previous residuals with optical flow registration' (flow prev. resid.), which described in Section B.2. All methods the exponential stretching function introduced in Section 3.2.1.
D.2 Uncertainty Quantification for Online Depth Estimation
In this section we analyze the performance of the uncertainty quantification heuristics described Section 3.2.1. We follow the experimental protocol explained in Section C.2.4, and display the results in Figure 11. This figure shows that all heuristics attain the desired risk levels level, as guaranteed by Theorem 3.1. Furthermore, the average length and center coverage metrics suggest that estimating the residual based residuals at previous timestamps outperforms the other heuristics. We propose two possible explanations for this phenomenon. First, since the residual magnitude model's architecture is huge, it may require further oflline fitting, on a larger data set. For comparison, we trained it for 60 epochs on 6000 samples, while the base depth prediction model, LeReS (Yin al., 2021), was trained over 300k samples. Socond, the problem of estimating a residual map equivalent to estimating depth map which known to be difficult (Jung Ho, 2010). As consequence, the residual estimates produced by the network may be inaccurate.
31

---

Published in Transactions on Machine Learning Research (11/2023)
D.3 Multiple Response Variables
D.3.1
The Aggregation Functions
In this section, we propose two options for aggregaling the vector D, into a scalar through Ae:
Mean. A (x(()) + p())). Taking the average of the entries compromises between the different risks and results in intervals that not too conservative and not too liberal.
Max. X max (x(()), s0 (()).. Since the maximal coordinate corresponds to the most conservative loss, the constructed intervals may be too conservative.
The third possible aggregation is the minimum function Xp = min(0,) that consistently follows the minimal entry in L. Since the minimal coordinate in 0 corresponds to the most liberal loss, this approach is likely to result in intervals that are loo liberal, as it ignores the conservative losses. Therefore, we do not consider this aggregation in our experiments.
D.3.2 The Stretching Function
In this section, we examine a natural baseline for the depth estimation task: Rolling RC without a stretching function. We evaluate the conditional validity using two new conditional coverage metrics. The first is the Center Acoverage, which is defined the average distance between the center coverage rate Pixel-wise
each timestamp and the total center coverage rate. The second metric, which we refer Acoverage, measures the average distance between all pixel coverage rates and the image coverage rate, where the pixel coverage is taken across the time horizon. For both metrics, a lower quantity indicates a better conditional validity.
We follow the experimental protocol Section 4.2 and apply Rolling RC to control only the 'image miscoverage" risk (2) at level 20% (single risk) or to control both the 'image miscoverage' and the 'center failure' (7) risks levels 20% and 10%, respectively (multiple risks). Figure 12 displays the results of both the vanilla Rolling RC (without stretching) and Rolling RC with the exponential stretching. This figure indicates that Rolling RC achieves valid risk with either stretching function, guaranteed by Theorems 3.1 and 3.2. Furthermore, this figure reveals that while the vanilla Rolling RC constructs narrower intervals, applying the exponential stretching leads to improved conditional coverage, as indicated by the conditional validity metrics. This experiment suggests that powerful stretchings can be used to improve the conditional validity of the constructed uncertainty sets.
E
Time-SSries Conditional Coverage Metrics
E.1 Average Miscoverage Streak Length
Following Section 4.1.1, recall that the miscoverage streak length of a series of intervals (Cx(X.))): is defined
as:
MSL := Σ
minfé: Ye++ E (++i(Xet)) or trt t=
TET
where I is a set containing the starting times of all miscoverage streaks:
I f t [To Ti): (t= To or Y-- E ((-((1-1)) and Y, & C(()))
Above, [Tb. Ti] the set of all integers between Tj and Ty.
To clarify this definition of the MSL, we now analyze the MSL in two concrete examples. Denote by "1" a coverage event and by "0" miscoverage event, and consider a sequence of 15 observations. A method that results in the following coverage sequence:
1, 1. 1, 1
1,
0,
0.0, 1, 1,1,1,1,1111
32

---

Published in Transactions on Machine Learning Research (11/2023)
Image coverage
86
Stretching
id
Average length
32
30
exp
84
28
82
26
80
RRC
RRC
(multi)
RRC
RRC (multi)
Method
Method
Center fallure rate
20
Center Acoverage
16
15
:
14
10
RRC
RRC (multi)
RRC
RRC (multi)
Method
Method
11
Pixel-wise Acoverage
10
9
8
7
RRC
RRC (multi)
Method
Figure 12: Performance of Rolling RC the depth estimation dataset without stretching (orange) with exponential stretching (blue). Results are evaluated 10 random initializations of the predictive model. The ACoverage metrics are scaled between O to 100.
has MSL (2 1)/2 1.5, and coverage 12/15 80%. By contrast, method that results in the following sequence
1,,
has the same average coverage of 80% but much larger MSL 3/1 = 3. This emphasizes the role of MSL: while the two methods the response in 12 out of 15 events, the second is inferior it has, 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:
P(Y C(X,) Xx x))=)))- = =1
Therefore, Z: = min(i: Dess C(X..)) or i Ti} is a geometric random variable with success probability a. The average miscoverage streak length of the true quantiles is the mean of Ze, which is:
MSL
2 1.111.
a=0.1
Therefore, having MSL is not necessarily equivalent to an optimal conditional coverage, as it indicates for undesired anti-correlation between two consccutive time steps: after miscoverage event follows a coverage event with probability one. Consequently, we would desire have MSL I-a which is the MSL attained by the true conditional quantiles.
33

---

Published in Transactions on Machine Learning Research (11/2023)
E.2 The Miscoverage Counter
How should one choose the risk level for the MC risk? If we aim al 1 - 90% coverage, argue that the right choice is = a/(1 a) = 1/9. To see this, suppose we have an ideal model that attains perfect coverage rate 1 - a conditional on t. In this case, the coverage events are i.id. realizations of Bernoulli experiments and so MC acts as a geometric random variable that counts the number of failures until reaching a success, where the success probability value of such a geometric random variable, which a/(1 - a... By Proposition 4.1 we know that if we control MC al level 1/9, the coverage will be at least 1 as 88.89%, where an ideal model will reach an 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.
- a. Hence, we define the risk level r be the expected
Note that Theorem 3.1 assumes that the loss is bounded, while MC is not bounded. To guarantee that Rolling RC will converge to the desired risk level of MC, we can use the following loss instead: MC² = min (MC, B} for some large N. In the experiments, however, we used the regular MC as we obscrved 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 in the feature vector. Therefore, we assess the violation of day-stratified coverage (Zaffran et al., 2022; Feldman al., 2021), as a 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 series of intervals (C)().)) their ACoverage is defined as:
ACoverage Σ
1
Σ 1 1x - a) LED:
iE(11......77
where Dj a set of samples that belong to the i-th day of the week. Since a lower value of this metric indicates for a better conditional coverage, we desire have a minimal ACoverage.
F Calibrating on the Quantile Scale In Regression Tasks
As an alternative for (6), where the calibration cocfficient ((0,) added to each of the interval endpoints, one can modify the interval's length by tuning the raw miscoverage level T. = (0,,) requested from the model:
0,,
(,,(X,, Me(X,, - r./2)]-
This formulation is inspired by the work of (Chernozhukov et al., 2021) that suggested tuning the nominal miscoverage level т, based on a calibration set. In contrast to (6), where we estimale only the lower a12 and upper - aa/2 conditional quantiles, here, we need to estimate all the quantiles simultaneously. To accomplish this, one can apply the methods proposed in (Park et al., 2021; Chung et al., 2021; Sesia & Romano, 2021). Turning to the choice of the stretching function şo the straightforward option is set p(0) = -T, where is bounded in the range: -1 < 0, < 0. The reason for having the negative sign in yo, is to form larger prediction sets (resulted by smaller values of T) as 0 increases.
G Constructing Prediction Sets for Classification Tasks
Consider a multi-class classification problem, where the target variable discrete and unordered y E (1,2, K). Suppose are handed classifier that estimates the conditional probability of PY,x, (Y, y X; = æ) for each class y, i.c., MM(X,, v) [0, 1] and Eyey Mr(Xe, y) 1. With this in place, we follow (Papadopoulos et al., 2002) and define the prediction set constructing function
f(X,, 0r, Mi) (u: M. 2 p(0)),,
(13)
34

---

Published in Transactions on Machine Learning Research (11/2023)
where one can choose (p(x) = -z, for instance. While this procedure is guaranteed to attain the pre-specified risk level according to Theorem 3.1, the function f in (13) may have unbalanced coverage across different. sub-populations in the data (Cauchois et al., 2021; Angelopoulos et al., 2021b). To overcome this, we recommend using the function ff presented next, which is capable of constructing prediction sets that better adapt to the underlying uncertainty. The idea, inspired by the work of (Angelopoulos al., 2021b; Romano et al., 2020), is 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 a. Formally, the confidence set. function is defined
2 -p((p))))))) }.
Mi, = (TI,-.., Tk), where l: inf k Σ (;))
and ıt is the permutation of (I sorted by the scores {M, y) :t E )) from the highest to lowest. As for the stretching function yp, recommend using ((x) z.
35


Reviews:
[{"review_id": "GbJp8xmxjs", "reviewer": "Reviewer_UR7h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The question is natural and well-motivated. \n- This work extends the techniques in ACI to more general losses than the 0/1 loss.\n- The proposed method is general and simple, since it can be used in a black-box fashion with any online learning algorithm. \n- Rolling RC is effective at controlling single and multiple risks in the given experiments. \n\nWeaknesses:\n- The technical contribution on the theoretical side appears to be marginal, building on prior results by Gibbs & Candes. \n- As stated, there are many ways to instantiate rolling RC, using different stretching functions. However, there are no specific guarantees for individual stretching functions. It would make sense for them to behave differently, and would be helpful to characterize which stretching functions are best for what type of problems. \n- For the experiments, the method’s hyperparameters are chosen based on a validation set. However, I’m wondering, if the data distribution changes in an online fashion, would the hyperparameters potentially need to change as well? \n- There is no baseline for the online image-depth estimation problem.\n- There is no comparison for the performance of rolling RC and prior methods on i.i.d distributed data. Does rolling RC perform just as well, or is there a tradeoff?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a general method for provably controlling user-defined risks in an online setting. This method constructs uncertainty sets at each time step such that the average risk converges to the user-defined risk level. The method is general in the sense that it can be implemented in a black-box manner for any underlying online learning algorithm. Furthermore, this method can be composed to provably control multiple risks under certain conditions. Finally, authors demonstrate that the method outperforms existing methods in practice on both tabular data, and for an online image-depth estimation problem. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- To control multiple risks, the risks need to satisfy a certain type of “independence” condition. Are there situations where this condition is not satisfied? It would be helpful to understand the limitation of controlling multiple risks with rolling RC.\n- It would be helpful to provide some explanation on how the error adaptive stretching function is constructed (in words), and why it is effective.\n\nTypos:\n- Theorem 3.1: what is B?\n- Theorem 3.2 proof: M_i instead of M?\n- Figure 6 caption, where is the green graph?\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qmZ6lbuDv6", "reviewer": "Reviewer_6qPw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The proposed RRC looks technically solid and sound for handling the risk control in non-IID settings\n2. The technique itself is very simple and straightforward for the applications in an online manner\n3. The extension from single risk to multiple risk makes the proposed RRC more generalizable in different scenarios\n4. Theoretical results presented in the paper provide a solid foundation of the proposed scheme\n5. The experimental results look promising and effectively validate the RRC\n\nWeaknesses:\n\n1. The motivation of using ACI in the RRC is not very clear\n2. What is the computational complexity of the RRC if it involves a very large model in an online manner? \n3. What is the quantitative impact of the distribution shift on the RRC performance? Any theoretical results on this?\n4. It would be better to see more empirical results in the classification task. Basically, the authors may need to use a couple more real-world datasets to make this part of results more convincing\n5. Please define properly all the notations in the theorem statements\n\n***************************************\nAfter carefully reviewing the rebuttals and comments from other reviewers, I recommend the acceptance for this work. However, the authors should make sure that the mentioned changes after addressing all comments from different reviewers are included into the final version to make it more technically sound and solid.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. Proposed a new algorithm called rolling risk control,  the first calibration procedure to form prediction sets in online settings\n2. Leveraged adaptive conformal inference to construct prediction sets for any arbitrary time-varying data distribution\n3. Extended the propose technique to control multiple risks and construct sets that are valid for all given risks over long-range windows in time\n4. Presented theoretical guarantees and promising empirical results to test the proposed techniques", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses above to make the corresponding changes.", "broader_impact_concerns": "Please add some discussion to the paper for the limitations of the proposed method and its societal impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jSL21Ual1v", "reviewer": "Reviewer_htjH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results in this paper appears to be solid and new to me.\n\nThe paper is easy to read. For example, the algorithm block is clearly shown. The figures and results are clearly and nicely presented.\n\nThe theoretical guarantees are provided and the proofs are shown.\n\nThe paper is well structured.\n\nAlthough the technical part may not be challenging, it is not a concern for this venue. This paper definitely meets the requirement of TMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a framework for constructing uncertainty sets that provably control risk for online learning models. Such a framework extends conformal prediction.\n\nFurthermore, the extension of the approach to control multiple risks simultaneously is shwon. \n\nMany experiments on real-world tabular time-series data sets and nice figure are presented.\n\nThe authors also provide theoretical guarantees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "good as is", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a practical method for controlling user-defined risks in online settings. While the theoretical contributions are considered somewhat marginal, the paper's strength lies in its applicability in real-world scenarios. Some reviewer raises concerns about the lack of guarantees for individual stretching functions and the adaptability of hyperparameters to changing data distributions. The authors provided proper response, and the reviewer accepted the response. The paper is recommended for acceptance, but the authors should make sure that the mentioned changes are included into the final version.
Decision: Accept (poster)