Online Conformal Prediction via Online Optimization
Authors: Felipe Areces
Christopher Mohri
Tatsunori Hashimoto
John Duchi
Venue: ICML 2025 poster (2025)
Keywords: conformal prediction
online conformal prediction
stochastic convex optimization
stochastic gradient descent
uncertainty quantification
Primary area: optimization
TL;DR: We introduce a family of algorithms for online conformal prediction with coverage guarantees for both adversarial and stochastic data.

Abstract: We introduce a family of algorithms for online conformal prediction with coverage guarantees for both adversarial and stochastic data. In the adversarial setting, we establish the standard guarantee: over time, a pre-specified target fraction of confidence sets cover the ground truth. For stochastic data, we provide a guarantee at every time instead of just on average over time: the probability that a confidence set covers the ground truth—conditioned on past observations—converges to a pre-specified target when the conditional quantiles of the errors are a linear function of past data. Complementary to our theory, our experiments spanning over $15$ datasets suggest that the performance improvement of our methods over baselines grows with the magnitude of the data’s dependence, even when baselines are tuned on the test set. We put these findings to the test by pre-registering an experiment for electricity demand forecasting in Texas, where our algorithms achieve over a $10$\% reduction in confidence set sizes, a more than a $30$\% improvement in quantile and absolute losses with respect to the observed errors, and significant outcomes on all $78$ out of $78$ pre-registered hypotheses. We provide documentation for the pypi package implementing our algorithms here: \url{https://conformalopt.readthedocs.io/}.

Online Conformal Prediction via Online Optimization
Felipe Areces Christopher Mohri 22 Tatsunori Hashimoto John Duchi 13
Abstract
ing a predictor that can always guarantee its accuracy is more than snipe hunt. Instead, however, we might seek an appropriate (and dynamic) level of confidence in our predictions, even in the face of changing data processes. Even more, we ought to develop procedures that can provide such guarantees in arbitrary settings, so that we do not rely on (likely invalid) modeling assumptions, but which can in fact do the "right thing," adapting to underlying structure when it exists. To address these desiderata, this work adopts and adapts online conformal prediction, providing predic- tive confidence sets for which, over time, a pre-specified fraction covers the ground truth, even if data is adversarial.
We introduce family of algorithms for on- line conformal prediction with coverage guar- antees for both adversarial and stochastic data. In the adversarial setting, we establish the stan- dard guarantee: over time, pre-specified tar- get fraction of confidence sets cover the ground truth. For stochastic data, we provide guaran- tee at every time instead of just average over time: the probability that confidence set covers the ground truth condi-onnitionee on past observa- tions-convedd to a pre-specified target when the conditional quantiles the errors are a linear function of past data. Complementary to our the- ory, our experiments spanning over 15 datasets suggest that the performance improvement of our methods over baselines grows with the magni- tude of the data's dependence, even when base- lines are tuned on the test set. We put these findings to the test by pre-registering an exper- iment for electricity demand forecasting in Texas, where our algorithms achieve over 10% reduc- tion in confidence set sizes, more than 30% improvement in quantile and absolute losses with respect to the observed errors, and significant out- comes on all 78 out of 78 pre-registered hypothe- ses. We provide documentation for the pypi pack- age implementing our algorithms here: https: //conformalopp lopt. readt hedocs. io/.
Current algorithms for online conformal prediction resem- ble bang-bang controllers from control theory, which switch between two extreme states to achieve desired behav- ior. The first algorithm to propose this approach, Gibbs & Candès's ' Adaptive Conformal Inference (ACT) 2021, con- structs confidence sets using a single parameter that governs their level of conservativeness. The update rule for this pa- rameter is simple: on an error, increase the parameter by a constant, and otherwise, decrease by (another) constant, inducing bang-bang behavior. Existing theoretical analy- ses for ACI suggest making these switches aggressive as possible to obtain the tightest coverage. Several works have extended ACI by adaptively tuning the magnitude of these updates (Gibbs & Candès, 2024; Zaffran et al., 2022; Bhatnagar et al., 2023) or with more sophisticated update nules that, that for example, incorporate other aspects from control (Angelopoulos al., 2023; Yang et al., 2024), but all fundamentally share the same bang-bang backbone.
This purely adversarial approach overlooks the possibility of achieving stronger guarantees under more predictable data. In this work, we show that directly modeling the distribution of errors can provide both new theoretical guar- antees and empirical benefits. Our key observation that we can develop algorithms that not only satisfy the standard adversarial guarantees, but also achieve time-conditional coverage guarantees for stochastic data by solving stochas- tic optimization problem. These tine-conditional coverage guarantees ensure that we eventually achieve the target cov- erage level at all times, instead of only when averaged across time. While we are not the first to depart from purely ad- versarial guarantees- ppttt work considers the i.i.d. setting (Angelopoulos et al., 2024) we provide guarantees for
1. Introduction
would be unreasonable to presume that a predictive model would maintain its accuracy new scenarios arise, individuals modify behavior-so seek-
change,
Eqqual contribution 'Department of Electrical Engineering, Stanford University, Stanford, USA 'Department of Computer Science, Stanford University, Stanford, USA 'Department of Statistics, Stanford University, Stanford, USA. Correspondence to: Felipe Areces <fareces wwwe@essttoooorurr..se Christopher Mohri <xmohri stanford.edu>>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Conformal Prediction via Online Optimization
general class of standard stochastic processes that exhibit dependence across time, such autoregressive processes.
2. Preliminaries
The goal of online conformal prediction is to generate confi- dence sets in an online fashion. In this setting, we sequen- tially observe covariates X; E X' and wish to construct confidence sets C2: X = y for the labels Y; E y.
Our theoretical results show the benefits of this approach across three main settings. In the first, we show the stan- dard adversarial guarantee that over time, a pre-specified fraction of our prediction sets contain the true label. That is, in the worst-case setting where an adversary hand-picks the data, we still satisfy the same general guarantees as in past work. In the other two, we consider stochastic data. We first prove that when our model for the underlying errors is well-specified, we get cime-conditional coverage guaran- tee. The byproducts of these guarantees are new theoretical results for strongly convex stochastic optimization, where we develop convergence guarantees for stochastic gradient methods that operate with dependent data. In the second setting, where model is mis mis-specified but ergodic stochastic process generates the data, we show the conver- gence of our algorithms to the minimizer of an expected loss with respect to the stationary data distribution. Here, we extend past results on convex optimization with ergodic data (Duchi et al., 2012; Agarwal & Duchi, 2013) to last-iterate strongly convex settings.
We construct these confidence sets from a score function St X' x y + RR which may be learned and updated over time. The score function defines (X2) via the level sets
C((X,) = {y E y: s (x v) $ &g).
for some threshold @t. E R. The conformal confidence set makes an error at time t if the conformal score
S. : s Yi),
exceeds the threshold qr, which we formally define as emr, := L The task of the online conformal learner is then to choose the thresholds qe adaptively.
The validity guarantee typically sought in online conformal prediction is that of long-run coverage, which requires that for any pre-specified a E (0, 1), the algorithm makes an error roughly an a fraction of the time over T E N steps:
In addition to our theory, we empirically evaluate our pro- posed algorithms alongside existing ones. We first use sev- eral standard datasets in the online conformal literature, where we control the marginal coverage of all algorithms to make fair comparisons. In the spirit of truly testing our proposed algorithms, we also conduct a pre-registered ex- periment on period of electricity consumption data in Texas. There, record our hyperparameter choices and experiment design before the data is available. Across all 18 datasets, our algorithms never perform discernibly worse than baselines (even after tuning baseline hyperparameters on the test set), and consistently outperform them when- ever the data exhibits strong linear dependence (which we measure in terms of autocorrelation of the first lag).
em, a = o(1)
(I)
T
even when the data is adversarial. This is, however, weak notion of validity, as the individual confidence sets C2 need not satisfy any non-trivial coverage guarantee. In fact, one could disregard the data and satisfy the guarantce (1) by alternating between q = oo and qt -oo, in which case the sets are either (X,) (x,) = Y' with trivial full coverage. A stronger guaran- tee, which would give a real sense of uncertainty at time t, would require that conditioned on the past, Cx(X,) con- tains Y, with probability 1 - a. This, of course, requires stochastic data.
0 with no coverage or
We summarize our contributions and the organization of the paper below.
Our main goal is therefore to develop algorithms that sat- isfy both this stronger conditional guarantee for stochas- tic processes as well as long-run coverage for adversarial data. More formally, when the covariate and label pairs {X,,, Y.)), are stochastic with canonical filtration {Fe) defined by F, = (X Y=)) )) we seek algorithms that satisfy the following consistency guarantee:
Section 3 presents a new algorithm for online conformal prediction, allowing for arbitrary parametric online con- formal predictors beyond sealars.
Section 4 develops adversarial guarantees, showing it always achieves long-run coverage (I).
Sections 5 and 6 develop stochastic guarantees, showing it attains conditional coverage when well-specified and relaxed conditional coverage when mis-specified.
P(Y: & C.(.)) Fi-1) -a =
(2)
Section 7 contains experiments on 17 datasets with a pre-registration to compare our method with existing al- ternatives and provide evidence of its empirical benefits.
for a general class of stochastic processes.
We defer all proofs to Appendix C.
To preface algorithms seeking this stronger coverage condi- tion, we briefly provide an equivalent characterization of (2) in terms of the conformal scores. Since Y, E C.(X.) e
2

---

Online Conformal Prediction via Online Optimization
a: 2 St, achieving (2) is equivalent to tracking the (1 11-a) a) conditional quantile of Ss Fi-1 defined
Algorithm 1 Batched projected online gradient descent
Input: 0₁ E Rd, batch size m. convex feasible set O learning rate schedule {
t. :- in E R: P(q 2 S: F(-1) 21 a)
for b = to B do
as long as these quantiles are unique. This property brings about a natural loss function for our problem: the (1 - a) quantile loss, which is defined as
for i = to m do
Predict threshold qb, (0))
Observe score So,
Quaaiite (r) (1 a) (r; 0) max(-r; 0}-
Compute gradient g t (0s,((0r)
end for
Update 0b+1 <- ITe (0s 7b
1 m Ei=1 Bi.s)
As first shown in Koenker & Bassett Jr. (1978), the quantiles of are the minimizers of the expected quantile loss:
end for
q = argmin [quantile (St - 4) Fr-1].
QER
3. Algorithms
We can thus achieve our goal (2) by minimizing this condi- tional loss, and we will use this equivalent characterization to develop online conformal algorithms.
Our online conformal predictors serve as estimators for the conditional quantiles qf so the core idea of our method is optimize their parameters via online gradient descent on the quantile loss (0) Lquanill (S, qr (0)) so to approach the the minimizers of its conditional expectation (() := (0) | Ft-1]- This procedure follows similar algorithmic principles as ACI but allows for arbitrary parametric online conformal predictors beyond scalars.
2.1. Definitions
We define our online conformal predictor at time t as a function q:: Xt-1 x yt-1 x R.. The predictor uses the
previous covariates X := ix and labels y ==
{=:)==1 to compute the threshold q: = 2e (x(-1, _ 0).
We present the framework of our proposed method in Al- gorithm 1, which performs a gradient descent step on the conformal predictors' parameter 0 E O after observing each batch of data. To simplify notation regarding batches, we use & to represent time f, and the tuple (b, i) to denote the i'th sample in the b'th batch. Our batch size is m, so time (b, is equivalent to time (b 1)m + When subscript appears on its own, it refers a quantity that is uniform across batch b.
We can update the parameter 0 E θ over time, and often use the simplified notation qr (0) == q: (x , 0).
The closed convex parameter set e defining conformal predictors } is well-specified for stochastic process {(X,, }. if a single parameter O represents all the con- ditional quantiles:
q. q
and asymptotically well-specifier if some parameters only satisfy this equality asympiotically, so that for 0* E O*
In the following examples, we instantiate some special cases of conformal predictors that can be used with Algorithm 1. Example 3.1. Scalar quantile tracking (SQT) (Angelopou- R and
sim lai q: (0))) 0.
In the asymptotic regime, our conformal predictors are also regular for any 0 E @ O) O*, lim inf lu; - 2e (+) | > 0
los et al., 2023): Choose
(0) = 0.
almost surely, and n--bouded if for a learning rate schedule
7 = {m Je and any 0* E O², Eie nela - q: (0*) < 0o
This model is well-specified when {Se}e are i.i.d. or all conditional quantiles qt are equal.
almost surely.
Many of our results apply to conformal predictors (-) with a bias term. In this case, for 0 E Ô C I and
Example 3.2. Scalar quantile tracking (SQT) scorecaster qe Choose Q IR and
e E IR such that 8 = cc] and all t e N. there exists by: x x D x θ + R satisfying
qe = 0 q:-
This model is asymptotically well-specified when (ûr - gi) converges to constant and fully well-specified when (g. fa--00 q:) is constant across all time. Since the conditional quantiles of not necessarily the same for all t as in Example 3.1, the scorecaster aims to predict the time de- pendence in the conditional quantile so that the differences (g. - 9;) are constant. In our experiment section, the model SQT+AR is of this form and fits qe as a quantile estimator for autoregressive (AR) models.
(0) = (0) c
We often also require these predictors to be bounded so that θ C {0 Id-1; Vt E N, (+)) K2) for Kg E (0, oo). In our experiments, we define conformal predictors using feature maps 4, x x y + Ed producing conformal covariates Z, = (X 1
-11 y(-1), so that (f) = 2, e: these are bounded if Z, and 0 have bounded Euclidean norm ||-
3

---

Online Conformal Prediction via Online Optimization
Example 3.3. Linear quantile tracking (LQT) of order
the parameter set @ is well-specified. We begin by showing this property asymptotically, and then provide finite sample rates characterizing the speed of convergence when suitably large batch sizes are chosen.
p: Choose Q RP+1, feature map (x y(-1)=
(S S.-p p. 1). and 2: (0) 0 (xi
For the remaining sections with stochastic data we always assume that our conformal predictor gr is linear its pa- rameter θ S R. so that qu (0) Q Z, for covariates Z (x ,Y--'> E Rd This implies that & is convex for all N. We also assume that these covariates have almost surely bounded norm sup, Zell < G so that our conformal predictor is G-Lipschitz.
This model is well-specified for AR processes of order at most p. and can be extended to richer feature vectors.
Our experiments focus on the models described above, but our framework is designed be flexible and allow for even more general conformal predictors. For example, given access to p N scorecasters (6 ) = we could extend Example 3.2 by choosing @ = (0, 1) x R and
For this section in particular, we make an assumption on the distribution of {S.}:t the conditional score distributions S, | Fi-1 have uniformly lower and upper bounded continuous densities ft in some s-neighborhood around their unique quantiles gf. More concretely, for all t: p S f((s if Is + e.
gr (0) T 1,,,,, :...: 1/.
Similarly to the SQT + scorecaster method, this variant would be well-specified if any of the scorecasters satisfy the conditions in Example 3.2 and enjoy regret bounds against the best predictor in hindsight with respect to the quantile loss immediately from classical online convex optimization results (Hazan, 2016). In particular, by choosing SQT pre- dictors with learning rates in a fixed grid scorecasters, we could obtain a conformal predictor that preserves long-run coverage and attains quantile loss at least as good as the best SQT predictor in that grid without the need for tuning.
While all of our stochastic guarantees apply to the existing SQT algorithm, they are stronger for the LQT algorithm; its larger parameter set @ well-specified more often and has minimizers 0+ O least as good, according any loss.
5.1. Asymptotic Consistency
The following result shows the consistency of Algorithm I under the weakest assumptions, where we require only asymptotic well-specification and non non-increasing learning rates du satisfying Σ 1/ and E 1/ co. We provide the proof in Section C.2 of Appendix C.
4. Guarantees under adversarial data
We first focus the setting where covariate and label pairs (X,, Yi) are adversarial. In this context, we show that by arguments similar to those in Gibbs & Candès (2021); An- gelopoulos et al. (2023; 2024), our algorithms satisfy the long-run coverage guarantee (1). We provide the proof in Section C.I of Appendix C.
Theorem 5.1. Let the assumptions in the previous para- graph hold, and assume that the conformal predictors have bias term, are asymptotically well well- vell-specified, regular, and n-bounded. Then the iterates O, produced by Algorithm I satisfy
Theorem 4.1. Let the scores St be almost surely bounded for any time t with sup, |Sa] <. Kg co and let {no be non-increasing sequence of learning rates. Then, for any bounded conformal predictor with a bias term initialized so that |es] < K₃ + Kr Algorithm I with batch size m and
Og 0.S. 000 E E
and attain the conditional coverage guarantee
B- = I almost surely satisfies
IP (Y: & Ct(X.)
8.a, a.
2m(Ks K2 + K, - m)) m -1 +
This consistency result also holds more broadly for confor- mal predictors that ensure that 4 convex for all with linear models being special case.
T err
TUB
T
This long-run coverage bound generalizes those in An- gelopoulos et al. (2023) and Angelopoulos et al. (2024) for SQT, as it allows batch sizes larger than and more complex underlying models.
5.2. Finite-sample Convergence
We will now provide finite-sample convergence rates for Algorithm 1. The two main challenges are the changing expected conditional loss L, (with expected subgradients that depends on the time f) and the lack of strong convexity or smoothness in the quantile loss.
5. Guarantees under well-specification
We now show that in addition to always satisfying the long- run coverage guarantee (1) for adversarial data, our algo- rithms achieve the conditional coverage guarantee (2) when
A key result for our convergence analysis is the following strong convexity lemma, which shows that the batched con-
4

---

Online Conformal Prediction via Online Optimization
ditional losses are large if our iterate 0 is far from 0* This is non-trivial, as each conditional loss La can have infinite number of minimizes, for example when Z, represents the last p 2 1 scores and has a bias term. We provide proof of this Lemma in Section C.3 of Appendix C.
Our result provides a data-dependent, last-iterate high- probability bound. To the best of our knowledge, it is the first sinite-sample convergence analysis for SGD that does not rely on stationarity or mixing, but instead assumes only the existence of a unique minimizer consistent across time.
Lemma 5.2. Let θ be well-specified with finite diameter D. For batch b, let X be the minimum eigenvalue of the sample covariance matrix th Ei=1 Zo, and let pa == pde min cTD 1.. Then, the conditional loss gap in batch b is lower bounded for any 0 E A:
This convergence resuls shows a trade-off in terms of learn- ing rate when compared to the long-run coverage bound in Theorem 4.1, As the learning rates decay quickly and ap- proach (1/tt). this bound tightens to fast (1//t), while the long-run coverage bound turns vacuous. On the other hand, as the learning rates approach (1), this convergence rate becomes vacuous while the long-run coverage bound strengthens to O(1/t). This suggests learning rate schedules with faster decay to achieve better convergence rates when the well-specified assumption holds. We will observe the same learning rate tradeoff in the following section, where we trade well-specification for mixing assumption on the data.
2
m Σ -0,,(00--,,1000' (0') 2
1010--010
The bound above is data-dependent and for our main con- vergence result, will need positive lower bound minse[B] [B] E[A, mm which ensures that the progress with each gradient step is lower-bounded. This requires an analysis of the minimum eigenvalues As, We provide an ex- ample lower bound for the weakly-stationaal AR(1) model iid St - + Et with |ø| 1 and zero mean E Ps. which we follow for most of our experiments, and prove it in Section C.4 of Appendix C.
6. Guarantees under mis-specification
Under mis- specifieciii,,,nnn the full conditional guarantee (2) impossible. Thus, we weaken this goal to consider achieving type of best-in-class approximation to conditional cover- age, where for a sequence of coverage values o, "optimal" relative to the data and parameters θ we obtain
Lemma 5.3. Let {Se) follow weakly-stationas AR(I)
stochastic process where E [c²] S (1)E [e]]² and there is a constant a > 0 such that P[[[]], 2 o) 2 1/2 and F([-5]+ 2 σ) 2 4. Let Zo,s = (So 1) and D. = 1 E Zo, Z,, Then for
(Y, & C,())) Fi-1) at = o(1).
1 there are numeri- cal constants P, C. > O such that
If 0r = a for all t, which holds under well-specification, we recover conditional coverage (2).
P(mmin (E6) 2 c. (a A1) Fo 1mm) 2 p.
We thus consider a setting where there is some stationary distribution II governing the long run behavior of {(S,, Z,) For this long-run distribution II, define the an implicitly via the best quantile predictor
In particular, E[Amin(Ei)) Fo-1.m] 2 pala A 1).
We can now state our finite-sample convergence result, which we prove in Section C.5 of Appendix C, provided that a result analogous to Lemma 5.3 holds almost surely.
0" argmin (Ln( EET - =]]]) BEe
Theorem 5.4. Let the assumptions of Lemma 5.2 hold, and let pmin < mingg[B] Eius 1.). B² 2 4, and c E [0, 1]. Then, for any < B and a universal constant C, the iterates of Algorithm I with learning rates no following bound with probability at least 1 6:
(Typically, we consider an ergodic stochastic process con- verging stationary distribution II.) When the minimizer @* is unique, it defines conformal sets
2--1 satisfy the
be
(X,) = (y e y s s(Xr. v) S Z,
< 1 < s (log( B (loggBlogg (Bg(B)/6) + 1)G2
M b
and "relatively optimal" confidence values
This implies that if v' is a uniform upper bound for the conditional densities in a neighborhood of size GD around of. then for some (other) constant C' depending on m, u', G. Puinn and any T.
0x = P (Y: $ (X+) | [F-.).
(3)
These a, are often close to a, as all other 0 E θ attain worse expected coverage relative to our chosen features Z, We formalize and prove this, as well as providing syn- thetic experiments showing the coverage properties of a, in Section D.1 of Appendix D.
(log(T log(T)/8)) t
P(Y & C(X)) Fr-1) s <C'
5

---

Online Conformal Prediction via Online Optimization
Aside from the good coverage provided by 0*, is not imme- diately clear that the quantile loss is the correct objective to minimize. The iterates of Algorithm I perform well with re- spect to the quantile loss since they achieve sublinear regret by the argument in Theorem 3.1 of Hazan (2016), but one may instead be concerned with alternative loss functions, such as conformal set sizes or the square loss. However, in Appendix D.2 we argue as in Mannor et al. (2009) that in the online adversarial setting, minimizing loss function subject to long-run average constraints is impossible even in the case of simple linear functions, so it is unlikely that this is possible in the case of minimizing some arbitrary loss subject to the long-run coverage guarantee (1).
Here we also observe the same tradeoff in Theorem 5.4 in terms of the learning rate when compared to the long-run coverage guarantee of Theorem 4.1.
7. Experiments
In this section, we empirically evaluate Algorithm 1 along- side baselines. We focus on SQT+AR as in Example 3.2 and LQT of order p as in Example 3.3, and use batch size = 1 since larger batch sizes provide comparable results.
7.1. Baseline algorithms
We now describe the baselines we compare against.
To characterize the speed of convergence to the o; in (3), we will assume the stochastic process generating {(S,, ct is B-mixing. If for 0
Adaptive conformal inference (ACI) (Gibbs & Candès, 2021). In offline conformal prediction, the threshold q to construct confidence sets C(-) is chosen (up to a minor cor- rection) as the (1 - a) empirical quantile of a heldout set of validation scores. ACI instead chooses the (1 ax)) empiri- cal quantile of past scores for time-varying a updated via gradient descent on the quantile loss.
t, we let Pir) be the distribution
of (Z,, St) given Fr with density Plyg- we can define the 3-mixing coefficient
B(T) sup IEN
{
2E
pt+T 11 |
with mixing time (P.cc) = inf(r N ((T) S c].
Our remaining baselines fall under the conformal PID con- trol framework (Angelopoulos et al., 2023).
Under these assumptions, Algorithm 1 with m reduces to special instance of ergodic mirror descent (Duchi et al., 2012: Agarwal& & Duchi, 2013) applied to the convex func- tion (0). When the scores S' have densities, the expected quantile loss behaves like a strongly convex function, allow- ing us to extend prior analyses to the last-iterate strongly convex setting. We provide a proof of this extension in Sec- tion C.6 of Appendix C. (Our proofs formally require that under II, the conditional score distribution S Z has contin- uous density Z with the uniformly upper and lower-bounds Pn S. (s) < un in a e-neighborhood of O²)
Scalar quantile tracking (SQT). This method (also known as conformal P control) directly updates the threshold d: via gradient descent on the quantile loss. It predicts de > i= 1/: (err; - a) when initialized qı 0.
1-
Conformal PI control (PI). This method incorporates an error integrator re R - IR adding r. r((E err, a) to the SQT update. As in Angelopoulos et al. (2023), we use the tangent integrator re(z) := Ky tan log(t)/tCsa)) where K5, Can > 0 are hyperparameters and tan(r)) sign(x) 00 for 1/m 722..
Theorem 6.1. Let the assumptions stated above hold, and let + have finite diameter D. For some X > 0, let En [ = AI, t E [T + 1], e E [0, 1], and μ = pnAminn { 13. Then the minimizer O* is unique and the iterates Oe produced by Algorithm with m = 1 and 2n N ue satisfy
Conformal PID control (PID). This method is the same as Pl, but also predicts future scores via scorecaster q whose predictions are added to the PI update. As in An- gelopoulos et al. (2023), we use a Theta (Assimakopoulos & Nikolopoulos, 2000) scorecaster, which we call the PID(T) method, and an AR scorecaster, which we call the PID(A) method.
[10, 110,-0013 001] <c
=c
G² 12
+
GD p
We use the code in Angelopoulos et al. (2023) to implement the ACI, PI, and PID methods, where we replace predictions of co with the maximum score in each test set. We test all methods with both fixed and decaying step sizes. The decay- ing step sizes are of the form e - as in Angelopoulos et al. (2024), which satisfies the conditions of our stochastic consistency guarantees. For the PI and PID methods, we additionally adopt their learning rate trick of multiplying the learning rate by the highest score over a trailing window, even though this does not satisfy the conditions of Theo- rem 4.1. We describe the hyperparameter grids for each
te²
for T TD (P(tt and universal constant C. This im- plies that if a uniform upper bound for the conditional densities in e e-neighborhood around Z 6*, for some other constant C' now depending on p. G. C,
E [I & C.(X.) ((X.))F-))) F--))aai aull SC F.
In both cases, the expectation is taken over the samples ((S,, 7m)
6

---

Online Conformal Prediction via Online Optimization
method in Section B.1 of Appendix B.
adapted to our algorithms (Gibbs & Candès, 2024; Zaffran et al., 2022; Bhatnagar et al., 2023).
7.2. Existing data
For our methods, we recommend tuning hyperparameters by performing a grid search on recent data. One almost al- ways has access to a validation set of past conformal scores, which can give a sense of general properties of the data. We provide a starting grid in Section B.1 of Appendix B, which is implemented in our code and used in all our experiments. If the optimal values are found at the edge of the grid, the grid should be made larger.
In this section, we run our algorithms and baselines on datasets appearing in the online conformal literature. We describe our datasets below.
7.2.1. .. DATASETS
Stock data (AMZN, GOOGL, MSFT). Using stock data is common in online conformal work. Here we consider the returns of Amazon, Google, and Microsoft stock, which are datasets used in Angelopoulos et al. (2023) and contain roughly 3,000 observations each.
7.2.3. EXPERIMENTAL RESULTS
Our experimental results come in two parts, as we separate datasets into ones with stronger and weaker linear depen- dence. Since we fit linear autoregressive models to the scores, we expect our algorithms to do well when the data exhibits linear dependence, and otherwise be on par with existing algorithms.
Daily climate. This dataset has 1,575 daily temperature measurements in Delhi, India from 2013 to 2017, and is also used in Angelopoulos et al. (2023).
For the stock and daily climate datasets, we use the fol- lowing four base forecasters: autoregressive (AR) model of order 3, Theta model, Prophet model, and Transformer model. These are retrained at every time-step and give pre- dictions [Y.), of the time series (Yr), defining conformal scores S, == I Ytl- We use the code in Angelopou- los et al. (2023) to generate the predictions and subsequent scores. This gives a total of 16 (small) datasets.
To measure this property in our setting, we consider the autocorrelation of the first lag, which quantifies the degree of linear dependence between a time series and its one-step lagged values. We foresee increasing linear dependence when the base forecaster gets worse. For example, in regression setting, if the labels Y, E R are decomposed into their conditional mean μe and uncorrelated zero-mean noise w2 as Y, = Me + Wi, then the scores S, = |wy] have no linear dependence when the base forecaster predicts the conditional mean f4, perfectly. Otherwise, the error in conditional mean (a function of past data) introduces correlations between the scores. This is supported by the stock data where we can directly compare base predictors: we show in Table 4 of Appendix B that larger loss (average score) corresponds to larger autocorrelation of the first lag.
Elec2 (Harries, 1999). This dataset consists of 45,3 hourly measurements of electricity demand in New South Wales, Austrailia from May 7, 1996 to December 5, 1998. As in Angelopoulos et al. (2024), we use a one-day de- layed moving average as base forecaster. that is Y; := 1 21
Li=1 Yz-24- and conformal scores S. == 12 Y/l.
24
7.2.2. EXPERIMENTAL SET-UP UP
In all experiments, we set the confidence level to 1-a- 0.9. We always reserve the first scores as validation set, and set the rest as the test set. We tune the hyperparameters for our algorithms on the validation set, and for the baselines, we directly tune the hyperparameters on the test set. We justify this approach below.
In the first four blocks of Table 1, we present results for the Microsoft stock dataset. Due to space constraints, we defer to Appendix B the remaining results for Amazon stock, Google stock, and the daily climate dataset, although they are similar. In the subsequent block, we report results for the larger Elec2 dataset. We only present separate re- sults for both fixed and decaying step sizes for our main algorithm (I-QT)-for all other algorithms we report the best result. We focus on both the quantile loss to mea- sure the closeness of the threshold to the true scores, as well as the set sizes to show how conservative the con- formal sets arc. In Appendix B, we also measure the av- erage win rate against LQT(fixed, which we define as T ΣT 1 If S LL, (sed)) when é corresponds to quantile loss or set size, to get a sense of instantaneous performance.
We choose our experimental design following the recom- mendation in Guirajani & Lopez-Paz (2020) to specify strategies for model selection under distribution shifts. Since this is not explicitly done in all prior online conformal work, we tune baseline hyperparameters on the test set to identify a rough upper bound on their performance. We want to nei- ther rely on heuristics (which can only be worse) nor subject baselines to our (potentially suboptimal) tuning strategies, so our setup ensures that the best possible choices, subject to our extensive grid, are always made. Several follow-up works on ACI have considered adaptively setting hyper- parameters; these are orthogonal to this work, and can be
The key takeaway that when there is linear dependence in the conformal scores, our algorithms fit the data better
7

---

Online Conformal Prediction via Online Optimization
Dataset, metric
LQT (fixed)
LQT (decay)
SQT+AR
SQT
AC1
PI
PID(T)
PID(A)
MSFT ar. loss (avg)
0.091
0.09
0.09
0.088
0.09
0.088
0.088
0.091
Smaller Autocorr.
MSFT ar. set size (avg)
0.853
0.818
0.869
0.83
0.85
0.822
0.812
0.838
MSFT theta, q. loss (avg)
0.139
0.133
0.136
0.14
0.154
0.14
0.128
0.138
MSFT theta, set size (avg)
2.048
1.956
1.997
2.113
2.266
2,092
1,922
2.068
MSFT prophet, loss (avg)
0.104
0.1
0.101
0.151
0.213
0.15
0.134
0.134
MSFT prophet, set size (avg)
2.718
2.705
2.738
3.117
3.57
3.143
2.938
2.934
Larger Autocorrelaton
MSFT transformer. q. loss (avg)
0.115
0.118
0.107
0.289
0.352
0.196
0.149
0.148
MSFT transformer, sel size (avg)
5.947
5.942
5.852
7.629
7.938
6.661
6.119
6.104
Elec2, q. loss (avg)
0,005
0.005
0,005
0.013
0.015
0,013
0.011
0.011
Elec2, set size (avg)
0.16
0.159
0.157
0.229
0.244
0.227
0.201
0.201
Flec2, runtime (sec)
0.18
129.82
0.05
17.57
0.58
234.76
3,94
ERCOT, q. loss (avg)
29.095
29.158
36.918
59.118
76.629
53.233
42.344
42.349
ERCOT, size (avg)
691.496
691.414
746.546
977.629
1117.69
912.214
778.808
778.99
Table Performance conformal predictors across datasets, separated by datasets with smaller autocorrelation (top 2) and larger autocorrelation (bottom 4) of the first lag. Our algorithms are the three the left. Numbers are in bold if they represent at least 5% improvement over all methods in other category. All algorithms achieved at least 0.88 long-run coverage. We do not report runtime for (.T(decca) because it is the same LQT((fxed).
Final
scores
Predictions (LQT (fixed))
12
Predictions (LQT (fixed)
2500
Predi Predictionn ctions (LQT (fixed)) Scores
Scores
10
Scores
2000
8-
1500
2-
1000
500
1700
1750
1800
1850
1900
1950
2000
1760
1750
1800
1850
1900
1950
2000
4400
4450
4500
4550
4600
4650
Figure Linear quantile tracking (fixed) predictions versus scores MSFT AR (left) MSFT Prophet (middle) and ERCOT (right).
than the baselines. Otherwise, all algorithms perform simi- larly. For stock data, this dependence typically exists for the Prophet and Transformer base predictors, but not much with the Theta and AR base predictors. This can be seen in Figure 1, where we show ending window of scores and predictions for the LQT algorithm on both the MSFT AR and Prophet datasets. In the former, the scores look more like pure noise with a first lag having autocorrelation 0.19, while there are clearer waves in the latter with the first lag having autocorrelation 0.95. LQT is roughly constant in the former and the scores appear unpredictable; in the latter, LQT tracks the scores.
7.3. Pre-registered experiment
Our main experiment is pre-registered on Open Science Framework (OSF). The pre-registration document is in- cluded in the supplementary material and we provide the OSF link here: https::/ /totps://oof...e io/ jbp/.
We gather data from the Electric Reliability Council of Texas (ERCOT), an organization that operates Texas's 's electrical grid. This data accessible through the Grid Status API, which provides the true electricity load and a forecast for the load every minutes. Our conformal scores are their absolute difference, and our test data is from 12/18/2024 to 1/04/2025, which provides roughly 5,000 scores. We tuned the hyperparameters for our algorithms the data from 2 weeks prior to the date of preregistration, and the hyperparameters for all baselines are tuned on the test data. Summarized results are at the bottom of Table 1, and we also show an ending window of scores in the rightmost plot of Figure 1, as well as long-run coverage rates in Fig- ure 2. Our methods show significant improvements, and the
Even when results are similar, it is advantageous to use the LQT algorithm due to its lightweight nature and simple update. In Table 1, we also show the running times of each algorithm with fixed step size for the largest Flec2 dataset. Here the p order for LQT is which is a very common choice in our experiments. This is only slightly slower than SQT, and much faster than any other method like PID that attempts to model the score distribution.
8

---

Online Conformal Prediction via Online Optimization
Long-nun nun coverage rates an ERCOT
Long-run coverage tradeoff via LQT learning rate decay on ERCOT
Lang run coverage rate (taget 0.9)
0.96
SQT
0.96
0.94
LOT
0.94
AC1
coverage rate (targt
PIDrtheta! SQT+AR
0.90
0.90
decay: 0
0.88
0.88
decay:
decay: 0.4
0.86
decay: 0.6
Long
decay:
decay. 1
0.84
10000
2000
3000
4000
1000
2000 3000
4000
Time
Time
Figure 2. Long-run coverage of online conformal algorithms pre-registered ERCOT data. The left plot shows the long eoverage as a function time for several algorithms; all converge to the target a 0.9) rather quickly. On the right, we vary the learning rate decay (the learning rate is of the form = vary here) for LQT exhibit the tradeoff from theory. We observe slower convergence for more quickly decaying learning rates.
autocorrelation of the first lag was 0.94.
Acknowledgements
In addition to reporting our standard metrics, we also com- mitted to hypothesis tests in our preregistration. We per- formed 78 tests with several loss functions comparing each baseline LQT((ixe)), and describe these Section B.2 of Appendix B. We report here that all 78 hypothesis tests can be rejected at 0.05 significance level, and that almost all p-values are significantly smaller than 0.05.
Partially supported by the Office of Naval Research Grant 10001-22-112669 and N00014-24- 1-2609, well as gift from Schmidt Sciences. Felipe Areces acknowledges sup- port from the Mr. and Mrs. Chun Chiu Stanford Graduate Fellowship.
Impact Statement
8. Conclusion
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
In this work, we developed a new framework for online con- formal prediction that not only satisfies standard marginal adversarial guarantees but also achieves time-conditional coverage at every time for more predictable stochastic data. In our experiments, we observed that the linear dependence of the data, which we measure in terms of autocorrelation, a strong indicator of the performance improvements that our algorithms offer over the baselines.
References
Agarwal, A. and Duchi, C. The generalization ability of online algorithms for dependent data. IEEE Transactions on Information Theory, 59(1):573-587) 2013.
While approach focused simple autoregressive mod- els, expect that more complex conformal predictors that, for example, use richer feature vectors or incorporate trans- formations of the data, can offer further empirical improve- ments. We expect that techniques from offline conformal prediction that approach covariate-conditional coverage can be incorporated into our framework to provide even stronger conditional guarantees. We also believe that similar con- sistency guarantees can hold when l, is weakly convex, stochastic subgradient iterates converge to stationary points in this case (Duchi & Ruan, 2017; Davis & Drusvyatskiy, 2019).
Angelopoulos, A., Candès, E., and Tibshirani. R. J. Confor- mal PID control for time series prediction. In Advances in Neural Information Processing Systems 36, 2023.
Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L., and Schuster, T. Conformal risk control. arXiv preprint arXiv:2208 02814, 2022.
Angelopoulos, A. N., Barber, R. F., and Bates, S. On- line conformal prediction with decaying step sizes. arXiv:2402.01133 [stat. [stat.ML), 2024.
Areces, F., Cheng, C., Duchi, J., and Kuditipudi, R. Two fundamental limits for uncertainty quantification in pre- dictive inference. In Proceedings of the Thirty Seventh Annual Conference on Computational Learning Theory, 2024.
9

---

Online Conformal Prediction via Online Optimization
Assimakopoulos, V. and Nikolopoulos, K. The theta model: decomposition approach to forecasting. International Journal of Forecasting, 16(4):521-530, 2000.
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. Online multivalid learning: Means, moments, and prediction intervals. In Proceedings of the Thirteenth In- novations in Theoretical Computer Science (ITCS), 2022.
Awasthi, P., Cortes, C., and Mohri, C. Theory and algorithm for batch distribution drift problems. In Proceedings of The 26th International Conference on Artificial Intelli- gence and Statistics, volume 206 of Proceedings of Ma- chine Learning Research, pp. 9826-9851. PMLR, 25-27 Apr 2023.
Harries, M. Splice-2 Comparative Evaluation: Electric- ity Pricing. University of New South Wales, School of Computer Science and Engineering, 1999.
Harvey, N. J. A., Liaw, C., Plan, Y., and Randhawa, Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the 36th International Conference Machine Learning, 2019.
Barber, R. F., Candès, E. J., Ramdas, A., and Tibshirani, R. J. Conformal prediction beyond exchangeability. arXiv:2202. 13415 [stat.ME], 2022.
Hazan, E. Introduction online convex optimization. Foun- dations and Trends in Optimization, 2(3-4):157-325, 2016.
Bartlett, L., Dani, V., Hayes, T. P., Kakade, S. M., Rakhlin, A., and Tewari, A. High-probability regret bounds for bandit online linear optimization. In Proceedings of the Twenty First Annual Conference on Computational Learn- ing Theory, pp. 335-342, 2008
Hermdorf, N. A functional central limit theorem for f- mixing sequences. Journal of Multivariate Analysis, 15 (1):141-146, 1984.
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Practical adversarial multivalid confor- mal prediction. arXiv:2206.0100 [cs.LG], 2022.
Jung, C.. Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction. a5X1v:220..15145 [cs. 2023.
Kiyani, S., Pappas, G., and Hassani, H. Conformal predic- tion with learned features. 7xXv:2244.17747 [cs.LG], 2024.
Bhatnagar, A., Wang, H., Xiong, C., and Bai, Y. Improved online conformal prediction via strongly adaptive online learning. 2rXiv:2302.07866 [cs. 2023.
Koenker, R. and Bassett Jr., G. Regression quantiles. Econo- metrica: Journal of the Econometric Society, 46(1):33- 50, 1978.
Davis, D. and Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, (0(1):277239)) 2019.
Kushner, H. and Yin, G. Stochastic Approximation and Recursive Algorithms and Applications. Springer, second edition, 2003.
Duchi, J. C. and Ruan, F. Stochastic methods for composite and weakly convex optimization problems. arXiv:1703.08570 [math. OCJ, 2017. URL https: //arxiv. org/ abs/ 08570.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-fres predictive inference for regression. Journal of the American Statistical Associa- tion, 1130523):009--1111 2018.
Duchi, J. C., Agarwal, A., Johansson, M., and Jordan, M. I. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1177 2012.
Lobato, I. N. Testing that a dependent process is uncorre- lated. Journal of the American Statistical Association, 96 (455):1066-109) 1076, 2001.
Gibbs, I. and Candès, E. Adaptive conformal inference un- der distribution shift. In Advances in Neural Information Processing Systems 34, 2021.
Mannor, S., Tsitsiklis, J. N., and Yu, J. Y. Online learn- ing with sample path constraints. Journal of Machine Learning Research, 10:569-599 2009.
Gibbs, I. and Candès, F. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1366, 2024.
Mansour, Y., Mohri, M., and Rostamizadeh, A. Domain adaptation: Learning bounds and algorithms. Pro- ceedings of the Twenty Second Annual Conference on Computational Learning Theory, 2009.
Gibbs, I., Cherian, J., and Candès, E. Conformal prediction with conditional aaatonallguuaaaa guarantees. arXiv:2305. /26/6 ( [stat.ME], 2023.
Mohri, C. and Hashimoto, Language models with con- formal factuality guarantees. In Proceedings of the 41st International Conference on Machine Learning, volume
Gulrajani, and Lopez-Paz, D. In search of lost domain generalization. arXiv:2007.01444 [cs.LG], 2020.
10

---

Online Conformal Prediction via Online Optimization
235 of Proceedings of Machine Learning Research, pp- PMLR, 21-27 Jul 2024.
Nemirovski, A. and Yudin, D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on Optimization, 19(4):1574- 1609, 2009.
Rakhlin, A., Shamir, O., and Sridharan, K. Making gradient descent optimal for strongly convex stochastic optimiza- tion. In Proceedings of the 29th International Conference
on Machine Learning, 2012.
Robbins, H. and Monro, S. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
Robbins, H. and Siegmund, D. A convergence theorem for non-negative almost supermartingales and some applica- tions. In Optimizing Methods in Statistics, pp. 233-257.
Academic Press, New York, 1971.
Romano, Y., Patterson, E., and Candès, E. J. Conformalized quantile regression. In Advances in Neural Information Processing Systems 32, 2019.
Ryu, E. K. and Yin, W. Large-Scale Convex Optimization: Algorithms & Analyses via Monotone Operators. Cam- bridge University Press, 2022.
Shamir, O. and Zhang, Stochastic gradient descent for non-smooth optimization: Convergence results and opti- mal averaging schemes. In Proceedings of the 30th In- lernational Conference Machine Learning, pp. 71-79, 2013. URL. http:/ http//oooodiggg//e ngg. mlw..resss v28 1788shaane shamir13 htmll.
Vovk, V., Grammerman, A., and Shafer, G. Algorithmic Learning in Random World. Springer, 2005.
Yang, Z., Candès, E., and Lei, L. Bellman conformal in- ference: Calibrating prediction intervals for time series. arXiv:2402.05200 [cs.LGG 2024.
Zaffran, M., Feron, O., Goude, Y., Josse, J., and Dieuleveut, A. Adaptive conformal predictions for time series. Proceedings of the 39th International Conference on Ma- chine Learning, 2022.

---

Online Conformal Prediction via Online Optimization
A. Related work
Online conformal prediction builds on standard offline conformal prediction for exchangeable data (Vovk et al., 2005), a framework that has recently grown in popularity, with its tools also finding applications in areas such as risk control (Angelopoulos et al., 2022) and language modeling (Mohri & Hashimoto, 2024). It guarantees that P( E C((++11) 2 1 - a; and P(Y++1 E C(X+-1)) s 1 + 4+1 when the conformal scores {Se) are almost surely distinct (Lei et al., 2018). A key property of these results is that the probability statements are marginal over both the dataset used to fit the predictive sets C' and the new covariate X1+1.
Real-world data can however fail to satisfy the exchangeability assumption. Similar to how more traditional machine learning theory has been adapted to develop guarantees under weaker assumptions (Mansour et al., 2009; Awasthi et al., 2023), adaptive conformal inference (ACT) (Gibbs & Candès, 2021) introduced the first algorithm to present an adversarial approach to conformal prediction. Subsequent work follows two main directions. The first explores how to adaptively tune the magnitude of ACI updates using online learning techniques, resulting in algorithms such as AgACI (Zaffran et al., 2022), SAOCP (Bhatnagar et al., 2023), and DiACI (Gibbs & Candès, 2024). These methods primarily address the adversarial setting, offering improved regret guarantees while preserving similar long-run coverage properties as ACI. Similarly to our work, Zaffran et al. (2022) discuss the idea of making ACI adaptive to time series with general dependency, but AgACI is not guaranteed to provide adversarial long-run coverage and is thus not comparable with our algorithms.
The second line of work proposes modifications to ACT's update rule inspired by ideas from control theory, leading to new algorithms like PID-conformal (Angelopoulos et al., 2023) and BCI (Yang al., 2024). Our work is more closely aligned with recent line of research developing online conformal algorithms that achieve good performance in stochastic settings while preserving long-run coverage when data is adversarial, such as decaying step-size ACI (Angelopoulos et al., 2024), which focuses on the i.i.d. setting.
Our work focuses on developing time-conditional conformal guarantees that average over the covariate distribution while conditioning on the set C. as in Angelopoulos et al. (2024). Such guarantees are fundamental for ensuring that our algorithms remain valid without the need for retraining, as common in standard offline conformal algorithms such as CQR (Romano et al., 2019). Recent work also addresses the remaining challenge of providing covariate-conditionall or simply ietiiitional-oveeeee
guarantees, both in the offline setting (Barber et al., 2022; Gibbs et al., 2023; Jung et al., 2023; Areces et al., 2024) and in the online adversarial setting (Gupta et al., 2022; Bastani et al., 2022). In particular, Kiyani et al. (2024) introduce mean squared conditional error as metric to evaluate algorithmss seeking covariate-condition guarantees in the stochastic i.i.d. setting, which is similar to the notion of time-conditional coverage we discuss in Section 6.
Our results are also related to the convergence theory of Stochastic Gradient Descent (SGD) (Robbins & Monro, 1951), which provides rates of convergence for the gap (or error) between the loss attained by the algorithm's outputs and the true minimizer. In the case where the algorithm receives i.i.d. samples from the target distribution and the loss is convex and smooth, Nemirovski et al. (2009) show that after T steps of SGD, the expected error of the last iterate is 0(2))/2) and "(T if the loss is additionally strongly convex.
The quantile regression framework, as presented in Koenker & Bassett Jr. (1978), has a non-smooth objective, so our results build upon the convergence theory for non-smooth functions. In this setting, many guarantees focus on the loss attained by the average iterate rather than the final iterate, achieving optimal expected rates of O (T-1/2) (Nemirovski & Yudin, 1983) and O (I (Rakhlin et al., 2012) when the loss is strongly convex. Shamir & Zhang (2013) show that these rates are indeed better than those for the final iterates, which only achieve expected errors of O (log(T)T and O (log(T)T-) in the convex and strongly convex settings, respectively. Harvey et al. (2019) extends both of these to the high probability
regime.
In our setting, we analyze the performance of SGD when the data not sampled i.i.d. from the target distribution, so our results are also related the convergence theory of SGD with dependent data. The class of problems we focus on is part of the family of stochastic problems with exogenous correlated noise (Kushner & Yin, 2003), which Duchi et al. (2012) analyzes in the context of (-mixing and ş-mixxng processes. Duchi et al. (2012) show that for convex losses under such mixing assumptions, the error rate of the average SGD iterate is governed by the 3 and o mixing times of our process, respectively. Agarwal & Duchi (2013) extend these results to the strongly convex setting but still focus on average iterate guarantees.
12

---

Online Conformal Prediction via Online Optimization
Dataset, metric
LQT (fixed)
IQQ (decay)
QT-AR
SQT
ACT
PT
PID(T)
PID(A)
Elec2, q. loss (avg)
0.005
0.005
0.005
0.013
0.015
0.013
0.011
0.011
Elec2, set size (avg)
0.16
0.159
0.157
0.229
0.244
0.227
0.201
0.201
Elec2, q. loss (win %)
1.0
0.563
0.603
0.158
0.183
0.189
0.241
0.243
Elec2, set size (win %))
1.0
0.567
0.612
0.183
0.206
0.209
0.255
0.258
Elec2, q. loss (avg) p-val
1.0
0.939
0.899
0.0
0.0
Elec2, set size (avg) p-val
1.0
0,948
0.914
0.0
0.0
0.0
0.0
0.0
Elec2, loss (avg) p-val
1.0
0.928
0.886
0.0
0.0
0.0
0.0
0.0
Elec2, loss (win %) p-val
1.0
0.881
0.977
0.0
0.0
0.0
0.0
0.0
Flec2, set size (win %)) p-val
1.0
0.884
0.988
0.0
0.0
0.0
0.0
0.0
Elec2, loss (win %) p-val
1.0
0.885
0.973
0.0
0.0
0.0
0.0
0.0
Table 2. Elec2 dataset. Our algorithms are the three on the left. Numbers are bolded if they represent at least a 5% improvement over all methods in the other calegory. All algorithms achieved at least 0.89 coverage.
Dataset, metric
LQT (fixed)
LQT (decay)
QT+AR
SQT
ACI
PI
PID(T)
PID(A)
ERCOT, q. loss (avg)
29.095
29.158
36,918
59.118
76.629
53.233
42.344
42.349
ERCOT, set size (avg)
691.496
691.414
746.546
977.629
1117.69
912.214
778.808
778.99
ERCOT, q. loss (win %) ERCOT, set size (win %)
1.0
0.371
0.399
0.227
0.288
0.296
0.286
0.283
1.0
0,34
0.407
0.243
0.31
0.317
0.301
0.296
ERCOT, q. loss (avg) p-val ERCOT, set size (avg) p-val ERCOT, loss (avg) p-val
1.0
0.5
0.0
0.003
0.016
0.002
0.0
0.0
1.0
0.507
0,0
0.002
0.016
0.001
0.0
0,001
1.0
0.494
0.0
0.004
0.015
0.003
0.0
0.0
ERCOT, q. loss (win %) p-val ERCOT, set size (win 56) p-val
1.0
0,183
0.001
0.0
0.0
0.0
0.0
0.0
1.0
0.175
0.003
0.0
0.0
0.0
0.0
0,0
ERCOT, a. loss (win %) p-val
1.0
0.18
0.0
0.0
0.0
Table 3, Pre-registered ERCOT dataset. Our algorithms are the three on the left. Numbers are bolded if they represent at least a 5% improvement over all methods the other category. All algorithms achieved least 0.89 coverage.
B. Additional Experiments
In this section, we report more detailed results for our experiments. In Table 2 and Table we present full results for the Elec2 dataset and the pre-registered ERCOT dataset, respectively. The hyperparameter grids are in B.I, with ours tuned on validation data and the baseline hyperparameters tuned the test sets. These additionally contain win rates versus LQT (fixed), defined as 1. E [f I L,QT (ixed)) when & corresponds quantile loss set size, well p-values to determine significance. For each baseline algorithm and loss function & corresponding to quantile loss, absolute loss, and set size, we construct a time series of the form
{ {Lr,haveline
le.1QQ (fixed) }
and one with corresponding indicator form
(1 2 (oxco (fxed)) 0.5).
This gives 6 time series per method. With the assumption that the data is (weakly) stationary, our null hypothesis is that the baseline algorithm is at least as good as (ffxed.))) That is, the mean μ of each stochastic process non-positive: μ S with alternative hypothesis μ 0. Since the data is not independent, we must resort hypothesis for dependent data. For that reason, use the test in Lobato (2001, Section 2.1), which we describe in detail in Section B.2.
Lastly, we show full results for the smaller datasets in Table 6. We reserve the first 1/3 of the datasets as validation data and tune our hyperparamters with the hyperparameter grid in Appendix B.I, while still tuning baseline hyperparameters on the test set.
We also show the relationship between loss base predictor and autocorrelation of the first lag for the stock data in Table 4.
13

---

Online Conformal Prediction via Online Optimization
Dataset
Base predictor
Loss (average score)
Autocorrelation of first lag
GOOGL
AR
4.68
0.23
Prophet
24.47
0.95
Theta
11.38
0.76
Transformer
151.40
0.99
MSFT
AR
0.38
0.19
Prophet
1.78
0.95
Theta
0.93
0.75
Transformer
5.03
0.99
AMZN
AR
3.85
0.31
Prophet
25.28
0.98
Theta
3.86
0.30
Transformer
63.53
0.99
Daily-Climate
AR
1,25
0.19
Prophet
2.16
0.67
Theta
1.48
0.15
Transformer
9.83
0.97
Table Relationship between loss (average score) and dependence (measured via autocorrelation of first lag) for stock data.
B.1. Hyperparameters
Here describe the hyperparameters used in our experiments. All hyperparameters are tuned via grid search, with grids presented in Table 5. Again, we emphasize that all baseline hyperparameters are always tuned on the test sets. When tuning hyperparameters, we use the ones that lead to the best quantile loss, since this is implicitly what all algorithms minimize and also a measure of the closeness of the predictions to the true scores, provided that they achieved 1 - a - 0.01 = 0.89 coverage. If no choice achieves at least 0.89 coverage, we disregard that constraint.
Hyperparameter
Applicable Algorithms
Grid Values
Learning rate
All
le-5, le-4, le-3, le-2, le-1, Ie0, lel, 1e2, 1e3, 1e4, le5
P order
LQT, SQT+AR
0, 1, 0.1. 5, 10, 100, 200, 1000
Bias covariate
LQT
Kr
PI, PID(A), PID(T)
10, 100, 200, 1000, Angelopoulos et al. (2023, Appendix B) heuristic
Csat
PI, PID(A), PID(T)
0.1, 5, 20, Angelopoulos et al. (2023, Appendix B) heuristic
Table 5. Hyperparameter grids.
We provide intuition for the hyperparameters of LQT here. The p order corresponds the AR(p) model that we use predict the quantiles of our scores. Therefore, it should correspond to the number of lags with large partial autocorrelation. which can be examined by plotting the partial autocorrelation function (PACF) plot. As heuristic, we observe that choosing equal to the number of consecutive lags with magnitude larger than 0.2 leads to good performance. In some cases, values larger than those Table can be helpful, as in the case of Elec2 dataset. The other main hyperparameter (besides the learning rate) is the feature corresponding to the bias in the conformal covariate. Specifically, we choose a order of 1, the conformal covariate will be the form Z: = [S,-1, w), where w is the bias covariate. While any non-zero bias term satisfies our guarantees, we generally observe that it should be the order of magnitude the scores. For that reason, heuristic is the average validation score (or slightly smaller value). We can likely achieve similar effect by normalizing the scores and setting w 1.
B. 1. SCORECASTER DETAILS
For the PID baseline methods, we implement both the Theta and AR scorecaster using code from Angelopoulos et al. (2023). Angelopoulos et al. (2023) train the scorescaster at using all past data at every time step. We follow this procedure for the smaller datasets Table 6. This becomes prohibitely slow for larger datasets, so there we only use the most recent 200
14

---

Online Conformal Prediction via Online Optimization
scores. In the ERCOT pre-registration, we had committed only using the most recent 10 scores, but show better results here with 200 scores since this is baseline.
The algorithm SQT+AR also uses an AR scorecaster to predict the next conditional quantile. In all datasets besides ERCOT, the AR scorecaster is trained using the most recent 200 scores via quantile regression and the cvxpy python library. The runtime can likely be made much faster by using other libraries. At the time of preregistration, we had only committed to using the most recent 10 scores, so for ERCOT data we only use the most recent 10 scores since this is one of our proposed methods.
B.2. Dependent hypothesis testing
To determine if our algorithm, represented by LQT (fixed), provides a significant improvement over a baseline for a specific loss function E, we look at the following two sequences of random variables
X le huseline LeLLTT (lixed)
W
buselline LILT (lixe)) } 0.5.
In this case, we assume that E [X.] = (rr and [W.] = Mbn are constant over time, testing for a significant improvement
would be equivalent to testing the null hypotheses (Ho, Ho) against the alternative hypotheses (H1, H1) in the following hypothesis tests
Ho: : 1/2 00
Ho Mw S 50
H1 : Pz > 0
H1 Nw > 0.
However, because X, and W, come from a time series and are not i.i.d. samples from an underlying distribution, standard hypothesis tests are not applicable here. For this reason, we use the hypothesis test in Lobato (2001, Section 2.1) which applies to an arbitrary dependent sequence Yú on probability space (2, P) satisfying the following properties:
1. Y is wide-sense stationary so that E [V,] My for all / E N and E [Y, Yz2 = =E =V,Y,, + for all 4,,2, E N.
2. For some d > 0, E [ < 0o.
3. For S. = Ei Y, | = of satisfies of + co.
4. Ye is p-mixing so that the maximum correlation coefficient
p(k) = sup (co Z2) Z, L2(22, : :s t)), Z, E
te
satisfies p(k) + 0.
Under these assumptions, if Myy 0, then Herrndorf (1984, Conollary) shows that for all [0
Ir
Σ
Y d
@B(r),
where Φ = (2) (0) is the spectral density of Y, at zero frequency, and B(r) a Brownian motion process. Lobato (2001) now uses this result to conclude that the test statistic
2
t!/2% 1/2 =
1/2 with
8t
=
2
Σ Y,
Y,
86
1=1
satisfies
B(1)
Ve 4 U1/2 with U1/2 =
Jd (B(r) rB
Assuming that the conditions outlined above hold for X, and W, under the null hypothesis, we can now perform one-sided hypothesis tests on our random sequences by computing the value of V, and comparing to the critical values of the distribution of U1/2- We provide estimated p-values with the same simulation technique in Lobato (2001) but using 10,000 10,000,000 sequences of length 10,000.
15

---

Online Conformal Prediction via Online Optimization
0.14
Fixed learning rate
Decaying learning rate
0.10
0.08
0.04
0.02
0.0
0.2
0.4
0.6
0.8
1.0
1e6
Figure 3. ||0, 0*|) vs. time I for synthetic AR(2) data, averaged over 10 runs where the error bars represent standard deviation.
B.3. Synthetic data
Here we experimentally verify our convergence theory Section by generating synthetic AR(p) data where our well- specified assumption holds. In this case, an optimal parameter 0* E O exists, so can track the distance between the iterates of Algorithm I and this optimal parameter.
Our synthetic data is sampled from the following AR(2) process:
S. 0.3S, 0.3S, Et:
where E N(,, 1). If
Algorithm with covariates Z, 18 1]T, the optimal parameters 0- = |0.3. 0.3, o a:] where o- represents the inverse of the standard normal CDF.
In Figure 3, we plot the distance to 0* over time for fixed and decaying learning rates. The decaying learning rates are (1/ft), which Theorem 5.4 suggests gives the fastest convergence. The results are as expected: fixed learning rates appear to converge noise ball, and decaying learning rates appear to converge f", suggesting that the conditional coverage condition (2) holds.
16

---

Online Conformal Prediction via Online Optimization
Dataset, metric
LQT (fixed)
LQT (decay)
SQT+AR
SQT
ACI
P1
PID(T)
PID(A)
MSFT ar, q. loss (avg)
0.091
0.09
0.09
0.088
0.09
0.088
0.088
0.091
MSFT ar, sel size (avg)
0.853
0.818
0.869
0.83
0.85
0.822
0.812
0.838
MSFT ar. q. loss (win %))
1.0
0.554
0.486
0.538
0.538
0,515
0.526
0.517
MSFT ar. set size (win %))
1.0
0.566
0.474
0,542
0.538
0.526
0.528
0.517
MSFT theta, q. loss (avg)
0.139
0.133
0.136
0.14
0.154
0.14
0.128
0.138
MSFT theta,
(avg)
2.048
1.556
1.997
2.113
2.266
2.092
1.922
2.068
MSFT theta, 9. loss (win %6)
1.0
0.56
0.485
0.428
0.447
0.451
0.547
0.505
MSFT theta, set size (win 56)
1.0
0.563
0.49
0,423
0,446
0.457
0.504
MSFT prophet. q. loss (avg)
0.104
0.1
0.101
0.151
0.213
0.15
0.134
0.134
MSFT prophet.
(avg)
2.718
2.705
2.738
3.117
3.57
3.143
2.938
2.934
MSFT prophet. q. loss (win %6)
1.0
0.519
0.466
0,302
0.28
0.301
0.257
0.251
MSFT prophet,
(win %6)
1.0
0.508
0.449
0.31
0.3
0.309
0.268
0.269
MSFT transformer. q. loss (avg)
0.115
0.118
0.107
0.289
0.352
0.196
0.149
0.148
MSFT transformer, set size (avg)
5.947
5.942
5.852
7.629
7.938
6.661
6.119
6.104
MSFT transformer, q. loss (win %6)
1.0
0.443
0.543
0.29
0,243
0.345
0.38
0.373
MSFT transformer.
(6)
1.0
0.441
0.536
0.294
0.257
0.356
0.379
0.373
AMZN ar. q- loss (avg)
1.198
1.215
1.205
1.198
1.29
1.195
1.197
1.228
AMZ.N set size (avg)
10.112
9.711
10.398
10.112
11,592
10.009
10.15
10.63
AMZN ar, loss (win %6)
1.0
0.538
0,446
1.0
0.508
0.537
0.528
0.469
AMZN set (win
1.0
0.556
0.446
1.0
0.513
0.554
0.554
0.481
AMZN theta, q. loss (avg)
1.218
1.203
1.207
1.188
1,283
1.192
1.195
1.23
AMZN theta, set size (avg)
10.252
10.364
10.586
9.927
11.364
9.91
9.976
10.426
AMZN theta, q. loss (win %)
1.0
0.405
0.397
0.452
0.42
0.458
0.453
0.406
AMZNN theta, set size (win %)
1.0
0.379
0.371
0.434
0.394
0.446
0.438
0.391
AMZN prophet. q. loss (avg)
2.208
1.419
1.341
2,432
2.998
2.264
1855
1.84
AMZN
prophet, set size (avg)
49.995
42.825
43.105
$2,808
57,934
51.747
46,209
46,231
AMZNN
prophet. q. loss (win 56)
1.0
0.529
0.511
0.341
0.293
0.364
0.384
0.378
AMZNN
prophet, set size (win %.)
1.0
0.514
0.488
0.352
0.302
0.369
0.386
0.379
AMZ transformer.
(avg)
1.713"
1863
1.39
4,975
6.622
4,286
2.055
2.057
AMZN transformer, set size (avg)
93.963"
97.903
92.614
127.9
143.724
120.728
97.04
97.04
AMZN transformer, q.
%6)
1.0
0.389
0.567
0.309
0.25
0.292
0.283
0.274
AMZN transformer, set size (win %6)
1.0
0.367
0.545
0.314
0.261
0.307
0.277
0.269
GOOGL. 9. loss (avg)
1.117
1.136
1.138
1.122
1,185
1.124
1.118
1.142
GOOGL ar, set size (avg)
10.436
9.828
10.681
10.335
11.167
10.334
9.932
10.827
GOOGL ar, q. (win
1.0
0.63
0.465
0.418
0,545
0.541
0.633
0.495
GOOGL ar, sel size (win %%)
1.0
0.675
0.477
0,413
0.557
0.567
0.666
0.494
GOOGL. theta, loss (avg)
1.744
1.61
1.615
1.76
1,911
1.762
1.623
1.724
GOOGL theta, sel size (avg)
24.999
23.433
23.027
25.503
27.248
24.773
23,235
24.545
GOOGL theta, q. (win %6)
1.0
0.594
0.603
0,458
0.495
0.509
0.586
0.512
GOOGL theta, sct size (win %6)
1.0
0.598
0.616
0.455
0.5
0.523
0.598
0.519
GOOGL prophet, loss (avg)
1.335
1.33
1.317
2,086
2,459
2,072
1.812
1.803
GOOGL prophet, set size (avg)
34.916
35.136
35.297
43.597
47.222
43.553
39.424
39.154
GOOGL prophet, q. loss (win %))
1.0
0.38
0.406
0.27
0.258
0.272
0.245
0.251
GOOGL prophet, set size (win %)
1.0
0.333
0.371
0,279
U.27
0.284
0.248
0.25
GOOGL transformer, loss (avg)
1.711
1.585*
1.6
5,729
12.424
4,045
2.396
2,407
GOOGL transformer. set size (avg)
208.989
206.891*
207.588
245.381
291,003
228.834
212.054
211,965
GOOGL transformer, loss (win %)
1.0
0.566
0.601
0.158
0.212
0.277
0.318
0.318
GOOGL transformer, set size (win %))
1.0
0.557
0.605
0.174
0.227
0.292
0.322
0.322
daily-climate ar, q. loss (avg)
0.243
0,246
0.249
0.243
0.251
0.239
0.237
0.254
daily-elimate ar,
(avg)
2.708
2,514
2.609
2.632
2.689
2,706
2.583
2.708
daily-climate q. loss (win 56)
1.0
0.537
0.525
1.0
0.5
0.549
0.556
0.47
daily-climate ar, set size (win 56)
1.0
0.539
0.532
1.0
0.504
0.558
0.564
0.461
daily-climate theta, q. loss (avg)
0.274
0,268
0.269
0.264
0,275
0.265
0.263
0.288
daily-elimate theta, size (avg)
3.325
3.351
3.291
3.295
3.192
3.245
3.174
3.247
daily-elimate theta, q. loss (win (6)
1.0
0.47
0.476
0.539
0.527
0.552
0.542
0.483
daily-cling laily-climate theta, set size (win (6)
1.0
0.454
0.473
0,541
0.533
0.57
daily-elimate prophet. q. loss (avg)
0.269
0.275
0,281
0.317
0.3
0.309
0.32
0.317
daity-elimate prophet,
size (avg)
3,828
3.788
3,918
4.219
4.22
4,168
4.2
4.162
daily-climate prophet, q. loss (win 56)
1.0
0,506
0.483
0.347
0,383
0,394
0.356
0.374
-lily-elimate prophet, set size (win %)
1.0
0.515
0.482
0.351
0.39
0.404
0.399
daily-elimate transformer, 4. loss (avg)
0.313
0.317
0.315
0.443
0.359
0.392
0.42
0.421
daity-elimate transformer, size (avg)
9.1
9.148
8.955
10.126
9,923
9,808
9.831
9.899
daily-climate transformer, q. loss (win %))
1.0
0.409
0.549
0.431
0.376
0.431
0.345
0.311
daily-climate transformer,
$6)
1.0
0.406
0.548
0.437
0.384
0.436
0.359
0.317
Table 6. Numbers are bolded if they represent at least a 5% improvement over all methods in the other category. Asterisk numbers achieved less than 0.87 coverage. All baselines achieved at least 0.89 coverage because we tuned them on the test set.
17

---

Online Conformal Prediction via Online Optimization
C. Deferred proofs for Sections 4, 5, and 6
C.1. Proof of Theorem 4.1
This proof follows Theorems and 2 of (Angelopoulos et al., 2024). Similarly, we argue that adversarial coverage follows from the boundedness of the bias terms in our iterates. More concretely, using the decomposition 0, (f,, cb) R we prove the following proposition.
Proposition C.I. susp lcs S C oo almost surely, then with probability Algorithm satifies
T a S
2mC TUB
m
err
T
t=1
now remains to show that the bias terms % are indeed bounded, which we do via the following claim.
Claim C.1. The iterates of Algorithm 1 satisfy sup, |col S K, - Kg + almost surely.
We now provide proofs for both of these results.
Demonstrating Proposition C.I. The final time T is not necessarily divisible by the batch size m, by time T, Algorithm will only perform updates based on the first Bm s 'I scores. For this reason, we first point out that by the triangle inequality,
T
Bm
T- Bm
1 +
err
a)
Σ
err; a)
eer
a),
T
T
T
and since |CI1++1, al S 1 for all i [T Bm]] and T - Bm S 1,
1 T
1 Bm
T
emr; - -a) $
CITY
a)
T
The rightmost term - matches the result in Proposition C.I, so it only remains to show that
Bm
2mC
eIry - a) S
(4)
T
TnB
For this purpose, we define
mm
if
A6
m(15"
no
if > 1,
to argue that the left-hand side of inequality (4) can be written in terms of the bias terms {co) B
bm as
(em a)
emry
a:)
B
b
?h (CITb,) - a)
m
b=
B
A
Th
(erTi,s - (1)
T
1=r t=1
A, (CB+1 - cr)
18

---

Online Conformal Prediction via Online Optimization
Since the bias terms are bounded JCB+1
c,l
2C, by Hölder's inequality have that
Bm
2C
em,
T
T
Since the learning rate schedule (mo)11 is non-increasing | I is a telescoping sum so that
| miB
which shows inequality (4) and thus the desired result.
Demonstrating Claim C.I. For C (K, + Kg + vi), we will only prove that с₁ 2 -C with probability 1, since the other direction c C' follows by identical argument. We will proceed by contradiction, so we let = inf N < -C} < oo be the first index where cs falls below -C, and note that 7 > 1 since |c1l - K2 + Kg. We will now show that if a finite T existed, then C--1 < G < CC contradicting our definition that T the first index where c falls below -C.
Recall that ê R. so the projection step in Algorithm leaves the last coordinate unchanged, and the update for the bias term has bounded magnitude
sup cb+1 col sup b
7Jb m
Σ
emr, al m-
This implies that the previous bias term C--1 < <(K, + K₂) and the predictions for batch (7 1) with i E [m]] satisfy
9r 0r-1.(0,-1) = h h, + c Ks
But, by assumption that all scores at least -K, almost surely, these predictions all lead to errors efr,-1,4 4--1588-11 1 and thus the previous update must inrease the bias term:
m
7 m
C =
c
eer 11 a) > Cr-1,
which shows the desired contradiction and demonstrates Claim C.I. This argument only requires that the bias term can take any value in the set [-C, C] so it can hold has finite diameter, as required by some of our other results.
C.2. Proof of Theorem 5.1
In our search for consistent conformal predictors that satisfy the conditional coverage guarantee (2), we must first characterize what model parameters (if any) attain this property. Our first step is thus establish the conditional coverage of any sequence which eventually represents all the conditional quantiles, matching our definition of asymptotic sell-specification:
Proposition C.2. For any sequence of iterates satisfying 0, a.s. Ozo E O*, then
P (Y E C((x)) Fi-1) 0.8. 1 a,
and our conformal predictors satisfy the consistency guarantee (2).
In light of this proposition, proving Theorem 5.1 1 is equivalent to showing that Algorithm eventually converges to some 0xc E e
Proposition C.3. The sequence of iterates (0o)s produced by Algorithm I satisfies
Op a.s. 0x0 E E
We now provide proofs for both of these statements.
19

---

Online Conformal Prediction via Online Optimization
Demonstrating Proposition C.2. Recall that for b
P (Y, E (x))
Ft-1) = IP (S, S (e6)) F(-1)
(St S q Fi-1)+ + / (1s.elot (f)) dPP
For any E > 0, if we let e be the neighborhood around the quantiles where the uniform density upper bound p1 holds, with probability we can take and b large enough that
(0)(0 - gil min(e/pi,e}
2
min/e/P1,e)
(0.) (00))
2
simultaneously. For such it must also be the case that
[P (Y2 E
and since was arbitrary
P PV E C.(X)) ( a.S. a.
Demonstrating Proposition C.3. We start by defining go,; E (86) empirical subgradient for batch and index i satisfying g E [Ba.i Fo,i-1] E aL.,,(0)), For any 0* E O³ we now use our assumption that the conformal predictor
has a bias term to define
D
T6. (0*)
which can be nonzero as we only require asymptotic well-specification, so that
-6, + Ab.s) T6.5
and
OL,,(0' Ab.i).
Our proof is based on the proof of Theorem 4 in Chapter 7 of Ryu & Yin (2022), which hinges on the following three claims:
(i) Almost surely, limo-+00 ||0, - 0-1 exists and is finite for all 0 e O*
(ii) The iterates {0 are arbitrarily close to optimal infinitely often, since for any 6* E O*
lim inf (gr O, (0 + Ab,i)) = 0.
(iii) Claims (i) and (ii) imply that 0, a.e, 0x e
Demonstrating Claims (i) and (ii). For this part, we rely on the Robbins and Siegmund quasimartingale convergence theorem (Robbins & Siegmund, 1971), which we state in Theorem E. in Appendix E without proof. To apply this result, we must first construct an appropriate quasimartingale.
20

---

Online Conformal Prediction via Online Optimization
Claim C.2. For any 0* Ør, define the mub-muuuurblle random variables
V/ = |10b+1
1*2
Db 2 llb+1
IE 1,5 06+1 (0* Ab+1,))) Fib)
m
Up = G + 2 T
E [10+1.5 90+ (,++1 Fmbb]
Then Vo, Do, Ub are non-negative with Eb=1 Up almost surely and
E [V. F Fm) S Vo-1 D6-1 + Ub-1;
so we can apply Theorem E.I.
Proof. Since 0b+1 = 11l (0s- m
Ei (o,i)
m
m
110+1- - 10 s 110g - 1¹ + nb
gb.
7bb
gb 0, - -0")
m7
m
1=1
i=1
110g 1²2 G2
2 716
Bb
(0" Ab,i))
7lb
Bb b.5).
m
772
If we now let 0, = (0o, es) E e x R, we can use the fact that our model has bias term to argue that the last coordinate of our empirical gradient il satisfies
BBula E Sn, (( (0,) cb);
so that ila I max(a, ax 1 a) < and
m
(8.. A
Σ
Bo, - (0r))
T. (0))
We can now use this fact and our previous upper bound to conclude that
m
m
|10+11 8-1 s 1|0g 1-1 + G2
7/6 lg6.s (6=)(")|-2
76
gb O, (0" + Ab,i)).
m
m
This shows that the Fmo measuraaee random variables
D₁ = 2 Tlb++1
E [g 06+1 - -00 + Ab+1,)) Fma)
m
m
U, = G2 + 7
E [16+1,1 - 06+1,((0)|1 [mmm)
m
satisfy
E [V6 Fm((bb)) $ Vo-1 - Do-1 + Ub-1.
The sequence [Da}s is also non-negative as
m
Dr
1
E E (8641,5,001) (0* Abt1,)) Fmb+i-1) Fmb)]
m
2 7b+1
E [go+1, 0u41 (0) Abt1,))) Fmbl
21

---

Online Conformal Prediction via Online Optimization
since (0) is convex and (0* Ab.)) minimizes Ls.s for any (b, Additionally, Uo is also non-negative and by n-summability and the fact that Eb=1 1i co, with probability
Ub 00.
We can now use Claim C.2 and Theorem E.1 to conclude that almost surely
(1) limp-+o0 Va exists and is finite.
(2) Eb= The s: Ob (0* + Ab,)) <0.
Theorem E.1 states that Σ D3 < oc almost surely instead of (2), but this is immediate consequence of the former since oc
Eb=1 Do being almost surely finite implies that E Dy] < co and
E
Σ
Do
E 2
gg. B, - -6 Ab.i))
so the finiteness of this expectation also implies (2). This argument holds for any l E O* by (1) for all 0 E O* [with probability limg-+0 10, 01 exists), and since O* Rd by Proposition 1 in Chapter of Ryu & Yin (2022) this implies (i) as with probability [for all 0* E O², lim ||0, - 0*l exists). For (ii), since Σb= no cc, by our positivity constraint (2) implies that for any 0* E e*,
m
lim inf 8-000
g Ob (0* + Ab,i))
770
Demonstrating Claim (iii). The fact that 110, - 0*| bounded by claim (i) implies that 0, almost surely bounded too, so by (ii) there exists a subsequence by - 00
On; 0.0
ghy Ob, (0" + Abg.))) 0.
We will now show that 00 A by contradiction, we assume that 600 A and argue that if this the case
lim sup
1 _
Σ go is Ob, (0" + Ab,,))) 0,
J
171
which contradicts the condition above. The fact that our conformal predictors are regular implies that there exist infinitely many k 2 1 such that
(0.0) T
for some e > 0. We can now find large enough so that any j 2 N satisfies ||0b, - -boll s 2G and by our Lipschitz assumption
146, - 20) 2
Therefore, for any of the infinitely many & 2 N where 19b2, - % 2 we also have
(0b,)) Abarl
2
22

---

Online Conformal Prediction via Online Optimization
We now apply Lemma E.3 and our uniform local lower bound on the conditional densities for any such & 2 N to conclude that there exist constants C1, C2 such that
Bb Bb. - -00" + Abnne) 2 m
1, 0b. - -00 + Abc,1))
772
(Lbz, 1 + Abr,1))
(ac A c2c²) )
> 0.
This result contradicts our assumption that limj- > x==1 (0b3. Obg -00 + Ab) 0, 000 =+, Finally, by (i)
we know that almost surely |0s- [*1 exists for all 6 E - which includes 0 = 0x ||0, 0x ll 0 and the entire sequence converges to &x E @ almost surely.
C.3. Proof of Lemma 5.2
T Zo.s 9h.s is the conditional quantile of So, Fo,1-1- Since θ is well-specified, there exists 0r θ such that 0"
Noting that Za,; is measurable with respect to Fo.i-1 and 10 Zo,i - 0- Zo.il l S GD by our Lipschtiz and finite diameter assumptions, we can use Lemma E.3, the lower bounds in the standard scalar case, to write
(0) - (0*)
Couaanite - 00 7b.s) - Lauantile - 0- 7o,i) Fobi
min
1]
1 Zo.s 8e Zn,
2
GD
This can further be lower bounded as:
(0)
(0*)
min
1) 1)
00 8¹) T Zo, -8")
m
2m
GD
1=1
P min
LGD 1] (0 0*)
1
Zb. b,i
(0 (0-0) 0*)
2
m
8 GD
1 110 0-11
min
1mh 10
1
The second inequality follows from the fact that x Ar 2 Amia (A) ||=11 for any symmetric matrix A and with minimum eigenvalue Amin(A) E R, and any x. Note that A here is non-negative since its corresponding matrix is the average of positive semidefinite matrices. This completes the proof.
C.4. Proof of Lemma 5.3
For simplicity, we consider only single batch of m observed covariate vectors Z; = (St, 1) for = 1,..., m. as in the assumed AR(1) process we have S, = oS + Ex, where E, are i.idd with B[=,] = 0. This is sufficient to show Lemma 5.3 since the proof for an arbitrary batch b identical after appropriately offsetting the indices of the scores. Define the matrix
1
S2 S
S
Z.Z.
1
Let = relate the minimal eigenvalues of E to first and second moments of Spz via the following lemma:
-
and ET and
no Σm S? be, respectively, the sample mean and second moment of the scores. We can
Lemma C.4. For the matrix Σ = Em Z,2,T we have
S
Amin (Σ) >
1
m
2 m
1 +
S2
m
23

---

Online Conformal Prediction via Online Optimization
Deferring the proof of Lemma C.4 temporarily, we see that show Lemma 5.3, it suffices show that both
(i) S 2 Cua for constant Co
i S. S C1 S for constant 01
with constant probability, as when these both occur, we have
Cuo?
Amin (2) 2 (1 c1)
+ coo2
with constant probability. For the remainder of the proof, we thus seek to demonstrate both of these, and in both cases, we assume So = s for a fixed scalar value E R. as the process is independent of (S=;)ieN given Sg, and we condition implicitly on So throughout.
Demonstrating claim (i). Writing S = @ Ei, we have
Σ
S
Σ
2
Σ (signsig((s)) sign(S:-1)
1=1
But of course, by assumption on the innovation process we have P([e]+ 2 σ) 2 1 and P([-E]+ 2 o) 2 1. so that
m
Σ
m esiggg)((E:) sign(Si-1)}
7 (1 o(1))o²
with high probability.' This demonstrates point (i).
Demonstrating claim (ii). This requires a substantially more tedious argument. We first develop explicit formulae for S, and their sums. Define the sequence of vectors
U = [ 6i-2 2 10 ... oJ E ERT.
Then have
S
Σ
J j Ej
+ 0 So = So + of
j=1
so that
m++
の m-++1
S
So
(5a)
1 ④
1=1
1=
and
2 (m++1)
S
So + of 6)
0²
S +
T
Σ
E
+
25p
D'uffe. e.
(5b)
1 02
We will control the deviations of both the expansions (5). For the former (5a), quick calculation with Chebyshev's inequality shows that with probability at least 1/t².
m Σ
pm +
0. 1- E, 50(1)
For the second term (5b), we control both the quadratic Dit (1. s)² and the final linear term.
Claim C.3. Let M Em uaae Then E Me] o² tr(M), and there a numerical constant p > such that for all
t e 10,
P ( Me 2 to ir (r(M) 2 (1 - 1)2
Making rigorous would use Azuma's 's inequality.
24

---

Online Conformal Prediction via Online Optimization
Proof. The expectation calculation is trivial. To lower bound the probabilities, note that by the Paley-Zygmund inequality, for any & [),
P(c P(ETMM ME 2 to tr(M)) 2 (1 t)2 o² tr(M)
BI(E" M
tr My Bi(e M
so that the claimed constant p assumptions of Lemma 5.3. To control the denominator, the expansion e" ME Eig Mie and that the E, are are i.i.d. and mean together imply
We now demonstrate that is indeed a (numerical) constant under the
11
Mc) Σ M + (1) Σ
M, Mlee) Σ Miflefej (#)
i#j
o(Loo (tr(M)) + MM
Because 2i has entries 01,4 sl- for S l and U2., = 0 otherwise,
(1v
My
V =
2 = x Σ ti
i-j σ
0² = ((vv)))
Ø
t=V
So tr(M)
D m
1 21)+1)
m
while by considering the diagonal, one-off diagonal, two-off-diagonal diagonal,,,,,,, and so on,
==
1-
P.r Z Observation C.I. Let e + 1. Then for any m N,
||
Ex=
m-
(m
1)0²
(1- The following observation allows us to control such sums:
m-1
m 1 c c
+ (m 1)c -1 c- c 1- c
Σ m i)c²
(1 c)- +
1-c
c
Proof. We observe that Em c¹ =
1-e" whenever C o 1, and so I-c
m-1
1 1- c
mp-1
Σ
(m- i)c' m
Σ
(i+1)e²
Σ c
1-c
2=0
1 n
0 m-1
1 m
1+1
m
1-c
dc
I-c c
1 cm
0
c
c+1
1- m
m
1-c c
de 1 c
1-c
Computing derivatives gives the result.
Returning chain of inequalities and substituting
2 in the observation, we thus obtain
|| 1 <
(1 2213 < tr(M)2,
m
and so the constant p (())(t((M)*++ M
desired.
Finally, we control the final sum in the expansion (5b). Defining the scalars
U₁ o² (1 - pm -
so for the vector u = (u....., Um) we observe that
od o'uf
U+E: = uT's
25

---

Online Conformal Prediction via Online Optimization
and
E
Σ o'
m
T
)}
B((("e))
Σ
u E + 0(1)
Eufufelefe]l- o(1)o² (Itull + -luula)
i=1
Because
||ul|]
S (1- (1-))
d² and ||u1| [T-
we obtain that
(1-03)
(1)
IP
to:
$ (1 o) 2²)²
for all t 2 0. Summarizing, in pursuit of proving claim (ii), have shown
Claim C.4. There is a numerical constant > 0 such that for any ta to 2 O. with probability at least 1/22 - 1/th.
m
S
m=
So
S 0(1)
v m
de 1-6
1-6 Φ
and
1
2
(m++1 1)
2
$0
ir
Σ
O(1)Sola0e
02
2
(1- (1-0)-1-) Φ²
By claim C.4, we may evidently choose ta to to be appropriate constants and see that with (numerical) constant probability,
d 1
Sm 2
m²(1 6)² 50
m(1 の)² and
S2
m
0² m(1 - o) -- d2
We consider two cases: depending on whether S 2 m In the first case (that it is larger), we see that 8m x
62
(1-0z Sg while
0
m(1
(2)
m3/2
o) V1 0²
That (1-677 S -- immediately shows 5g 2 Sm the latter case that S < ma? /0² we have Sm 2 S m[l-o|= while
o²
by the Fenchel- Fenchel-Young inequality ab S + g
O²S0
0²²
000
2
2
m(1 )2)
2m 02)
2m(1
6)2
2m 1
Φ2)
2m (1 +)
where incquality (+) used that m 2 - In particular, we have 52 2 Sm as desired.
Lastly, we return to prove Lemma C.4:
Proof. We explicitly find the eigenvalues of two-by-two matrix. For scalars a, and matrix
a bl A =
we have det(A - AT) = (a- A) A) b² = x² - (a+ + 1)A + a
b 1
Solving for det(A- AT) = 0, we obtain eigenvalues
A a a+1+ V (a 1)2 402
Now, let us assume that 62 = (1 7))a for some 7 E [0, 1]. Then using the first-order concavity of the square root (that is,
that V A V + 2/ we obtain
-a) 4(1 7)a = - V(a+ + 2Amin (A) = a = 1
1|2 -1+++++++++++ -4ya
27a
a
Substituting a = -22 and b = Sm, which satisfy 8² < a by Jensen's 's inequality, on the event that (1-7)57 2 Sm
we
have Aunin (E) 2
Noting that (1 S3, 2 _ if and only if S
3m² 2-
gives the lemma.
52
26

---

Online Conformal Prediction via Online Optimization
C.5. Proof of Theorem 5.4
We first introduce some new notation regarding gradients for ease of presentation. We denote the conditional subgradient by (f,x(f) (0) and the observed subgradient by (0) qu (So. O Z,,i). dropping the argument & when it is clear from context. We denote the batch expected subgradient conditioned on previous batches, gb EI Di= Sb.
Fm the batch empirical subgradient as go = >i= i= Eb,i. and define the difference 24 = g+ gb.
As in the proof of asymptotic consistency of Theorem 5.1, we start by establishing the connection between the conditional coverage guarantee (2) and the conformal predictor's parameter E O. The following proposition states that the conditional coverage error can be bounded by the distance of the optimal #* + that represents all conditional quantiles under well-specification.
Proposition C.5. Let So.z Foşs-1 have density Su, upper-bounded by v' in GD-neighborhooo around its conditional quantile T..- Then.
P(Y,, (Xb,))) Fo,i-1) (1 a) s LuG 10
Deferring the proof of Proposition C.5 temporarily, we see that to prove Theorem 5.4 it only remains to show that Algorithm I's parameters 0g E O satisfy |l0,- 0+ 0+1²² E O(log( log(B)/8) /8)//))))()/)/)) with high probability. We do this through the following two claims:
(i) For any 8 there exist recursive upper bounds ||0,+1 - 0-113 S V Ab. 10, 0- 0-112 Rd that hold simultane- ously for all < B with probability at least 1 - ō.
iii Under the event in (i), V V Ab,i 10, 0-1 + Rs E O(log (B log (og(B)/))/b) by strong induction.
Substituting our bound on |0, - 1-1 we get that for some constant C. which a function of G, Mmin u',
P(Y,, E (Xo,)) Fo. - (1 - a) s Cov (log( B log (B))))
b
Without batching, in the statement of Theorem 5.4 for different constant C, function of m, G, Mmin w/, we can write
(1- s sOV (log(T (oog(T))))))
(X()) -1-
ge
We now turn to the proof, which borrows several parts from Proposition 1 of Rakhlin et al. (2012). The novelty lies in the batch setting, the changing objective function, and the generalized learning rates.
Demonstrating Claim (i). We start by unrolling one iteration of Algorithm 1, using the fact that 0b+1 = Io - -()g:):
|10++1 - 0- S |0, 18.8 - 0*1|
|00 0+1| 2//b (go, 0g 0-) + n ||
S |0, - 0+1|2 - 21T0
(g), O, 0-) + 21/6 (go, Ob - -0* - 2n16 (go, 0, - 0²) + n G2
1 m
16, 1²1
2170
Egg, O, 0-) Fo-1.ml + 2766 (z,, 8r) n G2.
m
This expression can now be upper bounded using the subgradient inequality (go 0, -0)) 2 (o,( - (0*) and
Lemma 5.2 due to well-specification:
10.+1 - 0-1 < 100, - 0¹112 - 2776
(O(),,((b)) (o.)(0))) Fo 1.m] + 21p (zr, 0g 0") + G2
1=1
< 100 0- 112 2m 100
0 10 Fo 1,m] + 27p (zo, Os - 00) + G2
27

---

Online Conformal Prediction via Online Optimization
We the assumption that IE Ing Lemma 5.3), and our choice of step size QT
F is uniformly lower bounded by Mmin
0 with probability 1 (as in
2"
to argue that
Depmin
|10++1 - 0-112 Σ |10b 0-1 2mlll86 - 0- Mmnn + 21Jo (zb, 0, - 0-) + G
(1 27//mmiu ) 110, 1011 1?2= + 21%6 (zo, 0b 0¹) 116 G²
$ 1 (
110.
1011 2170 (ze, 0o 8*) + m G
Unrolling this recursion until = 2, we obtain:
[10++1 - 0-11
2 7
) |02
0-
5
II 1 (1
(2) )2))
2m (Zi, 0: 0-) + Σ j=i
II
1
(7)
G²
2
(1 ( (2) (ze, O2 0*)
1
G²
1
(
2
Σ
II
Σ
Punin
min
T20
where the first term vanishes since (2) = 1 at i = 2. Note that the sum in the second term can be bounded by 1
y using
Lemma E.6 so that using the simplified notation (1) IT (1 (3) je
110+1 0-1/2= < 2
[o(1) (z,; 02 0*) + G
Munn
M be
The upper bound in its current form does not match Claim (i) as it depends on (2,, 02 0*) rather than the norms ||0: 0- We bridge this gap in the following proposition using the fact that (+) is martingale that we can bound with high probability.
Proposition C.6. Let Mo( == fo( (z:, O: 0-) and 8 > O. Then My(i) is martingale difference sequence and with probability at least - 8
Σ fo(1)2 - 00112 GLb(b)
B log(B) 6
B log ()) 8
Mo(1) S 8G max
log
log
Mmin
for all b < B simultaneously.
Proof. Our sequence Ms(1) forms martingale difference sequence since
1 m
m
gg g: [i
8iJ
gig
1.
Fi
0,
m
m
(i()) is constant, and 0, is measurable with respect to F; The conditional variance, using the fact that ||2,|| S 2G, can be bounded by
Var(M,(1) (F I Gf) |00 - 11,
so that the sum of the conditional variances from M2( (b) satisfies
Var(M(() | Fm.1.)) s 4G2
fo(12 110, -
We also have the uniform bound (since fo is increasing by arguments in the inductive step of Lemma E.4)
2G f6bb
|M,(1) < fa(6)G ||0, 0+1 <
Amin
28

---

Online Conformal Prediction via Online Optimization
where the upper-bound ||0;
0* <
G follows from the fact that
Mmit
G | - 0- g: 10;
0-
gg 0*)
E Juu F(-1m
||0 0-11² |1 Pmin 110 10:-00 0-12
(6)
Now, we can apply Lemma E.2 from Bartlett et al. (2008) to bound the sum of martingale differences E M1(). As b increases from 2 to B, we have (B - 1) martingales, which we will bound together with union bound. As long as B 2 4 and 8' E (0, 1/e), with probability at least B8', for all b S B,
fo(1) 10: -01 2G fo(b) 2, 4G²
log( B) 8'
)
log B) 6'
Mo(1)= & 2 max
| 1og
log
Mmin
fo(i)2 110 0-112 Gfo(b) Umin
log( B)
log B)
s 8G max
log
log
Substituting 8'
B yields the stated result.
Summarizing, with the goal of establishing O(log (oog(B))))))))) rate for ||6, 01, we have shown that for all < B,
with probability at least - 8,
100+1 - 1-11
2
Σ fo(1) |10, B=11 Gfb(b)
B (Blg(BB)
(Blo((B)
G²
8G max
log
log
+
Amin
Umin
2 b
16G / log( log log( B)/6)
16G log log B)/5)
G2
fo(1) 10, 10
M'in
1 b
Menin I
16G / log( log ()/66)
fo(12 10, -0-1 G26 B (o)(BB)))) +1)
Mmin
1 b
This is equivalent to Claim (i).
Demonstrating Claim (ii). We now prove by strong induction that 110,-011'
- 001 < g for suitably chosen This holds for which holds by inequality (6). To show the inductive step, we Mani
b = 1,2 2 20 since that implies ||0, - 1+1 <
write the above inequality as
|1
8011 S
f601 (1: -0112+ y be²
for x
1GG /oog/ log(B)/0, and G16 log (Bgg(())))))) By the inductive hypothesis, 110;
0-11² < 10+12-
for 1,...b.
Mmin
Hith
To show that [|0p41 0-11 s (b+1)E. it suffices to find sufficiently large so that
(a(1)2 a
a (b 1)
1=2
By Lemma E.7, which bounds f6 2
(b+1) S a.
b 1+11"
y <
+ (aVa+ +)) w)
bec
(b+ 1)c
29

---

Online Conformal Prediction via Online Optimization
Using the fact that (4t))
I Y/f for b 2 2 and [0, 1J. then
3x
3y
2 (Tv lava+ a y) +
Va
2
0.
2
2
Solving the quadratic inequality, we get that
3x
9x
1/9x²
9x²
9x²
9x
va 2 2 2
+
6y
=
2
+
+
6y
+ 3y.
4
2
4
4
4
Substituting in the values of x and we get that
576G² (oggBloog(B)) (B)/6) 3G (16log/ ( B log B)/8) + +1
(624 B log( B)/5) + +)
2
a
P
Mmin
M
Note that this satisfies the condition on in the base case, that is 2 the first statement the theorem.
2G Penon
since
3G Pminn
2
2G
This shows Claim (ii) and
Mmnn
Lastly, we return to prove Proposition C.S:
Proof. We our assumption that S₁ Fi-1 has density fo upper-bounded by u' in GD neighborhood around the conditional quantile ot, so that
P(V., Co.(( (oo,-1)) - a))
P((0, 2 So.s Fo, P((b,;(0*) 2 So, Fo,s-1)
max { ( Su,(()dde (o..((O))
(an.((0)) Insla)do
s w/ (1ggn,((h)))
T0 (0*)
S u/ G 110g 1*1l
C.6. Proof of Theorem 6.1
We first provide roadmap for the proof, and then the details for each step.
For our iterates Bg to converge to H* which defines the best quantile predictor, we must first establish the existence and uniqueness of the minimizer 0* We will argue that under our assumptions, this a consequence of the strong convexity of (n( around its minimizer.
Claim C.5. Let the assumptions of Theorem 6.1 hold. Then:
(i) There exists 0* E A such that Ln(0*)= & Ln(0) for any other 0 O.
(i) For any and μ = pmd min {1, GD
(n((0) In()") 2 100 -0
so 6t is unique.
Claim C.5 not only states the existence and uniqueness of 8", but also the fact that LT behaves like a strongly convex function with respect to its minimizer. This allows us to bound the squared distance ||0, - 8-1 ussin a recursion argument based on Proposition 1 of Rakhlin al. (2012):
30

---

Online Conformal Prediction via Online Optimization
Claim C.6. The iterates Og of Algorithm with 1 and vit
2
satisfy
per
(3)
110++1 - 00
1
2T (TT(LT) -((0))
j=it1
Σ
(1 2
( )
2
n 11::11
To prove the first part of Theorem 6.1 it suffices to control the expected value of the bound in Claim C.6. Deriving bound for the rightmost term is straightforward from our Lipschitz assumption and the learning rate inequality in Lemma E.6. To control the remaining term we rely on the following lemma.
Lemma C.7. Les (u2,-.. ",,, v be any sequence of positive scalars and
A
Σ M (L,(()))) +(()))))(((+))))))))))
then for <T<E <t
S GD
Σ
L-T
1/ 2
[(T)
BTTT:GG 1is - 1s45l +
Σ
4
2v
D
1=2
1-t-++1
The expectation is taken over the samples {(St, Z:))==
Combining the bounds for both terms now yields the first part of Theorem 6.1, which we summarize below.
Proposition C.8. Based on the bound in Claim C.6, the iterates 0g of Algorithm with m 1 and Tt jas satisfy
2
10411 1-1]]]
G2 ( n²
)
GD
T
+
(t 1)c²
for E [T' + 1] and a universal constant C.
The final step is to link this upper bound to the expected coverage gap via the following lemma.
Lemma C.9. Let St Fi-1 have density upper-bounded by in c-neighborhood around Z, 0r. Then,
G E [IP (Ye & C((X)) Fi-1) - -all < ( + unG) v [10 [10t11-0113 0-1
We now provide proofs for each of these results, with the proof of Lemma C.7 deferred to the end of the section.
Demonstrating Claim C.5. Part (i) is a straightforward consequence of the extreme value theorem since θ is closed and bounded and (0) is continuous, so there exists 0* E O such that Ln(0*) < Ln((0) for any other E e. Part (ii) requires a more detailed analysis that we split into sub-parts:
(a) The Hessian Ln) exists for all 0 E (2(,",
(b))b) In is pnA-strongly convex in BB, (0*, ) since for any 0 in this set the Hessian satisfies
LD) ł PMAI.
(ii)c) Part (b) and the finite diameter of imply part (ii) of Claim C.5.
31

---

Online Conformal Prediction via Online Optimization
Demonstrating (a))
Recall that by the chain rule for subdifferentials
V Ln = En ((P (S 2' Z) -1-a))
For any z and E [d] we now define the auxiliary function
ge z) = ( (s S 0 2 -1
- ()),
so that for any j E [d] we now let n. be the continuous conditional density S = 2, then the derivative
dg, (0;
0
(=())
==(== =m=(=T0)zzzz
2i
00,
00;
-00
exists by the chain rule and the fundamental theorem of calculus. We now note that for any 0 E B2("", &
1. | S G < 0o so yi (0; =) is an integrable function of
2. |2/2|| & G² co and π. is upper bounded by un over fs= ====26 0 B2(0", 1211 s G)
0g. (0;
< G2 un
a8,
with probability 1 and GZ < oc is an integrable function of z.
These results allow to swap expectation and differentiation to conclude that for any A B2 &)
Ln) En 22 (Z (Z)Z)==
Demonstrating (ii)(). Armed with our proof of (ii)(a) and explicit expression for L²), the result (ii)(b) now
follows from the fact that for any 0 in this set Tz 7 0) 2 Pm and
L' > PMAL.
We have thus shown that (n( is p-strongly convex for μ PnI on (0 8)
Demonstrating (i))()) If GD then Ln is p-strongly convex for all O so the claim immediately holds. If GD for any 0 ④ and | E [0, 1] we can define @ 30 + (1 - 3)00 θ so that
0 0- = = 0- 3D,
We know that for any other o 0" the convex optimality conditions indicate that (V"n( 0*) and by the convexity of (0)
and choosing 3 लो E 1) now ensures that Ø (2 )).
1 (Lm()) - Lm((r))
Lm(0) Lm)
2
3
2 (0*),, 0+) + PII
0 0+ 1
2,
And 3 110 0-1
This implies that 0* is unique since (0) > (f") for + 0
32

---

Online Conformal Prediction via Online Optimization
Demonstrating Claim C.6. To obtain our upper bound define ge (l((0)) our empirical subgradient for time and turn to the standard recursive relationship
| 10 = 110: - 0-112 217; (gt, 0r - 8*) + nze 118:112
We now use the convexity of & to conclude that
|0++1 102 > 110: - 1= - (4o(0)) - 4s (07)) 1 1
110, - 0²1 2n (L) LTT )) + 2nd (L) LT) ( +(00))((000)))) +n 11::112.
Recall that by Claim C.5 if f prrd min { (GD } then
(n( - (n* 2 _ 110 -0'1?
2
so that
10c+1 0'11 S (1 (1-1mm) 10:- 0- 112 + 2m (0,) -n(0)) - +x(0)) + || 1
For arbitrary 1 12 2 we now set 1/-
2 uee
and unroll the inequality to obtain
(1
(
|0c+1 - 0-112
|10- 1-2
2=
)2) 2m. 2m((L(()) - L0
(
1
2 ( )
Σ
1 1
oi ||B:l1?,
x=
2
where the first term vanishes since (1 2 //9) = 0 at i = 2.
Demonstrating Proposition C.8. We can obtain a bound for the leftmost term in Claim C.6 by applying Lemma C.7 with
21+c
II 1 (1-
1/4
pic
j=i+1
and using the learning rate inequalities in Lemmas E.4, E.5, E.6, and E.8 to bound each individual term. After some algebra, this yields the upper bound
B[A] 5 GDB(T)
28+GD
8TG²
1
ptf
1,200
and choosing T = (t(
GD
28TGD
SrG²
E [[A] <
1lt + 1)c
utte
natte
To handle the remaining term, we see that by the learning rate inequality in Lemma E.6
I 1 2 )
(1-(2)
22c
4G2
4TG²
E
||8:
1
<
22220
22r
1²²60*
2=1=
and thus since (o < 3 for 2 2,
2
E [100+1 - 0-[13] <
GD
56rGD
18TG²
ult + 1)c
p(t + 1)c
+
G2
GD
< 58
+
(t + 130"
The value 2 2 was chosen arbitrarily so the result holds for any 3 < + 1 1 T + 1. Moreover, the inequality (6) in the proof of Theorem 5.4 also holds in this case, with the corresponding μ. so |10, --11 < GD/μ μ and the bound is also valid for + = 1,2.
33

---

Online Conformal Prediction via Online Optimization
Demonstrating Lemma C.9. We start by using our local upper bound on the conditional density upper bound the coverage gap
R₂ = (Y, E C,(X,) ( (1-aa)) IP (St S (r())) (F-1) - P (S, - q:(0") F(-1)1
1 s.c(((()))) [(ss.elaco0)aaann))) )
S 11, 1|> + / 110
(0 S.IF
< 1 100-011128 + u (u(g((()) (0))
$ 1 100-00118 1> + uG ||0, 0"1 ||
We now take the expectation of R2 conclude that
E [R.] S PP (110, - -011 1iff--011>>0 )) + +uGE [100, 1*1
and by Markov's inequality,
G + uG E 1110c 101
E [Rd S
Finally, applying Jensen's 's inequality
G + uG uG)
/B |10. 1-11]
E RR S
which proves the desired result.
Demonstrating Lemma C.7. The proof of this lemma follows from a similar decomposition as in the proof of Theorem 3.1 in Duchi et al. (2012), so we first introduce the following two lemmas adapted from their analysis.
Lemma C.10. [Adapted Lemma 6.3 in Duchi et al. (2012)] Let our ergodicity assumption hold, let our conformal models be G-Lipschitz, and let O have fiite diameter D. Then for E m(FF), t > T 2 0, t- T, and any 0 E θ
E [[L((0) Ln((0) li+1 (0) + litr (0*) FJ < GD | p
11 I|
Proof. Note that
E [m()) - (n((0) (() + ((+)(0*) [F]]
| /(((s
((((s= = - -((s -(s--2 2 ((s-=T8 (
-
(e(s- 2 TT)) f(s z 2T TT )dPPt (2,8),
and since we assume that 1I and pitt have densities with respect to the Lebesgue measure À on I2++1
E [[n( - Ln((r) (0) + (0*) Fill = 1 (e(s =T0)
E(s - ((s== (TT)))
8) - p/j (z, ())s)))(()))))) 8))
GD / [m(2,)) p/j (2, s))d)(2,s)
GD pft m
Tv
34

---

Online Conformal Prediction via Online Optimization
Lemma C.11. (Adapted from Lemma 6.4 in Duchi al. (2012)) Let our conformal models be G-Lipschitz and let Ane be non-increasing sequence of step sizes. For > and i S the iterates produced by Algorithm I with batch size I satisfy
(eitr (0.) Citr (Ditt)) 55+
Proof. Recall that
64--1
Oc+7 = =0
Σ
11,
and since the learning rate schedule } is non-increasing
||0++
0:11
Σ
(.-e((0r)
Σ
7 (0-)1
r=i
$ T..G.
Finally, using our Lipschitz assumption once again
((,+
We now note that decompose A into the following terms
A
vy (Ln( - -L((0*) - 1147 (0.) + li+7 (1*))
A2
=
Σ (e+t l(+r((
1=
t-
A3
(ui (4++) - (+)+(()))
1=2
A4
(L(((*) - E(((1))
As
Σ (l.)((.)) - (=t-++1
- +,(00)++++(00)))))
so that A = -b Ag. We will now bound the expectation of each of these terms individually. Firstly, we observe that
E [ = Σ E (Ln(O.)) Ln((0) - (1.r(1) + (+++
Σ Me EE [(Lm(O.)) - Lm((0)) - 4, (0.) e Fill,
and apply Lemma C010 to obtain
1-7
G, ((T)
E [An] < Σ
35

---

Online Conformal Prediction via Online Optimization
For Ag we note that by Lemma C.11
A2 S Σ V
1=2
so EE [A2] must also be upper bounded by this quantity. The upper bounds for the remaining 3 terms follow from the triangle inequality, our Lipschitz assumption, and our diameter bound
E[As] $ Σ GD - M++l
1=2
[[4 - Σ
GGD
[[As] V Σ
2nGD.
i=/-++
Summing all the stated upper bounds yields the result.
D. Justifying the quantile loss
Here we provide some intuition justify why the quantile loss is an effective metric for evaluating and comparing online conformal algorithms. We argue that the minimizers of the quantile loss exhibit desirable properties in both mis-specified ergodic and adversarial settings, as discussed in Sections D.1 and D.2, respectively.
In addition to these results, we also point out that the quantile loss is often quite natural for the online conformal task. Specifically, grows linearly as the predicted quantile deviates further from the observed score S., and its asymmetric nature penalizes mis-coverage, where an actual error occurs, more heavily than over-coverage, where the conformal set simply less conservative than necessary, as long as a 0.5.
D.1. Properties of the quantile loss in the mis-specified ergodic sefting
In Section 6, we argued that if our quantile models are linear and the covariate and score pairs ((Z,, are produced by an ergodic process P converging to a stationary distribution II, then the iterates of Algorithm with batch size m = 1 converge 0* minimizing Ln, the expected quantile loss with respect to the stationary distribution. This implies that the coverage properties of our algorithm are determined by
at P PS, > |
To argue that these at often provide good coverage in the mis-specified setting, we consider the case where (S, > z, FI-1) P (S; > Z, Z.). This holds, for example, when the distribution of S, only depends on the previous q scores and we use an LQT model of order p 2 q. this case we can provide an alternative characterization of the stronger guarantee (2), since we assume that IT is the stationary distribution of process
(2) P (S. z 0 Z. 2) En [1552T8r)
2]
so that 0g = a E (Z) if and only if
sup (2.2
En ((ss-(ss))))))) = 0.
In the mis-specified setting, our predictor will not be able to attain conditional coverage, but may able to attain the weaker condition of coverage with respect to a family of witnesses V (2 (Z),
En V(aa - ((5>2T0))) 0. VEV
sup
We will now argue that these a; provide good coverage within our class of conformal predictors since for any other @ we can find a witness function V defined by our features Z such that the sets obtained from qe (8) have strictly worse coverage than ge (f*) relative to V.
36

---

Online Conformal Prediction via Online Optimization
0.7
Beev
0.6
Average over random
0.5
0.4
0.2
0.1
10
Maximum degree of mis-specified model (p)
Figure 4. Comparison of attained Low for Oen, 0", and the average value of Lew over 10,000 randomly chosen 0.
Theorem D.1. Let the assumptions in the previous paragraph and those of Theorem 6.1 hold. Then, for any O E O {0)}
there exists B(0) E Rdd such that the witness V (3)) T Z satisfies
En [V(a- [ En [V(a= [[8>2T0.)]] 0.
Proof. Recall from our proof Theorem 6.1 that Ln (0) = En &quantite (5 - -ZT0) has gradient
VI(0) = En [ - (S>2TT0)]
and that by the convex optimality conditions
(VL) 0*) 2 (0) - Ln((*) 2 (VLn(0*), - 8r) + 100 10 (VLn( 1.000))
0*) 2 0.
This immediately implies that for 3(0) (0 8*) and V = =(()) Z
En [V 1 [SS>2Ta])] > En (V(a- - 1 (S>2 20.
Note that the proof of Theorem D.1 also shows that when 0* E Int((), the model defined by 0* is the only one to achieve coverage relative to our features Z, since VL(#*)= = En [Z(a= 1 a.]]] O. This result illustrates why minimizing the quantile loss is desirable, especially when l E Int(O). as the minimizer obtains the best coverage relative to our features.
We can also verify that provide good coverage in synthetic experiments where the stationary distribution II is known. For our experiment we consider the standard AR(1) model with standard Gaussian i.i.d. innovations and parameter 0.5, and use a mis-specified linear model with feature vector (,(S)) S1, ... SP] for 2 2. In this case, a natural way to measure coverage of our model is through
Lewe (0) En P (S P 0 2)
the expected absolute difference between the conditional mis mis-coverage of our model and a. We now show the values of Tew attained by the minimizer 0* of T.n, the minimizer Oew of Towss and the average value of T.wo for 10,000 randomly chosen in Figure 4. Our results suggest that even under the criterion L the 0* minimizing the quantile loss provides good coverage comparable to Ocw. which is significantly better than the coverage attained by most other parameter values.
D.2. Properties of the quantile loss in the adversarial setting
In many cases, we can interpret online conformal prediction algorithms from online convex optimization perspective, where we analyze the performance of algorithm A producing iterates O, optimizing sequence of convex functions fe : O R
in terms of static regret with respect to some set θ C θ
T Σ (1(0.) inf Σ
(A,, (ft). 3
(1()).
BEB 1=1
In this context, by the argument Theorem 3.1 of (Hazan, 2016) Algorithm (A1) also satisfies the following regret bound.
37

---

Online Conformal Prediction via Online Optimization
Theorem D.2. Let & be convex and G-Lipschtiz, for every N, and let @ have finite diameter D. Then the iterates {0s)e produced by Algorithm I with non-increasing learning rates {ne ht and 1 satisfy
D2
Rr (()), _ + G2
T
qT
We note that by Theorem 4.1, when bounded Algorithm 1 also achieves small constraint violation with respect to the constraint functions gr(0) = Il (0) Therefore, if we define the set of parameters that satisfy the
cumulative constraints in hindsight
T
f 1
Σ (0) s =
t=1
Algorithm I with learning rates 7/2 ol 1//-2 for some o, and m 1 provides a solution to the constrained
non-convex online optimization problem
Σ (((.))
min Σ (()
min 0,
BE
T
s.t.
(e,)) S 0,
t=1
having sublinear regret RT(A1, (A,,),)))))) = ((T1/2+)) and constraint violations ΣT= 9:(0,) & /( simultane-
ously.
Note that any algorithm with sublinear constraint violations will satisfy
Σ etr, - a S o())
which is equivalent to providing at least (1-o) a:) adversarial marginal coverage in the long-run. This naturally prompts design algorithms with least (1 - ax) adversarial marginal coverage and similarly small regret RT(An [fr], θr) for arbitrary set of convex functions {fr} chosen by the user. The following Lemma, which follows from simple adaptation of the argument in Proposition 4 of Mannor et al. (2009), points out that this is impossible in general even when objective and constraint functions are linear. We provide a proof of this fact in Section D.3 for convenience the reader.
the question of whether
Theorem D.3. Let θ have finite diameter D. Then there exist sequences of linear functions {fe, {9c) such that any algorithm A attaining
1 Σ
lim sup T-000
gc(O)) S0.
T
also suffers
Rr(A, (11, 0r) 0,
lim sup
T-300
T
and it is thus impossible to allain sublineur regret and constraint violations simultaneously.
However, we believe the design of online conformal algorithms that allow the user to trade off between coverage and regret with respect to some arbitrary sequence convex loss functions {fe} is a promising area future research.
D.3. Proof of Theorem D.3
This proof closely follows the proof Proposition 4 of Mannor et al. (2009); we only adapt it to our online convex optimization setup for the convenience the reader. To prove this result, we first define the behavior our adversary and then show how this choice makes it impossible to attain sublinear regret and constraint violations simultaneously.
38

---

Online Conformal Prediction via Online Optimization
Defining the adversary. Let (v, w) argmax,,wed l/v w be the furthest points in that ||u w|l D 2o, and consider setting where the behavior of our adversary is dictated by sequence of indices ja that
Jt 1
(0) (w - (0 v) Je = 2,
and f((0) = D (w T v). For any E
f((0) 2 D2 100 2|| |0 wl 2 20
and fww = O, so that w minimizes ft for any t. Let år + Ei= 1 then if år I 1/2 we could choose 0 = w (in hindsight) to minimize all f(( while satisfying the average constraint. We now let our adversary initialize a counter A: = 0 and pick the indices je using the following two steps:
1. While or D Σ (w u) (0. -
pick je and increment & by 1.
2. For the next & time indices jr = 1. Then, reset counter l: to and go back to step 1.
Proving the impossibility result. We will now show that any algorithm that has sublinear constraint violations against this adversary cannot attain sublinear regret. To do so, we show that:
(i) The adversary executes both steps infinitely often.
iii) Any algorithm attains least linear regret when the adversary finishes executing step 2.
Demonstrating claim (i). We will prove this result by contradiction, so we first assume that step 2 occurs only a finite number of times. This implies that after a finite number of time steps, the adversary only chooses je = 2 so that fr + 1. However, our sublinear constraint
T > 9. (0.) 0
limsup T-
T
[=]
implies that the condition 1) -0 (0) result implies that both steps occur infinitely often, so we can find infinitely many t; < t < f5+1 such that the adversary plays step I for & E (4,, 4] and step 2 for / E (1,, 4+1]
-
must violated some point, triggering step 2. This
Demonstrating claim (ii). Since both steps are equally long we know that g.. = and
inf OE
Σ f+(0) 0.
Observe that by construction 4+11 - 44 < 1/ so that 42 fut and thus
2
1
4+
t
w
T()( v) -
+ (t141
- ti)
D2t
t++
2
1=1
t
t
li+1
3
1:41
t+1
4
4"
This implies that
Rey, (A, (A,ffe) Oc...)
411
Σ
(w u) T(O,
(0, v)
2)>0
1
t++1
D24++1
4"
39

---

Online Conformal Prediction via Online Optimization
and also the desired result
(r,
1 0.
lim sup T-
T
4
E. Auxiliary results
E.1. Existing Theorems and Lemmas
In this section we compile several known results that we use in our proofs for the convenience the reader. The first result a useful tool for asymptotic convergence proofs commonly known as the Robbins-Siegmund quasimartingale convergence Theorem. We apply this result our proof of Theorem 5.1.
Theorem E.1. [Adapted from Robbins & Siegmand ( [1971)] Let (2,,F,) be a probability space and Fi C be sequence of sub-o- -albebas of F. For each nt = 1, 1,2,--. ... let Vns Dus Un. and in be non-negative F meemaauuable random variables such that
E Vn+1
Fx] S V1+1+ B,) - DD, Uns
then lim Vn exists and is finite and E Dn < almost surely
Σ
Bn < 00,
Σ Un < 500
n
The second result is a concentration inequality for martingale difference sequences from Bartlett et al. (2008) and used to derive the high- eeh-probabbilty bounds in Theorem 5.4.
Lemma E.2. [Copied from Bartlett et al. (2008)) Let di...., dr be martingale difference sequence with uniform bound Idal S b for all i. Let V >i=1 Var,-1 (de) be the sum of conditional variances of de 's. Further, let a = vV. Then we have, for any 8 < 1/e and T 2 4
IP Σ d 2 max {2o, by babbboooggo log(1/5)} Vlog(1/0)
log({))d
The final result provides some lower bounds the expected quantile loss gap between in terms of the distance between and q², We use this lemma for our proofs of the results in Section 5 and 6.
R and the true quantile q",
Lemma E.3. Let S have a positive continuous density f. lower bounded by p >> 0 in an e-neighborhood around its unique aa quantile q². Then,
(i) For q such that lq -9"1 SE,
E quantile (S - - Equantit (S (S})))} 2 2 1212.
(i) For q such that lg >'
pe 2 q 9%1.
L quantite (S -Q)) Equantite (S (S-4")1
(iii) For q such that - 9*1 < K with K e 00),
pE
Eliquannte (S 9) Equanttee (S - --)]
1
2K
Proof. We dedicate section to the proof of each lower bound.
40

---

Online Conformal Prediction via Online Optimization
Demonstrating (i). We only prove (i) for q 2 q² the other direction follows by identical argument. We temporarily
adopt the notation I(g) El quuaiite g)] and recall that
Sa a - --920 5 ! Ia 1,a]
dge oglquantie (S q)
S= q.
The subgradient of the expected quantile loss thus (g) 0g Bl quuntiit (S 9)] ( 9)] = Bla 1s- P(S (1-aa)
since we assume that S has density. This is single valued so we can conclude that L(g) is differentiable and L'(g) = P(S S g) - (1 a)). Note that PSS - q²) (1 a) since f is continuous, and for E [g" 9- +|)
L'(a") -'a) PPS s 9) P(S s0 ["" f(s)ds 2 plq 9³)
This now implies that
L(e) - L(g")= L(g")
'_- L'(x)dz
( --
90"
q
9x²
(g 9¹)²
Demonstrating (ii). We once again only prove (ii) for q 2 q" as the other direction follows by an identical argument. In
this case, y > d' = 9¹ + e so that
L(g) L(g")= L(g) L(d') L(g') L(g")
2 L'(''(4 - d)+ 2 (1' 8²)²
(convexity of L; lower bound for o' E [ .4" + +e))
2 pE(g- - d')+ + De (d' 9¹)
(q' q- E)
2 pe 1g 9'),
2
as desired.
Demonstrating (iii).
This follows immediately from the previous bound by noting that if [g - 8-1 S 8 then
L(g) L(q")=
pc 2K l 1²12
and if lg 9-| >
L(g) - L(qg)= 2
Pe (g 9*)
2
pe (g 9²)2
(q )*)
2 3e (g 9²)
2K
E.2. Learning rate inequalities
The proofs of Theorems 5.4 and 6.1 rely on multiple inequalities bounding functions of the products 1I; -+j (1
:
for 2 < i < t, so present and prove them in this section. In standard analyses of strongly convex stochastic gradient descent, the learning rates are of the form ((1/t)) for c = 1, which simplifies the analysis of these products.
Lemma E.4. For any 2 2, i E [2, and E [0, 1].
II j=+t1
1
Proof. We prove the statement by induction on = .,....2.

---

Online Conformal Prediction via Online Optimization
Setting up the induction. Let
(1- (2)
f101 II j=H+1
1
and note the recursive relationship
2
fili - 1
1)c fe(i).
Our goal is now to show that f+(1) Σ go
for the base case, and given fi(i) S f then Se(i - 1) S pa for the inductive step.
Base case.
Observe that [a(t) = ge so the inequality immediately holds.
Inductive step. We move the inductive step, where by our previous relationship (7) and the inductive hypothesis
2
j
fe(1)
(i - 1)c
8 2
(i - 1)
to
proving the desired result.
Lemma E.S. For 1. 2 2 and E 1].
Σ =
1- 11 (
(
2
Proof. We prove the statement by induction on 2 2.
Setting up the induction.
Let
X = Σ 1 (2)
2= 2-
and note the recursive relationship
X, = 1 (2)) X, x te¹
(8)
We already know that X₂ = - for the base case, so it remains to show that if X, 2--5tthen X 2
Inductive step. We now move the inductive step where, by our previous relationship (8) and the inductive hypothesis
2
X =
X, +
+ 1
(t+1)² 1)
2
1
+
+ 1
2c
1I+
1
2c
proving the desired result.
42

---

Online Conformal Prediction via Online Optimization
Lemma E.6. For &. 2 and E [0.
I 2 -=
12 S 1- 5
12
Proof. We prove the statement by induction 2 Setting up the induction.
Let
1 (1-1(111) (2) 1
X Σ
726
1=2 j=
and note the recursive relationship
X₁ 1 (2)
1
X +
(9)
f2c
We already know that X1 < for the base case, so our goal is to show that X1-1 s (1- then X, st_
Inductive step. For 2 2, using the recursive relationship (9) and the inductive hypothesis,
X, - 1 ? (2)) 1)r +
1 t2n - (
(1- + (1-2++1) 1) to:
(t (t-1)) 1)c
We now define g(t) t (t 1)e and note that gt(t) c(te-1 (t 1)(-1) s 0 so g(t) is decreasing with
g(t) I 9(2) = 2 - 1, and
( (1 1)c 2 1) =1 t
(g(1) 2 +1
[0())-2++
) - 1
X,
--
+1
(t - 1)c
(t - 1)
proving the desired result.
Lemma E.7. For t and E [0, 1].
I 1 (2))²
(1-(1))
i S 1
f2c
2=2 j-1+1
Proof. We prove the statement by induction >
Setting up the induction.
Let
X, = Σ 1 (1- (1)))) 130
1=2 j=
and note the recursive relationship
X, = (1
2
2 2
1
X +
(10)
We already know that X₁ 0 S 1 for the base our goal is to show that if X, S (t 1)-11-a2 2c then X, S tt--2 2c.
Inductive step. For 2 2, using the recursive relationship (10) and the inductive hypothesis,
X, < 11 )2))²
1
1
t 1--20 ((
2 1 1)c
+
(t-
(t
1)20
t3c
f2c
to
43

---

Online Conformal Prediction via Online Optimization
We now recall from the last step of the proof of Lemma E.6 that
1 -- 2
1 (8-1)
S
S 1,
(t - 1)
(t
1)
so that
2-
2-
and
[t-13e
Iy-
1
X S 120
1
+
s
(1 - 1)0
10
12c
proving the desired result.
Lemma E.8. For any 1 2 3, T [t - 2| and E [0, 1]
1- 20
II 1 (1)
II j=i+++1
(1- (2)
3r 1
(1 =)
j=it1
Proof. Note that
QG -
Σ
L-T
II
(1-29) 2c
it II j=it1
2
(i T)
je
T)
je
j
j=j==t++11
so applying Lemma E.9,
(1 2º) jr (1+7)22*
(1-3e)
3r
Qut
jmitr41
We finally note that
2
37
Qr S
1
j
120
1= j=i+1
1 2
37 120
j
j=it1
and applying the bound in Lemma E.6,
37 Q1, S te¹
Lemma E.9. For any t 2 2 and r 2 1,
E+r
2
+ 7)
37 (t
[
S
in
t
T)
(t+t8
i=t+1
Proof. For every & 2 we will use induction on 2 to show that the stated bound holds.
44

---

Online Conformal Prediction via Online Optimization
Setting up the induction. Note that we can express
E+T
2 +++
RE,
II
1m1+1
using the telescoping product
(1 + +)
1+T
1
to
(i 1)
i=t+1
so that
R
II i=++1
2n)
(1+--1)
1+ 1
j0
We will now show that for any t 2 2. then
R S
3 [1+1)
for the base case, and if [1 - Re S
then
(1+7)
3(++)) [1 +1 < (1-++1ye for the inductive step.
Base case. For the base case with 1, observe that
1 1--11+11
2
1 R = 1-
+
tr
so we can argue that
2
(1
2
3
1 R₁,1 I
10
to
(t+ 1)c
(1 + 1)e²
and
(1+
3
R
<
t
(t + 1)e²
This implies that the condition holds for the base case since
3
- 1 S
(t - 1)
Inductive step. We now move to the inductive step and note that
[
+ + 1) 2
T+ +100 -22 2 (t T)+
1- R
[1 Re.
(t T)
and by the triangle inequality
(t + T + 1)a 2 (t + T)
(t (++T+) T 1)a 2
| R
+
1 RE-l
(t + T)
Focusing the first term can apply the same logic as before conclude that
+ + (
2
(1+
(1+ T)
and
(l+ + 1)c 2
-15 c <
2
(t + T)
t (t + T)
45

---

Online Conformal Prediction via Online Optimization
equivalently
(L + 7 + 1)c - 2 2
T)
( 7)
We now let (c) be defined in Lemma E.10 and use the inductive hypothesis the second term conclude that
2
(1 +1+++1)--2
3r
RI,-- 115
(t (t+ T)o
7)+
T)
-
2
37 (t+
+9+++(c)
t+
(t+ (++++1)
1)
We now apply Lemma E.10 conclude that
3r (1 +
| Re,++1 5
+
(1 + + 110
3(T+1) 1)
$ (t (
proving the desired result.
Lemma F.10. For 2 and E [1/2, 1) the function
gu(c)= = (u + 1) 20)
2) u (u+1)
uc
satisfies ga(c) $ (1) $
Proof. By computation we find that the derivative of our function at c E [1/2, is
(c)c)
(u + 1)
2( +
log
u
2 log
2(u + 1)
2c
u²
Note that since u 2 3 we have u+1 > 1 and increasing. Therefore, for any u,
1(++1)
< 1. so that for any u, g((()) > and the function Iu (c) is
u2
(u 1)2 2(u + 1)
(c) S gm(
S 1.
42
u2
46


Reviews:
[{"review_id": "RgJfKcrqag", "reviewer": "Reviewer_oGmv", "summary": "This paper is looking at the problem of online conformal prediction, focusing on deriving stronger (conditional) guarantees than long run marginal coverage. They propose to look at asymptotic absolute value coverage deviation from the nominal value at each time step, conditioned on all the past observations. They then design and algorithm based on quantile tracking through pinball loss minimization. Relying on standard proof techniques through the connection of pinball loss derivatives and coverage, they both and adversarial long run coverage validity and stronger conditional coverage guarantees in the stochastic setup.\n\n\n\nI thank the authors for their response. I agree with them. I strongly encourage the authors to incorporate the comments on improving their presentations. In particular, it is good that the list of contributions would be stated in the introduction with pointers to the associated parts of the paper.\n\nThe paper [1] that the authors mentioned is indeed what i referred to.\n\nI keep my score and vote for acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**A very similar notion of conditional coverage has been previously discussed by [1], in a stochastic iid batch setting, named mean squared conditional error**\n\nWe thank the reviewer for pointing us to this reference. We would like to verify that it refers to [1], and we would be happy to incorporate it into our discussion of conditional coverage in the i.i.d. offline setting.\n[1] Kiyani, S., Pappas, G. and Hassani, H. Conformal prediction with learned features. arXiv:2404.17487 [cs.LG]. 2024.\n\n**The paper needs improvement in the presentation...beyond just running online gradient descent on pinball loss, which is the core algorithm in the literature.**\n\nOur main contribution is a new algorithm that both satisfies adversarial guarantees (long-run coverage) and does the “right thing” (achieves time-conditional coverage) if the data is not adversarial. Most online conformal work focuses solely on adversarial guarantees, but we provide a novel approach that can adapt to both settings.\n\nIn terms of the algorithm itself, the main novelty is that we run online gradient descent on the quantile loss with more complex models for the conformal predictor. Past work (e.g. ACI) only considers scalar models, while our algorithm applies to arbitrary parametric models. For our stochastic guarantees, we simply require that the conformal predictor q_t(\\theta) is linear in \\theta. We will preface the algorithm with more motivation and discuss the novelties in the final version.\n\n**In the current version, the organization of the assumptions...but your assumptions don't hold then.)**\n\nWe will make the assumptions for each guarantee clearer, and expand on how conventional and restrictive they are in the final version. At a high level, our assumptions fall into two categories: model assumptions and distributional assumptions. Our model assumptions determine the structure of the conformal predictor; most of our analysis requires that the conformal predictor $q_t(\\theta)$ is linear in its parameter $\\theta \\in \\mathbb{R}^d$ (though this can in fact be dropped for the adversarial guarantee in Theorem 4.1). These are less restrictive than conventional model assumptions that only allow for scalar models (as discussed in our response to the previous point). Our distributional assumptions hold for many data-generating processes. For example, in Theorem 5.4 we only require that the conditional quantiles are a linear function of the past, which is true for AR(p) processes and i.i.d. data. This is less restrictive than (Angelopoulos et al., 2024), which only considers the i.i.d. setting. \n\n\nExamples 3.1, 3.2, and 3.3 all satisfy the linear model assumption, and each has a description of when it is well-specified (for the guarantees of Section 5 to apply). Our experiments focus on these three examples, where we find that 3.2 and 3.3 perform the best. Algorithm 1 does allow for models that do not satisfy our assumptions (e.g. nonlinear), but these do not enjoy the same stochastic theoretical guarantees, which are a crucial part of our contribution. We believe that extending our guarantees to more complex model classes that could provide further practical benefits is a promising area of future research, and we will make this point clearer in the final version.  \n\n**What are the list of contributions this paper is claiming? is there also any algorithmic contributions? or it is mainly analyzing the online gradient descent on pinball loss under different assumptions and different notions of coverage?**\n\nConcretely, our contributions are:\n- A new algorithm for online conformal prediction that allows for conformal predictors beyond scalars as in ACI.\n- Theoretical guarantees showing that our algorithm always achieves\n  -  marginal coverage,\n\n    and under appropriate stochastic assumptions: \n  - conditional coverage when well-specified\n  - relaxed conditional coverage when mis-specified.\n- Experiments spanning 17 datasets and a pre-registration to compare our method with existing alternatives and provide evidence for the empirical benefits of our algorithm.\n\nAs previously discussed, the algorithmic contribution is to extend the model for the conformal predictor beyond a single scalar parameter (as in ACI) to parametric functions, and specifically for our theoretical results: linear functions of feature maps. This new algorithm can adapt to stochastic data, where it enjoys strong convergence guarantees both when well-specified and mis-specified. While our algorithm can replicate SQT as a special case, it encompasses a larger family of procedures and is thus not equivalent to exploring the behavior of existing algorithms under different assumptions. Moreover, our notions of coverage are not just different, but more general and stronger: we satisfy the standard marginal coverage property in the adversarial setting, but also a notion of conditional coverage when the data is stochastic. This has not been explored in past work beyond the i.i.d. setting.", "claims_and_evidence": "All the claims are backed by meaningful theorems and experiments.", "methods_and_evaluation_criteria": "The evaluations make sense to me.", "theoretical_claims": "The theoretical claims and proofs sound reasonable to me.", "experimental_designs_or_analyses": "I have not checked all the details of the experiments, but from a high level perspective, everything makes sense.", "relation_to_broader_scientific_literature": "The online conformal prediction is a very important and active area of research, as often time in practice there is a need to do uncertainty quantification in an online fashion. Even though conformal prediction can be extended fairly easily to the adversarial setup, but the theoretical guarantees of the form of long run marginal coverage are very weak and could be somewhat misleading. This work make progress toward offering stronger guarantees, which could be of interest in real world applications, providing a more robust and interpretable uncertainty quantification.", "essential_references_not_discussed": "A very similar notion of conditional coverage has been previously discussed by [1], in a stochastic iid batch setting, named mean squared conditional error.", "other_strengths_and_weaknesses": "The paper needs improvement in the presentation, particularly when presenting the algorithm. The algorithm suddenly appears without motivating or hinting toward what are the algorithmic principles behind it. To that end, it is not obvious what is the novel/new tweak to the algorithm beyond just running online gradient descent on pinball loss, which is the core algorithm in the literature.", "other_comments_or_suggestions": "In the current version, the organization of the assumptions needed for the theoretical argument is hard to navigate. It's good to state the assumptions once and assign numbers (or letters to them), assumption 1, assumption 2, ..., and then reference to them in the theorem statements. This will improve the clarity of the theorems. That being said, it is also good, to discuss whether such assumptions are conventional and/or how restricting they are. (Though I appreciate the three examples given, but it is also good to point out some examples, which might be of importance in practice, but your assumptions don't hold then.)", "questions_for_authors": "What are the list of contributions this paper is claiming? is there also any algorithmic contributions? or it is mainly analyzing the online gradient descent on pinball loss under different assumptions and different notions of coverage?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V5T0sDL0jy", "reviewer": "Reviewer_cZQF", "summary": "This paper introduces a conformal inference algorithm in the online setting that achieves both long-term coverage guarantees in adversarial settings, as well as expected coverage (conditioned on the past sequence) that converges to the desired coverage rate in certain stochastic settings. Many existing online conformal prediction algorithms apply some form of online gradient descent on the $(1-\\alpha)$-quantile loss, on either a (single-dimensional) prediction of the quantile or non-conformity threshold for the current time-step. The algorithm presented here generalizes this approach by instead performing OGD on a richer parameter class $\\Theta$, and then computing the non-conformity threshold $q_t$ as a deterministic function (called the conformal predictor) of the current iterate $\\theta_t$. \n\nThis algorithm inherits the long-term coverage guarantees of prior work by bounding the outcomes of the conformal predictors (analogous to directly bounding the predicted quantiles / thresholds). In stochastic settings, they define the notion of a process being well-specified if a single parameter in $\\Theta$ can correctly predict the quantile that minimizes expected quantile loss across all rounds. In such (or similar) settings, with appropriately chosen learning rates the algorithm converges to this parameter, thus recovering an expected coverage that converges to $1 - \\alpha$, with finite-sample guarantees if a batched version of the algorithm is run. When $\\Theta$ and the set of conformal predictors are chosen appropriately, well-specified processes include more than just IID settings (such as autoregressive processes).   \n\nThe authors run experiments with several datasets, showing that their algorithm performs on par with existing methods in the adversarial setting, while achieving better performance in terms of quantile loss and set size when there is more of a linear correlation between the predicted parameter and the appropriate quantile.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**I couldn’t find the long-term coverage rate reported for any of the experiments...I would have liked to see the trade-off it has when it comes to long-term coverage.**\n\nAt this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing], we have attached additional experiments to describe both (1) long-run coverage across several methods, and (2) the trade-off in terms of the learning rate for LQT. For (1), we observe that all methods converge rather quickly, and for (2), we observe that indeed there is a slower convergence for more quickly decaying learning rates. \n\nIn general, we do not report the long-run coverage because all methods achieve it. We also point out that Table 6 in the appendix shows that in all but 1 instance, the proposed algorithms (and baselines) achieve at least 0.87 long-run coverage when the target is set to 0.9. The baselines achieved tight marginal coverage since we tuned their hyperparameters on the test set.\n\n**There seems to be a tradeoff in terms of the stochastic and adversarial coverage guarantees when it comes to setting both the batch size and the set of learning rates, so the optimal rates of both cannot be achieved simultaneously. This is understandable and seems like a necessary tradeoff but in terms of application what approach would be taken to decide which algorithm to use? In unknown settings / sequences, it seems like one would want to set the parameters so that we achieve non-trivial long-term coverage (assuming adversarial), but this would have worse convergence rates than the other methods if you also wanted non-trivial guarantees of the stochastic variety.**\n\nWe thank the reviewer for their appreciation of our work.\nWe offer three answers to the tradeoff question:\n- The batch size and learning rate decay are hyperparameters that can be tuned on validation data, as we have done with the magnitude of the learning rate for our experiments. We sought the best performance on the quantile loss, given a constraint on the long-run coverage, but these heuristics can be changed to fit the practitioner’s goals.  \n- Domain-specific knowledge, if available, can help guide this choice. If the well-specified assumption is reasonable, or the errors happen to be linearly correlated often, then faster rates of decay are preferable to speed up convergence, while constant learning rates will provide the tightest coverage when the data is fully adversarial.\n- Choosing intermediate rates of decay (i.e. $\\Theta(t^{-0.6})$ as in the paper) allows us to attain both long-run coverage and consistency under well-specification, albeit at slower rates. Across our experiments, we have found this (and small batch sizes) to be a safe choice. We think these hyperparameter questions are important, so we have been careful to empirically validate this intuition through the preregistration.\n\n**As the authors mention, to achieve optimal convergence rates for coverage in the stochastic setting, we set the learning rate in a way that achieves a vacuous bound on long-term coverage in the adversarial sense (and vice versa). Did you think about the settings where you achieve these guarantees at the same time (though not at the optimal rates)?**\n\nOur results apply to a range of learning rates $\\Theta(t^{-c})$ for $c \\in [0,1]$, not just the $\\Theta(1/t)$ learning rates attaining optimal convergence rates in the stochastic setting and $\\Theta(1)$ attaining optimal long-run coverage rates in the adversarial setting. Choosing $c \\in (0,1)$ thus allows us to attain both long-run coverage and consistency under well-specification asymptotically, albeit at non-optimal rates.\n\n**Section 5 mentions that the finite sample rates are achieved with a particular batch size m and I didn’t get into the details of this proof – could the authors clarify what the relationship between m and the constant C’ in Theorem 5.4 is? Is m a function of T?**\n\nThe batch size m is not a function of T. It should be chosen so that the corresponding minimum eigenvalue in each sample covariance matrix has a sufficiently large conditional expectation. In Lemma 5.3, this just leads to a batch size of at least 2. The batch size m is constant, and the constant C’ increases with m. \n\n**How was the learning rate set for the decaying version of LQT in the experiments? Did it decrease at a $O(1/t)$ rate or was it slower to also achieve a non-trivial long-term coverage convergence rate?**\n\nThe rate of decay for our experiments is $\\Theta(t^{-0.6})$ following Angelopoulos et al. (2024). This is indeed to ensure non-trivial long-run coverage. The only exception is the synthetic experiment in Appendix B3 where we use the optimal $\\Theta(1/t)$.", "claims_and_evidence": "The claims are all proved and there is sufficient evidence (in particular the experiment registered by the authors themselves) that their algorithm shows improved performance over prior ones.", "methods_and_evaluation_criteria": "Yes, it seems fine.", "theoretical_claims": "I only briefly looked at most of the proofs, apart from Theorem 4.1 and Lemma 5.2 I looked at completely which both look sound.", "experimental_designs_or_analyses": "The experiments are fairly extensive. However, I couldn’t find the long-term coverage rate reported for any of the experiments. A plot showing the convergence rate to the desired coverage across the different methods would have been interesting. Also since LQT with a decaying learning rate is optimized for the stochastic setting, I would have liked to see the trade-off it has when it comes to long-term coverage.", "relation_to_broader_scientific_literature": "This paper has close connections with much of the work using OGD with pinball loss to obtain conformal-type coverage guarantees in adversarial settings, starting with the paper that introduced ACI (Gibbs et al 2021) and pointed out the connection (though not directly through no-regret guarantee), and then subsequent work that built on it with slight modifications (Bhatnagar et al. 2023, Gibbs & Candes 2022). This work follows a very similar idea, the main departure as I’ve understood is noting that in stochastic settings where there is a single parameter that optimizes expected coverage (well-specification), convergence to this parameter is possible using an appropriately chosen sequence of learning rates, and when a richer class of parameters than just the set of possible non-conformity thresholds is used, there are more settings in which the above well-specification property becomes true.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths:\n\nThe most interesting aspect of this paper for me is the idea of using higher-dimensional iterates to map to non-conformity thresholds, and performing gradient descent on these iterates rather than on thresholds directly. Turning the online conformal-prediction problem from one where we predict a one-dimensional threshold into one where we predict a higher-dimensional vector that may encode richer information but has a direct connection to the thresholds + coverage, through the conformal predictors $q_t$ at each time-step is clever. It generalizes the prior algorithms in this area in a meaningful way, and opens the possibility of using other kinds of conformal predictors to expand the collection of settings where this well-specification property holds. \n \nWeaknesses:\n\nThere seems to be a tradeoff in terms of the stochastic and adversarial coverage guarantees when it comes to setting both the batch size and the set of learning rates, so the optimal rates of both cannot be achieved simultaneously. This is understandable and seems like a necessary tradeoff but in terms of application what approach would be taken to decide which algorithm to use? In unknown settings / sequences, it seems like one would want to set the parameters so that we achieve non-trivial long-term coverage (assuming adversarial), but this would have worse convergence rates than the other methods if you also wanted non-trivial guarantees of the stochastic variety.", "other_comments_or_suggestions": "As the authors mention, to achieve optimal convergence rates for coverage in the stochastic setting, we set the learning rate in a way that achieves a vacuous bound on long-term coverage in the adversarial sense (and vice versa). Did you think about the settings where you achieve these guarantees at the same time (though not at the optimal rates)?", "questions_for_authors": "1.\tSection 5 mentions that the finite sample rates are achieved with a particular batch size m and I didn’t get into the details of this proof – could the authors clarify what the relationship between m and the constant C’ in Theorem 5.4 is? Is m a function of T?\n2.\tHow was the learning rate set for the decaying version of LQT in the experiments? Did it decrease at a O(1/t) rate or was it slower to also achieve a non-trivial long-term coverage convergence rate?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EsXZPnQDcs", "reviewer": "Reviewer_Ve1r", "summary": "The paper proposes an online conformal prediction method that integrates stochastic optimization to improve coverage guarantees. It claims existing methods use bang-bang control and lack time-conditional guarantees. The proposed method supposedly achieves better theoretical guarantees and outperforms baselines in 15 datasets, including a pre-registered electricity demand forecasting task.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments. We first provide a few general remarks. \n\nOur work provides stronger guarantees than standard online conformal works, by offering not just the standard adversarial marginal guarantee, but also a stronger conditional one when the data is non-adversarial. Crucially, our algorithm is adaptive when the process is non-adversarial. Adaptive and optimistic algorithms have been effective solutions in several areas of machine learning, such as online convex optimization and reinforcement learning.\n\n\n**Claims & Evidence**\n\n1. This is not a misinterpretation of online conformal methods when we take scalar quantile tracker (SQT, Example 3.1) updates to be controller actions. The SQT system, with $\\eta=1$ and $S_t = 0.1$ for all $t$ for simplicity, behaves precisely like a bang-bang controller with on signal = +0.9, off signal = -0.1, and set point = 0.1. Namely, if the state ($q_t$) is below the set point (0.1), the controller will always output the on signal (+0.9), and it will output the off signal (-0.1) otherwise.\n\n2. The batch version of our algorithm is fully compatible with the standard online conformal prediction setting. In the batched algorithm, the conformal predictor’s parameter is updated after every m (the batch size) steps, but *the prediction set at each time t is always generated immediately after the covariate X_t is observed.*\n\n3. We state that one can trivially obtain the guarantee “by *alternating* between $q_t = \\infty$ and $q_t = -\\infty$.” The thresholds should not always be $\\infty$ or $-\\infty$ as this would indeed lead to error rates of 0 or 1, respectively. \n\n4. The main purpose of this paper is to show that we can develop online conformal algorithms that enjoy strong guarantees for stochastic processes *while maintaining adversarial guarantees*. The only asymptotic part of the paper is Theorem 5.1, and this is in the analysis of the algorithm. Theorems 4.1, 5.4, and 6.1 are finite-sample guarantees for our algorithm. \n\n5. Our theoretical guarantees extend beyond well-specified models – we devote Section 6 to the mis-specified setting and preserve the adversarial coverage guarantees with no such assumptions. Our linear model assumption represents a generalization over methods such as ACI, which only considers scalars, and our experimental results across 17 datasets, along with our pre-registered experiment, suggest this generalization leads to significant performance improvements.\n\n**Experimental Designs Or Analyses**\n\n1. We have adapted the code provided by the authors of [2] to compare with our method and baselines on the preregistered ERCOT data. The algorithm provided in [2], AgACI, comes with several aggregation strategies, and we provide results at this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing]. \nThese all achieve marginal coverage, but the set sizes and quantile losses are all larger than every method appearing in Table 1. We also point out that AgACI is not proven to achieve long-run coverage and does not provide theoretical guarantees. \n\n2. We have attached these figures for our main pre-registered dataset and several methods at the link above (Figure 1 contains essentially this figure, we also attached analogous figures for the ACI and PID(theta) baselines for comparison).\n\n**Due to the lack of essential figures ... but did not find them.**\n\nPlease see the comment above.\n\n**Additionally, I read through the related work section ... auto-regressive case.**\n\nThank you for the suggestion, we will add a discussion of [2] to the final version.\n\n**Other Comments Or Suggestions**\n\n1. The parameter that we refer to here is the threshold, not the learning rate, which is instead a hyperparameter. \n\n2. In spite of the reviewer’s comments, we have not identified any technical errors. The reviewer, as far as we can tell, also does not seem to identify technical errors in our theoretical or experimental results. While we are sure there are typos that we have missed, it seems unreasonable to ask for more (on the technical side) than correct proofs and pre-registered real-world experiments.\n\n    In Section 2, we define “right thing” formally– always achieving the adversarial guarantee (1) while also achieving (2) when possible. We will clarify this statement in the final version. \n\n     We would be happy to clarify if anything about the notation $\\\\{(X_t,Y_t)\\\\}_t$ is unclear. \n\n3. We have been careful about dropping the argument to the conformal predictor when clear from context. If there is any instance that caused confusion, we would be happy to clarify. \n\n**Since the main claim of the paper has a major flaw, along with an inaccurate theoretical framing, I don't think requesting additional experiment results would be helpful.**\n\nDespite the reviewer’s comments, we have not identified any “major flaw” or “inaccurate theoretical framing”. Perhaps the reviewer can elaborate on what these refer to.", "claims_and_evidence": "The paper may inflate its novelty, rely on strong assumptions, and adopt a relaxed **batch** online setting. Moreover, it misuses a lot of basic conformal inference terminology and misinterprets existing works.\n\n1. The claim that existing methods resemble bang-bang control is misleading. \n\n    Actually, existing online conformal inference methods are variants of online gradient descent (OGD)[1], instead of a \"2 step on–off controller that switches abruptly between two states\". This is a fundamental misinterpretation of current online conformal inference methods.\n\n2. Online setting vs batched online setting.\n\n  From the abstract, the paper focuses on modeling data dependency in online conformal prediction. However, in the methodology, it shifts to a batched online setting, which is an obvious relaxation of the pure online setting.\n\n3. In Eq. (1), the authors claim the ACI guarantee \n\n    $\\left|\\frac{1}{T} \\sum_{t=1}^{T} \\text{err}_t - \\alpha\\right| = o(1)$, can be obtained by trivially setting $-\\infty, \\infty$ threshold. This is unclear, as the target error rate is $\\alpha$, not $0$.\n\n4. intertwined theoretical contribution\n\n    While the title of the paper is 'Online Conformal Prediction,' the proposed methods are an intertwined combination of conformal inference and asymptotic methods with strong model assumptions. Notably, conformal prediction is unique in its finite-sample guarantee and distribution-free nature. It difficult to discern the main purpose of this paper.\n\n5. Impractical assumption of well-specified models and conformal predictor is linear in its parameter.\n\n    The theoretical guarantees assume well-specified models and, moreover, a linear conformal predictor. This is highly impractical and further proves the paper's overstatement of its contributions.\n\n\n[1] Ramalingam, Ramya, Shayan Kiyani, and Aaron Roth. \"The Relationship between No-Regret Learning and Online Conformal Prediction.\" arXiv preprint arXiv:2502.10947 (2025).", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "I did not check the correctness of the proofs because of the above issues.", "experimental_designs_or_analyses": "1. Since the main novelty of the paper is claimed upon the modeling of the data dependency and auto-regressive cases, the authors should compare with baseline in [2]. [2] handles time series with general dependency and auto-regressive case. \n\n    However, the model does not include it in the baselines.\n\n2. Lack of essential 'sets vs time step' figure. \n    The paper contains no figures of prediction sets visualization for either its method or the baselines, which are essential in an online setting.\n\n[2] Zaffran, Margaux, et al. \"Adaptive conformal predictions for time series.\" International Conference on Machine Learning. PMLR, 2022.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Most of the related works are mentioned, but the discussion lacks depth and contains fundamental misunderstandings.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "There are lots of misinterpretation of conformal methods and ambiguity in the presentation. For example, \n\n1. \"The first algorithm to propose this approach, ACI, constructs confidence sets using a single parameter that governs their level of conservativeness.''\n\n    In fact, in ACI, the choice of the parameter $\\gamma$ creates a trade-off between adaptability and stability. A larger $\\gamma$ induces greater volatility in the realized coverage. However, \"conservativeness\" in conformal prediction refers to the size of the prediction intervals, which is a distinct concept.\n\n2. Despite the technical errors through the whole paper, the grammar is also cumbersome with ambiguous statements. For example,\n\n    \"so that we do not rely on (likely invalid) modeling assumptions, but **which can in fact do the “right thing,”** adapting to underlying structure when it exists.\"\n\n    {$(X_t, Y_t)$}$_t$\n\n3. The paper overuses $q_t$ to denote both the threshold and the conformal predictor, which may cause confusion.", "questions_for_authors": "Since the main claim of the paper has a major flaw, along with an inaccurate theoretical framing, I don't think requesting additional experiment results would be helpful.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2am1z0gvKh", "reviewer": "Reviewer_KPdH", "summary": "The authors propose an algorithm for online conformal prediction that achieve both long-run deterministic coverage as well as conditional coverage under stochastic data which is well-behaved. The idea is to train a predictive model of the quantile on the sequence of data. Different results are assumed under different assumption one model well-specification and data generating distributions. The approach is shown to reduce the set prediction set size and cumulative loss.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work.\n\n**However, I couldn’t find any long-run coverage results in the tables in the main text.**\n\nThe long-run coverage for all the methods in Table 1 is at least 0.87 - we will make this clearer in the final version. We have also attached plots showing the long-run coverage rates on the preregistered ERCOT data at this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing], where we see that all methods converge rather quickly. We have also attached plots showing the long-run coverage tradeoff for LQT in terms of the learning rate, for ERCOT data.\n\n**I don’t see any weaknesses in the existing approach, other than the fact that the current experiments lack results comparing long-run coverage.**\n\nPlease see the comment above.", "claims_and_evidence": "Yes, the developed theory is convincing and the results are clearly presented.", "methods_and_evaluation_criteria": "Yes, the proposed algorithm based on the estimation of the NC scores is thoroughly evaluated. In particular the algorithm’s benefit is shown to have better prediction set size and cumulative loss. However, I couldn’t find any long-run coverage results in the tables in the main text.", "theoretical_claims": "I did not have checked the proof of the theorems.", "experimental_designs_or_analyses": "I’ve reviewed the experiments in the main text, and they are sound; however, I could not find any results regarding adversarial coverage", "relation_to_broader_scientific_literature": "The results are well-connected to existing literature and the Appendix A does a good job at providing an overview of existing results in online calibration and stochastic optimization.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is original in that it proposes a new algorithm for online conformal prediction, achieving both long-run deterministic coverage and conditional coverage under well-behaved stochastic data. The core idea of the algorithm is to train a predictive model of the quantile based on the data sequence. This approach is novel, and, to the best of my knowledge, the asymptotics of online coverage have only been explored in i.i.d. settings for standard ACI [Online Conformal Prediction with Decaying Step Sizes] or localized ACI [Localized Adaptive Risk Control]. I don’t see any weaknesses in the existing approach, other than the fact that the current experiments lack results comparing long-run coverage.\n\n\n## update after rebuttal: My score remains positive and unchanged after the rebuttal.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a family of algorithms for online conformal prediction that provide long-run coverage guarantees in the adversarial data setting, as well as consistency guarantees in the stochastic setting. While existing work, such as that of Angelopoulos et al. (2024), has also proposed online conformal prediction algorithms with guarantees under both adversarial and stochastic setups, the framework developed in this paper allows for handling potentially non-i.i.d. stochastic data. The core idea is to consider a parametric model for the conditional quantiles. Both the well-specified and misspecified cases are analyzed.

Such an explicit parametric modeling approach, though classical in many other areas in statistics and learning, actually leads to solid contributions to the field of conformal prediction. All reviewers are positive about this work, except Reviewer Ve1r who is concerned about the presentation. Hence, I recommend acceptance of this submission. 

It would be beneficial to discuss whether the best-in-class-type guarantee in the misspecified case is an unavoidable feature of the parametric modeling approach, given that guarantees of this type do not appear in the work of Angelopoulos et al. (2024) for i.i.d. data.
Decision: Accept (poster)