The Benefit of Being Bayesian in Online Conformal Prediction

## Abstract

Abstract Based on the framework of Conformal Prediction (CP), we study the online construction of valid confidence sets given a black-box machine learning model. By converting the target confidence levels into quantile levels, the problem can be reduced to predicting the quantiles (in hindsight) of a sequentially revealed data sequence. Two very different approaches have been studied previously: • Direct approach: Assuming the data sequence is iid or exchangeable, one could maintain the empirical distribution of the observed data as an algorithmic belief, and directly predict its quantiles. • Indirect approach: As statistical assumptions often do not hold in practice, a recent trend is to consider the adversarial setting and apply first-order online optimization to moving quantile losses [ 8 ] . It requires knowing the target quantile level beforehand, and suffers from certain validity issues on the obtained confidence sets, due to the associated loss linearization. This paper presents a novel Bayesian CP framework that combines their strengths. Without any statistical assumption, it is able to both • answer multiple arbitrary confidence level queries online, with provably low regret; and • overcome the validity issues suffered by first-order optimization baselines, due to being “data-centric” rather than “iterate-centric”. In addition, it can adapt to an iid environment with the correct coverage probability guarantee. From a technical perspective, our key idea is to regularize the algorithmic belief of the above direct approach by a Bayesian prior, which “robustifies” it by simulating a non-linearized Follow the Regularized Leader (FTRL) algorithm on the output. For statisticians, this can be regarded as an online adversarial view of Bayesian inference. Importantly, the proposed belief update backbone is shared by prediction heads targeting different confidence levels, bringing practical benefits analogous to the recently proposed concept of U-calibration [ 16 ] .

## 1 Introduction

Figure: Figure 1: The CP interaction protocol.
Refer to caption: /html/2410.02561/assets/x1.png

Modern machine learning (ML) models are better at point prediction compared to probabilistic prediction. For example, when given an image classification task, they are better at responding “*this image is most likely a white cat*”, rather than “*I’m 90% sure this image is an animal, 60% sure it’s a cat, and 30% sure it’s a white cat*”. For downstream users, the more nuanced probabilistic predictions are often important for risk assessment. The challenge, however, lies in aligning the model’s own uncertainty evaluation with its actual performance in the real world.

*Conformal prediction* (CP) [] has recently emerged as a premier framework to address this challenge, as it blends the empirical strength of modern ML with the theoretical soundness of traditional statistical methods. As illustrated in Figure [1](#S1.F1), CP algorithms make *confidence set predictions* on the label space, by sequentially interacting with three other parties: the *nature* (i.e., the data stream), a *black-box ML model*, and *downstream users*. In each (the $t$-th) round,

- 1.
We, as the CP algorithm, observe a *target covariate* $x_{t}\in\mathcal{X}$ from the nature, and a *score function* $s_{t}:\mathcal{X}\times\mathcal{Y}\rightarrow[0,R]$ generated by a black-box ML model Base.
- 2.
The downstream users select a finite set of *confidence level queries*, $A_{t}\subset[0,1]$.
- 3.
Given each $\alpha\in A_{t}$, we predict a *score threshold* $r_{t}(x_{t},\alpha)$ based on existing observations, which leads to a *confidence set*(^1^11Without loss of generality, we assume the score function $s_{t}(x_{t},y)$ is *negatively oriented*: smaller means the ML model is more certain that the candidate label $y$ is the true one. See Appendix [1.3](#S1.SS3) for an example.)
$\mathcal{C}_{t}(x_{t},\alpha)=\left\{y\in\mathcal{Y}:s_{t}(x_{t},y)\leq r_{t}(x_{t},\alpha)\right\}.$
(1)
- 4.
Nature reveals the *ground truth label* $y_{t}\in\mathcal{Y}$ and the *true score* $r^{*}_{t}\mathrel{\mathop{:}}=s_{t}(x_{t},y_{t})$.
- 5.
The $(x_{t},y_{t})$ pair is passed to Base, which it optionally uses to generate the score function $s_{t+1}$.

By sequentially evaluating Base on the target data, we generate better score thresholds that “correct” the uncertainty evaluation from Base itself. As a concrete example, one could imagine Base being a trained image classifier, and the user being a wildlife conservation organization that uses Base to monitor endangered species. Generating a plethora of informative confidence sets would equip the user with a more accurate understanding of the species at risk.

Our goal is thus clear in a very broad sense – predicting confidence sets with *guaranteed validity*. Say if a user queries the confidence level $\alpha=90\%$, then our CP algorithm needs to provide certain quantitative evidence that incentivizes the user to treat $\mathcal{C}_{t}(x_{t},\alpha)$ as the $90\%$ confidence set about the true label $y_{t}$. While solutions are well-known in various statistical settings, the present work is about designing better CP algorithms without any statistical assumption at all.

### 1.1 Background

To introduce the necessary background, we start from the simplest case: within a time horizon $T$, the true scores $r^{*}_{1:T}$ are iid samples of a random variable $X$ with strictly positive density. This can happen if the target data $(x_{t},y_{t})$ for different $t$ are iid, and Base is fixed (i.e., Step 5 is skipped).
Further suppose the $\alpha$-*quantile* of $X$,(^2^22For the readers’ reference, the $\alpha$-quantile of a real random variable $X$ is defined as $q_{\alpha}(X)\mathrel{\mathop{:}}=\min\{x:\mathbb{P}(X\leq x)\geq\alpha\}$.) denoted by $q_{\alpha}(X)$, is known, then a natural strategy is to predict $r_{t}(x_{t},\alpha)=q_{\alpha}(X)$. This ensures that the *coverage condition* $y_{t}\in\mathcal{C}_{t}(x_{t},\alpha)$ holds with probability exactly $\alpha$. That is, the confidence set prediction is valid in a strong probabilistic sense.

Although the assumptions are clearly unrealistic, this example illustrates a central principle of CP: the predicted score threshold $r_{t}(x_{t},\alpha)$ should ideally be the $\alpha$-quantile of *some* distribution of $r^{*}_{1:T}$. A key challenge of CP is thus generalizing this principle to more realistic settings, as described below.

- •
*Direct approach:* Still assuming the sequence $r^{*}_{1:T}$ is iid but the population quantile $q_{\alpha}(X)$ is unknown, we could instead estimate $q_{\alpha}(X)$ on the fly. Specifically, our algorithm maintains the empirical distribution of $r^{*}_{1:t-1}$, denoted by $P_{t}=\bar{P}(r^{*}_{1:t-1})$, as an *algorithmic belief* about the unknown distribution of $X$. Then, when queried with any confidence level $\alpha$, it “post-processes” the belief by setting $r_{t}(x_{t},\alpha)=q_{\alpha}(P_{t})$. This is equivalent to *Empirical Risk Minimization* (ERM) with the *quantile loss* $l_{\alpha}(r,r^{*})\mathrel{\mathop{:}}=(\bm{1}[r\geq r^{*}]-\alpha)(r-r^{*})$, i.e.,
$r_{t}(x_{t},\alpha)=q_{\alpha}(P_{t})\in\operatorname*{arg\,min}_{r\in[0,R]}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i}).$
(2)
A standard improvement called *Split Conformal* [] sets $r_{t}(x_{t},\alpha)=q_{\alpha+o(1)}(P_{t})$, where the $o(1)$ offset (wrt $t\rightarrow\infty$) ensures that even under a relaxation of iid called *exchangeability*, a suitable notion of coverage probability is lower bounded by $\alpha$ [].
- •
*Indirect approach:* Since statistical assumptions often do not hold in practice, a recent trend [] is to remove all statistical assumptions, and instead estimate the empirical quantile of $r^{*}_{1:T}$ using first-order optimization algorithms from *adversarial online learning* [, ]. Taking gradient descent for example, such an approach amounts to picking an initialization $r_{1}(x_{1},\alpha)\in[0,R]$ and following with the *improper*(^3^33Improper means the predicted $r_{t}(x_{t},\alpha)$ can be outside the domain $[0,R]$. As discussed in Section [3](#S3), this is important for achieving low coverage frequency error.) incremental update
$r_{t+1}(x_{t+1},\alpha)=r_{t}(x_{t},\alpha)-\eta_{t}\partial l_{\alpha}(r_{t}(x_{t},\alpha),r^{*}_{t}),$
(3)
where $\eta_{t}>0$ is the *learning rate*, and $\partial l_{\alpha}(r,r^{*})$ can be any subgradient of the quantile loss $l_{\alpha}$ with respect to the first argument. Due to the absence of probability, alternative performance metrics have to be considered, such as the *post-hoc coverage frequency* and the *regret*.

How do these two approaches compare? Although first-order optimization does not need statistical assumptions, it requires being “iterate-centric” rather than “data-centric”: one needs to fix a single confidence level $\alpha$ beforehand, and the predicted threshold $r_{t}(x_{t},\alpha)$ depends on how previous predictions compare to the true scores $r^{*}_{1:t-1}$, rather than just $r^{*}_{1:t-1}$ itself. This leads to some paradoxical observations regarding the obtained confidence sets:

- •
Even if the learning rate $\eta_{t}$ is a constant $\eta$, the threshold prediction $r_{t}(x_{t},\alpha)$, thus also the confidence set $\mathcal{C}_{t}(x_{t},\alpha)$, is not invariant to permutations of $r^{*}_{1:t-1}$.
- •
As demonstrated in Section [2](#S2), two copies of an algorithm with $\alpha_{1}<\alpha_{2}$ can output $\mathcal{C}_{t}(x_{t},\alpha_{2})\subsetneq\mathcal{C}_{t}(x_{t},\alpha_{1})$, even if the initializations are the same. That is, the higher-confidence set is strictly smaller, violating the monotonicity of probability measures.

In contrast, the direct ERM approach does not suffer from such validity issues. The problem is that being equivalent to *Follow the Leader* (FTL) in online learning, it is well-known that ERM can suffer the vacuous $\Omega(T)$ regret on adversarial quantile losses. This motivates an important question:

Can we design an adaptive CP algorithm that enjoys the best of both worlds?

### 1.2 Our result

This paper presents a novel *Bayesian* approach that combines several strengths of previous attempts.

- •
Just like the ERM approach, it can answer multiple arbitrary confidence level queries online.
- •
Without any statistical assumption, and with just the uniform prior, it guarantees the optimal “frequentist” regret bound
$\mathrm{Regret}_{T}(\alpha)\mathrel{\mathop{:}}=\sum_{t=1}^{T}l_{\alpha}(r_{t}(x_{t},\alpha),r^{*}_{t})-\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(r^{*}_{1:T}),r^{*}_{t})=O(R\sqrt{T}),$
simultaneously for all time horizon $T$, true score sequence $r^{*}_{1:T}$, and confidence level $\alpha\in[0,1]$. Notice that the comparator $q_{\alpha}(r^{*}_{1:T})$ would be a natural fixed prediction had one known the empirical distribution of the true score sequence $r^{*}_{1:T}$ beforehand.
- •
Unlike first-order optimization baselines, it does not suffer from the aforementioned validity issues, due to being “data-centric” rather than “iterate-centric”.
- •
Under the iid assumption, it achieves almost the same guarantees, including the *dataset-conditional coverage probability* and the *excess quantile risk*, as the ERM baseline.

From a technical perspective, our algorithm is a simple Bayesian modification of the ERM approach: instead of setting the algorithmic belief as the empirical distribution of the past, $P_{t}=\bar{P}(r^{*}_{1:t-1})$, we set it as the convex combination

$$ $P_{t}=\lambda_{t}P_{0}+(1-\lambda_{t})\bar{P}(r^{*}_{1:t-1}),$ $$

where $P_{0}$ is a prior, and $\lambda_{t}\in[0,1]$ is a hyperparameter. The key observation is that this *Bayesian distribution estimator* leads to *downstream regularization*: the associated score threshold prediction $r_{t}(x_{t},\alpha)=q_{\alpha}(P_{t})$ is equivalent to the output of a non-linearized *Follow the Regularized Leader* (FTRL) algorithm, from which the regret bound naturally follows.

### 1.3 Related work

For additional background of CP and its applications, the readers are referred to several excellent resources [, , , ].

#### Score function

Following [], we first survey a score function for classification, in order to make our setting concrete. Here, given the covariate $x_{t}$, a ML model would generate a *softmax score* $\pi_{t}(y)$ for each candidate label $y$, satisfying $\sum_{y\in\mathcal{Y}}\pi_{t}(y)=1$. [] proposed the score function $s_{t}(x_{t},y)=\sum_{\tilde{y}:\pi_{t}(\tilde{y})\geq\pi_{t}(y)}\pi_{t}(\tilde{y})$. Consistent with our setting, it is negatively oriented, with the range $R=1$.

#### Online CP

Adversarial online CP was first studied by []. It was shown that gradient descent with constant learning rate can guarantee low *coverage frequency error*, i.e.,

$$ $\left|{\alpha-T^{-1}\sum_{t=1}^{T}\bm{1}[r^{*}_{t}\leq r_{t}(x_{t},\alpha)]}\right|=o(1),$ (4) $$

as well as its sliding-window analogues.
Later, [] demonstrated a weakness of this performance metric:
one could trivially satisfy this coverage frequency bound by predicting a data-independent alternation between the empty set and the entire label space. To rule out such cases, the typical solution is to consider an additional performance metric, such as the regret [, , ] and the *multi-calibrated* coverage frequency []. Under the additional iid assumption, [] studied the asymptotic coverage probability achieved by gradient descent.

The present work focuses on regret minimization, as we believe such a perspective offers advantages *even over simultaneously bounding the regret and the coverage frequency error* (since loss linearization is not necessary anymore). See Section [3](#S3) for a thorough discussion.

#### Bayesian uncertainty quantification

The traditional view of Bayesian methods is statistical: there is a statistical model on which we provide a prior, observe the data, and compute the posterior via the Bayes’ theorem. The obtained posterior can then be used to construct confidence sets (called *Bayesian UQ*; []), as long as the prior is good enough and the computational procedure is scalable. Our work shows the effectiveness of the Bayesian idea in an adversarial online CP problem. Importantly, no statistical assumptions are imposed on the data, good theoretical performance does not require an unrealistically good prior, and the algorithm also enjoys the computational efficiency of the CP framework. Related but different from our focus, [] studied a statistical CP problem where the base ML model itself is Bayesian.

#### Adversarial Bayes

Making sequential Bayesian methods “adversarially robust” is closely related to the classical *Follow the Perturbed Leader* (FTPL) algorithm in online learning []. In each round of a repeated game, FTPL randomly perturbs a summary of the historical observations, and best-responds to that using an optimization oracle. This can be regarded as maintaining a posterior belief over all possible environments, and best-responding to a hypothetical environment sampled from the posterior. Notable examples of FTPL include *Thompson sampling*, a prevalent Bayesian approach for bandits and reinforcement learning [, , ], and *U-calibration* [, ], a recently proposed framework for loss-agnostic decision making. Despite being deterministic, our approach resembles the high level idea of U-calibration and a related concept called *omniprediction* [, ]. The connections and differences are discussed in Section [5](#S5).

### 1.4 Notation

This paper studies the *marginal* setting of CP, which means the threshold prediction $r_{t}(x_{t},\alpha)$ will be independent of $x_{t}$; therefore we write it as $r_{t}(\alpha)$ for conciseness. For any symbol $x$, $x_{1:t}$ (e.g., $r^{*}_{1:t}$) represents the tuple $[x_{1},\ldots,x_{t}]$. $\bar{P}(\cdot)$ denotes the empirical distribution of its input, and $q_{\alpha}(\cdot)$ denotes the $\alpha$-quantile. Our regret bound concerns the quantile (or pinball) loss defined as $l_{\alpha}(r,r^{*})\mathrel{\mathop{:}}=(\bm{1}[r\geq r^{*}]-\alpha)(r-r^{*})$. $\log$ denotes the natural logarithm.

## 2 The need for monotonicity

To begin with, we use a numerical experiment to elaborate a validity issue suffered by existing adversarial online CP algorithms: the predicted confidence sets can violate the monotonicity of probability measures. This has been overlooked in the literature, as all the existing approaches we are aware of require fixing a single target confidence level $\alpha$ at the beginning of the CP game. Code is available at [https://github.com/zhiyuzz/Bayesian-Conformal/blob/main/QuantilePrediction_IID.ipynb](https://github.com/zhiyuzz/Bayesian-Conformal/blob/main/QuantilePrediction_IID.ipynb).

Specifically, we consider two baselines, *Online Gradient Descent* (OGD) from [], and *MultiValid Prediction* (MVP) from []. To enable multiple confidence level queries, we adopt the following nearest-neighbor routing on top of their independent copies.

- 1.
Evenly discretize the $[0,1]$ interval of possible confidence levels using a grid $\tilde{A}$.
- 2.
For each $\tilde{\alpha}\in\tilde{A}$, maintain a “base” online CP algorithm targeting $\tilde{\alpha}$.
- 3.
Given any queried $\alpha$, follow the base algorithm corresponding to its nearest neighbor in $\tilde{A}$.

The resulting algorithms are named as MultiOGD and MultiMVP respectively.

In the experiment, we fix $R=1$. The true score sequence $r^{*}_{1:T}$ is sampled iid from the uniform distribution on $[0,1]$, and we evaluate the thresholds $r_{1:T}(\alpha)$ predicted by different CP algorithms, under different $\alpha$ values. For each base OGD targeting $\tilde{\alpha}$, we use the standard learning rate $\eta_{t}=t^{-1/2}$, and initialize it with $r_{1}(\tilde{\alpha})=\tilde{\alpha}$. The base MVP algorithms are all initialized at 0 following []. The point is that the initialization of MultiOGD and MultiMVP cannot be the reason of any monotonicity violation. For comparison, we also test ERM as well as our Bayesian algorithm to be introduced in Section [3](#S3).

Figure: Figure 2: Evaluating the monotonicity of threshold predictions. Ideally the orange line should be always above the blue line, since the associated target confidence level is higher. Columns correspond to different algorithms; rows correspond to different confidence level pairs.
Refer to caption: /html/2410.02561/assets/x2.png

Our results are visualized in Figure [2](#S2.F2). Ideally, in all the figures the orange line should be always above the blue line (i.e., the predicted confidence set due to Eq.([1](#S1.E1)) is larger), since the associated confidence level $\alpha$ is higher. Unlike ERM and our Bayesian algorithm, both MultiOGD and MultiMVP violate this property, which somewhat harms their trustworthiness to downstream users. We remark that although the data generation mechanism and the MultiMVP baseline are both randomized, a single random seed is used in this experiment to demonstrate the existence of the problem.

## 3 Bayesian online conformal prediction

Given a sneak peek into our algorithm, now let us take a deeper dive. Our core algorithm (Algorithm [1](#alg1)) is perhaps the simplest one could think of. Setting the *Bayesian prior* as an arbitrary distribution $P_{0}$ on $[0,R]$ with strictly positive density function $p_{0}$, we update the algorithmic belief $P_{t}$ by mixing $P_{0}$ with the empirical distribution of the previous true scores, $\bar{P}(r^{*}_{1:t-1})$. This can be seen as regularizing the frequentist belief update $P_{t}=\bar{P}(r^{*}_{1:t-1})$, and the readers are referred to Section [5](#S5) for an interpretation of this procedure as *Bayesian distribution estimation*. Then, given each queried confidence level $\alpha$, the algorithm picks $r_{t}(\alpha)=q_{\alpha}(P_{t})$ just like the ERM approach. Note that the algorithmic belief $P_{t}$ does not depend on any specific $\alpha$, and different downstream users can select different $\alpha$ values online.

By construction, it is clear that $r_{t}(\alpha)$ is invariant to permutations of $r^{*}_{1:t-1}$, and for any $\alpha_{1}<\alpha_{2}$ we always have $r_{t}(\alpha_{1})\leq r_{t}(\alpha_{2})$. That is, Algorithm [1](#alg1) does not suffer from the two validity issues described in Section [1.1](#S1.SS1).

Figure: Algorithm 1 Online conformal prediction with regularized belief.

The most important idea of this paper is the following observation.

> The Bayesian regularization on the algorithmic belief $P_{t}$ induces *downstream regularizations* on the predicted threshold $r_{t}(\alpha)$, which best-responds to $P_{t}$.

Concretely, with a base regularizer defined as $\psi(r)\mathrel{\mathop{:}}=\mathbb{E}_{r^{*}\sim P_{0}}[l_{\alpha}(r,r^{*})]$, we characterize this observation by the following equivalence theorem.

###### Theorem 1 .

For all $\alpha\in[0,1]$, the output $r_{t}(\alpha)$ of Algorithm [1](#alg1) satisfies $r_{1}(\alpha)=\operatorname*{arg\,min}_{r\in\mathbb{R}}\psi(r)$,

$$ $r_{t}(\alpha)=\operatorname*{arg\,min}_{r\in\mathbb{R}}\left[{\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}\psi(r)+\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})}\right],\quad\forall t\geq 2.$ (6) $$

Specifically,

- •
$\psi$ is strongly convex with coefficient $\inf_{r\in[0,R]}p_{0}(r)$, if the latter is positive.
- •
If $P_{0}$ is the uniform distribution on $[0,R]$, then $\psi$ is a quadratic function centered at $\alpha R$,
$\psi(r)=\frac{1}{2R}r^{2}-\alpha r+\frac{1}{2}\alpha R.$

Theorem [1](#Thmtheorem1) shows that despite not knowing $\alpha$ at the beginning of the CP game, Algorithm [1](#alg1) generates the same output $r_{t}(\alpha)$ as a non-linearized *Follow the Regularized Leader* (FTRL) algorithm on the quantile loss $l_{\alpha}$. Specifically, Eq.([6](#S3.E6)) can be compared to the FTL-equivalence of the iid-based approach, Eq.([2](#S1.E2)). The important difference is the additional regularizer $\psi(r)$.

To provide more context here: FTRL is a standard improvement of ERM / FTL in adversarial online learning, with better stability and worst-case performance on “difficult loss functions”. Our analysis involves the non-linearized version of FTRL, which has previously received less attention than its linearized counterpart. This is largely due to computational reasons, since non-linearized FTRL has to solve a convex optimization subroutine in each round, whereas linearized FTRL admits closed-form solutions [, Chapter 7.3]. From this perspective, a novelty of our result is showing that for a class of benign regularizers, non-linearized FTRL on quantile losses can be simulated by a simple and efficient Bayesian procedure.

From Theorem [1](#Thmtheorem1), we can then obtain the regret bound of Algorithm [1](#alg1) using the standard FTRL analysis. In order to demonstrate the role of good priors, the strong convexity of the regularizer $\psi$ will be measured locally.

###### Theorem 2 .

Let $\mu_{t,\alpha}\mathrel{\mathop{:}}=\inf\{p_{0}(r):r_{t}(\alpha)\wedge r^{*}_{t}\leq r\leq r_{t}(\alpha)\vee r^{*}_{t}\}$. With the step size $\lambda_{t}=1/\sqrt{t}$, Algorithm [1](#alg1) guarantees

$$ $\mathrm{Regret}_{T}(\alpha)\mathrel{\mathop{:}}=\sum_{t=1}^{T}l_{\alpha}(r_{t}(\alpha),r^{*}_{t})-\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(r^{*}_{1:T}),r^{*}_{t})=O\left({\psi(q_{\alpha}(r^{*}_{1:T}))\sqrt{T}+\sum_{t=1}^{T}\frac{1}{\mu_{t,\alpha}\sqrt{t}}}\right),$ (7) $$

for all time horizon $T$, true score sequence $r^{*}_{1:T}$, and confidence level $\alpha\in[0,1]$. Here, $O(\cdot)$ subsumes an absolute constant. Furthermore, if $P_{0}$ is the uniform distribution on $[0,R]$, then

$$ $\mathrm{Regret}_{T}(\alpha)=O(R\sqrt{T}).$ $$

Let us interpret this regret bound. Suppose the time horizon $T$ and the empirical true score distribution $\bar{P}(r^{*}_{1:T})$ are known beforehand (but the exact $r^{*}_{1:T}$ sequence is unknown), then for all $\alpha$, a very natural strategy is to predict $r_{t}(\alpha)=q_{\alpha}(r^{*}_{1:T})$. Theorem [2](#Thmtheorem2) shows that without any statistical assumption, Algorithm [1](#alg1) with the uniform prior asymptotically performs as well as this oracle in terms of the total quantile loss, and importantly, the $O(R\sqrt{T})$ regret bound is known to be tight [, ]. Existing first-order optimization baselines are equipped with regret bounds of a similar type [, , ], but the difference is that they require knowing the confidence level $\alpha$ beforehand, whereas Algorithm [1](#alg1) achieves low regret simultaneously for all $\alpha\in[0,1]$.

###### Theorem 1 .

###### Theorem 2 .

#### The role of good prior

A particular strength of Theorem [2](#Thmtheorem2) is that the $O(R\sqrt{T})$ regret bound only requires the simplest uniform prior. Nonetheless,
if one has extra prior knowledge on the environment, picking a more sophisticated prior can indeed bring advantages. To see this, notice that the function $\psi$ in Eq.([7](#S3.E7)) is minimized at $q_{\alpha}(P_{0})$, therefore ideally we would aim for $P_{0}\approx\bar{P}(r^{*}_{1:T})$, which means $q_{\alpha}(P_{0})\approx q_{\alpha}(r^{*}_{1:T})$ for all $\alpha$. But unlike the discrete distribution $\bar{P}(r^{*}_{1:T})$, $P_{0}$ also needs to have a “positive enough” density function, as otherwise the second term in Eq.([7](#S3.E7)) would blow up.

#### Coverage frequency error

We also note that existing first-order optimization baselines [, , ] are equipped with both a regret bound and a coverage frequency error bound, Eq.([4](#S1.E4)). Hoping to challenge this convention, here we discuss the advantages of only considering the regret.

First, the coverage frequency error is fundamentally “iterate-centric”, whereas an ideal performance metric needs to be “data-centric”. To be more specific, consider the CP interaction protocol displayed in Figure [1](#S1.F1). Achieving low coverage frequency error requires the CP algorithm’s output to depend not only on the top level (the nature and the base model), but also on the users’ previous confidence level queries. This is in contrast with our regret minimization algorithm, whose output is independent of the users’ query history.

Furthermore, just like the pathological example given by [], first-order optimization baselines essentially achieve the desirable coverage frequency due to the “overshooting” provided by the loss linearization. This is perhaps clear from the first online CP algorithm (ACI) proposed by []: regarding the update Eq.([3](#S1.E3)) with the constant learning rate $\eta_{t}=\eta$, it is shown that the coverage frequency error monotonically decreases as $\eta\rightarrow\infty$. Such a peculiar behavior results precisely from overshooting: if $\alpha=90\%$, then a failed coverage needs nine successful coverages to compensate, and *ensuring* this does not have much to do with the observed data. This casts some natural doubt on the coverage frequency error that the algorithm is designed to optimize.

To reduce the clutter, more discussion on Algorithm [1](#alg1) is deferred to Section [5](#S5). Below we present a few extensions of this core result.

### 3.1 Reducing memory usage via quantization

Recall our construction of MultiOGD from Section [2](#S2). Although not studied by existing works, it is not hard to see that with the size of the grid $\tilde{A}$ being $O(\sqrt{T})$, MultiOGD also satisfies the same $\alpha$-agnostic $O(R\sqrt{T})$ regret bound as in Theorem [2](#Thmtheorem2), since the quantile loss $l_{\alpha}(r,r^{*})$ is $R$-Lipschitz with respect to $\alpha$. This raises a natural question: Algorithm [1](#alg1) requires $O(T)$ memory due to storing the empirical distribution of previous true scores – can we reduce it to $O(\sqrt{T})$?

#### Quantized algorithm

Here is a variant of Algorithm [1](#alg1), denoted as Quantized, achieving this goal. The idea is to discretize the domain $[0,R]$ rather than the $\alpha$-space: we maintain an evenly-spaced grid of size $\sqrt{T}$ over $[0,R]$, round each observed $r^{*}_{t}$ to its nearest neighbor $\tilde{r}^{*}_{t}$ on the grid, and replace the belief update Eq.([5](#S3.E5)) by

$$ $P_{t}=\lambda_{t}P_{0}+(1-\lambda_{t})\bar{P}(\tilde{r}^{*}_{1:t-1}).$ $$

The associated regret bound follows from the Lipschitzness of $l_{\alpha}(r,r^{*})$ with respect to $r^{*}$.

###### Theorem 3 .

With $\lambda_{t}=1/\sqrt{t}$ and the uniform $P_{0}$, Quantized achieves $\mathrm{Regret}_{T}(\alpha)=O(R\sqrt{T})$.

Compared to MultiOGD, Quantized achieves the same $O(R\sqrt{T})$ regret bound with $O(\sqrt{T})$ memory, while avoiding its validity issues. There is another practical advantage: after observing each $r^{*}_{t}$, MultiOGD needs to update all $\sqrt{T}$ base algorithms, whereas Quantized performs only one update on the algorithmic belief $\bar{P}_{t}$, and then makes $\left|{A_{t}}\right|$ inferences using the prediction head.

###### Theorem 3 .

### 3.2 Adaptivity to IID

In practice, a CP algorithm is often applied without knowing the characteristics of the nature. Previously we have been focusing on the adversarial setting, but what if the true scores $r^{*}_{1:T}$ turn out to be iid? We now demonstrate the *adaptivity* of Algorithm [1](#alg1): it automatically achieves almost the same guarantees as ERM under the additional iid assumption.

First, as the coverage probability becomes the default performance metric in the iid setting, we present the following bound on the *dataset-conditional coverage probability*. Notice that the event of successful coverage can be expressed as $r^{*}_{t}\leq r_{t}(\alpha)$, where $r_{t}(\alpha)$ is determined by the past true scores $r^{*}_{1:t-1}$ and the queried $\alpha$.

###### Theorem 4 .

Assume the true score sequence $r^{*}_{1},r^{*}_{2},\ldots$ is drawn iid from an unknown continuous distribution $\mathcal{D}$. With the step size $\lambda_{t}=1/\sqrt{t}$ and an arbitrary prior $P_{0}$, Algorithm [1](#alg1) guarantees that for any fixed $t\geq 2$, with probability at least $1-\delta$ over the randomness of $r^{*}_{1:t-1}$, we have for all $\alpha\in[0,1]$,

$$ $\alpha-\sqrt{\frac{\log(2/\delta)}{2(t-1)}}-\frac{1}{\sqrt{t}-1}\leq\mathbb{P}_{r^{*}_{t}\sim\mathcal{D}}\left[{r^{*}_{t}\leq r_{t}(\alpha)}\right]\leq\alpha+\sqrt{\frac{\log(2/\delta)}{2(t-1)}}+\frac{1}{\sqrt{t}-1}+\frac{1}{t-1}.$ $$

Compared to the analogous result for ERM [, Theorem 34], the difference here due to the Bayesian regularization is the $(\sqrt{t}-1)^{-1}$ factor, which is dominated by the existing $O(\sqrt{t^{-1}\log\delta^{-1}})$ term resulting from the randomness. It shows that under the iid assumption, Algorithm [1](#alg1) achieves almost the same coverage probability error as Split Conformal, despite being designed for the adversarial setting.

Besides the coverage probability, we can also analyze the *excess quantile risk* of Algorithm [1](#alg1), which matches the standard oracle inequality one would obtain using ERM.

###### Theorem 5 .

Assume the true score sequence $r^{*}_{1},r^{*}_{2},\ldots$ is drawn iid from an unknown distribution $\mathcal{D}$. With the step size $\lambda_{t}=1/\sqrt{t}$ and an arbitrary prior $P_{0}$, Algorithm [1](#alg1) guarantees that for any fixed $t\geq 2$, with probability at least $1-\delta$ over the randomness of $r^{*}_{1:t-1}$, we have for all $\alpha\in[0,1]$,

$$ $\mathbb{E}_{r^{*}_{t}\sim\mathcal{D}}[l_{\alpha}(r_{t}(\alpha),r^{*}_{t})]\leq\min_{r\in[0,R]}\mathbb{E}_{r^{*}_{t}\sim\mathcal{D}}[l_{\alpha}(r,r^{*}_{t})]+O\left({R\sqrt{\frac{\log(1/\delta)}{t}}}\right).$ $$

###### Theorem 4 .

###### Theorem 5 .

### 3.3 Continual distribution shift

Starting from [], the study of adversarial online CP has been largely motivated by the prevalence of continual distribution shifts in practice. Tackling this challenge requires *non-converging* algorithms characterized by sliding-window performance guarantees. We now present a discounted variant of Algorithm [1](#alg1), denoted by Discounted, along this direction.

#### Discounted algorithm

Let $\beta\in(0,1)$ be a *discount factor*, which is a bandwidth hyperparameter required by Discounted. Then, we define a regularized and discounted empirical distribution of $r^{*}_{1:t}$ recursively by

$$ $\bar{P}_{\beta}(r^{*}_{1})=\beta P_{0}+(1-\beta)\delta(r^{*}_{1}),$ $$

$$ $\bar{P}_{\beta}(r^{*}_{1:t})=\beta\bar{P}_{\beta}(r^{*}_{1:t-1})+(1-\beta)\delta(r^{*}_{t})=\beta^{t}P_{0}+(1-\beta)\sum_{i=1}^{t}\beta^{t-i}\delta(r^{*}_{i}),$ $$

where $\delta(r^{*}_{t})$ is the distribution with point mass at $r^{*}_{t}$. This is used to replace the undiscounted empirical distribution in the belief update, i.e., Eq.([5](#S3.E5)) is replaced by

$$ $P_{t}=\lambda_{t}P_{0}+(1-\lambda_{t})\bar{P}_{\beta}(r^{*}_{1:t-1}).$ $$

After that, the prediction head remains unchanged, i.e., $r_{t}(\alpha)=q_{\alpha}(P_{t})$.

Similar to Theorem [1](#Thmtheorem1) and [2](#Thmtheorem2), we can show that Discounted simulates the $\beta$-discounted non-linearized FTRL, which is equipped with a $\beta$-discounted regret bound. Importantly, reasonable step sizes $\lambda_{t}$ become constant (rather than decreasing), which emphasizes the crucial role of the prior $P_{0}$: instead of only using $P_{0}$ to regularize the beginning of the CP game, Discounted continually mix $P_{0}$ into its algorithm belief with constant weight, such that it does not “overfit the current environment”.

###### Theorem 6 .

With $\lambda_{t}=\lambda=\frac{\sqrt{1-\beta}}{\beta+\sqrt{1-\beta}}$ and the uniform $P_{0}$, the output $r_{t}(\alpha)$ of Discounted satisfies

$$ $r_{t}(\alpha)=\operatorname*{arg\,min}_{r\in\mathbb{R}}\left[{(1-\beta)^{-1}\left({\frac{\lambda}{1-\lambda}+\beta^{t-1}}\right)\psi(r)+\sum_{i=1}^{t-1}\beta^{t-1-i}l_{\alpha}(r,r^{*}_{i})}\right],$ $$

for all $\alpha$ and $t$. In addition, for all $\alpha\in[0,1]$, it guarantees the discounted regret bound

$$ $\mathrm{Regret}_{T,\beta}(\alpha)\mathrel{\mathop{:}}=\sum_{t=1}^{T}\beta^{T-t}l_{\alpha}(r_{t}(\alpha),r_{t}^{*})-\min_{r\in[0,R]}\sum_{t=1}^{T}\beta^{T-t}l_{\alpha}(r,r_{t}^{*})\leq\frac{R}{\sqrt{1-\beta}}+o(R),$ $$

where $o(\cdot)$ is with respect to $T\rightarrow\infty$.

We remark that [, Theorem 7] presents a discounted regret lower bound on linear losses, which can be converted to $\Omega(\min\{\alpha,1-\alpha\}R/\sqrt{1-\beta^{2}})$ on the quantile losses we consider. Since $(1-\beta)^{-1/2}\leq 2(1-\beta^{2})^{-1/2}$ for all $\beta\in(0,1)$, Theorem [6](#Thmtheorem6) matches this lower bound in the minimax sense (with respect to $\alpha$, i.e., when $\alpha=1/2$).

###### Theorem 6 .

## 4 Experiment

Complementing our theoretical results, we now evaluate the performance of our Bayesian approach using more experiments. Code is available at [https://github.com/zhiyuzz/Bayesian-Conformal](https://github.com/zhiyuzz/Bayesian-Conformal).

Figure: Figure 3: Regret on switching data.
Refer to caption: /html/2410.02561/assets/x10.png

#### Switching sequence

First, to demonstrate the failure of ERM without the iid assumption, we consider a synthetic $r^{*}_{1:T}$ sequence which switches in every round between 0 and 1. Similar to Section [2](#S2), four algorithms are tested: OGD [], MVP [],(^4^44Similar to Section [2](#S2), we use a single random seed for the MVP baseline throughout this section, since we find the results to be generally insensitive to the seed.) ERM and our Bayesian algorithm Quantized. Figure [3](#S4.F3) plots their regret measured by the quantile loss, under two different $\alpha$ values.

Consistent with the classical online learning theory, ERM becomes brittle when $\alpha$ matches the long run average of $r^{*}_{1:T}$ (i.e, $0.5$), suffering linear regret with respect to $T$. In contrast, both OGD (with $\eta_{t}=t^{-1/2}$; $\alpha$ is known) and our Bayesian algorithm achieve sublinear regret under both $\alpha$ values. Quite different from the conventional online learning framework, MVP is designed to minimize the conditional empirical coverage error, but nonetheless, it achieves low regret when $\alpha=0.5$. The limitation is that MVP requires a relatively long period to warm up: when $\alpha=0.7$, the regret of MVP grows linearly at the beginning, before hitting a plateau at $T\approx 800$.

#### Stock price

Next, we move to an actual CP problem: predicting the time-varying volatility of the stock price, with the base model being a standard time series forecasting method called GARCH []. This experiment was designed by [] and further studied by []. See [, Appendix B.3.1] for the specifics of its context.

Two baselines are considered: a specialization of OGD (ACI) for time series forecasting, and MVP. Besides requiring a fixed learning rate, the former operates on a sliding time window whose length is also a hyperparameter. Similarly, MVP requires picking the size of discretization. For both baselines, we follow the exact implementation from [], including the hyperparameters.

As for our Bayesian approach, we adopt the discounted version to handle the continual distribution shift, together with quantization. The discretization grid $\tilde{A}$ has the same size as the MVP baseline, and we pick the discount factor $\beta$ such that the effective length $(1-\beta^{2})^{-1}$ of the discounted time window exactly matches the length of the ACI baseline’s sliding window. Given this $\beta$, $\lambda_{t}$ is selected according to Theorem [6](#Thmtheorem6). It means that compared to the baselines, our algorithm cannot benefit from any extra hyperparameter tuning.

Figure: Figure 4: Predicted score threshold on AMD stock data.
Refer to caption: /html/2410.02561/assets/x12.png

Figure: Figure 5: Quantile loss on AMD stock data.
Refer to caption: /html/2410.02561/assets/x13.png

With $\alpha=0.9$, Figure [4](#S4.F4) plots the $r_{1:T}(\alpha)$ sequence predicted by different algorithms. As a visual sanity check, our algorithm generates a reasonable prediction sequence with slightly less fluctuation than the baselines. To make a more concrete comparison, Figure [5](#S4.F5) plots the total quantile loss suffered by all three algorithms, as well as the difference compared to ACI. It shows that our algorithm achieves almost the same total loss as ACI, and it is faster to warm up than MVP.

Finally, we also evaluate the empirical coverage rate of the tested algorithms. Although our algorithm is not designed for this metric, it performs competitively compared to the baselines. The target is $1-\alpha=0.9$, and closer to this target is better. ACI achieves $0.901$, MVP achieves $0.893$, and our Bayesian algorithm achieves $0.899$. Appendix [B](#A2) includes results on a different stock dataset.

## 5 Discussion

#### Loss-agnostic decision making

The downstream simulation of FTRL (Theorem [1](#Thmtheorem1)) deviates from the common scope of online learning, which requires specifying a single loss function in each round. Instead, it has a similar flavor as the recently proposed concept of *U-calibration* [, ]: forecasting for an unknown downstream agent. Prior works on U-calibration considered the setting of *finite-class distributional prediction* with generic *proper* losses, while our paper focuses on the continuous domain $[0,R]$ (i.e., “infinitely many classes”) with the more specific quantile losses. The extra problem structure allows our algorithm to be deterministic (rather than being randomized like FTPL), thus establishing a closer connection to typical deterministic algorithms in *online convex optimization*.

*Omniprediction* [, ] is another iconic framework for loss-agnostic decision making, whose main idea is to maintain a *multi-calibrated* algorithmic belief in the sense of []. Our approach does not require calibration as an underlying mechanism.

#### Bayesian interpretation

We have been calling our framework “Bayesian”, as the belief update Eq.([5](#S3.E5)) can be viewed by statisticians as a *Bayesian distribution estimator* from iid samples. Following [, Chapter 23], we now make this very concrete.

Consider the following distribution estimation problem: given $x_{1},\ldots,x_{n}\in\mathcal{X}$ sampled iid from an unknown distribution $X$, what is a good estimate of $X$? As opposed to the frequentist estimate $\bar{P}(x_{1:n})$, a Bayesian estimator would place a prior $F_{0}$ over all distributions supported on the domain $\mathcal{X}$, compute the posterior $F_{n}$ from the samples, and output the mean $\mathbb{E}[F_{n}]$.

For analytical convenience, one would typically choose $F_{0}$ as a *conjugate prior*: it refers to a family of priors such that if $F_{0}$ belongs to this family, then $F_{n}$ also belongs to this family. The most notable conjugate prior for distribution estimation is the *Dirichlet process* (DP), denoted as $\mathrm{DP}(\alpha,P_{0})$. Here $\alpha$ and $P_{0}$ are hyperparameters: $P_{0}$ equals the mean $\mathbb{E}[\mathrm{DP}(\alpha,P_{0})]$, while $\alpha$ controls the variance of $\mathrm{DP}(\alpha,P_{0})$. Due to the conjugacy, if $F_{0}=\mathrm{DP}(\alpha,P_{0})$, then

$$ $F_{n}=\mathrm{DP}\left({\alpha+n,\frac{\alpha}{\alpha+n}P_{0}+\frac{n}{\alpha+n}\bar{P}(x_{1:n})}\right).$ $$

Consequently, the Bayesian estimator of the distribution $X$ is

$$ $\mathbb{E}[F_{n}]=\frac{\alpha}{\alpha+n}P_{0}+\frac{n}{\alpha+n}\bar{P}(x_{1:n}).$ $$

This is the same as the belief update Eq.([5](#S3.E5)) in our algorithm, with the hyperparameter $\lambda_{t}=\alpha/(\alpha+n)$. Our results can therefore be regarded as an online adversarial treatment of Bayesian inference, embedded in the CP protocol, and without the iid assumption.

## 6 Conclusion

Focusing on the online adversarial formulation of conformal prediction, this paper demonstrates various benefits of being Bayesian. Specifically, we propose a novel Bayesian algorithm with a number of strengths – it supports multiple arbitrary confidence level queries, achieves probably low regret, avoids two validity issues on the obtained confidence sets, and adapts to iid environments. We further develop quantized and discounted extensions of this algorithm, and our theoretical arguments are supported by experiments.

For future directions, we believe that an important remaining problem in online conformal prediction is to rigorously characterize the strengths and limitations of various performance metrics. This paper contains an argument against the coverage frequency error, but additional effort is needed to make it more quantitative and concrete. Besides, it is valuable to have *group-conditional* guarantees analogous to [, ], and we defer their possible combinations with the Bayesian idea to future works.

## Acknowledgement

This work is partially funded by Harvard University Dean’s Competitive Fund for Promising Scholarship.

## Appendix

## Appendix A Omitted proofs

See [1](#Thmtheorem1)

###### Proof of Theorem 1 .

We first rewrite the base regularizer $\psi$ as

$$ $\displaystyle\psi(r)$ $\displaystyle=\int_{0}^{R}l_{\alpha}(r,r^{*})p_{0}(r^{*})dr^{*}$ $\displaystyle=(1-\alpha)\int_{0}^{r}(r-r^{*})p_{0}(r^{*})dr^{*}+\alpha\int_{r}^{R}(r^{*}-r)p_{0}(r^{*})dr^{*}.$ $$

It is twice-differentiable, with

$$ $\psi^{\prime}(r)=(1-\alpha)\int_{0}^{r}p_{0}(r^{*})dr^{*}-\alpha\int_{r}^{R}p_{0}(r^{*})dr^{*}=\int_{0}^{r}p_{0}(r^{*})dr^{*}-\alpha,$ $$

and $\psi^{\prime\prime}(r)=p_{0}(r)$. The strong convexity statement on $\psi$ is thus clear. If $P_{0}$ is uniform, we have

$$ $\displaystyle\psi(r)$ $\displaystyle=R^{-1}\left[{(1-\alpha)\int_{0}^{r}(r-r^{*})dr^{*}+\alpha\int_{r}^{R}(r^{*}-r)dr^{*}}\right]$ $\displaystyle=\frac{1}{2R}\left[{(1-\alpha)r^{2}+\alpha(R-r)^{2}}\right]=\frac{1}{2R}r^{2}-\alpha r+\frac{1}{2}\alpha R.$ $$

Next, consider the first part of the theorem. The case of $t=1$ is straightforward to verify. For any $t\geq 2$, Algorithm [1](#alg1) outputs

$$ $\displaystyle r_{t}(\alpha)$ $\displaystyle=q_{\alpha}\left[{\lambda_{t}P_{0}+(1-\lambda_{t})\bar{P}(r^{*}_{1:t-1})}\right]$ $\displaystyle=\min\left\{r:\lambda_{t}\int_{0}^{r}p_{0}(r^{*})dr^{*}+\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r]\geq\alpha\right\}.$ (8) $$

On the other hand, consider the optimization objective in Eq.([6](#S3.E6)), which we write as

$$ $F_{t}(r)\mathrel{\mathop{:}}=\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}\psi(r)+\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i}).$ (9) $$

Notice that the function $F_{t}(r)$ is continuous and right-differentiable. Taking its right-derivative, we have

$$ $\displaystyle F^{\prime}_{t,+}(r)$ $\displaystyle=\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}\left[{\int_{0}^{r}p_{0}(r^{*})dr^{*}-\alpha}\right]+\left({-\alpha\sum_{i=1}^{t-1}\bm{1}[r<r^{*}_{i}]+(1-\alpha)\sum_{i=1}^{t-1}\bm{1}[r\geq r^{*}_{i}]}\right)$ $\displaystyle=\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}\int_{0}^{r}p_{0}(r^{*})dr^{*}-\frac{\alpha\lambda_{t}(t-1)}{1-\lambda_{t}}-\alpha(t-1)+\sum_{i=1}^{t-1}\bm{1}[r\geq r^{*}_{i}]$ $\displaystyle=\frac{t-1}{1-\lambda_{t}}\left({\lambda_{t}\int_{0}^{r}p_{0}(r^{*})dr^{*}+\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r\geq r^{*}_{i}]-\alpha}\right).$ $$

Comparing it to Eq.([8](#A1.E8)), we see that the output $r_{t}(\alpha)$ of Algorithm [1](#alg1), given by Eq.([8](#A1.E8)), satisfies

$$ $r_{t}(\alpha)=\min\{r:F^{\prime}_{t,+}(r)\geq 0\}.$ $$

Since the function $F_{t}(r)$ is strictly convex, we have $r_{t}(\alpha)=\operatorname*{arg\,min}_{r}F_{t}(r)$, which is equivalent to Eq.([6](#S3.E6)).
∎

See [2](#Thmtheorem2)

###### Proof of Theorem 2 .

The proof can be decomposed into the following steps.

###### Proof of Theorem 1 .

###### Proof of Theorem 2 .

#### Step 1

Starting from the FTRL formulation Eq.([6](#S3.E6)), we first verify that the regularizer weight $\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}$ is increasing with respect to $t$ (when $t>1$), which is required by the FTRL analysis. To this end, define

$$ $h_{t}\mathrel{\mathop{:}}=\frac{\lambda_{t}(t-1)}{1-\lambda_{t}}=\frac{t-1}{\sqrt{t}-1}.$ $$

Taking the derivative with respect to $t$, for all $t>1$,

$$ $\frac{dh_{t}}{dt}=\frac{\sqrt{t}-1-\frac{t-1}{2\sqrt{t}}}{(\sqrt{t}-1)^{2}}=\frac{t-2\sqrt{t}+1}{2\sqrt{t}(\sqrt{t+1}-1)^{2}}=\frac{(\sqrt{t}-1)^{2}}{2\sqrt{t}(\sqrt{t+1}-1)^{2}}\geq 0.$ $$

For completeness, we also define $h_{1}=1$.

Besides, we have the order estimate $h_{t}=O(\sqrt{t})$, $1/h_{t}=O(1/\sqrt{t})$, where $O(\cdot)$ only hides an absolute constant.

#### Step 2

Next, due to Theorem [1](#Thmtheorem1), we can apply the standard FTRL analysis. Recall our notation from Eq.([9](#A1.E9)): we write the optimization objective in Eq.([6](#S3.E6)) as

$$ $F_{t}(r)\mathrel{\mathop{:}}=h_{t}\psi(r)+\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i}),\quad\forall t\geq 2.$ $$

Similarly, we also write $F_{1}(r)\mathrel{\mathop{:}}=h_{1}\psi(r)$. Notice that $r_{t}(\alpha)=\operatorname*{arg\,min}_{r\in\mathbb{R}}F_{t}(r)$ for all $t$.

The classical FTRL equality lemma [, Lemma 7.1] states that

$$ $\displaystyle\mathrm{Regret}_{T}(\alpha)$ $\displaystyle=h_{T+1}\psi(q_{\alpha}(r^{*}_{1:T}))-\min_{r\in\mathbb{R}}\psi(r)+\sum_{t=1}^{T}\left[{F_{t}(r_{t}(\alpha))-F_{t+1}(r_{t+1}(\alpha))+l_{\alpha}(r_{t}(\alpha),r^{*}_{t})}\right]$ $\displaystyle\qquad+F_{T+1}(r_{T+1}(\alpha))-F_{T+1}(q_{\alpha}(r^{*}_{1:T}))$ $\displaystyle\leq h_{T+1}\psi(q_{\alpha}(r^{*}_{1:T}))+\sum_{t=1}^{T}\left[{F_{t}(r_{t}(\alpha))-F_{t+1}(r_{t+1}(\alpha))+l_{\alpha}(r_{t}(\alpha),r^{*}_{t})}\right],$ $$

where the second line is due to $\min_{r}\psi(r)\geq 0$, and $r_{T+1}(\alpha)=\operatorname*{arg\,min}_{r\in\mathbb{R}}F_{T+1}(r)$.

Consider the sum on the RHS, where for conciseness we omit $(\alpha)$ in the notation. This is the typical one-step quantity involved in the FTRL analysis. Following a similar procedure as [, Lemma 7.8], we have

$$ $\displaystyle F_{t}(r_{t})-F_{t+1}(r_{t+1})+l_{\alpha}(r_{t},r^{*}_{t})$ $\displaystyle=~{}$ $\displaystyle F_{t}(r_{t})+l_{\alpha}(r_{t},r^{*}_{t})-F_{t}(r_{t+1})-l_{\alpha}(r_{t+1},r^{*}_{t})+(h_{t}-h_{t+1})\psi(r_{t+1})$ $\displaystyle\leq~{}$ $\displaystyle F_{t}(r_{t})+l_{\alpha}(r_{t},r^{*}_{t})-F_{t}(r_{t+1})-l_{\alpha}(r_{t+1},r^{*}_{t})$ ( $h_{t+1}\geq h_{t}$ , $\psi(r_{t+1})\geq 0$ ) $\displaystyle\leq~{}$ $\displaystyle F_{t}(r_{t})+l_{\alpha}(r_{t},r^{*}_{t})-\min_{r\in\mathbb{R}}\left[{F_{t}(r)+l_{\alpha}(r,r^{*}_{t})}\right].$ $$

Observe that since $F_{t}(\cdot)$ and $l_{\alpha}(\cdot,r^{*}_{t})$ are both convex, the minimizing argument of their sum lies between their respective unique minimizers, $r_{t}$ and $r^{*}_{t}$. On this segment, the function $F_{t}$ is $h_{t}\mu_{t,\alpha}$-strongly-convex, where $\mu_{t,\alpha}$ is defined in the assumption of the theorem. We now proceed using the property of strong convexity [, Lemma 7.6], which we restate as Lemma [A.1](#A1.Thmlemma1).

Concretely, if $g_{t}$ is a subgradient of $l_{\alpha}(\cdot,r^{*}_{t})$ at $r_{t}$, then it is also a subgradient of $F_{t}(\cdot)+l_{\alpha}(\cdot,r^{*}_{t})$ at $r_{t}$, since $r_{t}=\operatorname*{arg\,min}_{r}F_{t}(r)$. Moreover, such a subgradient $g_{t}$ satisfies $\left|{g_{t}}\right|\leq 1$ due to $l_{\alpha}(\cdot,r^{*}_{t})$ being $1$-Lipschitz. Combining these with the strong convexity, Lemma [A.1](#A1.Thmlemma1) yields

$$ $F_{t}(r_{t})+l_{\alpha}(r_{t},r^{*}_{t})-\min_{r\in\mathbb{R}}\left[{F_{t}(r)+l_{\alpha}(r,r^{*}_{t})}\right]\leq\frac{1}{2h_{t}\mu_{t,\alpha}}.$ $$

Plugging this all the way back into the regret bound, we have

$$ $\displaystyle\mathrm{Regret}_{T}(\alpha)$ $\displaystyle\leq h_{T+1}\psi(q_{\alpha}(r^{*}_{1:T}))+\frac{1}{2}\sum_{t=1}^{T}\frac{1}{h_{t}\mu_{t,\alpha}}$ $\displaystyle=O\left({\psi(q_{\alpha}(r^{*}_{1:T}))\sqrt{T}+\sum_{t=1}^{T}\frac{1}{\mu_{t,\alpha}\sqrt{t}}}\right).$ $$

#### Step 3

Finally we analyze the special case of uniform prior. From Theorem [1](#Thmtheorem1),

$$ $\psi(q_{\alpha}(r^{*}_{1:T}))\leq\max_{r\in[0,R]}\psi(r)\leq\max_{r\in[0,R]}\left({\frac{1}{2R}r^{2}-\alpha r+\frac{1}{2}\alpha R}\right)\leq\frac{R}{2}.$ $$

Furthermore, $\mu_{t,\alpha}=1/R$. Plugging in $\sum_{t=1}^{T}t^{-1/2}=O(\sqrt{T})$ completes the proof.
∎

See [3](#Thmtheorem3)

###### Proof of Theorem 3 .

Recall from Section [3.1](#S3.SS1) that the quantized true score is denoted by $\tilde{r}^{*}_{t}$. From Theorem [2](#Thmtheorem2), we have

$$ $\displaystyle\sum_{t=1}^{T}l_{\alpha}(r_{t}(\alpha),\tilde{r}^{*}_{t})-\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(r^{*}_{1:T}),\tilde{r}^{*}_{t})$ $\displaystyle\leq\sum_{t=1}^{T}l_{\alpha}(r_{t}(\alpha),\tilde{r}^{*}_{t})-\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(\tilde{r}^{*}_{1:T}),\tilde{r}^{*}_{t})$ $\displaystyle=O(R\sqrt{T}).$ $$

As $\left|{\tilde{r}^{*}_{t}-r^{*}_{t}}\right|\leq R/\sqrt{T}$ and the quantile loss function $l_{\alpha}(r,r^{*})$ is $1$-Lipschitz with respect to $r^{*}$, we have

$$ $\displaystyle\left|{\sum_{t=1}^{T}l_{\alpha}(r_{t}(\alpha),\tilde{r}^{*}_{t})-\sum_{t=1}^{T}l_{\alpha}(r_{t}(\alpha),r^{*}_{t})}\right|$ $\displaystyle\leq\sum_{t=1}^{T}\left|{l_{\alpha}(r_{t}(\alpha),\tilde{r}^{*}_{t})-l_{\alpha}(r_{t}(\alpha),r^{*}_{t})}\right|$ $\displaystyle\leq\sum_{t=1}^{T}\left|{\tilde{r}^{*}_{t}-r^{*}_{t}}\right|\leq R\sqrt{T}.$ $$

The comparator term $\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(r^{*}_{1:T}),\tilde{r}^{*}_{t})$ can be related similarly to $\sum_{t=1}^{T}l_{\alpha}(q_{\alpha}(r^{*}_{1:T}),r^{*}_{t})$, and combining the above completes the proof.
∎

See [4](#Thmtheorem4)

###### Proof of Theorem 4 .

The proof follows a similar strategy as [, Theorem 34]. First, for any fixed $t\geq 2$, the samples $r^{*}_{1:t-1}$ have no ties almost surely, since the underlying distribution $\mathcal{D}$ is continuous. We will condition the rest of the analysis on this event.

Next, recall Algorithm [1](#alg1)’s prediction rule, Eq.([8](#A1.E8)). On one hand, we have

$$ $\lambda_{t}\int_{0}^{r_{t}(\alpha)}p_{0}(r^{*})dr^{*}+\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]\geq\alpha,$ $$

which means

$$ $\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]\geq\alpha-\lambda_{t},$ $$

$$ $\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]\geq\alpha+\frac{\lambda_{t}}{1-\lambda_{t}}(\alpha-1)\geq\alpha-\frac{1}{\sqrt{t}-1}.$ $$

On the other hand, if we define $m=\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]$ and let $r^{*}_{-1}$ be the $(m-1)$-th smallest element of $r^{*}_{1:t-1}$, then it is also clear from Eq.([8](#A1.E8)) that

$$ $\lambda_{t}\int_{0}^{r^{*}_{-1}}p_{0}(r^{*})dr^{*}+\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r^{*}_{-1}]\leq\alpha,$ $$

which means

$$ $\frac{1-\lambda_{t}}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r^{*}_{-1}]\leq\alpha-\lambda_{t}\int_{0}^{r^{*}_{-1}}p_{0}(r^{*})dr^{*}\leq\alpha,$ $$

$$ $\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r^{*}_{-1}]\leq\frac{\alpha}{1-\lambda_{t}}\leq\alpha+\frac{1}{\sqrt{t}-1},$ $$

$$ $\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]\leq\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r^{*}_{-1}]+\frac{1}{t-1}\leq\alpha+\frac{1}{\sqrt{t}-1}+\frac{1}{t-1}.$ $$

In summary,

$$ $\alpha-\frac{1}{\sqrt{t}-1}\leq\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]\leq\alpha+\frac{1}{\sqrt{t}-1}+\frac{1}{t-1}.$ (10) $$

Finally we apply the DKW inequality (Lemma [A.3](#A1.Thmlemma3)). For all $\varepsilon>0$, we have

$$ $\mathbb{P}_{r^{*}_{1:t-1}}\left[{\sup_{\alpha\in[0,1]}\left|{\left({\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]}\right)-\mathbb{P}_{r^{*}_{t}}[r^{*}_{t}\leq r_{t}(\alpha)]}\right|>\varepsilon}\right]\leq 2\exp\left[{-2(t-1)\varepsilon^{2}}\right].$ $$

Therefore, with probability at least $1-\delta$ over the randomness of $r^{*}_{1:t-1}$, we have

$$ $\left|{\left({\frac{1}{t-1}\sum_{i=1}^{t-1}\bm{1}[r^{*}_{i}\leq r_{t}(\alpha)]}\right)-\mathbb{P}_{r^{*}_{t}}[r^{*}_{t}\leq r_{t}(\alpha)]}\right|\leq\sqrt{\frac{\log(2/\delta)}{2(t-1)}},\quad\forall\alpha\in[0,1].$ $$

Combining it with Eq.([10](#A1.E10)) above completes the proof.
∎

See [5](#Thmtheorem5)

###### Proof of Theorem 5 .

The proof follows from a standard uniform convergence argument [] combined with the Lipschitzness of the quantile loss.

First, notice that with any combination of $\alpha$, $r$ and $r^{*}$, the quantile loss $l_{\alpha}(r,r^{*})\in[0,R]$. Therefore, fixing any $\alpha\in[0,1]$ and $r\in[0,R]$, we apply the Hoeffding’s inequality (Lemma [A.2](#A1.Thmlemma2)) to obtain

$$ $\mathbb{P}_{r^{*}_{1:t-1}}\left[{\left|{\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})-\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r,r^{*}_{t})]}\right|\geq\varepsilon}\right]\leq 2\exp\left({-\frac{2(t-1)\varepsilon^{2}}{R^{2}}}\right).$ $$

Next, we evenly discretize $[0,1]$ by a grid of size $\sqrt{t}$, and also $[0,R]$ by a grid of size $\sqrt{t}$, and denote their combination as a set $S$. $\left|{S}\right|=t$. For all $\alpha$ and $r$, there exists $(\tilde{\alpha},\tilde{r})\in S$ satisfying $\left|{\alpha-\tilde{\alpha}}\right|\leq 1/\sqrt{t}$ and $\left|{r-\tilde{r}}\right|\leq R/\sqrt{t}$. Applying the union bound on $S$ yields

$$ $\mathbb{P}_{r^{*}_{1:t-1}}\left[{\max_{(\alpha,r)\in S}\left|{\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})-\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r,r^{*}_{t})]}\right|\geq\varepsilon}\right]\leq 2t\exp\left({-\frac{2(t-1)\varepsilon^{2}}{R^{2}}}\right),$ $$

which means with probability at least $1-\delta$,

$$ $\max_{(\alpha,r)\in S}\left|{\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})-\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r,r^{*}_{t})]}\right|\leq R\sqrt{\frac{\log(2t/\delta)}{2(t-1)}}.$ $$

Since $l_{\alpha}(r,r^{*})$ is $R$-Lipschitz with respect to $\alpha$, and $1$-Lipschitz with respect to $r$, we have

$$ $\max_{0\leq\alpha\leq 1,0\leq r\leq R}\left|{\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})-\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r,r^{*}_{t})]}\right|\leq R\sqrt{\frac{\log(2t/\delta)}{2(t-1)}}+\frac{2R}{\sqrt{t}}.$ $$

Finally, due to Theorem [1](#Thmtheorem1) we have for all
$\alpha$ and $r$,

$$ $\displaystyle\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r_{t}(\alpha),r^{*}_{i})$ $\displaystyle\leq\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})+\frac{\lambda_{t}}{1-\lambda_{t}}\left[{\psi(r)-\psi(r_{t}(\alpha))}\right]$ $\displaystyle\leq\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})+\frac{1}{\sqrt{t}-1}\max\left\{\psi(0),\psi(R)\right\}$ $\displaystyle\leq\frac{1}{t-1}\sum_{i=1}^{t-1}l_{\alpha}(r,r^{*}_{i})+\frac{R}{\sqrt{t}-1}.$ $$

Combining it with the generalization error bound above, with high probability we have for all $\alpha$ and $r$,

$$ $\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r_{t}(\alpha),r^{*}_{t})]\leq\mathbb{E}_{r^{*}_{t}}[l_{\alpha}(r,r^{*}_{t})]+\frac{R}{\sqrt{t}-1}+2\left({R\sqrt{\frac{\log(2t/\delta)}{2(t-1)}}+\frac{2R}{\sqrt{t}}}\right).$ $$

Taking $\min_{r}$ on the RHS completes the proof.
∎

See [6](#Thmtheorem6)

###### Proof of Theorem 6 .

Analogous to Eq.([8](#A1.E8)), we can write the output of Discounted as

$$ $\displaystyle r_{t}(\alpha)$ $\displaystyle=q_{\alpha}\left[{\lambda P_{0}+(1-\lambda)\bar{P}_{\beta}(r^{*}_{1:t-1})}\right]$ $\displaystyle=\min\left\{r:\frac{r}{R}\left[{\lambda+\beta^{t-1}(1-\lambda)}\right]+(1-\lambda)(1-\beta)\sum_{i=1}^{t-1}\beta^{t-1-i}\bm{1}[r^{*}_{i}\leq r]\geq\alpha\right\}.$ $$

Similar to Eq.([9](#A1.E9)), this can be verified as a minimizer of the objective

$$ $H_{t}(r)\mathrel{\mathop{:}}=(1-\beta)^{-1}\left({\frac{\lambda\beta^{1-t}}{1-\lambda}+1}\right)\psi(r)+\sum_{i=1}^{t-1}\beta^{-i}l_{\alpha}(r,r^{*}_{i}).$ $$

For the convenience of notation, we will write the regularizer weight as $z_{t}\mathrel{\mathop{:}}=(1-\beta)^{-1}\left({\frac{\lambda\beta^{1-t}}{1-\lambda}+1}\right)$.

Notice that with the uniform $P_{0}$, the base regularizer $\psi$ is $R^{-1}$-strongly-convex due to Theorem [1](#Thmtheorem1), therefore we can apply the strong-convexity-based FTRL analysis [, Corollary 7.9] on the scaled loss functions,

$$ $h_{t}(r)\mathrel{\mathop{:}}=\beta^{-t}l_{\alpha}(r,r^{*}_{t}).$ $$

This yields

$$ $\sum_{t=1}^{T}h_{t}(r_{t}(\alpha))-\min_{r\in[0,R]}\sum_{t=1}^{T}h_{t}(r)\leq z_{T}\left[{\max_{r\in[0,R]}\psi(r)-\min_{r\in[0,R]}\psi(r)}\right]+\frac{R}{2}\sum_{t=1}^{T}\frac{g_{t}^{2}}{z_{t}^{2}},$ $$

where $g_{t}$ can be any subgradient of $h_{t}(r)$ at $r=r_{t}(\alpha)$. Scaling both sides by $\beta^{T}$, we recover the discounted regret definition on the LHS:

$$ $\mathrm{Regret}_{T,\beta}(\alpha)\leq\beta^{T}z_{T}\left[{\max_{r\in[0,R]}\psi(r)-\min_{r\in[0,R]}\psi(r)}\right]+\frac{R\beta^{T}}{2}\sum_{t=1}^{T}\frac{g_{t}^{2}}{z_{t}}.$ $$

Next we simplify the obtained expression. The range of $\phi$ is contained in $[0,R/2]$. In addition, $\left|{g_{t}}\right|\leq\beta^{-t}$ since the quantile loss $l_{\alpha}(r,r^{*})$ is $1$-Lipschitz with respect to $r$. Therefore,

$$ $\sum_{t=1}^{T}\frac{g_{t}^{2}}{z_{t}}\leq\sum_{t=1}^{T}\frac{\beta^{-2t}}{(1-\beta)^{-1}\left({\frac{\lambda\beta^{1-t}}{1-\lambda}+1}\right)}\leq\frac{1-\beta}{\beta}\frac{1-\lambda}{\lambda}\sum_{t=1}^{T}\beta^{-t}\leq\frac{1-\lambda}{\lambda}\beta^{-T-1},$ $$

$$ $\mathrm{Regret}_{T,\beta}(\alpha)\leq\frac{R}{2}\left({\frac{\beta^{T}}{1-\beta}+\frac{\lambda}{1-\lambda}\frac{\beta}{1-\beta}+\frac{1-\lambda}{\lambda}\frac{1}{\beta}}\right).$ $$

Notice that our choice of $\lambda$ satisfies $\frac{\lambda}{1-\lambda}=\beta^{-1}\sqrt{1-\beta}$, therefore

$$ $\mathrm{Regret}_{T,\beta}(\alpha)\leq\frac{R}{2}\left({\frac{\beta^{T}}{1-\beta}+\frac{2}{\sqrt{1-\beta}}}\right)=\frac{R}{\sqrt{1-\beta}}+o(R),$ $$

where $o(\cdot)$ is with respect to $T\rightarrow\infty$.
∎

###### Proof of Theorem 3 .

###### Proof of Theorem 4 .

###### Proof of Theorem 5 .

###### Proof of Theorem 6 .

### A.1 Auxiliary lemma

###### Lemma A.1 (Lemma 7.6 of [ 23 ] ) .

Let $f$ be a $\mu$-strongly convex function with respect to a norm $\left\|{\cdot}\right\|$, over a convex set $V$. For all $x,y\in V$ and subgradients $g\in\partial f(y)$, $g^{\prime}\in\partial f(x)$, we have

$$ $f(x)-f(y)\leq\left\langle g,x-y\right\rangle+\frac{1}{2\mu}\left\|{g-g^{\prime}}\right\|_{*}^{2}.$ $$

Here $\left\langle\cdot,\cdot\right\rangle$ denotes the inner product, and $\left\|{\cdot}\right\|_{*}$ denotes the dual norm of $\left\|{\cdot}\right\|$.

The following lemma is a standard tool in ML due to [].

###### Lemma A.2 (Hoeffding’s inequality) .

Let $x_{1},\ldots,x_{n}$ be iid samples of a real-valued random variable on $[a,b]$. Let $\bar{x}$ be the mean of the distribution. Then, for all $\varepsilon>0$, we have

$$ $\mathbb{P}\left[{\left|{\frac{1}{n}\sum_{i=1}^{n}x_{i}-\bar{x}}\right|\geq\varepsilon}\right]\leq 2\exp\left({-\frac{2n\varepsilon^{2}}{(b-a)^{2}}}\right).$ $$

The next lemma is the celebrated Dvoretzky–Kiefer–Wolfowitz inequality, due to [, ].

###### Lemma A.3 (DKW inequality) .

Let $x_{1},\ldots,x_{n}$ be iid samples of a real-valued random variable with cumulative distribution function $F$, and let $\bar{P}(x_{1:n})$ be the empirical distribution of $x_{1:n}$, with cumulative distribution function $\hat{F}_{n}$. For all $\varepsilon>0$, we have

$$ $\mathbb{P}\left[{\sup_{x\in\mathbb{R}}\left|{\hat{F}_{n}(x)-F(x)}\right|>\varepsilon}\right]\leq 2\exp(-2n\varepsilon^{2}).$ $$

###### Lemma A.1 (Lemma 7.6 of [ 23 ] ) .

###### Lemma A.2 (Hoeffding’s inequality) .

###### Lemma A.3 (DKW inequality) .

## Appendix B Additional experiment

Extending Section [4](#S4), this section presents the result of our stock price experiment using a different dataset (NVDA instead of AMD). The same procedure from Section [4](#S4) is followed. Figure [6](#A2.F6) plots the predicted thresholds, and Figure [7](#A2.F7) plots the total quantile loss. Overall they exhibit the similar behavior as the result from Section [4](#S4).

Figure: Figure 6: Predicted score threshold on NVDA stock data.
Refer to caption: /html/2410.02561/assets/x15.png

Figure: Figure 7: Quantile loss on NVDA stock data.
Refer to caption: /html/2410.02561/assets/x16.png

As for the coverage frequency, ACI achieves $0.899$, MVP achieves $0.891$, and our Bayesian algorithm achieves $0.897$. Again, closer to the target $0.9$ is better. The conclusion is that in the fixed-$\alpha$ setting our algorithm performs competitively compared to the baselines, while in the multi-$\alpha$ setting it demonstrates the advantage from Section [2](#S2).

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: - In general in Bayesian methods for UQ, the role of the prior is very important to have good performance. So I would be curious to know if other reasonable choices of priors for the score thresholds would improve the regret compared to the uniform prior (apart from the one mentioned in line 320). Is this something that you have explored ?
soundness: 3
strengths: The paper is overall clearly written (I did not check carefully the math in Appendix B) and the proposed method is both simple and seems to have good guarantees.
summary: This paper introduces an algorithm to compute prediction sets in the context of online conformal prediction : given a sequence of previous input and labels, the goal is to compute (for a new observed input) a score threshold leading to a prediction set. 
The main idea of their algorithm is to define, at each step, a mixture of a prior distribution P_0 and the empirical distribution of the previous scores, and to use the quantile of this mixture as score thresholds. This approach is similar to the Follow The Regularized Leader (FTRL) in the bandits literature. From this similarity, the authors compute a regret bound for their algorithm and show that for a simple choice of prior (uniform distribution), their algorithm has a regret of O(\sqrt{T}). In the case of distribution shift, a variant of their algorithm reaches constant discounted regret.
Moreover, contrary to other existing approaches, the authors claim that the prediction intervals computed using their method satisfy a form of monoticity (meaning that the score thresholds for a higher coverage will be higher than those  for a lower coverage). 
Numerical experiments show that the method performs competitively with other approaches (online gradient descent, ERM, etc.)
weaknesses: I would have like more details on the numerical experiments. From what I understand, the figures only show that the method reaches the target coverage, but what about the size of the prediction sets that it produces ? How does it compare to other methods ? Also, the memory usage of the method ( O(\sqrt(T}) for the quantized version) seems redhibitory at first glance, but is not evaluated in practice in the experiments.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: - Can you provide more details on MultiOGD [in Section 2]. The current version is so sketchy that it is difficult to read.
- Provide more details in Section 3 [I know that the paper is short, you could provide more details in the appendix for example]
soundness: 4
strengths: - The paper is clearly written and comprehensively explains its novel Bayesian approach to online conformal prediction. It effectively outlines the limitations of existing methods and clearly presents its contributions. The theoretical foundations are well-developed, and the empirical results are presented to complement the theory, making the concepts accessible to readers. The structure allows for an easy understanding of the core ideas, technical details, and the practical advantages of the proposed method.
- The paper contains many interesting results, which are novel to my best knowledge
    - Theorem 2 establishes the regret bound for the Bayesian CP algorithm, showing that it achieves \( O(R\sqrt{T}) \) regret for any sequence length \( T \) and confidence level \( \alpha \) in adversarial settings.
    - Theorem 3 introduces the quantized version of the algorithm, demonstrating that it achieves the same \( O(R\sqrt{T}) \) regret bound with reduced memory requirements of \( O(\sqrt{T}) \).
   -  Theorem 4 shows, under the iid assumption,  that the Bayesian CP algorithm achieves probabilistic coverage guarantees similar to ERM-based CP in iid contexts.
   - Theorem 5  addresses the excess quantile risk under the iid assumption, demonstrating that the Bayesian CP algorithm achieves similar performance as traditional ERM approaches in iid environments.
   - Theorem 6 provides a discounted regret bound for the variant of the Bayesian CP algorithm designed to handle continual distribution shifts. This bound matches minimax optimality, indicating the algorithm’s resilience in non-stationary environments.
summary: The paper  presents a  novel approach to online conformal prediction (CP) that uses Bayesian regularization to overcome the limitations of previous direct and indirect CP methods. Conventional methods rely either on empirical quantile predictions (direct approach) or on adversarial optimization (indirect approach).  The Bayesian approach presented here addresses these issues by introducing a regularized Bayesian framework that combines empirical and prior-based distributions, thereby enabling more robust predictions without statistical assumptions about the data distribution.

Key contributions include:
- by implementing Bayesian regularization, the model provides reliable confidence sets that avoid the validity problems of purely adversarial CP methods, such as non-monotonicity across confidence levels.
- The Bayesian CP model achieves an optimal regret boundary, maintains competitive performance across different confidence levels, and provides stable results in both iid and adversarial contexts.
- Unlike traditional methods that require a single preset confidence level, the Bayesian approach supports online responses to arbitrary confidence queries - a critical improvement for dynamic, real-world applications.

The framework is theoretically validated with regret bounds and empirically demonstrated on both synthetic and real-world datasets, showing superior adaptability and efficiency compared to existing CP methods.
weaknesses: I do not see serious weak points.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: My main suggestion is to be clearer on what exactly a downstream user might be asking for, in specific inferential use cases, to support the goal of tracking with respect to multiple alpha values simultaneously.  A secondary suggestion is to clarify in what sense this is really Bayesian inference, beyond simply having a sum-of-distributions interpretation.  Why isn't this just an FTRL story pure and simple.
soundness: 3
strengths: It is true, and perhaps helpful, to point out that quantile-tracking algorithms can be incoherent in terms of the confidence sets that they deliver for different values of alpha.  It is also useful to point out that FTRL can address this issue.  Some of the other detailed critiques of Gibbs & Candes (e.g., the overshooting) are reasonable.
summary: The authors aim to contribute to the burgeoning literature on conformal prediction, in particular the approach based on quantile tracking.  The main goal of the paper is to develop a method that treats a set of alpha values, and not a single alpha value that has been fixed a priori.  The technical approach is essentially follow-the-regularized leader (FTRL) on the pinball loss, with an interpretation of the regularization in FTRL as a (nonparametric) Bayesian prior.
weaknesses: I'm not entirely sure what I've learned from the paper, other than being reminded of some of the virtues of FTRL.

Indeed, I want to emphasize that as best I can tell, this is a FTRL paper.  The connection to Bayesian inference is weak at best, and not very helpful.  There's a regularizer, but that alone doesn't make for Bayesian inference.  At the end of the paper, there's a suggestion that when regularization involves adding a uniform distribution to an empirical distribution we can interpret this as the (posterior mean) of a Dirichlet process, but I'm at a loss as to why that kind of Bayesian nonparametric terminology is called for here.  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.  Moreover, if one is really wanting to be Bayesian here, then it's the entire quantile process that should be the object of inference.

The main motivation of the paper doesn't seem to be Bayesian at all, but rather simply online learning, in a setting in which quantiles corresponding to multiple alpha values are desired.  Now, I'm not sure exactly when and how multiple alpha values might be desired by a downstream user.  Is there a decision-theoretic justification for asking for this?  The authors don't go much beyond simply suggesting that it's desirable in some intuitive sense.

There are frameworks in statistics for making repeated tentative decisions over time, e.g., the nonnegative supermartingale
approach, and such decision-theoretic frameworks are clearer (to me) ways of getting at the issue being hinted at here.

The other motivation for pursuing this approach is the "paradox" (lack of invariance to permutations) associated with quantile tracking. 
But this critique seems to lose its punch when one remembers that one of the main motivations for the quantile tracking approaches
is that of handling nonstationarity.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: My main gripes with the paper are:

- Too much focus on the IID setting (which is not what online conformal prediction is about)
- Theoretical results for non-IID data being lacking;
- Lacking experimental analysis;
- From the existing experimental analysis, I see no clear advantage of the method, and the theoretical contributions are not notable enough to compensate for it.

(All of them are better described in the 'Weaknesses' section.)

Any clarification or improvement on these points are appreciated.

I believe that, in its current form, the paper is not ready for acceptance, due to the issues raised above, and have thus opted for rejection.
That said, I would be willing to increase my score (and perhaps substantially) should my concerns above be resolved.
soundness: 3
strengths: The key idea of having an online conformal prediction method mimic online bayesian inference methods is interesting, and, as far as I am aware, original. The text is reasonably clear, and the authors provide a substantial number of theoretical guarantees, substantiating their method's strength. The inclusion of analyses in the IID case (i.e., not just an arbitrarily adversarial case) is appreciated.
summary: The paper proposes a method for online conformal prediction leveraging a Follow-the-Regularized-Leader approach, where the regularization is derived from a prior. Theoretical justification for the method is provided by the means of regret bounds. The method is empirically evaluated on synthetic data as well as financial time series.
weaknesses: The paper has a number of significant weaknesses.

- Line 117: The first paradox does not seem paradoxical at all. We are in a setting where, in principle, exchangeability does not hold. That precisely means that the order in which we have observed our data carries information. So our method *should not* be invariant to this order!
- The paper is about online conformal prediction, and thus for settings where exchangeability & IID do not hold. However, the paper focuses excessively on the IID setting, except for a single section (Section 3.3), which introduces a separate algorithm (dubbed 'Discounted') and a corresponding theorem (Theorem 6), and Theorem 2. 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. Theorem 2 suffers from the same issue. (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!)
- The experimental evaluation is very weak. Online conformal prediction is a topic that requires significant experimental evaluation. The paper's theoretical contributions aren't notable enough nor are any new things possible with the proposed method, so an advantage of the method validated through experiments (e.g., that the coverage would be more robust, or that the intervals would be smaller) is essential.
    - The only data considered was one synthetic dataset and stock market data. The main problem is, of course, with the real data; only stock market data was considered. Data coming from the stock market (and especially price time series) have very particular structure. The authors should consider many other time series. Moreover, considering all the attention that the authors laid on the IID setting, there was no dataset considering it (but, to be clear, I would rather the authors deemphasize the IID setting than an additional focus of experiments on IID data).
    - The baselines being considered are severly lacking. The authors consider ACI (Gibbs & Candès, 2021) and MVP (Bastani et al., 2022). While I wholeheartedly agree that these two methods should be present, they are already a bit dated, and considering only them brings a misleading comparison, as they are not quite the state-of-the-art anymore. Here are some other methods I suggest comparing against:
        - AgACI (https://arxiv.org/abs/2202.07282)
        - Bellman CP (https://arxiv.org/abs/2402.05203)
        - Copula CP (https://arxiv.org/abs/2212.03281)
        - Conformal PID control (https://arxiv.org/abs/2307.16895)
    - Finally, I must note that even with the lacking experimental comparison, I don't exactly see an advantage of the proposed method compared to the baselines.

Additionally, a number of nitpicks (which do not impact my score, but should probably be improved upon):

- Line 073: "without any statistical assumption at all" -- that's not right. While the assumptions are indeed quite lax, there _are_ statistical assumptions: namely, that the protocol described in lines 054-063 is followed (which implies, e.g., that confidence level chosen for a time step is independent of the outcome conditional on the past along with the new covariates).
- On the definition of the quantile in equation (2), you should consider the infimum rather than the minimum to ensure that the quantile is well-defined.
- Line 096: I'd expect a reader of this paper to be familiar with exchangeability. " a relaxation of iid called exchangeability" sounds like talking down. Also, consider citing https://arxiv.org/abs/2005.06095, which is an excellent reference on exchangeability and CP.
- Section 2 should probably be moved to the experiments section, or even the supplementary material. The experiment and the fact that it is embasing has already been mentioned in the introduction; additional motivation is not needed.
- Calling the proposed method 'Bayesian' feels a bit like a misnormer. There is no statistical model being used for Bayesian inference, no likelihood and no Bayes update. It is only related to Bayesian inference by the analogy of regularization being typically equivalent to some form of Bayesian inference and the specification of a 'prior' distribution. That said, again, this is a nitpick and has not weighted into my decision.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. Is it possible to achieve lower regret by adpatively choosing the regularized belief?
2. Is there a way to detect distributional shift such that the step size can be chosen adaptively? Is there a uniform way to measure the performance/regret for both the iid/exchangeable case and the distribution shift case?
soundness: 4
strengths: The paper is well-written and clear to its points. The Bayesian method proposed is easy to understand and implement. The theoretical guarantees of a tight regret bound is provided, and the CIs are monotone in the nominal level $\alpha$. The method enjoys both desired properties for "data-centric" and "iterate-centric" approaches, and is able to recover previous known bounds under properly chosen learning rate. Numerical experiments comparing to previous benchmarks were provided.
summary: The authors propose a Bayesian frame work for comformal prediction, bridging the two scenarios of "data-centric" approach where usually iid/exchangibility assumption is required, and the "iterate-centric" approach which is more robust towards distributional shift.

The Bayescian CP method has a few desired properties: the confidence sets are montone in the nominal confidence level $\alpha$ for the online prediction; the $O(\sqrt{T})$ regret bound is achieved; the method adapts to both the iid case and distributional shift case with properly chosen step size.
weaknesses: 1. The uniform prior is robust, but as the authors had mentioned, if certain knowledge is known a tighter bound could be achieved potentially. I would be interested to see more fine-grained analysis in this scenario, and whether there is a way to update the regularized belief instead of using the same one upon observing more data.
2. For the continual distribution shift case, the learning rate is constant for the discounted regret. There seems to be a gap of choosing diminising ($O(1/\sqrt{t})$) step size and $O(1)$ step size, and how to choose this adaptively.

Meta-review: Summary:

This paper introduces a Bayesian-inspired approach for online conformal prediction that aims to integrate strengths from both "data-centric" and "iterate-centric" methodologies. While it has theoretical merit, significant issues remain unresolved regarding its conceptual clarity, novelty, and experimental evaluation.

Strengths:

The proposal addresses the inconsistency of predictions for different confidence levels in traditional conformal prediction approaches.
Theoretical guarantees are provided, including regret bounds, which are well-aligned with the online learning framework.

Weaknesses:

Use of Bayesian Terminology: The use of "Bayesian" in the title and throughout the paper is misleading. The method lacks a clear Bayesian inferential framework, as highlighted by multiple reviewers. This terminology seems primarily rhetorical, which undermines the clarity and positioning of the work.

Lack of Novelty: The core method appears to be a straightforward application of Follow the Regularized Leader (FTRL). The claimed contributions, including the use of priors and a "Bayesian perspective," fail to substantiate meaningful technical advancements.

Weak Experimental Validation: The experiments are limited in scope, lack comparisons with state-of-the-art baselines, and fail to convincingly demonstrate practical advantages over existing methods. The focus on stock market data and the absence of broader, diverse datasets reduce the impact of the empirical results.

Conceptual Ambiguity: The discussion fails to justify the practical necessity of multiple alpha values, and the proposed approach risks enabling practices akin to p-hacking. Moreover, the invariance to permutation is poorly motivated and arguably undesirable in online settings.

Discussion:
While some reviewers found the idea of combining "data-centric" and "iterate-centric" approaches interesting, the conceptual and methodological execution is not sufficiently robust. Concerns regarding the misleading use of Bayesian terminology and the lack of novelty relative to FTRL were not adequately addressed in the discussion. Furthermore, the weak experimental evaluation fails to compensate for these conceptual shortcomings.

Conclusion:
Although the paper touches on an interesting topic, its issues—particularly the lack of conceptual clarity and convincing novelty—prevent me from recommending acceptance at this stage. Future work should focus on refining the core methodology, clarifying its conceptual underpinnings, and providing more rigorous experimental validation.

Decision: Reject