PAC-Bayes Generalization Certificates for Learned Inductive Conformal Prediction
Authors: Apoorva Sharma
Sushant Veer
Asher Hancock
Heng Yang
Marco Pavone
Anirudha Majumdar
Venue: NeurIPS 2023 poster (2023)
Keywords: Conformal Prediction
PAC Bayes
Generalization Theory
TL;DR: We derive PAC-Bayes generalization bounds for learned inductive conformal prediction and show how these bounds can be used to yield efficient and valid prediction sets.

Abstract: Inductive Conformal Prediction (ICP) provides a practical and effective approach for equipping deep learning models with uncertainty estimates in the form of set-valued predictions which are guaranteed to contain the ground truth with high probability.
Despite the appeal of this coverage guarantee, these sets may not be efficient: the size and contents of the prediction sets are not directly controlled, and instead depend on the underlying model and choice of score function.
To remedy this, recent work has proposed learning model and score function parameters using data to directly optimize the efficiency of the ICP prediction sets.
While appealing, the generalization theory for such an approach is lacking: direct optimization of empirical efficiency may yield prediction sets that are either no longer efficient on test data, or no longer obtain the required coverage on test data.
In this work, we use PAC-Bayes theory to obtain generalization bounds on both the coverage and the efficiency of set-valued predictors which can be directly optimized to maximize efficiency while satisfying a desired test coverage.
In contrast to prior work, our framework allows us to utilize the entire calibration dataset to learn the parameters of the model and score function, instead of requiring a separate hold-out set for obtaining test-time coverage guarantees.
We leverage these theoretical results to provide a practical algorithm for using calibration data to simultaneously fine-tune the parameters of a model and score function while guaranteeing test-time coverage and efficiency of the resulting prediction sets.
We evaluate the approach on regression and classification tasks, and outperform baselines calibrated using a Hoeffding bound-based PAC guarantee on ICP, especially in the low-data regime.

PAC- Generalization Certificates for Learned Inductive Conformal Prediction
Apoorva Sharma NVIDIA Research apoorvas@nvidia.cmm com
Sushant Veer NVIDIA Research
Asher Hancock Princeton University
sveerrnvidia.com com
ab4775@princeton.. edu
Heng Yang Harvard University
Marco Pavone Stanford University
Anirudha Majumdar Princeton University ani maajmddar@princeeeeoo
NVIDIA Research
NVIDIA Research
hengy@nvidia.cmm com
mpavone@nvidia.com com
Abstract
Inductive Conformal Prediction (ICP) provides a practical and effective approach for equipping deep learning models with uncertainty estimates in the form of set-valued predictions which are guaranteed to contain the ground truth with high probability. Despite the appeal of this coverage guarantee, these sets may not be efficient: the size and contents of the prediction sets are not directly controlled, and instead depend on the underlying model and choice of score function. To remedy this, recent work has proposed learning model and score function parameters using data directly optimize the efficiency of the ICP prediction sets. While appealing, the generalization theory for such an approach is lacking: direct optimization of empirical efficiency may yield prediction sets that are either no longer efficient on test data, or no longer obtain the required coverage on test data. In this work, we use PAC- PAC-Bayes theory obtain generalization bounds on both the coverage and the efficiency of set-valued predictors which can be directly optimized to maximize efficiency while satisfying a desired test coverage. In contrast to prior work, our framework allows us to utilize the entire calibration dataset to learn the parameters the model and score function, instead requiring a separate hold-out set for obtaining test-time coverage guarantees. We leverage these theoretical results to provide a practical algorithm for using calibration data to simultaneously fine- tune the parameters of model and score function while guaranteeing test-time coverage and efficiency the resulting prediction sets. We evaluate the approach regression and classification tasks, and outperform baselines calibrated using Hoeffding bound-based PAC guarantee on ICP, especially the low-data regime.
Introduction
Machine learning (ML) models have rapidly proliferated across numerous applications, including safety-critical ones such as autonomous vehicles (Schwarting et al., 2018, Waymo, 2021], medical diagnosis [Ahsan al., 2022], and drug discovery [Vamathevan al., 2019]. Due to the severity of outcomes in these applications, decision making cannot solely hinge on "point" predictions from the ML model, but must also encapsulate measure of the uncertainty in the predictions. As a result, accurate uncertainty estimation is cornerstone of robust and trustworthy ML systems; however, or overly- weely-conservative estimates limit their usefulness. this paper, we will present method that builds upon inductive conformal prediction (ICP) (ovkk et al., 2005] and probably approximately correct (PAC) Bayes theory [McAllester, 1998] furnish uncertainty estimates that provably control the uncertainty estimate's conservatism while achieving desired correctness rates.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Calibration Data
Test Data
Legend:
Standard ICP
compute
affilency
Used coveraga
Learned ICS Raco
fine-tume aczone lanciins
re-computa threshokd
aatrantedd coverage
PAC-Baysa
prior
Directly optimized time officlency
Figure I: Standard ICP uses calibration dataset to guarantee coverage on exchangeable test data, but the efficiency of the resulting prediction sets is not directly optimized. Using the same data to select score function and model parameters as well as to perform ICP no longer provides guarantees on test- time coverage and efficiency. Therefore, prior work on optimal ICP has typically relied on holding out some calibration data for post-optimization recalibration step to retain coverage guarantees. In this work, we leverage PAC- -Byes theory to optimize efficiency and provide generalization guarantees using the same dataset. Practically, data-dependent prior, and use the rest to further optimize and obtain generalization guarantees yields the best performance.
demonstrate that a hybrid approach using some data to tune
ICP has emerged as practical approach for equipping deep learned models with uncertainty estimates in the form of set-valued predictions with probaabbbbyllty coverage guarantees, i.c., with high probability, at test time, the ground truth labels will lie within the predicted set. However, post-hoc application of ICP can often lead to overly-conservative set sizes; the tightness of the predicted set (referred to as efficiency) highly depends on the underlying model as well as the choice of the score function used in ICP. Various approaches have worked towards alleviating this challenge either by developing new application-speciff score functions [Romano et al., 2020, Yang and Pavone, 2023, Lindemann et al., 2023] or by optimizing the model and / or score function directly [Yang and Kuchibhotla, 2021, Cleaveland et al., 2023, Bai et al., 2022]. The direct optimization approach is appealing as general inplicaaiionagnnssie method for obtaining tight uncertainty estimates; however, it requires re-calibration held-out data in order to retain generalization guarantees coverage. By coalescing ICP with PAC-Bayes, we are able to train using all available data, while retaining generalization guarantees for coverage and efficiency; see Fig. for more details.
Contributions: In this work, we make the following core contributions:
1. We use PAC-Bayes theory to obtain generalization bounds on both the coverage and efficiency of set-valued predictors. In contrast prior work (see Fig. I and Sec. 3), our framework allows us to utilize the entire calibration dataset to learn the model parameters and score function (instead of requiring a held-out set for obtaining a guarantee on coverage).
2. We leverage these theoretical results to provide a practical algorithm (see Alg. 1) for utilizing calibration data fine-tune the parameters of the model and score function while guaranteeing test-time coverage and efficiency. This algorithm allows the user to specify a desired coverage level, which in turn specifies the degree which efficiency can be optimized (since there is trade-off between the desired coverage level and efficiency).
3. We evaluate approach on regression and image classification problems with neural network- based score functions. We show that our method can yield more efficient predictors than prior work on learned conformal prediction calibrated using Hoeffding-boung based PAC guarantee on coverage [Vovk, 2012, Prop 2a].
Background: Inductive Conformal Prediction
We consider supervised learning setup, wherein goal is to predict labels y E Y given inputs æ E X' In inductive conformal prediction (ICP) [Vovk et al., 2005], our goal is to develop a set-valued predictor which maps inputs set-valued function to satisfy a coverage guarantee, ensuring that the chance that the prediction set fails to contain the ground truth label is bounded to user-specifted level a, i.e.
subset of the label space C(a:) S y. Specifically,
want this
P æ..yr
(y C(x)) I a,
(1)

---

where D is the joint distribution over inputs and labels that test data are drawn from. In practice, D is not known, but we assume we have access calibration dataset Drat {(x,, 3:) 3:)) where each example (zt y:) is exchangeable with the test data. Given this set-up, ICP constructs set-valued predictor of the form
(= I s(z, y) S 7)
(2)
i.e. the sub-level set of the nonconformity function 8 X' x y + IR evaluated at the input ar. The nonconformity function assigns scalar value quantifying how poorly an example æ y conforms to the training dataset. It is common to define nonconformity function that depends on the learned model f. choosing s(x, y) = ((f(x); (<x). .)). measuring how poorly the prediction f()) aligns with the label [Angelopoulos and Bates, 2021]. Armed with the calibration dataset as well as the nonconformity function, all that remains to construct the set-valued predictor is to choose the proper threshold miscoverage rate a. Specifically, let Seal = {s(x. y) x, y E Deat] and choose T (Deal, a:) to be the q = [(n + 1) a)] / quantile of the set S. Then, so long as the score function is independent from D Deat. we have the following guarantee on the prediction sets defined by (2):
ICP defines calibration strategy to choose that guarantees a desired
1
P N+1 DONNDN y)
(y C( T" (Deal, a:) a.
Importantly, this probabilistic guarantec is marginal over the sampling of the test data point well as the calibration dataset. In practice, we are given fixed calibration dataset, and would like to bound the miscoverage rate conditioned on observing Deal. As shown in Vovk [2012, Prop 2a], we can obtain a pooabby-pproximatll--ooot (PAC) style guarantee on the ICP predictor of the form
log 8 2N
P DeareD
(y & C(æ; (DDaa" a)) < a a.y~D
2 1 -1-6. S.
In other words, with probability least 1 â over the sampling of fixed calibration dataset, can ensure the test-time miscoverage rate is bounded by a by calibrating for a marginal coverage rate of ā = a v- log 6/2N. Alternatively, one can achieve the same PAC guarantee using the tighter bound in [Vovk, 2012, Prop 2b] by choosing the largest E (0, a)) for which
8 2 11-a (N [ā(N + 1) 11, [ā(N + +]+1)
(5)
where (a, b) is the regularized incomplete beta distribution. This lacks an analytic solution for the optimal â, but is less conservative.
The strength of ICP lies in its ability to guarantee test-time coverage for any base predictor and nonconformity score function. However, ICP does not directly control the efficiency of the resulting prediction sets; the size and make-up of the prediction set for any given input æ is highly dependent on the score function (and thus also the base prediction model f). For this reason, naïve application of ICP can often yield prediction sets that are too "loose" to be useful downstream. Often, both the model and the score function may depend various parameters 0 E R.d e.g., the weights of neural network base prediction model. The values of these parameters influence the ICP procedure, from the computation of the score function s(x,, y; 0), the resulting threshold 7" (Deal, a; 0), and finally, the prediction sets themselves C(æ;7" 7*, 0). Our goal in this work is to investigate how we can use calibration data to fine-tune these parameters to optimize an efficiency objective while retaining guarantees on test-time coverage.
3 Related Work
Handcrafted score functions. In classification ( = [K], suppose f(x) predicts the softmax class probabilities; typically the score function is chosen as either s(x y) = 1 f(x), or s(x, y) = Ene(K) (f(x)x f(x)x 2 f(x)y), where f(x)y denotes the softmax probability of the groundtruth label. While the former score function produces prediction sets with the smallest average size [Sadinle al., 2019], the latter produces prediction sets whose size adapt to the difficulty of the problem [Romano et al., 2020]. In 1-D regression ()² = R), [Romano et al., 2019] rec- ommend training f fxx = [fa/2(2), fi-al (x)) using quantile regression to output the (heuristic) a/2 and 1 - a/2 quantiles, and then set the score function as s(x, y) max[fa/2 y. y (x))
3

---

to compute the distance from the groundtruth y to the prediction interval f(x). In n-D regres-
sion (V' ), is common to design ()) - where f(x) = (u(2r), u(x))
u(æ)
outputs both the mean of the lahel ju(x) and a heuristic notion of uncertainty u(x:) [Yang and
Pavone, 2023, Lindemann al., 2023]. While this leads to ball-shaped prediction set, designing
((f(z)) y) = maX (Ix(z); - yil can produce a box-shaped prediction set [Bai et al., 2022].
Learning score functions. [Yang and Kuchibhotla, 2021] propose selection algorithms to yield the smallest conformal prediction intervals given a family of learning algorithms. [Cleaveland et al., 2023] consider a time series prediction setup and leverage linear complementarity programming to optimize a score function parameterized over multiple time steps. [Stutz et al., 2021] develop conformal training to shrink the prediction set for classification, which learns the prediction function and the score function end-to-end by differentiating through and simulating the conformal prediction procedure during training. [Bai et al., 2022] considers optimizing the efficiency of parameterized score function subject to coverage constraints on calibration dataset, and derives generalization bounds depending the complexity of the parametrization. [Einbinder et al., 2022] focus the classification-seecffee adaptive predictive set (APS) score function [Romano et al., 2020] score function, and propose an auxiliary loss term to train the model such that its predictions more closely meet the conditions under which the APS score function yields optimal efficiency. The drawback of [Cleaveland et al., 2023, Stutz al., 2021, Bai et al., 2022, Einbinder et al., 2022] that separate held-out dataset is required to recalibrate the optimized score function to obtain test-time coverage guarantees. In this paper, we leverage PAC-Bayes theory alleviate this drawback and allow learning the parameters of the model and score function using the entire calibration dataset, while offering efficiency and coverage guarantees.
Generalization theory and PAC-Bayes. Generalization theory seeks to quantify how well a given model will generalize examples beyond the training set, and how to learn models that will generalize well. Early work includes VC theory [Vapnik and Chervonenkis, 1968), Rademacher complexity Shalev-Shwartz and Ben-David, 2014], and the minimum description length principle [Rissanen, 1989, Blumer et al., 1987]. In this work, we make use of PAC-Bayes theory [McAllester, 1998). In PAC-Bayes learning, one fixes a data-independent prior over models and then obtains bound on the expected loss that holds for any (potentially data-dependent) choice of posterior distribution over models. One can then optimize the PAC-Bayes bound via the choice of posterior in order to obtain a certificate on generalization. In contrast to bounds based on VC theory and Rademacher complexity, PAC-Bayes provides numerically strong generalization bounds for deep neural networks for supervised learning [Dziugaite and Roy. 2017, Neyshabur et al., 2017a,b, Bartlett et al., 2017, Arora et al., 2018, Rivasplata et al., 2019, Pérez-Ortiz et al., 2021, Jiang et al., 2020, Lotfi et al., 2022] and reinforcement learning [Fard et al., 2012, Majumdar et al., 2021, Veer and Majumdar, 2020, Ren et al., 2021]. We highlight that the standard framework of generalization theory (including PAC-Bayes) provides bounds for point predictors (i.e., models that output a single prediction for given input). Here, we utilize PAC-Bayes in the context of conformal prediction to learn set-valued predictors with guarantees on coverage and efficiency.
4 PAC-Bayes Generalization Bounds for Inductive Conformal Prediction
Optimizing efficiency with ICP requires splitting the dataset train part and calibrate on the other. The reduced data for calibration can result in weaker miscoverage guarantees. Drawing from PAC-Bayes generalization theory, we will develop a theory that facilitates simultaneous calibration and efficiency optimization for ICP using the entire calibration dataset.
Our generalization bounds are derived by randomizing the parameters of the score function A. Let Q(0) be a distribution over parameters 6. Note that, for a fixed target miscoverage rate å, every sample from 0 induces different prediction set C(x; (Daall â; 0). Test-time coverage for such a randomized prediction set corresponds to the probability of miscoverage, marginalizing over the sampling of 0:
Loov (Q)
IP p 0~~Q a..yD
(y & C(z; C(x;T" ā; (; 0))
(6)
The efficiency left of a predicted set C is a metric that can encode task-specific preferences (e.g.. the volume of the predicted set) that we wish to minimize while satisfying the desired miscoverage rate.

---

Similar to (6), we can define the efficiency measure Let on randomized prediction sets by taking an expectation single-set set efficiency measure:
Left (Q) = E a-Q
LLa (C(x; a; 0), 0), D.YDD
E
(7)
Our core theoretical contributions are to provide bounds on Lovr ) and Len (Q) that can be computed using Deal and, critically, hold uniformly for all choices of Q, even those that depend on Deal- This allows us to learn the distribution Q over score function parameters using Deat. First, we state generalization bound for test-time coverage.
Theorem (PAC-Bayer Bound on Coverage of ICP Prediction Sets). Let P(0) be a (data- independent) prior distribution over the parameters of the score function. Let DN be set of N samples from D. Choose empirical coverage purameter á & (0, 1) such that N > 1/á 1. Then, with probability greater than 1 over the sampling of Dx, the following holds simultaneously for all distributions Q(1):
((N + 1) N
KL(QI + log
B(N)
kl
(co
(8)
N
where kl(pllq) is the KL divergence between Bernoulli distributions with success probability p and respectively, and ((N)= := Beta( (oaaaa=i110 N N+1-k -----=---VV O[VNN(((1-a))) where k = [[N+1)å
The proof for this theorem is presented in App. A'. This theorem states that applying the calibration procedure will yield test-time coverage rate (ev close [(V+1) and the amount that it can differ shrinks the cardinality N of the calibration set increases, but grows as Q deviates from P. Finally, we note that an upper bound on Ecov(Q) can computed by inverting the KL bound [Dziugaite and Roy, 2017] using convex optimization [Majumdar et al., 2021, Sec. 3.1.1].
Next, we will provide a generalization bound on efficiency.
Theorem 2 (PAC-Bayes Bound on Efficiency of ICP Prediction Sets). Let P(t) be (data- independent) prior distribution over the parameters of the score function. Let DN be a set of N samples from 'D and 7 > O. Let the efficiency test of predicted set C always lie within² [0. 1]. Assume the score function is bounded, s(x, y; 0) < 3, and the efficiency loss T - laft (C(:;; T, T,0) is T- Lipschitz continuous in for all values 0f 0. Then, with probability greater than for all Q
we have
(er(Cla:=" + 23L V /L P) log( 2N
Lont (Q)
S
E 0m
VN
The proof for this theorem follows a similar approach to standard PAC-Bayes bounds, but is compli- cated by the dependence of on DN. To mitigate this, instead consider the generalization error between empirical and test-time efficiency for the worst-case choice of r, which requires assuming bounded and the efficiency objective smooth w.r.t. т. The full proof presented in App. A.
5 Practical Algorithmic Implementation
The generalization bounds above suggest a practical algorithm for using calibration data to simulta- neously conformalize base predictor while also fine tuning model and score function parameters. Specifically, we leverage the theory to formulate a constrained optimization problem, where the objective aims minimize an efficiency loss, while the constraint ensures that test-time coverage can still be guaranteed. The overall algorithm is summarized in Alg. 1.
'Our bound takes a similar form to the Maurer-Langle anggorddSeegger PAC-Bayesian bound [Seeger et al., 2001, Maurer, 2004] on generalization risk given empirical risk. However, while the risk on two samples is independent for fixed hypothesis, the coverage for particular sample depends the threshold 7" which is function of the entire calibration dataset Dx. This key difference precludes a direct application existing bounds and necessitates a novel theoretical approach.
Any uniformly bounded efficiency measure be mapped to [0,1] by scaling factor.
5

---

Tirgee o 0.10, 0.05
Targit 0.1, 5000
0.10
Vock Prop Za Vork Prop 2b
Usaned pooride gaacaaiio
0.00-
Sopertaa
0.0
6-100
Beri2
Sesd1
S-46
Feu0 Eeud1
Figure 2: Visualization of the KL budget allowed by the PAC- BaC-B generalization bound to achieve target test-time coverage of 0.1, plotted as function of and calibration set size N (left) as well as guarantee failure probability (right). Note the log scale on the axis on both plots.
5.1 Guaranteeing test-time coverage via KL constraint
Using the bound Theorem 1, we derive a constraint over data-dependent posteriors Q(0) such that choosing threshold using the conformal prediction procedure r DN (:) will guarantee test-time coverage greater than 1 a, where the coverage we enforce over DN. (1-o:), maybe different from the coverage wish achieve at test time,
Corollary 2.1 (Constraint on Data- Dependent Posterior). Fix â a, and a prior distribution P(0). Given a calibration dataset Deal of i..dd samples from DD we have that with probability greater than 1 6, then simultaneously for all distributions Q(0) which satisfy
[L(AV + 1)ā] KL(Q)P) S B(a, (N 11jkl (LIA)
- log (B(N))
a))
-log
(10)
N --1
holds that cov (Q) a.
The proof for this corollary is provided in App. A. Importantly, this bound holds for all Q(0) that satisfy the KL constraint, including Q that depend on the calibration data Dx Thus, we are free to use any optimization algorithm to search for feasible Q that minimizes any auxiliary loss; with B(a, á, 6. serving as a "budget" for optimization, limiting the degree to which Q can deviate from the data-independent prior P. Fig. visualizes this budget as a function N, and for fixed and 8. As the plots show, by choosing the threshold J to attain more conservative á, we can afford more freedom vary Q. The curve defined by B(a, å, 5, N) 1 test time coverage with probability greater than
indicates the maximum
for which our theory provides guarantee d for a randomized cata-independent score function (Q = P). As visualized the figure, this boundary aligns with maximum á implied by the PAC guarantee from Vovk [2012. Prop 2a], where differences are likely due to differences in bound derivation. However, there remains a gap between analysis and the results from Vovk [2012, Prop 2b], suggesting room for future tighter bounds.
5.2 Optimizing efficiency via constrained stochastic gradient optimization
In order to select a Q from this set, we propose directly optimizing the efficiency objective" (7). However, direct optimization is difficult due (i) the expectation over æ and 0, and (ii) the non- differentiability of the efficiency objective Len (C). To address (i), we use minibatches of inputs Monte-Carlo
sampled from Deal and finite set of K samples of 0 from Q(0) to construct approximation of the expectation, providing a stochastic estimate of the objective that can be used in a stochastic gradient descent algorithm. To ensure differentiabilityy we follow the strategy proposed in [Stutz, et al., 2021] and replace any non-differentiable operations in the computation of Lef with their "soft" differentiable counterparts. For example, the quantile operation needed to compute the optimal threshold r r6, Deat. â)) can be replaced with soft quantile implementation leveraging soft sorting
"Alternatively, one could optimize the generalization bound (9) directly, which effectively introduces a penalty on the KL divergence. In our case, we already have a constraint on the KL which mitigates overfitting. opt not to add complexity the optimization.

---

Algorithm Optimal Conformal Prediction with Generalization Guarantees
Require: Parameterized score function s(x; y. 0), Calibration dataset Deal, Target coverage rate
1 1- Probability of correctness 8, Differentiable efficiency objective Les (C") Prior distribution
P(0) (0: Hu; Eo), Posterior distribution family Q(#) -V(:; μ. E), Empirical coverage â
Initialize posterior distribution parameters μ. Σ +- Po, Eo for each optimization iteration do
Lost (1e, Σ) t- DIFFERENTABLLLOOSSS......
c(p, 2) + (L E)I (No, Eo)) B(a, ā, 6, N)
Update μ4, Σ to minimize Left (1, Σ) subject to c(u, D) <
end for
function DIFERENTABLEEOSSS(A..
Sample mini- S = {(z,, y 1 from Deal
Sample S1...., <K ~ N/ E R Ia)
0g + a + I for all k E [1...., K}
8j,k f s(x, My; 0z) for all j E (i,...,J,,kke. (1...,
Th f SOFTQUANTILS
S|,8] [(]+1)(1 a)) for all & E (I....,K) K} Compute prediction sets CjE. C(2)iTe) for all E Jb....,...k fl...., K}
K return Latr Σ) JK Ek=1 Ej=1 (G,,))
end function
algorithm [Cuturi et al., 2019, Grover al., 2019]. As optimizing over the space of all probability distributions over θ is intractable, we restrict Q to be within a parametric class of distributions for which obtaining samples and evaluating the KL divergence with respect to the prior is tractable. In this work, we follow prior work in the PAC-Bayes and Bayesian Neural Network literature and fix both P and Q be a Gaussian with diagonal covariance matrix, N(u, diag(o") where μ Rd and ²² E R This allows analytic evaluation of the KL divergence, and differentiable sampling via the reparametrization trick, as shown in Alg. 1. In this way, both the optimization objective and the constraint can be evaluated in differentiable manner, and fed into gradient based constrained optimization algorithm. We choose the Q with the lowest loss that still satisfies Corollary 2.1. More details on the optimization procedure can be found in Appendix B.
5.3 Practical considerations
Choice of prior. A prior P(0) may give high likelihood to values of 0 that yield good prediction sets, but also to 8 that perform poorly. To optimize efficiency, Q must shift probability mass away from poor towards good f. However, due to the asymmetry of the KL divergence, [L) is larger if Q assigns probability mass where P does not than vere-versa. Thus, in order to effectively optimize efficiency under a tight KL budget, we must choose P that not only (i) assigns minimal probability density to bad values of 0, but more importantly, (ii) assigns significant probability density to good choices of 0. How do we choose an effective prior? In some cases, it suffices to choose P isotropic Gaussian distribution centered around random initialization of B. However, especially when 0 correspond to parameters of neural network, using data-informed prior can lead to improved performance [Perez-Ortiz et al., 2021, Dziugaite and Roy, 2018]. Care is needed to ensure that a data-informed prior does not break the generalization guarantee; we find that a simple data-splitting approach similar to "Perez-Ortiz et al., 2021] is effective: We split Deal into two disjoint sets: Dy, used to optimize the prior without any constraints, and DN. used to optimize the posterior according to Alg. In our experiments. we consider two methods of optimizing a Gaussian prior P = (p,, diag( ²))) First, we can optimize only the mean μe to minimize L (p)),,, keeping o² fixed. This aims to shift P to assign more density to good values of 0, but the fixed o² may still assign significant mass to bad choices of f. Alternatively, we consider optimizing both l and o² to minimize Loft P). By also optimizing the variance, we can minimize probability mass assigned to bad choices of 0, but this comes with risk of overfitting to Do-
Test-time evaluation. The guarantees on coverage and efficiency generalization hold in expectation over both data sampled from the data distribution D as well as model and score function parameters sampled from the learned posterior Q. Thus, in order to use such a predictor in practice and attain the desired coverage and efficiency, one would need to sample parameters 0 from Q, and then compute the
7

---

Standard
PAC-Bages
Cal dita
Sur 18083
Eand
C..
-0.75
0.0 012 0.5
825
200
-225 iido 6:3 0.75
66.00 -025
0.75
1.00
-0.70 -1.50 -0L25 (230)
1120
0.50
9.25
1001 -10M -111 -1.50
-0.25
10:0
1121
0.00
0.75
110
-1.00
-0.3
-0.30
-012
1000
0.25
0.00
1.75
1.00
Figure 3: Standard ICP with fixed score function (left) can yield over-conservative prediction sets. By using calibration data to also learn an uncertainty scaling factor the nonconfornity score function, both the learned (middle) and PAC-Bayes (right) approaches
yield more efficient prediction sets. When the calibration set size is large (bottom), both the learned and PAC-Bayes approaches do well. However, when calibration data is limited (top), our PAC-Bayes approach yields prediction sets with better test-time efficiency.
resulting prediction set C(x;;) r). However, as the threshold for this prediction set T (D a 0) depends on Deal, this approach would require holding on to the calibration dataset to find the optimal threshold of each sample of 0. In practice, once optimize Q. pre-sample K values of from Q, and pre-compute the optimal threshold for each. Then, at test-time, we randomly select one 0, T pair from the set to evaluate each test input.
6 Experimental Results
We evaluate our approach on an illustrative regression problem as well as on an MNIST classification scenario with simulated distributional shift." For each domain, we evaluate our PAC-Bayes approach against two baselines: (i) the standard ICP approach, where we use a fixed, data-independent score function ddefsult (2r, y) and use the entirety of the calibration data compute the critical threshold т; and (ii) a learned ICP approach [Stutz et al., 2021] which uses portion of Deal to optimize parameters 0 of a parametric score function Soptim (x. y; () to minimize an efficiency loss Letl. and the remaining portion to re-estimate the threshold 7 to guarantee test-time coverage. For the PAC- Bayes method, we consider the same parametric form as the learned baseline, but instead randomize the score function by modeling distribution over 6, Both the learned and the PAC-Bayes baseline require choosing data split ratio, i.e. what fraction is used for optimization (or prior tuning for the PAC-Bayes approach), and what fraction is held out for recalibration (or constrained optimization). For all methods, we target the same test-time coverage guarantee greater 1 - 8. For the standard and learned methods, the amount of data in the held-out recalibration set determines the empirical coverage level & needed to attain this guarantee, using either Vovk Prop 2a (4), or Vovk Prop 2b (5). We compare against both bounds in experiments. For the PAC-Bayes method, the choice of a hyperparameter: choosing lower value yields a larger budget for optimization, but entails using more extreme quantile for the threshold т. As all methods provide guarantees on test-time coverage, our evaluation focuses on the efficiency of each method's predictions held-out test data that exchangeable with the calibration data. Additional results (including coverage results), as well as specific details for all experiments, can be found App. B.
a coverage with probability
6.1 Illustrative demonstration: 1-D regression
As illustrative example, consider 1-D regression problem where inputs E E and targets y E R are drawn from a heteroskedastic distribution where noise increases with æ, as shown in Figure 3. We train two hidden layer fully connected neural network to minimize the mean squared error on this data, obtaining a base predictor f(x) that produces a single point estimate for y. We aim
WWe implemented our approach using Py Torch [Paszke et al., 2019] and Hydra (Yddan, 2019]; code to run all experiments is available at https: : ////ttgtbb hwtm///laab//gaa hwtps/aaaaaaaaaaaeeeeeeaeaaeeeee cowformll-ooooooooooooooocoooomm prraaaiciriiiiiioon

---

327 g
7
Standard (Voria 24)
Standord (Vorks 20)
Standard (Voe's
Standard (Vork
Aveenge Prodiction Sk Sioo
4.0-
Learned (Vork
Rebative Prelittan Set Size
1.50
Learned (Vork 21)
2
Tesmmed (Vork 2b)
Leurnee (Vork 2b)
3.3
PAC-BBooo
1.25
PACC-Bao
3.-
1.00
2.-
0.50
1.3
0.23
1.0
0.00
10000
1500
20000
2000
5000
0.25
0.5
0.76
Stor of Callbaation Ditiard (N)
Split
Figure 4: Left: A base model is trained on clean MNIST digits (top), but calibrated and tested on corrupted digits (bottom). Middle: Average prediction set size on test data versus calibration set size (N) for a data split ratio of 0.5. Right: Prediction set size relative to standard ICP (Vovk 2a) as a function of the data split ratio, averaged over random seeds and across all calibration set sizes.
to obtain set-valued predictor using held-out set of calibration data with 0.1 and d 0.05. For the sake of this example, we assume that we no longer have access to the training data, and only have calibration data and pre-trained base predictor which only outputs point estimates and no input-dependent estimate of variance. Therefore, for the standard application of ICP, we must use the typical nonconformity function for regression, Sdefauit (2r, y) = [ - y/l. Note that this choice yields prediction sets with a fixed, input-independent size, which is suboptimal in this heteroskedastic setting. To address this, we consider using the calibration dataset not only determine the threshold r", but also to learn a parametric score function that can capture this heteroskedasticity. Specifically, we learn an input-dependent uncertainty score u(x; 0) which is used scale the nonconformity score Soptim (x, y; 0) [=) - yll //u (e; ()) [Angelopoulos and Bates, 2021]. We model u(x, 0) as separate neural network with the same architecture as f. and optimize either or (()) to minimize the volume of the resulting prediction sets. To do so, we minimize loss proportional to the log of the radius of this set, which in this case can be written as Left (C(x, T)) = log(u( (=x: 0) -).
As can be seen in Figure 3, when N = 5000, both the learned baseline and our PAC- PAC-Bayes approach able to learn an appropriate input-dependent uncertainty function which yields prediction sets which capture the heteroskedasticity of the data, and thus yield tighter sets in expectation over æ. However, if reduce the amount of calibration data available to N 500, the learned approach starts to overfit on the split used to optimize efficiency. In contrast, the KL-constraint of the PAC- Bayes approach mitigates this overfitting, and outperforms both baselines in terms of test set efficiency for smaller amount of calibration data.
6.2 Corrupted MNIST
Next, we consider a more challenging distribution shift scenario, where we aim to deploy model trained on "clean" data to a domain with distribution shift. As the base predictor, we use LeNet convolutional neural network trained on a softmax objective to classify noise- free MNIST digits [LeCun al., 1998]. Then, we simulate distribution shift by adding Gaussian noise and applying random rotations to held-out set of the dataset: examples of the clean and corrupted digits are shown Figure Our goal is to use calibration dataset of this corrupted data design a set-valued predictor that achieves coverage on held-out test data with the same corruption distribution.
As is conventional, when applying ICP to probabilistic classifiers, we use the negative log probability as the nonconformity score ddefnutt (z, y) = [log softmax [ [Stutz et al., 2021, Angelopoulos and Bates, 2021]. This score function leverages the implicit uncertainty information encoded in the base model's 's probabilistic predictions; but these probabilities are far from calibrated, especially in the presence of distribution shift [Ovadia et al., 2019, Sharma al., 2021]. Thus, we consider using the calibration dataset, which is representative of the corrupted test distribution, to fine-tune the predicted probabilities, defining Soptim (x. y, 0) = [log voftmax/((as 0)](v) [v), where are the parameters of the fully connected layers of the base predictor. As before, we measure efficiency as the size of the prediction set, (C) = ICI. In contrast to the regression setting, here C' is discrete set over the set of class labels, and thus the size of this set is non-differentiable. To smooth this objective for training,

---

we follow the approach of [Stutz et al., 2021], and first use sigmoid to compute soft set- membership assignment for each possible label, and then take the sum to estimate the size of the set,
ean (C( r)) = Σ (T
s(x. y. 0)))
(11)
3/E (E......))
where the temperature I' is a hyperparameter which controls the smoothness of the approximation; in our experiments we use T = 0.1.
We evaluate each method for different calibration set sizes N and data split ratios, repeating each experiment using 3 random seeds. For all approaches, we desire a coverage guarantee of a 0.1 with ó = 0.05. For the PAC-Bayes approach, we run the algorithm with d = 0.01, performing a grid search over 5 values of evenly spaced between 0.2 and 0.8, and choosing the approach with the best efficiency generalization certificate (9); using the union bound for probability ensures that the efficiency for the best of the five runs will hold with probability at least 0.05, i.e., an effective 6 of 0.05. For the PAC-Bayes approach, we optimize both the prior mean f and variance o² on Do. as we found that optimizing the mean alone yielded a poor prior; ablations are provided in App. B. The results and plot the average test set size as a function of N. First, we note that even for the standard ICP approach, increasing N leads to smaller prediction set size, while still maintaining the desired test-time guarantee. In general, both the learned and PAC- MAy-Bayes approaches improve upon the standard baseline by fine-tuning on the corrupted calibration data. However, when data is limited (NV = 1000), the learned baseline overfits during optimization on the first half of the calibration data, and subsequent calibration yields set sizes that are even larger than the standard method. Our method mitigates this by using all the data to simultancously fine-tune and calibrate while ensuring test-time generalization, thanks to the KL constraint. Empirically, the PAC-Bayes method yields prediction sets with efficiency comparable or higher than the learned baseline calibrated using Vovk 2a. However, there still remains a gap between our results and the learned baseline calibrated with tighter bound in Vovk 2b, as is evident in our analysis of our bound in Figure 2. In the right figure, we explore the sensitivity of both learned methods on the choice of data split ratio. We observe that the PAC-Bayes method is less sensitive to the choice of data split ratio.
summarized in Figure 4. In the middle figure, we hold the data split fixed at 0.5,
are able to calibrate to larger å
7 Conclusion
In this paper, we introduced theory for optimizing conformal predictors while retaining PAC general- ization guarantees on coverage and efficiency without the need to hold-out data for calibration. We achieved this by combining Payes theory with ICP to furnish generalization bounds with the same data used for training. We translated our theory into practical algorithm and demonstrated its efficacy on both regression and classification problems.
I Limitations. As shown in Figure 2, our theory remains overconservative relative to the tight Vovk 2b PAC bound, which future work could aim to address. Practically, a key limitation of our approach is its dependence on the availability of a good prior. Although, we were able to mitigate this issue by training prior on a portion of the calibration dataset, this strategy can struggle when datasets are small or the number of parameters to optimize are very large. Furthermore, while diagonal Gaussian distributions are convenient optimize, they may not represent the optimal posterior. These limitations may explain why we obtained only modest improvements in efficiency with respect to the Vovk 2a baselines in our experiments; we optimistic that future advances in prior selection theory requires sampling
and representation may lead to improvements. Finally, while from the posterior Q, set-up also requires computing the threshold 7" for each parameter sample. Future work could explore applying disintegrated PAC-Bayes theory [Viallard et al., 2023] to yield (perhaps more conservative) generalization bounds that hold for a single sample from the posterior.
Broader Impact. This work is building towards safer and trustworthy ML systems that can reason about uncertainty in their predictions. In particular, this work is a step towards developing calibrated uncertainty set predictors that are efficient enough for practical applications.
Future work. This work opens up exciting new theoretical and practical questions to pursue. On the theoretical front, we are excited to explore the development of an online learning approach that can leverage this theory to provably adapt to distribution shifts on the fly. On the practical front, we look forward to using this framework for providing reasonable uncertainty estimates in robot autonomy stacks to facilitate decision making and safety certification.
10

---

Acknowledgments and Disclosure of Funding
Anirudha Majumdar was partially supported by the NSF CAREER Award [#2044149] and the Office of Naval Research [N00014-23-1-2449) Asher Hancock was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-2146755 Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and not necessarily reflect the views of the National Science Foundation.
References
Md Manjurul Ahsan, Shahana Akter Luna, and Zahed Siddique. srcchnn--leaning--aseee disease diagnosis: A comprehensive review. Healthcare, 10(3):541, 2022.
Anastasios Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv:2107.0755: 2021.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In Int. Conf. on Machine Learning, pages 254-263, 2018.
Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong. Efficient and differentiable conformal prediction with general function classes. In Int. Conf. on Learning Representations, 2022.
Peter L. Bartlett, Dylan J. Foster, and Matus J Telgarsky. Spectrally-Normalizee Margin Bounds for Neural Networks. In Conf. Neural Information Processing Systems, volume 30, 2017.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Occam's 's razor. Information Processing Letters, (466)3377-380 1987.
Matthew Cleaveland, Insup Lee, George Pappas, and Lars Lindemann. Conformal prediction regions for time series using linear complementarity programming. arXiv:2304.01075, 2023.
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In Conf. on Neural Information Processing Systems, volume 32, 2019.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain markov process expectations for large time. iv. Communications on Pure and Applied Mathematics, 36(2):183-212, 1983.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. In Proc. Conf. on Uncertainty in Artificial Intelligence, 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent pac-bayes priors via differential privacy. In Conf. on Neural Information Processing Systems, volume 31, 2018.
Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty-awar classifiers with conformalized deep learning. Conf. on Neural Information Processing Systems, volume 35, 2022.
Mahdi Milani Fard, Joelle Pineau, and Csaba Szepesvári. Pac-bayesian policy evaluation for rein- forcement learning. arXiv:1202.3717, 2012.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In Int. Conf. on Learning Representations, 2019.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic Generalization Measures and Where to Find Them. In Int. Conf. on Learning Representations, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2222 1998.

---

Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George J Pappas. Safe planning in dynamic environments using conformal prediction. IEEE Robotics and Automation Letters, 2023.
Sanae Lotfi, Mare Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and Andrew G Wilson. PAC-Bayes compression bounds so tight that they can explain generalization. In Conf. on Neural Information Processing Systems, volume 35, 2022.
Anirudha Majumdar, Alec Farid, and Anoopkumar Sonar. PAC-Bayes control: learning policies that provably generalize novel environments. Int. Journal of Robotics Research, 40(2-3):574-593, 2021.
Andreas Maurer. A note the pac bayesian theorem. arXiv:cs/0411099 2004.
David A McAllester. Some PAC-Bayesian theorems. In Proc. Computational Learning Theory, pages 230-234, 1998.
Behnam Neyshabur, Srinadh Bhojanapalli. David McAllester. and Nathan Srebro. A PAC-Bayesian Approach to Spectrally-Norman Normalized Margin Bounds for Neural Networks. arXiv:1707.09564 20
Behnam Neyshabur, Srinadh Bhojamapalli, David McAllester, and Nati Srebro. Exploring Gen- eralization in Deep Learning. In Conf. on Neural Information Processing Systems, volume 30, 2017b.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Conf. on Neural Information Processing Systems, 32, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perffrmance deep learning library. In Conf. Neural Information Processing Systems, volume 32, 2019.
Maria Perez-Ortiz, Omar Rivasplata, Benjamin Guedj, Matthew Gleeson, Jingyu Zhang, John Shawe- Taylor, Miroslaw Bober, and Josef Kittler. Learning pac-bayes priors for probabilistic neural networks. arXiv:2109.10304 2021.
María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certifi- cates for neural networks. Journal of Machine Learning Research, 22: 1236666--0,355, 2021.
Allen Ren, Sushant Veer, and Anirudha Majumdar. Generalization guarantees for imitation learning. In Conf. Robot Learning, pages 1426-1442 2021.
Jorma Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific Publishing, 1989.
Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvari. Pac-bayes with backprop.
a9Xiv: 190.0:1900.07380. 2019.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Conf. on Neural Information Processing Systems, volume 32, 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. In Conf. on Neural Information Processing Systems, volume 33, 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223 234, 2019.
Wilko Schwarting, Javier Alonso-Mora, and Daniela Rus. Planning and decision-making for au- tonomous vehicles. Annual Review of Control, Robotics, and Autonomous Systems, 1(1):187-210, 2018.
Matthias Seeger, John Langford, and Nimrod Megiddo. improved predictive accuracy bound for averaging classifiers. In Int. Conf. on Machine Learning, pages 290-297, 2001.
12

---

Shai Shalev-Shwariz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, 2014.
Apoorva Sharma, Navid Azizan, and Marco Pavone. Sketching curvature for efficient out-of- distribution detection for deep neural networks. In Proc. Conf. on Uncertainty in Artificial Intelligence, pages 1958-1967, 2021.
David Stutz, Ali Taylan Cemgil, Arnaud Doucet, et al. Learning optimal conformal classifiers. Int. Conf. on Learning Representations, 2021.
Jessica Vamathevan, Dominic Clark, Paul Czodrowski, Ian Dunham, Edgardo Ferran, George Lee, Bin Li, Anant Madabhushi, Parantu Shah, Michaela Spitzer, et al. Applications of machine learning in drug discovery and development. Nature Reviews Drug Discovery, 18(6):463-477, 2019.
Vladimir N Vapnik and Ya Chervonenkis. the uniform convergence of relative frequencies of events to their probabilities. Dokl. Akad. Nauk, (8), 1968.
Sushant Veer and Anirudha Majumdar. Probably approximately correct vision-baat based planning using motion primitives. In Conf. on Robot Learning, pages 1001-1014, 2020.
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the practical disintegration of pac-bayesian bounds. Machine Learning, 2023.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian Conf. on Machine Learning, pages 475-490, 2012.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer, 2005.
Waymo. The Waymo Driver Handbook: Teaching an autonomous vehicle how to perceive and understand the world around it, 2021. Available at https://blog waymo com/2021/10/
the-waymo- ddriver-handboo www.-habooooeeeeeetiiooeee wwwppppiin.neeeee html.
Omry Yadan. Hydra - a framework for elegantly configuring complex applications. Github, 2019.
URL https:tt////tt. thub. com//aaceeookressercchhaaa
Heng Yang and Mareo Pavone. Object pose estimation with statistical guarantees: Conformal keypoint detection and geometric uncertainty propagation. In IEEE Conf. on Computer Vision and Pattern Recognition, 2023.
Yachong Yang and Arun Kumar Kuchibhotla. Fimite-sample efficient conformal prediction. 13877, 2021.
13

---

A Proofs
Our coverage and efficiency generalization bounds follow similar form to many PAC-Bayes bounds. fundamental building block of these proofs is the Donsker- Varadhan Donsker-Varadhan variational formula [Donsker and Varadhan, 1983], which restate below.
Lemma (Donsker- Varadhan variational formula). For any measurable functioonn h I. we have,
E [h(0)] KI(QIIP) (~Q
log
E
(xxp(h(0))
sup QEP())
We then apply this lemma to obtain a core result relating to quantities depending on parameters 0 and sampled data DN which we derive first second lemma which is common the proof both generalization bounds.
Lemma 2. Let (0, DN): θ (X V)N + R be measurable function mapping a parameter and a set of sampled data to a scalar. Let P be an arbitrary distribution over O independent of D. Let denote another arbitrary probability distribution over O. Suppose there exists a function ((N) O such that, for any fixed f E ④
E DN
[exp( ((, Dx))) & B(N).
Then, we have that
& KL(QIIP) log B(N)
IP Dy
VQ:
2 1 6.
0~Q
5
Proof of Lemma 2.
We start with our assumed property of B(N), and integrate it with respect 0.
E [exp($(0,, Dx)) - B(N)
DN E
[exp(((0, Dx) ) - B(N)
6~ DN
The integrand is non-negative and P is independent of Dx; so, by Tonelli's theorem, swap the order of the integration with respect to the parameters 0 and the dataset DN. yielding [exp(0(0, Dx)) & B(N)
E Dx P~P
Now, apply the Donsker- Varadhan variational formula to get
- B(N) Dx
E
(12)
(ePPa DN
E
11
(13)
Now, by the Chernoff bound, for any random variable X, PP P(X> 5) Ele Je je
so if we let = = e= -log we have
P(X > - log 8) - 1|c
Now, applying this bound to X suPQEP(0) [Ea-q ( DN>] - KL(QIIP) - log B(N)), obtain
IP Dx
sup QEP(0)
E
(0,, DN)] - KT log B(N)) > >llog
A~Q
(uPppEr0,E00-00000000 1PP Bog B(VVI]
< E
DN
< 8
(14)
14

---

Now, since
3Q P(O): E [x), KL(QIIP) - log B(N) a
-log
sup QEP(O)
E 100 Dx)] KL(Q]IP) A~Q
log B(N)) (
-llog
-lo
the result from (14) implies that
IP
EPO):
E. (0,, PN)] - (T P) log B(N) B~Q
log)
s - log
Dx
Taking the complement, we have
I VQ P(O):
(00, (0, Dx)] (L( log B(N)
21-8
Dx
R-Q
Rearranging terms completes the proof.
Equipped with this lemma, we can now prove our core theorems. We start by proving the coverage bound.
Proof of Theurem I. First, let Loov (0, D (x) represent the miscoverage rate a conformal predictor calibrated to achieve - à empirical coverage on Dx:
(0, DD,d0 à) = P (y &
a.y~D
Note that for fixed 0, the distribution of coverage (and hence, mis-coverage) conditioned on particular calibration dataset follows a Beta distribution [Angelopoulos and Bates, 2021, Vovk, 2012]. Specifically, Leo (0, DN, à) Beta((L(N + 1) N + 1 L(N + 1)ā])).
Now, choose (0, Dx) to be
([NN + 1)
Φ(0, DN) = (N -NN-1K 1)kl
Leor (0, DN @i)
-
First, we derive the bound BNN) required to apply Lemma 2. Let h: |(N 1)ā b Loov (0, DN. â). Then,
k-1 and
N-
E [exp(1) (0, Dx))] DN
E [exp((N (a) (a|b))]
DN
(N - 1)alog a , + (N 1)(1 - -) a)
log - a
E
exp
1-
(N-1)a / (1-0 a
(N-1)(1-a)
E
1-b
Note that (N 1)a- k: 1, and (N - -1(1 - a)
N k. Substituting, we have
a k-1
1
N-
E (ex [N))] = E Dy
DN
b
1-b
k 1 (1 N-h
E
bb--((1 - b)* bN
DN
a k a) +
62 b2-h(1 b)t Beta k, k)
bl-b( b)k- D 6+ (1 N- db (k: 1)!(N - k:)!
k (1 a) N
N
x N)N-
(k: 1)!(N k))
= Beta(a; k, N +1-- k)
15

---

Thus, in this case we can analytically evaluate this expectation as
E (ex Px))] B(N) Beta 1) N k).
(15)
Dy
where [eta( a, 3) the pdf of the Beta distribution with parameters a, /3.
To compare our bound with other PAC-Bayes bounds and to quantify the asymptotic behavior of ((N), we can derive an upper bound. First, we plug in definition of a, and group terms
N
(N - 1)! (k: 1)a-1 (N k) k)
B(N) a a) (k 1)((N k:
N (N 1)N-1 (k 1)! (N k)!
By Stirling's 's approximation of a!, we know
V2raaee -raaaaeaatta at IIEII al < V2raa
Therefore,
aa e
<
a! V
a! V2TTae
The
a
Plugging in these bounds, we can obtain a simplified expression which removes the factorials and high powers of N:
-N exp 1T k 1)(N - k)
1
B(N) N
12N 12
12k
11
12N
12k +
Notice that for as long as N 2 a - 1. In this case, due to monotonicity, the exponential term is less than 1. This yields
N, the term the exponent negative. Given the definition of k, this true
VNN - := 2 1)(N k)
N
B(N) N
(16)
a(1
Having computed B(N). we can now apply Lemma to obtain
VQ:
T. (N- ((V-1)b6 1)kl Q-Q
( + 1)&J
[eoor(, Da, (o, Da,(i))
<KT(Q])P) log
B(N))
DN
N
Since kl(,,)) is convex in both arguments, we can use Jensen's inequality bring the expectation over inside each argument, yielding,
((VV + 1)&J -1
B(())
YQ 1)kl DN
[Ccor (O, & KL(Q]IP) log
2
Note that by definition in equation (6), Leov (Q) E (oov (0, DN, a:). Rearranging terms completes the proof.
Proof of Corollary 2.1. Let [(++1)&1-1 and for compactness, let Loov Loov (0, DN a)) Let C' be the event that our KL. constraint holds, i.e.
B(n) 8
KT(QIIP) < (n 1))1 log
Consider the event E that (Govl < Since S a, we have that
IP
[oor]
S Sa F. =1
A~Q
Now, consider the complement, E. We know that (l(g|l>)) ) is monotonically increasing in for g.
Thus, conditioned on E, we have
E [ s a F. = PP (p [n((ll A~Q
IP
E. enQ
(carl) s (a
16

---

Given these statements, we have
E cooll 1 $/())
A~Q
= = P)P
Coodl 3a + + [ C)
< <a < (. F
A~Q
=P((B ( (B
kl
all
[cav]]
- <kl a)
B~Q
P kl q
E
[Cood]
S <1l(q E.C)
A~Q
+P(RIC)
kl
all 8-Q
(aav)
k a) F.
=P(w
E 41
(Coou)
(17)
A~Q
Now, due to the convexity of kl, we have through Jensen's incquality,
[kl (gll 2 kl q
E [Ccor]
0~Q
8-Q
Plugging this to the result of Theorem I, we have
KL(QIIP) + log
B(a)
P
VQ.K! kl
(ll mil
E [Cool]
2 1 1
Now, since this holds for all Q, it must also hold for those Q satisfying the constraint. Thus,
KL(QII + log
B(a)
P
AQ, kl
9l E [Coorl
C
2 21-8
n
(n 1)kl (g|1a)
log
B(n)
+ log
B(n)
vQ, kl
(ll
E [corl) s
C
2 1
n2
((QQ.tt (Q2 kl (all (all, IE (cwrl)
P
s kl(allaa C)
Plugging this result into (17), we have
2 21-5, P E [eand] S sa/c) (nQ
completing the proof.
Next, we prove our bound on efficiency.
Proof of Theorem 2. We wish bound Leu (Q) function of the observed empirical efficiency. Define Loft (0, r, D2) as the empirical mean efficiency observed for a partieular value of parameter and threshold and (0 7) as the expected efficiency of the prediction sets constructed with and 7 on new data sampled from D:
1 N
(0, Dx) =
Σ
Last (C(a,T
N
-=1
Len (0, anD
E
Lea (C(x;
17

---

In ICP, the threshold r T c; f) itself depends on Dv. This means that even for fixed 6, the observed efficiency for the prediction set on each sample in Dx are not independent from one another. To avoid this complication, we define the quantity
(DD,
R(00, Dx) = sup || (0, T, Dx) - (0,T()))))
which measures the worst-case difference between the empirical and true mean efficiencies over the worst-case choice of threshold. Note that
Lat T" (Dx, à, 0)) (o, (0, 0), DN) S Rí(0, Dx).
(18)
Next, we consider the expectation of this quantity over the sampling of Dx:
R(O)
E DN
sup Sen (0, Dx) Loft (0, r)]l
Given that, by assumption, Left is L, -iisschit in т, and is bounded by 3 (due s(æ, y, 0) being bounded), we use the result shown in Proposition 4 of Bai et al. [2022] to show that R(0) can be bounded for fixed
2.3T.r
R(O) S VN
(19)
Furthermore, assuming lett is bounded by [0, 1], then, for fixed R(,,, Dx) satisfies the bounded differences property with bound L/N. Therefore, applying McDairmid's inequality, we obtain
(10(0, DN) R(O) 2 28) 2xpp 2exp(-2NN (-2Ns²))
TP
(20)
DE
This bound only holds for a fixed 0 independent of Dx-
To obtain bound which holds for 0 ~ Q for all Q, we can follow the standard PAC-Bayes bound sub-Gaussian random variables. Specifically, we turn to Lemma 2, this time defining
(00, DN) 2(N - (),, Dx) R(0))²
Note that given (20), applying Lemma 1.5, we can bound
E [ex Dx))] B(N) 2N.
Now, we can apply Lemma 2 to obtain
2N 2 7
IP
AQ
E 2(N () Dw) R(O))²] & (T)(Q)))) log ANQ
DN
?
Bringing the expectation into the quadratic using Jensen's inequality, and rearranging terms, obtain
KL(Q]IP) + log
2N ?
P
YQ:
E ANQ
R( DN) & E. a-Q
[R(O]] +
2 21-7
Dy
2(N - 1)
Now, substituting (19) and (18), we obtain that with probability greater than 1 - y, for all Q, it holds that
KL(QIIP) log
2N
23L, VN
E e~Q
(o, 0)) (0, (Dv, S
2(N 1)
E Q~Q
[Let (0, (Dx, (,))) < E
a, (D)
onQ
[KL(QIIP) + log 2N
23L
VN
Noting that by definition, Lat (Q) stated, concluding the proof.
Teg- Lett T* (DN,ā,0)) ()))), which yields the theorem as
18

---

B Implementation Details
All experiments were performed on a workstation with a Intel Core 19-10980XE CPU with a NVIDIA GeForce RTX 3090 GPU.
B.1 Detailed Algorithm Overview
In this section, give detailed description of general experimental method. Subsequent sections give specifics to each of the experimental domains we consider.
Model training. For each experiment, we first train a base neural network model on a training dataset. Next, for each calibration approach, we pair the neural network model with score function which is used for calibration.
Model calibration. In the calibration phase, we first split the calibration data Deal into two random splits, tuning dataset Do and true calibration dataset DN, where the fraction of data used for tuning (the data split) is a hyperparameter. In the standard baseline, the no optimization performed so Do is the empty set, and D Deat is used to calibrate the model. In the learned baseline, parameters are optimized on only Do. and D is used to calibrate by computing the threshold T In PAC-Bayes approach, tune prior parameters Do. and then optimize the posterior following Algorithm on DN-
We aim for the same PAC guarantee of 1 - a test coverage rate with probability greater than 1 1 8. For the standard and learned baselines, N,, i.c. the size of DN determines the required empirical miscoverage rate à. We can either â equal the value given by (4) [Vovk, 2012, Prop 2a], or by finding the value (e.g. by grid search) satisfying (5) [Vovk, 2012, Prop 2b]. For our PAC-Bayes approach, á is hyperparameter which trades off conservatism in choosing T" for the freedom to optimize score function parameters on DN while retaining the PAC generalization guarantees. To select this hyperparameter,
choose K values for á, and for each, run our algorithm with tighter = 5/K. This allows us to use a union bound argument to achieve the same PAC guarantee as the other approaches uniformly over the K predictors we obtain. We select between these predictors by choosing the predictor with the best generalization bound on efficiency (9).
Optimization on Do- In both the learned and PAC-Bayes approaches, we optimize parameters on the tuning dataset to minimize the efficiency via gradient descent. Note that the efficiency of conformal predictor depends on the score function evaluated at a given imput as well as the threshold 7* which corresponds the empirical quantile of the score function evaluated on the calibration dataset. We follow the approach of Stutz et al. [2021], and for each minibatch, we first compute 7" by evaluating the & quantile on the minibatch, and then use this threshold to evaluate the efficiency loss on the data. We use the softsort approach proposed by [Grover et al., 2019] to differentiate through the quantile function. The prior tuning in our PAC-Bayes approach follows the same protocol, with the addition of first sampling 0 ~ N(uo, En) (differentiably, via the reparameterization trick), before computing the efficiency loss for each sample and averaging.
Optimization on DN. In our PAC-Bayes approach, we further optimize the score function on the second split of data, this time holding the prior fixed and instead optimizing the posterior Q WV, Σ) to minimize the efficiency loss (7) subject to the KI. constraint (10). The efficiency loss is evaluated in the same way above, and the KI. constraint can be evaluated analytically. To perform the constrained optimization, we implement an augmented Lagrangian method. Specifically, construct an unconstrained optimization problem with the objective
Lang (M, E, s; X, p) Lof (V, Σ) + Ao(p, 5) (T.(N(P,, (1) (T..))KK((N(())) E)) B(a, &,
2 Eo,,
E,
where B(a, å, 5, N) is the KL budget defined in (10) and 8 E RR a positive slack variable translating the inequality constraint in (10) to equality constraint c(u, s) 0. In each outer iteration, we approximately solve this unconstrained optimization problem for μ, Σ and using projected gradient descent (clamping to 0 after any gradient step making it negative). After
19

---

optimization, we evaluate the constraint c(p, I, s), and update the penalty scale according to
À - X + pe(ju, E,
before rerunning the inner optimization. We run 10 outer iterations, and return the μa, E which yielded the best efficiency loss while satisfying the constraint.
Calibration on Dx- For all models, we calibrate using Dr by choosing T" (Dxx, alpha) be the - quantile of the set of score function values evaluated on DN In the case of the PAC-Bayes approach, the score function (and hence the threshold) depends on the sampled value of 0. Therefore, after optimization, we first pre-sample M values of 0 ~ Q, and for each, compute 7 as above. We store the sampled ( values along with their associated r" values for use at test time.
q= = 11 -
Evaluation. To evaluate we construct prediction sets according to the learned score functions on a held-out test set of Nuet points. For each point, the prediction set is constructed according to (2) using the 0, r² pair obtained from the calibration phase. In the case of the PAC- PAC-Bayes baseline, each test sample is randomly assigned to one of the pre-sampled parameter/threshold pairs. We measure the rate of coverage as well as the efficiency feft of each prediction set. We repeat the entire process from calibration and evaluation on multiple random seeds.
B.2 Illustrative example
Heteroskedastic data was generated by sampling U(-1,1), and computing the target cos(52)) + 0.3 * 61 + 1.8a (5ar)e,, where 61, 62 ~ (0-...,0,0555 and (-) 1) the sigmoid function.
The base predictor was a 2 hidden layer feedforward network with ReLU activations, with layer width of 64 neurons. We trained the network on 100 randomly sampled datapoints, and held out N new datapoints to use for calibration. In the results in the paper, for all methods we targeted = 0.1 with ô 0.05. We held the base predictor fixed, and optimize the score function
If(z) y
Soptim (2., 0)
(21)
(8,, ),(,),((, 0.)
where a is the sigmoid, and Og functions as gating parameter, and u(x;; 0) learned input- dependent uncertainty function defined as
u(E, y, 0w) = -1 + softplus(FF(z, y, 0w) + 0.6),
(22)
where FF is two-hidden layer feedforward network with tanh activations and a layer width of 128, and the softplus together with the offsets smoothly maps the output of the neural network to (approximately) R+.
For the learned model, we optimize the efficiency loss for 2000 steps with a learning rate of le-3 and a batch size of 100 samples. For the PAC-Bayes approach, we optimize using an augmented Lagrangian method, using 2000 steps of gradient descent with a learning rate of 1e-3 to solve the unconstrained penalized problem, running outer iterations in which the penalty terms are updated and the unconstrained problem is re-solved. Each round of inner optimization requires around I minute compute. In the results shown in the paper, we optimized only the prior mean μl, and held the prior variance fixed at ²² = 0.02/v / F where is the fan in for that parameter.
B.3 Corrupted MNIST
For the corrupted MNIST experiments, use 7000 images from the MNIST train split to train base predictor with the LeNet-5 architecture. For the calibration and test data, we use the held-out test split from MNIST and apply random rotation, uniform between -30 and 30 and Gaussian noise with standard deviation 1.3. We save these transformed data, and then split this data data into two disjoint subsets for the calibration and test sets respectively, using a different split for each choice of random seed. We evaluate each approach on 1000 test samples.
Here, the score function for all methods is fixed to be the negative log softmax output by the base predictor, but for the learned and PAC-Bayes methods, we consider optimizing the fully-connected portion of the network. The efficiency loss use is differentiable approximation of the output set
20

---

Data split: 0.2530.73
Dara split: 0.5020.00
Data spint 0.73.025
Steudedd Clokk 20)
Leaned (Nock 2o
Stesked (lick 20)
Leared (Nock 20o
1000
1100
2000
2000
2801
1000
2000 Boc Cuilentton Dattat (W)
1540
2001
3300
1000
1900
2000
2300
5000
Sac Culiorntio Danset (87
Ban Callernaa Dutaast (N)
Figure 5: Average prediction set size on held out test data as a function of calibration set size for different data split ratios.
Thtte silit 0:95:0
Dats split: 0,5080.5
Tata split: 0.550.0
Terget Cloezngr
Stesshed
Locaed (York
PAC-Bao
1.00
0651 CE ou collat cowtagg
Stancsed (lok 2h1
Loucadd (Yonk 2b)
6.98
631-
0.8
0.55
1530
2308
3000
.003
2000
3000
1000
2000
Callbeatioo
Uditeration Dltteet (N)
Datueer
Figure 6: Average coverage rate on held-out test data as function of calibration set size N for different data split ratios. Box plot shows variation in results over different seeds.
size. Note while the actual set-size of the resulting prediction sets is not Lipschitz continuous w.r.t. the threshold т, the smoothed loss is, Lipschitz continuous, where K is the number of classes. Here, the same optimization parameters as in the illustrative example. For the PAC-Bayes method, we initialize the prior with mean equal to the base predictor's 's original trained weights, and variance with scale 2 0.01/v F where once again, F corresponds to the is the fan_ in for the layer that the parameter is in. In the body, we report results obtained by optimizing both the prior mean and variance to minimize the efficiency objective
the sum of K sigmoid functions which are themselves
optimize the efficiency using
Do before optimizing the posterior subject to the KL constraint on Dx We found that this led to better results, as selecting the variance using the simple initialization strategy used in the illustrative example includes many & values which lead to inefficient sets, hindering the quality of the posterior that can be found within the KL. constraint.
B.3.1 Additional Results
In Figure 5, we show the complete of prediction set size calibration dataset size results, for all choices of dataset split. In general, the PAC-Bayes approach yields equal or better sets than baselines across the choice of data split. Figure shows the achieved test-time coverage rates for all methods. All methods target a generalization coverage rate of at least 1 - a = 0.9, but due to finite test set size Niest 1000, the empirical coverage rate may appear lower. We show 95% confidence intervals for the empirical mean of 1000 draws from Bernoulli random variable with probability 0.9. For our results to consistent with the desired PAC guarantee, failures would only happen the case of (a) our PAC guarantee failing to hold and the true coverage rate being lower than happen with probability less than 8, or (b) the coverage rate being higher than a but the empirical mean on the test set being lower than the 95% CI for 0.9, which should occur with probability
which should
21

---

Date rplit: 01200075
Data splin: 0,003300
Data spiit: 0,7300
Dicge: Uovenaee Bons 1-m
Standand (York Zel Scaziaan (York 21)
Learaed (York 2el
PAC-Bage
BSC CT for Now 1660
Lazzal (Vowk Zi:
0.00
D32
D:9
5000
0.28
0.00
0.32
0.56
0.00
0.88
0..00
0.92
0.00
0.50
0.35
(loorodd Coemage Bote Text
Ofterrod Clonrrgg Ratto on Teod See
Giteerve Comerage Rate tn Thet Set
Figure 7: Coverage vs efficiency plots on the MNIST experiment. There is an inherent trade-off between coverage and efficiency (larger sets inherently are more likely to contain the ground truth). Our PAC-Bayes approach consistently lies on the Pareto Frontier in these plots (high coverage and small set size).
less than 0.05. Indeed we see that all but one trial for the Learned (Vovk 2b) baseline yields an empirical coverage less than the 95% CI. We performed 30 total trials per method, so this observation consistent with our PAC guarantee and finite test-set size. We find that the PAC-Bayes method is not significantly over-conservative compared to baselines using Vovk 2a to select the empirical coverage targets. However, Vovk 2b leads to much tighter results, indicating room for improvement in PAC-Bayes results. The difference between the optimized methods and the standard ICP coverage rate is more pronounced for the 0.75:0.25 data split because the optimized method are using only quarter of the data to guarantee test time coverage, while the standard method uses the whole dataset and thus can calibrate to a lower empirical miscoverage rate å following (4).
We also visualize efficiency (prediction set size) as a function of coverage in Figure 7. Indeed, these two quantities are linked: achieving higher coverage for fixed score function requires increasing set size, coming at the cost of efficiency. The PAC-Bayes results lie on the Pareto frontier on this trade-off, highlighting that our method able to learn good score functions that yield efficient test-sets on the test set. Future work tightening the generalization bound has the potential to improve practical utility by reducing over-conservatism and allowing calibrating to lower empirical coverage levels.
In Figure we show the impact of different choices of prior optimization strategy, comparing no optimization (using the prior as initialized, using the whole calibration dataset to perform constrained optimization of the posterior) against both mean-only (μz), and mean-var (μ4, a²). As can be seen, a crude, naive strategy of arbitrarily defining a prior by choosing a fixed variance around the initialization of the weights does not work well for this problem setting, highlighting the value of using some data to tune the prior. Furthermore, fraction of the data outperforms optimizing only μ. for choices of data split.
find that optimizing both l and o² using
22

---

5.0
0.00/1.00
4.5
0.25/7.75
as.oP 0.25/00
0.50/0.50
4.0
Avenge Prodiction Sei Saz
ot 0.50/0.50
0.7550025
pl.o 0.75/00.5
3,0
2.5
2.0
1.5
1.0
1300
2000
2500
3000
Size Calibration Dataset (.)
Figure 8: Average test-time prediction set size as a function calibration set size N for different prior optimization strategies and data split between Dp and xx
23


Reviews:
[{"review_id": "9FKuMK4NzX", "reviewer": "Reviewer_jcN9", "summary": "This paper considers the setting of inductive conformal prediction (ICP). In this setting, given a learned point-predictor, a calibration set and a scoring function is used to obtain a set-valued predictor that contains the correct label with high probability. A drawback of previous approaches is that, for ICP guarantees to be valid, the scoring function has to be fixed, or part of the calibration set needs to be used to learn the scoring function, while the remaining part is used to learn the coverage sets. In order to solve this, the paper proposes to use PAC-Bayesian bounds for self-certified learning, so that the scoring function can be learned from the calibration data, while using the same calibration data to obtain test-time bounds by using generalization guarantees. The approach relies on new bounds, which are similar to known PAC-Bayesian bounds but specialized to the ICP setting, and data-dependent Gaussian priors according to a standard procedure. Numerical results demonstrate the potential of the proposed approach to improve ICP in low-data settings.\n\n\n**Post-Rebuttal edit**: I read the author rebuttal, which addressed my questions, and consequently updated the rating (as stated below).", "questions": "— Theorem 1, in terms of the binary KL, is very similar to the Maurer-Langford-Seeger bound (see, e.g., Maurer (2004)). In Maurer's result, a smaller $B(N)$ is found. However, I don't think that the two arguments of your binary KL are related by an expectation as in Maurer's derivation, which necessitates the path that you take. Is this interpretation correct? I think the paper would benefit by clarifying the relation to these classical PAC-Bayesian bounds.\n\n— The derivation of Theorem 3, once the step has been taken from $\\mathcal L$ to $R$, appears to be the same as a standard PAC-Bayesian bound via \"sub-Gaussian\"-type concentration for bounded random variables. Is there any other difference in terms of the proof?\n\n— In the introduction, you refer to PAC-Bayesian priors as data-independent, which may cause some confusion since you use data-dependent priors in your experiments. Perhaps a note should be made that they can be data-dependent in certain circumstances.\n\n---\n\nMaurer, A Note on the PAC Bayesian Theorem, 2004\n\n___\n---\n\nMinor comments:\n\nEq (5): Should this be averaged over the posterior? This is typically the case for PAC-Bayes bounds.\n\nLine 196: “for all for all”\n\nLine 197: bounuded -> bounded in footnote\n\nLine 326: “we found that optimizing the yielded a poor prior” incomplete sentence\n\nDonkser -> Donsker\n\nOverfull margins in appendix", "limitations": "Limitations are adequately discussed. Perhaps it can be made clearer that the proposed approach does not yield particularly significant improvements over the \"Learned\" baseline.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "— The paper proposes a creative and relevant use of the PAC-Bayesian framework for a practical use-case\n\n— The presentation is pedagogic, providing an essentially self-contained summary of the necessary background from ICP and PAC-Bayes\n\n— In addition to just presenting bounds, the paper suggests a well-motivated practical algorithm that is shown to have potential to improve results for certain settings. The interpretation of the PAC-Bayesian bound as providing a \"KL budget\" is neat.", "weaknesses": "— The discussion of the PAC-Bayesian bounds does not make it entirely clear what the relation to prior work is (see questions below).\n\n— The improvements that are seen in the numerical experiments appear to be marginal, and mostly within the error bars. The non-monotonicity in the order between \"Learned\" and \"PAC-Bayes\" in Figure 4 (middle) appears to highlight that they are essentially indistinguishable. Also, it was not entirely clear to me how Figure 3 demonstrated an improvement for PAC-Bayes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very thorough review and helpful comments! Below are answers to your specific questions:\n\n- *Theorem 1:* This is a great observation. Indeed, in the Maurer-Langford-Seeger bound, the two arguments to the binary KL are the empirical risk and the generalization risk: for a fixed hypothesis, the generalization risk has no dependence on the empirical risk. However, in conformal prediction, the test-time prediction sets depend on both the hypothesis (in this case, the score function) as well as the threshold, which is a function of the sampled data. Indeed, unlike typical loss functions that are defined per-datapoint, coverage and efficiency of conformal predictors depend on the threshold computed as a quantile of the entire calibration dataset. This is the key difference that precludes the direct application of a Maurer style PAC-Bayesian bound, and necessitates a different approach which yields a different B(n) term. We will more explicitly highlight these similarities and differences in our updated manuscript.\n- *Theorem 3:* Yes, our proof follows the standard steps after translating from $\\mathcal{L}$ to $R$. We will make this clear in the updated manuscript.\n- *Wording in introduction:* We agree that our original wording is a source of confusion. We will update our writing to clarify that the restriction is only that the prior is chosen independently from the data used to compute the generalization bound.\n\n*Limitations:* We will update our discussion of limitations to make clear that our approach yields modest improvements relative to the learned baseline; we will instead highlight the theoretical contributions as noted above, and the potential of the approach to become more useful with future complementary advances in PAC-Bayes literature. Finally, thank you for pointing out the small errors; we apologize for not catching these in our submission and will correct them in our updated draft. \n"}, {"review_id": "nlzja5vhVz", "reviewer": "Reviewer_kKqP", "summary": "Accurate uncertainty estimation is crucial in building robust and trustworthy machine learning systems. This paper utilizes PAC-Bayes theory and inductive conformal prediction (ICP) to develop a practical algorithm that fine-tunes parameters and score functions using calibration data, while ensuring inference coverage and efficiency. Empirical validation of this work shows that it is effective and outperforms prior methods.", "questions": "I am interested in understanding the extent to which distribution shift can affect the performance of calibration and its coverage. Adding more noise to MNIST figures can increase the level of uncertainty, making it more challenging to ensure accuracy.", "limitations": "The paper identifies various limitations and proposes practical solutions to address them. The significance of this work lies in its contribution to achieving a more reliable and secure ML system. Particularly, it demonstrates its effectiveness in providing assurance to enhance the calibration of uncertainty.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a well-executed translation from theory to practical algorithm and provides a comprehensive analysis of related work. It also discusses the practical considerations in their proposed algorithm and effectively demonstrates its ability to make efficient predictions and achieve good generalization certificates in two experiments. ", "weaknesses": "Here are some suggestions for improving the original content:\n\n1. It would be beneficial to provide more information and explanation in section 5.2 to help readers better understand the algorithm.\n2. Consider including an experiment that explores the tradeoff between desired coverage and prediction performance. This would provide valuable insights into the algorithm's effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and insightful criticisms and comments. We address specific comments below:\n- *Section 5.2:* We acknowledge that section 5.2 is a very succinct summary of the optimization approach. We will update our manuscript to go into more details of the algorithm, and add a section in the appendix which goes into more detail and reintroduces the concepts from [Stutz et al., 2022] that we re-use in our implementation to make the manuscript more self-contained.\n- *Coverage/Efficiency Tradeoff:* The coverage / efficiency tradeoff is a fundamental tradeoff for all conformal prediction approaches, and we agree that plots showing this tradeoff would be a welcome addition to the results presented in our paper. We plotted this trade-off across all dataset sizes in the attached pdf to the main response (Fig 3.), and we will include it in our updated version. Notably, while all methods see a tradeoff between coverage and efficiency, our PAC-bayes method consistently lies on the Pareto frontier. \n- *Distribution Shifts:* Indeed, distribution shifts can have an impact on calibration. Prior work evaluating uncertainty quantification under distribution shift has demonstrated that neural network uncertainty estimates can struggle to generalize as the data distribution is shifted [1]. Indeed, for this reason, we chose a distribution shift example to study our approach: While a network trained on clean MNIST does produce heuristic uncertainty estimates (through its predicted class probabilities), these estimates are unlikely to generalize well to corrupted data. Hence, if we have a limited amount of data from the test (shifted) domain, we would like to ideally use this data to both tune the network to produce better uncertainty signals as well as to produce calibrated uncertainty sets, as directly using the untuned network could yield loose prediction sets. \nNow, a separate challenge is handling distribution shift *after* the calibration procedure. Robustifying standard conformal prediction to future distribution shift is an active area of research [2], as is literature extending PAC-Bayes to settings where the test-data distribution differs from the training data distribution [3]. We considered this challenge to be out-of-scope for this work, but we wholeheartedly agree that this is an important problem and a worthwhile direction for future extensions of this work.\n\n [1] Ovadia, Yaniv, et al. \"Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift.\" Advances in neural information processing systems 32 (2019).\n\n [2] Tibshirani, Ryan J., et al. \"Conformal prediction under covariate shift.\" Advances in neural information processing systems 32 (2019).\n\n [3] Germain, Pascal, et al. \"A new PAC-Bayesian perspective on domain adaptation.\" International conference on machine learning. PMLR, 2016.\n"}, {"review_id": "FcY0lUAphF", "reviewer": "Reviewer_Akhh", "summary": "The efficiency of set-valued predictor is crucial and less explored, this paper use the framework of PAC-Bayes to obtain the generalization bounds on both the coverage and the efficiency of set-valued predictors. The authors also propose a novel algorithm to optimize the efficiency without a separate hold-out dataset. They provide a theoretical guarantee for the proposed method and empirically verify the superiority of the proposed method.", "questions": "Please see the weaknesses.", "limitations": "A limitation of this paper is that the theoretical results and proposed method can only be applied for a stochastic model.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper uses the framework of PAC-Bayes to analyze the efficiency of inductive conformal prediction, which is novel and less explored.\n- The algorithm proposed by this paper does not require a separate hold-out dataset, while still having a theoretical guarantee of coverage.\n- This paper is well organized and the presentations are clear to me.", "weaknesses": "- To achieve the test-time coverage, the key constraint is shown in Corollary 2.1. However, the authors do not show whether it is satisfied in the experiments. \n- In the experiments, the authors show the average size of the prediction set, but I think the marginal coverage evaluated on the test data in the experiments is also important, and does a smaller average size of the prediction set empirically lead to worse coverage?\n- In the experiments, the description of the ***learned*** baseline is unclear. Do the authors train the model using the method proposed in [1]? Meanwhile, the authors miss a recent work [2] that aims to output a smaller conformal prediction set with higher conditional coverage. [1] and [2] should be chosen as baselines in the experiments.\n\n[1] David Stutz, Krishnamurthy Dvijotham, Ali Taylan Cemgil, Arnaud Doucet. Learning Optimal Conformal Classifiers. ICLR 2022.\n\n[2] Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, Yanfei Zhou. Training Uncertainty-Aware Classifiers with Conformalized Deep Learning. NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed feedback. We address your questions below:\n- *Constraint Satisfaction:* The constrained optimization solver we use in our experiment ensures that solutions satisfy Corollary 2.1 by construction. In particular, we solve the constrained optimization problem with an augmented Lagrangian algorithm (approximating the inner optimization with stochastic gradient descent), and only return a solution if it is feasible (i.e., if the solution satisfies Corollary 2.1). We will clarify this in the updated manuscript, and include results on constraint values in the appendix.\n- *Coverage results:* We focused on presenting efficiency results because all approaches yielded similar coverage values that exceeded the desired value; however, we did include marginal coverage results in the supplementary material – we will update the main paper to highlight that these results are included in the appendix. We agree that the relationship between test-time coverage and test-time efficiency is interesting, and we will include these results (shown in the attached pdf, Fig. 2) in the updated version of the manuscript.\n- *Learned baseline:* Indeed, the learned baseline is a reimplementation of ConfTr [Stutz et al, 2022], extended to the regression case by using the radius of the prediction set as an efficiency loss. We will make this more clear in the updated version of the manuscript. We also thank the reviewer for pointing out the work of [Einbinder et al, 2022] – we will update our related work section to discuss it. Indeed, they tackle a similar problem as [Stutz et al, 2022] of training ML models to yield efficient sets after conformalization; however, their approach is limited to a specific nonconformity function designed for classification. In contrast, our work (as well as [Stutz et al, 2022]) works with any nonconformity function and extends beyond classification problems. For this reason, we cannot directly compare against [Einbinder et al, 2022] in our experiments.\n"}, {"review_id": "QVcsurYbUG", "reviewer": "Reviewer_6Bn9", "summary": "This work first derives coverage and efficiency generalization bound using PAC-Bayes for inductive conformal prediction. Furthermore, a practical algorithm, basing bayesian learning and conformal training, is proposed to learn efficient nonconformity score functions. In experiment section, the proposed algorithm is shown to outperform two baselines (original ICP and learned ICP) in some scenarios.", "questions": "1, How are the two derived bounds connected to the proposed algorithm?", "limitations": "1, The computation complexity might be so high that the proposed method cannot trivial extend to larger datasets and models.\n2, Without good prior, the derived bounds might be too loose.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1, This work is mathematically solid, by combining PAC-Bayes theory with inductive conformal prediction. Particularly, it derives a efficient loss bound using PAC-Bayes for ICP. \n2, In the experiment section, the proposed method outperforms other two baselines (original ICP and learned ICP) in many scenarios, demonstrating high efficiency, especially when limited calibration data is available.\n3, The manuscript is well-written; and proposed method is mathematically sound.", "weaknesses": "1, In the abstract, it is claimed that \"the entire calibration dataset\" can be utilized. In the practical algorithm, splitting the calibration dataset is still needed (to derive a good prior). As a result, in my opinion, the mentioned claim is at least controversial.\n2, Though not mentioned, the proposed algorithm could be expensive in training and inference, as multiple models need to be sampled.\n3, The empirical evaluation is insufficient. Only one synthetic dataset and one practical dataset are used. It would be appreciated if experiments on more practical datasets. With more empirical results, it could be more convincing to claim that the proposed method produces more efficient prediction sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful and helpful comments. We address your criticisms and questions below:\n- *Data-splitting:* As you point out, in the experiments we split the data, using part of it to tune the prior, and the rest to simultaneously tune the posterior and also achieve test-time coverage guarantees. However, both splits of data are used to optimize the score function. This is in contrast to prior work in learned conformal prediction, which optimizes the score function on one set of data, and then holds it fixed when using the remainder to compute the threshold needed to achieve test-time coverage guarantees. \n- *Sampling multiple models:* Indeed, PAC-Bayes style generalization bounds require reasoning over stochastic models rather than individual hypotheses. However, at test time, each data point is only evaluated under a single model: test-time computational complexity at a single-sample level is therefore similar to a non-stochastic approach. Indeed, our guarantee on test-time coverage holds in expectation over samples drawn from the posterior and data drawn from the data distribution, so as long as each new input is evaluated using a new sample, our guarantee holds. However, one important limitation is that we require recomputing the threshold $\\tau$ for each new sample. For small calibration sets and models, this can be done in parallel at test time. Alternatively, one can pre-sample K models from the posterior, and use the calibration data to pre-compute the threshold $\\tau$ for each sample. This offloads the computational burden from test-time evaluation, but adds to the memory burden, as multiple samples of model parameters need to be stored. We will emphasize this limitation in the updated manuscript and more clearly discuss this tradeoff.\n- *Empirical evaluation:* We believe the core of this paper is our theoretical contributions. In particular, in contrast to standard ML settings where the loss is defined per-datapoint, in conformal prediction, the efficiency and coverage on a particular data point depends on the threshold, which itself is computed as a function of the entire calibration dataset. This dependency precludes direct application of standard PAC-Bayes proofs, and requires a novel theoretical approach, which we consider the main contribution of our work. As such, while we agree that more experiments would always be better, we would like to stress that our goal in the empirical evaluation was not to demonstrate the immediate practical applicability of this approach, but rather to highlight the potential of our theoretical contributions. We believe our experiments demonstrate that our approach can already yield modest benefits in terms of efficiency in the low-data regime, and these benefits have the potential to become more pronounced thanks to future advances in the tightness of PAC bounds and advances in prior and posterior selection. \n- *How are generalization bounds used?* We produce two main generalization bounds. The bound on coverage (Theorem 1) is used to derive Corollary 2.1, which is used directly in the algorithm to compute the KL budget allowed for optimizing the posterior as a function of the desired test-time coverage guarantee. The bound on efficiency (Theorem 2) is used to select between different hyperparameter settings: we choose the model with the best bound on generalization efficiency among K hyperparameter choices. In our experiments, we evaluate these bounds using $\\delta’ = \\delta/K$, ensuring through a union bound argument that the generalization bounds hold for the best-performing model with probability greater than $1-\\delta$.\n"}, {"review_id": "jMQPZ8PHlc", "reviewer": "Reviewer_XWYk", "summary": "Inductive Conformal Prediction (ICP) provides a coverage guarantee of constructed prediction sets, while does not provide any guarantee on the efficiency of prediction sets. The efficiency depends on a conformity score function, and direct approaches optimize the score function to minimize the efficiency of prediction sets in two steps: (1) given a hold-out set from a calibration set, optimize the score function, and (2) given another hold-out set from a calibration set, run an ICP algorithm. However, the direct approaches do not provide a generalization guarantee for efficiency. The proposed approach combines ICP and the PAC-Bayes to provide generalization guarantees for both coverage and efficiency. In particular, the paper provides novel generalization bounds for coverage and efficiency and proposes an algorithm from them, where the efficacy is evaluated on regression and image classification problems.", "questions": "Each question is associated with each weakness in Weaknesses.\n\n1. What is the algorithmic benefit of the efficiency bound in Thm2?\n2. If the authors use the tiger PAC-style ICP (i.e., Proposition 2b in Vovk [2012]), would “the standard ICP” and “a learned ICP” baselines be possible to be better than the proposed approach in Figure 4? \n3. Could you clarify on the benefit of PAC-Bayes in achieving an efficient prediction set?\n4. If the authors use the variance normalized score function, do we still observe the same limitation of “the standard ICP” in Figure 3?\n", "limitations": "The limitations are clearly stated in Conclusion, and I agree with that. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**Originality**: The paper proposes new generalization bounds on coverage and efficiency. \n\n**Quality**: The proposed algorithm is supported by theorems, making the algorithm rigorous. \n\n**Clarity**: I like the paper structure. It first provides the main theories, and then explains an algorithm with practical details (appreciate it). \n\n**Significance**: I believe the PAC-Bayes interpretation introduces an interesting, novel view on conformal prediction, which could trigger interesting CP algorithms. \n", "weaknesses": "Combining PAC-Bayes and ICP is very interesting, though I have a few concerns. \n\n1. It is not easy to find the benefit of the bound on efficiency (i.e., Thm2). This is novel, but in Algorithm 1, it also uses the first term of (8). What is the algorithmic benefit of the efficiency bound Thm2?\n2. I assume that this paper uses the PAC-style ICP (4) as the baselines (i.e., “the standard ICP approach” and “a  learned ICP approach”. However, (4) is known to be loose (as clearly mentioned in Vovk [2012]. In the same Vovk’s paper, it also has a tighter ICP (i.e., Proposition 2b in Vovk [2012]) and its tightness (and efficiency) is also well-demonstrated in deep learning applications in [R1]. If the authors use the tiger PAC-style ICP, would “the standard ICP” and “a learned ICP” baselines be possible to be better than the proposed approach in Figure 4? \n3. It is unclear what the benefit of PAC-Bayes is in achieving an efficient prediction set. Based on Line 50 (i.e., “our framework allows us to utilize the entire calibration dataset…”), I initially thought that the proposed approach fully utilizes the calibration set (while direct approaches require splitting calibration sets into two). However, the proposed approach also needs to split the calibration sets for prior learning (i.e., Line 238). At this point, I was unsure of the benefit of combining PAC-Bayes with ICP. My guess is simultaneous optimization of a score function distribution Q and threshold \\hat{tau} is one factor for achieving a better efficiency than the baselines, but I want to hear the author's clarification. \n4. The nonconformity score function of the standard ICP in regression is quite weak, which misleads readers. The score function with only the residual (i.e., Line 282) is not recommended as it does not encode per sample uncertainty (as also mentioned in the paper). Instead, a variance normalized score function (i.e., (8) in [R2], 3.6 in [R1], or 2.2.1 in [R3]) is a better choice, where the variance is simply trained via a training set. Given this better score function, I don’t think “the standard ICP” result in Figure 3 is as poor as shown in the paper. \n\n\n[R1] https://arxiv.org/abs/2001.00106\n\n[R2] http://proceedings.mlr.press/v91/vovk18a/vovk18a.pdf\n\n[R3] https://arxiv.org/abs/1612.01474\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback. We address each of your questions below:\n- *Efficiency bound (Theorem 2):* As you noted, we don’t directly optimize the generalization bound in Theorem 2 in our algorithm. This is due to the fact that the optimizable part of the second term in (8) is just the KL divergence, and the coverage constraint already regularizes the KL value. We found that in practice, optimizing through the bound did not improve performance, and excluding it led to a simpler algorithm. However, we did use the generalization bound when comparing between hyperparameter settings, reporting test-time results on only the hyperparameters that achieved the best generalization bound according to Theorem 2. We use a union bound argument, using $\\delta’=\\delta / K$ when evaluating bounds, where K is the number of hyperparameter choices. \n- *Vovk Prop 2b*: First, we note that the mapping from our notation to that in [Vovk 2012] is $\\delta \\rightarrow \\delta, \\hat{\\alpha} \\rightarrow \\epsilon$, and $\\alpha \\rightarrow E$. We will use our notation to discuss comparisons between our choices and those in Vovk 2012. \n\n  - Indeed for the learned and standard ICP baselines in our experiments, we follow the recommendation of [Vovk 2012] and use the result of Prop 2a as a recipe to construct a $(\\alpha, \\delta)$-valid conformal predictor. Specifically, given $\\alpha$ and $\\delta$, this recipe involves constructing a set predictor to achieve $1-\\hat{\\alpha}$ coverage on the calibration dataset, where $\\hat{\\alpha} = \\alpha - \\sqrt{(-\\ln \\delta)/(2n)}$. Then, we apply Prop 2b once using the chosen $\\hat{\\alpha}$ and $\\delta$ to guarantee $(\\alpha,\\delta)$-validity of the resulting predictor. \n\n  - We implemented the Prop 2b bound and used it similarly to [R1] to find the largest $\\hat{\\alpha}$ for which the equation in Prop 2b holds for our desired $\\alpha$ and $\\delta$, and include the results in the attached pdf under the label (Vovk 2b). While the less conservative $\\hat{\\alpha}$ leads to tighter prediction sets, empirically we find that the coverage guarantee is violated, especially for the learned version. Indeed, applying a binomial test on the rate of test-time coverage violation for the Learned (Vovk 2b) trial evaluated on N=2500 calibration datapoints split at a ratio of 0.5/0.5 over 6 independent seeds, we obtain a p-value of 0.0327 for the null hypothesis that the probability of failure (coverage < $1- \\alpha = 0.90$) is less than $\\delta=0.05$, indicating we should reject the null hypothesis that the coverage guarantee is valid for this trial. We are investigating the reason for this discrepancy, to identify if there is an aspect of our approach which breaks the assumptions required by Prop 2b. In any case, we thank the reviewer for highlighting this tighter bound, and we will investigate if a similar tightening can be translated to a PAC-Bayes analysis.\n\n- *Benefit of PAC-Bayes:* Prior works learning score functions for conformal prediction use only a portion of the calibration dataset to optimize the score function to achieve good efficiency in prediction sets whose threshold $\\tau$ is computed on the same portion of the calibration dataset. However, especially in the low-data regime, this can lead to cases where the score function over-fits to the portion of calibration data – then, when recalibrating the model (i.e. re-computing the threshold $\\tau$ on the remaining portion of the dataset), the score function may behave erratically, leading to a different $\\tau$ value and potentially worse efficiency. In contrast, the PAC-Bayes approach allows further optimization of the score function on the second part of the dataset. In this way, it can mitigate the impacts of overfitting in the low-data regime.\n- *Variance-normalized score function:* Our aim in this work is to address situations where calibration data faithfully representing test-time conditions is limited, and one may want to simultaneously fine-tune models on this data while also producing calibrated prediction sets. To illustrate this set-up in a simplified illustrative example, we considered a (synthetic) example, where the pretrained model did not produce variance outputs, but the heteroskedasticity in the calibration dataset was information, which, if effectively incorporated, could lead to more efficient prediction sets. Our goal with the illustrative model was not to demonstrate the real-world use of the method, but rather to highlight that our approach can more effectively learn new concepts and produce calibrated prediction sets from a limited set of calibration data. While in practice, training a model to produce variance outputs would yield tighter prediction sets to begin with, this would not illustrate the utility of further fine-tuning a model on calibration data. Indeed, the utility of this approach is highest when calibration data is a scarce resource, e.g., when we only have a limited set of samples from a shifted test data-distribution. We will make this point clearer in the revision.\n"}]

Author rebuttal:
We would like to thank the reviewers for their time and valuable feedback on our manuscript. We are glad the reviewers all found our paper clear, sound, and well-structured. Furthermore, we are glad to hear that the reviewers appreciated the novelty of our approach in applying PAC-Bayes generalization bounds to the setting of conformal prediction. 

First, we would like to emphasize that our primary goal, as reviewer jcN9 highlighted, is to make a theoretical contribution which allows **self-certified learning of conformal predictors**. Indeed, all prior work on optimizing conformal predictors using data required heuristically splitting data and using part of the data to tune the model and score function parameters, and the rest to compute the threshold needed to achieve the desired test-time coverage guarantees. Our work uses PAC-Bayes generalization theory to show that data-splitting is **not** strictly required to achieve test-time coverage: instead, a coverage guarantee can be achieved by constraining the data-driven optimization in terms of KL divergence to a prior. We would like to reiterate that these results are novel, and more than a direct application of standard PAC-Bayes results: unlike typical loss functions which are defined per-datapoint, the coverage and efficiency of the prediction for a single input depend on the entire calibration dataset, since the threshold defining the prediction sets is computed as an empirical quantile. Handling this required novel extensions to classical PAC-Bayes theory.

Next, we would like to address shared concerns regarding the empirical evaluation of our practical algorithm. Many reviewers pointed out that in our evaluation, we considered using a portion of the available data to first optimize a prior, before then performing a second phase of optimization wherein we retain generalization guarantees on coverage and efficiency by enforcing a KL constraint to the (learned) prior. Indeed, as we state in the paper, this is a common practice for many works applying PAC-Bayes techniques to neural network models: while generalization bounds on loss are valid for any fixed prior, state-of-the-art methods achieving generalization performance competitive with empirical risk minimization (ERM) often use a portion of data to tune a prior [1,2]. Admittedly, this has the consequence of reducing the data that is used to compute the threshold for the conformal prediction sets. Nevertheless, we would like to stress that, in contrast to the data-splitting employed in the learned ICP baseline (and prior works), our approach uses **all** available data to optimize the score function and model parameters, while existing approaches only optimize parameters on one fraction of the dataset. Specifically, we use the first part to optimize the prior for the score function, and then use the second part to optimize the posterior. Earlier data-splitting techniques hold the score function fixed in the second step. Finally, we believe that future advances in applying PAC-Bayes to neural networks, both in terms of prior selection as well as posterior representation, will be complementary to the techniques in our paper and help enhance the practical utility of the algorithm.

Overall, we believe our core theoretical contributions are novel, and of interest to the broader NeurIPS community. Furthermore, we believe our experiments demonstrate that even with a very restrictive class of prior and posterior (diagonal Gaussian), our theoretical contributions yield an algorithm for learning conformal predictors which yields efficient prediction sets in practice and guaranteed test-time coverage, demonstrating the potential of the approach to be useful in the low-data regime. We refer the reviewers to our individual responses for response to other questions raised in the reviews.

[1] Ambroladze, Amiran, Emilio Parrado-Hernández, and John Shawe-Taylor. "Tighter pac-bayes bounds." Advances in neural information processing systems 19 (2006).
[2] Perez-Ortiz, Maria, et al. "Learning PAC-Bayes priors for probabilistic neural networks." arXiv preprint arXiv:2109.10304 (2021).

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions to the PAC-Bayes theory applied to conformal predictors. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers. Congratulations!
Decision: Accept (poster)