Length Optimization in Conformal Prediction
Authors: Shayan Kiyani
George J. Pappas
Hamed Hassani
Venue: NeurIPS 2024 poster (2024)
Keywords: Conformal prediction
Conditional coverage
Prediction set size
Uncertainty quantification
Primary area: learning_theory

Abstract: Conditional validity and length efficiency are two crucial aspects of conformal prediction (CP). Conditional validity ensures accurate uncertainty quantification for data subpopulations, while proper length efficiency ensures that the prediction sets remain informative. Despite significant efforts to address each of these issues individually, a principled framework that reconciles these two objectives has been missing in the CP literature. In this paper, we develop Conformal Prediction with Length-Optimization (CPL) - a novel and practical framework that constructs prediction sets with (near-) optimal length while ensuring conditional validity under various classes of covariate shifts, including the key cases of marginal and group-conditional coverage. In the infinite sample regime, we provide strong duality results which indicate that CPL achieves conditional validity and length optimality. In the finite sample regime, we show that CPL constructs conditionally valid prediction sets. Our extensive empirical evaluations demonstrate the superior prediction set size performance of CPL compared to state-of-the-art methods across diverse real-world and synthetic datasets in classification, regression, and large language model-based multiple choice question answering. An Implementation of our algorithm can be accessed at the following link: https://github.com/shayankiyani98/CP.

Length Optimization in Conformal Prediction
Shayan Kiyani, George Pappas, Hamed Hassani
Department of Electrical and Systems Engineering University of Pennsylvania {shayank, pappasg, hassani]@seas hassea......n......e... edu edu
Abstract
Conditional validity and length efficiency are two crucial aspects of conformal prediction (CP). Conditional validity ensures accurate uncertainty quantification for data subpopulations, while proper length efficiency ensures that the prediction sets remain informative. Despite significant efforts to address each of these issues individually, a principled framework that reconciles these two objectives has been missing in the CP literature. In this paper, develop Conformal Prediction with OongghtOptimizziionn (CPL)- a novel and practical framework that constructs pre- diction sets with (near-) optimal length while ensuring conditional validity under various classes of covariate shifts, including the key cases of marginal and group- conditional coverage. In the infinite sample regime, provide strong duality results which indicate that CPL achieves conditional validity and length optimality. In the finite sample regime, we show that CPL constructs conditionally valid predic- tion sets. Our extensive empirical evaluations demonstrate the superior prediction set size performance of CPL compared state-of-the-art methods across diverse real-world and synthetic datasets in classification, regression, and large language model-based multiple choice question answering. An Implementation of our algo- rithm can be accessed at the following link:
Introduction
Consider distribution D over the domain X' x V, where X' is the covariate space and y is the label space. Using a set of calibration samples (X1, Y11 Yi)..... (Xn, Yn) drawn i.i.d. from D, the objective of conformal prediction (CP) is create prediction set C(x), for each input x, that is likely to include the true label y. This is formalized through specific coverage guarantees on the prediction sets. For example, the simplest, and yet the most commonly-use The prediction sets (xx) C y achieve marginal coverage if, for a test sample (Xn+1, Yu+1), we have Pr(Y,++1 E C()++1)) = a. Here, is the given miscoverage rate, and the probability is over the randomness in the calibration and test points.
guarantee is the marginal coverage:
Conformal Prediction faces two major challenges in practice: conditional validity and length ineffi- ciency. Marginal coverage is often a weak guarantee; in many practical scenarios we need coverage guarantees that hold across different pooo-ppouliions of the data. E.g., in healthcare applications, obtaining valid prediction sets for different patient demographics crucial; we often need to construct accurate prediction sets for certain age groups medical conditions. This is known conditional validity- which ideally seeks a property called full conditional coverage: For every x E X' we require
Pr Pr C (X X =1=1-0 a.
(1)
Alas, achieving full conditional coverage with finite calibration data is known be impossible [T3]. Consequently, in recent years several algorithmic frameworks have been developed that guarantee relaxations of 11). However, the prediction sets constructed by these methods
are often observed to be (unnecessarily) large in size [2] 20 21] i.c., it is possible to find other conditionally-valid prediction sets with smaller length. Even in the case of marginal coverage, the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Conformal Calibration
Algerthm
Conformity Score
for (condationll: coverage
Our Framnework
model predictor
Prediction emors
Aims for (conditionali coverage and length efficteccy
Figure 1:
The CP pipeline.
prediction sets constructed by algorithms such as split-conformal can be far from optimal in size. This brings us the second major challenge of CP, namely length efficiency.
Length efficiency is about constructing prediction sets whose size (or length) is as small as possible while maintaining conditional validity. Here, "length" refers to the average length of the prediction sets C(X) over the distribution of X. Length efficiency is crucial for the prediction sets to be informative 25 In fact, the performance of CP methods
closely tied to the length efficiency of the prediction sets in practical applications in decision making making(26]]2) (2)) robotics (20] 21), communication systems 30 31I, and large language models (32 This raises the question of how length and
coverage fundamentally interact. Along this line, we ask: How can we construct prediction sets that are (near-) optimal in length while maintaining valid (conditional) coverage?
In this paper, we answer this question by proposing a unified framework for length optimization under coverage constraints. Before providing the details, we find it necessary to explain (i) where in the CP pipeline our framework is operating, and (ii) the crucial role of the covariate X.
First, we note that the pipeline of CP consists of three stages (see Figure 1 which are often treated separately [8] Training model using training data, designing a conformity score, and constructing the prediction sets. Our framework operates at the third stage, i.c., aim at designing the prediction sets assuming a given predictive model as well as a conformity score. In recent years, various powerful frameworks have been developed for designing better conformity scores [2 24 41
and obtaining conditional guarantees using a given score 1 42 43 The missing piece this
picture is length optimization which is the subject of this paper.
Second, we emphasize that length optimization can be highly dependent on the structural properties of the covariate X. It has been known in the CP community that the structure of X can play a role in
terms of length efficiency and coverage validity (see e.g. 22 35
However, to our knowledge, principled study of length optimization using the covariate X is missing. To showcase the principles and challenges of using the covariate X in the design of prediction sets, we provide a toy example.
Example. Let X' = [-1,- -1.. Assume X is uniformly distributed over X, and Y is distributed as:
-if x < 0, then Y + +((0,)) 2).
and -if x 2 0, then Y +N 1),
see Figure (a). For simplicity, we assume in this example that we have infinitely many data points available from this distribution. As the model, we consider fx) = E[Y X 2| x. As result, considering the conformity score S(x, y) = ly f(x),, the distribution of follows the folded Gaussian distribution: i.e. for < 0 we have D51æ = (N, 2) and for x 2 0 we have Da = [N (0, 1)] - see Figure (b.)). We aim for marginal coverage of 0.9, and consider prediction sets (xx) in the following form:
- < 0: (xx) {u E s.t. S(x.v) S )-), and - if a 2 0: C(x) = (v E R.t. S(a, S (+).
For every value of q+ in the range [1.4, +oo] there exists unique 9- that ensures 0.9-marginal coverage. This provides continuous family of prediction sets, parameterized by q+. all of which are marginally valid, but have different average lengths. Length optimization over this family amounts to minimizing the average length (which is equal to q- + q+) over the choice of q+ Figure (c) plots the average length versus q+- Four lessons from this example are as follows: (i) First, as we see from Figure (c), the optimal-length solution is different from the sets constructed by the Split-Conforma method (for which q- and 4+ are both equal to the 0.9-quantile of the marginal distribution of S). Hence, the structure of the optimal prediction sets depends on the structure of the covariates (in this case the sign of the covariate). It can be shown that the optimal-solution found is the unique globally optimal-length solution among all the possible marginally- valid prediction

---

Daus0
rrobabilo density function
Bner length
spit-contorm
1=2)) (00.))
Pa jlarco
1J) conditional
conditoonl PDF tal
optimal
(b)
(c)
Figure 2: (a) Distribution of the labels conditioned on the covariate x (b) The conditional PDFs. (c) Avg length vs 4+. The red dots correspond to three different marginally-vaiid prediction sets.
sets. Hence, the feature (xx) = sign(z: (z) is crucial in determining the optimal-length sets. (ii) Second, for (4-.9% corresponding to the optimal-length sets, the conditional PDFs take the same value; i.e. p(S - 4- x 2 0) p(S = q | I 0) see ( This is not coincidence, and as we will show, is the main deriving principle to find the optimal sets see Example (.2 below.
Contributions. We develop a principled and practical framework to design length-optimine diction sets that are conditionally valid. We formalize conditional validity using a class of covariate shifts (as in (8). As for the class, we consider a linear span of finitely-man many basis functions of the covariates. This is a broad class; E.g., by adjusting the basis functions we can recover marginal coverage or group-conditional coverage as special cases.
pre-
We develop a foundational minimax notion where the min part ensures conditional validity and the max part optimizes length. In the infinite-sample setting, the solution of the minimax problem is proved to the optimal-length prediction sets, through strong duality result. To design our practical algorithm for the finite-sample setting (termed as CPL), our key insight is to relax minimax problem using a given conformity score and hypothesis class that aims to learn from data features that are important for length optimization and uncertainty quantification. In the finite sample setting, we guarantee that our algorithm remains conditionally valid up to a knite-sample error.
We extensively evaluate the performance CPL on a variety of real world and synthetic datasets in classification, regression, and text-based settings against numerous state-of-the-arr algorithms ranging from Split-Conformi 22 44), Jacknife|45 [45, Local-CP[I]
and CQR 35). to BatchGGPP 4 and Conditional-Calibaaa 8 detailed discussion of experiments in section 5 showcase the
overall superior performance of CPL in achieving significantly better length efficiency in different scenarios where we demand marginal validity, group conditional validity, or the more complex case of conditional validity with respect to a class of covariate shifts.
2 Problem Formulation
2.1 Preliminaries on conditional validity and length of prediction sets
Recall that (X,Y) is generated from distribution D supported X' y (distributions Dx and Dyix are then defined naturally). The prediction sets are of the form C(xx) X + 2 for x E X.
Conditional Coverage Validity. Ultimately, in conformal prediction, the goal is to design prediction sets that satisfy the full conditional coverage introduced in (T). Despite the importance, full condi- achieve in the finite-sample setting [+3]. Therefore, several weaker notions of coverage such as marginal 22 44, group conditional [4 and coverage with respect to class of covariate shifts [0] have been considered in the literature. Here, focus the notion of conditional validity with respect to a class of covariate shifts, which unifies all these notions, and contains each of them as special case by adjusting the class. Fix any non-negative function ʃ and let D, f denote the setting in which {(X, } is sampled i.i.d. from D, while (Xn+1, Ya+1) is sampled independently from the distribution in which Dx is shifted by f, i.e.
tional coverage is impossible
f(x)
X ~ Ex[((x) dDx(2), Yn41 X ~ Dyjx.
We define the exact coverage validity under non-negative covariate shift f as. PIX.SIND, (Yx+1 E C(Xn+1))== = a, which can be equivalently written as,
EX s(Xntt) 1(Yntz E C(X.+ a)) -0.
(2)
3

---

This last equality enables us to define the notion of generalized covariate shift. For prediction sets C, we say that coverage with respect function f (which can take negative values) guaranteed if (2) holds. We often drop the term "generalized" when we refer to generalized covariate shifts.
Let F be a class of functions from X' to IR. We say the prediction sets C satisfy valid conditional coverage with respect to the class of covariate shifts F, if 2 holds for every f E F.
is easy see that if F is the class of all (measurable) functions on X, then conditional validity w.r.t. F is equivalent to full conditional converge @.. Accordingly, using less complex choices for would result in relaxed notions of conditional coverage. We now review three important instances of F:
1) Marginal Coverage: Setting F fIr + c c RJ, i.e. constant functions, recovers the marginal validity, i.e., Prx.+i=D(Y+t E C((n+1)) =
2) Conditoonl Coverage: Let G1 G2, Gm X be collection of sub-groups in the covariate space. Define fi(x) = 1[x E G. for every E [1. By using the class of covariate shifts can obtain the group-conditional coverage validity; i.c. PIX.) E C(X++1)|X E G.) = 1 a, for every i E [1,m].
F 1 (x)((x) B, E R for every i [I, ml
3) Finite-dimensional Affine Class of Covariate Shifts: Let Φ X + RRd be a predefined function (a.k.a. the finiteddimensiona basis). The class F is defined as F {B, {(x)) RRd. Here, F is an affine class of covariate shifts as for any f. E F and e E IR we have f +ef E F. We use the term "bounded" class of covariate shifts when we assume, max sup @, (x) < 00, where Igi ZE
(x) = (c) ;,("),,,,,,,,())))) :a(x)).
The finite-dimensional affine class fairly general and covers a broad range of scenarios in theory and practice (see Section 5.3 Remark in appendix [ as well as (8). As special cases, it includes both of the marginal and group-conditional settings. To see this, one can pick & (z) = 1 for the marginal case and & = [f (x), f2 (z). fm (z) for the group-conditional scenario. Consequently, from now on we will focus on the scenario where J is a d-dimensional affine class of covariate shifts.
Length. We use the term len(C(r)) to denote the length of prediction set at point E X. Length can have different interpretations different contexts, yet always depicts the same intuitive meaning of size. In the case of regression when y = R we have, len( (C(z)) = Jy [ E C(z)]dy. Here, dy can be interpreted as Lebesgue integral (i.e. the usual way to measure length on IR. Similarly, in the classification setting, when y (v1, 1/2, ... Jr we let len(C(x)) - 1 [ E C(+)]-
Problem Statement
In the previous section, we defined conditional validity and length as two main notions for prediction sets. The canonical problem that we study in this paper is:
Primary Problem:
Minimize ((x)
Ex [len(C(x))]
Ex,y ((x))- -1-))) =0, AfEF
subject to
lee., we want to construct predictions sets C(r), E X' with optimal (i.e. minimal) average length while being conditionally valid with respect to a dinite-dimensional) class of covariate shifts F.
In the special case of marginal validity the constraint becomes E [e [1[Y E C(X)] - -1 -a)} 0 for every e E R. or equivalently Pr(Y E C(X)) = =1-a a. Similarly, in the special case of group- conditional the constraint boils down to Pr(Y C(X))X E G,) = =1- - a for every i E [1.... ml.
Minimax Formulations
In this section we analyze the Primary Problem 2.2 in the infinite-data regime. Our goal is to derive the principles of an algorithmic framework for Primary Problem 2.2 We will do by deriving an equivalent minimax formulation whose solutions have a rich interpretation in terms of level sets of the data distribution. Having the practical sample setting in mind, then further relax the minimax formulation using a given conformity score and a hypothesis class, where we also analyze the impact of this relaxation on conditional coverage validity and length optimality.

---

3.1
The Equivalent Minimax Formulation: A Duality Perspective
natural way to think about the Primary Problem 2.2 to look at the dual formulation. Let us define,
ga C) = Ex,y [(X) 1 e
ad Ex [Ien(C(X)),
(3)
Note that the first term in ga (J, C) corresponds coverage w.r.t. and the second term corresponds to length. One can easily check that 9o (J. C)) is equivalen" to the Lagrangian for the Primary Problem (given that FF is an affine fmite-dimensional class). The dual problem can be written as:
Minimax Problem:
Minimize Maximize (f. feJ
((a)
Proposition 3.1 (Strong Duality) Assuming Drix is contimuous, the Primary Problem and the Minimax Problem are equivalent. Let (f", (x)) be an optimal solution of the Minimax Problem. Then, C is also the optimal solution of the Primary Problem. Furthermore, C* has the following form:
(x) E 2)
Example 3.2 (Marginal case) For the marginal case, where F= {I + C for every e. E R), we have (x) {y E y c' c'p(y)z)) > 1). In other words, the minimal length marginally valid prediction set is of the form of a specific level set of p(ylz). Note that the value of c* can be found using the fact that the marginal coverage should be 1
Simply put, Proposition 3.1 states that the answer the Primary Problem corresponds to specific level sets of the distributions p(y| rr) Further, this optimal level set has an equivalent minimax formulation. be used derive finite sample algorithm. Next, we will discuss the roles of the inner maximization and the outer minimization.
We will see in section how a relaxation of this minimax
The Inner Maximization. For function f X IR we define the level sets corresponding to f as
- 1 2 1].
(5)
From Proposition 3.1 the optimal prediction sets have the form C₁- for some f* F. The following proposition, shows that for fixed f the outcome of the inner maximization is exactly the level set Cj.
Proposition 3.3 (Variational representation) For any f F, and a [0, we have,
Cj argmax go ( C),
(6)
C(a)
The Outer Minimization. So far, we know that for every f. the inner maximization chooses the level set Cj given in (5). The next question is which of these level sets will be chosen by the outer minimization? The answer is simple: The one that is conditionally valid with respect to the class F. I.e., the outer minimization chooses I such that Cy- has correct conditional coverage w.r.t. to F.
Lemma 3.4 Let f F. Recall that is an affine class of functions. This means for every f E F and E R, Ef E F. We have for every f E F,
d de lo ttf
== =B (ixx ( 1 cxx() (I -1 -a- -1
=B
At the optimum solution /" of the outer minimization, all the directional derivatives are zero (since f stationary point). Hence, using the lemma, Cy- satisfies coverage validity on the class F.
Let us summarize: The outer minimization ensures that we navigate the space of conditionally valid prediction sets while the inner maximization finds the most length efficient among them.
3.2 Relaxed Minimax Formulation using Structured Prediction Sets
Taking a closer look at the Minimax formulation 3.1 the inner maximization is over the space of all the possible prediction sets, which is an overly complex set. We need to relax this maximization due to two reasons: (1) Eventually, we would like to solve the finite-sample version of this problem
'The definition of go C) is the negative of the conventional Lagrangian.
5

---

as in practice we have finite-size calibration data. Having an infinitely complex space of prediction sets simply lead overfitting. Consequently, we need restrict the maximization over a class of prediction sets of finite complexity. (2) In CP the prediction sets are often constructed by carefully designed conformity score. For instance, the common practice in CP to structure the prediction sets by threshold the conformity score. In light of these, we will need to relax the Minimax formulation.
Given the above considerations, we will restrict the domain of inner maximization in the most natural way. Aligned with the established methods in the CP literature, we look the prediction sets that are described by thresholding conformity measure. Let S(z, y) X' y + R be a given conformity score. Consider a function h X' + R. We will consider structured prediction sets of the form
Structured Prediction Sets:
= S(x. v) S h(x)).
For the ease of notation, we use go (f, h) instead ga (J, ). We then relax the Minimax Problem formulation 3.1 Let H be class of real valued functions on the set X. For now, H could be any class - g.g. could the class of all the real-valued functions on X' (with infinite complexity) or could be a class with bounded complexity (e.g. neural network parameterized by its weights).
Relaxed Minimax Problem:
Minimize Maximize 9ts (f, JEF
hEH
Here, the relaxation is that the inner maximization is over prediction sets of form 7 where h E H.
3.3 Theoretical Guarantees for the Relaxed Minimax Problem
natural question to ask now is whether this relaxation preserves valid coverage guarantees or length optimality. Clearly, the answer this question depends the choice of the conformity measure $ and the class H. Let us start by considering the structure of the optimal prediction sets given in (4): it easy to see that the optimal sets have the form
p(yl=) S ST
C ( = E
(8)
for some function f* : + R Comparing 8 with makes it clear that, unless the score S(x, y) aligned with 1/p(y(z), the structured sets C₁ may not be rich enough to capture the level sets in (8. That is to say, once we construct our prediction sets using the conformity score S - i.e. using S(x, v)) instead of (I, y)- there can be a fundamental gap to the best achievable length. That is to say the level sets of S(z,, 3) can be fundamentally different from the level sets of p(y(ar).
Given the above considerations, we ask: what is the appropriate notion of be achieved by solving the Relaxed Minimax Problem? A natural answer is the "optimal length" that can be achieved over all the structured prediction sets C.S. h E H. Accordingly, we introduce the Relaxed Primary Problem which is the dual form of the Relaxed Minimax Problem:
that can
Relaxed Primary Problem:
Minimize E [Ie((C(()))
E f e
-ax)))a-a)) YfeF
subject to
To study the connection between these two problems, one would ideally want to show that the Relaxed Minimax Problem is equivalent to the Relaxed Primary Problem, similar to the strong duality relation we showed in Proposition 3.I between the Minimax Problem B.I and the Primary froblem[.22
At a high level, we demonstrate that strong duality holds when H. is "sufficiently complex". Specifi- cally, we first let H be the class of all (measurable) functions from 2' R, and show that the Relaxed Minimax Problem and the Relaxed Primal Problem achieve the same optimal value-i.e.. strong du- ality. Hence, if the Relaxed Primal Problem admits an optimal solution /t* then the Relaxed Minimax
We are assuming ! = +00.

---

Problem has an optimal solution of the form (f*,h"). h²). Next, we consider a bounded-cood complexxttt class H. We show that under a realizability assumption, i... h E H. strong duality still holds.
We denote the optimal value of the Relaxed Minimax Problem by OPT and the optimal value of the Relaxed Primary Problem by Lt" One can interpret I." as the smallest possible length over all the structured prediction sets that are conditionally valid with respect to F. In this context, strong duality means L' -PT,, as our definition of gr, h) differs from the conventional definition of Lagrangian by a negative sign, as we wanted to stay consistent with the literature on level set estimation (e.g. see (46)). Let us now state a technical assumption needed develop our theory.
) | E R2,, where & X + Rd is predefined function (a..a. the finite finteedimensional basis). Let O ac) (z), ......... ........aaaaa....... da(r)). We assume each (i(x)) takes countably many values.
Assumption Recall that the class F is defined as F (BB, (xx))
Assumption T is mainly a technical assumption that helps to obtain a more simplified result. Assump- tion [ holld both marginal and group-conditional settings (as in these cases di 's take their value in {0. 1T.. We will provide a more general but weaker result without assumption I Appendix F Theorem 3.5 Let us assume Dsix and Dx are continuous. Let F be bounded fimite-dimensional affine class of covariate shifts and H be the class of all (measurable) functions from X to RR Under assumption [ the strong duality holds between the Relaxed Primary Problem and the Relaxed Minimax Problem. In other words,
Minimize Maximize ga Maximize Minimize ga(f, h), FEF
IEF
hEH
NEH
and the optimal values of the two problems coincide (I." = -PPT)
If the Relaxed Primary Problem (i.e., the right hand side of the above equation) attains it's optimal value at h- E H. then there exists f* E F such that (f", ) is an optimal solution to the Relaxed Minimax Problem. Otherwise, let f denote the optimal solution to the outer minimization of the Relaxed Minimax Problem. Then for every E > 0, there exists h" E H such that.
(i) 19a(f" (f,lff"h)) O E.
(ii) h" is conditionally valid; i.e., for every f F we have,
E ((x) { 1 Cx -(1 -1- -10 -0.
(ii) Ex (C.C--)) S I +
Put it simply, Theorem 3.5 says for any E >> O, there is an E-close optimal solution of the Relaxed Minimax Problem (statement (i)) such that is a feasible solution of the Relaxed Primary Problem with exact conditional coverage (statement (ii), and it achieves only e-larger prediction set length than the smallest possible, which is the solution of Relaxed Minimax Problem (statement (iii).
Bounded complexity class H: The following realizability condition paves the way to generalize the strong duality results to the case where H is class of functions with bounded complexity.
Definition 3.6 (Realizability) Let H be a class of real valued functions defined on X. We say H is Realizable if there exists h² E H such that he is an optimal solution of the Relaxed Primary Problem and the Relaxed Minimax Problem.
Proposition 3.7 Let H (hg 9 E {}, be a realizable class of functions where θ is compact set. Then the Relaxed Minimux Problem and the Relaxed Primary Problem are equivalent. In other worls, strong duality holds and the min and max are interchungeable in the Relaxed Minimax Problem.
4 Finite Sample Setting: The Main Algorithm
In this section, we present and analyze our main algorithm. Assume we have access to n independent and identically distributed (i.i.d.) calibration data ((x2, from the distribution D. Let S(x, y) X' x y > IR represents a given conformity score. We consider a bounded capacity class of functions H-e.g. a neural network parameterized by its weights. Additionally, we consider a given finite- dimensional affine class of functions FF that represents the level of conditional validity to be achieved.
Unbiased Estimation. From (3), the objective (f, h) of the Relaxed Minimax Problem 3.2 admits a straightforward unbiased estimator using n i.i.d. samples {1) 1/
Da (f.)
f(as)) (S((, vi) S M(x:)) - (1 - 0)
1 Σ
[[((,, v) S h(x:)ddy.
7

---

Smoothing, The objective Ja. (f. h) is non-smooth as it involves indicator functions. To make it differentiable, we will need to smooth the objective. A common way to smooth the indicator function 1 [a < b] is via Gaussian smoothing. Consider the Gaussian error function, erf(x> = 2 So e- dt, e-b ). where controls the v2a
and define the smoothed indicator function as: i(a, b)
erf
smoothness of the transition between 0 to 1. The value of is often chosen to be small, and when it approaches zero we retrieve the indicator function. The smoothed version our objective is
Ja.n (f. -) f(x)) ((S(a, (SSSa,,,), u)) - (1 - { Σ
R
i(5(x.. h(x:))d
ni
Given this smoothed objective, our main algorithm is presented in Algorithm 1
Algorithm 1 Conformal Prediction with Length- Optiiiztot (CPL)
1: Input: Miscoverage level a, conditional coverage requirements F, conformity score S, class H.
2: Objective:
Minimize Maximize Io.n ())
FEF
3: while not converged do
4: Perform a few iterations (e.g. SGD steps) on h to maximize Ga, (J. h)
5: Perform a few iterations (e.g. SGD steps) on f to minimize Ja.n (
6: end while
7: fCPL. + ff, hCPL f
8: Let (2) = {y E ((x s (x)).
Remark 4.1 Oftentimes in practice, the machine learning models, such Neural Networks, are parametric (ho, where the set of parameters). that case, performing the iteration on h can be implemented by updating 0.
Remark 4.2 Recalling the definition of F= {(G, ( TR each f F can be represented by f(x)= = (3,0(z)) = fa(z). Hence, performing the iteration on f can be implements by updating e Rd.
4.1
Finite Sample Guarantees
In this section we provide finite sample guarantees for the conditional coverage of the prediction sets constructed by CPL using the covering number of class H. (denoted by .V). We analyse the properties of stationary points of CPL. This is not a very restrictive choice as it is well known in the optimization literature that the converging points of gradient descent ascent methods (like CPL.) the stationary points the minimax problem (e.g. look at (47)). We now state the required technical assumption. Definition 4.3 A distribution P, is called L-lipschitz if we have for every real valued numbers d'
Pr X>P (x Pr (x S S Lg q)) X-P
Assumption The conditional distribution Dsix is L-Lipschitt almost surely with respect to Dx.
48 49 Consider CPL with smoothed function no.. with smoothing parameter a -. Let (JCPL: MCPL) denote stationary point reached by Algorithm T Also, the corresponding prediction sets given as C'PL (x) = (y E y S(x, y) & (h)p(())
Assumption iis often needed for concentration guarantees in CP literature
Theorem 4.4 (Conditional coverage validity) Under assumption let (fČPL: h(pt.) denote sta- tionary point reached by Algorithm] 7 (if exists) and CepL (z) its corresponding prediction sets. Then with probability 8 we have,
2d,
Ci In
+
E
Sal (x(X)
1 E (x)((X) (1 - an)
-1-
Afg FF,
where 12B111111 02 = |B|| +
2n ||3||
B =
max, sux (x)x) and tb is the
V2=
basis for F (see Section 2.7p.
PAC-style guarantees of the order 0 are generally optimal and common in CP literature Look at Appendix for further discussions and interpretations.
50
8

---

Experiments
In this section, we empirically examine the length performance CPL compared to state-of-the- art (SOTA) baselines under varying levels of conditional validity requirements. This section is organized into three parts, each dedicated to setups that demand a specific level of conditional validity. Throughout this section, demonstrate across different data modalities and experimental settings that CPL provides significantly tighter prediction sets (i.e. smaller length) that are conditionally valid. Additionally, we have provided Python notebook with step-by efficient implementation of our algorithm, which can be accessed at the following link:
5.1 Part I: Marginal Coverage for Multiple Choice Question Answering
We use multiple-choice question answering datasets, including TruthfulQA 511 MMLU [52]
OpenBookQA [53]. PIQA[54] and BigBench [55]. The task is to quantify the uncertainty of Llama 2 [66] and create prediction sets using this model. We follow a procedure similar to the one proposed by 33 described below.
For each dataset, we tackle the task of multiple-choice question answering. We pass the question to Llama 2 using simple and fixed prompt engineering approach throughout the experiment:
This is 4-choice question that you should answer:
{question} The correct answer to this question is:
We then look at the logits of the first output token for the options A, B, C. and D. By ap- plying a softmax function, obtain probability vector. The conformity score defined as (1 probability of the correct option), which is similar to (1 f(x),) for classification.
Our method is implemented using H linear head top of pre-trained GPT-2 [57]. GPT-2 has 768-dimensional hidden layers, so the optimization for the inner maximization involves a 768- dimensional linear map from GPT-2's last hidden layer representations to real-valued scalar. We also implemented the method of [33, which directly applies split conformal method on the scores.
Figures 3a shows the performance of our method (CPL) compared to the baseline. CPL achieves significantly smaller set sizes while ensuring proper 90% coverage.
0.55
0.50
Split Conformal
4.5
0.85
3.54
Coverage
0.75
Prediction
2.5
0.65
k.c
0.80
1.54
0.55
Bigenchh
OponRooKOA
BigBanch
OSonBooKOA
(a) Coverage
(b) Mcan Prediction Set Size
Figure 3: Left-hand-side plot shows coverage and right-hand--ee hand-side shows mean prediction set size.
5.2 Part II: Crouu-Conditional Coverage for Synthetic Regression
We use synthetic regression task in 4 to compare CPL with BatchGCP 4
The covariate
X (X,,...,, ......Xjmmm j0o)) a vector in R000 The first ten coordinates are independent uniform binary variables, and the remaining 90 coordinates are i.i.d. Gaussian variables. The label y is generated
y (0, XX + ex where ex is zero-mean Gaussian with variance ox + Σ iX; + (40-
1 1 100 X, 0 20). We generate 150K training samples, 50K calibration data points, and 50K test data points. We evaluate all algorithms over 100 trials and report average performance.
We define 20 overlapping groups based on ten binary components of X. For each in to 10, Group corresponds to X; and Group 2i to X; = 1. BatchGCP and CPL. are implemented to provide group-conditional coverage for these groups. We use 2-hidden-layer NN with layers of

---

20 and 10 neurons for the inner maximization. We also include the Split Conformal method and an optimal oracle baseline, calculated numerically using the optimal formulation of Proposition 3.1
As seen in Figure 4 the Split Conformal under covers in high-variance groups and over covers in low-variance groups. CPL and BatchGCP provide near-perfect coverage in all groups, matching the Optimal Oracle. The mean interval plot shows that BatchGCP performs similarly to Split Conformal, while CPL significantly reduces the average length, nearing the Optimal Oracle solution.
Sptiral Crede
Figure 4: sifd-hand- plot shows coverage and right-hand-side shows mean interval length.
5.3 Part III: Coverage w.r.f. General Class of Covariate Shifts for Image Classification
We conduct experiments on the RxRxI dataset from the WILDS repository, which consists of cell images for predicting one of 1.339 genetic treatments across 51 experiments, each exhibiting covariate shifts. Our objective is to construct prediction sets that retain valid coverage across these shifts. We compare two methods: CPL and the Conditional Calibration algorithm introduced by [8) which employs quantile regression to achieve valid conditional coverage under covariate shifts.
To implement these methods, we follow the approach in 8 where covariate shifts are defined by partitioning the calibration data. A multinomial linear regression model with l2 regularization is then trained on the first half of the calibration data to predict which experiment each image belongs to, and the features learned by this regression serve as the basis of the covariate shift class.
For the genetic treatment prediction task, we use pre-trained ResNet50 model (trained by 158), fz)), trained on data from 37 experiments. The remaining 14 experiments are split into separate calibration and test sets. To handle the inner optimization of our method, we train linear classifier on the final-layer representations of the pre-trained ResNet50. We then compute conformity scores 1339
as follows: for each image let f' (xx))=1 represent the output of the ResNer50 for each treatment class. We apply temperature scaling and softmax function to convert these outputs into probability estimates, n' (a)) == exp(T exp(TTi(xx)) /e, (xp(TTf(z)))) where T is the temperature parameter. The conformity score S(x, y) is calculated as the sum of n. (x) over treatments for which (T(2)) Ty-
Figure compares CPL, Conditional Calibration, and Split Conformal methods. While both CPL and Conditional Calibration maintain valid coverage, CPL achieves significantly smaller average prediction set sizes by focusing on feature learning without sacrificing conditional validity.
Sple
Cond and Celbretion
CPL
Hean Predeton Det Stze
Covenge
M
Experiments
Expertments
Figure 5: Left-hand-side plot shows coverage and right-hand-side shows mean prediction size.
The reported values are averaged over 20 different splits of calibration data.
10

---

Acknowledgments
This work is supported by the NSF Institute for CORE Emerging Methods in Data Science (EnCORE). The authors wish to thank Luiz Chamon for helpful discussions.
References
[1] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Steven C. H. Hoi and Wray Buntine, editors, Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pages 475 Singapore Management University, Singapore, 04 Nov 2012. PMLR.
[2] Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution- conditional predictive inference. arXiv e-prints, page 1w03:993.0400 046644 March 2019.
[3] Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71-96, 2014.
[4] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. In International Conference on Learning Representations, 2023.
[5] Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-fiee conditional predictive inference. Information and Inference: A Journal of the IMA, 2019.
[6] Vladimir Vovk, David Lindsay, Ili Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical Report, 2003.
[7] Adel Javammard, Simeng Shao, and Jacob Bien. Prediction sets for high- ligh-dimensional mixture of experts models. arXiv preprint arXiv:2210. 16710, 2022.
[8] Isaac Gibbs, John Cherian, and Emmanuel J. Candès. Conformal prediction with conditional guarantees, 2023.
[9] Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. In Neural Information Processing Systems, 2019.
[10] Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C Duchi. Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, pages 1-66, 2024.
[11] Leying Guan. Localized conformal prediction: A generalized inference framework for confor- mal prediction. Biometrika, 2021.
[12] Rohan Hore and Rina Foygel Barber. Conformal prediction with local weights: randomization enables local guarantees. arXiv preprint arXiv:2310.07854, 2023.
[13] Rafael Izbicki, Gilson Shimizu, and Rafael Stern. Flexible cirribution-free conditional pre- dictive bands using density estimators. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference Artificial Intelligence and Statis- rics, volume 108 of Proceedings of Machine Learning Research, pages 3068-3077. PMLR, 26-28 Aug 2020.
[14] Benjamin LeRoy and David Zhao. Md-split+: Practical local conformal inference in high dimensions. arXiv preprint arXiv:2107.03280. 2021.
[15] Rafael Izbicki, Gilson Shimizu, and Rafael B Stern. Cd-split and hpd-split: Efficient conformal regions in high dimensions. The Journal of Machine Learning Research, 23(1):3772-3803, 2022.
[16] Salim Amoukou and Nicolas JB Brunel. Adaptive conformal prediction by reweighting nonconformity score. arXiv preprint arXiv:2303. 12695, 2023.

---

[17] Tiffany Ding, Anastasios Angelopoulos, Stephen Bates, Michael Jordan, and Ryan J Tibshirani. conditoon conformal prediction with many classes, Advances Neural Information Processing Systems, 36, 2024.
[18] Wenwen Si, Sangdon Park, Insup Lee, Edgar Dobriban, and Osbert Bastani. Pac prediction sets under label shift. arXiv preprint 1rXiv:2310.129000 2023.
[19] Shayan Kiyani, George Pappas, and Hamed Hassani. Conformal prediction with learned features. arXiv preprint arXiv:2404.17487, 2024.
[20] Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George Pappas. Safe planning in dynamic environments using conformal prediction. IEEE Robotics and Automation Letters, 2023.
[21] Matthew Cleaveland, Insup Lee, George Pappas, and Lars Lindemann. Conformal prediction regions for time series using linear complementarity programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20984-20992, 2024.
[22] Jing Lei, Max Grazier G' G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry A. Wasser- man. Distribution--Fi free predictive inference for regression. Journal of the American Statistical Association, 113:1094- 1111, 2016.
[23] 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-235 2019.
[24] Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong, Efficient and differentiable conformal prediction with general function classes. arXiv preprint arXiv:2202.1100 1091, 2022.
[25] Matteo Zecchin, Sangwoo Park, Osvaldo Simeone, and Fredrik Hellström. Generalization and informativeness of conformal prediction. arXiv preprint 1.Xiv:2401.11810 2024.
[26] Jesse C Cresswell, Yi Sui, Bhargava Kumar, and Noël Vouitsis. Conformal prediction sets improve human decision making. arXiv preprint arXiv:2401. 137444 2024.
[27] Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez. Improving expert predictions with conformal prediction. In International Conference on Machine Learning, pages 32633-32653. PMLR, 2023.
[28] Varun Babbar, Umang Bhatt, and Adrian Weller. On the utility of prediction sets in human-ai teams. arXiv preprint NXXYv:2005.01411 2022.
[29] Eleni Straitouri and Manuel Gomez Rodriguez. Designing decision support systems using counterfactual prediction sets. arXiv preprint arXiv:2306.03998,, 2023.
[30] Kfir Cohen, Sangwoo Park, Osvaldo Simeone, and Shlomo Shamai. Calibrating ai models for wireless communications via conformal prediction. IEEE Transactions Machine Learning in Communications and Networking, 2023.
[31] Meiyi Zhu, Matteo Zecchin, Sangwoo Park, Caili Guo, Chunyan Feng, and Osvaldo Simeone. Federated inference with reliable uncertainty quantification over wireless channels via conformal prediction. IEEE Transactions on Signal Processing, 2024.
[32] Christopher Mohri and Tatsunori Hashimoto. Language models with conformal factuality guarantees. arXiv preprint arXiv:2402.10998, 2024.
[33] Bhawesh Kumar, Charlie Lu, Gauri Gupta, Anil Palepu, David Bellamy, Ramesh Raskar, and Andrew Beam. Conformal prediction with large language models for multi-choice question answering. arXiv preprint 2r..v:2305. 2023.
[34] John J Cherian, Isaac Gibbs, and Emmanuel Candès. Large language model validity via enhanced conformal prediction methods. arXiv preprint arXiv:2406. 09714, 2024.
[35] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
12

---

[36] Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Academy of Sciences, 1 18(48))c210779411 18, 2021.
[37] Nicolas Deutschmann, Mattia Rigotti, and Maria Rodriguez Martinez. Adaptive conformal regression with jackknife+ rescaled scores. arXiv preprint arXiv:2305. 2023.
[38] Shai Feldman, Stephen Bates, and Yaniv Romano. Improving conditional coverage via orthog- onal quantile regression. Advances in neural information processing systems, 14:2060-2071, 2021.
[39] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
[40] Yachong Yang and Arun Kumar Kuchibhotla. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, (ust-acccepeed)1122 2024.
[41] Harris Papadopoulos, Vladimir Vovk, and Alexander Gammerman. Regression conformal prediction with nearest neighbours. Journal of Artificial Intelligence Research, 40:815-8444 840, 2011.
[42] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional predic- tion for sequential decision making. Manuscript; Oral presentation at 15th International OPT Workshop on Optimization for MI, 2023.
[43] Matteo Sesia, Stefano Favaro, and Edgar Dobriban. Conformal frequency estimation using discrete sketched data with coverage for distinct queries. Journal of Machine Learning Research, 24(348):1-80 2023.
[44] Harris Papadopoulos, Kostas Proedrou, Vladimir Vovk, and Alexander Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, 2002.
[45] Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. 2021.
[46] Rehecca M Willett and Robert D) Nowak. Minimax optimal level-set estimation. IEEE Transac- tions on Image Processing, 16(1 (112))2265-29777 2007.
[47] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pages 4880-4889. PMLR, 13-18 Jul 2020.
[48] Matteo Sesia and Yaniv Romano. Conformal prediction using conditional histograms. In Neural Information Processing Systems, 2021.
[49] Jing Lei and Larry A. Wasserman. Distribution free prediction bands. ArXiv, abs/ 203.5422, 2012.
[50] Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020.
[51] Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. arXiv preprint (0Xi::21190099900 2021.
[52] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint vrXiv:2009.03000 2020.
[53] Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity?? new dataset for open book question answering. In EMNLP, 2018.
[54] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piga: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 7432-7439, 2020.
13

---

[55] BIG bench authors. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research. 2023.
[56] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint urXiv:230.00288. 2023.
[57] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[58] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664. PMLR, 18-24 Jul 2021.
[59] Ran Xie, Rina Foygel Barber, and Emmanuel J Candès. Boosted conformal prediction intervals. arXiv preprint arXiv:2406.0744) 2024..
[60] Valery Manokhin. Awesome conformal prediction. you use Awesome Conformal Prediction. please cite it as below, 2022.
[61] Alessandro Rinaldo and Larry Wasserman. Generalized density clusteringl. The Annals of Statistics, 38(5):2678-22 2722, 2010.
[62] PHILIPPE RIGOLLET and RÉGIS VERT. Optimal rates for plug-in estimators of density level sets. Bernoulli, 15211114117888 2009.
[63] Wolfgang Polonik. Measuring mass concentrations and estimating density contour clusters-an excess mass approach. The annals of Statistics, pages 855-881,1 1995.
[64] Jing Lei, James Robins, and Larry Wasserman. Efficient nonparametric conformal prediction regions. arXiv preprint arXiv: /tt:://11.10 1418, 2011.
[65] David Stutz, Krishnamurthy Dj Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet. Learning optimal conformal classifiers. In International Conference on Learning Representations, 2022.
[66] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[67] Ramon Van Handel. Probability in high dimension. Lecture Notes (Princeton University). 2014.
[68] David G Luenberger. Optimization by vector space methods. John Wiley & Sons, 1969.
[69] Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society London. Series A, Containing Papers of a Mathematical or Physical Character, 23 2316694-700)2289-3377 1933.
[70] Harris Papadopoulos, Alex Gammerman, and Volodya Vovk. Normalized nonconformity measures for regression conformal prediction. In Proceedings of the IASTED International Conference on Artificial Intelligence and Applications (AIA 2008), pages 64-69, 2008.
[71] Samuel H Zuvekas and David Kashihara. The impacts of the covid-19 pandemic on the medical expenditure panel survey. American journal of public health, 11(()))2157-216, 2021.
[72] Svetlana Pashchenko and Ponpoje Porapakkarm. Medical spending in the us: facts from the medical expenditure panel survey data set. Fiscal Studies, 37(3-4):689-716, 2016.
[73] Krisztian Buza. Feedback prediction for blogs. In Data analysis, machine learning and knowledge discovery, pages 155- Springer, 2013.
[74] Prashant S Rana. Physicochemical properties of protein tertiary structure data set. UCI Machine Learning Repository, 2013.
14

---

[75] Hadi Fanaee-T. Bike Sharing.
UCI Machine
Learning Repository, 2013. DOI:
https://bb..org//02444////C
[76] Michael Redmond. Communities and Crime. UCI Machine Learning Repository, 2009, DOI:
https///bb..rg//022432///3333
[77] Helen Pate-Bain, Jayne Boyd-Zaharias, Van A Cain, Elizabeth Word, and M Edward Binkley. Star follow-up studies, 1996- 1997: The student/teacher achievement ratio (star) project. 1997.
[78] I-Cheng Yeh. Concrete Compressive Strength. UCI Machine Learning Repository, 2007. DOI:
https://bbb.rr/l1222433///KK
[79] Kamaljot Singh. Facebook Comment Volume. UCI Machine Learning Repository, 2016. DOI: http://dbb.rr//022225///55888
[80] Kamaljot Singh, Ranjeet Kaur Sandhu, and Dinesh Kumar. Comment volume prediction using neural networks and decision trees. IEEE UKSim-AMSS 17th International Conference on Computer Modelling and Simulation, UKSim2015 (UKSim2015), 2015.
15

---

A
Outline
Section provides more discussions on the existing related works.
Appendix is dedicated on some interpretations of the finite sample guarantees of Section
Appendix D lists the all the Remarks that we moved to Appendix from the main body due to space limit.
Appendix provides the Lemmas, including their proofs, that are necessary for the develop- ment of out theoretical framework.
Section provides the proofs of all the statements proposed in Section 3 along with an extra
Theorem.
Section provides the proofs of all the statements proposed in Section 4
Section provides an extensive experimental setting to showcase the ability of CPL. to
improve length efficiency in real-world regression scenarios.
Section ! provides an extra experiment setup that showcases the possibility of applying CPL on top a CIFAR-10 classifier that is trained by conformal training.
Section provides references to all the 11 regression datasets used experiment setup of Section
B Further Related Works
We now review some of the remaining prior works that are relevant.
Designing better conformity scores: There is a growing body of work designing better conformity
scores to improve conditional validity and/or length efficiency [22] [1 [59] (see (60] for more references). As shown in Fig. []] our framework applies post selection of the score, and hence can use any of the conformity scores designed in the literature (see Section 5 for experiments with different
scores).
Level set estimation. As we will see, key ingredient to our framework is to study the problem of CP through the lens of level set estimation. Level set estimation has been extensively studied in the literature of statistics 44 61], and it was introduced to CP community by [64] and further studied by 23 Our framework expands and builds upon the connection of level set estimation and CP. In particular, comparing to [23 64), we take three significant steps. (i) We propose to
utilize the covariate, X, directly optimize length via an adaptive threshold. This results in major improvements in length efficiency in practice. (ii) We go beyond marginal coverage to different levels of conditional validity. (iii) Finally, unlike [64), we do not need directly estimate any marginalcconditional density function. Level sets and their approximations appear naturally in our optimization framework.
Several works have focused on directly optimizing the score function to enhance the length efficiency of conformal prediction pipelines (24 34, 63). In particular, [65] introduced conformal training, where a (marginal) calibration procedure is fixed, and derivatives of the prediction set size with respect to the model parameters are taken. This enables the model to be optimized not for predictive accuracy, as is typical, but for producing smaller prediction sets. However, key distinction separates our approach from the broader idea of conformal training. To illustrate this difference, consider the simpler case where we aim only to improve length efficiency under marginal coverage. Let (g y) : X x y + E be a parameterized conformity score (c.g., where 0 represents the parameters of a neural network). Conformal training optimizes / to improve the length efficiency of prediction sets of the form So y) S q. where q a fixed threshold. In contrast, we keep fixed and optimize an adaptive threshold h(x) X' + R to improve the length efficiency of prediction sets of the form (g y) I h(x).. That is say, our method can also be applied on top of score trained by conformal training. In appendix ! we show that it is possible to optimize length even further by applying our method on top of the conformal training introduced by (65]. It's important to note that our use of covariate-adaple adaptive thresholds is specifically for length optimization, distinct from the use in addressing conditional coverage in prior literature. Beyond the theoretical framework, our perspective allows for length optimization in various real-world applications. In practice, access to
Conformal training:
16

---

model's s internal parameters may be restricted due to privacy, security, or policy concerns. In section 5.1. we demonstrate how to construct efficient prediction sets for large language models (LLMs) without optimizing their internal parameters. Additionally, in uncertainty quantification, conformal prediction sets often serve to assess the behavior of a given black-box model. In these cases, the statistician's & role is to analyze the model's behavior rather than further optimizing it, which could degrade performance on nominal or out-of-distribution tasks. Additionally, in a concurrent work to ours, [34] extended conformal training idea to more general case, allowing the score function to optimized while targeting conditional coverage in the calibration procedure. They develop novel technique to differentiate through the conditional conformal algorithm introduced by [8]. However, while both approaches utilize similar relaxations for targeting conditional coverage, our work diverges in the underlying objective. Whereas (34] focuses optimizing the score function, we emphasize optimizing the threshold leaving the scores untouched. This leads to two distinct theoretical and algorithmic developments.
C Further Discussions on Finite Sample Result
Theorem C.1 (Conditional coverage validity) Under assumption 2 let (fCPL: liPL)) denote stationary point reached by Algorithm 7 Then with probability
(if exists) and Cpr, (x) its corresponding prediction sets.
8 we have,
(d.
C1 av
In
+ +
10 [ToLx] 1/x E (XPL(X)] -LL-a)
-
Bfg E F,
Vn
where = /2 02
|B|| +
||||
B max, saxxe Di(x)) and tb is the V2=
2B
basis for F (see Sec. 2.
We now provide three Corollaries to this Theorem.
The case of marginal validity: For this case we have to pick == far el IR,, i.e. constant functions. this case one can see = 1, so we have the following result.
Corollary C.2 (Finite sample marginal validity) Under assumption 2 let (JČPL: k(PL.) denote stationary point reached by Algorithm (if exists) and CCPL (x)) its corresponding prediction sets. Then with probability 8 we have,
dH, #
cI
In
+ 02
- Pr(Y E -
where 6 = V2 L. L V2T
The case of group-conditional validity: Let GI. ,G be collection of groups: each group is subset of covariate space, i.c. G, E X. These groups can be fully arbitrary and highly overlapping. Defin fx 1[x G.] for every i E [1, m. We can then run CPL using the class of covariate shifts F = Σ
1= (zf((x) 8 E IR for every i E [1.... m] m and obtain tight prediction sets with group conditoon coverage validity. In this case one can see 1, so we have the following result.
Corollary C.3 (Finite sample group-conditional validity) Under assumption 2 let (fCPL hCPL) denote a stationary point reached by Algorithm] (if exists) and CoPL (x) its corresponding prediction sets. Then with probability 8 we have,
In 2mN
+ C2
Pr(Y E CCp,
G.) - (1-a) <
Vi E [1...., m],
/n.
where = V2 LV3 V2
/
2
17

---

D Further Remarks
Remark D.1 Another important special case of conditional validity with respect affine finite dimensional class of covariate shifts is the framework introduced by ( which provides CP methods that guarantee valid coverage when there is known covariate shift between calibration data and test data. This exactly falls to our framework as the special case if we consider the class F {xr + cf(x) for every E R. where J is the known covariate shift (i.e. likelihood ratio between test and calibration data).
Remark D.2 We will need to assume that the members of the class H. are bounded functions; i.e. for every h E H and x E X we have h(x) E [0, 1.. Two points are in order. (i) This assumption is purely for the sake of theory development. In practice, one machine learning class of models. In fact, in Section we run our algorithm with a variety of models including deep neural networks (Resnet 50) and show case its performance. (ii) This assumption is not very far from practice. In fact, one can satisfy this assumption by using a Sigmoid activation function (or a scaled version of it) on the output layer satisfy this assumption. Similar assumptions has been posed in the literature
algorithm with any off- off-the-shelf
49).
E Technical Lemmas
Lemma E.1 Let f(a,z) = (1+ erf a-x be the smoothed indicator function where erf(z) is /2a/ the error fanction, defined as erf(s:) -/ Se e- dt, and the variance of the Gaussian kernel used for smoothing. Then x() is Lipschitz continuous with respect to with Lipschitz constant
V2x0
Proof: To prove that f(a, x) is Lipschitz continuous with respect to æ, we compute the derivative of f(a, x) with respect to
1 1
f(a,x)
V20
0
1 0
(1 1
(
aa=x)
1
2
-1
dr f(a.
Vzn
2 8x
V2a
2
v
v
20
Simplifying this, we get:
1
dr xa)
26
V
To show that this derivative bounded, observe that:
i Ox fla x:)
(a=z)2
2n
V2TO
V2TO
Since
is constant, we conclude that f(a xr) Lipschitz continuous with respect to æ with
VIño
Lipschitz constant Vena
Lemma E.2 Let ila b) be the smoothed indicator finicttttffuueeio function defined by
ila bl b| (1 erf
/20
where erf(z) is the error function, defined as erf(z) = 2 -e e -t² dt, and o is the variance of the
Gaussian kernel used for smoothing. The indicator function 1/a b) is also defined
1 ifa <
1(a bj
0
otherwise
18

---

The error between the smoothed indicator function 1[a < bj and the actual indicator function 1la < b), integrated over all is given by
E=
[aa < 6] 1la < bl| da
This integral evaluates
E
To compute the integral, we consider the cases separately: b and a 2 b. For b, the indicator function 1(a < bj = 1, so the absolute difference
Proof:
iaa < b] 1| + erf (a (a-b)
1
erf b
22
For the indicator function 1[a < b] 0, so the absolute difference
1
a aa
[i < bj - 0
1 erf
2
V2o
Combining these, the integral can be written
E = 1" 2 erf
a - - da +
[x]
x
1 1 + ))
da
22a
b
We know that where (xx) is the CDF of the standard normal distribution.
erf(2) (r) 2 (xv2) -
Using symmetry properties of the error function and Gaussian integrals, we can simplify the calcula- tions as follows:
{ erf
a b
1) da = -
/20
|0 0
(1+ert
(a-b)
22 ) da V π
2
Thus, the total error integral is:
(
π E
π 2
(
a
2
2
Lemma E.3 Let f E F be fixed function such that supzex I ((x) S B and let us define,
1
f(x)) (.)( ((1- -0-1
Zn
n
((O) [
-(ta -1-
E
The following uniform convergence holds: Fixing any & > 0, we have with probability 8,
VBB
(N(H) 8
2Bg
Zu 5
for every E H.
2
Vn
19

---

Proof. Let h1, h2 E H. be two arbitrary functions, We have,
(a) x
Fla)) i(S(en -
1Z, Zmza
(((((
E ((a)) ((ao)(((S6)))) ((5(2, - (o)
1
72
((x) i(s(s, (),
+
(c)
12
I(S(za (s hz(z)))
B
+
E
i ((S(2, ((S
B
1
(x,);;) ha
V2TO
B
E [1
h2(2)))
V
2B
sup (x) 12((x)
V2Ta
zEX
where (a) is triangle inequality, (b) is another triangle inequality, (c) comes from the definition of B, (d) follows from the Lipschitness Lemma E.I and finally (e) from the definition of sup.
Now let us define d (h1, h2) = supzex [h - h2(2)) Therefore, ZZ,, - Zhz I 2B (h1 h2). By Hoeffding's inequality for general bounded random variables (look chapter of (66)), fixing E H. we have with probability 5,
VBB In (3)
7 S
Vn
Now as a result Lemma 5.7 [67 (a standard covering number argument) we conclude,
V2B,
In
2N
2Be
Z
<
for every H.
V2Ra
Lemma E.4 The following equivalence between the three problems hold, Structured Minimax Problem
Convex Structured Minimax Problem
-Convex Structured Primary Problem
where by -Convex Structured Primary Problem we mean the optimal value of Convex Structured Primary Problem is equal to the negative of the optimal values of the other two problems.
Proof. We start by the following claim which will be proven shortly.
Claim Convex Structured Minimax Problem is equivalent to the Structured Minimax Problem.
20

---

Proof. Let us remind the objective,
ga C) - - -10000-oxxx
E u(X,u)dy,
which is linear in terms of C. Now fixing E F, since CH CH we have,
Maximize go CJ. Cecuge
Maximize ga (J.C). CEC
We now proceed by showing the other direction. Let {C. where C2 CH and oo Ia(f, C+) = Maximize (f C)) (pay attention that it is not trivial that this maximum CEC
achievable by a single member of its domain). Now by the definition of g we know each C; convex combination of finitely many members of CHo.. That is to say, for each C₁ there exists {Cig1y=1 where Cij E Cy and,
C. = Σ Cccyl,
-a==1. 2 2 SisT).
jml
Hence,
T (f. =a (f. Σ a,Ci((z,))) j=1
T Cij) S T go. (f. Cit)
- j=1
-=1
Let us assume that final maximum is achieved by the index j. Therefore, for each C₁ Coon there exists a Cıg, E Cz such that (J, S (a(S, C.j.). Hence we have,
Maximize C)( = lim (f. Ci) S lim Ja(S, Cij.) S Maximize go (f,C) 1-000
CEC
E0000
CECHx
Putting everything together, for every S F we have,
Maximize 9a (f,C)) = Maximize 9a (f, C)2 CEC
CEC2x0
which concludes the claim.
Now Let us define the Convex Structured Primary Problem.
Convex Structured Primary Problem:
Minimize CECon
E [len(C(X))]
[(X) (100(
subject to
E
VfeF
As the Convex Structured Primary Problem a linear minimization over convex set, Cam., with finitely many linear constraints, strong duality holds for this problem (See Theorem 1, Section 8.3 of [68]; Also see Problem 7 in Chapter 8 of the same reference), which means Convex Structured Primary Problem is equivalent to Convex Structured Minimax Problem (Here we are using the fact that Dsjx continuous hence the Convex Structured Primary Problem feasible). Now putting everything together we have,
Structured Minimax Problem
Convex Structured Minimax Problem
-Convex Structured Primary Problem
The negative sign appeared as our definition of 9. h) has a minus sign with respect to the conventional definition of Lagrangian.
21

---

Lemma E.5 Given a random variable Z taking values in [0, 1] and B|Z] 2 y > 0, we have,
Pr(Z Z 2 7 ) 27
Proof. Let us define 0 Pr(Z 2 f). Now have,
7 50x1+ (101+
Hence,
0(1
7 3)
2 2
3
Therefore,
2y
24
0 2
(10)
Lemma E.6 Consider 8 > 0,
16 > >>> 0 and N numbers "1, such that, Σ
7 and
24 E [0, 8) every sis N. Then there exists a subset _ [N] such that,
2 y 18
Σ iES
2 8
(11)
Proof.
Let us define for every 1 ISiSN,
with probability 7
yi
0
24
with probability 1 1
(12)
and assume that yıs independently generated. By Hoeffding inequality have,
-282
Pr(
Σ
U/
2xx
Σ 2?
This results in,
N
-26"
Pr( Σ
77 88
2 6) S 2exp
87
i=l
Now setting o get,
N
Pr
Σ
Ui
2 )2 <
exxp
< 1.
288
This means there exists a deterministic realization that satisñes II
F Proofs of Section
Here provide version of Theorem 3.5 which does not need the assumption D. Before that, let us remind that each element f E can be represented by B3 Rd,, where we use the notation fa(z) (B, ((x)) (look at section 2.1 for more details).
Theorem F.1 Let us assume Dsix and Dx are continuous. Let F be bounded affine class of covariate shifts and H be the class of all meusurable functions. Let J denote the optimal solution to the outer minimization and OPT denotes the optimal value of the Relaxed Minimax Problem3.2 3.2 Finally, T." denotes the optimal value for the Relaxed Primary Problem 3.3 For every > 0, there exists h² E H. such that,
22

---

(i) Ifa (,)fff"h))))))) - -PPT| E. (ii) For every la have,
fa((Nn fa((x-i) (f I|Ynti E (X,+ -as $ <
(iti) E len CO (X)) S tE.
Put simply, Theorem F.I says fixing any E > O, there an E-close optimal solution of the Relaxed Minimax Problem (statement (i)) such that it is e-close to the feasible solutions of the Relaxed Primary Problem which have perfect conditional coverage (statement (i)), and it achieves an at most e-larger prediction set length compare the smallest possible, which is the solution of Relaxed Minimax Problem (statement (iii)..
Proof of Theorem E.l.et us define 00 as the class of all measurable functions from X' to R. Now let us restate the Structured Minimax Problem 000
Structured Minimax Problem:
Minimize Maximize fa(f.))
fEF
bEH*
We can now rewrite this problem the equivalent form of the following, where we change the domain of the maximization from H.x to corresponding set functions. Let Cy be the set of all function from C(r,y) y) X' > RR such that there exists H00 such that C( v) = [S((,, y) S h(x)).
Structured Minimax Problem:
Minimize Maximize 9o (f. feF
CECy
We now proceed by defining convexified version of this problem. Let us define
Ceen a,C,(e,y) v)
Σ a; L, 1A)0 sis (M N}.
Now we can define the following problem.
Convex Structured Minimax Problem:
Minimize Maximize (f,fC). JEF
CEC
Now applying lemma
we have,
Structured Minimax Problem
Convex Structured Minimax Problem
-Convex Structured Primary Problem
The negative sign appears because our definition of (f, h) has a minus sign with respect the conventional definition of Lagrangian. Let us call the optimal value for all these three problems OPT (here pay attention that based off our definition OPT always negative number, hence when we are addressing the optimal length the term -OPT shows up). With some abuse of notation, Let us assume (0 where C; E C a feasible sequence of Convex Structured Primary Problem which achieves the optimal value in the limit, i.e, lim;- 9a (f. C.) = -OP.. This means, for any e 2 0, there is an index is such that |E Ien(C..) + OPT < e. Let us fix value for now, we will determine its value later. By definition, there should be {Ci and corresponding (h4)-= such that Õ; E CH=, he E 000 C 1[S(x, v) < hx(x)), and we have C, = Dím a,Ca(z, y) and
Σ. a, 1, 2 0 (V1 < sist).
23

---

Now Let us define L, E (en((C)) for every 1 S i S & (all of these expectations are finite cause [Elen(C,,) + OPT] I E). Now if look at the truncations of these expectations, by Dominated Convergence Theorem we have, [[[en((C)) [[en))))(C > k]]
O.
k-+00
This means, for any 2 0, there exists real valued number "n such that define the set Tn C X that (i) for every 1 i t and for every z Z len(C((x)) [Ilen(C;,)1(rr é 7 S 8.
7i, and (ii)
Now remind that Theorem there exists large enough real value "/2 such that Pr(X & 72)) where B(0, 72) is the ball with radius and e is positive real number that we will determine later.
R". Since we know Dx is continuous then by Dominated Convergence
Similarly we can again look T.kk T. is 7/ such that for every 1 S i t we have |[] 2 rall S.
[|| 2 k). By Dominated Convergence Theorem there
Let R m7x 72, 73, 1 and A ( RR) LR.
Now the rest of the proof proceed as follows. We will construct h' E H and as a result the corresponding set (a y) (x, y) h" (x)),, in way that coverage properties and the length of C* is close to the ones for C,, Let us proceed with the construction of h""
case 1: & A. For this case we define h² (a:) = 0.
case 2: x E A. This case is more involved. Let us fix e1 2 0. Let (B(b,, e1) be minimal & covering for A. We can then further prune this covering balls to {W. where (i) W; n W, - for every # j. (ii) U W; = A, and (iii) W; S B(b,, e1) for every i. Now we use the following randomized method to prove desirable construction for h exists. Let {2, j= be collection of uniform iid discrete random variables where they take values between and Then we define the random function (x) inside A in the following way. By construction, for each E A there is hz, h2,(2). We denote the corresponding set function to hyand by Crand- Now Let remind that F is a finite dimensional affine class of functions. In particular, let ((x) = Jon (z),. ............... Φa(x)] be a predefined function (a.k.a. the finite-dimensional basis). The class F is defined as F {(3, (ax) / E Rd). Now for each is E [1,-.. .d] we can do the following calculations.
unique W2 that includes x. We set (x)
N
E X,Y,brand
Σ
- du (1- w.l wil
E NyY.haandd
(x()) (1 a)) E
( a)) Al]
Σ E
(C,, (1- -1X1))111 e al]
E
E X,Y
(x,) - -1--))) & &AA
(C) (x,)) a))) -
<
E X,Y
1[x & Al)
BE1 & A]
B(0, R)) + ELR) 2Be,
where B is the upper bound for Φv. We now define the random variable
E, = E
Y) - (1 a)) e W.].
X.Y
24

---

for every 1 i S N. The computation above indicates a bound on the expectation of the sum of these variables. By the construction of Cann we know that they are independent. Furthermore. each random variable E is bounded by the quantity 2 M vol (B(O, E1)). where B is the upper bound for (b. M max p(x) (which is finite as ((0, R) is compact set and we assumed Dx is continuous), and ((0,e)) E1) appears as result of W, S ((,,, E1). Hence, can apply Hoeffding inequality for general bounded random variables and derive for every E 2 0,
-2 vol
Pr
Σ i=1
P
E
P.
< 2 1 exp
This results in,
Pr( E.
E Al
< 2BE)
X,Y
-2c²
2 1 eexp
Furthermore,
13 X.Y
a)) 2x (xx)) $ A
E (x (Crand (1 (I)) Al
BE1[X $ A]
s B(0,(0, R) + +RLR
s 2Be.
Therefore,
Pr( E X.Y
(x)))(Crnnn
(00-((11))]] on)
< 4Ba)
-2
2 2xp
LNB
Now since have this argument for each
< d, by union bound have,
a))
Pr(vk: 55
E
< 4BE)
(13)
X.Y
2s
-2dexp
(B
e1)
Now one can argue a similar inequality should hold for length too. This time we can define
Q: = [I Crana(XX) xX wa].. Now these variables are also independent and result
25

---

of the construction of the covering set they are bounded by (.,, We also have,
N
/
0 E W;] + OPT
X.Praan y (ran((X.
E
E A) + OPT
X,brand 1=1
Σ a,l / y.(X.) A] OPT
/ (x. E A OPT
E X
N / C. (X, +
$ /
& A]
8 E /
A]
< + B /
x Cx((X,))dy1IX & B(0, R)
+ E / (x, $ LR)]
3c.
Now again by applying Hoeffding inequality for general bounded random variables we have for every
E 2 0,
N
N
22
Pr
Q
E
Q.1 < 1- --2eep
This results in,
Pr( / (r, yddy1(X E A] OPT
2 NR
< 4E) 2 - -exxp
Furthermore, by construction of Crand.
/
E X
(X)nd(X,y)dd11p $ A] =0
Therefore,
Pr( E / Crand(X, + OPT < 4E) 2 2cxp X
-2
(14)
Now a union bound between 13) and
leads to,
Pr
vk: 1 1 d:
E
Φx (X)(Crand (X,)) (1-a))
4B+ and
X.Y
E
Crane(XX ()) + OPT
<
-2
-2
2 1 - 2d exp
2exp
ANB
N
Recalling, N = (A, ||. 11,, ,1 where A denotes the covering number, we have the following
inequality (look at chapter 4 of 66
3 )
vol(A) (ol( 1))
N
voI(B(O, ef
(B(O, 1)).
81
26

---

This results in,
(x(X) (Cand (1 (1-a)) -a))
Pr
Wk 1 sssd:
d:
E X
<E+ 4BB and
/
E X
Crand(X,y)dyy + OPT
<e
-5
-2
2 exp
2 exp
1))
Since we have this inequality for every > O, we can pick small enough such that,
Pr
Wk vkilsk
oz (X) -
(1-
< + 4Bc and
X,Y
J/g Crana(X, (X,na(X,))dy + OPT <
1 2
This means there is realization of hrand and accordingly Crand, which denote them by h and C such that,
: w.lsksd
E X,Y
du (x))
<E 4Bs and
E /
C* (x OPT < 4E.
Now since we proved this for any E >> 0, we can put E m 1418). Therefore the following
statement holds. For every > 0 there exists h 00 and its corresponding function (² = 1[S(x,8) v) - h² (x)] such that,
vk 13 d:
E X.Y
(xX (1 <e' and
E J C*(X + OPT <E'
This immediately proves the statement (ii) of the Theorem 3.5
The statement (iii) also follows by the fact that by weak duality between the Relaxed Minimax Problem and the Relaxed Primary Problem we have -OPT s L Finally, let f denotes an optimal solution to the outer minimization of the Relaxed Minimax Problem. There exists a 3 such that f*(x) (B", ((x)). Now we have,
((8,,((())) = E 1 ((X)) (on)(c10 (xXX)) - - -11-a) a -B cx), ydd < E (B" ((x)) ((x)))((xxx)) (1- -a)
(f (,"""""") OPT
a1 -1- (11)))((1-)))
E S/S (dx
|| +e'.
Hence 8 <
111 prove the statement (i) of the Theorem 3.5
Proof of Theorem 3.5; Let us define 7 as the class of all measurable functions from X' to R. Now let us restate the Structured Minimax Problem for 0
Structured Minimax Problem:
Minimize Maximize (f h). fe
We can now rewrite this problem in the equivalent form of the following, where we change the domain of the maximization from Hos to corresponding set functions. Let CH= the set of all function from C(x,v) & y -> IR such that there exists h E H such that C(x, v) = [S((,, v) S h(z)).
27

---

Structured Minimax Problem:
Minimize Maximize 9o(JCC) JEF
CECu
We now proceed by defining convexified version of this problem. Let us define
Coon "H
a,C,(a, Σ a; 1, 0(V1
Now we can define the following problem.
Convex Structured Minimax Problem:
Minimize Maximize go (f, fEF
CEC
Naturally we can also define the Convex Structured Primary Problem.
Convex Structured Primary Problem:
Minimize CE
[len(C(X))]
subject to E -(xx VfeF
Now applying lemma E.4 we have,
Structured Minimax Problem
Convex Structured Minimax Problem
-Convex Structured Primary Problem
Let us call the optimal value for all these three problems OPT (here pay attention that based off of definition OPT is always negative number, hence when we are addressing the optimal length the term -OPT shows up). With some abuse notation, Let us assume {C where C. Ceve is feasible sequence of Convex Structured Primary Problem which achieves the optimal value in the limit, i.c, lim Ia(f. C+) = -OPT. This means, for any s 2 0, there OPT
Let us fix the value of for now, we will determine its value later. By definition, there should be (Ci) and corresponding (14) such that Ö. E Cho,, h, E H0, C 1[$(x, 3) I h2(2)). and we have C. = Et a,C, y) and E. a = 1, 2 (V1 t).
an index is such that [Elen(C,,)
Let us recall that the class F is defined as F = ((3, ((r) E Rd) where X + Rd is predefined function ka.k.a. the countable values that it takes. In other words, each o is vector in Rd and there exists z E X' such that (z)) = L, Then we have,
basis). Now let ( ) be all the possible
Σ (x) ( /1SS(E,0) s h=(=))p(ul=)dd)) plz)do (1 ai)
1
(15)
Here we implicitly assumed that (xx) is properly normalized so that the Right hand side don't 't need any extra normalization. Let define,
/. [[S(x, v) h(()))p(p))ddd
cov;(x)
28

---

1(x)) = / [[S(x, v) s h,(x))dy.
from 15 we have,
a (x((2)cov,(<))(())t = (1 a)
X 1=1
We can then write,
Σ accovi()) ) pla)dr - (1 a)
(16)
X;
where X; (xr E X can assume p(2;) > 0 for every as otherwise we can just omit that $ since it does not contribute to any integral due to continuity assumptions. (ii) {x, } partitions X, i.c. their union is and they are pairwise disjoint. Now the idea behind the rest of the proof is we show for each region Xj. there is single function h E H such that,
((x) = . Now two points are in order. (i) Without loss of generality, one
(i) / XG
Σ a,cov.(()) p(z)de= = / (ova(x)p(a)de,
where cova(x) = / 1|8(x, S (z))p(y)=)dy
(ii) / x
(x))p(1)dd /
Ix) Σ aab((t)) p(z)dc+
+ =p(()))
where 11xx) = / ([S(x,)) S M())ddy.
Hence, from now on we fix an arbitrary Xj and prove the existence of such For the ease of notation let us define X' Xj and p(x)
p(æ) This way f&x ((x) 1 and p(xr) is still continuous.
p(x)
Now we can rewrite our goals with this new notation. With a simple normalization we have,
( x Σ (.covi(s) p(z)da / cova (z)
where cova(1) / 118(1, S hxx)ppyy))dd
(ii) / (x)) / Eashte)) Mor)d +
where (x(x)) =/o [[S(x, v) s h(x)ddy.
Now, as a result of Dominated Convergence Theorem, there is large enough real value R such that for the of X {a e X ||]||2 & R, max 4(x) S R} we have,
(E[1,--..]
[x & L Sa, 1=1
(17)
and
cov,( & &1p(( S E1.
(18)
8
29

---

where the value of E1 > O will be chosen later in way that it would be small enough for the proof to work. Among the functions cov], cov, there should be at least two of them, without loss of generality cov, and cov2 so that Jx covi (f))dd 2 fg cov2(r))((rddz + 7 where > 0. Otherwise we have alreasy achieved our goal by picking the h2 with the smallest average length. Now assume < & (we will make sure to pick ε in way that it satisfies this condition). Hence we have,
/
/ cov2(x)p(2)dzz + 4
2 (z)((2)(
(19)
Now applying Lemma
F.5 there exists &g S & such that ((2)) 2 2 and for every x
X2 we have co) cov2(2) + 12- (Here one have to use Lemma E.5 using Z = (covi (x) co))(2)) 1 (x) 2 cov2(x))1 E &)
Let us consider the following three sets that partition the space X,
A X2
B X &
(20)
C = i
Note that these three sets pair-wise disjoint and cover the space X. LEt first consider the set C. we would like to consider a function he such that,
[o Σ (.)) M(x)do 1 covne (x))(a)d
where covne (x) / 1[S(,, S (c(
To do so, without loss of generality, we assume,
Lc (z) > / cov2(z))(z)dr 2... (z)((2)(())dz.
Hence,
c covi (o)((1))()) / ( a.co)(())) ū(x)dx 2 / (o)((z))(z)dz.
:c
For r E [0, oo) let,
f(r) 1 JoHBOr.) cov,(2)((z)dz
(CIBOO.)) (o)(())
Note that f(0) fc cov, (x))())()) and f(x)) Sc (r)((r) (ov,)))d). Also, as result of continuity assumptions, frr is continuous function, therefore we can apply Intermediate Value Theorem. As a result, there should be ru < oo such that,
S(ro) = ( Mo)de..
We then naturally pick be to be,
[ha(x) if if hc(x) = (1())) ((
(21)
Let us now consider the sets A and B. Note that by construction they both are subset of B(0, R). Now let us consider a 8-net for and a separate š-net for Similar to our arguments the proof of Theorem F.I. we can construct these d-nets in way that they partition A and B. That is to say have, A م are empty. Now, for each A, (and B,) we choose independently one of (h+ with probabilities {a+ H= at random.
NA A, and B - B, such that withing each š-net the pair wise intersections
30

---

covn ((x)d Let JA, (similarly J(B:j)) be the index of the function h; assigned to A, (similarly By). Then we have,
Event 1:
Nø Σ
Co ((x)dr +
co
(z)
A
== B3
AnB ==1
S vo.
Event 2:
Σ p(A)) 2 01
2 ((A).
j:((A,))=
Event 3:
Σ P(A)) 2 02 ((A). (:((A.))2
Now we can repeat the probabilistic argument of proof of Theorem F. here. The key insight is all of the three above-mentioned events are high probability events, in way that by letting (the precision of the covering net) to be sufficiently small then the probability of these events happening approaches to 1. Hence, there is deterministic realization that make all these events happen. Now on, fix that deterministic realization. Particularly, this means we have a realization that satisfies all the events for arbitrary small 6. Now the idea is to make small change in the configuration that comes from this realization that make the approximate coverage of event to be an exact coverage. With a little abuse of notation, let J[ (A, (similarly J( ((,,)) be the assignments of that deterministic realization. Without loss of generality, we can assume,
Na
I j=1 B3
No
covE F(t)da
Σ
(z) - S2,
JABB
A
(22)
where 82 2 0 and < constant x Vo (the case of 82 < 0 can be similarly handled). That is to say, our deterministic assignment (A..) and (B. j) led to small under-coverage 62. The idea now is to "engineer" the assignments of some of the A,s in way that we make the coverage exact while not changing the average length of the current assignment significantly. Remind the definition the event 3 we defined above. Recall that a2 and ((A) are strictly positive numbers. Hence, result of (19) and (20) we have, p(A2) 2 T2- Now we can argue through Lemma E.6 Consider the set [a.] J(A,j) = 2). We know from event 3 that p(Q) >
22
((A)
a27 Now let for
every j Q: : Z, = =((A). We know that Zj S 8 and Y = Ejeq Zz 2
027
Applying Lemma E.6
24
there exists Q' C Q such that Ejeg' p(A,) [ à st 2 81.. Recall that since Q' S Q, then for any E Q' we have J(A,)) 2. now if we reassign all the Ay's, Q', to hı (i.e changing J(A,j) for every j E Q') then the amount of added coverage would be, Ejes' P(A,) i where 12 appears following 19 and the fact that A, E N2. Hence, the amount of added coverage would bounded by,
E(A))
7
r7 8
ag +
(23)
12
2
24
JES
Recall that we can pick d as small as we want. Hence, we can pick 5 small enough that we have,
(24)
24
where the last inequality follows from the definition of E2 in 22 This can be done by letting
4
5 s
03
Now by noting 23 and
24 it should be clear that by reassigning all any Aj.
24
2
31

---

Now again as a result of Danskin's theorem, obj(3) is convex in B. Therefore, as a consequence of (26). 9 is minimizer of obj(3). That is to say. (f", h²) is an optimal solution to the Relaxed Minimax Problem. On the other hand, h" is also a solution to the Relaxed Primary Problem (as is j E Q', the total coverage added will be larger than E2 (hence in total we will over-cover). Now we can apply Intermediate Value Theorem once again. Let define for [0. oo].
f(r) - Σ - JEQ' (,,)( CovI (x)((()(=) +
cov2 cov2(2)p(z)da
A, AA\B(O.r)
Here note that again as a consequence of continuity assumptions f is continuous function. Also, (RR - (() 2 &2. Hence there exists To E [0, Rt such that, f(ro) - ʃ(0) = E2. That to say we can make the coverage exactly valid. Now let us analyze the deviation in length. Not that for x E AU B we have length is bounded by R. This means by reassigning the elements in the set Aj,
j E Q' the change in length is at most R x Ejeq' p(A₂) S 2R jt, where the last inequaity gd
comes from the fact that Ejeq' ((A,) E
2 27 8t). Here again by choosing small enough,
particularly & 2R- 2
we can ensure the change in length smaller than e, hence we achieved
our goal.
Proof of Proposition 3.7: Let h" H. be an optimal solution of the Relaxed Minimax Problem and the Relaxed Primary Problem, when the optimization is over all the measurable functions from X' to R. Let us denote the corresponding optimal solution to the outer minimization of the Relaxed Minimax Problem by f Recall that F is a finite dimensional affine class of functions. That is to say there exists a vector f such that (xx = (B*, ((x)) fa- (z)) Since h" is a solution of the Relaxed Primary Problem so it should be conditionally valid with respect to class F. Therefore, as result of Lemma 3.4
we should have,
Va Da (Ja, h3)
= ō. 3a
(25)
Now define obj(3) = max 9o (fs, he). Since θ is compact set and go (fo, ha) is convex (in fact de linear) in /3 the Danskin's 'ss theorem applies ob)( Therefore, as result of 25
Ö E 0g obj(3)
(26)
solution to the Relaxed Primary Problem when solved over all the measurable functions). Putting everything together, ht is a joint optimal solution to both the Relaxed Minimax Problem and the Relaxed Primary Problem, hence we have strong duality.
Proof of Proposition
3.3:
Let us start by recalling the definitions,
9a (f. C) = E [(x) f 1 1 C(X) - (1 - (a- -E E 1/// 1/2 E C(X)]dy
where
Cy(x) = (y E f())p(1))) 1}.
Now, fixing f E FF, all we have to show is that go (f. Cf(z)) ga C(x)) 2 for every C(x)
X 2"
Claim
0 for every C(x) : X +2
-
proof: We have,
Ex (((XXXXX))) ( -I Jou 2 2x
9a
( Ex / (((X)((lXX)-) 11 / [[ 1/v (IE [W
(c) Ex / (F(X)x((X) (I
2 0,
32

---

where, (a) follows from the definitions. (b) follows from the definition of set difference operation ()) where, A {z x E and x & B}, and (c) comes from the definition of Cy (z)). The proof is complete now. One can define,
|1(XXX0XX) 1) (II dy.
Ex(d(Cy, C)] Ex
and rewrite the above calculation
Ja C(x)) 9. -
This reformulation is very intuitive. at a high level, it says maximizing 9o (J, C(x)) over C, is equivalent minimizing distance between C and Cy.
Proof of Proposition 3.1: Let us start by restating the proposition.
Proposition F.2 The Primary Problem and the Minimax Problem equivalent. Let (J", C (x)) be the optimal solution of Minimax Problem. Then, C is also the optimal solution of the PP. Furthermore, C has the following form:
(27)
Let us also recall the definition of Primary Problem,
Primary Problem (PP):
Minimize ((x)
E [len(C(X))]
E B [[1030 1/8 SangfiieecS c(X)) -1 -1- =0, vf
subject to
Recall that in this paper of functions (see section 2.1).
that F ((3, (3 Rd) is finite dimensional affine class
Assuming & [01, 02, 0a). The Primary Problem can be equivalently written in terms of d linear constraints on the prediction sets C(x).
Primary Problem- finite constraints:
Minimize ((x)
E [len(C(X))]
E (1
subject
=0,
Wi E [1,d].
We now take a closer look at the main optimization variable, i.e. the prediction sets C(x), and put in the proper format. The prediction sets C(xr) be equivalently represented by a function C=Xx) x + (0. 1} such that C(x, y) = 1yy E C(x)). Furthermore, we can expand the optimization domain from C(x, v) X' x
(0, 1) C(Λ,y) X' ) [0, 1]. One should pay attention that this change does not affect the optimal solutions as the solutions will be integer values. Putting everything together we can write the following problem,
Linear PP
S Cla, (la.v)p())u())ddde Jxxy
Minimize C(s,))x'x
subject
E
(x) ((x,Y)
=0, vi W [1,4].
Here is the lebesgue measure; recall from Section 2.1 that we defined length through the lebesgue measure on y R, which is equivalent to cardinality of a set in the case where ) is discrete and finite set. This problem Linear program in terms of C with finitely many constraints. Also, the Linear PP, includes the Primary Problem in the sense that any solution to the Primary Problem is
33

---

feasible solution for Linear PP. That is to say, to prove Proposition 3.1 we just have to prove it for Linear PP.
For d = 1. Linear PP can be seen through the lens of the Neyman- Pearson Lemma in Hypothesis
Testing [69] As result, our analysis of the Linear PP (for general d) be considered as
extension of this lemma which will be done using the KKT conditions.
Now, let rewrite the Linear PP:
Minimize
Cla, ((()))(()))
Xxy
/ (1(x) u)v f)drdy a) (1) =0, [1.] Xxy C(x,y) E [0.1]
subject to:
Vo E E.E.E
The above is a standard linear program on C(x, y). In what follows, we will find a closed-form solution using the dual of this program. Here, the "optimization variable" C(z, y) belongs to an space. Hence, in order to be fully rigorous, we will need to use the duality theory developed for general linear spaces that are not necessarily fiite-dimensional. For reader who is less familiar with anfiite-dimensione spaces, what appears below a direct extension of the duality theory (i.e. writing the Lagrangian) for the usual linear programs in finite-dimen miite-dimensionl spaces.
Let F be the set all measurable function defined on X' x y. Note that F a linear space. Letr Ω be the set of all the measurable functions X' y which bounded between and 1; L.e.
{C E s.t. C: : X x y [0, 1]}
(28)
Note that 52 is a convex set. We can then rewrite our linear program as follows:
Minimize
Jxxy
((a,))(())v(yddrdy
/
subject
(x(x)((z,))ll (ilddy (1 a) =0, Vi [1.d]
xxy
Ceo
Moreover, let us define the functional F F - as
[ (lx.))p())v())ddded
F(C)
(29)
and also define, for E [1, d). the functional G; F + R as
(C) /
(x(x))((,, () 9)) (1 a).
(30)
xxxy
Finally, we define the mapping G F Rdd as
G(C) (C), G2 Ga(C)]
Note that a linear (and hence convex) mapping from F the Euclidean space RRd
Using the above-defined notation, our linear program becomes:
Minimize
F(C)
subject to: G(C) 0
CEn Ω
where 0 E IRd the all-zero vector.
Note that the fcasibility set of the above program is non-empty, as C(x,y) 1 a, for all (x, v) X' x V, is feasible point. We can now use the duality theory convex programs in vector spaces (See Theorem 1, Section 8.3 of [68]; Also see Problem in Chapter 8 of the same reference). Specifically, let OPT be the optimal value achievable in the above linear program. Then, there exists vector B E Rdd such that the following holds:
OPT
inf (F(C) (B, G(C))) Cen
(31)
34

---

where (3, G(C)) denotes the Euclidean inner product of the two vectors B, G(C) R Here, note that the vector [ the usual Lagrange multiplier.
By denoting
(x) = (01(z), ... ,d(())) and using 330. we can write
J xxy
(3. GC))
(B, (x))C(( v)p(z, v)dady - (1 a) 1),
where 1 E R is the all-ones vector. As a result, by using 29) in order to solve the optimization in 31 need solve the following optimization:
( C(x, (o(x)u(y) - (B, & (z))p((, v)) dædy (1- CEn
inf
Xxx
And by noting the fact the p(z, v) p(z)p(y æ), and removing the term - (1-a)(B3 ( 1) which is independent of C, our dual optimization becomes:
U C(r, w) v(y) (G, (x)))p(ul))) p( inf CER
(32)
XXX
Now, it is easy to see that as C( y) E [0, (due to the constraint C' E 22), the above optimization problem has dlosed-form solution C*:
if (B. + (x))p(ul)) v(v). (B, (<)))(()))) < v(y),
(*,,,))
(33)
E []
otherwise.
Finally, note that in this paper the measure is considered to be the Lehesgue measure see Section 2.1 hence, up to a constant normalization factor that can be absorbed into f3, we have v(v) = 1 all E y.
The structure given in (33 is also sufficient. Le. for any pair (B, C*) such that (i) C* has the form given in (33; and (2) C* satisfies the coverage-constraints G(C*)= O, then C is an optimal solution of the Primary Problem(F). This sufficiency result follows again from the duality theory of linear programs in linear spaces; E.g. see Theorem 1 in Section 8.4 of [68]. This necessary and sufficient condition known Strong Duality, which then results the equivalence of Minimax Problem and Primary Problem, i.c we can change the order of min and max.
G Proofs of Section
Proof of Theorem 4.4 Let us recall the algorithm.
CPL:
Minimize Maximize (n.n(f.h) h), NEW
/EF
where, (xx = tu Ey S(x.v) s M(x)).
For the ease of notation let us call g(f, = Jo.n (f. ft). let us also call the stationary solution to CPL by hCpt, and föPL. Now since ğ a smooth function with respect to both of its arguments we have the following optimality condition,
d de
HrörL + + hCPl)
0, for every F.
(34)
==0
Recall that J is d-dimensional affine class of functions over the basis t ..,, ,.]. We can then rewrite 34 as what follows.
d
de @(Crr + tdjj hCrl)
0, for every j E [1.... , d].
(35)
l==0
Now looking at the definition of (({h))=
f(zi) ((a))([[Seo i[S(2,, v.), h(x,) -a) a1)
11111 Σ /
(i(S(ZL)) s h(x;)) -(1 -a))
a) dy.
35

---

We can take the derivative with respect to f. Hence we can rewrite 35 as what follows:
(y((n)) (Ist -1
0, for every j E [1, d|.
(36)
One can think of the mathematical term above as the smoothed version of coverage under covariate shift Øj. Now we can apply Lemma E.3 Therefore, fixing j E [I,-.., .d], with probability - ó we have,
(s(xz) i[s(11, ())) (1 -00 E [)(()} i[s(,, v). (xpr (1
}]
V2B In (2N(H)ddwi))
2Bs
for any 0.
V2Ta
vn
Combining with (36) get,
V2B /2By/1. (2Ning
i[S(,, v). (x) - - -n)
2Bs 2To
E
(x)
for any & > 0.
vn
Union bounding over 36 we have with probability - 8 for any j E [1,..., ,d.
V2B v In
(2N((H,
(x) i[S(,, v). (x)r (1 -i
2Bc ViTa
E
for any E >>
Vn
(37)
In other words, proved that the expected smoothed version of coverage is bounded. The last step that we have to take is then to prove that the expected smoothed coverage is actually close to the expected actual coverage. The following claim makes this precise.
Claim The following inequality holds for every j E [1,.... ,d].
E 05(2)) i|S( v), herr (1 -1- -
- E oz (x))) (z)
1[5(x. S hcrr(()) (11-))
S BLoy
Proof.
(5(2) hipl a) })}] (5(()) 115(x, s hx)r(()) -(1-a)))))))))))
E
E M), (x)] - EE (z) v) - hx)l(
IE
(x(+))
(((S(,,), 1[5(z.)) v) hx))(=)))
(6)
(i(S(z, w) (x)) - 1[( < hem (x))) ]
< BE
BEx Esix
(i(S(z, v), (x)) 1[S(,, y) & (.)r
(c)
< BEx La
π BLoy V
2
36

---

where (a) comes from triangle inequality, (b) is derived by the definition of B m suprex P, (z), and (c) is followed by assumption and Lemma E.2 Now combining 5,
Claim and 37 we have with probability
1[5(x, y) S hx)r,())] -(1-)))
[5(z)
v2B VaByll
π +
2Be
BLo
+
for any >> 0.
v 2To
VT
Putting = V
and & we have for every j E [1,... ,l,
V2B
2d
+ -BL
+
2B V2T
E (5(2)
[[s v) & (crl(()) -1
Let us also remind that each element f E F can represented by a 3 Rd where we use the notation f(z) (3, ((x)) fz( (look at section 2.1 for more details). By linearity of the class F we can conclude with probability 8 for every f8 E F.
|| [|311
/In In (dd((H.dw..) 1 + +113||1BL
+11 /
fa(æ) 1[5(2,1) s (cpL - -aa)a)) ai
E
Vn
H
Marginal Coverage Regression Experiment
In this section we aim at showcasing the ability of CPL in improving length efficiency in designing prediction sets with marginal coverage validity. We compare the performance our method, CPL, in terms of marginal coverage and length, to various split conformal prediction (SCP) methodologies. Specifically, we compare with: (i) Split Conformal (SC)
22 44 and Jackknife (45), the main methods in standard conformal prediction to achieve marginal validity; (ii) Local Split Conformal (Local-SC) [22 41 and LocalCP [12. as locally adaptive variants of Split Conformal; (iii) Conformalized Quantile Regression (CQR) 35 as state-of-the-- method for achieving marginal coverage with small set size.
Following the setup from 35 we evaluate performance on 11 real-world regression datasets (see Appendix [ and report the average performance all of them. Each dataset is standardized, and the response is rescaled by dividing it by its mean absolute value. We split each dataset into training (40%), calibration (40%), and test (20%) sets.
We focus on methods applicable to black-box predictors and conformity score. We compare SC, Jackknife, Local-SC, LocalCP, and CPL using the conformity score S(z, y) lv fx)), where f is a NN with two hidden layers of 64 ReLU neurons, trained on the training set.
First Part:
We evaluate CQR, which requires quantile regressors trained on the training set. We also examine our method combined with CQR (i.e. we use the score obtained by CQR), referred to as CQR+CPI. Tables and 2 summarize our results, reporting average performance over 100 random splits the datasets. All reported numbers have standard deviations below percent.
Second Part:
Table 1: First part Length
Table Second part
Method
Coverage
Method
Length
Coverage
Split Conformal
2. 2.16
89.92
Loc+Loc
1.59
90.15
Jacknife
1.95
89.81
Loc+L
1.48
90.01
Local-SC
1.81
89.95
CQR+SC
1.40
90.05
LocalCP
1.73
90.09
CQR+Jacknife
1.32
89.78
CPL
1.68
90.11
CQR+CPL
1.16
90.06
In Table 1, our method is shown to improve the interval length using generic conformity score. In Table 2, our method shows strength with sophisticated scores, highlighting that minimax
37

---

procedure significantly enhances length efficiency across various tasks and scoring methods. Our framework's 's advantages over CQR are: (i) It can use CQR scores to improve length efficiency, and (ii) it can use other scores, including residual scores with pre-trained predictors. This is advantageous when training quantile regressions from scratch is costly, while pre-trained models are accessible.
I CIFAR-10 Experiment
We conducted our experiments on the CIFAR-10 dataset, using two distinct training procedures: empirical risk minimization (ERM) with cross-entropy loss, and conformal training (ConfTr by [65]). The neural network architecture employed in all setups ResNet-32. To evaluate the predictive performance of these models, we aimed to generate prediction sets that achieve a marginal coverage level of 95
For the conformal training procedure, we utilized batch size of 500 and employed split conformal prediction to compute the prediction set sizes, which is a crucial component of the conformal training approach. We further fine-tuned the hyperparameters using grid search optimize the setup.
We considered four experimental scenarios: training the model with either ERM or ConfTr, followed by calibration using either split conformal prediction CPL. The primary goal was compare the effectiveness of these approaches in terms of both coverage and prediction set efficiency.
In setups involving ConiTr, we further optimized the data split ratios improve the length efficiency of the prediction sets, which explains the variation in train/calibrationneess splits across the different performed the split ratios,
ConfTr setups. For the ERsed setups, optimization as the focus was to emphasize the black-box nature of calibration approaches like CPL and split conformal prediction, which act as wrappers around the trained models without altering the training procedure.
As shown in the results (see Table CPI. combined with ConfTr produces more efficient prediction sets in terms of average length compared to split conformal prediction. This highlights the effective- ness of CPL in improving length efficiency while maintaining the desired coverage level, particularly in conjunction with conformal training.
Training
Calibration
Coverage
Avg Length
Samples (Train/Calib/Test)
Base Accuracy
ERM
Split Conformal
0.951
2.36
40k/10k/10K
82.6%
ERM
CPL
0.948
2,06
40k/10k/10k
82.6%
ConfTr
Split Conformal
0.954
2.11
45k/5k/10k
82.3%
ConfTr
CPL
0.947
1.94
35k/15k/10k
82.3%
Table 3: Comparison of different training and calibration methods
Refrences for 11 datasets for Section
Here we list all the datasets.
MEPS-19 7
MEPS-20 72
MEPS-21 [72
blog feedback Bolog-data]a 73
physicochemical properties of protein tertiary structure (bio)
bike sharing (bike) 75
community and crimes (community) 776
Tennessee's 's student teacher achievement ratio (STAR)
concrete compressive strength (concrete) 77
Facebook comment volume variants (facebook-1 1)
79
Facebook comment volume variants two (facebook-2
80
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the contributions and claims are properly explained in the introduction and abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We have separate section called Limitation and Future work that we discuss the limitations of the current work and the possibilities for further research.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: All the assumptions are noted the main body of paper in proper forms. We have moved all the proofs to Appendix section due space limit. In the appendix. have derived all the proofs carefully and either proved or gave proper references for all the technical details.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experimental setups are very easy to understand and well explained. We will also publish our codes for the camera ready version in case of acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We will publish codes for the camera ready version in case of acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/publiic/ cabblcc/guides gwt.///ieee//eee// Codeeoobiiieeeee dusee/uuuude//oeuubbiiii SanSSuubissss solbbmmsssioo ssionnoiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have explained all the details necessary for a self-contained experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we do report all the necessary statistics to have fair comparison.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
41

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The running time for the experiments of this paper can also be done on CPUs (in the order of half day). The point of view of experiment section regardless of compute time.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics attpps://neurr: wttpippp....pppeeee hc/ppubbii//tthhcccicidded.....d
Answer: [Yes]
Justification: This paper has no foreseeable ethical issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: In this paper, we focus on developing new algorithmic framework for Conformal Prediction which has immediate applications in areas such as healthcare. We do not anticipate any negative socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
42

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We don't 't see any foresecable need for safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We have properly cited all the datasets and prior works.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
43

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There is no new asset as an output.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not perform such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We do do such studies.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
44

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "jv4tPUJep7", "reviewer": "Reviewer_vXbJ", "summary": "The paper introduces a novel length optimization technique for conformal prediction designed to produce the shortest valid prediction intervals.", "questions": "- The equation (2) appears to be equivalent to conditional coverage instead of marginal coverage in Gibbs et al.(2023) [1].\n- In figure 2(b), the \"optimal\" solution is with respect to the choice of score function.\n- In chapter 5.3, do you compare with weighted version of split conformal or non weighted?\n\n\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "limitations": "See above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a novel framework, Conformal Prediction with Length-Optimization (CPL), which effectively balances the need for conditional validity and length efficiency in conformal prediction.\n- Extensive empirical work is provided demonstrating CPL's performance compared to different methods across various real-world and synthetic datasets.\n- The paper is overall well written. Beside the theoretical framework, it also provides practical insights into its implementation, which makes it easier to follow.", "weaknesses": "- The computational cost of the proposed algorithm seems expensive.\n- The length optimization framework dependent heavily on the structure of covariates, which might not be feasible in all practical situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing the strengths of our paper. We appreciate your acknowledgment of the novel framework introduced in the paper,  i.e., Conformal Prediction with Length Optimization (CPL), and the extensive empirical work we conducted to demonstrate its effectiveness. Your feedback on the clarity and practical insights of our writing is also greatly appreciated.\n\nBelow we respond to your comments.\n\n**Computational Cost**\n\nSolving minimax problems is a common approach within the machine learning community, particularly in areas such as adversarial learning. In the specific case of CPL, the outer minimization step is computationally lightweight and can be viewed as a form of hyperparameter tuning. For instance, in scenarios focused on marginal coverage, the outer minimization reduces to a simple scalar optimization. Additionally, the outer minimization is linear in terms of its variables, which simplifies gradient calculations. The complexity of the inner maximization is comparable to training a standard machine learning model; e.g. by using standard gradient steps on the parameters. In general, the complexity of the inner maximization is similar to the complexity of training for example a neural network; and CPL requires very simple neural networks--e.g. two layer MLPs, or fine-tuning a pre-trained model. We will ensure to include a comprehensive discussion on scalability in the camera-ready version of the paper.\n\n**Structure of Covariates**\n\nOur framework is designed to work for any given (black-box) predictive model and score function. Doing length optimization in this scenario requires learning features of the data to properly adapt the threshold function for the scores. These features are often present in real world datasets and can be learnt from data as we showcased in our experiments.\n\n**Additional Experiment on LLM Question Answering**\n\nTo further demonstrate the applicability/scalability of our method, we will include a large-scale experiment involving LLM question-answering in the camera-ready version (please see the uploaded 1-page PDF file). This experiment uses multiple-choice question-answering datasets, including TruthfulQA, MMLU, OpenBookQA, PIQA, and BigBench. The calibration data for MMLU alone consists of approximately 100,000 prompts and answers, illustrating the large scale of this experiment. \n\nThe goal is to quantify the uncertainty of Llama 2 and create prediction sets using this model. We follow a procedure similar to that proposed by prior work [4], adapting it as follows: for each dataset, the task is a multiple-choice question-answering. We pass the question to Llama 2 using a consistent prompt: \"This is a 4-choice question that you should answer: {question} The correct answer to this question is:\" We examine the logits of the first output token for options A, B, C, and D. Applying a softmax function gives us a probability vector, and we define the conformity score as $1 − \\text{probability of the correct option}$\nsimilar to $1-f(x)_y$ for classification.\n\nCPL is implemented using a linear head (as $h(x)$) on top of a pre-trained GPT-2. In more detail, with GPT-2 having 768-dimensional hidden layers, the inner maximization involves optimizing a 768-dimensional linear map from GPT-2’s last hidden layer representations to a scalar. We also implemented the baseline method that directly applies the split conformal method to the scores. Please **see the uploaded PDF for plots** and a caption for more details.\n\n**Other Comments**\n\n\"The equation (2) appears to be equivalent to conditional coverage ...\"\n\nIt is indeed equivalent to the notion of conditional coverage of Gibbs et al. [1]. As we also cited in our submission, the notion of conditional coverage was first introduced by Gibbs et al. [1]. We built upon their notion and introduced length optimization on top of it.\n\n\"In figure 2(b), the \"optimal\" solution is with respect to the choice of score function.\"\n\nThat is true. We thank the reviewer for bringing up this point. we will clarify this in the revised manuscript.\n\n\"In chapter 5.3, do you compare with weighted version of split conformal or non weighted?\"\n\nWe compare with both split conformal and the method of Gibbs et al. [1]. One can interpret the method of Gibbs et al. [1] as a generalization of weighted conformal prediction in the sense that weighted conformal prediction provides conditional validity with respect to a single covariate shift whereas the method of Gibbs et al. [1] provides conditional validity with respect to a class of covariate shifts.\n\n**References**\n\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "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": "", "extra_scores": {}}, {"review_id": "9ZEx5ZCtAe", "reviewer": "Reviewer_qXD6", "summary": "This paper introduces a new formulation of conformal prediction that not only aims to achieve the coverage property but also explicitly optimises the length of the prediction intervals. The framework is generic and can be applied to various conformity scores. The authors evaluate the approach through extensive empirical evaluations.", "questions": "* None.", "limitations": "* None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and enjoyable to read.\n* The motivating example and results, particularly the finding that the optimal length of the predictive set should be the level-set of the conditional probability and the smoothing step, are insightful and valuable for the community.\n* The experiments are thorough and cover different dimensions, including marginal coverage, group-conditional coverage, and performance under covariate shift.", "weaknesses": "* The readability of the figures could be improved.\n* The notation used for expectations, such as in Equation 2, is a bit misleading. It appears as though the expectation is taken only over $X_{n+1}$, whereas I suppose it also includes averaging over the calibration set.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and positive evaluation of our paper. We appreciate your recognition of the strengths of our work, particularly the formulation of conformal prediction and the insights gained from our motivating example, as well as the thoroughness of our experiments across different dimensions.\n\nWe acknowledge your feedback regarding the readability of the figures and the notation used for expectations, particularly in Equation 2. We agree that clarity in these areas is crucial, and we will make the necessary improvements in the camera-ready version to enhance the paper's overall presentation and precision.", "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": "", "extra_scores": {}}, {"review_id": "WHyVlY9tKR", "reviewer": "Reviewer_5vGW", "summary": "The paper presents a novel framework for conformal prediction that aims to balance conditional validity and length efficiency. The authors propose CPL to address the challenges of constructing prediction sets that are conditionally valid and have optimal length. This paper is well-written, provides a comprehensive review of related work, and demonstrates significant advancements in the field of conformal prediction.", "questions": "1) The paper assumes L-Lipschitz continuity for conditional distributions and bounded derivatives for conformity scores. How sensitive is the proposed CPL framework to violations of these assumptions in practical applications?\n\n2) The proposed CPL method involves both inner maximization and outer minimization steps. What is the computational complexity of these steps, and how does it scale with the size of the dataset?\n\n3) The paper discusses handling various classes of covariate shifts. How robust is the CPL method to unexpected or unmodeled shifts in the data distribution?\n\n4) How does the performance of CPL vary with different choices of conformity scores and hypothesis classes H? Can the authors provide a sensitivity analysis to show the robustness of their method?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The introduction of CPL is a significant contribution. It fills a gap in the existing literature by providing a unified approach to achieving both conditional validity and length efficiency.\n\n2) The paper provides both infinite sample and finite sample guarantees for the proposed method. This adds a strong theoretical foundation to the practical applicability of the method.\n\n3) The authors conducted extensive experiments on diverse real-world and synthetic datasets across both classification and regression settings. The results demonstrate the superior performance of CPL compared to state-of-the-art methods.\n\n4) The use of a minimax framework to derive optimal prediction sets is a sophisticated approach that shows deep theoretical insights.\n\n5) CPL can use any conformity score and adapt to different coverage requirements, making it highly versatile.", "weaknesses": "1) The paper assumes L-Lipschitz continuity for conditional distributions and bounded derivatives for conformity scores. While these assumptions are standard, they might limit the applicability of CPL in scenarios where these conditions do not hold.\n\n2) The computational complexity of the proposed method, especially the inner maximization and outer minimization steps, is not thoroughly discussed. Addressing the scalability of CPL for very large datasets would be beneficial.\n\n3) While the authors acknowledge the limitation regarding handling infinite-dimensional classes, they do not provide a concrete roadmap for future work in this area. A more detailed discussion on potential extensions and their feasibility would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to the reviewer for their thoughtful and detailed evaluation of our submission. We are glad that the introduction of the Conditional Prediction Length (CPL) framework has been recognized as a significant contribution to the field of conformal prediction, and we appreciate the acknowledgment of our theoretical foundations and extensive experimental validation.\n\n**Regarding Assumptions**\n\nWhile the Lipschitz continuity and bounded derivative assumptions are necessary for the theoretical aspects of our work, they are not prerequisites for running CPL. The CPL framework is designed to be agnostic to these assumptions. In our experiments, we demonstrate CPL's robust performance using various practical score functions, including $1-f(x)_y$ for classification, which may inherently violate these assumptions due to its discrete nature. Also in regression tasks, we have showcased CPL can be used in conjunction with practical scores like CQR and improve the length efficiency. It is worth noting that other methods, such as split conformal prediction, also require similar assumptions for meaningful analysis. For example, if the score distributions include deltas (violating the Lipschitz assumption), split conformal methods might produce overly conservative prediction sets.\n\n**Scalability**\n\nSolving minimax problems is a common approach within the machine learning community, particularly in areas such as adversarial learning. In the specific case of CPL, the outer minimization step is computationally lightweight and can be viewed as a form of hyperparameter tuning. For instance, in scenarios focused on marginal coverage, the outer minimization reduces to a simple scalar optimization. Additionally, the outer minimization is linear in terms of its variables, which simplifies gradient calculations. The complexity of the inner maximization is comparable to training a standard machine learning model; e.g. by using standard gradient steps on the parameters. In general, the complexity of the inner maximization is similar to complexity of a neural network; and CPL requires very simple neural networks--e.g. two layer MLPs, or by fine-tuning a pre-trained model. We will ensure to include a comprehensive discussion on scalability in the camera-ready version of the paper.\n\n**Infinite Dimensional Classes of Covariate Shifts**\n\nAddressing infinite-dimensional covariate shifts for coverage validity is an exciting direction for future work. A promising approach involves employing regularization techniques, as discussed by Gibbs et al.[1], though their framework lacks length optimization. Exploring regularization methods that integrate length optimization while maintaining strong duality results, as in Proposition 3.1, presents a valuable research avenue. We will expand on this idea in the future work section.\n\n**Unexpected or Un-modeled Covariate Shifts**\n\nAs the reviewer noted, our framework presumes a pre-defined class of covariate shifts. Addressing unexpected or un-modeled shifts involves several considerations: (i) Providing valid coverage without any prior knowledge or assumptions about covariate shifts is equivalent to solving the full conditional coverage problem, which is infeasible (as discussed in [1]). Thus, some assumptions or prior knowledge are essential. (ii) There is a growing body of work on leveraging unlabeled data from target distributions to ensure valid coverage amidst unknown covariate shifts. Investigating length optimization in such contexts could be a fruitful research direction. (iii) Utilizing a pre-trained foundational model (fine-tuned for the task) to define the class of covariate shifts can potentially capture unexpected shifts, similar to the experimental setup in section 5.3, where covariate shifts were not explicitly defined.\n\n**Regarding the Hypothesis Class $H$**\n\nOur experiments explore a variety of practical conformity scores in both regression and classification settings, demonstrating CPL's adaptability and robust performance across different scenarios. We have also evaluated CPL's effectiveness using both simple models, like Multi-Layer Perceptrons (MLPs), and by fine-tuning more complex models. If the model is too simple, it may fail to capture the necessary features for effective length optimization. Conversely, overly complex models might lead to overfitting, which could hinder finite sample generalization.\n\nTo provide a sensitivity analysis of $H$ **we conducted a numerical evaluation** based on the experimental setup in Section 5.2. We report the mean interval length over the test data while varying the number of activation functions in the hidden layer of the two-layer MLP used as $h(.)$ and the number of calibration samples and test samples are fixed to 50K. The results, depicted in the **uploaded PDF**, demonstrate how the mean interval length changes with different MLP complexities, highlighting CPL's robust performance across a range of model complexities.\n\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "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": "", "extra_scores": {}}, {"review_id": "V7o2HznMXa", "reviewer": "Reviewer_xcAK", "summary": "The paper proposes a new method to improve the efficiency and conditional validity of conformal prediction methods by proposing a minimax optimization problem, whereby the length of prediction intervals is minimized while ensuring (approximate) conditional coverage. The proposed method, conformal prediction with length optimization (CPL), comes with finite-sample guarantees for both the gap to optimal length and conditional coverage. Empirically, CPL is shown to produce narrower prediction intervals than previous methods both with and without distribution shifts.", "questions": "1. Which data is used to optimize $h(\\cdot)$ and $f(\\cdot)$ in Algorithm 1? I assume one needs a separate dataset (distinct from the calibration one) so as not to break exchangeability between calibration and test data, but, unless I missed it, this is not mentioned anywhere.\n2. In Figure 3, right-hand-side plot, CPL achieves smaller mean interval length than the optimal oracle in many cases. How is that possible?\n3. I am somewhat confused by the notation. Sometimes $f(\\cdot)$ is used to denote the shift, sometimes it is used to denote the machine learning model. In line 280, what exactly is a NN with two hidden layers?\n4. How are $h(\\cdot)$ and $f(\\cdot)$ parametrized in the experiments? Could the improvement in efficiency provided by CPL in these datasets be explained by the extra learnable parameters in $h(\\cdot)$ and $f(\\cdot)$? Or in other words, could we get the same performance simply by considering a more powerful model class for the underlying regressor or classifier?\n5. Could the authors share some intuition or results on how tight the bounds on Theorem 4.2. and 4.3. are? How do they compare to previous results? For instance, unless I am missing something, in comparison to Theorem 4.2. in this paper, Theorem 2 in [1] seems to provide a tighter bound that converges faster at $O(1/n)$.\n6. The description of the covariate shift experiments in section 5.3. is very unclear. Could the authors elaborate further on the experimental setup? \n\n### References\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).", "limitations": "The paper does comment on its limitations and provides promising avenues for future work.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Conformal prediction is a relevant uncertainty quantification method, and improving its predictive efficiency and robustness to distribution shifts are extremely important problems in the field. The proposed method is, to the best my knowledge, novel and addresses both issues in a principled manner.\n- The proposed method, CPL, can be applied on top of any pre-trained classifier, which facilitates its use in practice.\n- CPL comes with convergence guarantees in terms of coverage and predictive efficiency, and the mathematical results seem sound.\n- The empirical results show the proposed method outperforms the baselines in terms of predictive efficiency.", "weaknesses": "- While the paper is not exactly difficult to follow, I feel the presentation could be greatly improved. Some of the notation is confusing (see e.g. question 3 below) and there is barely any discussion on the theoretical and empirical results (see comments on experiments below).\n- I am not entirely convinced of the impact of the contributions of the paper. The novelty is somewhat limited—one could summarize the contribution as applying conformal training ideas [2, 3, 4, 5] on top of the machinery introduced by Gibbs et al. [1]—and this is not compensated by the results, which, at least in the way they are currently presented, are underwhelming: one gets some convergence guarantees, but it is not clear how tight or useful they are,  and one gets some gains in predictive efficiency, but the empirical evaluation leaves a lot to be desired (see comments below).\n- Experiments are not convincing. \n    - The experiments are not well described or analyzed. There is no description of the setup (only references to other papers). Tables and figures are not properly captioned. There is no report of any statistics besides mean results, despite the authors’ claims in the checklist. The only figure with error bars is Figure 3, but even there the reader has no idea how those were computed and what they mean.\n    - I am not convinced the experiments in the paper qualify as “extensive empirical evaluations”. The experiments are very small in scale, and similar methods that also directly optimize for small prediction intervals are missing [2, 3, 4, 5]. Split localized conformal prediction [6] is also a relevant baseline in my opinion, since $h(x)$ is essentially an estimator of the quantile of the conditional distribution of scores given X, as proposed in [6].\n    - Additional computational costs incurred by the proposed optimization procedure are not commented on. The computational efficiency of conformal prediction is one of its main selling points, especially with ever larger and more expensive machine learning models, and the cost of any additional step might be relevant. The fact that the experiments in the paper are very small in scale and can be run on CPUs does not mean the computational cost is irrelevant.\n\n### References\n[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. \"Conformal prediction with conditional guarantees.\" arXiv preprint arXiv:2305.12616 (2023).\n\n[2] Stutz, David, et al. \"Learning Optimal Conformal Classifiers.\" International Conference on Learning Representations.\n\n[3] Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong. Efficient and differentiable conformal prediction with general function classes. arXiv preprint arXiv:2202.11091, 2022.\n\n[4] Bellotti, Anthony. \"Optimized conformal classification using gradient descent approximation.\" arXiv preprint arXiv:2105.11255 (2021).\n\n[5] Correia, Alvaro HC, et al. \"An Information Theoretic Perspective on Conformal Prediction.\" arXiv preprint arXiv:2405.02140 (2024).\n\n[6] Han, Xing, et al. \"Split localized conformal prediction.\" arXiv preprint arXiv:2206.13092 (2022).\n\n### Minor Issues\n- I find the usage of the term “structured prediction sets” somewhat unnecessary. At the end of the day, this is no different from group conformal prediction or even adaptive prediction sets, where the threshold depends on the input x. The extra terminology only adds confusion.\n- Figure 1 does not add much to the paper, in my opinion.\n- Line 7: I believe the hyphen is unnecessary in “Conformal Prediction with Length-Optimization”.\n- Line 76: “the” is repeated.\n- Line 90: It seems a word is missing after “overly”.\n- Line 137: I think “converge” should be “coverage” instead.\n- Line 192: “that” should probably be removed.\n- Line 228: “relax” should probably be “relaxed”.\n- Line 255: Typo “velow”.\n- Line 548: Typo $Z{h_2}$\n- Line 664: Typo “traingle”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback. We appreciate the recognition of the strengths of our proposed method, CPL, particularly its novel approach to enhancing predictive efficiency and robustness in conformal prediction. We are glad that the reviewer mentions CPL's potential to be applied on top of any pre-trained classifier, its sound mathematical underpinnings, and its promising empirical results.\n\nDue to space constraints, we will respond to reviewer's concern about novelty and connection to conformal training ideas here, and we have three additional official comments in which we respond to reviewer's concern about the experiments and the other questions.  \n\n**Novelty and Fundamental Difference with Conformal Training Ideas:** \nWe respond to this comment from three angles. We will also add a discussion in our related work section of the paper with the relevant literature.\n\n**1. Different ideas and approach:**\nOur approach to conformal prediction is from the perspective of uncertainty quantification for a **given black-box model**, without altering the model itself. In the paper, we start by fundamentally characterizing the interplay between conditional validity and length efficiency in a minimax framework (please see Proposition 3.1). In particular, we derive **the optimal** prediction sets using a novel **level set formulation**. Obtaining the optimal sets amount to solving an **equivalent miniamx problem** where the max part guarantees length optimality and the min guarantees coverage. Having the black-box approach in mind, we then relax our minimax approach to search for prediction sets of the form $S(x,y)\\leq h(x)$ by fixing the choice of $S$ and **optimizing over the right-hand side**, i.e. the function  $h(x)$. Now, two points are in order. (i) Unlike Gibbs et al. [1], here the covariate adaptivity of the threshold $h(x)$, also roots in **learning features for length optimization**. I.e., we choose an adaptive threshold even for marginal coverage case (and **we show that an adaptive threshold is fundamentally necessary for optimizing length** even in the marginal case). (ii) Conformal training methods aim to produce tight prediction sets by going beyond the black-box approach and altering the base model, i.e. **optimizing the left hand side** of $S(x,y)\\leq h$ (while calibrating the constant $h$). This should clear the role of Figure 1 of our submission, where conformal training ideas belong to the first box on the left and CPL belongs to the right end.\n\nTherefore, we believe our approach **is not an extension of conformal training ideas** to Gibbs et al. It has new insights (level set perspective) and new techniques (minimax length optimization by threshold adaptivity). We now illustrate these points in depth with a simple example.\n\n**2. Simple Example:**\nWe start with the example on the second page of our submission. We focus exclusively on marginal coverage (in this case, Gibbs et al. [1] reduces to split conformal). Analogous to extending conformal training ideas, one might attempt to improve interval length by optimizing $\\hat{f}$ in $|y-\\hat{f}(x)|\\leq q$. However, in our framework, we keep $\\hat{f}$ fixed and instead optimize $h$ in $|y-\\hat{f}(x)|\\leq h(x)$. We encourage the reviewer to look at the details of the example and see the **necessity of the threshold adaptivity** to reduce interval length regardless of the choice of $\\hat{f}$ (even when $\\hat{f}(x) = E[Y|X=x]$). This necessity is due to the variance structure of the noise, which can't be captured by the base model alone and **requires an adaptive threshold**.\n\n**3. Additional Experiment:**\n**CPL and conformal training can also be used in conjunction** to enhance prediction set efficiency. To illustrate this, we conducted an experiment on CIFAR-10. In this experiment, we explored four different scenarios where the base model is either trained using simple Empirical Risk Minimization (ERM) with cross-entropy loss or using conformal training (confTR). The calibration phase is then performed using either the split conformal method or CPL. In this setup, we focus solely on marginal coverage, setting the nominal coverage level to 0.95. \n| **Training** | **Calibration** | **Coverage** | **Avg Length** | **Samples (Train/Calib/Test)** | **Base Accuracy** |\n|--------------|-----------------|--------------|----------------|-------------------------------|-------------------|\n| ERM          | Split Conformal | 0.951        | 2.36           | 40k/10k/10k                   | 82.6%             |\n| ERM          | CPL             | 0.948        | 2.06           | 40k/10k/10k                   | 82.6%             |\n| confTR       | Split Conformal | 0.954        | 2.11           | 45k/5k/10k                    | 82.3%             |\n| confTR       | CPL             | 0.947        | 1.94           | 35k/15k/10k                   | 81.8%             |\n\nThe results demonstrate that confTR can be further improved by using CPL as the calibration method. This supports our main message: even when the model is fixed, there is still potential to optimize length efficiency through a minimax framework that refines the threshold. \n\nFor ConfTR, as suggested by the original ConfTR paper, we first train the ResNet34 by ERM using cross entropy and then fine-tune it with confTR. For the inner maximization ($h(x)$) of CPL we fine-tuned only one additional (last) layer of the model learned in the training time. Hence, the CPL calibration step is significantly lighter in computation with respect to train step with either ERM or confTR. For confTR, we also optimized the train/calibration split to achieve maximum length reduction. However, for the ERM scenarios, we did not optimize this split, bolding our black-box perspective. We used APS scoring for calibration. The reported numbers are averaged over 20 independent random splits of the data. The standard deviation errors for all the reported coverage and length numbers are below 0.02.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for taking the time to review our submission and providing helpful feedback. We address the reviewers individually below. In addition, a pdf is attached including (i) plots for an additional experiment which we will add to the revised manuscript, and (ii) a sensitivity analysis asked by the reviewer 5vGW.

Meta-review: The present paper considers a framework for length optimization in conformal prediction. The idea is to design a predictive interval for the response variable with the prescribed coverage $1-\alpha$ and with nearly optimal length (this description is somewhat less general than the paper, where responses need not be real-valued). The idea is this: start with a nonconformity score $S(x,y)$ (as is standard) but try to choose the "quantiles" of $S(x,y)$ in an adapted fashion. This requires the introduction of an adequate framework at the population level (allowing for covariance shifts, groups and other things) that is then adapted to finite samples and well-behaved hypotheses classes. That framework is strong related to recent work by Gibbs et al. (arXiv:2305.12616), but the goals are quite different, as that paper does not address length optimization directly. 

The reviewers raised many questions during the discussion period about computational efficiency and many other details. Three of them had final scores in the "borderline accept to accept" range (5,6,7) and seemed satisfied with the discussion. The fourth reviewer (xcAK) gave a 4 score (borderline reject): they also seemed satisfied that the discussion helped clarify most points of interest, but felt that the revision required to address these points would be quite substantial. My own evaluation is somewhat at variance with xcAK's: although there are many points to be addressed, I believe that the paper will not be greatly changed. Therefore, I recommend acceptance.
Decision: Accept (poster)