The Benefit of Being Bayesian in Online Conformal Prediction

Thank you very much for your review!

Updating the prior online is indeed an interesting idea worth looking into in the future. As for unifying the regimes of decaying step sizes and constant step sizes, one might consider characterizing the dynamic regret (Zinkevich, 2003), which is another common performance metric in online learning. Algorithms targeting this performance metric usually have a "meta-learning" type of structure, where a number of "base algorithms" (like our Algorithm 1) with different learning rates are aggregated by a meta-algorithm on top (which in some sense "selects" the best learning rate). It's quite likely that extending our approach towards this direction would yield new theoretical results, but that would typically sacrifice the practicality (while not necessarily leading to new insights), which is why we did't pursue this direction in the present work.

Thank you for your careful review that found our paper's strengths. We really appreciate that!

Regarding your suggestions, we will try to add additional clarifying text to Section 3 in the revision. As for the MultiOGD baseline:

• First, recall that OGD itself has Eq.(3) in our paper as its update rule, which requires a fixed confidence level $\alpha$ throughout its operation (notice that $\alpha$ is used to define the quantile loss functions).
• MultiOGD is perhaps the simplest extension of OGD that doesn't require fixing $\alpha$ beforehand. To do that, MultiOGD maintains a bunch of independent OGD algorithms (called base algorithms), each targeting a different confidence level $\tilde \alpha$. At the beginning of each round, all these base algorithms (with different $\tilde \alpha$) would have their predictions ready. If a user queries a specific confidence level $\alpha$, then MultiOGD will output the prediciton of the base algorithm whose $\tilde \alpha$ value is the closest to $\alpha$.
• Particularly in Section 2, we only consider two different users in the experiments, each querying a fixed $\alpha$ value. In this case MultiOGD just becomes OGD itself, and our experiments essentially show that "two copies of OGD with different $\alpha$ can be inconsistent with each other".

Thanks again, and please let us know any remaining question!

Thank you very much for your constructive feedback. We will try to run more experiments on real datasets during the rebuttal phase and update here. Meanwhile we'd like to respond to the rest of your major criticisms.

1. Invariance to permutation is not a benefit

You are right, we will remove this "paradox" and only argue about the other one (inconsistency between different $\alpha$). Indeed, we agree that only when the data stream is iid can we confidently say the invariance to permutation is a desirable property.

2. Compatibility of performance guarantees with distribution shifts

We'd like to clarify two possible confusions from your review. The first is on the performance guarantee of Discounted (Theorem 6). Quoting your review,

And Theorem 6 does not seem to agree with the text surrounding it; the 'optimal' predictions considered for the regret bound seems to be constant over the course of the whole time (since the min over $r$ is outside the sum over time), which is deeply uninteresting. Any minimally decent predictor in the continual distribution shift setting should have predictions that change over time.

Our Theorem 6 bounds the discounted regret, which is one of the standard performance measures for "nonstaionary online learning". The intuition is that given a discount factor, it characterizes the performance of the algorithm over a sliding time window whose length is determined by the discount factor. Over any time window, the algorithm is compared to the best fixed action specifically for this time window. Importantly, over different time windows the algorithm will compare to different fixed actions, which is naturally compatible with the essence of "learning under distribution shifts".

Regarding the example you made:

A simple case where these things really matter is when your are in an adversarial setting with increasing conformity scores over time. No single prediction is going to be enough, you must increase your intervals over time!

Our discounted algorithm can indeed increase its prediction interval over time. We'll include an experiment to show this.

The second possible confusion is on the utility of the static regret bound (Theorem 2). We'd like to note that bounding the static regret doesn't mean that we assume the data is IID or exchangeable. In the learning-theoretic language, the static regret characterizes our algorithm's ability to learn the hypothesis class of time-invariant functions, which is independent of the data generation mechanism. This is also the key motivation for the field of adversarial online learning to focus on the static regret.

3. Significance our theoretical results

Quoting your review,

The paper's theoretical contributions aren't notable enough nor are any new things possible with the proposed method,

With all due respect, we'd like to push back against this evaluation. Most notably, our algorithm achieves an adaptive, best-of-both-worlds guarantee that prior works couldn't. In addition, in the adversarial setting, our algorithm is the first one to support multiple $\alpha$ queries with monotonicity.

To be more concrete on the first point, we argue that in many practical applications of CP one has to apply the algorithm without knowing the nature of environment in advance. In such cases it's impossible to say something like "we'll apply Split CP if the data sequence is exchangeable, and ACI otherwise"; instead, an ideal algorithm needs to work well under all data-generation mechanisms, which aligns with the statistical concept of adaptivity.

Our algorithm does this. Without knowing the nature of the environment beforehand, the same algorithm guarantees that

• if the data sequence is iid, then the dataset conditional coverage probability is as good as Split CP;
• over any data sequence, the regret bound of our algorithm is optimal (as good as gradient descent).

We are not aware of any prior work that achieves this.

Besides, we establish the equivalence between a Bayesian algorithm (with uniform prior) and a full-loss FTRL algorithm (with quadratic regularizer), which we see as a substantial technical contribution.

4. Experiment

Finally, the focus of this paper is theoretical, and with our synthetic data experiments (Figure 2 and 3) clearly showing the improvement of our approach over representative baselines, we thought the paper is already quite complete. In addition, we see CP as a particular aspect of "trustworthy computing", where theoretical guarantees are themselves among the key elements that determine the usefulness of an algorithm.

Thanks for your reply. To respond to your main remaining concern (writing doesn't sufficiently emphasize the adaptivity of the algorithm), we revised the paper and updated the pdf. The newly added text is marked in red. In particular, we removed all discussions of permutation invariance, and added a major paragraph to Section 1.2 (summary of results) in order to make the benefit of adaptivity clearer.

We'd also like to kindly remark that besides adaptivity, another major strength of our algorithm is its ability to answer multiple arbitrary confidence level query in a monotonic (or "probabilistically plausible") manner. We hope this strength is also factored into your evaluation. Essentially our paper presents multiple results of possible independent interest (see Section 1.2). People may have different opinion on the ideal proportion of each result, but overall we believe that having multiple results is a plus rather than a minus (Reviewer J1rZ appears to have a more positive sentiment on this).

Appendix D in the updated pdf contains some new experiments. We show that the monotonicity issue demonstrated in Section 2 (synthetic data) also shows up in the stock experiment (actual data). It seems to us that experiments of this type are best suited for our paper. "Multi-confidence consistency" a novel and important evaluation metric that hasn't been considered in the conformal prediction literature before, and it supports our claim well. Overall, we believe that the scientific message in our current experiments is self-complete, solid and clear.

Before reading your latest reply, we also performed the experiment you suggested in your original review (monotonically increasing true score sequence), which demonstrates the effectiveness of discounting. It seems that your criticism regarding discounting is now dismissed, but nonetheless, we included the results in Appendix D for the readers' information.

Finally, we see the role of permutation invariance as an open-ended question. When the true score sequence has temporal structures, being permutation-invariant is not as good as permutation-dependency that "ideally exploits" the temporal structure, but still it's better than permutation-dependency that "wrongly incorporates" the temporal structure. Overall it's hard to draw conclusions at this point, but indeed it suggests a good question for future works.

We hope the above addresses your remaining concerns.

Thank you very much for your constructive review. Regarding your comments,

1. Reason to call our algorithm Bayesian

To begin with, we thought it's quite important to note that we only call our algorithm Bayesian, rather than the problem setting and the analysis.

From only the algorithmic perspective, as discussed in Section 5, our belief update backbone is the same as the standard Bayesian distribution estimator. This estimator doesn't seem have a separate fancy name from the Bayesian statistics literature, but it should be a fairly standard textbook-level concept as covered by (Chapter 23, Gelman et al., Bayesian Data Analysis, 2021). We see a major novelty of our work as showing the equivalence of a Bayesian algorithm from statistics and a full-loss FTRL algorithm from adversarial online learning, which is significant but hasn't been concretely explored in the past.

As for the problem setting and the analysis, ours are indeed very different from Bayesian statistics, as also pointed out by your review:

Note in particular that a Bayesian would consider the observations forming the empirical distribution to be iid draws from a multinomial, quite out of the spirit of the "no statistical assumptions" statement that the authors make.

Indeed, traditional Bayesian statistics doesn't consider the "adversarial settings" like in our work. This leads to the main operational value of the above algorithmic equivalence: we could give certain performance guarantees of the proposed Bayesian algorithm, without statistical assumptions at all. We call such analytical framework "adversarial Bayes".

2. Importance of multiple confidence level queries

Supporting multiple $\alpha$ queries can be useful in plenty of applications.

• Imagine a "central" CP algorithm predicting confidence sets on the stock prices, and different downstream users apply those sets for their respective investment activities. Each user has a different risk preference, which determines a different $\alpha$ to be queried from the CP algorithm.
• Another case is when a single downstream user applies the confidence sets in an iterative subroutine, which requires multiple queries in the same round. For example, the user first queries $\alpha=90\%$ and gets the algorithm's prediction set. If the set is deemed "too large" then the user might consider lowering $\alpha$ to 80% and query again (in the same round). So on and so forth.

3. Invariance to permutation is not a benefit

This is a good point! We will remove this "paradox" and only argue about the other one (inconsistency between different $\alpha$). Indeed, we agree that only when the data stream is iid can we confidently say the invariance to permutation is a desirable property.

4. Why not a pure and simple FTRL story?

Compared to a pure FTRL story, there are two benefits of the Bayesian statistical perspective:

• Computation. It's worth-noting that we use the "full-loss" FTRL rather than the linearized version of FTRL more commonly found in the generic online learning literature. Such unpopularity of full-loss FTRL has been mainly due to computational reasons, as the online learning algorithm needs to solve a convex program in each round, similar to the RHS of Eq.(6).
  In contrast, our paper uses the Bayesian interpretation to avoid the need of convex programs (the special structure of CP is important here), and the algorithm admits a backbone-head decomposition which enables multiple $\alpha$ queries in a computationally efficient manner.
• Probabilistic bound under IID assumption. CP is conventionally a statistics problem, and the Bayesian perspective allows us to obtain a coverage probability bound assuming IID (Section 3.2), which is beyond the scope of typical regret analyses on FTRL. In particular, the proofs of Theorem 4 and 5 are essentially built on this Bayesian perspective.

Besides these concrete operational benefits, we would argue that connecting full-loss FTRL with Bayesian statistics is itself quite interesting from a technical perspective. It requires exploiting the structure of the quantile losses, which hasn't been considered in the generic online learning literature. At least we found it surprising that the quadratic regularizer shows up when the prior is uniform. Section 1.2 summarizes the conceptual takeaway of our paper and the associated quantitative benefits.

Please let us know if you have any remaining concern.

Thank you very much for your review. Regarding your questions:

1. "what about the size of the prediction sets (in the experiment)?"

Figure 5 in the paper shows the score thresholds predicted by our algorithm and the baselines, which essentially determines the sizes of the prediction sets. It could be visually seen that all three algorithms perform similarly in terms of the set sizes.

2. "the $O(\sqrt{T})$ memory usage seems redhibitory at first glance, but is not evaluated in practice in the experiments."

In principle, our algorithm needs to maintain a histogram of the past true scores, and the memory usage is determined by the number of bins the histogram contains. We need $O(\sqrt{T})$ bins for theoretical purposes, but in practice it's natural to keep the number of bins constant (in our experiment we pick 40, which induces negligible approximation error). This is the same reasoning as in (Bastani et al., 2022) which is also built on binning.

3. The role of prior

Theoretically speaking the uniform prior is the "minimax optimal" choice: for any other prior, there exists an environment where it's worse than the uniform. But in practice we would expect better performance using suitable non-uniform priors, just like typical Bayesian algorithms. Appendix A contains a comparison of our approach to Bayesian UQ.

We hope the above answers your questions!