The Relationship Between No-Regret Learning and Online Conformal Prediction
Authors: Ramya Ramalingam
Shayan Kiyani
Aaron Roth
Venue: ICML 2025 poster (2025)
Keywords: Conformal prediction
no-regret learning
online gradient descent
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: Simple algorithms for online conformal prediction with group conditional guarantees.

Abstract: Existing algorithms for online conformal prediction---guaranteeing marginal coverage in adversarial settings---are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between *threshold calibrated* coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the *follow the regularized leader* family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes (2021).

The Relationship Between No-Regret Learning and Online Conformal Prediction
Ramya Ramalingam"
Shayan Kiyani" Aaron Roth
Abstract
ate over for even moderately large label spaces. But key insight of the conformal prediction literature (see e.g. (Angelopoulos & Bates, 2021)) is that given an arbitrary non-conformity score
Existing algorithms for online conformal vrediction-guaranteeei marginal coverage in adversarial settings-are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i..d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the regularized leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi group generalization of the ACI algorithm of Gibbs& & Candes (2021).
X y + Rzo. there is 1- dimensional family of nested prediction sets defined as (x) = {y E y f(x, y) S } that we can optimize over, and - simply by adjusting т, we can obtain marginal cover- age at any desired rate q E (0, 1). If there is data distribu- tion D, marginal coverage at rate of q corresponds the guarantee that Pr(x.))~Dly C+) = Stronger guar- antees of groupwise conditional coverage and (threshold- calibrated) "multivalid" coverage have also been recently developed (Jung et al., 2021; Gupta et al., 2022; Bastani et al., 2022; Jung et al., 2023; Noarov et al., 2023; Gibbs et al., 2025), which ask for coverage hold conditionally various events. These methods involve learning thresh- old model T X + R, and producing prediction sets of the form C+ = {v f(x < )- Group conditional coverage starts with a collection of groups 91.... IK rеp- resented as indicator functions 9i X' - {0, 1} (which can be arbitrary and intersecting) and asks that (x [y E C+(x) (z) 1] = q for each group 9.. Multivalid coverage asks that the prediction sets simultaneously sat- isfy group conditional coverage while also being thresh- old calibrated i.e. it further conditions on the thresh- old value 7(x) = v (in a manner similar to calibration), and asks that for all groups 9r and all threshold values u: E(z,y)=D|B bly E C, (z) = 1, T(x) = v| q. The algo- rithm proposed by Jung et al. (2023) for obtaining groupwise coverage over a set of groups learns r(x) by minimizing pinball loss over the class of línear combinations of group indicator functions.
1. Introduction
In prediction problems over label space D, a popular method for quantifying uncertainty is to produce predic- tion sets C(x) y that contain subsets of the label space. Given features æ, the intended semantics of C(x) is that true label y will fall into the prediction set (i.e. will covered by the prediction set) with some specified prob- ability, say 90%. A-priori producing prediction sets is very high dimensional problem: there are 2 possi- ble prediction sets, which becomes intractable to enumer-
It is also possible to obtain coverage guarantees in online adversarial settings in which there is no distribution D, but instead an arbitrary sequence of examples (æ,, y:) that ar- rive sequentially. Here we ask for empirical coverage the threshold (or function) тe can now be updated over time, and marginal coverage over T' rounds corresponds to the requirement that 1/7 I/7 1 [y, E (xx)) q. Group- wise and multivalid coverage can be similarly defined in the sequential setting. Gibbs & Candes (2021) and Gupta et al. (2022) independently studied coverage in online adversarial settings and proposed quite different algorithms. Gibbs Candes (2021) gave very lightweight algorithm which
Department of Computer Science. University of Pennsylvania. Correspondence to: Ramya Ramalingam scas.upen..euu>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
implements online gradient descent on the pinball loss, and prove that it guarantees marginal coverage. This algorithm chooses Ti every day independently of the context Zt. They give a custom analysis of the coverage properties of their algorithm, however, and do not derive them from the regret guarantees of online gradient descent. Gupta et al. (2022) (later refined by Bastani et al. (2022)) on the other hand give more complex algorithm modeled on techniques for sequential calibration, and prove that it obtains multivalid coverage with respect to an arbitrary collection of group functions. As it promises groupwise coverage, it necessarily chooses 7r as function of zt. This suggests a number of interesting questions:
external regret not just marginally over the whole sequence of rounds {1. (1..... 7) but simultaneously on each subse- quence S(g.) {t gi(e)) 1} corresponding to rounds on which the examples are members of group g. Algorithms promising no groupwise regret must receive context I2 at each round before they make their prediction specifying which groups the current example a member of. We show that even when the examples (zt, ye) are drawn i.i.d. from distribution D, contextual algorithms obtaining no exter- nal regret (and hence any algorithm obtaining no groupwise external regret) do not necessarily obtain any non-trivial cov- erage bounds - because even in i..d. settings, the context can correlate the prediction and the outcome.
1. If a sequence of thresholds Tr has no regret with re- spect to the pinball loss, does this its own guarantee coverage? Are there circumstances in which it does? Is there a stronger form of regret that does?
Swap Regret We then turn our attention to swap regret, which corresponds to a guarantee of no external regret con- ditional on the value of the threshold played i.e. swap regret guarantee corresponds to guarantee of no external regret simultaneously Swv) = {t: 7 = 4 defined by threshold values v. There exist many efficient algorithms for guaranteeing no swap regret for convex losses (Blum & Mansour, 2007; Foster & Vohra, 1999; Dagan et al., 2024; Peng & Rubinstein, 2024). There also exist efficient algorithms for obtaining group- conditional swap regret for arbitrary polynomially sized collections of intersecting groups (Lee et al., 2022; Noarov et al., 2023). We show that (under mild smoothness assump- tions on the distribution). threshold calibrated coverage is equivalent to swap regret in the sense that any algorithm for guaranteeing no swap regret with respect to the pinball loss produces thresholds that guarantee threshold calibrated coverage at the target rate, and vice versa. This tight connec- tion carries over to group-conditions swap regret group conditional swap regret is equivalent to multivalid coverage over the same group structure. This connection holds even for algorithms that use context. This gives new algorithms for guaranteeing group conditional multivalid coverage.
2. Can algorithms for guaranteeing groupwise regret with respect to pinball loss (c.g. (Blum & Lykouris. 2020: Lee et al., 2022)) similarly be used to give groupwise or multivalid coverage guarantees?
each subsequence
3. Alternately, if the guarantees of Gibbs & Candes (2021) do not follow from the regret guarantee of online gra- dient descent, can we identify a broader class of algo- rithms that offer these guarantees and generalize them to offer multigroup (rather than just marginal) coverage guarantees?
In this paper we provide answers to these questions.
1.1. Our Results
1. REGRET AND COVERAGE
First we consider the relationship between different kinds of regret that a sequence of thresholds 76 can have with respect to the pinball loss objective, and how they correspond to coverage guarantees.
1.1.2. COVERAGE GUARANTEES BEYOND REGRET
External Regret A sequence of thresholds Tı, Tr is said to have external regret if their average pinball loss is no larger than that of the best fixed threshold r" chosen in hindsight. This is the kind of regret guarantee offered by algorithms like online gradient descent and multiplicative weights (Arora et al., 2012). We observe that in adversarial settings, a no external regret guarantee on the thresholds Tı does not guarantee non-trivial coverage (similar observa- tions have previously been made (Gibbs& & Candes, 2021)), I)), but show that it does if the algorithm chooses its threshold independently of any context I; (as ACI does) and out- comes yr are drawn i.i.d. from an unknown distribution D. We then turn our attention to groupwise regret guaran- tees. A groupwise external regret guarantee promises no
We then turn our attention generalizations of the "ACT" guarantee that Gibbs & Candes (2021) prove for online gra- dient descent on the (1 dimensional) pinball loss. Gibbs & Candes (2021) analyze their algorithm by showing that 1) the marginal mis-coverage rate is proportional to the magnitude of the threshold used at the final iterate, and that 2) all iterates (and so in particular the final one) are bounded. We generalize this result in two ways. First, given collection of groups G, we consider multi-dimensional problems in which we minimize the pinball loss of func- tion Te(x) = (0', .g(z)) defined as a |g] (cl-dimesiional linear function of the group indicator functions (mirroring the form of r(æ) used to obtain group conditional coverage in batch settings in (Jung et al., 2023)). We show that if we
2

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
optimize the pinball loss of (1)) using any algorithm from the "follow the regularized leader" (FTRL) family of no- regret algorithms (Shalev-Shwartz et al., 2012) (a family that includes online gradient descent, but also multiplicative weights and many other no regret learning algorithms), then the coverage rate within each group 9i can be bounded as a function of the magnitude of of (the coordinate of the parameter vector corresponding to group i) and the gradient of the regularization function used to instantiate FTRL. This generalizes the bound proven in (Gibbs& & Candes, 2021) for I I-dimensional online gradient descent (which is an in- stance of FTRL regularized by the Euclidean norm). We then prove that when using [g] d-imensiionll online gradient descent for groupwise coverage, it is possible to bound the magnitude of the maximum coordinate of 8 by O(VT) even when the group functions need not be binary, and can be general weighting functions g. X' - [0. This im- plies a O(VT) groupwise coverage bound. We show that this is tight (even in I-dimension) for real valued weighting functions by demonstrating an 2 (((T) lower bound- - but conjecture a better rate for binary-valued group indicator functions. Finally, we perform an experimental evaluation of this algorithm, and compare it to the online algorithm for guaranteeing multivalid coverage given by (Bastani et al., 2022). We show that our method converges faster to the de- sired coverage rate. Further, though our upper-bound on the rate of the maximum coordinate of Or grows with T, empir- ically we see in each experiment (using binary groups) that it grows much slower and remains very small over the full transcript. We conjecture (but cannot prove) that for binary groups, the norm of Or can be bounded by much more slowly growing function of T (or perhaps can be bounded as a function of only k, the number of groups).
groupwise coverage bounds was independently and con- currently discovered by Angelopoulos et al. (2025). An- gelopoulos et al. (2025) develop their bounds as part of an elegant and general theory of gradient equilibrium, whereas we restrict attention to pinball loss and the online coverage problem. We study the more general class of follow the reg- ularized leader algorithms, whereas they restrict attention to online gradient descent.
For some additional related work, please see Appendix B.
2. Definitions
Define a joint feature-label space (X,))). In uncertainty quantification, one of our goals is to learn prediction sets C: X + 2 that satisfy certain probabalistic guarantees. Specifically, for some specified coverage rate q. we would like to produce sets that include the true label with proba- bility q. Conformal prediction simplifies this problem by defining a collection of nested sets parametrized by single variable (call it r) in the following manner:
C+(x) = fu :e):f(a.))) <T
(1)
X' where / : x Rzo can be any arbitrary function, called non-conformity measure. Conformal methods can be viewed as predictors that choose the "correct" values of т. In distributional settings, to achieve an exact coverage guarantee of the form ((.,))) (y E (x)) ~ q, this can be done by using training data to get an estimate i of the q-th quantile of con-oonfrry score values induced by D.
The g-th quantile of a distribution minimizes the expectation of a convex function called the pinball loss, defined as:
pg(f, T) = { q(( - +) { (g ()(r
i <<<
1.2. Related Work
Online conformal prediction was introduced by Gibbs & Candes (2021), who gave the "ACT" (Adaptive Conformal Inference) algorithm, and noted that it was an instantia- tion of I-dimensional online gradient descent on the pinball loss - but that the coverage bound did not follow from the standard regret analysis of online gradient descent. This spurred a number of follow up works that modified re- fined the original ACI analysis (Gibbs & Candès, 2022; Feldman et al., 2022; Lekeufack et al., 2024; Angelopou- los et al., 2024; Bhatnagar et al., 2023), some of them by making explicit connections to algorithms which guaran- tee more refined adaptive regret bounds (Gibbs& & Candès, 2022; Bhatnagar et al., 2023) - but the worst-case coverage bounds are never derived via the regret bounds, which are used make auxiliary claims (such convergence to the true quantile of the loss in stationary or slowly changing environments).
The procedure used in conformal prediction can therefore also be seen as finding an estimate 7 of the true value r that minimizes the expected pinball loss. But in the adversarial setting, there is no longer any distribution over which to es- timate a fixed parameter +. Instead, at each round t, we may be given features x, (if we are in the "contextual" setting) and use it to predict a parameter 7z (and correspondingly the prediction set C².). Then receive the true label yt. In the non-contextual setting we must choose f, without any 2t, solely based on the history thus far. Note that yı E Ct. iff tt 2 T.. Thus, we may view online conformal prediction as a sequential prediction task, where over T rounds,
1. The adversary chooses a joint distribution over contexts T2 E X' and non-conformity score thresholds тę E [0, 1].
2. The learner, given a realized context Fe, makes a pre- diction řt of the score threshold.
Our generalization of the 1-dimensional ACI bounds to
3

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
3. The learner receives realized threshold Tt-
where we define the size of the group Tg
Ei= 34 ft). For a desired coverage rate q É (0, 1), we have groupwise coverage error y with respect to g if [Cov G) -gl S y for all E.
Given a desired coverage level g, the goal is to make predic- tions such that + Ei= ( 2 Te] R q. Note that for simplicity, we abstract away the true label y/ and non- conformity score ft - implicitly, T fe(Te. We assume that all thresholds 72 are bounded in [0, 1]. In prac- tice, non-conformity measures can be normalized to ensure this holds.
Since our setting reduces the problem of building predic- tion sets to one of predicting sequence of real-valued parameters, we may ask, in addition to achieving a coverage guarantee, that the sequence of predictions satisfies cover- age over groups defined by the level sets of the predicted threshold value.
Definition 2.1 (Transcript). A transcript IIr { Ta, f=) denotes sequence of contexts, outcomes and predictions in the sequential prediction setting. Let II" = (X' x [0.1] x [0, 1))* denote the set of all transcripts.
Definition 2.5 (Threshold-calibratte coverage). Given a transcript Il and a desired coverage rate q E (0.1), 1), we have threshold-calibutle if we have groupwise coverage error y with respect the collection of groups 9 = {G, Vr E [0, 1]}, where G, is binary group including all stmes t for which f
coverage with coverage error 7
2.1. Coverage
Definition 2.2 (Coverage, Coverage Error). Given a tran- script Il7 = {11,, Te, 4))==1 the coverage of Hl is de- fined as:
Definition 2.6 (Multivalid coverage). Given a transcript Ily, a set of groups G, and a desired coverage rate E (0, 1), we have multivalid coverage with coverage error y, if we have groupwise coverage error y with respect to the new collection of groups H = {H : VT E [0, 1), G E 9). where Ho, (II, (IT, Je; ft) G4,,, A. -1 7] for all GE GG E [0,
Cov(Ily)= T t=1
1 ml
For desired coverage rate g E (0, 1), we have coverage error y with respect to if [Cov(IIT) - gl 5.
One can examine coverage not just marginally over the transcript, but also over subsequences of the transcript that define groups within the full sequence. These groups may be defined by context, the predicted threshold, or even the past transcript, as long as membership can be determined at the start of the round, as the learner makes prediction.
2.2. Regret
Definition 2.7 (Ø-regret (Greenwald & Jafari, 2003)).
Given a transcript 11, = {(Tr, Te, ft) allowable ac- tion space of predictions A, and a loss function / A x A + R. the regret with respect to the loss function with respect to a strategy modification rule Φ A A is:
Definition 2.3 (Group). A group G : 11' x X x [0, + [0, 1] is mapping from a transcript, context, and threshold to real value indicating group-membership.
( (
If G(I,,, E 1) for all I1, E II*,, , E xxTE E [0, 1]. we call G a binary group. If G(I,, 2, T)) = G(IL, x, 72) for all II, E [T", x E X' and тı, 72 E [0, 1). we call G a prediction-independee group.
For any collection of strategy modification rules 4, we say that Il7 has 4-regrett y with respect to / if (IIl,,,,)) S for all 6 E Φ.
A transcript has external regret if it has p-regret with re- spect to the set of all constant strategy modification rules (of the form o(x) y for all x R), and it has swap re- grer if it has --regret with respect to the set of all strategy modification rules. Existing swap-regret algorithms such as (Blum& & Mansour, 2007) achieve regret guarantees that have a dependence on the size of the action set A. Therefore, though the true parameter values {Tr) are allowed take any value in [0, 1J. we will consider discretized prediction space parametrized by parameter n, i.e. predicted values & can take values only in the set A.. {0, 1/n, 2/n,.... 1), and the set of strategy modification rules being compared to is t,,, the collection of all strategy modification rules Φ : An - An. We can similarly define groupwise external and swap regret given some collection of groups g:
We allow group-membership to be real-valued to be able to model scenarios involving partial or probabalistic mem- bership in a group, but in most cases group- memuershmbership is deterministic, and only binary groups need be used. The value of prediction-independee the prediction being made on that day- in Section 4, our results for group conditional coverage hold only for such groups.
group cannot depend
Definition 2.4 (Groupwise Coverage, Group Size). Given transcript 117 = {(I,, Te, fr) and a set of groups G, the coverage of group G E 9 over Hy is defined as:
1 T To
Cov( G)
Σ
1 2 n. G(II,, 24, f1)
t=1
4

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
Definition 2.8 (f-groupwise regret). Given a transcript Tlr, an allowable action space of predictions A, a loss function A x A + R, and a set of groups G, the regret with respect to the loss function i and group G, with respect to strategy modification rule Φ A - A is:
With this, we can move from a regret bound to a bound on our miscoverage rate. We give a sketch of the proof here, with the full version in the appendix.
Theorem 3.2. Fix transcript Ilr - ((TE, fo))== in a setting without context fi.e. in which there are observable features Ix) and where the sequence of labels is drawn i.i.d. from a fixed distribution, i.e. Tt ~ D for all t E [T]. If "D is (ax, p,r) -smooth, and if Hr has external regret with respect to the pinball loss Pa then the set of predicted thresholds has marginal coverage evror:
(III,,1,0 = Σ (1(f), ((((f)) G.) 24, ft)
For any collection of strategy modification rules o, we say that 1T has d--rrupwise regret y with respect to I if r G) S y for all Φ E o and G g.
[Cov(IIT) al S
2p(r + 2c)
6
To
T
Groupwise external regret corresponds to Ø-regret with re- spect to the set of all constant strategy modification rules, and groupwise swap regret corresponds to P-regret with re- spect to the set of all strategy modification rules. There exist efficient algorithms for obtaining diminishing groupwise external and swap regret for any polynomial action space and collection of groups G (Blum & Lykouris, 2020; Lee et al., 2022; Acharya et al., 2024; Deng et al., 2024).
c² (- 2T
with probability at least 1 - 6xxp
Proof Sketch. We are given an upper-bound on the realized regret with respect to Pq. which with high probability is close the expected regret (using Azuma's inequality). We then bound the sum of squared differences between the optimal threshold 7" (which minimizes simultancously the expected pinball loss and deviation of expected coverage from q) and the predicted thresholds f. using Lemma 3. The smoothness condition implics thresholds that are close together must have similar expected coverages, and another application of Azuma's 's inequality proves that this is (with high probability) close to the realized coverage.
To move between no regret and coverage guarantees, note that it is necessary for the threshold parameters to not be too closely clustered together. Suppose for example we had an empirical distribution defined by (re) that put all prob- ability mass single value a. Then the fixed prediction in An closest to would achieve no swap-regret, but would correspond to coverage over either all rounds or no rounds, thus being bounded away from the desired coverage rate for any q E (0, 1). To avoid this kind of scenario, we intro- duce a smoothness condition that guarantees the parameters we are trying to predict are sufficiently distributed across the support of our probability space.
When we have sublinear external regret, the bound above goes to zero as T increases. But in adversarial settings, there is no such connection between external regret and coverage even in the non-contextual setting.
Definition 2.9 ((a, p, -))sooothhesss. A distribution D E A 1] is said to be (a, p. -mmoohhh if for every pair of values p, q such that 0 < p S q S and lp- <l I 1/r, we have D E [p, 4l] s p. and if p - gl >= 1/r, then PTND|T E [p. all 2 a.
Example 3.3. Define the transcript Hr = {(T,, +t) in the non-contextual setting where the predicted threshold न = 0.4 for odd L and 0.9 for even L, and the adversary chooses Tt 0.5 for odd and T. 1 for even On each day t,, the loss with respect to Pg (for q 0.5) is 0.1, and since the true thresholds distribute evenly over the set (0.5,1) 1}, the best fixed threshold T" in hindsight is the me- dian 0.75 which achieves a loss of every day. Therefore Σi (f, TT) - Pp(T", TT) S 0, i.e this transcript has no regret with respect to pinball loss at the level q = 0.5. How- ever, the predicted threshold is always lower than the true threshold, and so Cov(IlT) = 0.
3. Coverage Guarantees Through Regret
In stochastic settings without context, external regret (under some mild smoothness conditions) is sufficient to obtain marginal coverage. To prove this, we first draw a connection between the expected difference in pinball loss between two thresholds and their absolute difference, using a slightly modified version of Proposition 5 from (Gibbs & Candès, 2022):
In fact, the connection between low regret on a sequence and achieving low miscoverage on that same sequence falls apart even in i.i.d. settings when move to groupwise coverage. Theorem 3.2 is driven by the fact that in non-contextual settings, the prediction made each day is independent of the realized outcome drawn from D. When we introduce groups, we move to the contextual setting. As soon as we allow the threshold to depend on context, we find that external regret
Lemma 3.1. Fix a distribution D. and let T" be the q-th quantile of DD. Then, assuming 'D is an (s)sooh) distribution, for any other threshold T',
or (T" 2
< E, ErwDlPy(T .) x)- (T(T",
2
5

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
no longer implies coverage even in i.i.d. settings because of the correlation that the context introduces between our predictions and the outcomes.
2007) achieve such rates. We can also move from threshold- calibrated coverage regret bounds. The proof is similar in idea to Theorem 3.6, so we relegate it to the appendix.
Define the context space X' = {A, B), and suppose we are interested only in marginal coverage over the group G containing all days. The distribution 'D over (a, v) pairs is defined such that randomize uniformly over contexts (i.e. P(x== A) = P(x = B) 0.5), and non-conformity score function f is such that f(A,.) 0.5, and f(B..) = 1. Then an algorithm A that always predicts a threshold ft = 0.4 when zt = A, and a threshold ft 0.9 when 2t B. simulates the environment described in Example 3.3. Thus A will achieve an expected regret of 0 (which will be arbitrarily close to the realized regret with high probability for sufficiently large T), but always realized coverage of zero.
Example 3.4.
Theorem 3.6. Fix a transcript II1- {(ra, Ta, fe) If coverage with coverage error
It has Yy (at desired coverage rate q). and D, defined by (Telet=r is (a, p. r-)-moothh for each T E An, then the transcript also has swap regret with respect to the loss Pv: such that:
TT2P
r(Ll,, Pq. 3) S 0²²r
for each o E Q, the collection of all strategy modification rules for action set Aq.
and so + grows at a rate faster than T, we achieve sub- linear regret. Applying the same analysis in the context of groupwise swap regret (analyzing subsequences determined by fixed predicted threshold and group inclusion) gives us an analagous relationship between groupwise swap regret and multivalid guarantees.
To make further connections between regret and coverage, we will need to move to stronger guarantees. Low regret subsequences for which a prediction is fixed (which are by definition disjoint) allows us to compare the performance of the optimal quantile on that subsequence with the fixed prediction. Thus, given the empirical distribution over these subsequences are smooth, we can draw an equivalence be- tween chaestold-calibratedd coverage and swap-regret.
Theorem 3.7. Fix transcript IT, and a set of binary groups G. If has groupwise swap regret 7 with respect to the pinball loss Pa and the empirical distributions Da.r defined by the set {Te)u:tr,tee are (a,, p. p.r) rmsoooth then the set of predicted thresholds satisfies multivalid coverage at the level q such that
Theorem 3.5. Fix a transcript T. = {(r,, Tt, TT If Br has swap regret y with respect to the pinball loss Por and the empirical distribution D, defined by the set frttet= is (a,, p. r)r) rmssshh for each т E An, then the set of predicted thresholds satisfies threshold-calibne coverage the level g:
P pr [cov(T[,,H,,r)9ll)
27 P (+
(++22
2 + n
n *
TG a
for each group lG.. defined HG. (s, G(I,, 21, fi) 11 -[+==]] T].
[Cov G-) -9l S P pr +
27
(1 +
V Trar +
Theorem 3.8. Fix a transcript Il, and a set of binary groups G. If HT has multivalid coverage with coverage error (at desired coverage rate q), and DG.r is (a. r)- smooth for each T E An, G E G. then the transcript also has groupwise swap regrel with respect to the loss Pa, such that r(I,,, Pq: Φ, G) S Toy'p for each & E D the collection of all strategy modification rules for action set An, where To is the size of group G.
Sketch. Sketch. bound on the regret of the subsequence defined by all time- steps making fixed prediction т. Due to convexity of the pinball loss function, the true minimizer of the sum of pin- ball losses must be close to the minimizer in the discrete set An, which in turn can be bound closely to 7 using Lemma A.1 and the regret bound. The smoothness condition im- plies not lot of probability weight can be placed in the interval (T) -7,, and so the difference in coverage is also small. Since (7) should achieve the desired coverage rate q. this gives a bound on the miscoverage on the subsequence defined by any fixed prediction 7 (for all T E An).
The swap regret guarantee gives an upper-
ofr
Algorithm 1 Follow The Regularized Leader (pinball loss)
Input: Timesteps T, regularizer R [0,1] + R, loss parameter
for t = 2, . do
Receive from adversary
Choose 0₂ = arg min Σ'=1 40, R(0).
Predict ł; = (0z: 9t)
The full proof can be found in the appendix. Note that if y (as a function of T) grows sublinearly, then the final term in the above inequality vanishes as becomes arbitrarily large. Several existing swap-regret algorithms (Blum& & Mansour,
Receive Ti from the adversary.
Define loss 40 T.) = (0, (op,(((t.gt)) Tx))
end for
6

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
4. Coverage Guarantees for FTRL Algorithms
us whenever we can upper-bound [ by any function that grows sublinearly with T, we get non-trivial groupwise coverage bound. In the following section we do this for online gradient descent, an especially simple instantiation of FTRL. Note that both in this section and Section 5, the analysis for coverage does not go through regret- - hence no smoothness assumptions need be made on the empirical data distributions.
Having established that, in general, external regret guaran- tees with respect to the pinball loss do not imply non-trivial coverage on their own, either in adversarial settings, or in settings with context (as relevant to groupwise coverage) even in the i.i.d. setting, we turn our attention to partic- ular (but broad) class of no regret learning algorithms those in the "follow the regularized leader" (FTRL) family. This class of algorithms includes multiplicative weights, online gradient descent, and many other algorithms. At a high level, an algorithm in the FTRL family receives loss function {(z, y) at every iteration, parameterized by choice of action y by the adversary and choice of ac- tion I E IRd by the learner. The loss is assumed to be linear in x for all choices y of the adversary. An instantia- tion of FTRL is given by a convex regularization function R : RRd + IR, and the action that FTRL plays at every iteration is 2, arg ming Σ ((z.y.) + R(x) - the regularized empirical risk minimizer on the empirical loss distribution so far. Follow the regularized leader can also be used with loss functions f(x, y) that are convex in z. In this case, the algorithm takes as input the linear loss function f(x; y)= = (x. Vz vz((xe,,) v)) - defined by the gradient of the loss function evaluated at the point xe the learner plays at round t. This reduces to the linear case and obtains the same regret bound (see e.g. (Shalev-Shwartz al., 2012)). Online gradient descent is an instance of FTRL regularized by the Euclidean norm; multiplicative weights is an instance of FTRL regularized by entropy; other algorithms follow from different regularization functions.
5. Group Conditional ACI
Algorithms such as ACI ("Adaptive Conformal Inference") (Gibbs & Candes, 2021) can be seen as special cases of the connection between FTRL and coverage guarantees we have shown - in particular the special case in which we ask only for marginal coverage, and use gradient descent with step size 17, which is an instantiation of FTRL in which the regu- larization function R(O)) 2n ||0| 12. We give the "gradient descent" implementation of our algorithm in Algorithm 2.
Algorithm 2 Group Conditional ACI (GCACI)
Input: Timesteps T, number of groups k. coverage target
9. step-size 17 Choose 01 = 0.
for / = 1, 1, ... do
Receive g, from the adversary.
Predict 6 = (0c, g)).
Receive Ti from adversary.
if (0,, 8.) < T: then
0,+1 = 0, + 17 9 ge
(Update A)
else
In this section we study coverage guarantees for algorithms in the FTRL family when actions for the learner are pa- rameter vectors O₂ E R* actions for the adversary are nonconformity scores Te E [0, and the loss function is (().. TT) - the pinball loss (at target quantile v) of the prediction + = (0,,9; with respect to TE. Here Ii E j0, 11 is the vector of group membership for the exam- ple at round I, i.e. given ls rreiction-independer groups (G,.... .G... St.: = G, (TI, .t.. We show that in this setting, for all algorithms in the FTRL family, the miscov- erage rate be bounded as function of the magnitude of the parameter Or and the gradient of the regularization function R(-).
p.41 = 0₂ 17 . (1 11-91 9) g:
(Update B)
end if
end for
We can instantiate our Theorem 4.1 to bound the groupwise miscoverage of Algorithm 2, it is special case of FTRL. Lemma Running Algorithm 2 for any number of rounds T with a coverage target of q for any set of k group func- tions, we uchieve groupwise miscoverage bounded by the following function of 0T+1:
[Cov(Ilr, G.) - -gl S 101+1llo
T
Theorem 4.1. For the parametrization of FTRL given in Algorithm I with regularization function R: : Rdd - IR, for any target coverage rate and any T the resulting transcript 11 is guaranteed to satisfy groupwise coverage for groups G (i E [k6) at the rate:
If we are able to upper-bound the magnitude of the last iterate of gradient descent as a sublinear function of T, we can bound the deviation from desired coverage not just marginally, but groupwise for arbitrary intersecting groups: Lemma 5.2. When Algorithm 2 is run with step-size n (0, 1), for any collection of k group functions, any coverage target q E (0. 1), and every T, the iterate 0r41 has norm bounded as:
[V((0++))lbb T;
[Cov(TT, G.)- g1
The proof is given in the appendix. This theorem tells
110 S 5O(ViT((n) + 1))
7

---

The Relationship Between No- No-Regret Learning and Online Conformal Prediction
Convergenca rate MVP
Convergence rate HVP
Convergence rato of MVP
6.-
PVP
MSP
20-
08
644
64
6.2-
0:2
Resied wwwowwrggee Ait
Convergence rale GCAC)
Cotvergeetcerall GEACI
Convergerea tele
1.5
10-
2.5
Seilted melccveraga
relerweragg
60-
60
1000
1500
2000
102
200
302
560
1000
2008
2500
3083
2000
Time
Time
Figure I: Comparison of convergence rates between GroupACI (GCACI) and MVP for group coverage. Each curve captures the averaged miscoverage over time of a single group. From left to right, the graphs show results on the time series data, the UCI Airfoil Data, and the Folktables data respectively. Note that group size varies within each graph.
Putting these two lemmas together gives us groupwise coverage bound for Algorithm 2 (GCACI):
evaluate MVP in (Bastani et al., 2022). We compare rates of convergence to the desired coverage over all groups. Since the guarantees for our algorithm are more fine grained, and are proven in terms 0 we plot also the L norm of the parameters 0, maintained by Algorithm 2 over time. To achieve our derived O O(VTk/T.) bounds we set the learning rate 1 = for these experiments. We also then empirically investigate the relationship between the rate of convergence to the target coverage rate and the learning rate, by measur- ing the time-step' at which the empirical group conditional coverage for the rest of the sequence falls within of the desired coverage rate, as a function of n,. We set e = 0.01 for all tests. More fine-grained details on how these experi- ments were run are given in Appendix C.
Theorem 5.3. Fix any collection of l group functions laking values in [0, 1] and any target coverage rate q E (0, 1). If run Algorithm for T rounds with step size 1) E (0, 1]. we achieve groupwise miscoverage bounded by:
< (nk 1)
[Cov(Ilz, - () 50
Tm
When we set = 1, this gives us a OVTTk/T,) groupwise coverage error bound. This analysis is tight even for we allow the groups to be real valued.
and pick any coverage target q E 1). The sequence of 1-dimensional weighting functions 9t _ T together with thresholds тr
Theorem 5.4. Let
causes Algorithm 2 to produce parameter vector 0r+1 E ((VT).
We remark that this lower bound construction seems to require real valued group functions. We conjecture that much better upper bound on ||0++1llss is true for binary valued group functions growing much more slowly with (or perhaps even independently of) T. Our experiments support this conjecture, but we are unable to prove it.
Figure 2: ||0:|lo over time for all three experiments, when running GCACI.
6. Experiments
In this section compare the performance of Algorithm 2 with that of the MVP ("multi valid predictor"" algorithm (Bastani et al., 2022), that to our knowledge is the only other method for obtaining non-trivial group-conditional coverage guarantees in sequential adversarial settings. We run experiments on the same collection of datasets used to
Time Series Data We run both algorithms on stock market data from the WSJ daily price data, which used to test ACI algorithm's (Gibbs & Candes, 2021) performance for
Here, time-step is defined as within the subsequence defined by a group, not the full sequence.
8

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
312
125
334
175
10
Figure 3: Convergence rate of GCACI as function of the learning rate n) Each plot measures (across different chosen learning rates) the earliest time-step at which coverage for each group is within e = 0.01 of the desired coverage for the remainder of the transcript.
marginal coverage. As in (Bastani al.. 2022), we define 20 groups, where group includes data from time-step & iff = 0 (mod i), and introduce artificial noise to the data to get variability in scores based on group membership.
converges as function of the learning rate. We see that expected, larger learning rates give faster convergence, with the algorithm generally converging most quickly with learning rate of f/ 1. This naturally trades off with the regret guarantees of follow the regularized leader, which are optimized in the worst case when v) = 1/vT and vacuous for constant y).
Synthetic Distribution Shift (UCI Airfoil Data) We run both MVP and GCACI on the airfoil dataset from the UCI Machine Learning Repository (Dua & Graff, 2017). In (Bastani al., 2022), only marginal coverage was tested. Here, we define groups where membership is again defined by time-step, in the previous section. Since the test set is much smaller (N = 564), we define only 6 such groups.
Impact Statement
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.
Natural Distribution Shift (Folktables) Finally, we com- pare performance on a covariate shift problem using 2018 Census data from the Folktables repository (Ding et al., 2021). The data (N 52794) drawn from two different states (CA& & PA) simulate an unknown distribution shift; use non-conformity score defined using quantile re- gression model trained on a separate part of the CA data. We compare performance across all of the nine race groups in the dataset, groups for both sexes, as well as the full group.
References
Acharya, K., Arunachaleswarrnn E. R., Kannan, S., Roth, A., and Ziani, J. Oracle efficient algorithms for group- wise regret. The Twelfth International Conference on Learning Representations, 2024.
Angelopoulos, N. and Bates, S. gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511 2021.
6.1. Results
Figure I compares how quickly the two algorithms are able to achieve the desired miscoverage rate. We see that conver- gence substantially faster for our algorithm - despite the fact that both algorithms have similar O(VT) guarantees for worst-case coverage rates. MVP doesn't even converge fully for some smaller-sized groups. We also find that for GCACI, the O(VT) upper bound on | lxo appears to be very loose, at least in the setting of our evaluation. Figure 2 shows that for each experiment, it remains bounded by a small constant, explaining our superior observed coverage performance - because in our experiments, ||0r|loc remains bounded by small constant at all iterates I, we actually get groupwise coverage rates (1/TT). This supports our conjecture that much better bounds might be possible for binary group structure. Figure 3 plots how quickly GCACI
A Angelopoulos, A. N., Barber, R., and Bates, S. Online conformal prediction with decaying step sizes. In Pro- ceedings of the 41st International Conference on Machine Learning, pp. 1616-1630, PMLR, 2024.
Angelopoulos, A. N., Jordan, M. I., and Tibshirani, R. J. Gradient equilibrium in online learning: Theory and ap- plications. arXiv preprint arXiv:2501.08330 2025.
Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: a meta algorrttg and applica- tions. Theory of computing, 8(1):121-166) 2012.
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Practical adversarial multivalid con-

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
formal prediction. In Advances in Neural Information Processing Systems, 2022.
Gibbs, I., Cherian, J. J., and Candès, E. J. Conformal pre- diction with conditional guarantees. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkaf008, 2025, ISSN 1369-7412.
Bhatnagar, A., Wang. H., Xiong, C., and Bai, Y. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learn- ing, Pp. 2337-2363, PMLR, 2023.
Greenwald, A. and Jafari, A. A general class of no-regret learning algorithms and game-theoretic equilibria. In Learning theory and kernel machines, pp. 2-12. Springer, 2003.
Blum, A. and Lykouris, T. Advancing subgroup fairesss via sleeping experts. In 1 11th Innovations in Theoreli- cal Computer Science Conference (ITCS 2020). Schloss Dagstull-LeibnizZZnnrue für Informatik, 2020.
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. Online multivalid learning: Means, moments, and prediction intervals. 13th Innovations in Theoreti- cul Computer Science Conference (ITCS 2022). Schloss Caaiuuhl-LLiibni-zZeetue für Informatik, 2022.
Blum, A. and Mansour, Y. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Bollerslev, T. Generalized autoregressive conditional het- eroskedasticity. Journal of econometrics, 31(3):307-327, 1986.
Höbert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (computationally- identifiable) masses. In International Conference on Ma- chine Learning, pp. 1939-1948. PMLR, 2018.
Dagan, Y., Daskalakis, C., Fishelson, M., and Golowich, N. From external to swap regret 2.0: An efficient reduction for large action spaces. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1216- 1222, 2024.
Jung, C.,, Lee, C., Pai, M., Roth, A., and Vohra, R. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pp. 2634-2678, PMLR, 2021.
Deng, S., Hsu, D., and Liu, J. Group-wing wise oracle-efficient algorithms for online multi-group learning. arXiv preprint arXiv:2406.05287 052877, 2024.
Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction. In International Confer- ence on Learning Representations (ICLR), 2023.
Ding, F., Hardt, M., Miller, and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Lee, D., Noarov, G., Pai, M., and Roth, A. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35:29051-29062 2022.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http: /aa//aaccivveeee. uci. edu/ml.
Lekeufack, J., Angelopoulos, A. N., Bajesy, A., Jordan, M. I., and Malik, Conformal decision theory: Safe autonomous decisions from imperfect predictions. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pp. 11668-11675. IEEE, 2024.
Feldman, S., Ringel, I.., Bates, S., and Romano, Y. Achiev- ing risk control in online learning settings. arXiv preprint arXiv:2205.09095. 2022.
Foster, D. P. and Vohra, R. Regret in the on-line decision problem. Games and Economic Behavior, 29(1-)):7-35 1999.
Noarov, G. and Roth, A. The statistical scope of multicali- bration. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceed- ings of Machine Learning Research, pp. 26283-263 10. PMLR, 2023. URL https: pttppeeiicceeeeeeoe/eeeepcec.sse mlr. press/v202 htt2///oaro23... .tt.2ml........mm.mmmm.mm.m....m
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2):379-335 3900,,99999,, 1998.
Foygel Barber, R., Candes, E. J., Ramdas, A., and Tibshirani, J. The limits of distribution free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455 482, 2021.
Noarov, G., Ramalingam, R., Roth, A., and Xie, High- dimensional prediction for sequential decision making. arXiv preprint arXiv:2310. 17650, 2023.
Gibbs, I. and Candes, E. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660-1672, 2021.
Peng, B. and Rubinstein, A. Fast swap regret minimiza- tion and applications to approximate correlated equilibria. Proceedings of the 56th Anmual ACM Symposium on Theory of Computing, pp. 1223-1234, 2024.
Gibbs, I. and Candès, E. Conformal inference for online pre- diction with arbitrary distribution shifts. arXiv preprint arXiv:2208. 08401, 2022.
10

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
Shalev-Shwartz, S. al. Online learning and online vex optimization. Foundations and Trends@ in Machine Learning, 4(2):177-14,, 2012.
Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ram- das, A. Conformal prediction under covariate shift. Ad- vances in Neural Information Processing Systems, 32: 2530-2540, 2019.

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
A. Proofs
Lemma 3.1. Fix a distribution D, and let T" be the q-th quantile of D. Then, assuming D is an (ax, p. -mmoothh distribution, for any other threshold T',
or 17-(TT- -T- S - p
and Ps = Pr( E [r', where D. We can compute the expectation (T', py(T", -)] by looking at these three cases separately. When I r', the difference in loss is (1 () - -²)). Similarly, when T 2 r", the difference in pinball loss is q(T"" - 7'). Finally, when 7' ST"
Proof. Assume without loss of generality that r' S r*. Define the probabilitiess pi P( S. p))
PT(T", PT(T', - r) = q( - -') - (1 - --(((=- -)
= = - -T)- - (T' -)
= (1 - () - -T") + (T (T)
This difference in loss is dependent on T, so the conditional expectation in this case is:
Elp,(T', (
(1- (1- - ('
Computing the marginal expectation using the law of total expectation.
(', 7]] 11 (T"
-]] = (1 - ()(F' -T") p2(1)(T* - 7') + ps - 4)(T' - -T") + - -
= =P -)- -²) po(a)() -') + ps(11 -1( -T" -T))
=E((T -s-srr
with the final simplication due to pi + P3 = q, and p2 = 1 - q, by definition of 7" Since D is (a, p, -moothh, we can obtain lower-bound on this expectation by taking a discrete sum over 1/r pieces of the interval (each of which has probability weight at least a... There will be [r(r" r')] such intervals, and over the i-th such interval, 7' 2 i-1 so we get:
Elp,(T', Elp, (T", Or (T" -7')2
2
as desired. The proof for the 7" 7' case is nearly identical.
Theorem 3.2. Fix transcript II, {(T, fo in a setting without context (i.e. in which there are no observable features T4) and where the sequence of labels is drawn i..dd from a fixed distribution, i.e. Tı ~ D for all E [T]. Df is (a, p. -msooth, and if Hy has external regret 7 with respect to the pinball loss Ptp then the set of predicted thresholds has marginal coverage error:
2p(r + 26)
Cov(IIT) g
Ta
T
with probability at least 1 - 6exp
(-27) 2T
Proof. Define the realized loss L Σ (ft, and the loss with respect to any fixed threshold La
Σx. pa T.). The regret guarantee tells us that
L L- S
for -" = m B[[,,] this is the g-th quantile of the distribution D. For 0 S t S T, define the sequence of random
variables X; [[L, adapted to the filtration {1l, tt 2 0}. Note that since [[X [I]]] = Xx,, this sequence is a
martingale. Since X₂ = E E[L] and Xy = L. using Azuma's 's inequality gives us:
2²
Plz - B[ 2 d exx
2T
12

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
Thus obtain bound the difference between expected losses:
E [.] - E. S y +
with probability at least 4 exp
22 27
Using Lemma 3.1 separately for the difference in losses for each time-step,
or (T' - =2)
T
(T' -T)² 2(7 + 2e)
S + 2c
(2)
t=1
Now, define for each round t the expected miscoverage Mt ErED[L ( 2 ri] - Since know T' achieves the optimal coverage q, M₁ Pr(r (*)) (or the interval [r", fr). and due to the smoothness condition, this implies that
M
(r" h1 M2
r'1
pr
pr
Combining with the inequality from (2), we get:
M 2p(7 + 2c)
2p(( + 2c)
Σ
M₁ S VT
a
a
t=1
1 Σ M, S
1ppl + 2e)
T
Ta
using Cauchy-Schwarz. Another application of Azuma's inequality tells us that the average expected miscoverage above is more than e/T away from the realized miscoverage rate with at most probability exp both probabilities, this gives us:
Taking union bound over
2T
(Co((IT)) - - V
2p(r + 2e)
Ta
T
with probability at least 6 exp
27
In the stochastic case, we implicitly make the simplifying assumption that the exact g-th quantile 7' of the distribution D exists. When we move the adversarial setting, this is longer viable assumption, and we must also consider discretization error. The following lemma is discretized version of Lemma 3.1.
Lemma A.1. Given a sequence of parameter values {Ta)T= define the sum of pinball losses L. Et (a, T.) and La = Ei= (b, Ti) respectively, where a = minre.A, Σi= Po(a,, Ti) is the minimizer of the sum of pinball losses over the discretized set An, and is any value in [0, 1]. If the empirical distribution D defined by {T) is (a, p. (.r..rr)ssoo -moooth + & (1 2)
and if Ls - La S then 16 al S
27 Par
Proof. Without loss of generality, assume that a S b. For any fixed E [T], consider the difference AL; = Lb Ti) T), There are three cases to consider. If T3 < min b), then:
AL; = (1 - (b - (a --))))) = (1 (b - a)
Similarly, if max(a, 6} < Tú, then AL; = g(a= - b). For the third case, consider when S T; < b. Then,
AL; = (1 (b (b- T3) 9(T, a) g(a -) b) + (b T:)
Let N1, N2 and N₂ be the number of E [4] falling into each of these three cases respectively. We first estimate N1; since minimizes the sum of pinball losses, it must be one of the two grid-points A,, closest to the value M that minimizes the sum of pinball losses over the continuous interval [0, 1] (since the sum of pinball losses a convex, piece-wise linear function). By definition M must be the value that comes closest to covering of the probability weight over D. The amount of probability weight on M cannot exceed p. and J al $ 1/n. By the smoothness condition on we have
13

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
N1 g < pT/2 prT/n. This implies that (N2 + N₂) (1 -)) S p2 prT/n. Using Lo Lo 7 and
rewriting the difference in loss as Ei=1 ALi.
y 2 N1 - ()(b a) + 44N2(a - b) + +qNasaa - b) +
Σ
(6 - Ts)
RaST.ch
= (b (Ni(1 9) (N22 N₂)) +
Ti)
pT'
prf
2 (b- a)
Σ (b
Ti)
n
Ra
2 pT
prT
Σ
(b - T()
2
where the second inequality comes from the bounds on N1 and N₂ + N3. Using the smoothness condition on D, we can bower-bound the second term by splitting the interval [a, b] into pieces of length 1/r, getting
Tar(b a)²
Σ (b- Ra
r
2
Rearranging, we get
(b 00- <
2 Tor
(7+
pT
+
pr
1b al S
27 Tor
p
1 r
2 n
n
Theorem 3.5. Fix transcript 1I = (1r2, To, +)) IIT has swap regret with respect to the pinball loss Pa and the empirical distribution D defined by the set {Te)t= is (a,, p. -mooohh for each T E An then the set of predicted thresholds satisfies threshold-calibattee coverage at the level q:
Cov([Ir, - - - 2
pr
V
2y T
+
(
1 2 r
+
Proof. Since each predicted value iz is in An, we can rewrite regret via the separate contributions over each prediction value:
rTT,, Pg. 1)
Σ Σ
(t) pp(o(ft)
TEAn CifE
Tr.o
Define the swap function on that, for each T E An, is defined as:
om (m)(T)=
min Σ (T()
r' E.Aa #:
as well as the loss minimizer mapping M : An + 10, 1]:
M(T)
Σ (T( r'E l=f=
min
Note that by definition, since (T) minimizes the sum of pinball losses, it is the q-th quantile of the empirical distribution D, over the set (feles=r. Further, since the sum of pinball losses (as a function of the first argument) is convex, piece- wise linear function, Φm (T) must be one of the two closest grid-points in An to (T), i.e. we have [M(r) - @m 1 - 1/n.
Since T Fr.0m 2 0 for each 7 E An, a total swap-regret of 7 implics that Fr.am S for each T. Using Lemma A.I,
T,ar + P {
2y
(dm (T) - r| s
/
a
14

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
where we define T, = EEer] l = Due to the (a, p. -mooothnes condition over D,, the amount of probability weight on (T) cannot exceed p. and so the number of values N, in {Te)t:ter that M() equals or exceeds satisfies
qT, - p2, S N, I qI, + //. Finally, using the bound on [M( 7| along with the smoothness condition, the
number values the set {1 : f = } between M() and T cannot exceed T. pr (++ + Trar + aa (++ +)) Using the upper bounds of the inequalities,
1 1m sTssT pT,
pr
2y T,ar
2 n
+
lf=
Notice that the left hand side equals Cov(IIT; Gr), where G, is the binary group including all time-steps for which it = T. Thus, performing the same steps using the lower bounds of the inequality and dividing by Tr,
P or 2 2 n
27 Toorr +
{ - 2)
(Cov(IIT, - al
Theorem 3.6. Fix a transcript 11T {(11, Tr, f.)]T== lIT has threshold creeshold-calibrate coverage with coverage error Y (at
desired coverage rate q) and D, defined by (Tilteer (a, p, -mmooth for each T E Ans then the transcript also has swap regret with respect to the loss Pn, such that:
Th²p
(T,, Pq: o)
QrT
for each o E 4, the collection of all strategy modification rules for action set An
Proof. Fix a threshold 7 E An- Let M(r) = min.g (.11] time-steps for which the predicted threshold was т. Note that since by definition M(T is the q-th quantile the empirical distribution D,, it is also the value that minimizes the sum of pinball losses Σ [f 7] Py Tz) We assume without loss of generality that this exact g-th quantile over DD, exists since any other value would get worse coverage (at the rate q), r achieving comparable performance to the true minimizer implies it achieves the same (or better) performance even if the exact q-th quantile does not exist. By the coverage error guarantee,
7) where G, is the binary group including all
P PrED, (r E [M(T), S
or instead [T, (7)), based on their ordering. Using the smoothness condition, we have:
1-M((F) S ?
ar
Thus the regret with respect to the best action in hindsight M(T over the subsequence where only prediction is made be bound:
Fr = max aEAAn l:f==T
Σ
PT(TT, - po(a,
Σ (T(T, Py (M))) (0))))())))) )2))² pr
::f==7
Assume without loss of generality that M(r) T. Define the variables N1, N2 and N₂ as the number of thresholds in the set {Tr)er less than or equal to (T), in the interval (T), and greater than 7 respectively. Since M()) is
exactly the q-th quantile. N1 qT, and N2 + N₂- = (1 - (1- where we define T,, ΣT= 1[ r]. We can rewrite the difference in pinball loss by dividing into these three categories, as in the proof for Lemma A.1, to get:
Σ Tb) - (1 (T - M(7)) - - M(7)) No M(7))
Σ (T-
= - (() - - 2(N2+ + +Na)
Σ (T-T))
taST.<b;ī
22p
S NNa(7 -(()) T, 7pr 7 T,
ar
or a.
15

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
using the smoothness condition and the bound on [M 7| bound the value of Ng. Thus the maximal regret with respect to the best action (on each subsequence defined by fixed threshold prediction) is bounded. Summing across all E An.
Ty²p 2²r
r r(I,, Pq: ②) -
Theorem 3.7. Fix a transcript Nr, and a set of binary groups G. Ir has groupwise swap regret with respect to the pinball loss Pa and the empirical distributions Da defined by the set {Tr (Teteee are (a, p, rmsmooth, then the set of predicted thresholds satisfies multivalid coverage at the level q such that
[Cov(IlT, Ha.)) - 9/55 e pr
2y
L
1 - +
2 n
2
+
|
Ta,ar
+
for each group HG.r defined as Ho.r (Il,, Tr. ft) = G(I,,, Tt, ft) T/.
Proof. We follow a nearly identical approach to Theorem 3.5. Fix a group G E G. The groupwise regret with respect to G can be rewritten via the separate contributions over each prediction value:
r(1,,, Pr: o, G)
Σ
(Pa(Fi.T)) Po (o(ff)) m.)) Gill,, ft)
TEAD :T
ra.
Defining om and M as in Theorem 3.5, we get that
2n
2
(M - 7| S - +
+
+
Ta,aor
where we define Ta., = Exerry 1[ = r] G(I,,, :e: ft) Since the amount of probability weight on M(7) cannot exceed P. we get an upper-bound the group conditional coverage:
Σ 1/2 ST. CI, S gaar + pla. pr + =
27
+ P - +
2
+
n
V
To,oor
and then a similar lower-bound. So,
[Cov Ha.r) - a) < 0 pr
2y + P
20(10 - +
2
+
+
2 n To,or
where HG.r is the group defined such that Ha,, (Il, xy, f.) = G(IL,, Dz, ft) 1[A =].
Theorem 3.8. Fix a transcript II, and a set of binary groups g. II has multivalid coverage with coverage error y (at desired coveruge rate q), and Da,r is (ox, p. r-)ssooth for each swap regret with respect to the loss Pai such that r[Il,, Pq. 6, G) < modification rules for action set An where To is the size of group G.
An, E G, then the transcript also has groupwise TapLP for each & h, the collection of all strategy a²r
Proof. Fix threshold E An, and group G E G. Using exactly the approach in the proof for Theorem 3.6, we can bound the sum of difference in loss, over the subsequence for which group G is active and the predicted threshold was 7:
Σ (pG(T,T) (M()) G(T,,, x4, ft) S Ta, o²
where To,r = EiE' 1lfe- = 7] G(I,, Fz, f.). Summing over all E An, we get
To?2p r²r
r(Te, d. G)
16

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
Theorem 4.1. For the parametrization of FTRL given in Algorithm I with regularization function R Rd IR, for any target coverage rate q and any T the resulting transcript Ty is guaranteed to satisfy groupwise coverage for groups Gi (i E [K] at the rate:
[V((O++1)lls
[Cov(IIT; Gi) -
T;
Proof. Pinball loss convex, and so to apply FTRL, we feed the algorithm the linear surrogate loss E(O, Tp) =
(0, V Vopg((0e, (t), Te)). We can compute:
{(0, m1) = q (0.0)t)
Te > (0c, gt),
(1 ②) (0,gt),
if S (0t: gt)-
The gradient of the loss at round with respect to is therefore:
99t
if T. > g.)
V Vol(H,
{
②) ge.
it S gt).
FTRL with regularizer R plays the action 0, round that solves:
0: = arg min
800, + R(O)
0
First order optimality conditions imply that:
Vel(O,, + V =0
Or equivalently,
VR(0.) =
Σ
99s +
Σ
(q 1)g.
(0,>(0,.)))))
s:T, (0..
1-1
= Σ gala 1|Ts S f.))
Hence we can bound the miscoverage rate for every group i at time T can be bounded as:
[Cov(TT,, G.) - 9/ ||
T
Lemma 5.1. Running Algorithm 2 for any number of rounds T. with coverage target of q for any set of group functions, achieve groupwise miscoverage bounded by the following functiin of OT41:
[cov G.) - 4l $ 11
Tm
Proof. Algorithm 2 is an instantiation of follow the regularized leader as analyzed in Theorem 4.1 with regularization
function R(0)= by 2 We can compute v (((O++)) # Or41. Plugging this into Theorem 4.1 gives the stated bound.
Lemma 5.2. When Algorithm is run with step-size r, E (0, for any collection of group functions, any coverage target q E (0, 1), and every the iterate Or+1 has norm bounded as:
|00+1|lo S O( T/ (nk 11)
17

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
Proof. First, note that since the non-confornity scores are assumed be bounded in [0, 1], must have for every that
T. E [0, 1]. So, if (0t; gt) O, we must also have (0t, 9t) I 7a which triggers Update A. Similarly, whenever (0,, 9t) 2 this necessarily triggers update B. Said another way: if the update A was triggered at round t we know that (0z, gt) < 1,
whereas if update B was triggered, we know that (0,, .t) 2 0. We consider these two cases separately.
Case (Update A triggered); We can compute
10++1112 = 10 12 + 17 11922119 + 2n. 9t)
- 10 2 + 1 n² + 2nq
Case 2 (Update B triggered): Similarly.
|0 = 110.12 + n2 - 11911 2m(11 - () gt)
- |10:112 + n³ ²)²k
As initially |0:1|2 = 0, we obtain:
|10++112 - T (17 max (g. -)²²+ 2nq)
- Tn max 1 1 9)²² 2g)
This immediately gives us a bound on the Loe norm:
|10+t1100 S /Tn n/ max - 24
Theorem 5.4. Let = and pick any coveruge larget q E (0, 1). The sequence of I-dimensional weighting functions Dt TVT-T logether with thresholds = causes Algorithm 2 to produce parameter vector 0r+1 E (((V)).
Proof. Assume that 91 0. Since T, = 1, whenever 0, 9t we will trigger update Assume all rounds up through --1
_ round 1 triggered update A, in which case 02 = 17-77-9 - 9h < 2/t 1. But because we set 9t 2/1-1 we have
that 0: 9t < 1. once again triggering update A. Inductively, update A is thus triggered at every round, and so we have that 0rt1 = 17 q Σt Os S(VT)).
B. Additional Related Work
In parallel line of work, Gupta et al. (2022) introduced the problem of online uncertainty quantification in the form of mean, variance, and quantile estimation, using techniques deriving from the online calibration literature (Foster & Vohra, 1998). Bastani et al. (2022) gave a refinement of their quantile calibration technique to give an online conformal prediction method that gave conditional guarantees of various sorts. Coverage bounds from algorithms of this sort follow from quantiee-calibration arguments.
(Foygel Barber al., 2021) consider the problem of group conditional coverage in conformal prediction and propose running separate algorithms for each group, and for examples that are in multiple groups, using the most conservative threshold amongst each of the groupwise algorithms. (Jung et al., 2021) give the first non-consevvative method for getting groupwise coverage for intersecting groups, by adapting ideas from multicalibration (Héhert-Johnson et al., 2018) to calibrate to moments of the score function, conditional on group membership. (Gupta et al., 2022) give algorithms for group-conditional quantile multicalibration, and show how this can be used to give tight "multivalid" confidence intervals. (Bastani et al., 2022) and (Jung et al., 2023) apply these ideas explicitly conformal prediction. (Gibbs al., 2025) give a variant of the algorithm from (Jung et al., 2023) which gives coverage guarantees in expectation over the calibration set, rather than PAC-style guarantees as in (Jung et al., 2023).
The characterization we give of threshold calibrated coverage by swap regret bounds on the pinball loss mirrors an equivalence between swap regret on the squared loss and (mean) calibration (Foster & Vohra, 1998; 1999). More generally the connection between calibration of different distributional quantities and their corresponding "clicitation functions" was made by (Noarov& & Roth, 2023).
18

---

The Relationship Between No-Regret Learning and Online Conformal Prediction
C. Experiments
Here we provide additional details on the set-up for each experiment. We closely follow the steps described (Bastani al., 2022), which performed experiments on the same datasets to measure the performance of their algorithm MVP for group-conditional coverage guarantees.
C.1. Time Series Data
We replicate the prediction task described first in (Gibbs& & Candes, 2021), for testing the ACI algorithm's 's ability to achieve marginal coverage. which uses AMD stock market data from the WSJ daily price across years 2000-2020. The dataset gives price points {pe) of the stock for T 5283. Using this data, we compute the daily return ra. defined r Pt
P
which correspondingly defines the daily realized volatility t2 r The task is to predict this volatility. Using the predictive model GARCH ((Blllerseev, 1986)), which makes a prediction of the volatility êt the scoring function used on day t is (a v) -y- normalized to ensure scores are always in the range [0, 1J. Then, as in (Bastani et al., 2022), we define the collection of 20 groups [G. where G; includes all time-steps for which 1 (mod i), and introduce artificial noise to group data in the following way- for each time-step we add noise (N0, o,) the return value for each group in G2 that t is included in, where क, is the standard deviation of the original return sequence. We run both GCACI and MVP on this data, asking for a desired group conditional coverage level of q = 0.9. In (Bastani et al., 2022), they show that MVP achieves the desired group conditional coverage while ACI is unable to. Here, we see that GCACI not only achieves group conditional coverage, but converges at much quicker rates than MVP.
C.2. Synthetic Distribution Shift (UCI Airfoil Data)
We run both MVP and GCACI on the airfoil dataset from the UCI Machine Learning Repository (Dua & Graff, 2017), which consists of 1503 instances of NASA airfoil blades; the task is to predict the Scaled Sound Pressure Level (SSPL). In (Bastani et al., 2022), they compare against the performance of the weighted split conformal prediction algorithm of (Tibshirani al., 2019), and test only for marginal coverage. Following their approach, we use 25% of the data to train a linear regression model g : X' R, which defines the scoring function [(r,, v) = [g(x>) - yl- Another 25% of the data is used is, and the final 50% of the data is sampled (with replacement) using exponential tilting each datapoint x is drawn with probability proportional to (x, B)), where we set / = (- (-1, 1, 0, 0, 1) as in (Tibshirani et al., 2019) and (Bastani et al., 2022), representing synthetic covariate shift. The test set is sequenced such that the original (unshifted) data comes first, followed by the shifted data. Then, as in the previous section, we define a set of six groups {G:) where membership is again defined by time-step, i.c. G, includes all time-steps for which & = 0 (mod i). Both algorithms are run with a desired coverage rate q = 0.9.
C.3. Natural Distribution Shift (Folktables)
Finally, we compare performance of MVP and GCACI on a distribution shift problem using 2018 Census data from the Folktables repository (Ding et al., 2021). The task involves predicting individuals' income. We use census data from two different states (California & Pennsylvania) and sample 0.2 of both states to get test set with N 52794 data points. The data is sequenced with all CA datapoints first, giving us unknown distribution shift from natural source. A quantile regression model h X' + IR is trained on 50% of the remaining California data, defining the fixed scoring function f(z. v) = [h(z) - y/. We define 12 total groups, over all nine codes for race available in the Folktables dataset, two groups for sex, as well as the group including all data points. In (Bastani et al., 2022), four of the race groups are omitted due to being very small fractions of the overall dataset- we include even these small-sized groups to illustrate that GCACI is able to converge quickly even for such groups. We run both algorithms with desired coverage rate of q = 0.9.
"Note that though the feature vector x included generically here as an argument in the non-conformity score, the GARCH model typically uses only past volatility data to make predictions for the next time-step in the sequence.
19


Reviews:
[{"review_id": "byDBZvYsUs", "reviewer": "Reviewer_8yW2", "summary": "This paper explores how to make better predictions with reliable uncertainty estimates in challenging, real-world settings—like when data changes over time or comes from many different groups. It focuses on *conformal prediction*, a method that builds a set of likely outcomes for each input, with a guarantee that the true answer falls inside that set a desired percentage of the time (say, 90%). Traditionally, conformal prediction works well in nice, stable environments, but struggles in harder, online or adversarial scenarios. The key insight of this paper is that existing learning techniques based on *external regret* (which just try to do as well as the best fixed action in hindsight) aren't enough to ensure these prediction sets stay reliable—especially when we care about fairness or accuracy across different groups. Instead, the paper shows that a stronger concept called *swap regret*—which says “I wouldn’t have done better even if I had consistently changed certain decisions in a smarter way”—is exactly what's needed to ensure these coverage guarantees hold, even in complex settings. [That's my hand wavy understanding]\nUsing this idea, the authors design a simple and effective new algorithm called GCACI that can adjust its uncertainty sets over time for many groups simultaneously. They prove this method works in theory, and show in experiments that it beats previous approaches by achieving better coverage, more quickly, and with less computational effort.", "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": "Thank you for your detailed feedback! We will try to address your concerns and comments.\n\nFirst, as a clarification: there are two kinds of relationships we develop in this paper - (1) the relationship between the *properties* of no-regret and of conformal coverage guarantees, agnostic to the algorithm used. (2) specific algorithms that are able to achieve both kinds of properties, even if the properties do not imply one another. One of the motivations for this paper was identifying that though external regret and coverage guarantees do not imply each other (i.e. an arbitrary algorithm that achieves no external regret cannot guarantee coverage guarantees, and vice versa), there exist specific algorithms that are able to achieve both properties. GCACI is an example of this - the analysis for coverage does not go through regret. \n\n1. **Smoothness condition on distribution of thresholds:** Smoothness is a mild condition and we can view it either as an assumption on the adversary (a “smoothed analysis” like assumption --- for example, the adversary can pick an arbitrary score which is then perturbed by small amounts of noise), or alternately as a condition that we can enforce ourselves. If we want to enforce it ourselves we simply perturb the scores  from a uniform distribution $[-\\epsilon, \\epsilon]$ before passing them to the algorithm. We then randomize the algorithm’s threshold in this range. This doesn’t require us to make assumptions on the adversary at all. \n\n    Note that it is not possible to draw a direct relationship between coverage and regret without some kind of smoothness guarantee. As you mention, the relationship between regret wrt pinball loss and coverage relies on the non-conformity scores being sufficiently spread out. If, for example, the distribution over scores is a point mass on some value $a$, the only achievable threshold-calibrated coverage rates are 0 and 1 - to achieve low miscoverage for any quantile $q$ in between, some assumption of smoothness is necessary. Similarly, in the stochastic setting, marginal $(1-\\alpha)$-coverage could be achieved with predicted values arbitrarily far away from $a$ as long as $(1-\\alpha)$ fraction of the values were below $a$, but this obviously doesn’t translate into a regret guarantee.\n\n    We also emphasize that the smoothness guarantee is only required for algorithms achieving coverage through swap regret. Our new algorithm GCACI achieves coverage through properties of the class of FTRL algorithms, and thus no assumptions on smoothness need be made. This is an advantage over the MVP algorithm we compare against, which does require it.\n\n####\n\n2. **Power of adversary when smoothness is required:** Since smoothness can be enforced posthoc via the perturbation strategy, we do not typically enforce any kind of constraints on the adversary directly. \n\n####\n\n3.  **Experiments not rich enough:** We included experiments to compare against all the benchmarks described in Bastani et al (2022), which to our knowledge details the only other algorithm for groupwise coverage in adversarial settings. We would be happy to include additional experiments that may be relevant to evaluation, if the reviewer has any particular benchmarks in mind.", "claims_and_evidence": "The core claims are mostly theoretical and comes with formal proofs. The paper essentially provide this:\n\n- External regret is not sufficient for coverage guarantees: counter-example appears in adversarial setting or even iid but with group structure. Instead Swap regret is both necessary and sufficient for coverage.\n\n- Derive new conformal algorithms from no-swap-regret learning and achieve group-conditional coverage", "methods_and_evaluation_criteria": "The evaluations are quite weak and more benchmark could be done with more datasets", "theoretical_claims": "Just skim quickly and did not check in details.", "experimental_designs_or_analyses": "The experiments section can be improved with richer experiments", "relation_to_broader_scientific_literature": "The paper fall into connecting conformal prediction and online learning. Mostly borrow ideas from the latter to improve understanding of the former.", "essential_references_not_discussed": "Adaptive Conformal Inference by Betting by (Aleksandr Podkopaev, Darren Xu, Kuang-Chih Lee)", "other_strengths_and_weaknesses": "The paper is reasonably well written and the core contributions are solid.\n\nThe weakness is mostly the experimental section.", "other_comments_or_suggestions": "NA", "questions_for_authors": "- Your coverage guarantees rely on an smoothness condition on the empirical distribution of true thresholds . This assumption is key for bounding the difference between pinball loss regret and coverage error. Could you clarify how realistic this assumption is in practice, especially in adversarial or highly structured environments where the distribution of may be heavily clustered or even discrete?\nHave you observed situations (empirically or theoretically) where violation of this smoothness significantly affects coverage, and do you foresee ways to either relax the assumption or detect when it may not hold?\n\n- In your setup, the adversary is allowed to choose the sequence of examples (or losses), but the smoothness assumption effectively constrains the sequence of threshold values. How should we interpret the adversary’s power in this setting? Is the smoothness constraint best understood as an assumption on the data-generating process (i.e., nature, not an adversary), or are there adversaries within your model who can adaptively shape  while still satisfying smoothness?\nMore generally, could you comment on the interaction between adversarial flexibility and the structural assumptions needed for regret-to-coverage equivalence?\n\n\n \"## update after rebuttal\"\n\nThe authors provided some more clarifications about the novel contributions, which is nice; However, several points regarding the importance of swap regret and strength of the propositions compared to previous (group) conditional coverage are quite unclear to me. I think the paper would benefit from more rewritting and concret examples. That being said I am globally positive but cannot increase my score to full accept", "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": "FXWVmpMu2x", "reviewer": "Reviewer_obBc", "summary": "This paper explores the connection between online conformal prediction, which aims to construct prediction sets that cover the true labels with a specified probability, and online learning algorithms minimizing the pinball loss, which aim to achieve a certain regret guarantee. The authors show that standard external regret guarantees ensure marginal coverage when the data is i.i.d.; however, they do not provide meaningful coverage guarantees in adversarial settings or multi-group settings. In contrast, when the data distribution is smooth, the stronger notion of swap regret guarantee is \"equivalent\" to threshold-calibrated coverage, meaning an upper bound on one directly implies a corresponding upper bound on the other. Finally, the authors extend the adaptive conformal inference algorithm of Gibbs \\& Candes (2021) to the multi-group setting and demonstrate that the FTRL algorithm ensures group-wise coverage.", "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": "Thank you for your thoughtful and detailed comments! First we would like to note a small change to the statement of Theorem 3.5. It should read: $|Cov(\\Pi_T, G_\\tau) - q| \\leq \\frac{\\rho}{2} + \\frac{\\rho}{rn} + \\sqrt{\\frac{2\\gamma}{T_{G, \\tau}\\alpha r} + \\frac{\\rho}{\\alpha}\\left(\\frac{1}{r} + \\frac{2}{n}\\right)}$.\n\n* The cube in $T_{G, \\tau}$ was a typo. $\\sqrt{\\frac{2\\gamma}{ T_\\tau \\alpha r}}$ on line 705 should be $\\sqrt{\\frac{2\\gamma T_\\tau}{\\alpha r}}$.\n* The result in Lemma A.1. should read $|a-b| \\leq \\sqrt{\\frac{2\\gamma}{T\\alpha r} + \\frac{\\rho}{\\alpha}\\left(\\frac{1}{r} + \\frac{2}{n}\\right)}$, translating to an additional constant term in Theorem 3.5. We explain this below.\n\n####\nAddressing your questions / comments:\n\n1. **Dependence on $\\rho$ and $T_{G, \\tau}$ in Theorem 3.5:** It’s true that $T_{G, \\tau}$ may grow slower than $\\gamma$ for some $\\tau$. However, we think of overall threshold-calibrated coverage as the sum of coverages $Cov(\\Pi_T, G_\\tau)$, weighted by the size of $G_\\tau$. For each threshold $\\tau$, either $T_{G, \\tau}$ grows slower than $T$, and its weighted contribution $T_{G, \\tau}/T$ goes to zero, or it grows on the order of $T$, and Theorem 3.5 tells us that miscoverage goes to zero - so overall threshold-calibrated coverage should converge. We will add this detail in revision.\n    The dependence on $\\rho$ is unavoidable, since exact coverage $q$ comes at the $q$-th quantile of the empirical distribution over thresholds. If a single value is allowed to carry $\\rho$ of the total probability weight, then the closest we may be able to get is $q \\pm \\rho/2$. \n\n####\n2. **Stronger quantitative equivalence result:** The relationship between swap regret wrt squared loss and mean calibration is not in general tight because of choices in how calibration is normally measured (Linfty/L1 norm vs L2 norm). Similarly we don't believe the relationship between quantile calibration and swap regret wrt pinball loss is tight in the metric we give, but there may be another in which it is. We can note this in the revision.\n\n####\n3. **Using threshold-calibrated coverage as a metric:** We agree that it would be interesting to compare the performance of existing swap regret algorithms against MVP using threshold-calibrated coverage as a metric. \n\n    However, one of the key points demonstrated in this paper is that achieving threshold-calibrated coverage is at least as difficult as achieving no swap-regret, which requires more computational overhead than obtaining external regret (no-swap-regret algorithms are based on finding fixed points of various sorts). Thus, there is a necessary tradeoff in terms of algorithmic simplicity if threshold-calibrated coverage is what we want - and we believe that MVP already occupies a good place in the tradeoff space, as a more complicated algorithm with a stronger qualitative bound. But as we see in Sections 4 & 5 (and in experiments), if all we want is group conditional coverage (giving up on threshold calibration), then MVP is overkill - we can get much simpler algorithms with faster convergence to the desired coverage rate. For marginal coverage, ACI already demonstrated this was possible compared to MVP - it is a strikingly simple and efficient algorithm that obtains marginal (not threshold calibrated) coverage. In our work we show that we can recover the same kind of simple, efficient algorithms even with group conditional coverage.\n\n####\n4. **How an optimal learning rate $\\eta$ is chosen:** In both our paper and in ACI, choosing $\\eta = 1$ gives the best rate of convergence towards desired coverage ($O(1/\\sqrt{T}$ for ours, $O(1/T)$ for ACI). The discussion of optimality of $\\eta$ in Gibbs & Candes (2021) is to do with balancing between having quick rates of convergence and having low volatility in predicted thresholds. The larger $\\eta$ is, the quicker coverage converges and the more adaptive predictions are to adversarial shifts. The smaller $\\eta$ is, the less predictions fluctuate round to round. They use this to describe how $\\eta$ may be chosen in conditions where the distribution shift can be measured. Our work inherits the same balance between convergence and volatility, but since we are interested specifically in adversarial coverage we didn’t discuss this in detail. Empirically, we found indeed that the convergence rate improves the closer to 1 that $\\eta$ gets. \n\n####\n5. **Lemma A.1 questions:** We should have the bounds $|N_1 - qT|, |N_2 + N_3 - (1-q)T| \\leq \\rho T/2 + \\rho r T/ n$. The bound of $\\rho T / 2$ is true if $a$ is the exact $q$-th quantile (or the closest value to it). Since $a$ may be at a distance of $1/n$ away from this value, there should be an additional term of $\\rho r T / n$.\n\n    The meaning of “optimal” was in reference to getting a lower-bound on the terms involving $N_1, N_2$ and $N_3$. Based on the updated bounds above, this appears as an additional term $-(b-a)(\\frac{\\rho T}{2} + \\frac{\\rho rT}{n})$ on Line 652.", "claims_and_evidence": "Most of the claims are well supported by counterexamples or theorems. However, I have some questions regarding the equivalence result between swap regret and the threshold-calibrated coverage. \n- In Theorem 3.5, the authors provide an upper bound on threshold-calibrated coverage in terms of swap regret. However, the right-hand side approaches zero only if $\\rho \\rightarrow 0$ and $T_{G,\\tau}^3$ grows faster than the swap regret, which is not immediately clear. Consequently, it does not directly follow that any algorithm achieving no swap regret will necessarily lead to the desired threshold-calibrated coverage.\n- Ideally, a stronger quantitative equivalence result would establish that a transcript achieves a certain coverage error at most $\\gamma$ __if and only if__ it attains a corresponding swap regret bound $R$. However, Theorems 3.5 and 3.6 seem to provide only a qualitative connection rather than a strict equivalence.", "methods_and_evaluation_criteria": "The first part of the paper focuses on the relationship between regret and coverage, so evaluation criteria are not applicable. In the second part, the authors propose a group conditional ACI algorithm, which is lightweight and appears reasonable for the intended application.", "theoretical_claims": "To the best of my knowledge, the proof appears to be correct. However, there are some steps in the derivation that I do not immediately follow, which I have detailed in the \"Questions\" section.", "experimental_designs_or_analyses": "The experimental design follows that of Bastani et al. (2022) and seems reasonable to me. However, as also discussed in Bastani et al. (2022), for the group-conditioned coverage setting, it may be more meaningful to consider the threshold-calibrated version as the evaluation metric.", "relation_to_broader_scientific_literature": "This papers focus on sequential online conformal prediction problems, initially studied by Gibbs \\& Candès (2021) and Gupta et al. (2022). The first part establishes an interesting connection to swap regret, a concept studied in the online learning literature. In the second part, the authors propose and analyze a group-conditional ACI algorithm, which can be viewed as a natural extension of ACI in Gibbs & Candès (2021).", "essential_references_not_discussed": "Some prior works have also explored the use of online learning algorithms for online conformal prediction but with different notions of regret, such as strongly adaptive regret (Bhatnagar et al., 2023) and discounted regret. It would be helpful to discuss these papers to better position the current work within the broader literature. \n\n\nBhatnagar, A., Wang, H., Xiong, C., & Bai, Y. (2023). Improved online conformal prediction via strongly adaptive online learning. ICML 2023.\n\nZhang, Z., Bombara, D. & Yang, H. (2024). Discounted Adaptive Online Learning: Towards Better Regularization. ICML 2024.", "other_strengths_and_weaknesses": "My main concern is that the paper's main results feel somewhat incomplete. \n- In the first part, after establishing the connection between swap regret and threshold-calibrated coverage, a natural follow-up question is whether this insight can lead to a new algorithm for online conformal prediction and how its coverage guarantee compares to the state-of-the-art methods, such as MVP in Bastani et al. (2022). Addressing this would help demonstrate the strength of the equivalence result.\n- In the second part, my understanding is that a key issue with the ACI algorithm is that the optimal learning rate $\\eta$ depends on unknown quantities of the sequence, as noted in Gibbs & Candès (2022). However, this issue does not appear to be discussed in the current submission.", "other_comments_or_suggestions": "- In the abstract (Line 027), \"follow the perturbed leader\" should be corrected to \"follow the regularized leader\".  \n- It would be more natural to define the $\\Phi$-regret as the opposite of the version currently used in this paper. This way, in Theorems 3.2, 3.5, 3.6, 3.7, 3.8, the regret will be expressed in terms of the pinball loss rather than the negative of pinball loss, which aligns better with standard conventions. \n- In Theorems 3.2 and 3.5, the distribution should be $(\\alpha,\\rho,r)$-smooth instead of $(\\rho,r)$-smooth. Also, this definition appears to be related to the definition given in Definition 3.1 of Bastani et al. (2022), which is worth discussing.", "questions_for_authors": "- In the proof of Lemma A.1, the authors state that by the smoothness condition on $\\mathcal{D}$, we have $|N_1 - qT| \\leq \\rho T/2$ (Line 644). Could you please elaborate on this? It seems that the bound should be  $|N_1-  \\lceil qT \\rceil| \\leq \\rho T$, and it is unclear where the additional factor of $1/2$ comes from. \n- Also, on Line 654, you mention that the final inequality follows from evaluating the expression at the optimal values of $N_1 = qT$ and $N_2 + N_3 = (1-q)T$. Could you clarify in what sense these values are \"optimal\"?", "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": "ouFmkRsh2w", "reviewer": "Reviewer_fRME", "summary": "- This paper studies the relationship between no-regret learning and online conformal prediction\n- They show that no-external regret guarantees imply non-trivial coverage guarantees if data is selected stochastically. Moreover, this is *not* true if the data stream is adversarially generated. \n- Moving beyond external regret, the authors also consider group-wise regret. Here, they show that even if the data stream is chosen stochastically, no group-wise regret guarantees does *not* imply non-trivial groupwise coverage bounds. \n- The authors turn to swap regret. Here, they show that thresholded calibrated coverage is equivalent to no-swap regret. They extend this result to show a similar equivalence between no group-conditional swap regret and multivalid coverage. \n- Finally, the authors study the coverage guarantees of online learning algorithms in the FTRL family. Their main theorem in this section relates the miscoverage rate for FTRL with a generic regularizer as a function of the magnitude of the last iterate in FTRL and the gradient of the regularizer. They then instantiate this theorem with specific algorithms in the FTRL family. like gradient descent, to get concrete upper bounds on the miscoverage rates in terms of $T$ and the number of groups $k$. The authors complement their theoretical findings with experiments.\n\n## Update after rebuttal\nI thank the authors for their response. As they have satisfactorily addressed my questions and concerns, I will maintain my positive score for this paper.", "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": "Thank you for your feedback! We will fix the typos you’ve pointed out, and address your other specific concerns / questions below: \n\n1. **$\\Pi_T$ as a random variable:** We apologize for any confusion here - In Theorem 3.2, $\\Pi_T$ is a realization of the transcript where $(x_t, y_t)$ are drawn from a fixed distribution. This theorem connects the empirical regret $\\gamma$ to the empirical coverage, but at a high level uses the fact that expected regret being low implies expected coverage is close to the desired rate. Since we are in a stochastic setting, the empirical and expected values are close to each other with high probability, which is why the result is a high-probability guarantee. \n\n####\n\n2. **Definition of $\\Phi$-regret:** Thank you for pointing this out - the definition of regret should be the algorithm’s loss minus the competitor’s loss, letting us consider regret with respect to the pinball loss directly. We will update this in revision.\n\n####\n\n3. **Undefined quantities:** $\\Phi_t$ in line 202 is a typo - this should be $\\Pi_t$ instead. $\\mathcal{D}_\\tau$ in Theorem 3.6 has the same definition as given in Theorem 3.5 - it is the empirical distribution over threshold values defined by the subsequence of the transcript for which the algorithm predicted $\\tau$. \n\n####\n\n4. **Why coverage guarantees matter:** Achieving a marginal $(1-\\alpha)$ coverage guarantee for threshold predictions is equivalent to producing prediction sets that include the true label marginally $(1-\\alpha)$ fraction of the time (since the predicted threshold maps to a prediction set through the scoring function); this link similarly applies to groupwise and in general conditional coverage guarantees as well. \n\n    Prediction sets with high coverage guarantees can be used in and of themselves as an interpretation of the uncertainty of a model’s point predictions. More practically, they can also be used to guide decisions for downstream agents. For example, if one is using a learning model in a safety-critical environment, it may be useful to utilize prediction sets with a very high guarantee of coverage to decide which actions minimize or eliminate the possibility of harmful outcomes. [1] formalizes this intuition and shows why prediction sets with coverage guarantees are the right form of uncertainty quantification for risk-averse decision-makers.\n\n ####\n\n[1]  Kiyani, Shayan, et al. “Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents.” ArXiv.org, 2025, arxiv.org/abs/2502.02561.", "claims_and_evidence": "Yes,  the claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods and/or evaluation criteria (e.g., benchmark datasets) make sense for the problem.", "theoretical_claims": "As no proofs were included in the main text, I did not verify the correctness of any proofs.", "experimental_designs_or_analyses": "Yes, I reviewed the experiments in Section 6, but found no glaring issues.", "relation_to_broader_scientific_literature": "This paper studies the relationship between various notions of regret minimization and online conformal prediction. In particular, while previous works have established coverage bounds for online conformal prediction under a worst-case adversary, these bounds are not in terms of regret bounds. This work fills this gap by trying to understand what sort of regret bounds can yield bounds on converge for online conformal prediction and vice versa. In addition, while previous works have given OGD-based algorithms for online conformal prediction, this paper extends this to a strictly larger family of FTRL-based online learning algorithms that are able to obtain *both* marginal and multi group coverage guarantees.", "essential_references_not_discussed": "To my best knowledge, the authors covered all related works that are essential to understanding the key contributions of the paper.", "other_strengths_and_weaknesses": "**Strengths**:\n- The paper is well-written and easy to follow\n- I found the connection between swap regret and thresholded-calibrated coverage interesting\n- I found the experimental results to be strong \n\n**Weaknesses**\n- Lack of Clarity. In many places, the authors consider transcripts that are random variables themselves (e.g. Theorem 3.2). Unfortunately, I feel that the authors do not do a good job at properly dealing the randomness here. In addition, the authors consider losses throughout the paper, yet the theorem statements are written in terms of gains (i.e. negative losses). More confusingly, in Definition 2.6, regret is defined \"with respect to the loss function l\", yet the order of the terms in the definition of regret is flipped -- instead of regret being defined as the algorithm's loss minus the competitor's loss, its defined as the competitor's loss minus the algorithm's loss.\n- Lack of proper definitions. In many places, the authors do not property define certain objects. For example, what is $\\Phi_t$ in the second column of line 202? What is $\\mathcal{D}_{\\tau}$ is Theorem 3.6? \n- Unclear Motivation. I'm not fully convinced of why we should care about coverage guarantees", "other_comments_or_suggestions": "- In the second column of line 26, I think it should be $f(x, y)$ not $f(x)$\n- I think it should be \"multi valid coverage\" instead of \"threshold-calibrated coverage\" in Definition 2.5\n- I think it should be $\\tau_t$ not $\\Phi_t$ in the Equation in the second column on line 201-202", "questions_for_authors": "(1) In Theorem 3.2, the transcript $\\Pi_T$ is a random variable as the examples $(x_t, y_t)$ are drawn iid. What does it mean to fix a transcript when it's random? Do you mean to fix a realization of the transcript? What does it mean for $\\Pi_t$ to have external regret $\\gamma$? Is this in expectation or point wise? When stating the coverage guarantees, what exactly is the probability over? Is this theorem essentially saying that if there is algorithm which can obtain *expected* regret $\\gamma$ against the pin ball loss, then, with probability at least blah it achieves the stated coverage guarantees?", "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": "elqPMDbhMD", "reviewer": "Reviewer_b1E4", "summary": "The paper investigates the relationship between coverage and various definitions of regret in online learning. The results of this investigation are as follows:\n- Sublinear regret with respect to the pinball loss implies coverage guarantees if the data sequence is i.i.d. and a smoothness condition holds on the distribution of the data.\n- Sublinear swap regret  implies (approximate) threshold-calibrated coverage when the empirical distribution of the threshold is smooth.\n- Sublinear  Groupwise swap regret can be linked to (approximate) group-wise coverage if the empirical distribution of the threshold is smooth.\n\nAlgorithmically, the author proposes group conditional ACI, a variant of ACI, which guarantees coverage for different groups in the covariate space.", "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": "Thank you for your thoughtful feedback! We address your main concerns here:\n\n1. **Benefits / Relevance of our work:** In regards to the guarantees of our paper, we wish to clarify a misconception the reviewer may have. Our goal in this paper is to elucidate the relationship between regret and coverage in two separate ways:\n\n    * What is the direct relationship between the *properties* of “no-regret” and “marginal/group-conditional coverage” in conformal prediction. This is algorithm-agnostic --- we are interested in when one property of an algorithm generically implies another. \n\n    * What are algorithms that are able to simultaneously achieve both kinds of properties, even when the properties are not (approximately) equivalent. This is algorithm-specific, since when the properties are not equivalent, our analysis needs to be specific to the algorithm itself.\n\n    Our goal in this paper is to make explicit which connections between regret and coverage are connected through the first point and which are connected through the second. To our knowledge, apart from concurrent work in [1], no other work in either the no-regret or the online conformal prediction literature has focused on distinguishing between these points as well as substantiating when the properties do not imply one another. \n\n    Our discussion in Sections 4 & 5 (including the introduction of GCACI) examines the second point. Though external regret wrt pinball loss does *not* imply coverage (as we show in Section 3), a general class of FTRL algorithms (which have been known for several decades to achieve external regret) are *also* able to achieve coverage guarantees bounded by the norm of the regularizer’s value. This is an insight not found in prior work, and it is through this connection that we instantiate the GCACI algorithm. The prior work related to this algorithm (ACI and its later variants) all apply only to the marginal, not the group conditional case. We will add discussion in our results section to explain this with more clarity.\n\n    As far as practical benefits, we show in our experiments that GCACI, in addition to being more lightweight, achieves much faster convergence rates than the MVP algorithm from  [2] which satisfies the stronger threshold-calibration guarantee. Previously, the only two families of online conformal prediction algorithms (MVP, and ACI and its variants) differed in multiple respects: the ACI algorithms obtained faster convergence and were more lightweight, but offered weaker guarantees than MVP in two respects: they were not threshold calibrated, and they did not offer group conditional guarantees. Here we show that we can obtain lightweight algorithms with fast convergence by giving up only on threshold calibration, while keeping group conditional validity --- this was not previously known.\n\n#### \n\n2. **Smoothness requirement:** Smoothness is a mild condition that we can enforce if necessary by perturbing the scores chosen by the adversary (which implicitly perturbs the threshold) by a value drawn from a uniform distribution $[-\\epsilon, \\epsilon]$. This doesn’t require us to make assumptions on the adversary. \n\t\n\tWe also note that Theorems 3.5 through 3.8 are making direct connections between no regret and coverage, and it is not possible to make this connection without some kind of smoothness guarantee - we address this in more detail in point (1) with reviewer **8yW2**. \n\n####\n\n3. **Follow-the-perturbed-leader mention in abstract:** This is a typo; it should be follow-the-regularized leader instead. Oops! Thanks for pointing it out!\n\n####\n\n4. **More natural definition of group-membership:** Our experiments are of course synthetic, and you are completely right that in some of them the groups are not “natural”. Our goal in these experiments is simply to compare the convergence rates of coverage, and for this purpose we think that the results are agnostic to the meaning of the group functions. In general, we agree that it is more interesting to define groups based on features we wish to eliminate disparity between, as we do in the Folktables experiments.\n\n\tThe time-series data does not come with features, so we found the most natural way to define groups was as a function of the time-step. For the UCI Airfoil data, all features are numerical variables measuring parts of the airfoils - we did not find there was any meaningful way to define groups through these variables.\n\n####\n\n[1] Angelopoulos, Anastasios N, et al. “Gradient Equilibrium in Online Learning: Theory and Applications.” ArXiv.org, 2025, arxiv.org/abs/2501.08330\n\n[2] Bastani, Osbert, et al. “Practical Adversarial Multivalid Conformal Prediction.” ArXiv.org, 2022, arxiv.org/abs/2206.01067.", "claims_and_evidence": "Yes, all claims are supported by proof and theorems.", "methods_and_evaluation_criteria": "Yes, the authors consider simple benchmarks where group membership is accounted for by differentiating samples over time or features. Except for the last example, the group membership definitions are artificially defined. Datasets with more natural membership conditions would be more instructive.", "theoretical_claims": "I have checked the proof on the coverage guarantees of G-ACI and those about the relationship between swap regret and coverage.", "experimental_designs_or_analyses": "I have read the description of the experimental set-up and it appears to be reasonable. However,  doing the experiments with datasets with more natural membership conditions would be more instructive.", "relation_to_broader_scientific_literature": "I think the paper does a good job explaining what are the existing work in the field.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper’s theoretical contributions are sound; however, it is not clear how one benefits from the derived guarantees. More specifically, I don’t see how they refine the analysis of existing online conformal calibration algorithms or lead to new ones. I would suggest elaborating on the implications of each result in the context of online calibration. As they are presented now, I have the impression that the results lack sufficient context and fail to explain their practical relevance to the field of online calibration.\n\nThe criticism above applies to Section 5, in which G-ACI is introduced. In fact, it appears that the proposed algorithm is derived using standard techniques that are independent of the results developed in the preceding sections.", "other_comments_or_suggestions": "As mentioned in the previous section, I would suggest better contextualizing the theorems, explaining their practical relevance, and highlighting more clearly how the theoretical results are used to analyze G-ACI in a way that could not have been done before.", "questions_for_authors": "- Theorems 3.5 to 3.8 make some assumptions about the smoothness of the empirical distribution of $\\tau$ values at specific intervals. Does this imply an assumption on the distribution of the sequence $(x_t, y_t)$? If so, can this be elucidated? does this means that this coverage guarantees are not adversarial as normally assumed in online CP?  \n- In the abstract, the perturbed leader algorithm is mentioned but the connection between this algorithm and online CP is not clarified in the main text.\n\n\nUpdate after rebuttal: I have decided to raise my original score to weak accept.", "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": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This work identifies a novel connection between coverage conditions in conformal prediction and classes of no-regret algorithms in online learning. Specifically, group (multivalid) coverage conditions are identified as linked to swap regret, for which follow the perturbed/regularized leader achieve no regret. Theoretical and experimental implications of these connections are illuminated, which the reviewers unanimously assess to be meritorious for the machine learning research community. While there is some disagreement on the novelty of the proofs and discussion of related works, this is not enough to be disqualifying. Moreover, the paper is well-written and contributes fundamentally new results to an important area of machine learning.
Decision: Accept (poster)