Online Conformal Prediction via Online Optimization

We thank the reviewer for their appreciation of our work.

However, I couldn’t find any long-run coverage results in the tables in the main text.

The long-run coverage for all the methods in Table 1 is at least 0.87 - we will make this clearer in the final version. We have also attached plots showing the long-run coverage rates on the preregistered ERCOT data at this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing], where we see that all methods converge rather quickly. We have also attached plots showing the long-run coverage tradeoff for LQT in terms of the learning rate, for ERCOT data.

I don’t see any weaknesses in the existing approach, other than the fact that the current experiments lack results comparing long-run coverage.

Please see the comment above.

We thank the reviewer for their detailed comments. We first provide a few general remarks.

Our work provides stronger guarantees than standard online conformal works, by offering not just the standard adversarial marginal guarantee, but also a stronger conditional one when the data is non-adversarial. Crucially, our algorithm is adaptive when the process is non-adversarial. Adaptive and optimistic algorithms have been effective solutions in several areas of machine learning, such as online convex optimization and reinforcement learning.

Claims & Evidence

1. This is not a misinterpretation of online conformal methods when we take scalar quantile tracker (SQT, Example 3.1) updates to be controller actions. The SQT system, with $\eta=1$ and $S_t = 0.1$ for all $t$ for simplicity, behaves precisely like a bang-bang controller with on signal = +0.9, off signal = -0.1, and set point = 0.1. Namely, if the state ($q_t$) is below the set point (0.1), the controller will always output the on signal (+0.9), and it will output the off signal (-0.1) otherwise.

2. The batch version of our algorithm is fully compatible with the standard online conformal prediction setting. In the batched algorithm, the conformal predictor’s parameter is updated after every m (the batch size) steps, but the prediction set at each time t is always generated immediately after the covariate X_t is observed.

3. We state that one can trivially obtain the guarantee “by alternating between $q_t = \infty$ and $q_t = -\infty$.” The thresholds should not always be $\infty$ or $-\infty$ as this would indeed lead to error rates of 0 or 1, respectively.

4. The main purpose of this paper is to show that we can develop online conformal algorithms that enjoy strong guarantees for stochastic processes while maintaining adversarial guarantees. The only asymptotic part of the paper is Theorem 5.1, and this is in the analysis of the algorithm. Theorems 4.1, 5.4, and 6.1 are finite-sample guarantees for our algorithm.

5. Our theoretical guarantees extend beyond well-specified models – we devote Section 6 to the mis-specified setting and preserve the adversarial coverage guarantees with no such assumptions. Our linear model assumption represents a generalization over methods such as ACI, which only considers scalars, and our experimental results across 17 datasets, along with our pre-registered experiment, suggest this generalization leads to significant performance improvements.

Experimental Designs Or Analyses

1. We have adapted the code provided by the authors of [2] to compare with our method and baselines on the preregistered ERCOT data. The algorithm provided in [2], AgACI, comes with several aggregation strategies, and we provide results at this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing]. These all achieve marginal coverage, but the set sizes and quantile losses are all larger than every method appearing in Table 1. We also point out that AgACI is not proven to achieve long-run coverage and does not provide theoretical guarantees.

2. We have attached these figures for our main pre-registered dataset and several methods at the link above (Figure 1 contains essentially this figure, we also attached analogous figures for the ACI and PID(theta) baselines for comparison).

Due to the lack of essential figures ... but did not find them.

Please see the comment above.

Additionally, I read through the related work section ... auto-regressive case.

Thank you for the suggestion, we will add a discussion of [2] to the final version.

Other Comments Or Suggestions

1. The parameter that we refer to here is the threshold, not the learning rate, which is instead a hyperparameter.

2. In spite of the reviewer’s comments, we have not identified any technical errors. The reviewer, as far as we can tell, also does not seem to identify technical errors in our theoretical or experimental results. While we are sure there are typos that we have missed, it seems unreasonable to ask for more (on the technical side) than correct proofs and pre-registered real-world experiments.

   In Section 2, we define “right thing” formally– always achieving the adversarial guarantee (1) while also achieving (2) when possible. We will clarify this statement in the final version.

   We would be happy to clarify if anything about the notation $\\{(X_t,Y_t)\\}_t$ is unclear.

3. We have been careful about dropping the argument to the conformal predictor when clear from context. If there is any instance that caused confusion, we would be happy to clarify.

Since the main claim of the paper has a major flaw, along with an inaccurate theoretical framing, I don't think requesting additional experiment results would be helpful.

Despite the reviewer’s comments, we have not identified any “major flaw” or “inaccurate theoretical framing”. Perhaps the reviewer can elaborate on what these refer to.

I couldn’t find the long-term coverage rate reported for any of the experiments...I would have liked to see the trade-off it has when it comes to long-term coverage.

At this link [https://drive.google.com/file/d/1AT1hbP3ohYowIt0_Hy209yadYvZjl9cJ/view?usp=sharing], we have attached additional experiments to describe both (1) long-run coverage across several methods, and (2) the trade-off in terms of the learning rate for LQT. For (1), we observe that all methods converge rather quickly, and for (2), we observe that indeed there is a slower convergence for more quickly decaying learning rates.

In general, we do not report the long-run coverage because all methods achieve it. We also point out that Table 6 in the appendix shows that in all but 1 instance, the proposed algorithms (and baselines) achieve at least 0.87 long-run coverage when the target is set to 0.9. The baselines achieved tight marginal coverage since we tuned their hyperparameters on the test set.

There seems to be a tradeoff in terms of the stochastic and adversarial coverage guarantees when it comes to setting both the batch size and the set of learning rates, so the optimal rates of both cannot be achieved simultaneously. This is understandable and seems like a necessary tradeoff but in terms of application what approach would be taken to decide which algorithm to use? In unknown settings / sequences, it seems like one would want to set the parameters so that we achieve non-trivial long-term coverage (assuming adversarial), but this would have worse convergence rates than the other methods if you also wanted non-trivial guarantees of the stochastic variety.

We thank the reviewer for their appreciation of our work. We offer three answers to the tradeoff question:

• The batch size and learning rate decay are hyperparameters that can be tuned on validation data, as we have done with the magnitude of the learning rate for our experiments. We sought the best performance on the quantile loss, given a constraint on the long-run coverage, but these heuristics can be changed to fit the practitioner’s goals.
• Domain-specific knowledge, if available, can help guide this choice. If the well-specified assumption is reasonable, or the errors happen to be linearly correlated often, then faster rates of decay are preferable to speed up convergence, while constant learning rates will provide the tightest coverage when the data is fully adversarial.
• Choosing intermediate rates of decay (i.e. $\Theta(t^{-0.6})$ as in the paper) allows us to attain both long-run coverage and consistency under well-specification, albeit at slower rates. Across our experiments, we have found this (and small batch sizes) to be a safe choice. We think these hyperparameter questions are important, so we have been careful to empirically validate this intuition through the preregistration.

As the authors mention, to achieve optimal convergence rates for coverage in the stochastic setting, we set the learning rate in a way that achieves a vacuous bound on long-term coverage in the adversarial sense (and vice versa). Did you think about the settings where you achieve these guarantees at the same time (though not at the optimal rates)?

Our results apply to a range of learning rates $\Theta(t^{-c})$ for $c \in [0,1]$, not just the $\Theta(1/t)$ learning rates attaining optimal convergence rates in the stochastic setting and $\Theta(1)$ attaining optimal long-run coverage rates in the adversarial setting. Choosing $c \in (0,1)$ thus allows us to attain both long-run coverage and consistency under well-specification asymptotically, albeit at non-optimal rates.

Section 5 mentions that the finite sample rates are achieved with a particular batch size m and I didn’t get into the details of this proof – could the authors clarify what the relationship between m and the constant C’ in Theorem 5.4 is? Is m a function of T?

The batch size m is not a function of T. It should be chosen so that the corresponding minimum eigenvalue in each sample covariance matrix has a sufficiently large conditional expectation. In Lemma 5.3, this just leads to a batch size of at least 2. The batch size m is constant, and the constant C’ increases with m.

How was the learning rate set for the decaying version of LQT in the experiments? Did it decrease at a $O(1/t)$ rate or was it slower to also achieve a non-trivial long-term coverage convergence rate?

The rate of decay for our experiments is $\Theta(t^{-0.6})$ following Angelopoulos et al. (2024). This is indeed to ensure non-trivial long-run coverage. The only exception is the synthetic experiment in Appendix B3 where we use the optimal $\Theta(1/t)$.

A very similar notion of conditional coverage has been previously discussed by [1], in a stochastic iid batch setting, named mean squared conditional error

We thank the reviewer for pointing us to this reference. We would like to verify that it refers to [1], and we would be happy to incorporate it into our discussion of conditional coverage in the i.i.d. offline setting. [1] Kiyani, S., Pappas, G. and Hassani, H. Conformal prediction with learned features. arXiv:2404.17487 [cs.LG]. 2024.

The paper needs improvement in the presentation...beyond just running online gradient descent on pinball loss, which is the core algorithm in the literature.

Our main contribution is a new algorithm that both satisfies adversarial guarantees (long-run coverage) and does the “right thing” (achieves time-conditional coverage) if the data is not adversarial. Most online conformal work focuses solely on adversarial guarantees, but we provide a novel approach that can adapt to both settings.

In terms of the algorithm itself, the main novelty is that we run online gradient descent on the quantile loss with more complex models for the conformal predictor. Past work (e.g. ACI) only considers scalar models, while our algorithm applies to arbitrary parametric models. For our stochastic guarantees, we simply require that the conformal predictor q_t(\theta) is linear in \theta. We will preface the algorithm with more motivation and discuss the novelties in the final version.

In the current version, the organization of the assumptions...but your assumptions don't hold then.)

We will make the assumptions for each guarantee clearer, and expand on how conventional and restrictive they are in the final version. At a high level, our assumptions fall into two categories: model assumptions and distributional assumptions. Our model assumptions determine the structure of the conformal predictor; most of our analysis requires that the conformal predictor $q_t(\theta)$ is linear in its parameter $\theta \in \mathbb{R}^d$ (though this can in fact be dropped for the adversarial guarantee in Theorem 4.1). These are less restrictive than conventional model assumptions that only allow for scalar models (as discussed in our response to the previous point). Our distributional assumptions hold for many data-generating processes. For example, in Theorem 5.4 we only require that the conditional quantiles are a linear function of the past, which is true for AR(p) processes and i.i.d. data. This is less restrictive than (Angelopoulos et al., 2024), which only considers the i.i.d. setting.

Examples 3.1, 3.2, and 3.3 all satisfy the linear model assumption, and each has a description of when it is well-specified (for the guarantees of Section 5 to apply). Our experiments focus on these three examples, where we find that 3.2 and 3.3 perform the best. Algorithm 1 does allow for models that do not satisfy our assumptions (e.g. nonlinear), but these do not enjoy the same stochastic theoretical guarantees, which are a crucial part of our contribution. We believe that extending our guarantees to more complex model classes that could provide further practical benefits is a promising area of future research, and we will make this point clearer in the final version.

What are the list of contributions this paper is claiming? is there also any algorithmic contributions? or it is mainly analyzing the online gradient descent on pinball loss under different assumptions and different notions of coverage?

Concretely, our contributions are:

• A new algorithm for online conformal prediction that allows for conformal predictors beyond scalars as in ACI.

• Theoretical guarantees showing that our algorithm always achieves

  • marginal coverage,

  and under appropriate stochastic assumptions:

  • conditional coverage when well-specified
  • relaxed conditional coverage when mis-specified.

• Experiments spanning 17 datasets and a pre-registration to compare our method with existing alternatives and provide evidence for the empirical benefits of our algorithm.

As previously discussed, the algorithmic contribution is to extend the model for the conformal predictor beyond a single scalar parameter (as in ACI) to parametric functions, and specifically for our theoretical results: linear functions of feature maps. This new algorithm can adapt to stochastic data, where it enjoys strong convergence guarantees both when well-specified and mis-specified. While our algorithm can replicate SQT as a special case, it encompasses a larger family of procedures and is thus not equivalent to exploring the behavior of existing algorithms under different assumptions. Moreover, our notions of coverage are not just different, but more general and stronger: we satisfy the standard marginal coverage property in the adversarial setting, but also a notion of conditional coverage when the data is stochastic. This has not been explored in past work beyond the i.i.d. setting.