The Importance of Being Bayesian in Online Conformal Prediction

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-03 22:25:03

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. Converting the targeted confidence levels to quantile levels, the problem can be reduced to predicting the quantiles (in hindsight) of a sequentially revealed data sequence, where existing results can be divided into two types. 
- Assuming the data sequence is iid, one could maintain the empirical distribution of the observed data as an algorithmic belief, and directly predict its quantiles. 
- As the iid assumption is often violated in practice, a recent trend is to apply first-order online optimization on moving quantile losses (Gibbs & Candes, 2021). This indirect approach requires knowing the targeted quantile level beforehand, and suffers from certain validity issues on the obtained confidence sets, due to the associated loss linearization.

This paper presents a Bayesian approach 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".

From a technical perspective, our key idea is to take the above iid-based procedure and regularize its algorithmic belief 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 nonparametric distribution estimation. Importantly, the proposed belief update backbone is shared by "prediction heads" targeting different confidence levels, bringing practical benefits similar to U-calibration (Kleinberg et al., 2023).

Main paper: 
 introduction: 
 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) [VGS05] 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 Submitted to Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (BDU at NeurIPS 2024). Do not distribute. traditional statistical methods. In a nutshell, CP algorithms make confidence set predictions (rather than point 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. Writing the covariatelabel space as X × Y and the time horizon as T , we consider the following sequential interaction protocol. In each (the t-th) round, 1. We, as the CP algorithm, observe a target covariate x t ∈ X from the nature, and a score functions t : X × Y → [0, R] generated by a black-box ML model BASE. 12. The downstream users select a finite set of confidence level queries, A t ⊂ [0, 1]. Given each α ∈ A t , we predict a score threshold r t (α),2 which leads to a confidence setC t (x t , α) = {y ∈ Y : s t (x t , y) ≥ r t (α)} .(1)3. We observe the ground truth label y t ∈ Y from the nature, and send the (x t , y t ) pair to BASE (which it optionally uses to update the score function s t+1 ). Define the true score r * t := s t (x t , y t ).The essential objective of CP is to have the prediction r t (α) close to the (1 -α)-quantile of the true score sequence r * 1:T , while only knowing r * 1:t-1 [Rot22, Tib23] . For the readers' reference, the (1 -α)-quantile of a real random variable X is defined as q 1-α (X) := min{x; P(X ≤ x) ≥ 1 -α}. Guided by this general principle, the community has focused on two very different approaches under distinct assumptions.• Assuming the sequence r * 1:T is iid, it suffices to maintain the empirical distribution of r * 1:t-1 , denoted as P t = P (r * 1:t-1 ), as an algorithmic belief. Then, when queried with the confidence level α, the CP algorithm directly "post-processes" the belief by setting r t (α) = q 1-α (P t ), or in situations with only exchangeability, q 1-α-o(1) (P t ) [Tib23] . This is essentially Empirical Risk Minimization (ERM) with the quantile loss l α (r, r * ) :EQUATION• Since the iid assumption is often violated in practice, a recent trend [GC21] is to indirectly view CP as an instance of adversarial online learning [Haz23, Ora23] , and apply first-order optimization algorithms from there. Taking gradient descent for example, such an approach amounts to picking r 1 (α) ∈ [0, R] and following with the projected incremental updater t+1 (α) = Π [0,R] [r t (α) -η t ∂l α (r t (α), r * t )], where η t > 0 is the learning rate, and ∂l α (r, r * ) can be any subgradient of the quantile loss l α with respect to the first argument.Strictly speaking the two approaches are incomparable due to targeting different performance metrics, but nonetheless, let us compare the algorithms side by side. Although first-order optimization seems more robust due to the nonnecessity of statistical assumptions, it requires being "iterate-centric" rather than "data-centric": one needs to fix a single confidence level α beforehand, and the prediction r t (α) depends on how previous predictions r 1:t-1 (α) compare to the "data" r * 1:t-1 , rather than just the "data" itself. This leads to some paradoxical observations regarding the obtained confidence sets.For example,• The confidence set C t is not invariant to permutations of r * 1:t-1 .• Suppose one runs two first-order optimization algorithms targeting different α (say,α 1 < α 2 ), then even if the initialization r 1 (α 1 ) = r 1 (α 2 ), it is still possible that C t (x t , α 1 ) is strictly contained in C t (x t , α 2 ).That is, the confidence sets violate the monotonicity of probability measures.In contrast, the ERM approach does not suffer from such issues, therefore is more "valid / plausible" in some sense. The problem is that ERM, also known as Follow the Leader (FTL) in online learning, is not robust to adversarial environments with quantile losses. Can we enjoy the best of both worlds?Contribution This paper presents a Bayesian approach to CP, which (i) does not require any statistical assumption; (ii) does not suffer from the aforementioned validity issues; and (iii) efficiently handles multiple, arbitrary confidence levels revealed online, with provably low regret. Our main workhorse, in short, is an online adversarial view of Bayesian nonparametric estimation. 
main result: 
 Overview Our proposed algorithm (Algorithm 1) is perhaps the simplest one could think of.Defining the Bayesian prior as an arbitrary distribution P 0 on the domain [0, R] (with strictly positive density p 0 : [0, R] → R >0 ), we update the algorithmic belief P t by mixing P 0 with the empirical distribution of the previous true scores, P (r * 1:t-1 ). This can be seen as regularizing the frequentist belief update P t = P (r * 1:t-1 ). Then, given each queried confidence level α, our algorithm picks r t (α) = q 1-α (P t ) just like the iid-based approach. It is clear that r t (α) is invariant to permutations of r * 1:t-1 , and for any α 1 < α 2 we always have r t (α 1 ) ≤ r t (α 2 ).Algorithm 1 Online conformal prediction with regularized belief. Require:Step sizes {λ t } t∈N+ , where each λ t ∈ [0, 1] and λ 1 = 1. Bayesian prior P 0 . 1: for t = 1, 2, . . . do 2:Compute the empirical distribution P (r * 1:t-1 ), and set the algorithmic belief P t toEQUATION3:for α ∈ A t do 4:Output the score threshold r t (α) = q 1-α (P t ).end for 6:Observe the true score r * t . 7: end for Our central observation, however, is quite profound in our opinion:The Bayesian regularization on the algorithmic belief P t induces downstream regularizations on the predicted threshold r t (α).In particular, Theorem 1 shows that despite not knowing α beforehand, Algorithm 1 generates the same output r t (α) as a non-linearized Follow the Regularized Leader (FTRL) algorithm with the quantile loss l α . To provide more context, FTRL is a standard improvement of ERM / FTL with better stability in adversarial environments, and our framework involves its non-linearized version which retains the full structure of quantile losses. It is also important to note that the downstream simulation of FTRL deviates from the common scope of online learning (which requires specifying a single loss function in each round [Haz23, Ora23] ), and instead has a similar flavor as the recently proposed U-calibration [KLST23, LSS24]: forecasting for an unknown downstream agent.From a more technical perspective: prior works on U-calibration considered the setting of "finite-class distributional prediction" with generic proper losses [KLST23, LSS24], 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 Follow the Perturbed Leader; FTPL), thus establishing a closer connection to deterministic online convex optimization.Appendix A further discusses the interpretation of the belief update Eq.(3) as Bayesian nonparametric distribution estimation. The nontrivial insight here is that this statistical procedure induces downstream adversarial regret bounds, without statistical assumptions at all.Analysis Formally, we first present the FTRL-equivalence of Algorithm 1, which can be compared to the FTL-equivalence of the iid-based approach, i.e., Eq.(2).Theorem 1. With a base regularizer defined as ψ(r) := E r * ∼P0 [l α (r, r * )], the output r t (α) of Algorithm 1 satisfiesEQUATIONSpecifically, (i) ψ is strongly convex with coefficient inf r∈[0,R] p 0 (r); and (ii) if P 0 is the uniform distribution on [0, R], then ψ is the quadratic function,ψ(r) = 1 2R r 2 -(1 -α)r + 1 2 (1 -α)R.Next, using Theorem 1, we obtain the following regret bound for our CP algorithm. Here we only consider the uniform prior, and defer the case of generic priors to longer versions of this paper (the benefit of good priors can be shown using the local norm analysis of FTRL [Ora23, Section 7.4]).Theorem 2. Let P 0 be the uniform distribution on [0, R]. With the step size λ t = 1/ √ t, the output of Algorithm 1 against any r * 1:T sequence satisfiesT t=1 l α (r t (α), r * t ) - T t=1 l α (q 1-α (r * 1:T ), r * t ) = O(R √ T ), ∀α ∈ [0, 1],where q 1-α (r * 1:T ) denotes the (1 -α)-quantile of the hindsight empirical distribution P (r * 1:T ), and O(•) subsumes absolute constants.Let us interpret this bound. Suppose P (r * 1:T ) is known beforehand (but the exact r * 1:T sequence is unknown), then for all α, a very reasonable strategy is to predict r t (α) = q 1-α (r * 1:T ). Theorem 2shows that without statistical assumptions, Algorithm 1 asymptotically performs as well as this oracle in terms of the total quantile loss. Existing first-order optimization baselines are equipped with regret bounds of a similar type [BWXB23, GC24, ZBY24], but the key difference is that they require knowing α beforehand, whereas Algorithm 1 achieves low regret simultaneously for all α ∈ [0, 1]. 
discussion: 
 Any-α baseline Although not studied in existing works, it is actually possible to construct a nonstochastic CP algorithm from first-order optimization algorithms, without specifying a fixed α beforehand. The idea is simple: (i) evenly discretize the [0, 1] interval using a grid Ā of size √ T ;(ii) for each ᾱ ∈ Ā, run a "base" CP algorithm targeting ᾱ; and (iii) at test time, given a queried α, However, such a baseline also suffers from the previously mentioned validity issues. Even more, the update (based on r * t ) and the queries (based on A t ) are coupled: if A t is empty for a certain t (all the users abstain), the baseline still needs O( √ T ) time in that round to process the observation r * t . In comparison, Algorithm 1 needs one UPDATETIME to process r * t and |A t | QUERYTIME to answer the α-queries, where their exact values depend on the data structure used to maintain the belief P t .Coverage bound A common objective in online CP, initiated by [GC21] , is to show that given a confidence level α, the post-hoc empirical coverage frequency of an algorithm approaches α, i.e.,α -T -1 T t=1 1[r * t ≥ r * t (α)] = o(1).Since this can be achieved by switching between r * t (α) = 0 and r * t (α) = R independently of data[BGJ + 22],one needs an extra objective, such as the regret (Theorem 2), to justify the validity of an online CP method. Existing first-order optimization baselines satisfy both desirable bounds.Here we argue that the regret could be a better-posed objective than the coverage. To support this argument, notice that just like the previous pathological example, first-order optimization baselines achieve the coverage bound due to the "overshooting" provided by the loss linearization, and the latter also causes the validity issues discussed earlier. Besides, achieving the coverage bound requires adjusting the prediction based on the coverage history: if an algorithm keeps mis-covering, then it has to predict a very small r t (α) to "almost ensure" coverage. These are different from regret minimization, where loss linearization is not necessary, and the algorithm is incentivized to bestrespond to its belief (on the empirical distribution of the environment in hindsight).Theorem 1. With a base regularizer defined as ψ(r) := E r * ∼P0 [l α (r, r * )], the output r t (α) of Algorithm 1 satisfiesEQUATIONSpecifically, (i) ψ is strongly convex with coefficient inf r∈[0,R] p 0 (r); and (ii) if P 0 is the uniform distribution on [0, R], then ψ is the quadratic function,ψ(r) = 1 2R r 2 -(1 -α)r + 1 2 (1 -α)R.Proof of Theorem 1. We first rewrite the base regularizer ψ asψ(r) = R 0 l α (r, r * )p 0 (r * )dr * = α r 0 (r -r * )p 0 (r * )dr * + (1 -α) R r (r * -r)p 0 (r * )dr * .It is twice-differentiable, withψ ′ (r) = α r 0 p 0 (r * )dr * -(1 -α) R r p 0 (r * )dr * = r 0 p 0 (r * )dr * -(1 -α),and ψ ′′ (r) = p 0 (r). The strong convexity statement on ψ is thus clear. If P 0 is uniform, we haveψ(r) = R -1 α r 0 (r -r * )dr * + (1 -α) R r (r * -r)dr * = 1 2R αr 2 + (1 -α)(R -r) 2 = 1 2R r 2 -(1 -α)r + 1 2 (1 -α)R.Next, consider the first part of the theorem. Algorithm 1 outputsEQUATIONOn the other hand, consider the optimization objective in Eq.(4), scaled by (1 -λ t )/(t -1); it can be written asγ(x) := λ t ψ(x) + 1 -λ t t -1 t-1 i=1 l α (x, r * i ).Notice that the function γ is continuous and right-differentiable. Taking its right-derivative, we haveγ ′ + (x) = λ t x 0 p 0 (r * )dr * -(1 -α) + 1 -λ t t -1 (α -1) t-1 i=1 1[x < r * i ] + α t-1 i=1 1[x ≥ r * i ] = λ t x 0 p 0 (r * )dr * + λ t (α -1) + 1 -λ t t -1 (α -1)(t -1) + 1 -λ t t -1 t-1 i=1 1[x ≥ r * i ] = λ t x 0 p 0 (r * )dr * + 1 -λ t t -1 t-1 i=1 1[x ≥ r * i ] + α -1.Comparing it to Eq.( 5), we see that the output r t (α) of Algorithm 1 satisfies r t (α) = min{s; γ ′ + (x) ≥ 0}. Therefore it also satisfies the FTRL update, Eq.(4).Theorem 2. Let P 0 be the uniform distribution on [0, R]. With the step size λ t = 1/ √ t, the output of Algorithm 1 against any r * 1:T sequence satisfiesT t=1 l α (r t (α), r * t ) - T t=1 l α (q 1-α (r * 1:T ), r * t ) = O(R √ T ), ∀α ∈ [0, 1],where q 1-α (r * 1:T ) denotes the (1 -α)-quantile of the hindsight empirical distribution P (r * 1:T ), and O(•) subsumes absolute constants.Proof of Theorem 2. Starting from Eq.(4), we first verify that the regularizer weight λt(t-1) 1-λt is increasing with respect to t (when t > 1), so that the classical FTRL regret bound can be applied. To this end, defineh(t) := λ t (t -1) 1 -λ t = t -1 √ t -1 .Taking the derivative, for all t > 1,h ′ (t) = √ t -1 -t-1 2 √ t ( √ t -1) 2 = t -2 √ t + 1 2 √ t( √ t + 1 -1) 2 = ( √ t -1) 2 2 √ t( √ t + 1 -1) 2 ≥ 0.Now, since the regularizer weight is increasing and the base regularizer ψ corresponding to the uniform prior is R -1 -strongly convex, we can apply the strong-convexity-based FTRL regret bound [Ora23, Corollary 7.9] starting from t = 2 (and implicitly, T ≥ 2). This yieldsT t=2 l α (r t (α), r * t ) - T t=2 l α (q 1-α (r * 1:T ), r * t ) ≤ λ T (T -1) 1 -λ T max r∈[0,R] ψ(r) -min r∈[0,R] ψ(r) + R 2 T t=2 1 -λ t λ t (t -1) g 2 t ,where g t is defined asg t =   α, r t (α) > r * t , 1 -α, r t (α) < r * t , 0, r t (α) = r * t . In all cases we have g 2 t ≤ 1. Furthermore, min r∈[0,R] ψ(r) = 1 2 α(1 -α)R ≥ 0, max r∈[0,R] ψ(r) = R 2 max{α, 1 -α} ≤ R/2. Therefore, plugging in λ t = 1/ √ t we have T t=2 l α (r t (α), r * t ) -T t=2 l α (q 1-α (r * 1:T ),r * t ) ≤ R 2 λ T (T -1) 1 -λ T + T t=2 1 -λ t λ t (t -1) ≤ R 2 4 √ T + T -1 t=1 √ t + 1 t = O(R √ T ).Adding the instantaneous regret from the first round only results in an additional R on the total regret bound.An example is classification, where the score function is usually the softmax score of each candidate label (R = 1). It is positively oriented: larger means the model is more certain that the candidate label is the true one. For regression, it is more common to use negatively oriented score functions, which means the inequality in Eq.(1) is reversed.This extended abstract focuses on marginal CP. More generally, the CP algorithm can predict rt(xt, α). 
 
 Appendix:  



Reviews: review: title: title: Introducing the Bayesian prior in online conformal prediction
main_review: main_review: This paper proposed a method of online constructing the valid confidence sets given a black-box machine learning model. The key idea is to take the iid-based procedure and regularize its algorithmic belief by a Bayesian prior. The algorithm mixes the Bayesian prior with the empirical distribution of the data sequence to predict quantiles. The authors show that this method simulates a non-linear version of the FTRL algorithm, and discuss about the possibility of answering multiple confidence level queries online, and the convergence bound. Overall it is a clean and useful implementation of Bayesian theory relaxing the common i.i.d. assumptions. 

My comments are: 
1. How to choose appropriate priors is an unavoidable topic in such topics; It will be good if there are more discussions about what priors for what scenarios and applications, and their effects on the results. Are the results sensitive to the prior choice?  
2. How to change the step size in the algorithm \lambda? There should be a strategy of quickly adapting it according to the shifts of data distribution. 
3. If there are more applications in real-world datasets it will be better.
title: title: Assessing the Validity and Robustness of Follow the Regularized Leader in Online Conformal Prediction
main_review: main_review: Summary: The paper proposes an algorithm (Follow the Regularized Leader) for online conformal prediction, which does not require the assumption of iid sample and addresses the validity issues from previous proposed baselines. Moreover, the proposed algorithm does not require knowing the quantile beforehand.

Strength: The paper contributes towards designing an improved algorithm that addresses the shortcomings of existing methods, particularly in terms of validity and robustness under adversarial settings.

Weakness: 1. The paper lacks empirical results compared to the various baselines, comparing the proposed algorithm to various baselines, which would help demonstrate its practical advantages. 2. The discussion on adversarial robustness is too brief. It remains unclear to me how the proposed algorithm can be thought of in the context of adversarial online learning and what mechanisms make it robust in such settings. A more detailed exploration would strengthen this aspect of the work.