Conformal Bayesian Computation
Authors: Edwin Fong
Christopher C. Holmes
Venue: NeurIPS 2021 Poster (2021)
Keywords: Conformal prediction
Bayesian Inference
Calibration

Abstract: We develop scalable methods for producing conformal Bayesian predictive intervals with finite sample calibration guarantees. Bayesian posterior predictive distributions, $p(y \mid x)$,  characterize subjective beliefs on outcomes of interest, $y$, conditional on predictors, $x$. Bayesian prediction is well-calibrated when the model is true, but the predictive intervals may exhibit poor empirical coverage when the  model is misspecified, under the so called ${\cal{M}}$-open perspective. In contrast, conformal inference provides finite sample frequentist guarantees on predictive confidence intervals without the requirement of model fidelity. Using 'add-one-in' importance sampling, we show that conformal Bayesian predictive intervals are efficiently obtained from re-weighted posterior samples of model parameters. Our approach contrasts with existing conformal methods that require expensive refitting of models or data-splitting to achieve computational efficiency. We demonstrate the utility on a range of examples including extensions to partially exchangeable settings such as hierarchical models.

Conformal Bayesian Computation
Edwin Fong University of Oxford The Alan Turing Institute fewin.ffng@sstee ox ac.
Chris Holmes
University Oxford
The Alan Turing Institute cholmes@stats. ox ac uk
Abstract
We develop scalable methods for producing conformal Bayesian predictive in- tervals with finite sample calibration guarantees. Bayesian posterior predictive distributions, p(y æ). characterize subjective beliefs on outcomes of interest, y, conditional on predictors, æ. Bayesian prediction well-calibrated when the model is true, but the predictive intervals may exhibit poor empirical coverage when the model is misspecified, under the so called M-oopnn perspective. In contrast, conformal inference provides finite sample frequentist guarantees on predictive confidence intervals without the requirement of model fidelity. Using 'add-one-in' importance sampling, we show that conformal Bayesian predictive intervals are efficiently obtained from re- re-weighted posterior samples of model parameters. Our approach contrasts with existing conformal methods that require expensive refitting of models or data-splitting to achieve computational efficiency. We demonstrate the utility on range of examples including extensions to partially exchangeable settings such as hicrarchical models.
Introduction
We consider Bayesian prediction using training data Zim [Y,, Xihi=i:n for an outcome of interest Y, and covariates X; E Rd Given a model likelihood fo 2) and prior on parameters, (() for
0 e R", the posterior predictive distribution for the response at new X In+1 takes on the form
ply Intt, 71..) = f Foly In-1) ( Z1..) d0,
(1)
where [0 Z1.n) is the Bayesian posterior. Asymptotically exact samples from the posterior can be obtained through Markov chain Monte Carlo (MCMC) and the above density can be computed through Monte Carlo (MC), or by direct sampling from an approximate model. Given a Bayesian predictive distribution, one can then construct the highest density 100 x (1 aa% posterior predictive credible intervals, which are the shortest intervals to contain (1 a) of the predictive probability. Alternatively, the central 100 x (1 a %% credible interval can be computed using the a/2 and 1 - a/2 quantiles. Posterior predictive distributions condition on the observed Z and represent subjective and coherent beliefs. However, it is well known that model misspecification can lead Bayesian intervals to be poorly calibrated in the frequentist sense (Dawid) 1982; Fraser et al.) [001]) that is the long proportion of the observed data lying in the (1 (1-a) a) Bayes predictive interval is not necessarily equal to (1 - a.. This has consequences for the robustness of such approaches and trust in using Bayesian models to aid decisions.
Alternatively, one can seek intervals around point prediction from the model, ğ fi(x), that have the correct frequentist coverage of a:) This is precisely what is offered by the conformal prediction framework Vovk al. (2005), which allows the construction of prediction bands with finite sample validity without assumptions on the generative model beyond exchangeability of the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

data. Formally, for Z, Xi i=n Z, lid IP and miscoverage level a, conformal inference allows us to construct a confidence set C. (Xa+1) from Zi. and Xn+1 such that
P(Yn+1 E (Xn+1)) 2
Note that PP is over Z1:++1, that is we also treat X as random; see Lei and Wasserman (0014) for discussion the difficulties of attaining coverage conditional on X.+1- In this paper we develop computationally efficient conformal inference methods for Bayesian models including extensions to hierarchical settings. A general theme of our work is that, somewhat counter-intuitively, Bayesian models are well suited for the conformal method.
Conformal inference for calibrating Bayesian models was previously suggested in Melluish et al. (200T), Vovk et al.] (2005), Wasserman (201T) and Burnaey and Vovk (2014), where is referred to "de-Bayesing". "frequentizing" and "conformalizing", but only in the context of conjugate models. Here, we present a scalable MC method for conformal Bayes, implementing full conformal Bayesian prediction using an 'add-one-in' importance sampling algorithm. The automated method can construct conformal predictive intervals from any Bayesian model given only samples of model parameter values from the posterior 0 ~ T( :I. ). up to MC error. Such samples are readily available in most Bayesian analyses from probabilistic programming languages such as Stan (Carpenter et al. (017) and PyMC3 (Salvatier al. 2016). We also extend conformal inference to partially exchangeable settings which utilize the important class of Bayesian hierarchical models, and note the connection to Mondrian conformal prediction (Vovk et al. 2005 Chapter 4.5). Previously, the extension of conformal prediction to random effects was introduced in Dunn et al. (220) in a non-Bayesian setting, with focus on prediction new groups, as well as within-group predictions without covariates. We will see that the Bayesian hierarchical model allows for a natural sharing of information between groups for within-group group predictions with covariates. We discuss the motivation behind using the Bayesian posterior predictive density as the conformity measure for both the Bayesian and the frequentist, and demonstrate the benefits in number of examples.
1.1 Background
The conformal inference framework was first introduced by Gammerman et al. (1998), followed by the thorough book of Vovk et al. (2005). Full conformal prediction is computationally expensive, requiring the whole model to be retrained at each test covariate Fn+1 and for each value in a reference grid of potential outcomes, e.g. y IR for regression. This makes the task computationally infeasible beyond few special cases where we can shortcut the evaluation along the outcome reference grid, e.g. ridge regression (Vovk et al. 2005; Burnaev and Vovk. 2014) and Lasso (Lei 2019). Shrinking the search grid is possible, but still requires many refittings of the model (Chen et al. (016)). The split conformal prediction method (Lei et al., 2018) a useful alternative method which only requires a single model fit, but increases variability by dividing the data into a training and test set that includes randomness in the choice the split, and has a tendency for wider intervals. Methods based on cross-validation such cross-conformal prediction (Vovk] 2015) and the jacknife+ (Barber et al.) 202T) lie in between the split and full conformal method in terms of computation and average length of the intervals. A detailed comparison of various conformal methods are provided in Barber et al.
2021 Section 4). A review of recent advances in conformal prediction is given in Zeni ct al. (2020). and interesting extensions have been developed by works such as Tibshirani and Foyge! 2019
Romano et al. 2019): Candès et al. (2021).
2 Conformal Bayes
2.1 Full Conformal Prediction
We begin by summarizing the full conformal prediction algorithm discussed in Vovk et al. (2005); Lei et al. (2018). Firstly, conformity (goodness-of of-fit) measure,
o, := a (Z Z,),
takes as input a set of data points Zi:+1,, and computes how similar the data point Z; is for i 1, 1.....,7 n + A typical conformity measure for regression would be the negative squared error arising from a point prediction {y (x where ((x) is the point predictor fit to the augmented dataset Z1m++1, assumed to be symmetric with respect to the permutation of the input

---

dataset. The key property of any conformity measure is that it is exchangeable in the first argument, Le. the conformity measure for Z, is invariant to the permutation of Z1:++1- Under the assumption that 71 is exchangeable, we then have that 01n++1 is also exchangeable, and its rank is uniform among (1..... n }} (assuming continuous 1mm+1). From this, we have that the rank of d=+1 is a valid p-value. If we now consider a plug-in value Yn+1 (where Xn+1 is known), we can define the rank of xn+1 among 0mm++ as
n+
r(v)
1 S ont1).
n
n1
For miscoverage level a, the full conformal predictive set,
Cx = {y E R r(v) a), satisfies the desired frequentist coverage as in (2) under the exchangeability assumptions above. Intuitively, reporting the values of which conform better than the fraction of observed conformity scores the augmented dataset. A formal proof can be found in Vovk et al. (2005) Chapter 8.7). For continuous 11 also have from Lei et al. (2018) Theorem 1) that the conformal predictive set does not significantly over-cover.
In practice beyond a few exceptions, the function r(y) must be computed on fine grid E Vgrria for example size 100, in which case the model must be retrained 100 times to the augmented dataset to compute iin+1. with plug-in values for 3/++1 the grid. This is illustrated in Algorithm [ below. We note here that the grid method only provides approximate coverage, as y may be selected even it lies between two grid points that are not selected. This is formalized in Chen et al. (2018), but do not discuss this further. In Appendix D.6 we provide an empirical comparison of the grid effects.
This is also valid for binary classification where now have finite Vgna = {0, 1), and so the grid method for full conformal prediction is exact and feasible.
Observed data is Zi.: Xn+1; Specify miscoverage level a for each y E Vgria do Fit model to augmented dataset [Z....., Zno {y, X xn+1]}
Compute iam and 0n+1
Store the rank, r(y), of on+1 among 0l.++1
end
Return the set Ca {y E Vena r(y) a).
Algorithm 1: Full Conformal Prediction
2.2 Conformal Bayes and Add-One-In Importance Sampling
In Bayesian model, natural suggestion for the conformity score, as noted in Vovk et (2005):
Wasserman (201T), is the posterior predictive density (I), that is
1m 1: Z,) = p(Y; X,, Zim-1)
i E (1 .... n + 1), where
p(Y: X,, Z1m+1)= fo(Y; X:) ( Z1:m+1) d0
(4)
We highlight that the datum 2; = X.} also lies in the conditioning Z1m+1- This is a valid conformity score, as we have (0) Z1s41) x x0) II= fo(Y: Xx)), and so a is indeed invariant the permutation of Z1 1- We refer to this method as conformal Bayes (CB) this is a special case of full conformal prediction, and we will see shortly that the exchangeability structure of Bayesian models key to constructing conformity scores in the partial exchangeability scenario.
Beyond conjugate models, we are usually able to obtain (asymptotically exact) posterior samples ((LTT) ~ T00 Zi,),, e.g through MCMC, where T a large integer. Such samples are typically available as standard output from Bayesian model fitting. The posterior predictive can then be computed up to Monte Carlo error through
T Sace (Yn+1 Xn+1).
p(Yn+1 Xx411, Zim) = T
Σ 1=1
3

---

The key insight is that refitting the Bayesian model with (Zi..... Zn. Xx+1] is well approx- imated through importance sampling (IS), as only (y+1, changes between refits. This leads immediately to an IS approach to full conformal Bayes, where we just need to compute 'add-one-in" (AOI) predictive densities. Here AOI refers to the inclusion of (Vn=1,xx+1) } into the training set, named in relation to 'lave-one-out" (LOO) cross-validation. Specifically, for Yn+1 y and g(l:T) ~ T(() Z1 we can compute
T
P | X,, Zim+1)
Σ
Tl fece (Y, X.)
(5)
where wi(t) are our self-normalized importance weights of the form
w
wit
fyce:(y) (x+1),, Te
(6)
Lt'=1
w((")
We that the unnormalized importance weights have the intuitive form of the predictive likelihood at the reference point {v, 1 given the model parameters ((().
The use of AOI importance sampling has similarities to the computation of Bayesian leave-one-out (LOO) predictive densities for cross- validation (Vehtari et al. (2017), which is also used in accounting for model misspeciffiation. An interesting aspect AOI in comparison with LOO that AOI predictive densities are less vulnerable to importance weight instability for the following reasons:
In LOO, the target x Z-:) generally has thicker tails than the proposal =(9 Zim) leading to importance weight instability. In contrast, AOI uses the posterior (0 Zim) as proposal for the thinner-tailed T 11 For LOOO the importance weights are proportional to 1/fo(y æ.), in contrast to the typically bounded fo(y 2)) for AOI.
For AOI, we are predicting Zi given Z which is always in-sample unlike in LOO where the datum is out-of-sample, we can expect greater stability with AOI.
The IS weight stability is governed by Y y. which is not random as we select it for the grid, unlike in LOO pross-validation For sufficiently large a, we will not need to compute the AOI predictive density for extreme values of y.
The above discussion is natural analogy to the discussion provided Vehtari et al. (2017] Sec- tion 2. for computing I.O0 predictives. Note that the LOO predictive density is also a valid conformity score; we provide more details and verify the above comparisons between LOO and AOI empirically in Appendix [B] We also provide some IS weight diagnostics in Section 4.1.1 and find that they are stable. In difficult settings such as very high-dimensions, one can make use of the recommendations of Vehtari et al. (2015) for assessing and Pareto-smoothing the importance weights necessary.
2.3 Computational Complexity
Given the posterior samples, we must compute the likelihood for each f()) at Z well at {y, x for y E Vgrid The additional computation required for CB for each X,+1 thus T x (n + Nggiia) likelihood evaluations, which is relatively cheap. This is then followed by the dot product of an (n + 1) x T matrix with T vector for each y, which OnTT', so the overall complexity is OfigiaTT)) The large matrices involved in computing the AOI predictives suggests we can take advantage of GPU computation, and machine learning packages such as JAX (Bradbury et al. 2018) are highly suitable for this application.
The values Rggid and are constants we select, and we now briefly provide guidance on this. Selecting grid is general problem for full conformal prediction (beyond just CB), and this has been investigated in Chen et al. (2066 2018). Here, we opt for a default choice of Ngrid = 100 in Section and we show in Appendix[D.eg that this is sufficient for accurate coverage. For the selection of T, there are standard methods based on the effective sample size (ESS) which we compute Section 4.1.I One could then approximate the Monte Carlo standard error in the density estimates which is proportional to 1/ VESS, or estimate the IS variance directly. The ESS will depend both on MCMC mixing and IS stability, which may further depend on the dimensionality of the model. More details can be found in Owen 2013 Chapter 9.3)

---

2.4 Motivation
Much has been written on the contrasting foundations and interpretation of Bayes versus frequentist measures of uncertainty (Little, 2006 [Shafer and Vovk 2008 Bernardo and Smith, (2009 Wasserman 2011), and we provide summary in Appendix A both Bayesian and frequentist perspective.
Here we motivate CB predictive intervals from
The pragmatic Bayesian, aware of the potential for model misspecification in either the prior or likelihood, may be interested conformal inference as a countermeasure. CB predictive intervals with guaranteed frequentist coverage can be provided as a supplement to the usual Bayesian predictive intervals. The difference between the Bayesian and conformal interval may also serve as an informal diagnostic for model evaluation (e.g. /eelman et al. (2 Posterior samples through MCMC or direct sampling are typically available, and so CB through automated AOI carries little overhead.
The frequentist may also wish to use Bayesian model as tool for constructing predictive confidence intervals. Firstly, the likelihood can take into account skewness, heteroscedasticity unlike the usual residual conformity score. Secondly, features such sparsity, support, and regularization can be included through priors, while CB ensures correct coverage. Thirdly, CB provides a computationally feasible method compute full conformal prediction intervals for larger class of models. Finally, subtle issue that arises in full conformal prediction is that we lose validity if hyperparameter selection not symmetric with respect Zn+1. e.g. if we estimate the Lasso penalty using only Z1.0. before computing the full conformal intervals with said X 1Z1m). For CB, a prior on hyperparameters induces weighting of the hyperparameter values by implicit valsdvaaio for each refit (Gneiting and Raftery 2007 Fong and Holmes (2020). We highlight here that this issue does not affect the split conformal method, e.g. Lei and Wasserman (2014] Section 5).
3 Partial Exchangeability and Hierarchical Models
A setting of particular interest is for grouped data, which corresponds to a weakening of exchange- ability often referred to as partial exchangeability (Bernardo and Smith 2009. Chapter 4.6). Assume that we observe data from J groups, each of size Ni., where again Zr,j [Y.j. )- We write the full dataset 7 {Z
....., n 1, ,,...,,J We may not expect the entire sequence Z to be exchangeabl,, instead only that data points are exchangeable within groups. Formally, this means that
p(Z ZI.,,.) = p( (m))) (.t.::))).....22.000000 (1)()))((m))))))
for any permutations Y, of I,..., Ny. for j = 1, J. Alternatively, we can enforce the usual definition of exchangeability but only consider permutations of 1, .....,, such that the groupings iid
preserved. A simple example of this partial exchangeability is if Zr,j ~ P3 for = I,..., ng j I,...,J, where P, can now be distinct.
Partial exchangeability is useful multilevel modelling, e.g. where Zi:yy.5 records exam results on students within school j. for schools j 1.... J. Students may be deemed exchangeable within schools, but not between schools. Further examples may be found in Gelman and Hill (2006).
3.1 Group Conformal Prediction
Given a new X1y belonging to group j for j E (1....,J}, we seek to construct (1 - aaz) confidence interval for Y Yny+1.j- We define within-group conformity score as
Jzy = 0= 0z. (Z Zi.))
for i I,...,n, + We write Z-, as the dataset without group j. and Zーح j in the subscript indicates the dependence of the conformity score on this, which motivate in the next subsection. For each Z=y, we require the score to be invariant with respect to the permutation of Z1: For Zn = (v, Xny+l.3). the conformal predictive set then defined
+1+1
()) n2 +1
Σ
1 (ais S Snytt.)), Caz (Xay+1a) = E > a.)
(8)
In other words, we rank the conformity scores 0lmytl. within the group j. and compute the conformal interval as usual with Algorithm|] [
The interval is valid from the following.
5

---

Proposition 1. Assume that fZ, Zn,+1.1 is partially exchangeable as in 77. and the conformity measure og for group j is invariant to the permutation of Z 11..-11.3 We then have
P PYn,ti.5 Caz (xn++1,)) - oj
where Caz (Xatt1.) is defined in 18). and IP is over (Z, 7n,+1,)
Proof. Conditional on Z-j. the observations Z1m,+1,1 are still exchangeable, and thus so are 01: from the invariance of the conformity measure. The usual conformal guarantee then holds:
P PYng+1, E Cas (Xny+1.)) Z-2) 2 a-ja.
Taking the expectation with respect to Z gives us the result.
is interesting to note that the above group conformal predictor coincides with the attribute- conditional Mondrian conformal predictor of Vovk et al. (2005 Chapter 4.5), with the group alloca- tions as the taxonomy. Validity under the relaxed Mondrian-exchangeablle of Vovk et al. (2005) Chapter 8.4) is key for us here.
3.2 Conformal Hierarchical Bayes
Under this setting, a hierarchical Bayesian model can be defined of the form
[Y X fj. iid - (is) i= 1, ......n. 1
[0, Φ) iid T(- Φ) ~ (Q)) T T~ (T))
Here is a common parameter across groups (e.g. common standard deviation for the residuals under homoscedastic errors). The desired partial exchangeability structure is clearly preserved the Bayesian model (Bernardo) 1996). De Finetti representation theorems are also available for partially exchangeable sequences (when defined in a slightly different manner the above), which motivate the specification of hierarchical Bayesian models (Bernardo and Smith 2009 Chapter 4.6).
The posterior predictive is once again natural choice for the conformity measure. Denoting Z, as the entire dataset augmented with Zny +1, = {y, X Xnyt1.h }. we have
/ f0 (Yi. X1.)) T(0j [ Zzy) d0, dr
p(Y., Xi.j 2n)
Oej
for 1,...,, Ny - 1. The within group permutation invariance follows as the likelihood is exchange- able within groups, and thus so is the posterior and resulting posterior predictive. Practically, this structure allows for independent coefficients Aj for each group, but partial pooling through T Φ) allows information to be shared between groups. A fully pooled model, whilst still valid, is usually too simple and predicts poorly, whereas no-pooling conformity score ignores information sharing between groups. More details on hierarchical models can be found in Gelman et al. (2013 Chapter 5). We point out that we can select separate coverage level a; for each group, which will be useful when group sizes ny vary we provide a demonstration of this in Appendix [.4.2] Computation of Jzy is again straightforward, where MCMC now returns (e(T:) ((1:7), (017))>7(17))))) ((:7T] T(81,, 2, We can then estimate (9) using AOI importance sampling as in (5) and (6) using the marginal samples (0 (1:T)) T0,,, Z) and weights ( foge (e (y Xny+1o).
T Ø, Z).
In the above, we consider predictive intervals within groups with covariates, extending the within- group approach Dunn al.) (2020). Predictive intervals for new groups are possible with the Bayesian model, but conformal predictor would require additional stronger assumptions of exchange- ability to ensure validity. The relevant assumptions and methods based on pooling and subsampling for new group predictions are discussed in Dunn et al. 2020), but would require rerunning MCMC in our case. We leave this for future work, noting that utilizing the Bayesian predictive density directly here seems nontrivial due to different group sizes.

---

4 Experiments
We run and time all examples on an Azure NC6 Virtual Machine, which has 6 Intel Xeon E5-2690 v3 vCPUs and a one-half Tesla K80 GPU card. We use PyMC3 (Salvatier et al., 2016) for MCMC and sklearn (Pedregosa et al. 2011) for the regular conformal predictor: both are run on the CPU.
Computation of the CB and Bayes intervals is implemented in JAX (Bradbury et al. 2018). and run
on the GPU. The code is available online and further examples are provided Appendix D
4.1 Sparse Regression
We first demonstrate our method under a sparse linear regression model on the diabetes dataset (Efron ct al. 2004) considered by Lei (201)). The dataset is available in sklearn, and consists of 442 subjects, where the response variable is continuous diabetes progression and the d = 10 covariates consist of patient readings such as blood serum measurements. We standardize all covariates and the response to have mean 0 and standard deviation 1.
The Bayesian model consider is
foly (1) -N 0x 0o. 72) (00) 1, T(b)= Gamma
(10)
= (00,) Laplace b),
x(T)=
for = l,..., d, and where b is the scale parameter and N is the half-normal distribution. Note that hyperprior on b has removed the need for cross-validation that is required for Lasso. We consider two values of с for the hyperprior on т, which correspond to a well-specified (c = 1) and poorly- specified (c 0.02) prior; in the latter case posterior T will be heavily weighted towards small value. This model is well-specified for the diabetes dataset (Jansen 2013 Chapter 4.5) under reasonable prior (c 1). We compute the central (1 a) credible interval from the Bayesian posterior predictive CDF estimated using Monte Carlo and the same grid as for CB.
To check coverage, we repeatedly divide into training and test dataset for 50 repeats, with 30% of the dataset the test split. We evaluate the conformal prediction set on a grid of size Ngrid 100 between [B/min - 2, Mmax + 2). where Ymin, 3max is computed from each training dataset. The average coverage, length and run-times (excluding MCMC) with standard errors are given Table [ for = 0.2. MCMC induced an average overhead of 21.9s for = 1 and 26.8s for 0.02 for the Bayes and CB interval, where we simulate = 8000 posterior samples. The CB intervals are only slightly slower than the Bayes intervals, and still small fraction of the time required for MCMC, and is thus an efficient post-processing step. For c = 1, the Bayesian intervals have coverage close to (1 - a) with the smallest expected length, with CB slightly wider and more conservative. However, when the prior is misspecified with c = 0.02, the Bayes intervals severely undercover, whilst the CB coverage and length remain unchanged from the c 1 case.
As baselines, we compare to the split and full conformal method using the non-Bayesian Lasso as the predictor, with the usual residual as the nonconformity score. For the split method, we fit Lasso with cross-validation on the subset of size Muain/ /2 to obtain the Lasso penalty X. For the full conformal method, we use the grid method for fair timing, as other estimators beyond Lasso would not have the shortcut of Lei (2019). As setting a default = gives poor average lengths, we estimate À = 0.004 on cross- vols-validotion we must emphasize again that this is somewhat misleading, as discussed in Section 2.4 A fairer approach would involve fitting Lasso with CV for each of the 100 grid values and 133 test values, but this is infeasible as each fit requires around 80ms, resulting in a total run-time of 17 minutes. On the other hand, the AOI scheme of CB is equivalent to refitting b for each grid/test value. In terms of performance, the split method has wider intervals than CB/full, but performs well given the low computational costs. The full conformal method performs well as CB, but is comparable in time as MCMC + CB, whilst not refitting A. We note that the value of e does not affect the split/full method.
one of the training sets, and use this value over the 50 repeats. However,
7

---

Table 1: Diabetes: Coverage values nor within 3 standard errors (in brackets) of the target coverage - a) 0.8 are in red. Run-times exclude overhead MCMC times, which are provided the main text.
Bayes
CB
Split
Full (A 0.004)
Coverage
c = 1
0,806 (0.005)
0.808 (0.006)
0.809 (0.006)
0.808 (0.006)
0.02
0.563 (0.006)
0.809 (0.006)
/
Length
= 1
1.84 (0.01)
1.87 (0.01)
1.91 (0.02)
1.86 (0.01)
= 0.02
1.14 (0.00)
1.87 (0.01)
Run-time (secs)
= 1
0,488 (0.107)
0.702 (0.019)
0.065 (0.001)
11.529 (0.232)
0.02
0.373 (0.002)
0.668 (0.003)
4.1.1 Importance Weights
For the diabetes dataset, we look at the ESS of the self-normalized importance weights (6 which can be computed as ESS = 1/ :=1 {w! for each xx+1 and The ESS as a function of for single #n++ shown in Figure [ for the two cases c 1, 0.02, with the CB conformal bands given for a = 0.2, 0.5. We have scaled the ESS plots by ESSMcMe/TT where T 8000 is the number of posterior samples and MSS the minimum ESS out of all posterior parameters return by PyMC3. We observe the ESS is well behaved and stable across the range of values. In both cases, the ESS for a 0.2 sufficiently large for reliable estimate of the conformity scores. However, for c = 0.02, the ESS decays more quickly with as the Bayes predictive intervals are too narrow, which the CB corrects for. Other values of rn+1 produce similar behaviour.
4000
2000
a= 0.5
Effective Sample Size
3000
1500
Effertive Sample
2000
1000
1000
500
-2
y
Figure 1: Effective sample sizes of IS weights with CB conformal bands for diabetes dataset with (left) 1 and (right) c 0.02.
4.2 Sparse Classification
In this section, we analyze the Wisconsin breast cancer (Wolberg and Mangasarian 1990), again available in sklearn. The dataset is of size 569, where the binary response variable corresponds to malignant or benign tumour. The 30 covariates consist of measurements of cell nuclei. Again, we standardize all covariates to have mean 0 and standard deviation 1.
consider the logistic likelihood foly = 1 x) [1 + exp (- +0)++0))]]+ with the same priors for 0, 0g as in (10). The Bayesian predictive set is the smallest set from (0), (1), {0, 1} that contains at least (1 10--2 a) of the posterior predictive probability. The conformal baselines are as above but with T--peenaized logistic regression, and for the full conformal method we have X = 1. We again have 50 repeats with 70-30 train-test split, and set a = 0.2. The grid method now exact, and the size of the CB intervals can take the values {0, 1, 2}. The results are provided in Table 2 where MCMC required an average of 45.4s to produce T 8000 samples. We see that even with reasonable priors, Bayes over-cover substantially, which CB corrects in roughly the same amount of time as it takes to compute the usual Bayes interval. However, we point out that CB may produce empty prediction sets, whereas Bayes cannot, and we investigate this in Appendix D.3.2

---

Table 2: Breast Cancer: Coverage values not within 3 standard errors (in brackets) of the target coverage (1 a) = 0.8 are in red. Run-times exclude overhead MCMC times, which are provided in the main text. "Size" denotes the average number of elements in the conformal prediction set, averaged over the test points and repetitions.
Bayes
CB
Split
Full
Coverage
0.990 (0.001)
0.812 (0.005)
0.809 (0.006)
0.811 (0.005)
Size
1.06 (0.00)
0.81 (0.00)
0.81 (0.01)
0.81 (0.00)
Run-time (secs)
0.364 (0.007)
0.665 (0.012)
0.079 (0.002)
1.008 (0.016)
4.3
Hierarchical Model
We now demonstrate Bayesian conformal inference using a hierarchical Bayesian model for multilevel
data. We stick to the varying intercept and varying slope model (Gelman al. 2013). that is for
j l:
fa, (Mna) = -Niss 10,X,, + 00J,
(11)
=(0,) - (o,, T0o,,) = Noo.. 2g)
with hyperpriors (0, 1) on the location parameters o, @ and Exp(1) 1) on the standard deviations 8. Sp. T. We now apply this simulated example, and an application to the radon dataset Gelman and Hill (0066) is given in Appendix D.4.2
We consider simulation scenarios, with J groups and nj 10 elements per group:
1. Well-specified: We generate group slopes 0j N(O, 1) for .,...,, J. For each j. generate X1, ~ ((( 1) and Yı ~ N (0, X. 1).
2. Misspecified: We generate group slopes and variances 0z NOO, j J. For each we generate Xi, ~O 1) and Yi N (0)
Exp(1) for
The first scenario has homoscedastic noise between groups as assumed in the model [I]) whereas the second scenario is heteroscedastic between groups. To evaluate coverage, only draw 01.1, T1. once (and not per repeat), giving us the values
01:1 [1.33, 0.77, 0.32, 0.99, -1.0], TI. = [1.24, 0.76, 0.28, 1.11).
For each of the 50 repeats, we draw nj = 10 training and test data points from each group using the above f1:7 (and Tı.J for scenario 2), and report test coverage and lengths within each group. We use grid of size 100 between [-10, 10). The group-wise average lengths and coverage given in Table 3 again with a = 0.2. Again run-times are given Post-MCMC, where MCMC required an average of 90.1s and 78.4s for scenarios 1 and respectively to generate T 8000 samples. The Bayes interval is again the central (1 1--- a) credible interval. The CB and Bayes methods have comparable run-times, likely due to the small As reference, fitting a linear mixed-effects model in statsmodels (Seabold and Perktold (2100) to the dataset takes around 200ms, so the full conformal method, which requires refitting for each of the 100 grid value and 50 test values, would take total of 17 minutes. For scenario 1, both Bayes and CB provide close to (1 ax) coverage, with the Bayes lengths being smaller. This is unsurprising, the Bayesian model is well-specified. In scenario the Bayes intervals noticeably over/under-covee depending on the value of Tı. in relation to the Bayes posterior mean 1.3. CB is robust to this, adapting interval lengths accordingly (in particular for Groups 2 and 4) and providing within-group validity.

---

Table 3: Simulated grouped dataset; Coverage values not within 3 standard errors (in brackets) of the target coverage (1 ax) = 0.8 are in red. Run-times exclude overhead MCMC times, which are provided in the main text.
Scenario
Scenario 2
Group
Bayes
CB
Bayes
CB
Coverage
0.808 (0.020)
0.794 (0.022)
0.826 (0.020)
0.786 (0.025)
2
0,800 (0.019)
0.812 (0.024)
0.522 (0.027)
0.812 (0.024)
0.824 (0.017)
0.824 (0.022)
0.974 (0.008)
0.824 (0.020)
4
0.786 (0.017)
0.798 (0.022)
1.000 (0.000)
0.836 (0.021)
0.772 (0.019)
0.810 (0.020)
0.826 (0.022)
0.796 (0.022)
Overall
0.798 (0.009)
0.808 (0.009)
0.830 (0.010)
0.811 (0.009)
Length
2.80 (0.05)
3.19 (0.13)
3.65 (0.08)
4.01 (0.17)
2.76 (0.05)
3,21 (0.15)
3..1
7.27 (0.33)
3
2.75 (0.04)
3.07 (0.13)
(0.08)
2.28 (0.09)
4
2.75 (0.05)
3.05 (0.12)
3.57 (0.08)
1.23 (0.04)
5
2.78 (0.05)
3.14 (0.11)
3.61 (0.08)
3.47 (0.12)
Overall
2.77 (0.04)
3.13 (0.06)
3.61(0.08)
3.65 (0.09)
Run-time (secs) Overall
0.222 (0.002)
0.381 (0.009)
0,221 (0.002)
0.375 (0.002)
5
Discussion
In this work, we have introduced the AOI importance sampling scheme for conformal Bayesian computation, which allow us to construct frequentist-valid predictive intervals from a baseline Bayesian model using the output of an MCMC sampler. This extends naturally to the partially exchangeable setting and hierarchical Bayesian models.
Under model misspecification, or the M-open scenario (Bernardo and Smith 2009 CB can produce calibrated intervals from the Bayesian model. In the partially exchangeable case, CB can remain valid within groups. We find that even under reasonable priors, Bayesian predictives can over-cover, and CB can help reduce the length of intervals get closer nominal coverage. Diagnosing Bayesian miscalibration is in general non-trivial, but CB intervals may provide a diagnostic tool while also automatically correcting the miscalibration. When posterior samples of model parameters are available, AOI importance sampling is only minor increase in computation, and interestingly much faster than the split method (with the Bayesian model) which would require another run of MCMC. For the frequentist, CB intervals enjoy the tightness of the full conformal method, for single expensive fit with MCMC followed by cheap refitting process. We are also free to incorporate prior information, and use more complex likelihoods or priors, as well as automatically fitting hyperparameters.
There are however limitations to our approach, dictated by the realities of MCMC and IS. Firstly, the intervals are only approximate up MC error, although we expect some robustness as the CB intervals are computed from the ranks and not the exact values. The stability of AOI importance sampling also depends on the posterior predictive being good proposal, which may break down if the addition of the new datum {,. X } has very high effect on the posterior. Finally, if our Bayesian model is grossly misspecified and the predictive densities are too narrow, the IS weights may have low ESS and the AOI estimates may have high variance.
If only approximate posterior samples are available, e.g. through variational Bayes (VB), then AOI scheme may still be feasible, where one includes an additional correction term in the IS weights for the VB approximation, e.g. Maggusson the IS weight stability is strongly reliant on the quality of the approximate posterior. Combining this with the Pareto-smoothed IS method of vehtari al. (2015) may lead to feasible solution. In our experience, CB intervals tend to be a single connected interval, which may allow for computational shortcuts in adapting the search grid. would also be interesting pursue the theoretical connections between the Bayesian and CB intervals, in similar light to Burnaev and Vovk (2014).
al. (2019). However, this remains to be investigated, as
10

---

Acknowledgements
We thank the anonymous reviewers for their feedback on our paper. Fong is funded by The Alan Turing Institute Doctoral Studentship, under the EPSRC grant EP/N510129/1. Holmes is supported by The Alan Turing Institute, the Health Data Research, U.K., the Li Ka Shing Foundation, the Medical Research Council, and the U.K. Engineering and Physical Sciences Research Council through the Heyes4Health programme grant EP/R011561/1.
References
Barber, R. F., Candes, J., Ramdas, A., Tibshirani, R. J., et al. (2021), Predictive inference with the jackknife+. Annals of Statistics, 49(1))486-55)
Bernardo, J. M. (1996). The concept of exchangeability and its applications. Far East Journal of Mathematical Sciences, 4: 4:111-122.
Bernardo, J. M. and Smith, A. F. (2009). Bayesian theory, volume 405. John Wiley & Sons.
Bradbury, J., Frostig. R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., and Wanderman- Milne, S. (2018). JAX: composable transformations of Python+NumPy programs.
Burnaev, E. and Vovk, V. (2014). Efficiency of conformalized ridge regression. In Conference Learning Theory, pages 605-622.
Candès, E. J., Lei, L., and Ren, Z. (2021). Conformalized survival analysis. arXiv preprint 0977:3
Carpenter, B., Gelman, A., Hoffman, M. D., Lee, D., Goodrich, B., Betancourt, M., Brubaker, M. A., Guo, J., Li, P., and Riddell, A. (2017). Stan: probabilistic programming language. Grantee Submission, 76(1):1-32.
Chen, W. Chun, K.-J,, and Barber, R. F. (2018). Discretized conformal prediction for efficient distribution-fre free inference. Stat, 7(1):e173.
Chen, W., Wang, Z., Ha, W., and Barber, R. F. (2016). Trimmed conformal prediction for high- dimensional models. arXiv preprint arXiv: 161.:93111
Dawid, A. (1982). The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):605-611
Dunn, R., Wasserman, L., and Ramdas, A. (2020). Distribution-free prediction sets with random effects. arXiv preprint /8Xvv2/80900744122
Efron, B., Hastie, T., Johnstone, L. Tibshirani. R., et al. (2004). Least angle regression. Annals of statistics, 32(2):407-499.
Fong. and Holmes, C. (2020). On the marginal likelihood and cross-validation. Biometrika, 107(2):489-496.
Fraser, D. al. (2011). Bayes posterior just quick and dirty confidence? Statistical Science, 26(3):299-316.
Gammerman, A., Vovk, V., and Vapnik, V. (1998). Learning by transduction. In Proceedings the Fourteenth conference on Uncertainty in artificial intelligence, pages 148-155.
Gelman, A., Carlin, J. B., Stemn, H. S., Dunson, D. B., Vehtari, A., and Rubin, D. B. (2013). Bayesian data analysis. CRC press.
Gelman, A. and Hill, J. (2006). Data analysis using regression and mulrilevel/hierarchhcca models. Cambridge university press.
Gneiting, T. and Raftery, A. (2007). Strietly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477)3599-78.

---

Jansen, L. (2013), Robust Bayesian inference under model misspecification. PhD thesis, Master's thesis, Leiden University.
Lei, J. (2019), Fast exact conformalization of the lasso using piecewise linear homotopy. Biometrika, 106(4):749-764.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. (2018). Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113952)):1094- 1111.
Lei, J. and Wasserman, L. (2014). Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series B: Statistical Methodology, pages 71-96.
Little, R. J. (2006). Calibrated Bayes: Bayes/frequentist roadmap. The American Statistician, 60(3):21--233.
Magnusson, M., Andersen, M., Jonasson, and Vehtari, A. (2019). Bayesian leave-one-out cross- validation for large data. In International Conference Machine Leurning, pages 4244-4253.
PMLR.
Melluish, T., Saunders, C., Nouretdiioov, I., and Vovk, (2001). Comparing the Bayes and typicalness frameworks. In European Conference on Machine Learning, pages 360-371. Springer.
Owen, A. B. (2013). Monte carlo theory, methods and examples.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M.,
Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-leam: Machine learning Python. Journal of Machine Learning Research, 12:2825-2830.
Romano, Y., Patterson, E., and Candès, E. J. (2019). Conformalized quantile regression. arXiv preprint 1905.0995..22
Salvatier, J., Wiecki, T. V., and Fonnesbeck, C. (2016). Probabilistic programming in Python using PyMC3. PeerJ Computer Science, 2:e55.
Seabold, S. and Perktold, J. (2010). Statsmodels: Econometric and statistical modeling with python. In Proceedings of the 9th Python in Science Conference, volume 57, page 61. Austin, TX.
Shafer, G. and Vovk, V. (2008). A tutorial on conformal prediction. Journal of Machine Learning Research, 9(Mar):371-421.
Tibshirani, R. and Foygel, R. (2019). Conformal prediction under covariate shift. Advances in neural information processing systems.
Vehtari, A., Gelman, A., and Gabry, J. (2017). Practical Bayesian model evaluation using leave-one- out cross-validation and WAIC. Statistics and computing, 27(5):1413-1433
Vehtari, A., Simpson, D., Gelman, A., Yao, Y., and Gabry, (2015). Pareto smoothed importance sampling, arXiv preprint arXiv:1507.026466
Vovk, V. (2015). Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence. 74(1):9-28.
Vovk, V., Gammerman, A., and Shafer, G. (2005). Algorithmic learning in a random world. Springer Science & Business Media.
Wasserman, L. (2011). Frasian inference. Statistical Science, pages 322-325.
Wolberg, W. H. and Mangasarian, O. L. (1990). Multisurface method of pattern separation for medical diagnosis applied to breast cytology. Proceedings of the national academy of sciences, 87(23):9193 9196.
Zeni, G., Fontana, M., and Vantini, (2020). Conformal prediction: unified review of theory and new challenges. arXiv preprint 2701::2005.07972.
12


Reviews:
[{"review_id": "xaNH3ET0R1S", "reviewer": "Reviewer_mkBe", "summary": "This paper proposes a scalable method for conformal Bayesian prediction, by estimating the modified posterior predictive density using \"add-one-in\" importance sampling.  On several tabular datasets with sparse and hierarchical models, estimation is shown to be efficient for non-extreme miscoverage levels, and the produced credible intervals have good coverage.\n\n**Post-rebuttal update:** Thank you for the response.  I am keeping my score unchanged: on the plus side, the method is sensible and easy to implement; on the other hand, there are some (understandable) limitations when scaling to large datasets or applied on approximate posterior samples; and some reviewers raised questions about novelty, which I'm not most suited to judge, as I'm not an expert in this field.  In aggregate, the rating of \"marginally above the acceptance threshold\" still describes my opinions well.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe proposed method assumes that a large number of samples from the (original) posterior can be produced efficiently, after which prediction on a single test input can be carried out in O(N_{samples} * N_{train} * N_{grid}) time.  While there is no guarantee on the number of posterior samples needed, diagnostics is possible by looking at the effective sample size.  As the method is easy to implement and diagnostics is always possible, it can be a sensible choice as a \"first attempt\" at moderately-sized problems, especially when Bayesian modeling is also being considered.\n\nStill, the time complexity above can still be expensive for large-scale datasets.  Also the efficiency of the importance sampling procedure is not fully clear, even though the authors provided some informal discussion: as reported in the first experiment, importance sampling is more difficult when the desired miscoverage level is more extreme, or when the prior is misspecified; the latter setting can be relevant in practical applications.  It is also unclear how the sample size requirement changes as the model becomes more complex.\n\nThe experiments demonstrate consistent improvement over standard Bayesian modeling, but it is not fully clear if the method outperforms other scalable conformal prediction methods based on alternative scores: for example, in the first two experiments, the split conformal method has comparable or only slightly worse (CI 5% wider) performance than the proposed method, while being significantly cheaper computationally.  It will strengthen the paper if the authors provide more comparison between these two methods, by e.g., evaluating the split method on a grouped dataset.\n\nThe paper is well written, I didn't find any unsubstantiated claims, and it seems that relevant prior work has been discussed; although I'm not an expert in this field, so I'm not fully confident.\n\nMinor: L123: thinner -> thicker\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The methodological limitations (requiring the original posterior to be a good IS proposal) is discussed in the paper.\n\nAs mentioned above, the work will be strengthened if there are more empirical comparisons of scalable conformal prediction methods using alternative scores.\n\nPotential societal impacts are adequately discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "aBEBPjadfOI", "reviewer": "Reviewer_tEpY", "summary": "This paper introduces Bayesian and importance sampling techniques into a previously known conformal prediction framework.\n\nI had troubles identifying what exactly is the novel contribution of this paper. It could use a brief section stating \"our own contributions are A, B , C\". In my understanding the conformal prediction framework was known before and the novel items are using the Bayesian posterior predictive density as a conformity score and additionally estimating the predictive distribution given new data from a weighted importance sampling where the weights are just the likelihoods of the prameter draws based on the new data point.\n\nThere are modelling extensions from completely exchangeable models to partial exchangeability, i.e., where we have groups and complete exchangeability is still valid in the groups, but not outside the groups. From this flat hierarchical structure there is a further extension to hierarchical models that may model deeper hierarchies and via hyperpriors may share information between groups.\n\n", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper describes fairly straightforward ideas and there is not much surprising or interesting work here. I might be misunderstanding or missing some points, but the main questions that arise are not even attempted to be answered.\n\nFor instance the discretization into a discrete finite grid: What is its size, or more specifically, what is the trade-off between its size and the accuracy of approximation. The same question arises for me when I think of the parameter T for approximating an integral by an empirical average. how large should I choose T such that the error is within an eps error or within a multiplicative (1+-eps) error? Shouldn't the sample size be highly dependent on the dimension d of the parameters? I mean like a large polynomial in d or even 2^d.\n\nThe answer given by the paper is that those values are constants so it's easy for me to say that the paper introduces arbitrarily complicated models and their algorithm is only a heuristic without any guarantees. I think the modeling efforts are nice but too straightforward for a top conference like this. The only theoretical claim/proof is also more like an observation.\n\nIn the experimental part the distributions are concretized with quite simple distributions. Would it be possible to quantify the computational efforts here in those special cases?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "_3U37vs8xfz", "reviewer": "Reviewer_dTHk", "summary": " The authors develop a fast conformal Bayesian computation approach.  The original conformal prediction method can be computationally intensive:  It often requires refitting the model for every augmented value y. The authors avoid this refitting step by using importance sampling. The authors also show the extension to conditionally exchangeable data, which is especially useful for hierarchical data. The resulted conformal interval has finite sample correct coverage and is immune to model misspecification or distribution assumptions.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well structured and easy to follow. I also agree with the authors that prediction calibration is crucial in the M-open world, which is arguable always the case. The prospered conformal Bayesian computation method sheds some light on this direction. \n\nHowever, I am concerned about whether the novelty of the proposed method can be distinguishable from its existing building blocks. Conformal inference/distribution-free Predictive Inference—and thereby the main algorithm considered in this paper—are not new ideas. It is also not a new idea to use (regularized) importance sampling to avoid model refitting and obtain posterior integrals in the context of either the leave-data-out (LOO) or the add-one-data-in (AOI, e.g. Bürkner et al. 2020 used this importance-sampling-AOI idea in time series).  It appears the only methodology contribution this paper is making is to apply the importance sampling strategy to the model refitting step in conformal Bayesian inference. I am not convinced that such incremental contribution would grant a publication. \n\nIn terms of its practical usefulness, I have two concerns. First, throughout the paper, the authors seem to emphasize the situation in which x_{n+1} is fixed. But this is not a typical perdition task in which we have a known x_{n+1}. In the words of Lei  (2018): “In some applications, where Xn+1 is not necessarily observed, prediction intervals are build by evaluating 1{y ∈ Cconf (x)} over all pairs of (x,y) on a fine grid“. Perhaps x_{n+1} can also be evaluated on a grid, but then that method is rather related to jackknife-conformal-inference, which itself can be computed by importance sampling.  \n\nSecond, the “correct frequentist coverage” is a probabilistic statement averaged over all observed data and x_{n+1}. This does not mean the interval estimate derived from conformal Bayes is exact for y_{n+1} conditional on a fixed x_{n+1}, nor necessarily optimal for interval predictions (optimal in the sense of interval scoring rules). Think about the Jackknife case in which the bandwidth is a constant across x_i. I suggest the author clearly state the definition of frequentist coverage as not all audience in the machine learning community can immediately tell the subtle difference.\n\nMinor:\n* L-82: why is the rank normalized by n+1? I think the rank statistic should the integer. \n\n* How is the grid of y chosen? Could you use Bayes prediction to design the grid?\n\n* What is the advantage of AOI against jackknife used in conformal Bayes? Is the only difference that IS-AOI is computationally easier than IS-LOO?\n\n* “The CB and Bayes methods have comparable run-times” I think it is misleading. CB can have an arbitrarily larger running time if x_{n+1} is evaluated at many values.\n\n* Overall, the experiment section is relatively weak. The sample sizes in all three examples are too small to reflect a modern big data challenge. It is not common to see all MCMC running time < 1 second from ML conferences.\n\n* L-336: I think “leverage” is the wrong concept here. The leverage only depends on x. Here you have the influence of y too.\n\n* \"If only approximate posterior samples are available, e.g. through variational Bayes (VB), then an AOI scheme may still be feasible, where one includes an additional correction term in the IS weights for the VB approximation\". I disagree. Note that Magnusson et al. (2019) are on the LOO of exact Bayes when there are only VB samples. In your context, you need not only adjust for the VB approximation for sigma_{n+1}, but also all sigma_{1}, ... sigma_{n} for lack of exact posteriors. Such a task is generally not feasible.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The  authors have adequately addressed potential negative societal impact of their work.\nI have listed more limitations in my main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "OsNHr_4zj7j", "reviewer": "Reviewer_ijh8", "summary": "The authors present an approach to using a Bayesian model to provide predictive intervals with  frequentist coverage within the framework of conformal prediction.  This work generalizes existing Bayesian methods for conformal inference that apply only to conjugate models.  The authors provide a straightforward generalization of their approach to partially exchangeable data.  Empirical validation on several datasets, and comparison to a baseline approach is provided.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The approach to extending conformal intervals beyond conjugate models is a sensible, simple and novel contribution.  The overall exposition and description of the method are very clear.   The work appears potentially significant and may be impactful within the Bayesian community by virtue of its simplicity and clear exposition.\n\nHowever the benefits of the conformal Bayes in comparison to the broader space of non-Bayesian methods for conformal inference and methods for constructing prediction intervals beyond conformal prediction are not clear; it is not clear what (if anything) the authors provide which is not provided by Barber et al. (2021), for example.  A more detailed comparison to existing conformal prediction methods (both in pros and in experimental validation) is needed.\n\nAdditionally, the use of the “add one in” (AOI) posterior predictive density as the conformity score was surprising to me.  Can the authors clarify when this will and will not work usefully as a conformity score?\n\nAssuming I understand the set-up correctly, the score will break down, for example, when predicting with a noiseless Gaussian process regression:\ntheta ~ GP(0, k)\nX_i   \\overset{i.i.d.}{\\sim} N(0,1)\nY_i = theta(X_i)\nIn this case, the density in the first display equation of section 2.2 does not exist (i.e. you cannot define it w.r.t Lebesgue) because for any i satisfying 1<i <= n+1, theta(X_i) | X_i,  Z_{1:n+1} is no longer random once we condition on Z_{1:n+1}.\n\nIn any case, the authors would strengthen the paper by clarifying what is meant by the first display equation of section 2.2; if since (X_i, Y_i) is an element of Z_{1:N+1} (following lines 75-76 of the paper), how should p(Y_i | X_i, Z_{1:N+1}) be interpreted?\n\n\n\nRelatedly, the preference for AOI predictive densities rather than leave one out densities was surprising to me.  And the discussion of this choice on lines 123-131 appeared to me as a bit of a red herring; the three bulleted claims are neither obvious nor supported with evidence or references.  Could the authors comment on whether these observations are part of their contribution, or if these differences to LOO are already known?  In any case, I would have appreciated an empirical comparison to LOO predictive densities used to define the conformity score (again using IS).\n\nIt would greatly strengthen the paper to include (as a theorem) explicit conditions under which the CB intervals have the correct coverage.  Such a statement would help the practitioner/reader understand when the method should be applied.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "FsA-G4BCDQ-", "reviewer": "Reviewer_Ph2T", "summary": "This article proposes a novel approach to constructing prediction intervals with approximately correct frequentist coverage, even on misspecified models.  The basic idea is to employ the conformal prediction technique using the Bayesian posterior predictive density as the conformity (goodness-of-fit) measure.  The main innovation of the article is to use an importance sampling approximation to the posterior predictive density at candidate values of outcome $y$.  This leads to a computationally fast and generally applicable algorithm for using samples from the standard Bayesian posterior to construct well-calibrated prediction intervals, even under misspecification of the Bayesian model.  An extension to hierachical models is also provided, and empirical results are presented demonstrating the performance of the method.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an elegant idea.  The innovation of using importance sampling is pretty simple, but it works out really nicely and I find it quite compelling.  The paper is clear and well-written.  I especially appreciate the clear and concise explanation of the full conformal prediction technique in Section 2.1.  In terms of significance, I could see this becoming a standard part of predictive analysis when using Bayesian models -- it is both powerful and seems easy to implement.\n\nCOMMENTS\n1. How should one choose $T$ (the number of importance samples)?  How should one choose $\\mathcal{Y}_\\mathrm{grid}$ (the grid of $y$ points)?  The choices of $T$ and $\\mathcal{Y}_\\mathrm{grid}$ used in the examples are made without much explanation.  More guidance would be helpful here.\n2. On lines 333-337, the paper mentions that conformal Bayes is limited by Monte Carlo error and the quality of the posterior predictive as a proposal distribution.  Does the severity of misspecification affect coverage?  Are there other factors that affect the coverage performance?\n3. What role does the choice of model have on the quality of the prediction intervals obtained using conformal Bayes?\n4. Does conformal Bayes provide a mechanism for diagnosing misspecification?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article presents a novel method for constructing prediction intervals with correct frequentist coverage, based on combining frequentist ideas from conformal prediction with a Bayesian model.  The main idea is to use the Bayesian posterior predictive density as the conformity measure in the standard conformal prediction framework, and employ importance sampling to avoid having to re-fit the model for every data point.  The method uses "add-one-in" importance sampling rather than leave-one-out, which is advantageous in that it lowers the variance of the importance weights, leading to more stable results.  The computational cost is also significantly reduced by approximating the outcome space with a discrete grid of points, following Chen *et al* (2018).

The idea is relatively simple but very generally applicable, and has the potential to be high impact in the Bayesian community.  The simplicity with which it can be implemented is attractive, and the computational cost is modest: it takes less than 2x the time as the standard Bayesian technique (Tables 1-3). Further, the performance guarantees are quite general, and the experiments demonstrate a striking improvement in coverage performance compared to standard Bayes (Tables 1-3). The paper is well-written and sound.

In my view, the main limitations are:

1) Novelty. The method combines standard techniques for conformal prediction, importance sampling, and Bayesian inference.  Thus, the constituent parts are not novel, and they are integrated in a fairly straightforward way.  The novelty lies in bringing these pieces together and recognizing its utility.

2) Need to appropriately choose the grid of $y$ points, $\mathcal{Y}_\mathrm{grid}$.  The paper provides a reasonable default recommendation for this, which is to use 100 evenly spaced points between $y_\mathrm{min}-2$ and $y_\mathrm{max}+2$.  However, it seems that this choice may require application-specific tuning.

3) Model misspecification may increase the variance of the importance sampling approximation, resulting in more unstable inferences.

There was a fairly wide range in the reviewers scores.  There were two ratings of 4 from reviewers tEpY (with a low confidence of 2) and dTHk (with a medium confidence of 4).  I have carefully examined the paper, the reviews, and the authors' reply, and I believe the main criticisms can be addressed as follows:

- Regarding novelty, reviewers tEpY and dTHk criticize the article for providing incremental improvement upon existing approaches.  While it is true that the method can be viewed as combining existing methods, I would argue that the utility of the proposed method —  in comparison with existing alternatives — justifies its simplicity.  Reviewer dTHk also states that Bürkner *et al* (2020) already introduced the idea of using add-one-in importance sampling for approximating posterior integrals; however, I have examined the Bürkner *et al* (2020) paper and while they use importance sampling, I do not see any use of a technique resembling the method in the present paper.

- Regarding the choice of $\mathcal{Y}_\mathrm{grid}$:  Reviewer tEpY criticizes the article for outsourcing the problem of choosing the grid, and the associated tradeoff between computational cost and accuracy, to Chen *et al* (2018).  Since the use of a discrete grid for conformal prediction is not the main novel contribution of the paper, this outsourcing seems reasonable in my opinion.

- Reviewer dTHk is concerned that the assumption of a known $x_{n+1}$ may not be practical, and discusses making predictions for a grid of $x_{n+1}$ points.  However, as the authors state in their reply, the coverage guarantees are for random $X_{n+1}$, not a given fixed $x_{n+1}$. Thus, in fact, the method effectively considers all possible $x_{n+1}$ values.

- Additionally, reviewer dTHk felt that the article should emphasize more clearly that the coverage guarantees hold in expectation, when averaging over the entire dataset as well as the future datapoint $x_{n+1}$.  This is a good suggestion, which is easily addressed via a minor edit, which the authors have volunteered to do in their reply.


Bürkner, P. C., Gabry, J., & Vehtari, A. (2020). *Approximate leave-future-out cross-validation for Bayesian time series models.* Journal of Statistical Computation and Simulation, 90(14), 2499-2523.

Chen, W., Chun, K.-J., and Barber, R. F. (2018). *Discretized conformal prediction for efficient distribution-free inference.* Stat, 7(1):e173.


Decision: Accept (Poster)