Efficient and Differentiable Conformal Prediction with General Function Classes
Authors: Yu Bai
Song Mei
Huan Wang
Yingbo Zhou
Caiming Xiong
Venue: ICLR 2022 Poster (2022)
Keywords: uncertainty quantification
conformal prediction
prediction sets

Abstract:   Quantifying the data uncertainty in learning tasks is often done by learning a prediction interval or prediction set of the label given the input. Two commonly desired properties for learned prediction sets are \emph{valid coverage} and \emph{good efficiency} (such as low length or low cardinality). Conformal prediction is a powerful technique for learning prediction sets with valid coverage, yet by default its conformalization step only learns a single parameter, and does not optimize the efficiency over more expressive function classes.
  In this paper, we propose a generalization of conformal prediction to multiple learnable parameters, by considering the constrained empirical risk minimization (ERM) problem of finding the most efficient prediction set subject to valid empirical coverage. This meta-algorithm generalizes existing conformal prediction algorithms, and we show that it achieves approximate valid population coverage and near-optimal efficiency within class, whenever the function class in the conformalization step is low-capacity in a certain sense. Next, this ERM problem is challenging to optimize as it involves a non-differentiable coverage constraint. We develop a gradient-based algorithm for it by approximating the original constrained ERM using differentiable surrogate losses and Lagrangians. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly over existing approaches in several applications such as prediction intervals with improved length, minimum-volume prediction sets for multi-output regression, and label prediction sets for image classification.

Published as a conference paper at ICLR 2022
EFFICIENT AND DIFFERENTIABLE CONFORMAL PRE- DICTION WITH GENERAL FUNCTION CLASSES
Yu Bai
Song Mei UC Berkeley songmei @berke edd:
Salesforce Research yu.bal @sa esforce.com
Huan Wang & Yingbo Zhou & Caiming Xiong
Salesforce Research
{huan. wang, yingbo. zhou, exicng]@salesfooree.c com
ABSTRACT
Quantifying the data uncertainty in learning tasks often done by learning a pre- diction interval or prediction set of the label given the input. Two commonly desired properties for learned prediction sets are valid coverage and good effi- ciency (such as low length or low cardinality). Conformal prediction is power- ful technique for learning prediction sets with valid coverage, yet by default its conformalization step only learns single parameter, and does not optimize the efficiency over more expressive function classes.
In this paper, we propose a generalization of conformal prediction to multiple learnable parameters, by considering the constrained empirical risk minimization (ERM) problem of finding the most efficient prediction set subject to valid em- pirical coverage. This meta-algorithm generalizes existing conformal prediction algorithms,, and we show that it achieves approximate valid population coverage and near-optimal efficiency within class, whenever the function class in the con- formalization step is low-capacity in certain sense. Next, this ERM problem is challenging to optimize as it involves a con-differenttable coverage constraint. We develop a gradient-based algorithm for by approximating the original con- strained ERM using differentiable surrogate losses and Lagrangians. Experiments show that algorithm is able to learn valid prediction sets and improve the efficiency significantly over existing approaches in several applications such as prediction intervals with improved length, minimum-volume prediction for multi-output regression, and label prediction sets for image classification.
INTRODUCTION
Modern machine learning models can yield highly accurate predictions in many applications. As these predictions are often used in critical decision making, it increasingly important to accompany them with uncertainty quantification of how much the true label may deviate from the prediction. A common approach to quantifying the uncertainty in the data is to learn prediction ser-a set- valued analogue of usual (point) predictions-whin which outputs subset of candidate labels instead of single predicted label. For example, this could be prediction interval for regression, or discrete label set for multi-class classification. A common requirement for learned prediction sets is that should achieve valid coverage, i.e. the set should cover the true label with high probability (such as 90%) on a new test example (Lawless & Fredette, 2005). In addition to coverage, the prediction set is often desired to have good efficiency, such as a low length small cardinality (Lei et al., 2018; Sadinle et al., 2019), in order for to be informative. Note that coverage and efficiency typically come trade-off, as it is in general more likely to achieve better coverage using larger set.
This paper is concerned with the problem of finding the most efficient prediction set with valid coverage. Our approach builds on conformal prediction (Vovk al., 2005), powerful framework for generating prediction sets from (trained) base predictors with finite-sample coverage guarantees.
Code available https: //tg////ttttt///t com/ al Tenbai 01/ 00/cp-gee

---

Published as a conference paper at ICLR 2022
Vanilla conformel
CP-Gen Larger class (Cac)
Class (C)
0.7
Coverage
0.5
0.3
0.1
0.5
Lendcy))
Len(Cros)
LaniCa
Length
Length
Figure 1: Comparison of vanilla conformal prediction and our CP-Gen for learning a prediction interval with 90% nominal coverage on a real-world regression task. Left: The function class {Ct the prediction intervals used by Conformalized Quantile Regression. Right: {Ca,s) is larger class of intervals used by our conformal quantile finetuning procedure with the same base predictor; here the additional trainable parameter 0 the last linear layer within the quantile neural network (cf. Section 5.1 and Appendix E.3 for more details).
Conformal prediction has been used for learning prediction sets in a variety of tasks in regres- sion (Lei & Wasserman, 2014; Lei al., 2018; Romano et al., 2019), classification (Cauchois al., 2020b; Romano et al., 2020; Angelopoulos et al.. 2020), structured prediction (Bates et al., 2021), and so on. However, the conformalization step in conformal prediction by default does not offer the flexibility for optimizing additional efficiency metrics, as the efficiency is already determined by the associated score function and the target coverage level. As concrete example, the Conformalized Quantile Regression algorithm learns single width adjustment parameter that turns two-sided quantile predictor into a prediction interval of valid coverage (Romano et al., 2019); however, does not offer way of further optimizing its length (cf. Figure Left).
For certain efficiency metrics and prediction tasks, several approaches have been proposed, for ex- ample by designing better score function (Angelopoulos et al., 2020), using base predictors of specific form (Izbicki et al., 2019; 2020; Sadinle et al., 2019), or selecting a best training hyperpa- rameter (Yang & Kuchibhotla, 2021). However, optimizing the efficiency for more general tasks or efficiency metrics still largely requires "manual" efforts by the researcher, as it (1) often relies on specific domain knowledge about the task hand: (2) is often done in conjunction with confor- mal prediction in multiple rounds of trial-and-error; (3) is often done by reasoning about high-level properties of the efficiency loss and coverage constraints (e.g. what makes the length short), but not by directly optimizing the knowledge, there lack of more principled and unified approach for optimizing any efficiency metric subject to valid coverage over any class of prediction sets.
trade-off in data- dete-depnndnnt way. To the best of our
In this paper, we cast the above task as a constrained empirical risk minimization (ERM) problem of optimizing the efficiency subject to the coverage constraint, over any general function class of prediction sets with potentially multiple learnable parameters. This is motivated by simple obser- vation that vanilla conformal prediction is already equivalent to solving such constrained ERM with one learnable parameter (Section 2.1). Overall, our algorithm can be viewed as an automatic and data-dependent approach for optimizing the efficiency simulatncously with conformal predic- tion. Our contributions are summarized as follows.
We propose CP-Gen (Conformal Prediction with General Function Class), a generalization of conformal prediction to learning multiple parameters. CP-Gen selects within arbitrary class of prediction sets by solving the constrained ERM problem of best efficiency subject to valid empirical coverage (Section 3.1), and is systematic extension of existing algorithms.
We show theoretically that CP-Gen achieves approximately valid coverage and near-optimal ef- ficiency within class, whenever the class is low-capacity with respect to both the coverage and the efficiency loss (Section 3.2, with concrete examples in Appendix C). We also provide a prac- tical variant CP-Gen-Recal using data splitting and reconformalization, which achieves exact coverage, as well as good efficiency under additional assumptions (Section 3.3).
To address the issue that CP-Gen and CP-Gen-Reod involve non-differentiable coverage constraint, we develop a differentiable approximation using surrogate losses and Lagrangians (Section 4). This allows to solve the constrained ERM problem over higher-dimensional con- tinuous parameter spaces via gradient- based optimization, and is more flexible than existing al- gorithms that require discretization and brute-force search.
2

---

Published as a conference paper at ICLR 2022
We empirically demonstrate that CP CP-Cen-Recal with our gradient- pradientbbased implementation can learn prediction sets with valid coverage and significantly improved efficiency on three real-data tasks: prediction intervals for regression with improved length, mainimum-volume prediction sets for multi-output regression, and label prediction sets for ImageNet (Section 5 & Appendix F).
We illustrate our main insight via the coverage ve-fffciiey trade-off plots in Figure 1: While vanilla conformal prediction only learns a single parameter (within its conformalization step) by a simple thresholding rule over coverage-efficiency curve, our CP is able to further improve the efficiency by thresholding a region formed by larger function class.
1.1 RELATED WORK
Learning prediction sets via conformal prediction The framework of conformal prediction for learning prediction sets originated the early works of (Vovk et al., 1999; 2005; Shafer & Vovk, 2008). The main advantage of conformal prediction is that it yields (marginal) coverage guarantees regardless of the data distribution (i.e. distribution-freet been applied to variety of uncertainty quantification tasks, such as prediction intervals for regres- sion (Papadopoulos, 2008; Vovk, 2012: 2015; Lei & Wasserman, 2014; Vovk et al., 2018; Lei et al., 2018; Romano al., 2019; Izbicki et al., 2019; Guan, 2019; Gupta al., 2019; Kivaranovic al., 2020; Barber et al., 2021; Foygel Barber et al., 2021), label prediction sets for classification problems (Lei et al., 2013; Sadinle al., 2019; Romano al., 2020; Cauchois al., 2020b;a; Angelopoulos et al., 2020), and prediction sets for structured output (Bates et al., 2021).
More recently, conformal prediction has
Optimizing efficiency in addition to valid coverage The problem of finding a prediction set with (approximate) valid coverage and small size has been considered, e.g. in Pearce et al. (2018); Chen al. (2021) for regression and Park et al. (2019) for classification; however, these approaches do not use conformal prediction. Yang & Kuchibhotla (2021) propose to minimize the length of the confor- mal interval over either finite class or a linear aggregation of base predictors, and provides coverage and efficiency guarantees. All above works formulate this task as risk minimization problem, yet are restricted to considering either finite classes or specific efficiency loss functions. Our work inspired by (Yang & Kuchibhotla, 2021) and generalizes the above works by allowing any function class and efficiency loss, along with providing a differentiable approximate implementation.
The problem of optimizing the efficiency can also be done by utilizing structures of the particular efficiency loss to choose a specific base predictor and an associated prediction set (Lei & Wasserman, 2014: Sadinle et al., 2019; Izbicki et al., 2019; 2020). By contrast, approach does not require either the efficiency loss or the base predictor to possess any structure, and is thus complementary.
Other algorithms and theory An alternative line of work constructs prediction intervals / predic- tion sets by aggregating the prediction over multiple base predictors through Bayesian neural net- work (Mackay, 1992; Gal & Ghahramani, 2016; Kendall & Gal, 2017; Malinin & Gales, 2018; Mad- dox et al., 2019) or ensemble methods (Lakshminarayanan et al., 2016; Ovadia et al., 2019; Huang al., 2017; Malinin al., 2019). However, these methods do not typically come with (frequentist) coverage guarantees. The recent work of Hoff (2021) studies ways of enhancing Bayes-optimal pre- diction with frequentist coverage. Prediction intervals can also be obtained by parameter estimation using a parametric model for the data (Cox, 1975; Bjornstad, 1990; Beran, 1990; Barndorff- & Cox, 1996; Hall et al., 1999; Lawless & Fredette, 2005); see (Tian et al., 2020) for review. How- ever, the coverage of such prediction intervals relies heavily on the parametric model being correct (well-speeified), and can even fail in certain nigh-dimensional regimes where the model is indeed correct (Bai et al., 2021).
2 PRELIMINARIES
Uncertainty quantification via prediction sets We consider standard learning problems which we observe a dataset D of examples (z4, Wi) E X x y from some data distribution, and wish to predict the label y from the input x. A prediction set is a set-valued function C : X + 2 where regression ()) RR in which we can choose C(x) C R as a prediction interval, and (multi-class) classification () = [L] == {1...., L}) in
C(x) is subset of y. Two prevalent examples
which we can choose C(x) C [T.] as (discrete) label prediction set.
3

---

Published as a conference paper at ICLR 2022
Coverage and efficiency The (marginal) coverage probability (henceforth coverage) of predic- tion set C' is defined as
Coverage(C)) == P(Y C(X))
where (X, is a test example from the same data distribution. We also define the (mieerco loss Leoverage (C) := Coverage(C) = P(Y & () A learned prediction set is often desired to achieve valid coverage in the sense that Covorago C*) 2 a for some a E (0. 1). Here - a pre-determined target coverage level; typical choices are e.g. a (90%, 95%], which corresponds to picking a E 0.05).
In addition valid coverage, it is often desired that the prediction set has good efficiency (such as small size). This is motivated by the fact that valid coverage can be achieved trivially if we do not care about the size, e.g. by always outputting C y, which is not informative. Throughout this paper we will use left to denote the particular efficiency loss we care about, where let (C; (x, y)) measures the efficiency loss of C' on an example (az, y), such as the length (Lebesgue measure) of prediction intervals, or the size (cardinality) of label prediction sets.
Nested set framework We adopt the nested set framework of (Gupta et al., 2019) for convenience for our presentation and analysis. A family
is said to be (family of) nested sets if t < t' implies that (z) C (x) for all x E X. Throughout this paper out notation C2 or Co. are assumed to be nested sets with respect t. We assume that our efficiency loss let is non-decreasing w.r.t. its (set-valued) argument, i.e. Lan (C; ()) S (Cn(C'; (x. if C S C². Therefore, for nested sets the loss + Len (z. y)) non-decreasing I(C,) P(Y & (X)) (and its empirical version) is instead non-increasing in I, the efficiency loss and the coverage loss always comes as trade-off.
As the coverage loss
2.1 CONFORMAL PREDICTION
Conformal prediction (Vovk et al., 2005; Lei & Wasserman, 2014) is powerful technique for learn- ing prediction sets with coverage guarantees. The core of conformal prediction its conformaliza- tion step, which turns any base prediction function (or training algorithm) into prediction set.
We here briefly review conformal prediction using the vanilla (split) conformal regression method of (Lei et al., 2018), and refer the readers to (Angelopoulos & Bates, 2021) for more examples. Given any base predictor f : X + R (potentially learned on a training dataset Dtrain), conformal prediction outputs prediction interval
C=(x)= -1, + +7],
(I)
where f Rzg is chosen the (1 a) au-qunntile'' of ly - f(x) on calibration dataset Deal with size Teall = [Deal using the following conformalization step:
f= [(1 - ammm.ai -th largest of flu-- - fzx)) Recd
(2)
The main guarantee for the learned interval Cj that it achieves a (1 a) coverage guarantee of the form P (x E C;(X)) > 1 - (Lei et al., 2018, Theorem 2.2). The proof relies on the exchangeability between the scores (lv: (x:))) and ((X),, which allows this guarantee to hold in a distribution- -ree fashion (i.c. for any data distribution).
Conformal prediction as constrained ERM with one parameter We start by simple re- interpretation that the conformalization step (2) is equivalent to solving constrained empirical risk minimization (ERM) problem with a single learnable parameter / (cf. Appendix A for the proof).
Proposition (Conformal regression as constrained ERM with one learnable parameter). The parameter T E R defined in (2) is the solution to the following constrained ERM problem
minimize Leff (Ct) Teall DeDaa
Σ (ot (1)) = 2t
(20
subject to Leoverogo (Ct) Neal
Σ DEDaa
1l6 k $ C+(zi)) aa
'Technically (2) requires the [(1 -0) () 1)]-th largest element to guarantee valid coverage (Vovk al., 2005); here we choose the close [(1 a Me)rrcall |th largest allow the following insight.
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 Conformal Prediction with General Function Class
Input: Class of prediction sets C
target miscoverage level (0, 1); Eo 2 0.
Efficiency loss lett: Calibration dataset Deal with size Teall
1: Solve the following constrained ERM problem on dataset Deal (with relaxation parameter Eo):
(0,7)
arg min (etr(Co 0EB,ET
1
E
Lott (Cup(CC.()))):.))
Theal iEDaal
(5)
subject to Zeoverage(Caa neal DeDial
E
Hm & Co,( S E0.
Output: Prediction set Cp.7-
Above, lett (C; (z, y)) length(C((x)) is the length of the interval C(z).
Though simple, this re-interpretation suggests limitation the conformalization step (2) as well as its analogue in other existing conformal methods: It only learns single parameter f, and thus cannot further optimize the efficiency due to the coverage-effiiincc trade-off (cf. Figure 1). However, the form of the constrained ERM problem (3) suggests that it can be readily extended to more general function classes with more than one learnable parameters, which the focus of this work.
3 CONFORMAL PREDICTION WITH GENERAL FUNCTION CLASSES
3.1 ALGORITHM
Our algorithm, Conformal Prediction with General Function Classes (CP-Gen; full description in Algorithm 1), is an extension of the constrained ERM problem (3) into the case of general function classes with multiple learnable parameters. CP-Gen takes in function class of prediction sets
C= (z) 0 T
(4)
where (as mentioned) assume that {Co.t is nested set for each 9 E O. The parameter set θ as well as the form of Co., in (4) can be arbitrary, depending on applications and the available base predictors hand. Given C, our algorithm then solves the constrained ERM problem (5) of finding the smallest interval among C subject to valid coverage on dataset Deal-
Compared with vanilla conformal prediction, Algorithm allows more general tasks with an bitrary function class and efficiency loss; for example, this encompasses several recent algorithms such finite hyperparameter selection and linear aggregation (Yang & Kuchibhotla, 2021; Chen et al., 2021). We remark that (5) includes an additional relaxation parameter Eg 2 0 for the coverage constraint. This for analysis (for Proposition 2(b) & 7(b)) only: our implementation uses Eo
3.2 THEORY
An important theoretical question about CP-Gen is whether it achieves coverage and efficiency guarantees on the population (test data). This section showcases that, by standard generalization arguments, CP-Gen achieves approximate validity and near-optimal efficiency whenever function class is low-capacity in certain sense. We remark that experiments the modified algo- rithm CP Gen Gen-Reeall (Section 3.3) which involves a reconformalization step. Here we focus on CP Gen as we believe its theory could be more informative.
Let [oveerccoe (Co,t) := Blf coverage) (Co.t; (X, Y)) denote the population coverage and ef- ficiency lossesfor any (0, t). We define the following uniform concentration quantities:
Ceff == supa Loer (Co.t) Lett (Ctr)Co.:),
(6)
Ecoverage supBEO.IET Leoverage (Co,t) (Co.
(7)
5

---

Published as a conference paper at ICLR 2022
Algorithm 2 Conformal Prediction with General Fn. Class and Recalibration (CP-Gen-
Gen - (eP-Gen-Recal)
Input:
Class of prediction sets C {Ca, reT target miscoverage level (0, 1); Eo 2 0. Efficiency loss lett; Calibration datasets Deat, Drecal with size Reall Rrecal- Run Algorithm 1 on dataset Deal (with relaxation parameter Eg) to obtain (0, t).
2: Keep 8, and reconformalize & E 'T on the recalibration dataset Drecal:
Freeal t inf {tE VEET: Ca (24) for at least [(1 - (Trecal + 1)] examples (xi, Us) E Drecul
Output: Prediction set Cj.ycooal
The following proposition connects the generalization CP-Gen to the above uniform concentra- tion quantities by standard arguments (see Appendix B for the proof. We remark that the proof relies on Deal being i.i.d., which is slightly stronger than exchangeability assumption commonly assumed in the conformal prediction literature.)
Proposition! 2 (Generalization of CP CP-Gen). The prediction set learned by Algorithm satisfies
(a) (Approximately valid population coverage) We have
Leoverage (Cop) S a + Eo + Ecoverages i.e. the population coverage of C3.7 at least 1
(Eo Ecoverage).
(b) (Near-optimal efficiency) Suppose Eo 2 Ecnverage: then we further have
Leff Cg,z) S
inf Leet(Co.d) + 25eff
(0,0ExxT
Leoverage (Co.))
i.e. C3 achieves 2E near-opiaal efficiency against any prediction set within C with at least
(1 a:) population coverage.
Examples of good generalization Proposition 2 shows that CP-Ger: acheives approximate cov- erage and near-optimal efficiency if the concentration terms Setr and elf coveovee small. In Appendix C, we bound these on two example function classes: Finite Class (Proposition 4) and VC/Rademacher Class (Proposition 5). Both classes admit bounds of the form {Feff eff cofeoreagg S / (Comp(C)/nea) with high probability via standard concentration arguments, where Comp(C) is certain complexity measure of C. Combined with Proposition 2, CP-Gen algorithm with these classes achieve an 1 - / /Comp(C)/nen /nea approximate coverage guarantee and / /Comp(C)//m near-optimal efficiency guarantee. In particular, our Proposition 4 recovers the coverage guarantee for the finite-class selection algorithm of (Yang & Kuchibhotla, 2021, Theorem 1) though our effi- ciency guarantee is more general.
We remark that both examples above contain important applications. The finite class contains e.g- optimizing over a K K-dimensional hyperparameter to use via grid search, with e.g. (1/8)* confi- O(K log(1/))). The VC/Rademmache class
dence sets and thus Comp(C) Olog (118))(( contains the important special case of linear classes with K base predictors (we defer the formal statement and proof to Appendix C.3). Also, these examples are not necessarily exhaustive. Our take-away is rather that we may expect CP to generalize well (and thus achieves good coverage and efficiency) more broadly practice, for instance whenever learns K << Teal parameters.
3.3 ALGORITHM WITH VALID COVERAGE VIA RECONFORMALLIZATION
Although CP-Gen enjoys theoretical bounds the coverage and efficiency, a notable drawback is that it does not guarantee exactly valid (at least) 1 - a coverage like usual conformal prediction, and its approximate coverage bound depends the uniform concentration quantity &coverage that is not computable from the observed data without structural assumptions on the function class
To remedy this, we incorporate simple reconformalization technique another recalibration dataset Drecal (c.g. a further data split), which guarantees valid finite-sample coverage by exchange- ability. We call this algorithm CP CP-Gen-Ree Recal 1 and provide the full description in Algorithm 2.

---

Published as a conference paper at ICLR 2022
We remark that this reconformalization technique for obtaining guaranteed 1 - coverage is widely used in the conformal prediction literature, e.g. (Angelopoulos et al., 2020). However, to the best of knowledge, there is no known analysis for our See-Gen-Reca algorithm for general function classes, for which we provide a result below (formal statement and proof can be found in Proposi- tion 7 & Appendix D). The proof of the coverage bound is standard as in the conformal prediction literature, while the proof of the efficiency bound builds upon the result for CP Deenn (Proposi- tion 2(b)) and handles additional concentration terms from the reconformalization step.
Proposition 3 (Coverage and efficiency guarantee for OP-Gen-Recane Informal version). The prediction ser Cg learned by Algorithm 2 achieves (1 - a) finite-sample coverage:
F (.eea:(X.Y)) E Co.rrees) 2 1 - a. Further, achieves O + Ecoverage + 1/ /Trecal) near- optimal efficiency under additional regularity assumptions.
4 DIFFERENTIABLE OPTIMIZATION
Our (meta) algorithms CP-Gen and CP-Gen-Reee involve solving the constrained ERM prob- lem (5). One feasible case is when θ is finite and small, in which we enumerate all possible & E θ and find the optimal f for each 0 efficiently using quantile computation. However, this optimization significantly more challenging when the underlying parameter set is continuous and we wish to jointly optimize over (0, t): The coverage loss Lcoverage (Co.t) is non-differentiable and its "gra- dient" is zero almost everywhers as it uses the zero-one loss. This makes the coverage constraint algorithm.
challenging to deal with and not amenable to any gradient-
To address this non- differentiability, develop gradient- based practical implementation by ap- proximating the coverage constraint. We first rewrite each individual coverage loss into the form
1 Ey & Co,, = 1 (s0..(x; y) < 0} = Lo y)).
where Loz (2) == 1 fa < 0} is the zero-one loss. (Such a rewriting is possible in most cases by taking s0, as a suitable "score-like" function; see Appendix E for instantiations in experiments.) Then, inspired by the theory of surrogate losses (Bartlett et al., 2006), we approximate for (2) by the hinge =I+ which is (almost everywhere) differentiable with a non-trivial gradient. We find the hinge loss to perform better empirically than alternatives such as the logistic loss.
loss (hinge (z)
To deal with the (modified) constraint, we turn into an exact penalty term with penalty parameter A 2 O, and use a standard primal-dual formulation (Bertsekas, 1997) to obtain an unconstrained min-max optimization problem on the Lagrangian:
min max Lett (Co.)) + [niingo a O.f A20
(8)
where Lhinge (Co.t) Texi i=l fninge (59.ee (I), 34)) is the empirical hinge loss on the calibration dataset Deat- Our final practical implementation of (5) solves the problem (8) by Stochastic Gradient Descent-Ascent (with respect to (0, t) and )) to yield an approximate solution (0, f). We remark
that in our experiments where we use the reconformalized version CP-Gen-Recal we only keep the i obtained from (8) and perform additional reconformalization to compute frecal guarantee coverage.
We also emphasize that the approximation in (8) makes the problem differentiable at the cost of deviating from the true constrained ERM problem (5) and thus potentially may sacrifice in terms of the efficiency. However, our experiments in Section show that such an implementation can still improve the efficiency over existing approaches in practice, despite the approximation.
5 EXPERIMENTS
We empirically test our De--Gen-oe - algorithm (using the practical implementation (8)) on three representative real-data tasks. The concrete construction of (Co.e) will be described within each application. Throughout this section we choose - a = 90% as the nominal coverage level, and use the Ce-Gen-Recal algorithm to guarantee coverage in expectation. We provide ablations with a E {80%, 95%} in Appendix G.I and G.2 and the CP CP-Gen algorithm in Appendix G.3. Several additional ablations and analyses can be found in Appendix H.
7

---

Published as a conference paper at ICLR 2022
Table 1: Results conformal quantile finetuning on real-data regression tasks at level 1 90%. each method we report the (test) coverage, length, and pinball loss of the corresponding base quantile predictor. All results are averaged over 8 random seeds.
CQR
QR + CP-Gen -Reaa (ours)
Dataset
Coveraget %6)
Length
L pinball
Coverage(%)
Length
text pinball
MEPS_19
89.98
1.167
0.112
90.09
0.890
0.131
MEPS 20
89.72 72
1.165
0.117
89.99
0.830
0.141
MEPS 21
89.81
1.145
0.107
90.22
0.962
0.129
Facebook.1
90.12
0.555
0.052
90.34
0.384
0.090
Facebook.2
90.13
0.491
0.044
90.02
0.364
0.092
kin8nm naval
90.03
1.214
0.076
89.31
1.173
0.078
89.70
3.095
0.164
89.71
3.077
0.166
bio
90.26
2.271
0.130
90.20
2.164
0.148
blog_data
90.19
0.605
0.058
90.01
0.496
0.107
Nominal (1 a.)
90.00
90.00
5.1 IMPROVED PREDICTION INTERVALS VIA CONFORMAL QUANTILE FINETUNING
Setup We consider regression tasks in which base quantile predictor F(x) (z), fu((z)] 0 (xx) on Dursin (with learning rate decay by monitoring validation loss on Deat). Here + + Rd the learned representation function, 8 12d,22
quantile regression (pinball loss) to train
x2 is the last linear layer (d,, denotes the last hidden dimension), and fio fu are the learned {lower, upper) quantile functions (see Appendix E. for more details on the training procedure). Given F, we learn a baseline prediction interval of the form (fo(() - t, fn)( + t) on Drecal via Conformalized Quantile Regression (CQR) (Romano et al., 2019).
We then attempt to improve the length over CQR by conformal quantile finetuning: Fix the repre- sentation function & and finetune the linear layer 0 using our CP-Gen-Recal algorithm, so that Co.e 10 (xx) - tt 2
(z) + (where 0 [0to, 0mi)). We learn a new & on Deal via (8) (where left is chosen the length), and then compute Trocal on Drocal in Algorithm
We perform the above on 9 real-world regression datasets with a 3-layer MLP with width d, = 64, similar as (Romano et al., 2019; Feldman et al., 2021). Additional details about the setup can be found in Appendix F.1. We also test various tweaks of the CQR baseline (results provided in Appendix H.2).
Results Table compares the (test) coverage and length between COR and the finetuned linear layer via our CP-Gen-Recal. While both CQR and Re-Gen-Recal 1 achieves valid 90% cover- age, CP-Gen-Recal can systematically improve the length over CQR on all tasks. Table also reports the pinball loss for both the base (z)(2)) as well as the fine-tuned Ø (xx) on the test set Dust. Intriguingly, our conformal finetuning made the pinball loss worse while managing to im- prove the length. This suggests the unique advantage of our constrained ERM objective, as it rules out the simple explanation that the length improvement is just because of a lower test loss. We remark that while CP GencRecal improves the length over CQR, it comes at a cost in terms of worse conditional coverage (analysis presented in Appendix H.1).
5.2 MINIMUM-VOLUNE PREDICTION SETS FOR MULTI-OUTPUT REGRESSION
Setup This task aims to learn a shx-sd prediction set for multi-output regression with a small volume. Our learning task regression with output dimension dout 1. We first learn based predictor f Rdd - dout by minimizing the MSE loss on Dtrain- We then learn a box-shaped prediction set of the form Cz(x) = dost [f((x) ū, f((z) 2.] by one of the following methods:
(Coord-wise): Each ū is obtained by vanilla conformalization (2) over the i-th output ordinate on Deat I U Drecal- To guarantee 1 - a coverage, each coordinate conformalized at level a/ aodout motivated by the union bound.
8

---

Published as a conference paper at ICLR 2022
Table Results multi-output regression on next-state prediction tasks, at a 90%. each method we report the (test) coverage and volume of its learned box- soxped prediction set. The reported volume the "halfened" version T ug- All results averaged over 8 random seeds.
Coord-wiss
Coord-wiss Recal
CP-Gen-Reca (ours)
Dataset
Coverage( %)
Volume
Coverage(%)
Volume
Coverage(%))
Volume
Caripole
94.28
1.20 x 10-5
90.17
5.10 x 10-6
90.12
2.30 x 10
Half-Cheetah
93.90
1.10 x 10
90.06
1.23 x 10
90.02
9.07 10
Ant
93.56
3.37 x 10-3
89.99
1.70 x 10
90.02
8.25 x 10
Walker
94.42
2.59 x 10
90.01
7.33 x 10-7
89.94
3.47 10
Swimmer
95.62
2.80 x 10
89.90
2.22 x 10
90.13
1.46 x 10-7
Hopper
92.87
2.81 x 10-9
90.02
1.01 x 10-9
89.92
8.25 x 10-10
Humanoid
94.75
4.28 x 10"4
89.95
8.53 x 10
89.94
4.95
10
Nominal (1 ())
90.00
90.00
90.00
(Coord-wise-Recal Perform the above on Deal learn ū, and reconformalize an addi- tional 2 0 on Drecal to reshape the prediction set proportionally:
Ca,( = IT [F(()) tū, f((x) + tū.).
(CP-Gen-Recal, ours): Optimize the volume directly over all u E Rdom using (8) on Deal= where (Cu: (z, y)) = II (2u,) is chosen as the volume loss. We then reconformalize an additional [ 2 0 on Drecal to reshape the prediction set same as in (9). Note that this reconformalization step is equivalent to Algorithm 2 with the re-parametrization ū - (0,7) where 0 E 1 denotes the ratio between ü; and i E R> denotes a common scale.
Our datasets are a collection of next-state prediction tasks with multi-dimensional continuous states in offline reinforcement learning (RL), constructed similarly D4RL (Fu al., 2020) with some differences. Additional details about the dataset and experimental setup are in Appendix E.2. We also test additional Max Score-Conse rmal baseline (which uses vanilla conformal predic- tion with score function 1y - (=)]l equivalent to hypercube-shaped predictor) Appendix H.3, which we find also performs worse than our CP Re--Gen-Recal
Results Table 2 reports the (test) coverage and volume of the above three methods. The Coord-wise method achieves valid coverage but is quite conservative (over-covers), which is as expected as the union bound is worst-case in nature and the coordinate-wise conformalization does Goord-wise-Recal achieves approximately 90% coverage with a much smaller volume. Our CP-Gen-Recal also achieves valid 90% coverage but further lower volume across all tasks. This suggests that optimizing the volume over all possible u E 1o data-dependently using our CP-Gen-Recal is indeed more flexible than pre-determined conformalization schemes such as Coord-wise.
utilize the potential correlation between the output coordinates.
Additional experiment: label prediction sets for ImageNet show that CP-Gen- (Gen--ecaa 1 can leam label prediction sets for ImageNet with valid coverage and improved size over existing ap- proaches, by finding an optimized set of ensemble weights over multiple base neural networks (Ta- ble 5). The full setup and results are presented in Appendix F.
CONCLUSION
This paper proposes Conformal Prediction with General Function Class, a conformal prediction algorithm that optimizes the efficiency metric subject to valid coverage over a general function class of prediction sets. We provide theoretical guarantees for its coverage and efficiency in certain situations, and develop a gradient-basee several large-scale tasks. We believe our work opens up many directions for future work, such as stronger theoretical guarantees via more structured function classes, further improving the gradient- based approximate implementation, experiments other uncertainty quantification tasks.
practical implementation which performs well empirically

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENT
We thank Silvio Savarese for the suggestion on the multi-output regression task, and Yuping Luo for the help with preparing the offline reinforcement learning dataset. We thank the anonymous reviewers for their valuable feedback.
REFERENCES
Physicochemical properties of protein tertiary structure data set. https://archive. ics. wessuui..ddummm/dde http///tttteettttstsasssseseeeee sccchen..cc..opeerreeeefrroooaa Srrt Accessed: January, 2019.
Blogfeedback data set.
ics http://e.....c....cceaaaaaaaaaaa
BlogFeedback. Accessed: January, 2019.
Facebook comment volume data set. https://archiver /tttt/tt///////aattttt///////// Crrebook-CCommen--VVe +Dataset, Accessed: January, 2019.
Kinematics of an link robot arm. http: cs..t........................... http//tt.......oottoooooooooooot wtt../oooottttteeep////e/erroona
toronto. edu wwtp/ppbb.nneurron//alaaea data/tarfiles/ family/. Accessed: May, 2021.
Medical expenditure panel survey, panel 19. https::/mepa htt.://s...aggggggegeeeeb/bb/b/e
statss downl oa ddddd_a___iiieeeeeee lerlllee__e_lleeeeeeeeeeee bet. cessed: January, 2019.
a. Ac-
Medical expenditure panel survey, panel 20. https////eess.aarrg.o/////eess/ stats/ /donn////w///ooo sdd_d_t__fiii htt.eeee..eaall..pppppoooofffafe cessed: January, 2019.
b. Ac-
Medical expenditure panel survey, panel 21. http:::/mme...aacccccc//////s//p stats/ down///wwwwll oad dadaaaaaaaa. files_detail http://ccooofffmmbrrr----1-12122
httpa/ffiie....../oo/ooooooooorr cessed: January, 2019.
Ac-
Condition based maintenance of naval propulsion plants data set. http://arccieeeeeeee ics uci. edu/m1/dataset Condit on htt.ai/awwscccccceeeeecceaaaaaaa Plants. Accessed: May, 2021.
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.1419. 14193, 2020.
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.05511 2021.
Yu Bai, Song Mei, Huan Wang, and Caiming Xiong. Understanding the under-coverage bias in uncertainty estimation. arXiv preprint arXiv:2106.05515. 2021. 2021.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-500 2021.
Ole E Barndorff-Niee and David R Cox. Prediction and asymptotics. Bernoulli, pp. 319-340, 1996.
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 1388-3):333111 156, 2006.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. arXiv preprint arXiv:2101.02703 2021.
Rudolf Beran. Calibrating prediction regions. Journal of the American Statistical Association, 85 (411):715-723, 1990.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):
334-334, 1997.
10

---

Published as a conference paper at ICLR 2022
Jan F Bjornstad. Predictive likelihood: A review. Statistical Science, pp. 242-2544 1990.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint arXiv:2008. 2020a.
Maxime Cauchois. Suyash Gupta, and John Duchi. Knowing what you know: valid confidence sets in multiclass and multilabel prediction. arXiv preprint arXiv:2004. 10181, 2020b.
Haoxian Chen, Ziyi Huang, Henry Lam, Huajie Qian, and Haofeng Zhang. Learning prediction
intervals for regression: Generalization and calibration. International Conference on Artificial Intelligence and Statistics, pp. 920-828. PMLR, 2021.
DR Cox. Prediction intervals and empirical bayes confidence intervals. Journal of Applied Proba- bility, 12($1):47-55, 1975.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Shai Feldman, Stephen Bates, and Yaniv Romano. Improving conditional coverage via orthogonal quantile regression. arXiv preprint vxXi:22166000344 2021.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455-482 2021.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep
data-driven reinforcement learning, 2020.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059.
PMLR, 2016.
Leying Guan. Conformal prediction with localization. arXiv preprint arXiv:1908.000 2019.
Chirag Gupta, Arun Kuchibhotla, and Aaditya Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. arXiv preprint arXiv:1910.1056: 2019.
Peter Hall, Liang Peng, and Nader Tajvidi. On prediction intervals based on predictive likelihood or bootstrap methods. Biometrika, 86(4))871-800, 1999.
Peter Hoff. Bayes-optimal prediction with frequentist coverage control.
arXiv preprint
14045 2021.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E Hoperoft, and Kilian Q Weinberger. Snapshot ensembles: Train 1, get m for free. arXiv preprint (:Xiv:/704.001100 2017.
Rafael Izbicki, Gilson Shimizu, and Rafael B Stern. Flexible distribution-free conditional predic- tive bands using density estimators. arXiv preprint 19Xiv:1910.0555/7 2019.
Rafael Izbicki, Gilson Shimizu, and Rafael B Stern. Cd-split and hpd-split: efficient conformal regions in high dimensions. arXiv preprint arXiv:2007.12778, 2020.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? arXiv preprint arXiv:/703.000 04977, 2017.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In International Conference Artificial Intelligence and Statistics, pp. 4346-4356. PMLR, 2020.
Balaji Lakshminarayanan. Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. arXiv preprint arXiv: 1172,01444 2016.
11

---

Published as a conference paper at ICLR 2022
JF Lawless and Mare Fredette. Frequentist prediction intervals and predictive distributions. Biometrika, 92(3):29- 542, 2005.
Jing Lei and Larry Wasserman. Distribution-fied prediction bands for non non-parametric regression.
Journal of the Royal Statistical Society: Series B: Statistical Methodology, pp. 71-96, 2014.
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):78--87,, 2013.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111, 2018.
David John Cameron Mackay, Bayesian methods for adaptive models. PhD thesis, California Institute Technology, 1992.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. Advances in Neural Information Processing Systems, 32:13153-13164 2019.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. arXiv preprint arXiv: 10501, 2018.
Andrey Malinin, Bruno Mlodozeniec, and Mark Gales. Ensemble distribution distillation. arXiv preprint 100006690..00076 2019.
Pascal Massart. The tight constant in the dborezaty-kiefer-wwlloowzz inequality. The annals of Probability, pp. 1269-1283, 1990.
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. In Advances in Neural Information Process- ing Systems, pp. 13991-14002, 2019.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools in artificial intelligence. Citeseer, 2008
Sangdon Park, Oshert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. arXiv preprint arXiv:2001.00 2019.
Tim Pearce, Alexandra Brintrup, Mohamed Zaki, and Andy Neely. High-quality prediction inter- vals for deep learning: A distribution-free ensembled approach. International Conference on Machine Learming. pp. 4075 PMLR, 2018.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize imagenet? In International Conference on Machine Learning, pp. PMLR, 2019,
Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. arXiv preprint arXiv:1905. 102.022,0 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. arXiv preprint wrXiv:2006.02544, 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-2) 234, 2019.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
Qinglong Tian, Daniel Nordman, and William Q Meeker. Methods to compute prediction intervals: A review and new results. arXiv preprint arXiv:201 10220/1.00000 1.03065, 2020.
Aad Van Der Vaart and Jon Wellner. A note on bounds for ve dimensions. Institute of Mathemat- ical Statistics collections, 5:103, 2009.
12

---

Published as a conference paper at ICLR 2022
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pp. 475-490. PMLR, 2012.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74 (1):9-28, 2015.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science Business Media, 2005.
Vladimir Vovk, Ilia Nouretdinov, Valery Manokhin, and Alexander Gammerman. Cross-conformal predictive distributions. In Conformal and Probabilistie Prediction and Applications, pp. 37-51. PMLR, 2018.
Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of gorithmic randomness. 1999.
Yachong Yang and Arun Kumar Kuchibhotla. Finite-sample efficient conformal prediction. arXiv preprint arXiv:2104. 13871, 2021.
A PROOF OF PROPOSITION
Recall that Cx(x) [f(x) t, f(x) satisfies Lott (Cz; (I, (I,y) 3) length(C((z)) 2t for any (x, v). Also, we have
1 1v C((a)] (v $ [f(x) t, f. +[] f(v) t}
or equivalently (u E (x)) = (lv [(x) s t). Therefore, problem (3) is equivalent to
minimize 120
subject to 1 - Leoverage (C₂) = Σ 1 f(x)) St 2 1110 a.
Thcal
By definition quantiles, this problem is solved at
T= [(1 - a)meal -th largest element (ly [a::))) Bead
which is the desired result.
B PROOF OF PROPOSITION 2
(a) As Cg solves problem (5), it satisfies the constraint Leoverage (Cz,)) S a + co. Therefore, Leoverage (Ca.))
Leoverage (Cg.z) Leoverage (Co.z) Leoverage (Cz.))
Satto
< a + sup (0x))
Leoverago (Co.t) - Leoverago (Co.t)
Eo Ecoverage-
(b) Suppose Ecoverage S Eo. Taking any (0,1) x T such that Leoverrgge(aan S a, we have
Leoverage (Co,t) < Leoverage (Co.s) + Ecoverage S a + Ecoverage I a Eg.
This shows that (0, 1) lies within constraint set problem (5). Thus as (0,7) further minimizes the loss Loft within the constraint set, we have Leer (C',,) < Lott (Co.)). This shows that
Lostt (Ca.) Testt (Co.t)
13

---

Published as a conference paper at ICLR 2022
(Cnn( - (Co,)) +2
(Co() - Letl (Co,e)
sup (0,0ExxT
<0
I 26eff.
As the above holds simultaneously for all (0,1) E e x T with at most a coverage loss, taking the sup over the left-hand side yields
Left (C,,)
inf (0x))=exT Leooerage (Ca,
Lett (Ce,)) 2f
C EXAMPLES OF GOOD GENERALIZATION FOR CP-Gen
We provide two concrete examples where the concentration terms 6eff and cooerrgee are small with high probability, in which case Proposition guarantees that CP learns prediction set with approximate validity and near-optimal efficiency.
Assumption A (Bounded and Lipschitz efficiency loss). The loss function lett satisfies
AI (Bounded loss). (ett(Caaa (I, u))l & M for all (0, E E x T and all (r,y) E X x > A2 (f-Lipschirrness). ++ leat (Co,s; (x, v)) is Lippipschitt all (0, x. y) E θ x X x y. Assumption B (Bounded T). The parameter space T C. IR is bounded: supteT |t| By.
C.I FINITE CLASS
Proposition 4 (Finite class). Suppose is a finite set (Ne == | < oo), and suppose Assump- tions A1, A2, B hold. Then, we have with probability at least 1 5 that
Ecoverage
CV Cooooo(Ne//))/
and Eeff SC [.M Nog(NNo0 LT LT /VTAl
where C. >> 0 is an absolute constant.
Proof. We first bound Ecoeragge- Fix any 0 E θ define
to to inf (t E T Cg 3 v) to be the smallest possible E T such that the Co.((z) contains y. Observe that, as (C) are nested sets, the coverage event can be rewritten as 1 fy E Co.((x)) 1 {t 2 ta y)} for any (x, y). Therefore, we have
(10)
Leoverage (Co, Leoverage (Co,))
sup EET
sup
(ys & Ca,((x)) - P(V & Co,(
EET
neal
sup
1 (ys E Ca,(x))) P(Y E Co,(X))
IET
Meal
sup :
(ta v) 5 - (to,, 5)
Teaa i=1
Fo(t) Fo(t)
sup ETT
where we have defined Fg R - [0, 1] as the CDF of the random variable (X(, Y) and similarly F
the empirical CDF of the same random variable over the finite dataset Deat Applying the Dvoretzky-Kiefer-Woon Wolffwitz (DKW) inequality (Massart, 1990, Corollary 1) yields that
Pa(1) Fo(O)
log(2/6)
sup *ET
2neal
14

---

Published as a conference paper at ICLR 2022
with probability at least 5. Now, taking the union bound with respect to 0 θ (where for each we plug in tail probability 8/2NN) we get that with probability at least 8/2,
Ecoverage
sup sup AEA ET
Lroverrago (Co.s)
Leoverage (Co.s)
(11)
sup Po(l)= Fo(1) S 86 TT
log(4Ne/0)
log(Ne/o)
<C1
2neal
neal
for some absolute constant C' > O.
We next bound Eeff. Fix any 0 E O. We have by standard symmetrization argument that
Letr( (Co.)) - Lott (Co.o)
E
sup LET
=E =E
sup LET
Last (Co,e: (2i,, vi)) Ellett (Co,:: (X, Y)]
ncal
==1
< 2B
sup tET
exlen (Co,s3 (Ii,
(i), vi))
Real
1
2L Ez,
sup
Ei /
= 2LT Exc
sup |
LET
Real
neal
EE
im
i=1
(4)) <
(12)) 2LT BT Meal-
2T.7 By
Egg Real t=1
Above, (i) used the Lipschitzness Assumption A2 and the Rademacher contraction inequality (Ver- shynin, 2018, Exercise 6.7.7); (ii) used Assumption B, and (iii) used Ez,,
Real Diaal E I
Real Ens Es) 9) 1/2 1/ Real- (Above E lid Unif((+1)) are Rademacher variables.)
Ee,
Next, as each loss Reet (Ce.ss (I, 8))l s M by Assumption AI, the random variable
sup iET
(Co. - Lea (Co.t)
satisfies the M/ M/neal fifite-difference property. Therefore by McDiarmid'ss Inequality, have with probability at least 1 - that
Lett(Ca.) Lott Lotr
sup 1ET
Prott (Co.t) - Liott (Caii)
M log(1/5)
< E
sup LET
+ +1
2neal
< C Lr M (lo((1/0)
Vical
Finally, by union bound over 0 E θ (where we plug in 6/2Ne as tail probability into the above), we have with probability least 5/2 that
Prent (Co.)) - Leet (Ca+))
Eeff sup sup 8 LET
(12)
< C LTBT + M / (lo((No/))
/Teall
(11) together with (12) is the desired result.
15

---

Published as a conference paper at ICLR 2022
C.2 VC/RADEMACHER CLASS
Next, for any class C, let VC(C) := VC(((a,)) + tv & Co.(+)) :0 0 0 denote its VC dimension with respect the coverage loss.
Proposition 5 (VC/Rademacher class). We have for some absolute constant C > 0 that
(a) Suppose VC(C) K oc, then with probability at leust - 5/2,
Ecoverage S SCV(K +1+ (og//0ll//)))//mmmm
(b) Suppose Assumption Al holds. Then have with probability least 1 - 8/2 that
Seff S cofette (C) + VM2 log(1/)))
where Reft (C)
(e(osa)), (UP(OA))EXXTT
Peal Ees eelett (Ca,ti (ri, (Fi, is the Rademacher
complexity the class C with respect lett (above EL (ni((
jid
Proof. (a) By assumption, the class of Boolean functions ((x, v) + 1 tv Co,( (o.Eexx has VC dimension K + 1 < Therefore by the standard Rademacher complexity bound for VC classes (Vershynin, 2018, Theorem 8.3.23) and McDiarmid's Inequality, we have with probability at least 1 5/2 that
coveraaee
sup (0,1)ExX
{va & - - P(Y & Ca,((X)
neal 1=1
log(2/8)
K + (1/()
I CC
S SO
Peal
2neal
Real
(b) We have by standard symmetrization argument that (below & Unif((+1)) denote Rademacher variables)
E
Geft E
sup BEATET
(Co,) - Lott (Cor(C
Real
E
sup 0ET.ET
Lest Co, (x:. Bleett (C (X,
Real
1=1
Thaa
< 2E (x.sn)ee
sup 0EG.ET
Eslort (Ca,t (o;, (4t, 9i))
(C).
Peal
Further by Assumption A1, the quantity Eeff satisfies M/neal bounded-difference applying Mc- Diarmid's Inequality gives that with probability at least - 8/2.
2M log(2/5)
2 log(1/5)
Eaft < E E[EeH]] +
C
peff (C) + Ren
neal
C.3 CASE STUDY: LINEAR CLASS
In this section, we study prediction intervals with specific linear structure and show that it satisfies the conditions of the VC/Rademacher class of Proposition 5.
Concretely, suppose we have regression task ()' R), and the prediction interval (a,((=) takes linear form
Co.(x)) _T (x) to (x), 0 (ma()) tx)),
(13)
16

---

Published as a conference paper at ICLR 2022
where 0 ? E o : Ryo-
+ R Pni Plo X + R are feature maps such that (1)(2); I Pmi(z); for all
For intuitions, can think of & (hi.lo) pretrained representation functions and (optional) pretrained function for modeling the variability of y/a. Note that this encompasses linear ensem- bling several existing methods, such as vanilla conformal regression (Lei et al., 2018) by taking Pni 1 = & where each Φ; X - IR is base predictor, well Conformalized Quantile Re- gression (Romano et al., 2019) where each (flo, Pai,s) is a pair of learned lower and upper quantile functions.
Our goal is to find an optimal linear function this representation that yields the shortest prediction interval (with fixed width) subject to valid coverage.
We assume that both the features and the parameters are bounded:
Assumption C (Bounded features and parameters), We have supice |0||| S Be, supzex [((x))] 5
Bą, x (x) < Ba, and suPieT [6] < BT.
The following result shows that Proposition 5 is applicable on the linear class.
Corollary (Coverage and length guarantees for linear class). For the (K + 1)-dimmessoona linear class (13), suppose Assumption C holds, and we take the efficiency loss be the length of the interval: fell (C; (x, y)) == length(C(#)). Then, we have with probability at least - ô (over the calibration dataset Deal) that
K 1 + log(1/5) and Sett S BB + BTBo!
log(1/0)
Ecoverage S SCV
Peal
where C is an absolute constant.
Proof. We verify the conditions of Proposition 5. First, have
1 ty & Ce.((x)) = 1 {max {v 0 (T),,, oJ 11o(x) - y} > to(x))
The set within the indicator above is the union of two sets { yz, : - T TT to > >0} and { (xr,)) P1o(x) y (xx 0}. Note that each family of (over (0, E R K
linear halfspaces with feature dimension K + 2), and thus has VC-dimension < K + 2. Applying
the VC dimension bound for unions of sets (Van Der Vaart & Wellner, 2009, Theorem 1.1), we get
VC(C) < C'(K + + K + 2) < C(K + 1) for some absolute constant C > 0. Therefore the condition of Proposition 5(a) holds from which we obtain the desired bound for Ecoverage-
To bound Ceft, we first note that for any (z, E X x R,
(Co ii (z, v))l = [length(Co,(()))
= 0 (ffilz) (x)) + 2t ||0|| (m)))) (1)()) 2tx
< 2B + 2B B, =: M,
and thus the boundedness assumption (A (Assumption A1) holds with M defined above. Next, we have the following bound on the Rademacher complexity
Real (C) = E
sup (xxT)
ex(0 (PPn(x:)) (1o(2:)) + 210(1)))
Neal Tm1
1
Real
>
E sup
0.
+ E
sup TET
2t
EjO (Ii)
9g
Real
Thaal 1=1
1=1
127 1/2
271/2 1/2
sup 066
||0||
E
e: (m)()))) - (x)())
sup IET
|t|
R
(10
neal 1=1
Reall 1=1
1/2
1/2
<
Bg
E
p (11) - (11))1
+ BB
E
(x
neal
neall
17

---

Published as a conference paper at ICLR 2022
C. BoBb + Bo
Vieal
Applying Proposition 5(b), we get Ceff I C. (B + By) /log(1/6)/naa) with probability at least 1 - 6. This is the desired bound for Coff-
D THEORETICAL GUARANTEE FOR CP-Gen-Reca
In this section we state and prove the formal theoretical guarantee for the Ce-Gen-Recal algo- rithm (Algorithm 2).
Define the score (g(X, Y) inf (t E T Y Co,(()) and let Fo(t) = P(Y Co,(XX) ((t, Y) & t) denote its CDF.
Assumption D (Lower bounded density for score function). For any I O, tx(X, Y) has a positive density fe(t) = (t) > O on t E T. Further, let tg.1 == inf {t E T Fe(() 2 a} denote its (1 (1-a) quantile, then there exists some constants Sp. dg such that
inf rElte.1 0o fo(t) 2 Su
Proposition (Valid coverage and near-optimal efficiency for reconformalized algorithm). The following holds for Algorithm 2:
(a) (Valid coverage) For any possible & O learned in Line I and the resulting frecull have
Ep Dreecal Leoverago ( S ar and thus IP P (y Cp.Erra (x)) 2
(b) (Efficiency) Suppose Assumptions A2 and D hold, max (Ecoverage + 1//eal, 2 (og((16)//nooo codo (recall the definition of Ecoverage in (7)), and Ecoverage S Eg. Then for 6 I 0.5, we have with probubility at least - 5 that
log(1/8) nrecal
Letf (Cg,Eooo))
(Co,e) + 2Eef + CLT (0x1)=xxT
min
Ecoverage
/co-
Teaal
Tvoeeraage (Co,)
Proof. (a) As the learned parameter 0 (and thus the family of nested sets Cz ) is independent the recalibration dataset D Drecal, we have that the scores tz(x, y) on dataset Drecal and new test point (X,Yl Y) exchangeable given any 0. Therefore by (Gupta al., 2019, Proposition 1), we have for any that
(X (X Ca (x)) a,
equivalently E Draesl Leoverage Ci Sa.
(b) For any O, define the score function fo( y) the same as in (10), and similarly define the CDF (t(() = P(lo(X,X, Y) S () and its empirical counterpart Fraal (1) and Frecal (1) as the finite- sample version dataset Deal and Drecal respectively.
We first analyze f. By the same derivation in (11), we have
sup YTT
Feaa
(t) Pt(()
<
sup (0.0)xxT
F (t) Fo(t) Ecoverage-
As (0, t) solves the constrained ERM (5) and by the assumption that loul (Co.e: (z, v)) is monotone in 6, have that E is the minimal value of E T such that ]raa(() 2 a. Therefore, (as Deall = Real and (1e y)) y.)ieD... are almost surely distinct by Assumption D.) we have
1 Seal 1 <
1/neat-
18

---

Published as a conference paper at ICLR 2022
This shows that
Fo(t) F [F((O) - (1- -1-o)] ccoeraage + 1/
where we recall that 10,10 is the (1 - a)) (population) quantile of 1,(X, Y). Note that FT(1) fo(t) 2 co on & E 1- 6o, 8, + dol by Assumption D. Further, Ecoverage + 1/neal S G000- Therefore, by monotonicity of Fg. we must have E 1t - -o. tā + oo], and thus
T 10.1-a S (Coowerage + 1/meal)/So.
(14)
We next analyze Treeat. As the dataset Drocat independent of 0, we can apply the DKW Inequal- ity (Massart, 1990, Corollary 1) to obtain that
Procal
Fa(O/ S
log(1/6)
sup TET
2mrreal
with probability at least
Using a similar argument as above, we get (for $ 0.5)
1og((/6)
log(1/8)
Fylrecca)) Fo S
$2
2Mrecal
Orecal
nrrccl
As 2//oog1/00///////////// /recall S codu, we can apply the similar argument as above to deduce that
Erocal t t, < 2 2/ /ro
(15)
Combining (14) and (15) and using the Lipschitzness the efficiency loss (Assumption A2), we get
Leff (G Leff (Ca,z)
S LT Frecal - 8) S Lo (frrecal - -ti
+ 1t - E)
-1 Ecoverage + Real + 1og(1/)) (1/)
S CLT
/ca-
nirecal
Finally, as we assumed Ccoverage
I Co, the condition of Proposition 2(b) holds, so we have
Leff Cg.z)
inf
Lett(Co,e) + 26
(0,1)E0x Leaverage Lesverau-Coo.)Sea
Summing the preceding two bounds, we get
1og(1/5)
Lett Co
inf (0.1) Leoverage (Co,)5a
Lea + 2Ech + CLT
Ecoverage n + V
cco-
nrecal
which is the desired result.
E ADDITIONAL EXPERIMENTAL DETAILS
E. CONFORMAL QUANTILE FINETUNING
Datasets Our choice the datasets follows (Feldman et al., 2021). We provide information about these datasets in Table 3.
All datasets are standardized so that inputs and labels have mean 0 and standard deviation 1, and split into (train, cal, recal, test) with size 70%, 10%, 10%, 10% (varying with the random seed).
19

---

Published as a conference paper at ICLR 2022
Table 3: Information about regression datasets, Here (n, d) denotes the (sample size, feature dim).
Dataset
d
MEPS 19 (mep,
13785
139
MEPS_20 .20 (mep.
17541
139
MEPS (mep. e)
15656
139
Facebook_] (fac)
40948
53
Faccbook 2 (fac)
81311
53
kin8nm (kin)
8192
8
naval (nav)
11934
17
bio (bio)
45730
9
blog data (blo)
52397
280
Base predictor and optimization Our network architecture is 3-layer MLP with width 64 and output dimension 2 (for the lower and upper quantile). We use momentum SGD with initial learning rate 10-3 and momentum 0.9, batch-size 1024, and run the optimization for max of 10000 epochs. A 10x learning rate decay is performed if the validation loss on Deal has not decreased in 10 epochs, and we stop the learning whenever the learning rate decay happens for times. The loss function used training F [fi. fuil is the summed pinball loss of level a/2 for fio and 1 - a/2 for fui. following (Romano al., 2019):
e E(F; (I,, v:)) = gor/2
pinball (Po(z;)) - y.) + Cimnn ( V.),
where for any 3 E (0, 1), p
"inball is the pinball loss at level ,3:
g pinball (1) =
{
i 0, 3t
B)t
ift 2 0.
Optimization details for CP CP-Gen-Recce Recal For the conformal quantile finetuning procedure with our CP -enaal, we rewrite the miscoverage loss for the quantile- based prediction interval as
1 ty & Ca,( = 1( max 0 ((x) - v. y.y-0aa00 (x)) < o).
(In practice our f also includes a trainable bias same as the original top linear layer; here we abuse notation slightly to allow casier presentation.) We approximate the right-hand side above with the hinge loss to obtain the formulation (8). To solve that optimization problem, we use SGD on (0, t) with learning rate 0.01 and (ascent on) À with learning rate 0.1. The batch-size here is 256 and the number of episodes is 1000. To ensure t > O we use a log parametrization for t. Finally, frecal is computed by the reconformalization step in Algorithm
Dreeal-
E.2 MULTI-OUTPUT REGRESSION
Datasets We generate offline datasets consisting of (state, action, next_state) pairs within RL tasks within the OpenAI Gym (Brockman al., 2016). For each task, the data is generated by executing medium-perte -erblomm-prforminggg behavior policy that is extracted from standard RL training runs. All tasks are continuous state and continuous action. Table 4 summarizes the state and action dimension, along with the reward of the policies used for generating the data. All datasets contain 200K examples.
All datasets are standardized so that inputs and labels have mean and standard deviation and split into (train, cal, recal, test) with size 70%, 10%, 10%, 10% (varying with the random seed).
Base predictor and optimization Our network architecture a 3-leyrr MLP with width 64, input dimension din = ds + d. and output dimension dout ds. We use momentum SGD with initial learning rate 10-3, momentum 0.9, and batch-size 512. We run the optimization for 1000 epochs with a 10x learning rate decay at epoch 500. The loss function for training the network is the standard MSE loss.
Optimization details for EP-Gen- Recal For the conformal quantile finetuning procedure with our CP- Tee-GennReee Recal, we rewrite the miscoverage loss for the box-shaped prediction set as
dont
[f((z) u, fa(x)) + ue] = 1ft
ly: fr(s)//) < <o}
1 {y & Cu(x))
max 1siddon
1=1
20

---

Published as a conference paper at ICLR 2022
Table Information the stxt-state prediction datasets. (ds, d.a) denotes (state, action) dimen- sion of the corresponding RL task. Datasets with (slim) note only extract a subset of the full state (so that ds is less than the full state dimension). We also report the mean reward of the behavior policies.
RL. Task
ds
d
mean reward
Cartpole
Half-Cheetah
17
8015
Ant (slim)
27
4645
Walker
17
3170
Swimmer
51
Hopper
2066
Humanoid (slim)
45
17
1357
where recall Rdout is the learnable parameter within the initial optimization stage of CP Ce--en-Recal as discussed in Section 5.2. We approximate the right-hand side above with the hinge loss to obtain the formulation (8). To solve that optimization problem, use SGD on (6, t) with learning rate 0.01 and (ascent on) À with learning rate 0.01. The batch-size here is 1024 and the number of episodes is 1000. To ensure
we use log parametrization for u.
For the reconformalization step, we keep the (relative) ratios the ā obtained above (as the 0), and then reconformalize an additional frecal > 0 on Drecal via the proportional reshaping of (9).
E.3 DETAILS FOR FIGURE 1
Figure obtained on one run of our conformal quantile finetuning experiment on the MEPS_ dataset, and illustrates the coverage-efficieng tradeoff. Both figures there compute the coverage and length on the (unseen) test set Dtest. for better illustration. Figure Left plots the family [Ro(() - I, (x) + used by Conformalized Quantile Regression. Figure Right plots the family
Co.( (x) 0 (x)).
The specific function class shown in the thinner lines is a finite set of linear interpolations of the original 8g obtained in QR and the new obtained by conformal quantile finetuning, with combination weights within (0..3, -0.2. 1.0). The shaded region then obtained by filling in the area.
F RESULTS FOR LABEL PREDICTION SETS ON IMAGENET
Here we present the ImageNet label prediction set experiment abbreviated in Section
Dataset and model We take ing set (Deng et al., 2009). Our models are [ResNeXt101, ResNet152, ResNet101, DenseNet161, ResNet18, ResNet50, VGG16, Inception, ShuffleNet), similar as in (Angelopoulos al., 2020).
large-scale pretrained neural networks on the ImageNet train-
We then consider task of constructing label prediction sets with valid coverage and small cardinal- ity. We train and test out conformal procedures on the following two datasets, neither seen by the pretrained models:
(1) ImageNet- Val: The original validation set ImageNet with 50000 images. We randomly split (varying with seed) this into Deaal 10000. Drecal 10000, and Drest 30000.
(2) ImageNet-V2. V2 (Recht et al.. 2019): A new validation set following the roughly the same collection routines of the original images in ImageNet, however believed have mild dis- tribution shift and thus slightly harder for classifiers pretrained on ImageNet. This dataset contains 10000 images, which we randomly split (varying with seed) into DDaal = 4000, Drecall 1000, and Drest| 5000.
Methods for learning prediction sets Our constructions of the prediction sets are based on the Least Ambiguous Set- Valued Classifier (LAC) method of (Sadinle al., 2019), which turns any base
21

---

Published as a conference paper at ICLR 2022
Table Results for ImageNet Prediction Sets with Conformal Ensembling. For each method we report the (test) coverage and set size. Each entry reports the (mean, std) over 8 random seeds.
Best conformalized single model
Conformalized uniform ensemble
Ensemble via CP-Gen -en--Gen-Reen Recal (ours)
Dataset
Coverage(%))
Size
Coverage
Size
Coverage(%%)
Size
ImageNet-Van Val
90.10 + 0.29
1.70 0.03
90.13 + 0.21
1.62 + 0.02
90.11 + 0.33 90.18 + 0.85
1.51 + 0.03
ImageNetV2
90.01 + 0.71
5.00 0.24
89.93 + 0.71
4.66 + 0.22
4.39 + 0.44
predictor p where p(-|z) denotes the predicted distribution of the L 1000 labels into prediction set Ca(2) via
(x))) = {u (T) p(ul=) > 1),
where / is found by conformal prediction.
We consider learning a valid prediction set with smaller set size by finding an optimized ensem- ble weight of the K base predictors using our CP-Gen-Recal algorithm. This means we learn prediction sets of the form
{W [L po(ul>))
Co.(x -
Σ (v)a(v))) 10nnn(ia)>>
k=1
where {pk <pk] are the base predictors.
Our Ce-Gen-Recal algorithm (and its practical implementation (8)) would solve primal-dual optimization problem with the efficiency loss and hinge approximate coverage constraint to optimize (f, However, here the efficiency loss we care about (the cardinality) non-differentiable. We make a further approximation by considering the Lg norm with q 0.5 as the surrogate efficiency loss:
let (0, (x4,y:))
Σ po(l/11,)) +
with the intuition that the q 0 limit exactly the cardinality of Co.e(az). Our final optimization problem is then
Real
min AEAx XSO
(oll'(lxe)) +)4
Cninge (po(ys(2z) - t)-
neal
Meal
11=1
We solve this by SGD on (0, and (ascent on) X, with the softmax parameterizzatin for 0 (0 E AK as an ensemble weight is a probability distribution) and log parametrization for > 0. The learning rate is 10 2 for (9, f) and 10-4 for A. We perform this optimization for 500 epochs over Deal with batch-size 256 for ImageNet-Ve Val and 64 for ImageNet-V2.
After we obtain the iterates {ō,} (where j denotes the epoch count), we perform further iterate
selection of first re-computing the ?(O,) by conformalizing on Drats and then choosing the iterate with the best average set size also on Deal. before feeding into the reconformalization step with Drecal- As the Deeall is only used in the reconformalization step, such as method still guarantees valid coverage like the original Algorithm
We compare above algorithm against two baselines: conformalizing each individual model and reporting the best one, or conformalizing the uniform ensemble (which uses weights Ounif = + lx). For these two baselines, for fairness of comparison, allow them use the whole Deal Drecal as the calibration set, as their construction (apart from pre- to-iiraiiin) is not data-dependent.
Results Table shows that our algorithm is able to learn label prediction sets with valid coverage and improved set sizes the baselines. This demonstrates the advantage of our method even in applications where the efficiency loss (here set size) is non-differentiable and needs to be further approximated to allow gradient-based algorithms.
22

---

Published as a conference paper at ICLR 2022
G ABLATION STUDIES
G.1 CONFORMAL QUANTILE FINETUNING
We report ablation results for the conformal quantile finetuning problem with nominal coverage level f80%, 95%), and otherwise exactly the same setup Section 5.1. The conclusions are qualitatively the same as the 90% version presented in Table 1.
Table 6: Results for conformal quantile finetuning on real-data regression tasks at level 1 80%. For each method report the (test) coverage, length, and pinhall loss of the corresponding base quantile predictor. All results are averaged over 8 random sceds.
CQR
CP-Gern-Recae (ours)
Dataset
Coverage($6)
Length
L pinhall
Coverage(%))
Length
L pinball
MEPS_19
80.42
0.702
0.154
80.45
0.514
0.190
MEPS 20
80.44
0.707
0.161
80.48
0.466
0.200
MEPS 21
79.91
0.696
0.151
79.85
0.618
0.192
Facebook_1
80.38
0.348
0.072
80.01
0.198
0.137
Facebook.2
79.96
0.329
0.063
79.80
0.189
0.138
kin8nm
79.59
0.865
0.119
78.69
0.832
0.125
naval
79.91
2.777
0.311
79.76
2.721
0.311
bio
80.07
1.791
0.222
80.54
1.674
0.248
blog data
80.64
0.399
0.082
80.10
0.272
0.158
Nominal (1 a.)
80.00
80.00
Table 7: Results for conformal quantile finetuning real-data regression tasks at level 1 95%. For each method report the (test) coverage, length, and pinball loss the corresponding base quantile predictor. All results are averaged over 8 random seeds.
CQR
QR + CP-Ger -eer.--ecaa. (ours)
Dataset
Coverage(Sh)
Length
pinball
Coverage(%))
Length
T.lest 'pinball
MEPS_19
94.60
1.674
0.078
95.10
1.292
0.091
MEPS_20
94.72
1.650
0.081
94.78
1.261
0.097
MEPS 21
94.64
1.633
0.071
94.99
1.351
0.086
Facebook. 1
94.96
0.797
0.036
95.04
0.601
0.061
Facebook
95.17
0.700
0.031
94.98
0.560
0.060
kin8nm
95.15
1.602
0.047
94.95
1.557
0.048
naval
94.87
3.308
0.084
94.83
3.265
0.088
bio
95.17
2.698
0.073
95.22
2.587
0.084
blog.data
95.07
0.862
0.040
95.09
0.744
0.068
Nominal (1 o)
95.00
95.00
G.2 MULTI-OUTPUT REGRESSION
We report ablation results for the multi-output regression problem with nominal coverage level a E (80%, 95%), ) and otherwise exactly the same setup as Section 5.2. The conclusions are qualitatively the same the 90% version presented in Table 2, except for one dataset at level 95%.
G.3 COMPARISON OF Ce-Gen AND CP TP-Gen- Reca-
We compare the performance of CP CP-Gen and -P-Gen-Reed using the same setup as Section 5.2. Recall that the vanilla CP-Gen optimizes both (0, i on Deal (we additionally reconformalize on the same Deat to address the potential bias 7 brought by the approximate optimization (8)), whereas our main CP-Gen-Recal algorithm optimizes on Deal and reconformalizes frecal on Drecal-
the multi-output regression tasks
Table 10 reports the results. Observe that, except for the volume dataset (Humanoid), there is no significant difference in both the coverage and the volume for the two methods. For practice we recommend CP-Gen -eccal whenever the exact coverage guarantee is important, yet this result
23

---

Published as a conference paper at ICLR 2022
Table Results multi-output regression on next-state prediction tasks, at a 80%. each method we report the (test) coverage and volume its learned box- soxped prediction set. The reported volume is the "halfened" version dou uj- All results averaged over 8 random seeds.
Coord-winn
Coord-wise Reecalle-Reca
CP-Gen-Recal (ours)
Dataset
(overage((k)
Volume
Coverage(%)
Volume
Coverage(%))
Volume
Cartpole
87.82
1.74 x 10-6
80.08
7.83 x 10-7
80.09
7.45 x 10
Half-Cheetah
88.28
4.26 10
79.96
2.42 10
80.04
1.37
10
Ant
87.77
1.97 x 10
80.12
3.97 x 10 10-7
80.06
1.75 x 10
Walker
90.25
5,88 10-7
80.28
3.13 10
80.28
1.45 10
Swimmer
91.49
1.33 x 10-6
79.99
6.18 x 10-6
79.97
4.32 x 10
Hopper
86.47
3.25 X 10
79.87
7.40 x 10-11
79.97
4.41 x 10
Humanoid
90.84
2.86
10"7
80.05
9.47 x 10-13
80.02
2.41
Nominal .))
80.00
80.00
80.00
Table Results multi-output regression on next-state prediction tasks, at a 95%. each
method we report the (test) coverage and volume its learned box-shaped prediction set. The reported volume the "halfened" version Ioon uç- All results averaged over 8 random seeds.
Coord-uv wise
Coord-w se Recal
CP-Gen-Recal (ours)
Dataset
Coverage( (
Volume
Coverage(%)) (%)
Volume
Coverage($6)
Volume
Cartpole
97.21
1.07 x 10 10-4
95.10
4.60 x 10-5
95.12
8.61 x 10 6
Half-Cheetah
96.80
2.37 10-
95.03
4.03 10
95.01
3.29 10
Ant
96.65
5.30 x 10
95.02
4.87 x 10
95.09
2.39 x 10
Walker
97.01
8.08 x 10
94.94
6.21 10
94.99
4.27 x 10
Swimmer
97.74
3.44 x 10
94.95
3.77 x 10 10-5
95.01
5.34 x 10
Hopper
96.27
1.76 x 10-8
94.96
8.23 x 10
94.96
1.19 x 10
Humanoid
97.22
3.58 x 10
94.99
7.69 x 10
94.91
7.49
Nominal (1
95.00
95.00
95.00
shows that that-perhaps originating from the fact that here Viaal = 20000 is large-the coverage (gen- eralization error) of CP-Gen is also nearly valid, which may be better than what our Proposition suggests.
Table 10: Comparison of CP-Gen and CP-Gen-Recae on the multi-output regression tasks. The reported volume the "halfened" version Yout w.
CP-Gen-Rewe Recal
CF CF-Gen
Dataset
Coverage(%)
Volume
Coverage (%)
Volume
Cartpole
90.12
2.30 x 10
90.09
2.30 x 10
Half-Cheetah
90.02
9.07 10-7
89.96
8.83 x 10
Ant
90.02
8,25 x 10
89.98
8.21 x 10
Walker
89.94
3.47 10-7
89.91
3.30 x 10-7
Swimmer
90.13
1.46 x 10
89.96
1.29 x 10-7
Hopper
89.92
8.25 x 10-10
89.92
8.23 10-10
Humanoid
89.94
4.95 x 10
90.05
7.08 x 10
Nominal
90.00
90.00
24

---

Published as a conference paper at ICLR 2022
H ADDITIONAL EXPERIMENTS AND ANALYSES
H.1 CONDITIONAL COVERAGE OF CP-Gen-Recal
We analyze the improved length prediction intervals learned by CP- Ce-Gen-Recal (Section 5.1) by evaluating its conditional coverage metrics and comparing with the baseline CQR method.
As conditional coverage hard to reliably estimate from finite data, consider proxy metrics proposed in (Feldman et al., 2021) that measure the independence between length and indicator of coverage:
The correlation coefficient (Corr) between the following two random variables: the interval size
L = length(C((X)) and the indicator of coverage = = E ) A (population) corre- lation of 0 necessary (but sufficient) condition of perfect conditional coverage (Feldman et al., 2021). Here we measure the absolute correlation, which is smaller the better.
HSIC: A more sophisticated correlation metric between and V that takes into account nonlin- correlation structures. A (population) HSIC of 0 is necessary and sufficient condition of the independence between and V. We estimate HSIC on the finite test data using the method in (Feldman al., 2021).
Table 11 reports the results. Observe that while our Gen-Recal improves the length, achieves worse (higher) Correlation/HSIC than the baseline COR, which expected length and conditional coverage often come trade-off.
Table 11: Conditional coverage results for conformal quantile finetuning on real real-data regression tasks at level 1 90%. For cach method report the (absolute) correlation coefficient as well as the HSIC metric between length and indicator of coverage. All results averaged over random seeds.
CQR
QR CP Gee--en-iie Gen-Recal (ours)
Dataset
Corr(L)
HSIC(L)
Length([)
Corr(L)
HSIC(L)
Length(L)
MEPS_19
0.022
3.03 x 10 5
1.167
0.049
1.77 x 10
0.890
MEPS 220
0.032
3.63 10
1.165
0.113
2.66 10
0.830
MEPS 21
0.029
4.72 x 10
1.145
0.068
2.20 x 10
0.962
Facebook_1
0.029
1.27 10
0.555
0.175
7.34
10
0.384
Facebook.2 2
0.024
1.16 x
0.491
0.116
2.68 10
0.364
kin8nm
0.031
4.85 x 10
1.214
0.084
9.32 10
1.173
naval
0.091
1.05 x 10
3.095
0.064
2.16 10
3.077
bio
0.026
4.15 X 10
2,271
0.041
1.09 10
2.164
blog_data
0.013
4.60
10-5
0.605
0.141
5.75
10
0.496
H.2 ALTERNATIVE TWEAKS CQR BASELINE
Here we test two additional tweaked versions of the CQR baseline in the prediction interval experi- ment of Section 5.1:
CQR-Derain U Deat: Use dataset Dirain U Dral for training the base quantile regressor, then
conformalize on Drecal-
CQR-Pinba 11Ft: llFt: Train the base quantile regressor Derain, and finetune the last linear layer on Deal using the pinball loss (same as training), and conformalize on Drecal-
Optimization details about these two methods are described in Section H.2.1.
Result Table 12 reports the results for these two tweaked baselines. in comparison with our orig- inal baseline CQR as well as our proposed QR CC-CCC----B----- Gen-Re Observe that using more train- ing data (CQR-Dtrain U Deat) improves the length slightly some datasets but not all. In con- trast, CQR-P 1ittllFF coR(observe that PRR-PinballFt uses the same set of training data as COR-Durain Deal but uses a less expressive model in the finetuning stage). Overall, on almost all datasets (except for kin8nm), our CP-Gen- still achieves the best length.
unable to improve either the pinball loss or the length over the base
25

---

Published as a conference paper at ICLR 2022
Table 12: Results conformal quantile finetuning data regression at level 1-a 90%. Here we compare our Ce-Gen Reccal method with tweaked versions of the baseline CQR method. All results are averaged over the same 8 random seeds in Table 1. All (average) coverages are within (90 + 0.5) % and omitted here.
Sqa-Dirain
CQR- Darin U Deal
CQR-Pinballrs
QR + GP-Gen-Recal (ours)
Dataset
Length
Test L pinbsll
Length
Lest pinbbal
Length
test L pinball
Length
teus pinbsll
MEPS. 19
1.167
0.112
1.171
0.111
1.192
0.112
0.890
0.131
MEPS 20
1.165
0.117
1.179
0.114
1.190
0.117
0.830
0.141
MEPS 21
1.145
0.107
1.150
0.106
1.249
0.107
0.962
0.129
Facebook. I
0.555
0.052
0.549
0.051
0.578
0.052
0.384
0.090
Facebook
0.491
0.044
0.472
0.042
0.523
0.044
0.364
0.092
kin8nm
1.214
0.076
1.165
0.072
1.232
0.075
1.173
0.078
naval
3.095
0.164
3.089
0.164
3.096
0,164
3.077
0.166
hio
2.271
0.130
2.240
0.128
2.271
0.130
2.164
0.148
blog_data
0.605
0.058
0.551
0.056
0.660
0.058
0.496
0.107
H.2.1 OPTIMIZATION DETAILS
CQR-Dtrain Deat: Our original CQR baseline used Deal for monitoring validation loss and lomatically determining the early stopping (cf. Section E.1). and Drecal for conformalization. To optimize on Dirsin U Deal, we do not use automatic learning rate decay and early stopping, but in- stead manually picked the number of epochs and corresponding learning rate decay schedule that is close to average runs of the CQR method on each dataset. This choice ensures that our new baseline still gets to use see the exact same amount of data for conformalizing (Drecat) and testing (Drest), and has a optimization setup as close as possible the original CQR baseline.
More concretely, we optimize for 800 epochs for (MEPS 19, MEPS 20, MEPS 21), 1,500 epochs for (Facebook_i Facebook blog_data), 6000 epochs for kin8nm, 350 epochs for naval, and 2500 epochs for bio. For all datasets, the learning rate decays by 10x twice, at 90% and 95% of the total epochs.
CQR-Pinball lFtt: We finetuned on Deat with 1000 epochs and batch size 256. The learning rate was chosen within {10 - 10 10-3) and the results are not too different for these two choices (length difference is within 0.010 for these two choices, and there is overall winner). We presented the results with learning rate 10-3
H.3 ADDITIONAL Max Max-score so-oscrr---oooomme BASELINE FOR MULTI-OUTPUT REGRESSION
We test one additional baseline method for the multi-output regression experiment in Section 5.2:
Max-score- wwcoorroooooooaaaaa..l.....aa Here we consider the hypercube-shaped predictor
C,(x) = (1) tt)
(16)
and use conformal prediction on Deal Droeal to compute conformalized 7 and the final prediction set Cz(2). In other words, we perform standard conformal prediction with score function - fxx)
remark that both the Coord-wise Rice-Raall and the Max seee-score-CCee -cnoor-aa baseline methods special instances of CP-Gen-Recalwith some fixed 0g: In our parametrization, u = (H,t), determines the shape (i.e. relative ratios between the u(s) whereas determines the size. Therefore, wwa---cor--oofffreoe
can be thought of choosing to be the all-ones tio (i.e. hypercube-shaped), whereas Coord-w" se-Re ce-Reca can be thought of as choosing Op from coordinate-wise dimensional conformal prediction.
Result Table 13 reports the result for Max-scorre-Confozmall Compared with the exist- ing baseline Goord-vise-Reca Max-score secore-Conformall achieves better volume on the Cartpole dataset but worse volume almost all other datasets (except for Swimmer where their
26

---

Published as a conference paper at ICLR 2022
volumes similar). Further, note that Max-scoreeConnoorall achieves significantly higher volumes for certain datsets (Ant, Humanoid). Our inspection shows that this due to the fact that there are certain number of hard-to-predice state dimensions (and many other casy-to-predice state dimensions) for these two datasets. Therefore, Coord- Re-Reca -eeeReeee which builds on Coord-wi se adapts this structure and uses only high length on these dimensions only, whereas the Max-score Con-ooonoraaaaa method pays this max conformal score on all dimensions to yield an unnecessarily high volume.
We remark that our CP-Gen 1e-Gen-Recal still performs significantly better than both baselines.
Table 13: Results for multi-output regression on next-state prediction tasks, at level 1 - 90%. The setting is the same in Table (with the same 8 random seeds), and here compare additionally with the Sexx-score-Coffoooee baseline method described (16).
Coord-wise-Recal
Max-score -ocooreeCoooomaaal
CP-Gen-Recal (ours)
Dataset
Coverage(%)
Volume
Coverage(%)
Volume
Coverago(%))
Volume
Cartpole
90.17
5,10 x 10
90.10
3.07 x 10-6
90.12
2.30 x 10 6
Half-Chectahi
90.06
1.23 x 10
89.96
1.72 x 10-4
90.02
9.07 10
Ant
89.99
1.70 x 10-4
90.06
3.46 x 102
90.02
8.25 x 10 10-5
Walker
90.01
7.33 x 10
90.02
1.03 x 10
89.94
3.47 10
Swimmer
89.90
2.22 x 10
90.08
2.21 x 10-6
90.13
1.46 x 10-7
Hopper
90.02
1.01 x 10-9
89.96
1.29 x 10
89.92
8.25 x 10
Humanoid
89.95
8.53 x 10
89.98
2.48 x 10
89.94
4.95 x 10
Nominal (1 o.)
90.00
90.00
90.00
H.4 100 RANDOM SEEDS AND STANDARD DEVIATION
Here we repeat the experiments in Section 5.1 & 5.2 with 100 random seeds and the exact same se- tups. We report the mean and standard deviations Table 14 for the prediction intervals experiment (Section 5.1), Table 15 for the mean and Table 16 for the standard deviation for the multi-output regression experiment (Section 5.2).
Table 14: Results for conformal quantile finetuning on real-data regression tasks at level - = 90%. For each method we report the (test) coverage, length, and pinball loss of the corresponding base quantile predictor. All results are averaged over 100 random seeds.
CQR
QR + CP-Gen-Ro-eoeooo (ours)
Dataset
Coverage(Sb)
Length
L
test pinball
Coverage %))
Length
test pinball
MEPS_IV .99
89.92 1.16
1.147
+0.057
0.107 #0.013
89.95 #0.012
0.895 + 0.126
0.130 #0.015
MEPS 20
89.90 #0.98
1.164
#0.054
0.109 +0.012
89.97 #0.011
0.872 + 0.113
0.131
#0.015
MEPS_2.
90.00 +0.94
1.162 +0.056
0.104 +-0011
90.08 +0.011
0.910 + 0.133
0.126 +.0013
Facehook
90.12 +0.71
0.540 +0.040
0.050 +0.007
90.07 +0.007
0.382
0.051
0.089 +0.009
Facehook
90.04 +0050
0.497 +0.028
0.044 400005
90.06 +0.005
0.389 0.075
0.091 +0.007
kinSnm
90.34 1.37
1.238 10.067
0.076 10.004
90.31 #0.013
1.21610.00
0.080 10.004
naval
89.99 1.13
3.101 10.015
0.164 10.001
89.95 10.011
3.095 1 0.028
0.167 10.001
bio
90.00 10.69
2.261 10.033
0.130 10.002
89.97 10.005
2.154 0.031
0.148 10.003
blog-dam -daaaaaa
89.99 10.60
0.593 10.033
0.058 10.005
89.95 10.007
0.460 0.075
0.104 10.006
Nominal a))
90.00
90.00
27

---

Published as a conference paper at ICLR 2022
Table 15: Results for multi-output regression (mean) on next-state prediction tasks, at level 1 90%. For each method report the (test) coverage and volume of its learned box- sox-shaped prediction set. The reported volume is the "halfened" version
I 14. All results are averaged over 100 random seeds.
Coord- w se
Coord-w se- Recal
CP-Gen-Reca (ours)
Dataset
Coverage(%)
Volume
Coverage(%)
Volume
Coverage($6)
Volume
Cartpole
94.30
1.14
10-3
90.02
4.80
10-8
90.03
2.05 10
Half-Chectah
93.84
1.05 x 10
90.00
1.22 x 10-6
90.02
9.01 x 10
Ant
93.53
3.26
10
89.94
1.75 10
89.98
9.22 10
Walker
94.52
2.82 x 10
89.99
7.48 x 10-7
90.00
3.74 x 10
Swimmer
95.65
2.82
10-5
90.02
2.18 10
90.01
1.24 10
Hopper
92.95
2.53
10-9
89.98
8.86
10-10
89.99
7.04
10-10
Humanoid
94.87
7.43
10
90.06
1.69 x 10
90.03
8.95 x 10
Nominal (1 o)
90.00
90.00
90.00
Table 16: Results for multi-output regression (standard deviation) on next-state prediction tasks, at level 1- 90%. For each method we report the (test) coverage and volume of its learned box box-shaped prediction set. The reported volume is "halfened" version dous ug. standard deviations are computed over
random seeds.
Coord-wise
Coord-win se se-Recal
CF CF-Gen-Reca (ours)
Datasct
Coverage(%)
Volume
Coverage($6)
Volume
Coverage($))
Volume
Cartpole
0.35
3.57 x 10
0.31
1.33 10
0.27
4.46 10-7
Half-Cheetah
0.25
2.46 x 10
0.32
2.75 x 10-7
0.31
2.10 x 10
Ant
0.27
1.50 x 10-3
0.29
8.06 10
0.29
4.15 10-5
Walker
0.24
8.81 x 10
0.30
2.18 x 10
0.29
1.12 x 10
Swimmer
0.24
6.47 x 10
0.29
5.83 10-7
0.33
3.36 10
Hopper
0.29
6.83 10-10 10
0.29
2.26 x 10
0.33
1.97 x 10
Humanoid
0.23
1.22 x 10
0.30
2.71
10
0.29
1.47
10
28


Reviews:
[{"review_id": "y54CMMFSuN", "reviewer": "Reviewer_3LHz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my review I would like to address each of the evaluation criteria.\n\nTechnical novelty and significance: \n\nThe presented idea is novel and interesting. It is well supported by theoretical arguments and experimental results. It is interesting to see that the bound on coverage becomes weaker when the complexity of the space over which is optimized increases. This is in fact a natural result.\n\nThe presented idea is in fact quite similar to this ICML paper: https://arxiv.org/pdf/1802.07167.pdf. Similarly as the Lagrange formulation in Eq. 8, in that paper an optimization problem that incorporates both efficiency and coverage is introduced, but the objective function is a bit different. It would be interesting to compare empirically with that method.\n\nEmpirical novelty and significance: \n\nThe experiments show what they need to show, i.e. that the proposed method is better than conformalized quantile regression. However, the results reported for CQR are a bit worse than those reported in https://arxiv.org/pdf/2107.00363.pdf (look for the datasets that are reported in the two papers). It is not so clear why that is the case.\n\nThe experiments for multi-output regression and multi-class classification are a nice add-on to illustrate the broad applicability of the presented method, but they are not essential for the paper.\n\nCorrectness: \n\nThe theoretical look correct, but at some stages the readability could be improved:\n\nProposition 2a looks a bit awkward because the inequality has on the left side an average over all randomly drawn calibration sets, whereas the right hand side is about a specific calibration set. I would suggest to add \"for any calibration set D_cal\" to the beginning of the proposition.\nI don't understand why epsilon_zero is included in Algorithm 1. The authors mention in Section 3.1 \"for analysis purposes\", but which analysis is this? Perhaps this could be removed to improve readability.\nThe experimental results have some minor issues w.r.t. which baselines are considered and how these baselines are tuned (see above). However, I don't see a problem with the main message of the paper.", "summary_of_the_paper": "This paper introduces an extension of conformal prediction with a different formulation. Instead of guaranteed coverage for a finite calibration set, the authors solve a constrained optimization problem where the length of prediction intervals is minimized subject to a coverage constraint. As a result, coverage is only asymptotically guaranteed, but instead the length of the prediction intervals can be shortened compared to traditional split conformal prediction. \n\nThe authors present theoretical results in the form of coverage bounds for specific function classes. \n\nIn the experiments classical regression datasets are analyzed, as well as multi-output regression problems and one multi-class classification problem. ", "summary_of_the_review": "Interesting paper. Some minor issues w.r.t. comparison with existing work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "smge_-Pm1e", "reviewer": "Reviewer_bDLk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There are a number of strengths that I quite like about this paper: \n- The paper is exceptionally well written and clear to read. \n- The core idea itself is appealing: strict adherence to proving marginal (or other) coverage for set-based classifiers, which generally relies on preserving exchangeability, is generally a good thing, but can be limiting/overly conservative. It is useful to formalize what practitioners stand to gain/lose by directly optimizing conformal predictors for efficiency.\n- The framework itself is fairly simple (which is a nice thing), and empirically improves over a good CQR baseline. \n\nThere are, however, some weaknesses, and I do have a few questions/concerns. \n\n- A minor point: though it is nice to formalize Propositions 2-4 (and they are nicely stated and proven), from a practical point of view $\\epsilon_{\\mathrm{coverage}}$ and $\\epsilon_{\\mathrm{eff}}$ are still quite loosely bounded and its unclear how much value they really add. As a practitioner, as a rule of thumb I already know that my train performance will roughly generalize well to my test performance if my model is low capacity and my data sample is large. The bounds given in Props. 3 & 4 might be too large to be practically useful, i.e., if I was setting $\\alpha' = \\alpha - \\epsilon_{\\mathrm{coverage}}$ based on this analysis. (I also appreciate the use of absolute constant C to clean up notation, but it does make the bound looser/not directly computable). \nThat said, I understand that as positioned in this paper, these theoretical results are intended to formalize that stated \"rule of thumb\", i.e, that \"we may expect $\\texttt{CP-Gen}$ to generalize well [...] whenever it learns $K \\ll n_{\\mathrm{cal}}$ parameters,\" though it may be good to qualify this result more.\n\n- I don't think this was mentioned: the proof of Proposition 2 (and others) relies on $D_\\mathrm{cal}$ being i.i.d., which is slightly stricter than exchangeability (required for standard CP).\n\n- It is interesting from Table 1 that the quantile loss increases after optimizing $\\texttt{CP-Gen}$. An advantage of CQR is that it is adaptive to local variability. In this sense, it can achieve better approximate conditional coverage than a fixed interval. Do you lose any of this when you train $\\texttt{CP-Gen}$?\n\n- The length numbers in Table 1 seem quite a bit lower than those reported in the CQR paper (for example, Fig. 3 in CQR lists the best meps_19 result at 2.36, vs the 1.167 reported in your Table 1). Can you explain this difference? At the same time, it would be good to understand how much optimizing for $\\texttt{CP-Gen}$ actually helps over choosing better base predictors with favorable properties (e.g., see [Conformal Prediction using Conditional Histograms](https://arxiv.org/abs/2105.08747) which improves over CQR on many of the same datasets reported here).\n\n\n\n=== Minor Comments ===\n\n- At the start of Sec. 3.2 you define $L_{\\mathrm{eff}, \\mathrm{coverage}}$  as the expected i.i.d. sample mean, which is equal to the true population average. However, I do find the notation slightly confusing (in terms of expectation over $D_{\\mathrm{cal}}$) with what would be the train accuracy on $D_{\\mathrm{cal}}$ after solving the optimization problem. In Section B.2 you write L in terms of $\\mathbb{E}[l_\\mathrm{eff} (C_{\\theta, t}); (X, Y))]$ which I find preferable and would recommend that you could simply use here as well.\n\n-  Typo: when bounding $\\epsilon_{\\mathrm{eff}}$ in the proof Prop. 3, it should be $L_{\\mathrm{eff}}$ instead of $L_{\\mathrm{coverage}}$.\n\n- For clarity, it might be good to formally define $\\epsilon_i$ as Rademacher r.v.'s when applying the symmetrization argument in the proof of Prop 3.  \n\n- I would suggest reconsidering the use of \"exact coverage\" in Section 3.3, as this can be conflated for the case where the bound $\\mathbb{P}(Y \\in C(X)) \\geq 1 - \\alpha$ holds with equality.\n\n- Typos, bottom of page 7: \"$\\hat{t}_{\\mathrm{recal}}$ to _guarantee_ coverage\" and \"emphasize that the _approximation_ in (8)\".\n\n- Typo, Section 5.1: I believe you mean to include $+ t$ in the upper interval bound of $C_{\\theta, t}$.", "summary_of_the_paper": "This paper generalizes the standard conformal prediction calibration setup to a constrained empirical risk minimization problem. Specifically, this work seeks to optimize some efficiency loss, while satisfying coverage constraints. This formulation allows for the introduction of multiple, learnable parameters which can help find a better set-based predictor. The paper explains the implications of this approach by analyzing the generalization error that may occur when transferring the solution learned by constrained ERM to a test population. It also explains practical ways of learning this problem via differentiable surrogate losses and Lagrangians. Contributions-wise, the paper contributes validating theoretical analysis that proves that this method can achieve approximate coverage and near optimal efficiency for certain set-function classes. It also empirically shows that the proposed method can improve over baselines that are not directly optimized for efficiency. ", "summary_of_the_review": "In general, the paper is well-written and the idea is appealing. As mentioned in the main review, it would be good to understand more about the solutions that the proposed method finds and what (if anything) they might be sacrificing (e.g., conditional coverage). It would also be good to compare to somewhat more recent baselines (e.g., CHR for regression, RAPS for classification).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZX7NrEYKwCM", "reviewer": "Reviewer_G6jH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n1. The paper considers an important and interesting issue (i.e., maximizing efficiency of conformal prediction).\n2. The proposed approach is evaluated over various setups and datasets (i.e., 9 regression datasets, 7 multi-out regression datasets, and 2 classification datasets).\n\n\n**Concerns:**\n1. I agree that reducing size in conformal prediction is important issue, but the way that this paper considers this issue is currently less motivational; one beauty of (inductive) conformal prediction is that it isolates the issue of choosing the score function and the issue of constructing a conformal predictor---i.e., the guarantee of the constructed conformal prediction holds for any score functions. This implies that we can isolate the task of learning the score function by empirical researchers and the task of conformal predictor construction by theory researchers. Moreover, as we have a better score function (e.g., by devising better network architectures), the size of a conformal predictor is naturally reduced---this can be easily verified if the score function is perfect (e.g., true classifier in classification). However, the proposed approach mixes up the two isolated procedures and making it complex for getting better conformal predictors. What's the problem of designing a better score function to get efficient conformal predictors?\n\n2. Related to above issue, important motivational experiments are missing; for example, in the experiment of Table 1, CQR could be more efficient in terms of interval size by including D_{cal} into D_{train} (i.e., improving the score function by having more training samples); here hyperparameters can be chosen as the paper chooses for \\theta. (1) what's the performance of CQR where the quantile regressor is trained over D_{cal} + D_{train} with pinball loss? (2) what's the performance of CQR where the quantile regressor is trained over D_{train} with pinball loss and then the last layer is fine-tuned over D_{cal} with the same pinball loss?\n\n3. for all experiments, I think the variance statistics over random trials would be necessary to show the significance of the proposed approach. Also, the current number of random trials (i.e., 8) is small; I do believe that the paper could be stronger if the proposed approach is evaluated over larger trials (e.g., 100), which is possible if a score function is trained only once with a fixed training set as in inductive conformal prediction. As in the current form, I'm not sure if we can compare lengths among approaches without having the same or very similar coverage---as mentioned in the paper, coverage also affects on the efficiency, so the better efficiency could be due to some randomness of calibration splits.\n\n4. Section 1.1 \"Both works formulate this task as a risk minimization problem\": I think the earlier work [R1] already consider conformal prediction in the ERM framework, where it also allows any function class and efficiency loss, along with one-parameter special case as their approach; it's better to acknowledge similar prior work and mention differences.\n\n5. \"3.2 Theory\" is not well connected to the final algorithm; basically the proposed algorithm is (1) fine-tune the score function with a proper efficiency loss and (2) run a known conformal prediction for coverage guarantee. What's the novelty compared to known analyses on the generalization bound? \n\n6. In Table 5, it's better to add comparison results to make the results stronger; the standard conformal prediction can be applicable here.\n\n*[R1]: https://arxiv.org/abs/2001.00106", "summary_of_the_paper": "This paper considers to improve efficiency of conformal prediction (measured in the \"size\" of prediction sets). To this end, this paper uses multiple-learnable parameters by generalizing single-parameter conformal prediction. By doing so, the paper demonstrate that the proposed approach can improve the efficiency of conformal predictors while satisfying valid coverage. The efficacy of the proposed approach is demonstrated over regression, multi-output regression, and classification.", "summary_of_the_review": "This paper considers interesting and important problem, and the proposed approach is broadly evaluated; but as mentioned in the main review, I lean to reject though I'm willing to adjust my understanding and score.\n\n\n\n==== POST-REBUTTAL ==== \n\nThanks for the additional discussion and experiments; I think the response mostly addressed my concerns so raise my score to 6. To my understanding, the key message of this paper is that finetune a base predictor with respect to a desired length metric (along with a coverage constraint) if we want to improve the efficiency (in the same length metric) of the final conformal predictor given fixed sample size; this is likely to be true and is more convincing given the additional experiments. As one minor note, [R1] is applicable to both classification and regression as demonstrated in their experiments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CNOtS2AI8-p", "reviewer": "Reviewer_Pu7a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\nThe paper is a useful sequel to the earlier work of Yang & Kuchibhotla (2021). Now that more people are aware of conformal methods, it makes sense to develop methods that incorporate tuning of learning algorithms with the goal of obtaining the most precise predictive confidence sets.\n\n## Weaknesses\n\n1. *Clarity*: Definitions or details that are important for understanding the paper are frequently postponed without warning.\n\n- The explicit meaning of *parameter* (as in \"a single parameter\" or \"multiple learnable parameters\") is left unspecified till p. 4, where the problem is formally described. At the same time, it seems eminently possible to communicate the content of earlier pages using more intuitive language. For example, consider the following sentence: \"Conformal prediction is a powerful technique for learning prediction sets with valid coverage, yet by default its conformalization step only learns a single parameter, and does not optimize the efficiency over more expressive function classes.\" All this is saying is that the existing approaches treat the learning algorithm as completely fixed (so that conditional on the observed data, there is only one set prediction map for each confidence level), whereas the proposed methods aim to find the most precise set prediction map over a *collection* of learning algorithms, where the collection is allowed to be uncountably infinite.\n\n- Similarly, the question of where the extra parameter $\\theta$ is coming from or how it may arise is not addressed till p. 8. For example, Figure 1 has less impact because it cannot be clear to the reader at the time what $\\theta$ represents in the context of CQR. As a result, the paper reads mainly like a purely theoretical exercise until concrete instances of $\\theta$ are finally given in the last sections. (This is just a suggestion, but consider starting the paper with a concrete example from Section 5 that is well-defined.)\n\n- The descriptions of the experimental setups ought to be more clear, too. For example, it is doubtful how much of Section 5.1 can be understood *without* Romano et al. (2019). The symbols $\\hat F$, $\\hat f_{\\text{lo}}$, $\\hat f_{\\text{hi}}$, etc. do not appear to be defined anywhere, and the symbol $d_h$ is defined 7 lines after its first occurrence. I also do not understand what the authors mean by \"1r decay.\"\n\n- I am confused about the experiment in Section 5.2. In light of the stated motivation for the proposed method, I would have thought that the interesting comparisons are the ones in which first, a parametric family of learning algorithms is fixed, and then the method that does this for a fixed $\\theta_0$ is compared to the proposed method that learns an optimal $\\hat \\theta$. It is not clear to me if the two baseline methods are comparable in this manner. (By the way, a slightly less naive method that adapts to the correlation structure would probably utilize the maximum statistic, e.g., $\\|Y - \\hat f(X)\\|_\\infty$, rather than a Bonferroni bound.)\n\n2. *Balance / Completeness*: The paper actually proposes *two* meta-algorithms: CP-Gen and CP-Gen-Recal. The theory sections are almost exclusively concerned with CP-Gen (with the exception of Section 3.3), whereas the experimental results are only reported for CP-Gen-Recal. This has created an odd imbalance in the manuscript. I feel like either the experimental results for CP-Gen ought to be included in the paper as well as the content of Appendix G.3, or most of the material pertaining to CP-Gen ought to be moved to the appendix.\n\n3. *Originality*: As of writing, I am still trying to decide whether the contributions of this paper are substantial enough in light of the contributions of earlier works. From the point of view of theoretical validity, many of the ideas here appear to be already present in, say, Yang & Kuchibhotla (2021), although it is true that they have not been worked out at this level of detail. On the other hand, from the point of view of practical implementation, optimizing over an arbitrary and large $\\Theta$ is a nontrivial challenge, and the authors do well to borrow from a different line of uncertainty quantification literature. This may well be a matter of emphasis or branding. In any case, I would like to hear other opinions on this point.\n\n## Typos\n- (p. 5. The line above Section 3.2) $\\epsilon = 0$ -> $\\epsilon_0 = 0$.\n- (p. 9. The line after the itemized list) Our datasets is -> Our datasets are\n- (p. 9. **Additional experiment**) The citation for the ImageNet dataset is incorrectly given as (Angelopoulos et al., 2020).\n- (Section B.2 from after Eq. (11)) $\\hat L_{\\text{coverage}}$  -> $\\hat L_{\\text{eff}}$ and $L_{\\text{coverage}}$  -> $L_{\\text{eff}}$ throughout\n- (Section B.3) $R_n(\\mathcal{C})$ is used, but $R^{\\text{eff}}_{n{\\text{cal}}}(\\mathcal{C})$ was given on p. 6.\n- (p. 16, Paragraph 4) a shortest prediction interval -> the shortest prediction interval\n- (p. 17. The last unnumbered display equation) Remove , from the subscript.\n- (p. 18. The line after the first unnumbered display equation) Add \"by\" between \"and\" and \"the assumption.\"\n- (p. 18) $F_{\\hat \\theta}$, $\\hat F^{\\text{cal}}_{\\hat \\theta}$, etc. all look too similar, making the proof unnecessarily difficult to read.\n- (p. 21) On p. 3, $K$ was used to denote the number of classes. Here, $L$ is used to denote the number of classes, and $K$ now represents the number of base predictors in an ensemble.\n- (p. 21) $p$ in the exponent can be confused with $p_\\theta$.\n- (p. 21) In **Methods for learning prediction sets**, $i$ denotes the epoch count. However, $i$ is already being used to denote a single base predictor in an ensemble.", "summary_of_the_paper": "This paper proposes conformal methods for learning a predictive confidence set that is guaranteed to be nearly the most statistically efficient among predictive confidence sets produced by a parametric class of learning algorithms. To explain, many wrapper methods for assessing prediction uncertainty assume that the user has already committed to one particular learning algorithm and aim to quantify uncertainty in predictions produced by using *this* learning algorithm. By contrast, the methods proposed here assume that the learning algorithm has been specified only up to some parameter $\\theta$ so that it makes sense to optimize $\\theta$ with respect to the precision of the resulting predictive confidence sets.\n\nFrom the point of view of practical implementation, the obvious challenge is the optimization of $\\theta$ (as well as the associated prediction sets) over an arbitrary and large space of possible values of $\\theta$, as the optimization involves a hard constraint. Thus, one main contribution of the paper is to propose a differentiable proxy that allows an efficient search over the parameter space. Regarding theoretical guarantees, the paper proves that the original, non-differentiable formulation of one of the methods achieves approximately valid coverage and nearly optimal statistical efficiency when the class of learning algorithms has a low capacity.", "summary_of_the_review": "Overall, I think the paper is a useful extension of some earlier works on uncertainty quantification with an eye towards statistical efficiency. I tentatively recommend it for acceptance with some reservations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes a few practically relevant extensions of the conformal prediction framework, that has recently become popular in the ML community for providing (marginally valid) prediction sets without making distributional assumptions. The conceptual contributions are not major, given existing work --- without recalibration, the main idea of optimizing over two parameters was explored by Yang and Kuchibhotla (and is well understood even before YK, albeit not fleshed out). The current paper generalizes YK, and with the additional recalibration dataset, it is again simply an instance of standard conformal prediction. The optimization via Lagrangians is a nice addition, but it is ultimately a heuristic that performs well in practice. Nevertheless, the paper is well written, and the experiments are well done, making this a good contribution for practitioners. I recommend acceptance, and congratulate the authors on a nice work. 

As a minor note, Remark 1 should not be attributed to [AB21], since it is a well known fact and deserves an earlier reference.
Decision: Accept (Poster)