Length Optimization in Conformal Prediction

Authors: shayan  kiyani
george  pappas
hamed  hassani
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:47:21

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.

Main paper: 
 introduction: 
 Consider a distribution D over the domain X × Y, where X is the covariate space and Y is the label space. Using a set of calibration samples (X 1 , Y 1 ), . . . , (X n , Y n ) drawn i.i.d. from D, the objective of conformal prediction (CP) is to create a 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-used guarantee is the marginal coverage:The prediction sets C(x) ⊆ Y achieve marginal coverage if, for a test sample (X n+1 , Y n+1 ), we have Pr(Y n+1 ∈ C(X n+1 )) = 1 -α. Here, α is the given miscoverage rate, and the probability is over the randomness in the calibration and test points.Conformal Prediction faces two major challenges in practice: conditional validity and length inefficiency. Marginal coverage is often a weak guarantee; in many practical scenarios we need coverage guarantees that hold across different sub-populations of the data. E.g., in healthcare applications, obtaining valid prediction sets for different patient demographics is crucial; we often need to construct accurate prediction sets for certain age groups or medical conditions. This is known as conditional validity -which ideally seeks a property called full conditional coverage: For every x ∈ X we requireEQUATIONAlas, achieving full conditional coverage with finite calibration data is known to be impossible [1] [2] [3] . Consequently, in recent years several algorithmic frameworks have been developed that guarantee relaxations of (1) [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] . However, the prediction sets constructed by these methods are often observed to be (unnecessarily) large in size [2, 20, 21] ; i.e., it is possible to find other conditionally-valid prediction sets with smaller length. Even in the case of marginal coverage, the prediction sets constructed by algorithms such as split-conformal can be far from optimal in size. This brings us to 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 [22] [23] [24] [25] . In fact, the performance of CP methods are closely tied to the length efficiency of the prediction sets in practical applications in decision making [26] [27] [28] [29] , robotics [20, 21] , communication systems [30, 31] , and large language models [32] [33] [34] . 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 a model using training data, designing a conformity score, and constructing the prediction sets. Our framework operates at the third stage, i.e., we 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 [22, 24, [35] [36] [37] [38] [39] [40] [41] and obtaining conditional guarantees using a given score [4-19, 42, 43] . The missing piece in 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, a 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 ∼ x + N (0, 2), and -if x ≥ 0, then Y ∼ x + N (0, 1), see Figure 2-(a) . For simplicity, we assume in this example that we have infinitely many data points available from this distribution. As the model, we considerf (x) = E[Y | X = x] = x.As a result, considering the conformity score S(x, y) = |y -f (x)|, the distribution of S follows the folded Gaussian distribution: i.e. for x < 0 we have D S|x = |N (0, 2)|, and for x ≥ 0 we have D S|x = |N (0, 1)| -see Figure 2-(b ). We aim for marginal coverage of 0.9, and consider prediction sets C(x) in the following form:-if x < 0 : C(x) = {y ∈ R s.t. S(x, y) ≤ q -}, and -if x ≥ 0 : C(x) = {y ∈ R s.t. S(x, y) ≤ q + }.For every value of q + in the range [1.4, +∞] there exists a unique q -that ensures 0.9-marginal coverage. This provides a 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 2-(c ) plots the average length versus q + . Four lessons from this example are as follows: (i) First, as we see from Figure 2-(c ), the optimal-length solution is different from the sets constructed by the Split-Conformal method (for which q -and q + 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 < l a t e x i t s h a 1 _ b a s e 6 4 = " F x 5 O P k q q W E j 7 x S F 7 n P o 0 c j u 6 z y 4 sets. Hence, the feature h(x) = sign(x) is crucial in determining the optimal-length sets. (ii) Second, for (q * -, q * + ) corresponding to the optimal-length sets, the conditional PDFs take the same value; i.e. p(S = q * + |x ≥ 0) = p(S = q * -|x ≤ 0) -see Figure 2 -(b). This is not a coincidence, and as we will show, it is the main deriving principle to find the optimal sets -see Example 3.2 below. Contributions. We develop a principled and practical framework to design length-optimized prediction 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-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.d t z Y + O n V B n O B E 4 K n U R j T N m I D r B t q a Q h a j + d H T o h J 1 b p k X 6 k b E l D Z u r v i Z S G W o / D w H a G 1 A z 1 o j c V / / P a i e l f + y m X c W J Q s v m i f i K I i c j 0 a 9 L j C p k R Y 0 s o U 9 z e S t i Q K s q M z a Z g Q / A W X 1 4 m j b O y d 1 m + q J 2 X K r d Z= " > A A A B 6 n i c b V D L S g N B E O y N r x h f U Y 9 e B o M g C G F X f B 2 D X j x G N A 9 I l j A 7 6 S R D Z m f X m V k h L P k E L x 4 U 8 e o X e f N v n C R 7 0 M S C h q K q m + 6 u I B Z c G 9 f 9 d n J L y y u r a / n 1 w s b m 1 v Z O c X e v r q N E M a y x S E S q G V C N g k u s G W 4 E N m O F N A w E N o L h z c R v P K H S P J I P Z h S j H 9 K + 5 D 3 O q L H S / W P n p F M s u W V 3 C r J I v I y U I E O 1 U / x q d y O W h C g N E 1 T r l u f G x k + p M p w J H B f a i c a Y s i H t Y 8 t S S U P U f j o 9 d U y O r N I l v U j Z k o Z M 1 d 8 T K Q 2 1 H o W B 7 Q y p G e h 5 b y L + 5 7 U S 0 7 v y U y 7 j x K B k s 0 W 9 R B A T k c n f p M s V M i N G l l C m u L 2 V s A F V l B m b T s G G 4 M 2 / v E j q p 2 X v o n x + d 1 a q X G d x 5 O E A D u E Y P L i E C t x C F WWe 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 be the optimal-length prediction sets, through a 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 a 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 finite-sample error.We extensively evaluate the performance of CPL on a variety of real world and synthetic datasets in classification, regression, and text-based settings against numerous state-of-the-art algorithms ranging from Split-Conformal [22, 44] , Jacknife [45] , Local-CP [12] , and CQR [35] , to BatchGCP [4] and Conditional-Calibration [8] . A detailed discussion of our 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. 
preliminaries on conditional validity and length of prediction sets: 
 Recall that (X, Y ) is generated from a distribution D supported on X × Y (distributions D X and D Y |X are then defined naturally). The prediction sets are of the form C(x) : X → 2 Y for x ∈ X .Conditional Coverage Validity. Ultimately, in conformal prediction, the goal is to design prediction sets that satisfy the full conditional coverage introduced in (1). Despite the importance, full conditional coverage is impossible to achieve in the finite-sample setting [1] [2] [3] . Therefore, several weaker notions of coverage such as marginal [22, 44] , group conditional [4] [5] [6] , and coverage with respect to a class of covariate shifts [8] [9] [10] have been considered in the literature. Here, we focus on the notion of conditional validity with respect to a class of covariate shifts, which unifies all these notions, and contains each of them as a special case by adjusting the class. Fix any non-negative function f and letD f denote the setting in which {(X i , Y i )} n i=1 is sampled i.i.d. from D, while (X n+1 , Y n+1 ) is sampled independently from the distribution in which D X is shifted by f , i.e., X n+1 ∼ f (x) E D [f (X)] • dD X (x), Y n+1 | X n+1 ∼ D Y |X .We define the exact coverage validity under non-negative covariate shift f as,Pr Xn+1∼D f (Y n+1 ∈ C(X n+1 )) = 1 -α,which can be equivalently written as,EQUATIONThis last equality enables us to define the notion of generalized covariate shift. For prediction sets C, we say that coverage with respect to a function f (which can take negative values) is 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 R. 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 ∈ F.It is easy to 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 (1). Accordingly, using less complex choices for F would result in relaxed notions of conditional coverage. We now review three important instances of F: 1) Marginal Coverage: Setting F = {x → c | c ∈ R}, i.e. constant(Y n+1 ∈ C(X n+1 )) = 1 -α. 2) Group-Conditional Coverage: Let G 1 , G 2 , • • • , G m ⊆ X be a collection of sub-groups in the covariate space. Define f i (x) = 1[x ∈ G i ] for every i ∈ [1, m]. By using the class of covariate shiftsF = { m i=1 β i f i (x) | β i ∈ R for every i ∈ [1, • • • , m]} m i=1 we can obtain the group-conditional coverage validity; i.e. Pr Xn+1∼D (Y n+1 ∈ C(X n+1 )|X ∈ G i ) = 1 -α, for every i ∈ [1, m].3) Finite-dimensional Affine Class of Covariate Shifts: Let Φ : X → R d be a predefined function (a.k.a. the finite-dimensional basis). The class F is defined asF = {⟨β, Φ(x)⟩|β ∈ R d }.Here, F is an affine class of covariate shifts as for any f, f ′ ∈ F and ϵ ∈ R we have f + ϵf ′ ∈ F. We use the term "bounded" class of covariate shifts when we assume, max1≤i≤d sup x∈X ϕ i (x) < ∞, where Φ(x) = [ϕ 1 (x), • • • , ϕ d (x)].The finite-dimensional affine class is fairly general and covers a broad range of scenarios in theory and practice (see Section 5.3, Remark D.1 in appendix D, as well as [8] ). As special cases, it includes both of the marginal and group-conditional settings. To see this, one can pick Φ(x) = 1 for the marginal case andΦ = [f 1 (x), f 2 (x), • • • , f m (x)]T for the group-conditional scenario. Consequently, from now on we will focus on the scenario where F is a d-dimensional affine class of covariate shifts.Length. We use the term len(C(x)) to denote the length of a prediction set at point x ∈ X . Length can have different interpretations in different contexts, yet it always depicts the same intuitive meaning of size. In the case of regression when Y = R we have, len(C(x)) = Y 1[y ∈ C(x)]dy. Here, dy can be interpreted as Lebesgue integral (i.e. the usual way to measure length on R). Similarly, in the classification setting, whenY = {y 1 , y 2 , • • • , y L }, we let len(C(x)) = L i=1 1[y ∈ C(x)].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 C(x) E X [len(C(X))] subject to E X,Y f (X) 1[Y ∈ C(X)] -(1 -α) = 0, ∀f ∈ FI.e., we want to construct predictions sets C(x), x ∈ X with optimal (i.e. minimal) average length while being conditionally valid with respect to a (finite-dimensional) class of covariate shifts F.In the special case of marginal validity the constraint becomesE [c {1[Y ∈ C(X)] -(1 -α)}] = 0 for every c ∈ R, or equivalently Pr(Y ∈ C(X)) = 1 -α.Similarly, in the special case of groupconditional the constraint boils down toPr(Y ∈ C(X)|X ∈ G i ) = 1 -α for every i ∈ [1, • • • , m]. 
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 so by deriving an equivalent minimax formulation whose solutions have a rich interpretation in terms of level sets of the data distribution. Having the practical finite-sample setting in mind, we 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.A natural way to think about the Primary Problem2.2 is to look at the dual formulation. Let us define,EQUATIONNote that the first term in g α (f, C) corresponds to coverage w.r.t. to f and the second term corresponds to length. One can easily check that g α (f, C) is equivalent 1 to the Lagrangian for the Primary Problem (given that F is an affine finite-dimensional class). The dual problem can be written as: Then, C * is also the optimal solution of the Primary Problem. Furthermore, C * has the following form:Minimax Problem: Minimize f ∈F Maximize C(x)EQUATIONExample 3.2 (Marginal case) For the marginal case, whereF = {x → c | for every c ∈ R}, we have C * (x) = {y ∈ Y | c * p(y|x) ≥ 1}.In other words, the minimal length marginally valid prediction set is of the form of a specific level set of p(y|x). 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 to the Primary Problem corresponds to specific level sets of the distributions p(y|x). Further, this optimal level set has an equivalent minimax formulation. We will see in section 4 how a relaxation of this minimax can be used to derive a finite sample algorithm. Next, we will discuss the roles of the inner maximization and the outer minimization.The Inner Maximization. For a function f : X → R we define the level sets corresponding to f asEQUATIONFrom Proposition 3.1, the optimal prediction sets have the form C f * for some f * ∈ F. The following proposition, shows that for a fixed f the outcome of the inner maximization is exactly the level set C f . Proposition 3.3 (Variational representation) For any f ∈ F, and α ∈ [0, 1] we have,EQUATIONThe Outer Minimization. So far, we know that for every f , the inner maximization chooses the level set C f 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 a f * such that C f * has correct conditional coverage w.r.t. to F.Lemma 3.4 Let f ∈ F. Recall that F is an affine class of functions. This means for every f ∈ F and ε ∈ R, f + ε f ∈ F. We have for every f ∈ F,d dε g α (f + ε f , C f +ε f ) ε=0 = E f (X) 1[Y ∈ C f (X)] -(1 -α) .At the optimum solution f * of the outer minimization, all the directional derivatives are zero (since f * is a stationary point). Hence, using the lemma, C f * 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.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 as in practice we have finite-size calibration data. Having an infinitely complex space of prediction sets simply lead to overfitting. Consequently, we need to restrict the maximization over a class of prediction sets of finite complexity. (2) In CP the prediction sets are often constructed by a carefully designed conformity score. For instance, the common practice in CP is to structure the prediction sets by threshold the conformity score. In light of these, we will need to relax the Minimax formulation.Structured Prediction Sets: 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 at the prediction sets that are described by thresholding a conformity measure. Let S(x, y) : X × Y → R be a given conformity score. Consider a function h : X → R. We will consider structured prediction sets of the formEQUATIONFor the ease of notation, we use g α (f, h) instead of g α (f, C S h ). We then relax the Minimax Problem formulation 3.1. Let H be a class of real valued functions on the set X . For now, H could be any class -e.g. it could be the class of all the real-valued functions on X (with infinite complexity) or it could be a class with bounded complexity (e.g. a neural network parameterized by its weights).Relaxed Minimax Problem:Minimize f ∈F Maximize h∈H g α (f, h).Here, the relaxation is that the inner maximization is over prediction sets of form (7) where h ∈ H.A natural question to ask now is whether this relaxation preserves valid coverage guarantees or length optimality. Clearly, the answer to this question depends on the choice of the conformity measure S and the class H. Let us start by considering the structure of the optimal prediction sets given in (4); it is easy to see that the optimal sets have the formEQUATIONfor some function f * : X → R. 2 Comparing (8) with (7) makes it clear that, unless the score S(x, y) is aligned with 1/p(y|x), the structured sets C S h 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 (x, S(x, y)) instead of (x, y)there can be a fundamental gap to the best achievable length. That is to say the level sets of S(x, y) can be fundamentally different from the level sets of p(y|x).Given the above considerations, we ask: what is the appropriate notion of length-optimality that can 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 , h ∈ H. Accordingly, we introduce the Relaxed Primary Problem which is the dual form of the Relaxed Minimax Problem:Relaxed Primary Problem:Minimize h∈H E len(C S h (X)) subject to E f (X) 1[Y ∈ C S h (X)] -(1 -α) = 0, ∀f ∈ FTo 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.1 between the Minimax Problem 3.1 and the Primary Problem 2.2.At a high level, we demonstrate that strong duality holds when H is "sufficiently complex". Specifically, we first let H be the class of all (measurable) functions from X to R, and show that the Relaxed Minimax Problem and the Relaxed Primal Problem achieve the same optimal value-i.e., strong duality. Hence, if the Relaxed Primal Problem admits an optimal solution h * then the Relaxed Minimax Problem has an optimal solution of the form (f * , h * ). Next, we consider a bounded-complexity class H. We show that under a realizability assumption, i.e., h * ∈ 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 L * . One can interpret L * 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 * = -OPT, as our definition of g α (f, 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 to develop our theory.Assumption 1 Recall that the class F is defined asF = {⟨β, Φ(x)⟩|β ∈ R d }, where Φ : X → R d is a predefined function (a.k.a. the finite-dimensional basis). Let Φ(x) = [ϕ 1 (x), • • • , ϕ d (x)].We assume each ϕ i (x) takes countably many values. Assumption 1 is mainly a technical assumption that helps to obtain a more simplified result. Assumption 1 holds in both marginal and group-conditional settings (as in these cases ϕ i 's take their value in {0, 1}). We will provide a more general but weaker result without assumption 1 in Appendix F. Theorem 3.5 Let us assume D S|X and D X are continuous. Let F be a bounded finite-dimensional affine class of covariate shifts and H be the class of all (measurable) functions from X to R. Under assumption 1, the strong duality holds between the Relaxed Primary Problem and the Relaxed Minimax Problem. In other words, Minimizef ∈F Maximize h∈H g α (f, h) = Maximize h∈H Minimize f ∈F g α (f, h),and the optimal values of the two problems coincide (L * = -OPT).If the Relaxed Primary Problem (i.e., the right hand side of the above equation) attains it's optimal value at h * ∈ H, then there exists f * ∈ F such that (f * , h * ) 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 ε > 0, there exists h * ∈ H such that,(i) |g α (f * , h * ) -OPT| ≤ ε.(ii) h * is conditionally valid; i.e., for every f ∈ F we have,E f (X) 1[Y ∈ C S h * (X)] -(1 -α) = 0. (iii) E X len(C S h * (X)) ≤ L * + ε.Put it simply, Theorem 3.5 says for any ε > 0, there is an ε-close optimal solution of the Relaxed Minimax Problem (statement (i)) such that it is a feasible solution of the Relaxed Primary Problem with exact conditional coverage (statement (ii)), and it achieves only an ε-larger prediction set length than the smallest possible, which is the solution of Relaxed Minimax Problem (statement (iii)).The following realizability condition paves the way to generalize the strong duality results to the case where H is a 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 * ∈ H such that h * is an optimal solution of the Relaxed Primary Problem and the Relaxed Minimax Problem. Proposition 3.7 Let H = {h θ | θ ∈ Θ}, be a realizable class of functions where Θ is a compact set. Then the Relaxed Minimax Problem and the Relaxed Primary Problem are equivalent. In other words, strong duality holds and the min and max are interchangeable in the Relaxed Minimax Problem. 
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 {(x i , y i )} n i=1 from the distribution D. Let S(x, y) : X × Y → R 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 finitedimensional affine class of functions F that represents the level of conditional validity to be achieved.Unbiased Estimation. From (3), the objective g α (f, h) of the Relaxed Minimax Problem 3.2 admits a straightforward unbiased estimator using n i.i.d. samples {(x i , y i )} n i=1 :g α,n (f, h) = 1 n n i=1 f (x i ) 1[S(x i , y i ) ≤ h(x i )] -(1 -α) - 1 n n i=1 Y 1[S(x i , y) ≤ h(x i )]dy.Smoothing. The objective g α,n (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 function1[a < b] is via Gaussian smoothing. Consider the Gaussian error function, erf(x) = 2 √ πx 0 e -t 2 dt, and define the smoothed indicator function as:1(a, b) = 1 2 1 + erf a-b √ 2σ, where σ controls the 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 of our objective isgα,n (f, h) = 1 n n i=1 f (x i ) 1(S(x i , y i ), h(x i )) -(1 -α) - 1 n n i=1 Y 1(S(x i , y), h(x i ))dy.Given this smoothed objective, our main algorithm is presented in Algorithm 1.Algorithm 1 Conformal Prediction with Length-Optimization (CPL) Perform a few iterations (e.g. SGD steps) on h to maximize gα,n (f, h)5:Perform a few iterations (e.g. SGD steps) on f to minimize gα,n (f, h) 6: end while7: f * CPL ← f, h * CPL ← h 8: Let C * CPL (x) = {y ∈ Y | S(x, y) ≤ h * CPL (x)}.Remark 4.1 Oftentimes in practice, the machine learning models, such as Neural Networks, are parametric (h θ , where θ is the set of parameters). In that case, performing the iteration on h can be implemented by updating θ. Remark 4.2 Recalling the definition ofF = {⟨β, Φ(x)⟩|β ∈ R d }, each f ∈ F can be represented by f (x) = ⟨β, Φ(x)⟩ ≡ f β (x).Hence, performing the iteration on f can be implements by updating β ∈ R d .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 N ). 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) are the stationary points of 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 q ≤ q ′ ,Pr X∼P (X ≤ q ′ ) -Pr X∼P (X ≤ q) ≤ L (q ′ -q) . Assumption 2 The conditional distribution D S|X is L-Lipschitz, almost surely with respect to D X .Assumption 2 is often needed for concentration guarantees in CP literature [4, 11, 48, 49] . Consider CPL with smoothed function gα,n with smoothing parameter σ = 1 √ n . Let (f * CPL , h * CPL ) denote a stationary point reached by Algorithm 1. Also, the corresponding prediction sets are given asC * CPL (x) = {y ∈ Y | S(x, y) ≤ h * CPL (x)}. Theorem 4.4 (Conditional coverage validity) Under assumption 2, let (f * CPL , h * CPL )denote a stationary point reached by Algorithm 1 (if exists) and C * CPL (x) its corresponding prediction sets. Then with probability 1 -δ we have,E f β (X) 1[Y ∈ C * CPL (X)] -(1 -α) ≤ c 1 ln 2dN (H,d∞, 1 n ) δ + c 2 √ n , ∀f β ∈ F,wherec 1 = √ 2B||β|| 1 , c 2 = ||β|| 1 BL π 2 + ||β|| 1 2B √ 2π , B = max i sup x∈X Φ i (x), and Φ is the basis for F (see Section 2.1). PAC-style guarantees of the order O( 1 √ n ) are generally optimal and common in CP literature [1, 4, 50] . Look at Appendix C for further discussions and interpretations. 
experiments: 
 In this section, we empirically examine the length performance of CPL compared to state-of-theart (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, we 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 a Python notebook with a step-by-step efficient implementation of our algorithm, which can be accessed at the following link: https://github.com/shayankiyani98/CP.We use multiple-choice question answering datasets, including TruthfulQA [51] , MMLU [52] , OpenBookQA [53] , PIQA [54] , and BigBench [55] . The task is to quantify the uncertainty of Llama 2 [56] 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 a simple and fixed prompt engineering approach throughout the experiment: This is a 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 applying a softmax function, we obtain a probability vector. The conformity score is defined as (1probability of the correct option), which is similar to (1 -f (x) y ) for classification.Our method is implemented using H as a linear head on top of a pre-trained GPT-2 [57] . GPT-2 has 768-dimensional hidden layers, so the optimization for the inner maximization involves a 768dimensional linear map from GPT-2's last hidden layer representations to a 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. We use a synthetic regression task as in [4] to compare CPL with BatchGCP [4] . The covariateX = (X 1 , • • • , X 100 ) is a vector in R 100 .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 as y = ⟨θ, X⟩ + ϵ X where ϵ X is a zero-mean Gaussian with variance σ 2 X = 1 +10 i=1 iX i + (40 • 1 100 i=11 X i ≥ 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 i in 1 to 10, Group 2i -1 corresponds to X i = 0 and Group 2i to X i = 1. BatchGCP and CPL are implemented to provide group-conditional coverage for these groups. We use a 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. We conduct experiments on the RxRx1 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 ℓ 2 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 a pre-trained ResNet50 model (trained by [58] ), f (x), 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 a linear classifier on the final-layer representations of the pre-trained ResNet50. We then compute conformity scores as follows: for each image x, let f i (x) 1339 i=1 represent the output of the ResNet50 for each treatment class. We apply temperature scaling and a softmax function to convert these outputs into probability estimates, π i (x) := exp(T f i (x))/( j exp(T f j (x))), where T is the temperature parameter. The conformity score S(x, y) is calculated as the sum of π i (x) over treatments for which π i (x) > π y .Figure 5 • Section B provides more discussions on the existing related works.• Appendix C is dedicated on some interpretations of the finite sample guarantees of Section 4.• Appendix D lists the all the Remarks that we moved to Appendix from the main body due to space limit.• Appendix E provides the Lemmas, including their proofs, that are necessary for the development of out theoretical framework.• Section F provides the proofs of all the statements proposed in Section 3 along with an extra Theorem.• Section G provides the proofs of all the statements proposed in Section 4.• Section H provides an extensive experimental setting to showcase the ability of CPL to improve length efficiency in real-world regression scenarios.• Section I provides an extra experiment setup that showcases the possibility of applying CPL on top of a CIFAR-10 classifier that is trained by conformal training.• Section J provides references to all the 11 regression datasets used in experiment setup of Section H.We now review some of the remaining prior works that are relevant.There is a growing body of work on designing better conformity scores to improve conditional validity and/or length efficiency [22, [35] [36] [37] [38] [39] [40] [41] 59 ] (see [60] for more references). As shown in Fig. 1 , 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, a 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 [46, [61] [62] [63] , 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, to 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 to directly estimate any marginal\conditional density function. Level sets and their approximations appear naturally in our optimization framework.Conformal training: Several works have focused on directly optimizing the score function to enhance the length efficiency of conformal prediction pipelines [24, 34, 65] . 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, a 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 S θ (x, y) : X × Y → R be a parameterized conformity score (e.g., where θ represents the parameters of a neural network). Conformal training optimizes θ to improve the length efficiency of prediction sets of the form S θ (x, y) ≤ q, where q is 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 S θ (x, y) ≤ h(x). That is to say, our method can also be applied on top of a score trained by conformal training. In appendix I, 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-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 a model'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 a more general case, allowing the score function to be optimized while targeting conditional coverage in the calibration procedure. They develop a 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 on optimizing the score function, we emphasize optimizing the threshold leaving the scores untouched. This leads to two distinct theoretical and algorithmic developments.Theorem C.1 (Conditional coverage validity) Under assumption 2, let (f * CPL , h * CPL ) denote a stationary point reached by Algorithm 1 (if exists) and C * CPL (x) its corresponding prediction sets. Then with probability 1 -δ we have,E f β (X) 1[Y ∈ C * CPL (X)] -(1 -α) ≤ c 1 ln 2dN (H,d∞, 1 n ) δ + c 2 √ n , ∀f β ∈ F,wherec 1 = √ 2B||β|| 1 , c 2 = ||β|| 1 BL π 2 + ||β|| 1 2B √ 2π , B = max i sup x∈X Φ i (x), and Φ is the basis for F (see Sec. 2.1).We now provide three Corollaries to this Theorem.The case of marginal validity: For this case we have to pick F = {x → c | c ∈ R}, i.e. constant functions. In this case one can see B = 1, so we have the following result. Pr(Y ∈ C * CPL (X)) -(1 -α) ≤ c 1 ln 2N (H,d∞, 1 n ) δ + c 2 √ n ,wherec 1 = √ 2, c 2 = L π 2 + 2 √ 2π .The case of group-conditional validity: Let G 1 , • • • , G m be a collection of groups: each group is a subset of covariate space, i.e. G i ∈ X . These groups can be fully arbitrary and highly overlapping.Define f i (x) = 1[x ∈ G i ] for every i ∈ [1, m].We can then run CPL using the class of covariate shiftsF = { m i=1 β i f i (x) | β i ∈ R for every i ∈ [1, • • • , m]} m i=1and obtain tight prediction sets with group-conditional coverage validity. In this case one can see B = 1, so we have the following result.Corollary C.3 (Finite sample group-conditional validity) Under assumption 2, let (f * CPL , h * CPL ) denote a stationary point reached by Algorithm 1 (if exists) and C * CPL (x) its corresponding prediction sets. Then with probability 1 -δ we have,Pr(Y ∈ C * CPL (X) | X ∈ G i ) -(1 -α) ≤ c 1 ln 2mN (H,d∞, 1 n ) δ + c 2 √ n , ∀i ∈ [1, • • • , m],wherec 1 = √ 2, c 2 = L π 2 + 2 √ 2π .Remark D.1 Another important special case of conditional validity with respect to an affine finite dimensional class of covariate shifts is the framework introduced by [9] which provides CP methods that guarantee a valid coverage when there is a 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 = {x → cf (x) | for every c ∈ R}, where f 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 ∈ H and x ∈ X we have h(x) ∈ [0, Γ]. Two points are in order. (i) This assumption is purely for the sake of theory development. In practice, one can run our algorithm with any off-the-shelf machine learning class of models. In fact, in Section 5, 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 to satisfy this assumption. Similar assumptions has been posed in the literature [4, 11, 48, 49] .E Technical Lemmas Lemma E.1 Let f (a, x) = 1 2 1 + erf a-x √ 2σbe the smoothed indicator function, where erf(x) is the error function, defined as erf(x) = 2 √ πx 0 e -t 2 dt, and σ is the variance of the Gaussian kernel used for smoothing. Then f (a, x) is Lipschitz continuous with respect to x with a Lipschitz constant1 √ 2πσ .Proof: To prove that f (a, x) is Lipschitz continuous with respect to x, we compute the derivative of f (a, x) with respect to x:f (a, x) = 1 2 1 + erf a -x √ 2σ ∂ ∂x f (a, x) = 1 2 ∂ ∂x 1 + erf a -x √ 2σ = 1 2 • 2 √ π • -1 √ 2σ e -a-x √ 2σ 2Simplifying this, we get:∂ ∂x f (a, x) = - 1 √ 2πσ e -(a-x) 2 2σ 2To show that this derivative is bounded, observe that:∂ ∂x f (a, x) = - 1 √ 2πσ e -(a-x) 2 2σ 2 ≤ 1 √ 2πσ Since 1 √ 2πσ is a constant, we conclude that f (a, x) is Lipschitz continuous with respect to x with Lipschitz constant 1 √ 2πσ . Lemma E.2 Let 1[a < b] be the smoothed indicator function defined by 1[a < b] = 1 2 1 + erf a -b √ 2σwhere erf(x) is the error function, defined as erf(x) = 2 √ πx 0 e -t 2 dt, and σ is the variance of the Gaussian kernel used for smoothing. The indicator function 1[a < b] is also defined as1[a < b] = 1 if a < b 0 otherwiseThe error between the smoothed indicator function 1[a < b] and the actual indicator function 1[a < b], integrated over all a, is given byE = ∞ -∞ 1[a < b] -1[a < b] daThis integral evaluates toE = π 2 σProof: To compute the integral, we consider the two cases separately: a < b and a ≥ b.For a < b, the indicator function 1[a < b] = 1, so the absolute difference isEQUATIONFor a ≥ b, the indicator function 1[a < b] = 0, so the absolute difference is| 1[a < b] -0| = 1 2 1 + erf a -b √ 2σCombining these, the integral can be written asE = b -∞ 1 2 erf a -b √ 2σ -1 da + ∞ b 1 2 1 + erf a -b √ 2σ da We know that erf(x) = 2Φ(x √ 2) -1where Φ(x) is the CDF of the standard normal distribution.Using symmetry properties of the error function and Gaussian integrals, we can simplify the calculations as follows:b-∞ erf a -b √ 2σ -1 da = - π 2 σ ∞ b 1 + erf a -b √ 2σ da = π 2 σThus, the total error integral is:E = 1 2 π 2 σ + π 2 σ = 1 2 2 π 2 σ = π 2 σLemma E.3 Let f ∈ F be a fixed function such that sup x∈X f (x) ≤ B and let us define,Z h = 1 n n i=1 f (x i ) 1(S(x i , y i ), h(x i )) -(1 -α) -E f (x) 1(S(x, y), h(x)) -(1 -α)The following uniform convergence holds: Fixing any ε > 0, we have with probability 1 -δ,|Z h | ≤ 2Bε √ 2πσ + √ 2B ln 2N (H,d∞,ε) δ √ n for every h ∈ H.Proof. Let h 1 , h 2 ∈ H be two arbitrary functions. We have,|Z h1 -Z h2 | (a) ≤ 1 n n i=1 f (x i ) 1(S(x i , y i ), h 1 (x i )) -1(S(x i , y i ), h 2 (x i )) -E f (x) 1(S(x, y), h 1 (x)) -1(S(x, y), h 2 (x)) (b) ≤ 1 n n i=1 f (x i ) 1(S(x i , y i ), h 1 (x i )) -1(S(x i , y i ), h 2 (x i )) + E f (x) 1(S(x, y), h 1 (x)) -1(S(x, y), h 2 (x)) (c) ≤ B 1 n n i=1 1(S(x i , y i ), h 1 (x i )) -1(S(x i , y i ), h 2 (x i )) + B E 1(S(x, y), h 1 (x)) -1(S(x, y), h 2 (x)) (d) ≤ B √ 2πσ 1 n n i=1 |h 1 (x i ) -h 2 (x i )| + B √ 2πσ E [|h 1 (x) -h 2 (x)|] (e) ≤ 2B √ 2πσ sup x∈X |h 1 (x) -h 2 (x)|where (a) is a triangle inequality, (b) is another triangle inequality, (c) comes from the definition of B, (d) follows from the Lipschitness Lemma E.1, and finally (e) is from the definition of sup.∞ (h 1 , h 2 ) = sup x∈X |h 1 (x)-h 2 (x)|. Therefore, |Z h1 -Zh 2 | ≤ 2Bd ∞ (h 1 , h 2 ). By Hoeffding's inequality for general bounded random variables (look at chapter 2 of [66] ), fixing h ∈ H, we have with probability 1 -δ,EQUATIONNow as a result of Lemma 5.7 of [67] (a standard covering number argument) we conclude,|Z h | ≤ 2Bε √ 2πσ + √ 2B ln 2N (H,d∞,ε) δ √ n for every h ∈ H.Lemma E. 4 The following equivalence between the three problems hold,Structured Minimax Problem ≡ Convex Structured Minimax Problem ≡ -Convex Structured Primary Problemwhere 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 1 Convex Structured Minimax Problem is equivalent to the Structured Minimax Problem.Proof. Let us remind the objective,g α (f, C) = E f (X) C(X, Y ) -(1 -α) -E Y C(X, y)dy, which is linear in terms of C. Now fixing f ∈ F, since C H ∞ ∈ C con H ∞ we have, Maximize C∈C con H ∞ g α (f, C) ≥ Maximize C∈C H ∞ g α (f, C).We now proceed by showing the other direction. Let {C i } ∞ i=1 , whereC i ∈ C con H ∞ and lim i→∞ g α (f, C i ) = Maximize C∈C con H ∞ g α (f, C) (pay attention that it is not trivial that this maximum is achievable by a single member of its domain). Now by the definition of C con H ∞ , we know each C i is a convex combination of finitely many members of C H ∞ . That is to say, for each C i , there exists{C ij } T j=1 where C ij ∈ C H ∞ and, C i = T j=1 a j C ij (x, y), T j=1 a j = 1, a j ≥ 0(∀1 ≤ i ≤ T ).Hence,g α (f, C i ) = g α (f, T j=1 a j C ij (x, y)) = T j=1 a j g α (f, C ij ) ≤ T max j=1 g α (f, C ij )Let us assume that final maximum is achieved by the index j i . Therefore, for eachC i ∈ C con H ∞ there exists a C iji ∈ C H ∞ such that g α (f, C i ) ≤ g α (f, C iji ). Hence we have, Maximize C∈C con H ∞ g α (f, C) = lim i→∞ g α (f, C i ) ≤ lim i→∞ g α (f, C iji ) ≤ Maximize C∈C H ∞ g α (f, C)Putting everything together, for every f ∈ F we have, Maximize Convex Structured Primary Problem: C∈C con H ∞ g α (f, C) = Maximize C∈C H ∞ g α (f, C),Minimize C∈C con H ∞ E [len(C(X))] subject to E f (X) C(X, Y ) -(1 -α) = 0, ∀f ∈ F As theThe negative sign appeared as our definition of g α (f, h) has a minus sign with respect to the conventional definition of Lagrangian. □ Lemma E.5 Given a random variable Z taking values in [0, 1] and E[Z] ≥ γ > 0, we have,Pr(Z ≥ γ 3 ) ≥ 2γ 3 .Proof. Let us define θ = Pr(Z ≥ γ 3 ). Now we have,γ ≤ E[Z] ≤ θ × 1 + (1 -θ) × γ 3 .Hence,θ(1 - γ 3) ≥ 2 γ 3 .Therefore,EQUATION□EQUATIONProof. Let us define for every 1 ≤ i ≤ N ,EQUATIONand assume that y i s are independently generated. By Hoeffding inequality we have,Pr( N i=1 y i - N i=1 E[y i ] ≥ ε) ≤ 2 exp -2ε 2 N i=1 z 2 i .This results in,Pr( N i=1 y i -γγ -1 2 δ 1 4 ≥ ε) ≤ 2 exp -2ε 2 δγ . Now setting ε = 1 2 γ 1 2 δ 1 4, we get,Pr( N i=1 y i -γ 1 2 δ 1 4 ≥ 1 2 γ 1 2 δ 1 4 ) ≤ 2 exp -1 2δ 1 2 < 1.This means there exists a deterministic realization that satisfies 11. □Here we provide a version of Theorem 3.5, which does not need the assumption 1 . Before that, let us remind that each element f ∈ F can be represented by a β ∈ R d , where we use the notation f β (x) = ⟨β, Φ(x)⟩ (look at section 2.1 for more details).Theorem F.1 Let us assume D S|X and D X are continuous. Let F be a bounded finite-dimensional affine class of covariate shifts and H be the class of all measurable functions. Let f * denote the optimal solution to the outer minimization and OPT denotes the optimal value of the Relaxed Minimax Problem 3.2. Finally, let L * denotes the optimal value for the Relaxed Primary Problem 3.3. For every ε > 0, there exists h * ∈ H such that,(i) |g α (f * , h * ) -OPT| ≤ ε.(ii) For every f β ∈ F we have,E f β (X n+1 ) 1[Y n+1 ∈ C S h * (X n+1 )] -(1 -α) ≤ ε||β|| 1 . (iii) E len(C S h * (X)) ≤ L * + ε.Put it simply, Theorem F.1 says fixing any ε > 0, there is an ε-close optimal solution of the Relaxed Minimax Problem (statement (i)) such that it is ε-close to the feasible solutions of the Relaxed Primary Problem which have perfect conditional coverage (statement (ii)), and it achieves an at most ε-larger prediction set length compare to the smallest possible, which is the solution of Relaxed Minimax Problem (statement (iii)).Proof of Theorem F.1:Let us define H ∞ as the class of all measurable functions from X to R. Now let us restate the Structured Minimax Problem for H ∞ .Structured Minimax Problem:Minimize f ∈F Maximize h∈H ∞ g α (f, h).We can now rewrite this problem in the equivalent form of the following, where we change the domain of the maximization from H ∞ to corresponding set functions. Let C H ∞ be the set of all function from C(x, y) :X × Y → R such that there exists h ∈ H ∞ such that C(x, y) = 1[S(x, y) ≤ h(x)].Structured Minimax Problem:Minimize f ∈F Maximize C∈C H ∞ g α (f, C).We now proceed by defining a convexified version of this problem. Let us defineC con H ∞ = { T i=1 a i C i (x, y) | T i=1 a i = 1, a i ≥ 0(∀1 ≤ i ≤ T ), C i ∈ C H ∞ (∀1 ≤ i ≤ T ), T ∈ N }.Convex Structured Minimax Problem:Minimize f ∈F Maximize C∈C con H ∞ g α (f, C).Now applying lemma E.4 we have,Structured Minimax Problem ≡ Convex Structured Minimax Problem ≡ -Convex Structured Primary ProblemThe negative sign appears because our definition of g α (f, h) has a minus sign with respect to the conventional definition of Lagrangian. Let us call the optimal value for all these three problems OPT (here pay attention that based off of our definition OPT is always a negative number, hence when we are addressing the optimal length the term -OPT shows up). With some abuse of notation, Let us assume {C i } ∞ i=1 , where C i ∈ C con H ∞ is a feasible sequence of Convex Structured Primary Problem which achieves the optimal value in the limit, i.e, lim i→∞ g α (f, C i ) = -OPT. This means, for any ε ≥ 0, there is an index i ε such that | E len(C iε ) + OPT| ≤ ε. Let us fix the value of ε for now, we will determine its value later. By definition, there should be { Ci } t i=1 and corresponding This means, for any ε ≥ 0, there exists a real valued number γ 1 such that we can define the set Γ γ1 ⊂ X so that (i) for every 1 ≤ i ≤ t and for every x ∈ Γ γ1 , len( Ci (x)) ≤ γ 1 , and (ii){h i } t i=1 such that Ci ∈ C H ∞ , h i ∈ H ∞ , Ci = 1[S(x, y) ≤ h i (x)],E[len( Ciε )1[x / ∈ Γ γ1 ]] ≤ ε.Now remind that X = R p . Since we know D X is continuous then by Dominated Convergence Theorem there exists large enough real value γ 2 such that Pr(X / ∈ B(0, γ 2 )) ≤ ε where B(0, γ 2 ) is the ball with radius γ 2 and ε is a positive real number that we will determine later.Lik = L i 1[||X|| 2 ≥ k]. By Dominated Convergence Theorem there is a γ 3 such that for every 1 ≤ i ≤ t we have E[L i 1[||X|| 2 ≥ γ 3 ]] ≤ ε. Let R = max{γ 1 , γ 2 , γ 3 , 1} and A = B(0, R) ∩ L R .Now the rest of the proof proceed as follows. We will construct h * ∈ H ∞ , and as a result the corresponding set C * (x, y) = 1[S(x, y) ≤ h * (x)], in a way that coverage properties and the length of C * is close to the ones for C iε . Let us proceed with the construction of h * . case 1: x / ∈ A. For this case we define h * (x) = 0.case 2: x ∈ A. This case is more involved. Let us fix ε 1 ≥ 0. Let {B(b i , ε 1 )} N i=1 be a minimal ε 1 covering for A. We can then further prune this covering balls to {W i } N i=1 , where (i) W i ∩ W j = ∅ for every i ̸ = j, (ii) N i=1 W i = A, and (iii) W i ⊆ B(b i , ε 1 ) for every i. Now we use the following randomized method to prove a desirable construction for h * exists. Let {Z i } ∞ i=1 be a collection of uniform iid discrete random variables where they take values between 1 and t. Then we define the random function h rand (x) inside A in the following way. By construction, for each x ∈ A there is a unique W i that includes x. We set h rand (x) = h Zi (x). We denote the corresponding set function to h rand by C rand . Now Let us remind that F is a finite dimensional affine class of functions. In particular, let Φ(x) = [ϕ 1 (x), • • • , ϕ d (x)]E X,Y,h rand N i=1 ϕ k (X)(C rand (X, Y ) -(1 -α))1[X ∈ W i ] = E X,Y,h rand ϕ k (X)(C rand (X, Y ) -(1 -α))1[X ∈ A] = t i=1 a i E X,Y ϕ k (X)( Ci (x, y) -(1 -α))1[X ∈ A] = E X,Y ϕ k (X)(C iε (X, Y ) -(1 -α))1[X ∈ A] = 0 -E X,Y ϕ k (X)(C iε (X, Y ) -(1 -α))1[X / ∈ A] ≤ E X,Y ϕ k (X) (C iε (X, Y ) -(1 -α)) 1[X / ∈ A] ≤ B E 1[X / ∈ A] ≤ B(E B(0, R) + E L R ) ≤ 2Bε,where B is the upper bound for ϕ k . We now define the random variableE i = E X,Y [ϕ k (X)(C rand (X, Y ) -(1 -α))1[X ∈ W i ]]for every 1 ≤ i ≤ N . The computation above indicates a bound on the expectation of the sum of these variables. By the construction of C rand we know that they are independent. Furthermore, each random variable E i is bounded by the quantity 2BM vol(B(0, ε 1 )), where B is the upper bound for ϕ k , M = max x∈B(0,R) p(x) (which is finite as B(0, R) is a compact set and we assumed D X is continuous), and B(0, ε 1 ) appears as a result of W i ⊆ B(b i , ε 1 ). Hence, we can apply Hoeffding inequality for general bounded random variables and derive for every ε ≥ 0, Pr(N i=1 E i -E[ N i=1 E i ] < ε) ≥ 1 -2 exp -2ε 2 4N B 2 M 2 vol(B(0, ε 1 )) 2 .This results in,Pr( E X,Y ϕ k (X)(C rand (X, Y )-(1 -α))1[X ∈ A] < ε + 2Bε) ≥ 1 -2 exp -2ε 2 4N B 2 M 2 vol(B(0, ε 1 )) 2 . Furthermore, E X,Y ϕ k (X)(C rand (X, Y )-(1 -α))1[X / ∈ A] = E X,Y ϕ k (X) (C rand (X, Y ) -(1 -α)) 1[X / ∈ A] ≤ B E 1[X / ∈ A] ≤ B(E B(0, R) + E L R ) ≤ 2Bε. Therefore, Pr( E X,Y ϕ k (X)(C rand (X, Y )-(1 -α)) < ε + 4Bε) ≥ 1 -2 exp -2ε 2 4N B 2 M 2 vol(B(0, ε 1 )) 2 .Now since we have this argument for each 1 ≤ k ≤ d, by a union bound we have,Pr(∀k : 1 ≤ k ≤ d : E X,Y ϕ k (X)(C rand (X, Y )-(1 -α)) < ε + 4Bε) (13) ≥ 1 -2d exp -2ε 2 4N B 2 M 2 vol(B(0, ε 1 )) 2 .Now one can argue a similar inequality should hold for length too. This time we can defineQ i = E X Y C rand (X, y)dy1[X ∈ W i ]. Now these variables are also independent and as a result of the construction of the covering set they are bounded by RM vol(B(0, ε 1 ). We also have,E X,h rand N i=1 Q i 1[X ∈ W i ] + OPT = E X,h rand Y C rand (X, y)dy1[X ∈ A] + OPT = t i=1 a i E X Y C i (X, y)dy1[X ∈ A] + OPT = E X Y C iε (X, y)dy1[X ∈ A] -OPT = E X Y C iε (X, y)dy + OPT -E X Y C iε (X, y)dy1[X / ∈ A] ≤ ε + E X Y C iε (X, y)dy1[X / ∈ A] ≤ ε + E X Y C iε (X, y)dy1[X / ∈ B(0, R)] + E X Y C iε (X, y)dy1[X / ∈ L R )] ≤ 3ε.Now again by applying Hoeffding inequality for general bounded random variables we have for every ε ≥ 0, Pr(N i=1 Q i -E[ N i=1 Q i ] < ε) ≥ 1 -2 exp -2ε 2 N R 2 M 2 vol(B(0, ε 1 )) 2 .This results in,Pr( E X Y C rand (X, y)dy1[X ∈ A] + OPT < 4ε) ≥ 1 -2 exp -2ε 2 N R 2 M 2 vol(B(0, ε 1 )) 2 .C rand , E X Y C rand (X, y)dy1[X / ∈ A] = 0.Therefore,EQUATION)Now a union bound between ( 13) and ( 14) leads to,Pr ∀k : 1 ≤ k ≤ d : E X,Y ϕ k (X)(C rand (X, Y ) -(1 -α)) < ε + 4Bε and E X Y C rand (X, y)dy + OPT < 4ε ≥ 1 -2d exp -2ε 2 4N B 2 M 2 vol(B(0, ε 1 )) 2 -2 exp -2ε 2 N R 2 M 2 vol(B(0, ε 1 )) 2 .Recalling, N = N (A, ||.|| 2 , ε 1 ), where N denotes the covering number, we have the following inequality (look at chapter 4 of [66] ),N ≤ ( 3 ε 1 ) p vol(A) vol(B(0, 1)) , vol(B(0, ε 1 )) = ε p 1 vol(B(0, 1)).This results in,EQUATION.Since we have this inequality for every ε 1 > 0, we can pick a small enough ε 1 such that,Pr ∀k : 1 ≤ k ≤ d : E X,Y ϕ k (X)(C rand (X, Y ) -(1 -α)) < ε + 4Bε and E X Y C rand (X, y)dy + OPT < 4ε ≥ 1 2 .This means there is a realization of h rand and accordingly C rand , which we denote them by h * and C * such that,∀k : 1 ≤ k ≤ d : E X,Y ϕ k (X)(C * (X, Y ) -(1 -α)) < ε + 4Bε and E X Y C * (X, y)dy + OPT < 4ε.Now since we proved this for any ε > 0, we can put ε = ε ′ min{ 1 4 , 1 1+4B }. Therefore the following statement holds. For every ε ′ > 0 there exists h * ∈ H ∞ and its corresponding set functionC * (x, y) = 1[S(x, y) ≤ h * (x)] such that, ∀k : 1 ≤ k ≤ d : E X,Y ϕ k (X)(C * (X, Y ) -(1 -α)) < ε ′ and E X Y C * (X, y)dy + OPT < ε ′ .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 ≤ L * . Finally, let f * denotes an optimal solution to the outer minimization of the Relaxed Minimax Problem. There exists a β * such that f * (x) = ⟨β * , Φ(x)⟩. Now we have,g α (f * , h * ) -OPT = E ⟨β * , Φ(X)⟩ C * (X, Y ) -(1 -α) -E Y C * (X, y)dy ≤ E ⟨β * , Φ(X)⟩ C * (X, Y ) -(1 -α) + E Y C * (X, y)dy + OPT ≤ ε ′ ||β * || 1 + ε ′ . Hence ε ′ ≤ ε 1+||β * ||1prove the statement (i) of the Theorem 3.5. Proof of Theorem 3.5: Let us define H ∞ as the class of all measurable functions from X to R. Now let us restate the Structured Minimax Problem for H ∞ .Minimize f ∈F Maximize h∈H ∞ g α (f, h).We can now rewrite this problem in the equivalent form of the following, where we change the domain of the maximization from H ∞ to corresponding set functions. Let C H ∞ be the set of all function from C(x, y) :X × Y → R such that there exists h ∈ H ∞ such that C(x, y) = 1[S(x, y) ≤ h(x)]. Structured Minimax Problem: Minimize f ∈F Maximize C∈C H ∞ g α (f, C).We now proceed by defining a convexified version of this problem. Let us defineC con H ∞ = { T i=1 a i C i (x, y) | T i=1 a i = 1, a i ≥ 0(∀1 ≤ i ≤ T ), C i ∈ C H ∞ (∀1 ≤ i ≤ T ), T ∈ N }.Now we can define the following problem.Minimize f ∈F Maximize C∈C con H ∞ g α (f, C).Naturally we can also define the Convex Structured Primary Problem.Minimize C∈C con H ∞ E [len(C(X))] subject to E f (X) C(X, Y ) -(1 -α) = 0, ∀f ∈ FNow applying lemma E.4 we have,Structured Minimax Problem ≡ Convex Structured Minimax Problem ≡ -Convex Structured Primary ProblemLet us call the optimal value for all these three problems OPT (here pay attention that based off of our definition OPT is always a negative number, hence when we are addressing the optimal length the term -OPT shows up). With some abuse of notation, Let us assume {C i } ∞ i=1 , whereC i ∈ C conH ∞ is a feasible sequence of Convex Structured Primary Problem which achieves the optimal value in the limit, i.e, lim i→∞ g α (f, C i ) = -OPT. This means, for any ε ≥ 0, there is an index i ε such that | E len(C iε ) + OPT| ≤ ε. Let us fix the value of ε for now, we will determine its value later. By definition, there should be { Ci } t i=1 and corresponding{h i } t i=1 such that Ci ∈ C H ∞ , h i ∈ H ∞ , Ci = 1[S(x, y) ≤ h i (x)], and we have C iε = t i=1 a i Ci (x, y) and t i=1 a i = 1, a i ≥ 0 (∀1 ≤ i ≤ t).Let us recall that the class F is defined asF = {⟨β, Φ(x)⟩|β ∈ R d }, where Φ : X → R d is a predefined function (a.k.a. the finite-dimensional basis). Now let {Φ i } ∞i=1 be all the possible countable values that it takes. In other words, each Φ i is a vector in R d and there exists x ∈ X such that Φ(x) = Φ i . Then we have,EQUATION)Here we implicitly assumed that Φ(x) is properly normalized so that the Right hand side don't need any extra normalization. Let us define,cov i (x) = Y 1[S(x, y) ≤ h i (x)]p(y|x)dy, l i (x) = Y 1[S(x, y) h i (x)]dy.from (15) we have,X t i=1 a i Φ(x)cov i (x)p(x)dx = (1 -α)     1 1 . . . 1     .We can then write,EQUATIONwhere X j = {x ∈ X | Φ(x) = Φ j }. Now two points are in order. (i) Without loss of generality, one can assume p(X j ) > 0 for every j as otherwise we can just omit that Φ j since it does not contribute to any integral due to continuity assumptions. (ii) {X j } ∞ j=1 partitions X , i.e., their union is X and they are pairwise disjoint. Now the idea behind the rest of the proof is we show for each region X j , there is a single function h ∈ H such that,(i) Xj t i=1 a i cov i (x) p(x)dx = Xi cov h (x)p(x)dx, where cov h (x) = Y 1[S(x, y) ≤ h(x)]p(y|x)dy. (ii) Xj l h (x)p(x)dx ≤ Xj t i=1 a i l i (x) p(x)dx + εp(X j ), where l h (x) = Y 1[S(x, y) ≤ h(x)]dy.Hence, from now on we fix an arbitrary X j and prove the existence of such h. For the ease of notation let us define X = X j and p(x) = p(x) p( X ) . This way X p(x) = 1 and p(x) is still continuous. Now we can rewrite our goals with this new notation. With a simple normalization we have,(i) X t i=1 a i cov i (x) p(x)dx = X cov h (x)p(x)dx, where cov h (x) = Y 1[S(x, y) ≤ h(x)]p(y|x)dy. (ii) X l h (x)p(x)dx ≤ X t i=1 a i l i (x) p(x)dx + ε, where l h (x) = Y 1[S(x, y) ≤ h(x)]dy.Now, as a result of Dominated Convergence Theorem, there is a large enough real value R such that for the set ofEQUATIONEQUATIONwhere the value of ε 1 > will be chosen later in a way that it would be small enough for the proof to work. Among the functions cov 1 , • • • , cov t there should be at least two of them, without loss of generality cov 1 and cov 2 so that X cov 1 (x)p(x)dx ≥ X cov 2 (x)p(x)dx + γ where γ > 0.Otherwise we have alreasy achieved our goal by picking the h i with the smallest average length. Now assume ε 1 < γ 4 (we will make sure to pick ε 1 in a way that it satisfies this condition). Hence we have,EQUATIONNow applying Lemma E.5 there exists X2 ⊆ X1 such that p( X2 ) ≥ γ 6 and for every x ∈ X2 we have cov 1 (x) ≥ cov 2 (x) + γ 12 . (Here one have to use Lemma E.5 usingZ = (cov 1 (x) -cov 2 (x)) 1[cov 1 (x) ≥ cov 2 (x)]1[x ∈ X1 ])Let us consider the following three sets that partition the space X ,EQUATIONC = X \ X1Note that these three sets are pair-wise disjoint and cover the space X . LEt us first consider the set C. we would like to consider a function h C such that,C t i=1 a i cov i (x) p(x)dx = C cov h C (x)p(x)dx, where cov h C (x) = Y 1[S(x, y) ≤ h C (x)]p(y|x)dy.To do so, without loss of generality, we assume,C cov 1 (x)p(x)dx ≥ C cov 2 (x)p(x)dx ≥ • • • ≥ C cov t (x)p(x)dx.Hence,C cov 1 (x)p(x)dx ≥ C t i=1 a i cov i (x) p(x)dx ≥ C cov t (x)p(x)dx. For r ∈ [0, ∞) let, f (r) = C∩B(0,r) cov t (x)p(x)dx + C\B(0,r) cov 1 (x)p(x)dx.Note that f (0) = C cov 1 (x)p(x)dx and f (∞) = C cov t (x)p(x)dx. Also, as a result of continuity assumptions, f (r) is a continuous function, therefore we can apply Intermediate Value Theorem. As a result, there should be r 0 < ∞ such that,f (r 0 ) = C t i=1 a i cov i (x) p(x)dx.We then naturally pick h c to be,EQUATIONLet us now consider the sets A and B. Note that by construction they both are a subset of B(0, R). Now let us consider a δ-net for A and a separate δ-net for B. Similar to our arguments in the proof of Theorem F.1, we can construct these δ-nets in a way that they partition A and B. That is to say we have, A =N A j=1 A j and B = N Bj=1 B j such that withing each δ-net the pair wise intersections are empty. Now, for each A j (and B j ) we choose independently one of {h i } t i=1 with probabilities {a i } t i=1 at random.Let J(A, j) (similarly J(B, j)) be the index of the function h i assigned to A j (similarly B j ). Then we have, Event 1:N A j=1 Aj cov h J(A,j) p(x)dx + N B j=1 Bj cov h J(B,j) p(x)dx - A∩B t i=1 a i cov i (x)p(x)dx ≤ √ δ.Event 2:j:J(A,j)=1 p(A j ) ≥ a 1 2 p(A).Event 3:j:J(A,j)=2 p(A j ) ≥ a 2 2 p(A).Now we can repeat the probabilistic argument of proof of Theorem F.1 here. The key insight is all of the three above-mentioned events are high probability events, in a 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 a deterministic realization that make all these events happen. Now on, we fix that deterministic realization. Particularly, this means we have a realization that satisfies all the events for arbitrary small δ. Now the idea is to make a small change in the configuration that comes from this realization that make the approximate coverage of event 1 to be an exact coverage. With a little abuse of notation, let J(A, j) (similarly J(B, j)) be the assignments of that deterministic realization. Without loss of generality, we can assume,EQUATIONwhere ε 2 ≥ 0 and ε 2 ≤ constant × √ δ (the case of ε 2 ≤ 0 can be similarly handled). That is to say, our deterministic assignment J(A, j) and J(B, j) led to a small under-coverage of ε 2 . The idea now is to "engineer" the assignments of some of the A j s in a 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 a 2 and p(A) are strictly positive numbers. Hence, as a result of ( 19) and (20) we have, p(A 2 ) ≥ γ 12 . Now we can argue through Lemma E.6. Consider the set Q = {j ∈ [N a ] | J(A, j) = 2}. We know from event 3 that p(Q) ≥ a2 2 p(A) ≥ a2γ 24 . Now let for every j ∈ Q : Z j = p(A j ). We know that Z j ≤ δ and γ ′ ≡ j∈Q Z j ≥ a2γ 24 . Applying Lemma E.6there exists a A, j ) to 1 for every j ∈ Q ′ ) then the amount of added coverage would be, j∈S ′ p(A j ) × γ 12 , where γ 12 appears following ( 19) and the fact that A i ∈ X2 . Hence, the amount of added coverage would be bounded by,Q ′ ⊆ Q such that j∈Q ′ p(A j ) ∈ [ γ ′ 1 2 δ 1 4 2 , 2γ ′ 1 2 δ 1 4 ]. Recall that since Q ′ ⊆ Q, then for any j ∈ Q ′ we have J(A, j) = 2. now if we reassign all the A j 's, j ∈ Q ′ , to h 1 (i,e changing J(EQUATIONEQUATION)Recall that we can pick δ as small as we want. Hence, we can pick δ small enough that we have,EQUATIONEQUATIONwhere the last inequality follows from the definition of ε 2 in (22) . This can be done by lettingEQUATIONEQUATION. Now by noting (23) and (24) it should be clear that by reassigning all any A j , j ∈ Q ′ , the total coverage added will be larger than ε 2 (hence in total we will over-cover). Now we can apply Intermediate Value Theorem once again. Let us define for r ∈ [0, ∞],f (r) = j∈Q ′ Aj ∩B(0,r) cov 1 (x)p(x)dx + Aj \B(0,r) cov 2 (x)p(x)dx.Here note that again as a consequence of continuity assumptions f is a continuous function. Also,f (R) -f (0) ≥ ε 2 . Hence there exists r 0 ∈ [0, R] such that, f (r 0 ) -f (0) = ε 2 .That is to say we can make the coverage exactly valid. Now let us analyze the deviation in length. Not that for x ∈ A ∪ B we have length is bounded by R. This means by reassigning the elements in the set A j ,j ∈ Q ′ , the change in length is at most R × j∈Q ′ p(A j ) ≤ 2Rγ ′ 1 2 δ 1 4, where the last inequaity comes from the fact thatj∈Q ′ p(A j ) ∈ [ γ ′ 1 2 δ 1 4 2 , 2γ ′ 1 2 δ 1 4]. Here again by choosing δ small enough,particularly δ ≤ ε 2Rγ ′ 1 2 4, we can ensure the change in length is smaller than ε, 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 β * such that f * (x) = ⟨β * , Φ(x)⟩ ≡ f β * (x). Since h * is a solution of the Relaxed Primary Problem so it should be conditionally valid with respect to class F. Therefore, as a result of Lemma 3.4, we should have,EQUATIONNow define obj(β) = max θ∈Θ g α (f β , h θ ). Since Θ is a compact set and g α (f β , h θ ) is convex (in fact linear) in β so the Danskin's theorem applies to obj(β). Therefore, as a result of ( 25),EQUATION)Now again as a result of Danskin's theorem, obj(β) is convex in β. Therefore, as a consequence of (26), β * is a minimizer of obj(β). 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 it is a solution to the Relaxed Primary Problem when solved over all the measurable functions). Putting everything together, h * 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,g α (f, C) = E f (X) 1[Y ∈ C(X)] -(1 -α) -E Y 1[y ∈ C(X)]dy where C f (x) = {y ∈ Y | f (x)p(y|x) ≥ 1}. Now, fixing f ∈ F, all we have to show is that g α (f, C f (x)) -g α (f, C(x)) ≥ 0 for every C(x) : X → 2 Y . Claim 2 g α (f, C f (x)) -g α (f, C(x)) ≥ 0 for every C(x) : X → 2 Y proof: We have, g α (f, C f (x))-g α (f, C(x)) (a) = E X Y (f (X)p(y|X) -1) (1[y ∈ C f (X)] -1[y ∈ C(X)]) dy (b) = E X Y (f (X)p(y|X) -1) 1[y ∈ C f (X)\C(X)] -1[y ∈ C(X)\C f (X)] dy (c) = E X Y (f (X)p(y|X) -1) 1[y ∈ C f (X)∆C(X)] dy ≥ 0,where, (a) follows from the definitions, (b) follows from the definition of set difference operation (\) where, A\B = {x | x ∈ A and x / ∈ B}, and (c) comes from the definition of C f (x). The proof is complete now. One can define,E X [d(C f , C)] ≡ E X Y (f (X)p(y|X) -1) 1[y ∈ C f (X)∆C(X)] dy,and rewrite the above calculation as,g α (f, C(x)) = g α (f, C f (x)) -E X [d(C f , C)].This reformulation is very intuitive. at a high level, it says maximizing g α (f, C(x)) over C, is equivalent to minimizing a distance between C and C f . be the optimal solution of Minimax Problem. Then, C * is also the optimal solution of the PP. Furthermore, C * has the following form:EQUATIONLet us also recall the definition of Primary Problem, Primary Problem (PP):Minimize C(x) E [len(C(X))] subject to E f (X) 1[Y ∈ C(X)] -(1 -α) = 0, ∀f ∈ FRecall that in this paper we assume that F = {⟨β, Φ(x)⟩|β ∈ R d } is a finite dimensional affine class of functions (see section 2.1).Assuming Φ = [ϕ 1 , ϕ 2 , • • • , ϕ d ].The Primary Problem can be equivalently written in terms of d linear constraints on the prediction sets C(x).Primary Problem-finite constraints:Minimize C(x) E [len(C(X))] subject to E ϕ i (X) 1[Y ∈ C(X)] -(1 -α) = 0, ∀i ∈ [1, d].We now take a closer look at the main optimization variable, i.e. the prediction sets C(x), and put it in the proper format. The prediction sets C(x) can be equivalently represented by a functionC : X ×Y → {0, 1} such that C(x, y) = 1[y ∈ C(x)]. Furthermore, we can expand the optimization domain from C(x, y) :X × Y → {0, 1} to C(x, y) : X × Y → [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 Minimize C(x,y):X ×Y→[0,1] X ×Y C(x, y)p(x)ν(y)dxdy subject to E ϕ i (X) C(X, Y ) -(1 -α) = 0, ∀i ∈ [1, d].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 Y is a discrete and finite set. This problem is a 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 a 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 a result, our analysis of the Linear PP (for general d) can be considered as an extension of this lemma which will be done using the KKT conditions. Now, let us rewrite the Linear PP: Minimize X ×Y C(x, y)p(x)ν(y)dxdy subject to:X ×Y ϕ i (x)C(x, y)p(x, y)dxdy -(1 -α) = 0, ∀i ∈ [1, d] C(x, y) ∈ [0, 1] ∀x ∈ X , y ∈ YThe 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(x, y) belongs to an infinite-dimensional 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 finite-dimensional. For a reader who is less familiar with infinite-dimensional spaces, what appears below is a direct extension of the duality theory (i.e. writing the Lagrangian) for the usual linear programs in finite-dimensional spaces.Let F be the set of all measurable function defined on X × Y. Note that F is a linear space. Let Ω be the set of all the measurable functions on X × Y which are bounded between 0 and 1; I.e.EQUATIONNote that Ω is a convex set. We can then rewrite our linear program as follows: and also define, for i ∈ [1, d] , the functional G i : F → R asEQUATIONFinally, we define the mapping G :F → R d as G(C) = [G 1 (C), G 2 (C), • • • , G d (C)] .Note that G is a linear (and hence convex) mapping from F to the Euclidean space R d .Using the above-defined notation, our linear program becomes:Minimize F (C) subject to: G(C) = 0 C ∈ Ωwhere 0 ∈ R d is the all-zero vector.Note that the feasibility set of the above program is non-empty, as C(x, y) = 1 -α, for all (x, y) ∈ X × Y, is a feasible point. We can now use the duality theory of convex programs in vector spaces (See Theorem 1, Section 8.3 of [68] ; Also see Problem 7 in Chapter 8 of the same reference). Specifically, let OPT be the optimal value achievable in the above linear program. Then, there exists a vector β ∈ R d such that the following holds:EQUATIONwhere ⟨β, G(C)⟩ denotes the Euclidean inner-product of the two vectors β, G(C) ∈ R d . Here, note that the vector β is the usual Lagrange multiplier.By denoting Φ(x) = (ϕ 1 (x), ϕ 2 (x), • • • , ϕ d (x)), and using (30) , we can write⟨β, G(C)⟩ = X ×Y ⟨β, Φ(x)⟩C(x, y)p(x, y)dxdy -(1 -α)⟨β, 1⟩,where 1 ∈ R d is the all-ones vector. As a result, by using (29) , in order to solve the optimization in (31) we need to solve the following optimization: Now, it is easy to see that as C(x, y) ∈ [0, 1] (due to the constraint C ∈ Ω), the above optimization problem has a closed-form solution C * :EQUATION)Finally, note that in this paper the measure ν is considered to be the Lebesgue measure -see Section 2.1 -hence, up to a constant normalization factor that can be absorbed into β, we have ν(y) = 1 for all y ∈ Y.The structure given in ( 33) is also sufficient. I.e. for any pair (β, C * ) such that (i) C * has the form given in (33) ; and (2) C * satisfies the coverage-constraints G(C * ) = 0, 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 is known as Strong Duality, which then results in the equivalence of Minimax Problem and Primary Problem, i.e we can change the order of min and max.Proof of Theorem 4.4: Let us recall the algorithm.f ∈F Maximize h∈H gα,n (f, h),where,C S h (x) = {y ∈ Y | S(x, y) ≤ h(x)}.For the ease of notation let us call g(f, h) = gα,n (f, h). let us also call the stationary solution to CPL by h * CPL and f * CPL . Now since g is a smooth function with respect to both of its arguments we have the following optimality condition,EQUATION)Recall that F is a d-dimensional affine class of functions over the basis Φ = [ϕ EQUATIONNow looking at the definition of g(f, h) =1 n n i=1 f (x i ) 1[S(x i , y i ), h(x i )] -(1 -α) - 1 n n i=1 Y 1[S(x i , y) ≤ h(x i )] -(1 -α) dy,We can take the derivative with respect to f . Hence we can rewrite 35 as what follows:EQUATIONOne 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 ∈[1, • • • , d],with probability 1 -δ we have,1 n n i=1 ϕ j (x i ) 1[S(x i , y i ), h * (x i )] -(1 -α) -E ϕ j (x) 1[S(x, y), h * CPL (x)] -(1 -α) ≤ 2Bε √ 2πσ + √ 2B ln 2N (H,d∞,ε) δ √ n for any ε > 0.Combining with (36) we get,E ϕ j (x) 1[S(x, y), h * CPL (x)] -(1 -α) ≤ 2Bε √ 2πσ + √ 2B ln 2N (H,d∞,ε) δ √ n for any ε > 0.Union bounding over (36) we have with probability 1 -δ for anyEQUATIONIn other words, we 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.The following inequality holds for every j ∈[1, • • • , d]. E ϕ j (x) 1[S(x, y), h * CPL (x)] -(1 -α) -E ϕ j (x) 1[S(x, y) ≤ h * CPL (x)] -(1 -α) ≤ BLσ 2 π Proof. E ϕ j (x) 1[S(x, y), h * CPL (x)] -(1 -α) -E ϕ j (x) 1[S(x, y) ≤ h * CPL (x)] -(1 -α) = E ϕ j (x) 1[S(x, y), h * CPL (x)] -E [ϕ j (x)1[S(x, y) ≤ h * CPL (x)]] (a) ≤ E ϕ j (x) 1(S(x, y), h * CPL (x)) -1[S(x, y) ≤ h * CPL (x)] (b) ≤ B E 1(S(x, y), h * CPL (x)) -1[S(x, y) ≤ h * CPL (x)] = B E X E S|X 1(S(x, y), h * CPL (x)) -1[S(x, y) ≤ h * CPL (x)] (c) ≤ B E X Lσ 2 π = BLσ π 2 ,where (a) comes from triangle inequality, (b) is derived by the definition of B= max i∈[1,••• ,d] sup x∈X Φ i (x), and (c) is followed by assumption 2 and Lemma E.2. Now combining Claim 3 and (37) we have with probability 1 -δ,E ϕ j (x) 1[S(x, y) ≤ h * CPL (x)] -(1 -α) ≤ BLσ π 2 + 2Bε √ 2πσ + √ 2B ln 2dN (H,d∞,ε) δ √ n for any ε > 0. Putting σ = 1 √ n and ε = 1 n we have for every j ∈ [1, • • • , d], E ϕ j (x) 1[S(x, y) ≤ h * CPL (x)] -(1 -α) ≤ √ 2B ln 2dN (H,d∞, 1 n ) δ + BL π 2 + 2B √ 2π√ nLet us also remind that each element f ∈ F can be represented by a β ∈ R d , where we use the notation f (x) = ⟨β, Φ(x)⟩ ≡ f β (x) (look at section 2.1 for more details). By linearity of the class F we can conclude with probability 1 -δ for every f β ∈ F,E f β (x) 1[S(x, y) ≤ h * CPL (x)] -(1 -α) ≤ ||β|| 1 √ 2B ln 2dN (H,d∞, 1 n ) δ + ||β|| 1 BL π 2 + ||β|| 1 2B √ 2π√ n .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 of 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] , as the main methods in standard conformal prediction to achieve marginal validity; (ii) Local Split Conformal (Local-SC) [22, 41, 70] and LocalCP [12] , as locally adaptive variants of Split Conformal; (iii) Conformalized Quantile Regression (CQR) [35] , as a state-of-the-art 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 J) and report the average performance over 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.First Part: 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(x, y) = |y-f (x)|, where f is a NN with two hidden layers of 64 ReLU neurons, trained on the training set.Second 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+CPL. Tables 1 and 2 summarize our results, reporting average performance over 100 random splits of the datasets. All reported numbers have standard deviations below 1 percent. 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 was ResNet-32. To evaluate the predictive performance of these models, we aimed to generate prediction sets that achieve a marginal coverage level of 95For the conformal training procedure, we utilized a 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 to optimize the setup.We considered four experimental scenarios: training the model with either ERM or ConfTr, followed by calibration using either split conformal prediction or CPL. The primary goal was to compare the effectiveness of these approaches in terms of both coverage and prediction set efficiency.In setups involving ConfTr, we further optimized the data split ratios to improve the length efficiency of the prediction sets, which explains the variation in train/calibration/test splits across the different ConfTr setups. For the ERM-based setups, no optimization was performed on the split ratios, as the focus was to emphasize the black-box nature of calibration approaches like CPL and split conformal prediction, which can act as wrappers around the trained models without altering the training procedure.As shown in the results (see Here we list all the datasets.• MEPS-19 [71] • MEPS-20 [72] • MEPS-21 [72] • blog feedback (blog-data) [73] • physicochemical properties of protein tertiary structure (bio) [74] • bike sharing (bike) [75] • community and crimes (community) [76] • Tennessee's student teacher achievement ratio (STAR) [77] • concrete compressive strength (concrete) [78] • Facebook comment volume variants one (facebook-1) [79] • Facebook comment volume variants two (facebook-2) [80] • The method for calculating the error bars should be explained (closed form formula, call to 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. • It 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 a 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 of range (e.g. negative error 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The running time for the experiments of this paper can also be done on CPUs (in the order of half a day). The point of view of our experiment section is 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 or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This paper has no foreseeable ethical issues.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: In this paper, we focus on developing a new algorithmic framework for Conformal Prediction which has immediate applications in areas such as healthcare. We do not anticipate any negative societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We don't see any foreseeable need for safeguards.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: We do not do such studies.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.The definition of gα(f, C) is the negative of the conventional Lagrangian.We are assuming 1 0 = +∞. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: The paper introduces a novel length optimization technique for conformal prediction designed to produce the shortest valid prediction intervals.
strength_weakness: strength_weakness: - The computational cost of the proposed algorithm seems expensive.
- The length optimization framework dependent heavily on the structure of covariates, which might not be feasible in all practical situations.
questions: questions: - The equation (2) appears to be equivalent to conditional coverage instead of marginal coverage in Gibbs et al.(2023) [1].
- In figure 2(b), the "optimal" solution is with respect to the choice of score function.
- In chapter 5.3, do you compare with weighted version of split conformal or non weighted?


[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. "Conformal prediction with conditional guarantees." arXiv preprint arXiv:2305.12616 (2023).
limitations: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: * The readability of the figures could be improved.
* 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.
questions: questions: * None.
limitations: limitations: * None.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2) 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.

3) 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.
questions: 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?

2) 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?

3) The paper discusses handling various classes of covariate shifts. How robust is the CPL method to unexpected or unmodeled shifts in the data distribution?

4) 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: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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).
- 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).
- Experiments are not convincing. 
    - 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.
    - 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].
    - 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.

### References
[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. "Conformal prediction with conditional guarantees." arXiv preprint arXiv:2305.12616 (2023).

[2] Stutz, David, et al. "Learning Optimal Conformal Classifiers." International Conference on Learning Representations.

[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.

[4] Bellotti, Anthony. "Optimized conformal classification using gradient descent approximation." arXiv preprint arXiv:2105.11255 (2021).

[5] Correia, Alvaro HC, et al. "An Information Theoretic Perspective on Conformal Prediction." arXiv preprint arXiv:2405.02140 (2024).

[6] Han, Xing, et al. "Split localized conformal prediction." arXiv preprint arXiv:2206.13092 (2022).

### Minor Issues
- 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.
- Figure 1 does not add much to the paper, in my opinion.
- Line 7: I believe the hyphen is unnecessary in “Conformal Prediction with Length-Optimization”.
- Line 76: “the” is repeated.
- Line 90: It seems a word is missing after “overly”.
- Line 137: I think “converge” should be “coverage” instead.
- Line 192: “that” should probably be removed.
- Line 228: “relax” should probably be “relaxed”.
- Line 255: Typo “velow”.
- Line 548: Typo $Z{h_2}$
- Line 664: Typo “traingle”
questions: 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.
2. In Figure 3, right-hand-side plot, CPL achieves smaller mean interval length than the optimal oracle in many cases. How is that possible?
3. 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?
4. 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?
5. 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)$.
6. The description of the covariate shift experiments in section 5.3. is very unclear. Could the authors elaborate further on the experimental setup? 

### References
[1] Gibbs, Isaac, John J. Cherian, and Emmanuel J. Candès. "Conformal prediction with conditional guarantees." arXiv preprint arXiv:2305.12616 (2023).
limitations: limitations: The paper does comment on its limitations and provides promising avenues for future work.

Comments: title: Please interact with authors
Additional Experiment on LLM Question Answering
Experimental Setup in Section 5.3
Response to Individual Questions
Addressing Reviewer's Comments on the Experiments
comment: Dear Reviewer,

First of all, we’d like to thank you for your thoughtful feedback and for considering our rebuttal and additional experimental results! We appreciate your acknowledgement of CPL’s contribution to enhancing predictive efficiency and robustness in conformal prediction. We agree with you regarding the need to incorporate these additional details which we will make sure to add in the revised version (given the extra page). And we hope that there is more opportunity to discuss these points, as we think that this feedback has improved our paper.

Regarding the importance of the black-box approach, the fundamental objective is to quantify the uncertainty of a model as it is used for point prediction. This means taking the model as given and focusing on understanding its uncertainty behavior without altering its internal parameters. In contrast, if an additional layer is trained on top of a model, as seen in some experiments by Stutz et al., it effectively quantifies the uncertainty of a different model. I.e., we would like to keep the model unchanged and provide uncertainty sets around what the model is predicting (i.e., quantify the uncertainty of the model). If we fine-tune the features learned by the model (e.g. by using some extra layers), the fine-tuned version will be a different model, and the resulting prediction sets quantify the uncertainty of the fine-tuned model (i.e. they are not a wrapper around the original model). This distinction is central to the standard approach in the conformal prediction literature.

To help clarify that our arguments are not “arbitrary”, let us mention two quotes from Gibbs et al. highlight the black-box perspective: (1) “In the predictive inference literature, conformal inference is often described as a protective layer that lies **on top of a black-box machine learning model** and transforms its point predictions into valid prediction sets,” and (2) “Emulating split conformal, we design our procedure as a **wrapper that takes any black-box machine learning model** as input. We then compute conformity scores that measure the accuracy of **this model’s predictions** on new test points.” These statements underscore the significance of treating the model as a black box.

That said, we do not believe that CPL and conformal training ideas should be seen as rivals but as complementary methods applicable at different stages of the conformal prediction (CP) pipeline. The CIFAR-10 experiment in our rebuttal demonstrates how both methods can be used together to optimize prediction set efficiency.

To further elaborate on scenarios where CPL is more applicable than conformal training due to its black-box approach: In many real-world applications, direct access to a model’s internal parameters is restricted due to privacy, security, or proprietary concerns. For instance, models like GPT-4 are closed-source, making it crucial to quantify uncertainty without altering the model itself. Even if we had access, altering the model to improve length efficiency could potentially degrade both in-distribution and out-of-distribution performance of the base model. Moreover, keeping the base model for point prediction and a fine-tuned one for constructing prediction sets means quantifying the uncertainty of a different predictive model, which is not aligned with our objective.

Additionally, looking beyond the important black-box distinction, our example in the introduction of the paper illustrates that the absorption of the threshold into the score ($|y - f(x)|$), as suggested by the reviewer, is not sufficient to achieve the optimal length in general. In that example (which we also highlighted in our rebuttal), we have argued that for length optimization, one must optimize the threshold, and this cannot be replaced by further optimizing the base model. I.e., **the threshold $h(x)$ can not be absorbed into $S(x,y)$**. The variance structure of the noise requires an adaptive threshold for length optimization, which is not possible through adjustments to the base model alone if we want to achieve optimal length.

We hope this response clarifies the distinctions and importance of the black-box approach in our work and further elaborates on the complementary nature of CPL and conformal training. 

Regarding the additional question, for the cases involving confTR, we also optimized over the split ratios between calibration and training to maximize length efficiency. I.e., since the underlying model is optimized in ConfTR, then we can also treat the split between training and collaboration data as a hyper-parameter that is optimized.  However, for the cases of ERM we used only 10k calibration and did not optimize over the split, to highlight the black box perspective. I.e,. in the black-box approach most of the training data is often used for training the model (to maximize its accuracy), and the prediction sets are constructed afterwards using a relatively small set of calibration data.
I thank the authors for the extensive rebuttal and extra experimental results. I am inclined to maintain my score, as the current version of the paper would need a thorough revision to include all the clarifications and new experimental details and results. That said, I am not going to oppose acceptance if the other reviewers are in favor of it.

Further, I would still argue the main contribution lies in combining conformal training (or length optimization) with the framework of Gibbs et al., and some of the distinctions made by the authors with respect to related work are somewhat arbitrary. For instance, emphasizing that the method works with black-box predictors is not helpful, since conformal training can also be applied on top of a black-box model by training an additional layer, like Stutz et al. did in some of their experiments. The distinction between manipulating the score function or the threshold is also not clear cut, since one could argue that $h(x)$ could be absorbed in $s(x, y)$. That is not to say the contribution of the paper is not valid. It is. Though I would argue the contribution is not strong enough to outweigh the other problems with the presentation and experimentation in the current version of the paper.

As a final question, in the additional experiments in the comparison against conformal training, why are the train/calibration/test splits not the same in the last two rows?
I have reviewed the authors' responses and the discussions from other reviewers, and I am confident in maintaining my positive score.
Thank you for the rebuttal. I have read through it and will maintain my score.
Dear reviewers to "Length Optimization in Conformal Prediction" (NeurIPS),

Thanks a lot for your work so far. This is a gentle reminder that you should interact with the authors at this stage. At a minimum, this would involve acknowledging the rebuttal (if you have not done so yet). 

Best,
The AC
We would like to express our gratitude to the reviewer for their thoughtful review and positive assessment of the paper. We appreciate the valuable feedback, which has helped to improve our work.
I thank the authors for the detailed response. I maintain my positive score of weak accept.
To further demonstrate the applicability/scalability of our method, we will include a large-scale experiment involving LLM question-answering in the camera-ready version. 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. 

The 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}$
similar to $1-f(x)_y$ for classification.

CPL 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.
Here we respond to the reviewer's concern regarding the clarity of our description of the experimental setup in Section 5.3. Below, we provide a more detailed explanation of our experimental setup for the RxRx1 dataset from the WILDS repository, highlighting key aspects and methodologies.

Dataset Overview:

The RxRx1 dataset consists of cell images obtained through fluorescent microscopy, with the task of predicting one of 1,339 genetic treatments. These images come from 51 different experiments, each representing covariate shifts due to varying execution and environmental conditions. Our goal is to create prediction sets that maintain valid coverage across these shifts, a challenge due to heterogeneity in the quality of predictions across different experiments and cell types.

Experimental Design:

1. **Covariate Shift Characterization:**

   - We follow a data-driven approach to characterize covariate shifts, similar to the method in Gibbs et al. (2023), by splitting the calibration data in half and estimate the probabilities of experiment membership in the first half. We estimate these probabilities using $\ell_2$-regularized multinomial linear regression on the pre-trained ResNet50 model's feature map outputs. We then use these estimated probabilities to form the class of covariate shifts. 

2. **Model and Data Splitting:**

   - We use a ResNet50 as the base model, pre-trained on 37 of the 51 experiments. These 37 experiments contain a total of approximately 91000 images. The remaining 14 experiments are split into calibration and test sets, each of which with approximately 16000 images. For CPL inner maximization (corresponds to $h(.)$), we train a linear head on the last-layer representations of the pre-trained ResNet50 model.

3. **Conformity Scores and Temperature Scaling:**

   - For each image $x$, the ResNet50 model outputs weights $\{f^i(x)\}_{i=1}^{1339}$ for the treatments. These are converted to probability weights $\pi^i(x)$ using softmax with a temperature parameter $T$ that is calibrated to adjust these probabilities. Temperature refines the accuracy of these probabilities. The conformity score $S(x, y)$ is computed as the sum of probabilities for treatments where the predicted probability $\pi^i(x)$ exceeds that of the correct treatment $\pi_y(x)$. 

4. **Comparative Analysis:**

   - We compare CPL with the Conditional Calibration algorithm, as proposed by Gibbs et al. (2023), and the Split Conformal method. Our findings, depicted in Figure 4, show that while both CPL and Conditional Calibration maintain almost valid coverage across shifts, CPL significantly reduces the average prediction set size due to its length optimization, which enhances the efficiency of prediction sets.

We will take advantage of the extra page in the revised manuscript to enhance the description of section 5.3.
“Which data is used to optimize...”

The algorithm 1 uses all the calibration data to optimize both $f(\cdot)$ and $h(\cdot)$, through a minimax procedure, where we alternatively take gradient descent with respect to $f(\cdot)$ and gradient ascent with respect to $h(\cdot)$. In that process, the outer min ensures the conditional validity of the prediction sets and the inner max improves length efficiency. We will clarify this in the updated manuscript. 

“In Figure 3, right-hand-side plot, CPL achieves smaller ...”

The optimal oracle has the smallest interval length **averaged over all the covariates (all the test samples)**, while achieving valid coverage with respect to each of the groups. You can see this by looking at the first bars on the right of the “Figure 3, right-hand-side plot”. The optimal oracle is achieving mean length interval of around 8.0 while CPL is clearly achieving more than 8. However, looking at the mean interval conditioned on each grouping of the data (which corresponds to the rest of the bars in the “Figure 3, right-hand-side plot”) CPL has smaller or larger mean interval lengths in different groups. We will elaborate on this matter in the revised version.

“I am somewhat confused by the notation. Sometimes ...”

We acknowledge the difficulty in the notation and we will make sure to improve the clarity of the notations in the revised version. In general, throughout the paper $\mathcal{F}$ denotes the class of covariate shift and $f\in\mathcal{F}$ a single covariate shift function in the class. However, sometimes $f(\cdot)$ is also used to address the base model (which will be fixed).
In line 280, by a NN with two hidden layers we meant our neural network architecture consists of three fully connected layers, with ReLU nonlinearities between layers. The first layer takes as input the feature vector X and outputs 64 hidden variables. The second layer follows the same template, outputting another 64 hidden variables. Finally, a linear output layer returns a pointwise
estimate of the response variable Y.

"How are $f(.)$ and $h(.)$ are parametrized in the experiments? Could the ..."

The function $h(\cdot)$ is parameterized by the natural parameters of the machine learning model used to implement it. For example, $h(\cdot)$ could be implemented as a neural network (NN). In each experimental setup, we specify the ML model we use for $h(\cdot)$. In our experiment setups, simple MLP models or fine-tuning the last layer of a pre-trained model suffices to get a good performance.

For the function $f(\cdot)$, recall that we define $\mathcal{F} = \{\langle \boldsymbol{\beta}, \Phi(x)\rangle \mid \boldsymbol{\beta} \in \mathbb{R}^d\}$, where each $f \in \mathcal{F}$ can be represented as $f(x) = \langle \boldsymbol{\beta}, \Phi(x)\rangle \equiv f_{\boldsymbol{\beta}}(x)$. Therefore, iterating on $f$ can be implemented by updating $\boldsymbol{\beta} \in \mathbb{R}^d$. For instance, in the case of marginal coverage, $\boldsymbol{\beta} \in \mathbb{R}$, hence it becomes a scalar optimization. For the case of conditional coverage with respect to $m$ groups, $\boldsymbol{\beta}$ would be an $m$-dimensional vector (see section 2.1).

In a nutshell, the number of parameters used for $h(\cdot)$ and $f(\cdot)$ is typically significantly less than the number of (learned) parameters at training time.

Concerning a more powerful base model, as mentioned above, we treat the base model as a black-box and quantify its uncertainty. We have also added a CIFAR-10 experiment (described earlier) to showcase that CPL can also improve the length on top of training methods like conformal training.

"Could the authors share some intuition or results on how tight..."

The coverage results in conformal prediction are typically provided in two ways. One is over the expectation on the calibration data (e.g. the one in Gibbs et al. [1]). The others are PAC-style guarantees similar to what we provide in Theorems 4.2. and 4.3. PAC-style guarantees are very common in the CP literature (e.g. see [2], [3], [4]). The PAC-style guarantees are stronger in the sense that they are stated with high probability over the draw of the calibration (rather than over expectation). These bounds are also known as training-conditional guarantees in the literature. PAC-style guarantees of $O(1/\sqrt{n})$ are generally optimal (e.g. see [2], [3]).

"The description of the covariate shift experiments in"

We will respond to this question fully in the next official comment.

**Regarding the minor comments, we thank the reviewer very much and we'll revise the text accordingly.**

**References**

[1] Gibbs, Isaac, et al.. "Conformal prediction with conditional guarantees." (2023).

[2] Sangdon Park, et al. "Pac confidence sets for deep neural networks via calibrated prediction." 2019.

[3] Vovk, Vladimir. "Conditional validity of inductive conformal predictors." 2012.

[4] Jung, Christopher, et al. "Batch multivalid conformal prediction." (2022).
**Scaleability of Experimental Design**

In our section on the experiments, we evaluate the performance of CPL in three different setups ranging in both regression and classification settings on real-world and synthetic datasets. Our experiments aim to compare CPL with other **state-of-the-art conformal prediction algorithms that treat the base model as a black box**. All three experimental setups are standard and have been used in the community to measure the performance of CP methods. In particular, section 5.1 setup is standard in comparing methods that provide marginal coverage as introduced by [2], section 5.2 is standard for group conditional methods as designed by [3], and finally, 5.3 setup is identical to that used by Gibbs et al. [1] to showcase performance under a class of covariate shifts.

Also, in response to the reviewers request, we will add the method of "Split localized conformal prediction" to the baselines of section 5.1.

**Additional Experiment on LLM Question Answering**

To further demonstrate the applicability/scalability of our method, we will include a large-scale experiment involving LLM question-answering in the camera-ready version. 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. 

The 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}$
similar to $1-f(x)_y$ for classification.

CPL 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.

**Computational Cost**

We acknowledge and agree with the reviewer's comment on the importance of computational cost. Two points about this matter are in order. (i) Going beyond the simple solution of split conformal for black box base models, would require an adaptive threshold (as argued in our paper). This adaptive threshold is often achieved by an extra optimization on the calibration data (e.g. see [1] and [2]). We are introducing length optimization on top of conditional validity, hence it is expected that one would have to still do optimization to find the threshold. (ii) our computational cost is not more than training an ML model for the threshold, and it can effectively be solved by gradient descent. For example, computing the gradients for inner maximization amounts to computing the gradient with respect to the parameters of a neural network (hence is totally scalable). Also, the outer minimization step is computationally lightweight and can be viewed as a form of hyper-parameter tuning. For instance, in scenarios focused on marginal coverage, the outer minimization reduces to a simple scalar optimization. We will ensure to include a comprehensive discussion on scalability in the camera-ready version of the paper.

**Description of the Experiments**

We acknowledge the reviewer's comment on the importance of a detailed description and detailed report of the results. The brevity in some parts is due to space constraints. In the revised version, we will take advantage of the allowed extra page to include more details on the setups and plot captions. 

We also acknowledge the importance of higher-order statistics. Some of these reports are in the paper (e.g. see lines 283-284 or 297), and some others were dropped as the error bars were negligible. We will make sure to improve the quality of statistics reports in the revised manuscript. We thank the reviewer for this comment.

We will also provide full details of implementation specifications, and include a link to our Python implementations in the camera-ready version.

**References**

[1] Gibbs, Isaac, et al.. "Conformal prediction with conditional guarantees." (2023).

[2] Romano, Y., et al. "Conformalized quantile regression" (2019).

[3] Jung, Christopher, et al. "Batch multivalid conformal prediction." (2022).

[4] Kumar, Bhawesh, et al. "Conformal prediction with large language models ...." (2023).