The Relationship Between No-Regret Learning and Online Conformal Prediction

Thank you for your thoughtful feedback! We address your main concerns here:

1. 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:

   • 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.

   • 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.

   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.

   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.

   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.

2. 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.

   We 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.

3. 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!

4. 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.

   The 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.

[1] Angelopoulos, Anastasios N, et al. “Gradient Equilibrium in Online Learning: Theory and Applications.” ArXiv.org, 2025, arxiv.org/abs/2501.08330

[2] Bastani, Osbert, et al. “Practical Adversarial Multivalid Conformal Prediction.” ArXiv.org, 2022, arxiv.org/abs/2206.01067.

Thank you for your feedback! We will fix the typos you’ve pointed out, and address your other specific concerns / questions below:

1. $\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.

2. 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.

3. 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$.

4. 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.

   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.

[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.

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)}$.

• 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}}$.
• 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.

Addressing your questions / comments:

1. 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. 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$.

2. 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.

3. 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.

   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.

4. 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.

5. 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$.

   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.

Thank you for your detailed feedback! We will try to address your concerns and comments.

First, 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.

1. 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.

   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.

   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.

2. 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.

3. 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.