On Volume Minimization in Conformal Regression
Authors: Batiste Le bars
Pierre Humbert
Venue: ICML 2025 poster (2025)
Keywords: Conformal Prediction; Minimum Volume Sets
Primary area: general_machine_learning->everything_else
TL;DR: We study the question of volume minimization in Conformal Regression, we present new algorithms and derive finite sample bounds on the excess volume loss.

Abstract: We study the question of volume optimality in split conformal regression, a topic still poorly understood in comparison to coverage control. Using the fact that the calibration step can be seen as an empirical volume minimization problem, we first derive a finite-sample upper-bound on the excess volume loss of the interval returned by the classical split method. This important quantity measures the difference in length between the interval obtained with the split method and the shortest oracle prediction interval.
    Then, we introduce *EffOrt*, a methodology that modifies the learning step so that the base prediction function is selected in order to minimize the length of the returned intervals. 
    In particular, our theoretical analysis of the excess volume loss of the prediction sets produced by *EffOrt* reveals the links between the learning and calibration steps, and notably the impact of the choice of the function class of the base predictor. We also introduce *Ad-EffOrt*, an extension of the previous method, which produces intervals whose size adapts to the value of the covariate. Finally, we evaluate the empirical performance and the robustness of our methodologies.

On Volume Minimization in Conformal Regression
Batiste Le Bars
Pierre Humbert
Abstract
This is particularly useful when the user prefers to be con- fident with the range of values that Y can take, rather than having only a single predicted scalar value. In Section 2.1, we give short reminder on CP, and on the most important techniques to construct C' satisfying Eq. (1). While these techniques are completely distribution-free, making them quite powerful in practice, they still suffer from an important limitation: how can we be sure that the trivial prediction set C(a) = y is not returned? Indeed, this prediction set neces- sarily satisfy the condition (1). To prevent this, theoretical analyses of CP methods typically include an upper-bound the probability of coverage P(Y C(X)). Such upper- bound tends to 1 - a as the number of sample used to build C' grows, which somehow reflects that the prediction set cannot be the full support of Y. However, this is still insuffi- cient as one may take C(z) = y with probability 1 - a and C(x) = with probability a, resulting in coverage ex- actly equal 1-a, a. but with an expected size of (1 (1-a))D1 D*) Here, | denotes the size of y and will typically be infinite in regression settings where y = R. Such set is too large and therefore highly uninformative. Hence, the CP litera- ture suggests to also look at the size of the predicted sets to measure the performance of CP methods. The smaller is a prediction set, the more efficient it is considered. However, most works do this analysis empirically, while very few has been focusing on the statistical control of the size of CP sets.
We study the question of volume optimality in split conformal regression, topic still poorly un- derstood in comparison to coverage control. Us- ing the fact that the calibration step can be seen as an empirical volume minimization problem. we first derive a finite-sample upper-bound on the excess volume loss of the interval returned by the classical split method. This important quan- tity measures the difference in length between the interval obtained with the split method and the shortest oracle prediction interval. Then, we in- troduce Effort, a methodology that modifies the learning step so that the base prediction func- tion is selected in order minimize the length of the returned intervals. In particular, our the- oretical analysis of the excess volume loss of the prediction sets produced by F.f fort reveals the links between the learning and calibration steps, and notably the impact of the choice of the function class of the base predictor. We also introduce Ad-Efforte an extension of the pre- vious method, which produces intervals whose size adapts to the value of the covariate. Finally, we evaluate the empirical performance and the robustness of our methodologies.
In this paper, we therefore propose to study when C(x) is in fact solution of an optimization problem of the form:
1. Introduction
d Blu(C(X))
Conformal Prediction (CP) (Vovk et al., 2005) has recently been considered as one of the state-of-art technique to construct distribution-freee prediction sets satisfying proba- bilistic coverage guarantees. Formally, consider random variable Y) E X' x y' and some miscoverage level E [0, 1]. CP techniques construct a set-valued function C:X + 2 such that:
s.t. P(Y E C(X))
where μ is measure of the volume of the set C(x), typi- cally the Lebesgue measure in regression problems, the counting measure in classification. This optimization prob- lem ensures that among all prediction sets C(x) that satisfy the coverage condition (1), the volume of the returned set is also of minimal size. Looking at problem (2) instead of (1) alone is therefore more meaningful as it encapsulates the two key aspects of CP: coverage and efficiency.
P(Y E ((X))
(1)
Univ. Lille, Inria, CNRS, Centrale Lille. UMR 9189, CRISIAL. F-59000 Lille "Sorbonne Université Univ. Paris Cité, CNRS, LPSM, F-75005 Paris, France. Correspondence to: Batiste Le Bars Abatiste.le-bars @ @nria..rr.
1.1. Main Contributions
After describing the problem in Section 2.2 in Section 3 we restrict the prediction sets to be intervals of constant size, and show in Section 3.1 that the calibration step of
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Volume Minimization in Conformal Regression
split CP solves an empirical version of problem (2). This allows us to derive finite-sample bound on the excess volume loss of the returned prediction set, namely on the volume difference between the learned and the oracle prediction sets.
C: + 2 such that Vo X::
(t):=(uE)) s7(2, S á kn-a}
(3)
In the case where [(nc + 1)(1 - -0)1 > ne, we fix Ô1-a = +00, meaning that we take the trivial prediction set ((x) =V. Stated differently, Ô1-0 corresponds to the (1 (1-aj qu-anntle of the data set {S:) U [++00. Quite remarkably, if we only assume that the scores SI,..., Sn. and s(X, Y) are exchangeable, the set (3) satisfies con- dition (1) (Papadopoulos et al., 2002). Moreover, if the scores are continuous random variables, it can be shown that P(Y E Č(X)) S 1 a + 1/(m, + 1). Note that this type of guarantees are referred as marginal because the probabilities are taken with respect to the test point (X, Y) and the calibration set Deal
We then argue that for the learning step to be efficiency- oriented, the prediction function should minimize the (1 - a) e-quaantile of the absolute error. This motivates Ef fort, a new split CP approach that finds an empirical minimizer of such quantile. In Theorem 3.7, an excess volume bound shows the joint impact of the learning and the calibration step, supporting the intuition that more data- points should be dedicated to the learning step.
Section 4, we increase the class of prediction sets intervals with length adaptive to the covariates value, and present fo-Effort, an extension of the previous method. Finally, in Section 5, set of synthetic data ex- periments illustrates the empirical performance and the robustness of our approaches on asymmetric and heavy- tailed distributions.
Example 1. (Conformal regressors).
In the standard Split CP (Papadopoulos et al., 2002) the base predictor is function μ in F, class of regres- sion function. Typically, j = arg minnee Σ (Y; p(X.))²² Then, the score function is taken to be the absolute residual s(x, v) = [(x)). This gives the interval C(x) [ā(z) ai-as ((z) + 9--o]-
2. Background
2. In -eiihted Conformal Inference (Papadopou- los et al., 2008), an additional base predictor is added in order to have interval sizes that adapt to the value of X. More precisely, we have f (tu, o). with μ E F1. o E F2- ه is fitted as above, and â fits the residuals given X = x. i.e. à = arg min, oeF, Exs (R, o (X where R, = |Y; j((;)). Taking the scoring function s(z, y) = y (z)))//(x), the resulting prediction interval is given by C(x) = if(z)
2.1. Preliminaries on Split Conformal Prediction
In this section, we give some important reminders CP, focusing on the split approach at the core of this paper (Papadopoulos et al., 2002).
Let us assume that we have access to a data set D = {(X,, Ii)ss that split into a learning set Dirn and non-overlapping calibration set Deal, containing respec- tively ny 2 and n. 2 1 data points such that ni + n. = n.
((x) +
The first step of split CP, referred to as the learning step, consists in finding base predictor f F using the learning data set Dimn This predictor, denoted f, is then used to define nonconformity score function = 8 xxx - R. such that for pair (z. v) E X V, 8 s y) measures the level of non-conformity of the point (z, 3) with respect to the base predictor f. In other word, it measures how far the true value y from the prediction f(x). Whether we are in the regression or classification setting, many possible base predictors and score functions exist in the literature (see e.g. (Angelopoulos & Bates, 2023)). In Example I, we recall the most widely used base predictors and associated score functions for conformal regression.
3. In Conformalized Quantile Regression (CQR) (Ro- mano et al., 2019), we have f = (Qa/2: Q Q12) where Qa/2 E Fi (respectively Q1 E F2) is a quantile regressor of Y given X = I, of order oz (respectively 1 1 2) For instance, we take Qa/2 arg minqer, Σ Pa/z(X, - Q(X,)), where Pa/2 is the "pinball" loss (Koenker & Hallock, 2001). Q1-0/2 is defined analogously with P1-a/2- Then, we take (2, v) max mmax(Qa,22()) ((())) y. Q1-a/2(x)); which gives Č(x) = 1Q./2(2)) (z) - -a-a; Q (1 (x) ) + q1-a]
As our task here is not to be exhaustive on the CP literature, we refer to Vovk et al. (2005), Angelopoulos & Bates (2023). and Fontana et al. (2023) for in-depth presentations of CP and to Manokhin (2022) for curated list of papers.
In the second step of split CP, referred to the calibra- tion step, construct the prediction set. To this end, we first calculate the values of s taken on the calibration set Deal, called the nonconformity scores S; = 8 8x, Y.), i E [.ne]l Then, we compute the [nn + 1)(1 (011-a) a)] 1th small- where (1)) S .... S S(n)): and we return the set-valued function
2.2. Problem Statement
est nonconformity score -i-a := S([(m=+)((
In this work, we focus on conformal regression problems with y = R. Precisely, we study when and how split
2

---

On Volume Minimization in Conformal Regression
CP outputs prediction sets approximating the solution of Problem (2). Since consider regression tasks, let us first re-write the latter optimization problem by replacing j with the Lebesgue measure À : B(R) + [0, too]. ((R) being the Borel o-algebra on R::
which is itself linked with the problems of support estima- tion (Schölkopf et al., 2001; Munoz & Moguerza, 2006) and density level sets estimation (Polonik & Yao, 2000). De- spite the fact that these methods can all be used to construct prediction sets with a desired coverage level, their link with Conformal Prediction has received little attention in the past. Among the most well known works, we can mention those taking the idea of plug-in (conditional) density estimators mentioned above, top of which they add a calibration step to obtain better coverage guarantees (Lei et al., 2013; Lei & Wasserman, 2014; Izbicki et al., 2022; Chernozhukov et al., 2021). However, their theoretical results regarding the size of the returned set are mostly asymptotic. More importantly, modern supervised learning and CP techniques are rarely based on a non-parametric estimation of the (conditional) density, which can be difficult in practice. They are mostly based on the learning of a (parametrized) prediction function that belongs to set of hypotheses (see Example 1). Thus, the framework of Section 2.2, largely inspired by Scott & Nowak (2005), where we restrict the class of prediction sets to a smaller subset, seems more appropriate for the design and analysis of CP methods.
min E[X(C(X)) S.L. P(Y E ((X)) 2 at, (4) CECrent
where CRorel == (Measurable functions C : X' - (T)).
In the following, we refer to C as one minimizer of (4).
Note that optimizing over all possible measurable func- tions in CBoret can be difficult in practice but also some- times useless. For instance, in the regression setting where f (XX) (O, o²), the distribution of Y given X = x
Y = is symmetric and has only one mode. The optimal (*)
will thus necessarily be an interval centered at (x) (see the discussion below on closed-form expressions for C*).
In this simple case, we see that looking at the full set Crorel is useless one could only consider the set of functions ((x) that outputs intervals.
In this work, we will restrict the space of research CRreel in (4) to smaller sets of set-valued functions, namely those outputting intervals. Like in statistical learning theory, this restriction can be thought of as source of approximation error. In other words, we would like the restricted set to be sufficiently complex so that it includes (one of) the function solving (4). If it is not the case, we face such an approxi- mation error. Nevertheless, controlling this error is not the objective of this paper, as we are going to mostly focus on the estimation error, which comes from the fact that only an empirical version of (4) is going to be solved.
Efficient Conformal Prediction. Recently, the question of controlling the size of the learned prediction set and ex- plicitly see this as minimization objective has attracted a lot of attention. For instance in Yang & Kuchibhotla (2024) and Liang et al. (2024), the authors focus on efficiency- oriented model selection. Closer to our work, we can men- tion Stutz et al. (2022) and Kiyani et al. (2024), which consider an optimization problem similar to that of (4), with focus on the optimization aspects and on relaxations of the problem. However, they do not provide statistical guar- antees on the learned estimates. Finally, Bai et al. (2022) proposes a generalization of the split calibration step, where instead of a single quantile, multiple learnable parameters are optimized to minimize the size of the final prediction set.
On closed-form expressions for (4). In some settings, we can derive oracle prediction sets solving (4). For instance, when there is no covariate X, we recover the Minimum Volume Set (MVS) estimation problem of Scott & Nowak (2005). In that case, if Y admits a density py (y) with respect to X, we can derive a closed-form expression for C* in terms of density level sets: 3t, 2 such that C* = E E R (g) 2 t& as soon as A({y e R pY pv) = (a)) = O. Similarly, if we condition the expectation and the probability in (4) on X = x, and if Y|X = admits conditional density pyjx (v/=), we get C' = {y E R : PyIx (y) x=== 2 t., (x)} for some 1a, (x) 2 0 (Polonik & Yao, 2000; Lei & Wasserman, 2014). This has led to a whole literature based on plug-in (conditional) density estimators, which is not the approach considered in this paper but which is worth mentioning.
Other recent studies (Dhillon et al., 2024; Zecchin et al., 2024) have analyzed the expected size of split CP sets, high- lighting key factors such as the impact of the score function choice and the generalization properties of the base predictor. In Sharma et al. (2023), the authors derive PAC-Bayesian upper bound on the expected CP set size, involving em- pirical estimate of the size and a KL divergence term. They also propose an algorithm that modifies the calibration step of split CP to minimize their bound; however, they do not ex- plicitly instantiate their bound for their proposed algorithm, leaving the practical implications unclear.
2.3. Related Work
Our work differs from these approaches in several funda- mental ways. First, our theoretical guarantees are PAC- based rather than PAC-Bayesian eliminating the need for restrictive assumptions such as boundedness of the score
Minimum Volume Sets and Density Level Sets estima- tion. As mentioned above, problem (4) is strongly linked with the MVS estimation Problem (Scott & Nowak, 2005),
3

---

On Volume Minimization in Conformal Regression
function target variable Y. More crucially, our analysis introduces upper-bound on the excess volume loss, plicitly quantifying how much larger the CP set is compared to an oracle reference. This perspective is absent in prior works, which focus only on bounding the expected CP set size without reference to an optimal baseline. Finally, it is worth mentioning Correia et al. (2024), which provides an information-theone perspective by linking CP set size to conditional entropy.
I is given, the calibration step in split CP outputs a conser- vative empirical estimator of the oracle prediction interval solution of Problem (5).
From the theory of CP, we already know that f.
P(Y (X)) 2 1- a (see e.g. Lei et al.
(2018, Theorem 2.2)). It remains to study the excess volume loss of C),²" which is measured by the difference in length between Cf and C), To this aim, is sufficient to study the difference between the empirical quantile = Q(11 - a) m (S and the true quantile t = Q(1 - a; S), as done in the following proposition (proof in Appendix A.1).
3. Restriction to Intervals with Constant Size
In this section, we restrict the space of research in Problem (4) to the class of prediction sets C = {-),a()) = [f(-)- (.) + 4; J E F, 2 0}. This class is already quite interesting as it encapsulates the standard split CP regressor (see Example 1.1). Notice that for simplicity of exposition, and because it does not depend on z, in this section the expected size of Cf, E Coonst is simply denoted X(C},)) 2t.
Proposition 3.1. Let i @((1 ( and C1,7" the corresponding set. If the points in Deal are ii.d,, and if (n.+ +1(111110) a) is not an integer, then with probability greater than 1 5 we have:
The
fi A(1)2)) s 20(11 a
1-
log(2/0) :S) (7)
3.1. Base Predictor| f E F is Given: Optimality of the Conformal Step
a
+
nee 2nc
We first start in the setting where the base predictor is given, meaning that we do not consider the learning phase. Over C2 the optimization problem (4) becomes:
Interestingly, the right-hand side of (7) also corresponds to the optimal length of more conservative oracle, namely
X x with pn. = 1-a +
[og(2/8)
2n. This means
min 2t s.t. P(Y f(X) S t) 21-a: $20
(5)
Th
that, with high probability, the empirical interval obtained with the conformal step is smaller than the smallest oracle
Denoting by S - ( [(X] the random variable of the absolute residual, the solution of the above optimization cor- responds to the quantile of order 1-a of the random variable S. More formally, if we denote by Q( SS) [o, 1] + R the quantile function of S, then the optimal value solving (5) is exactly t" = Q(1 1011-00 ax; S) and the associated optimal set is O),² = [ - 1", (xx + ["]
interval with increased coverage 1 - a + Sm,, and where Sn. is tending to 0 as nhe grows.
Although interesting, the previous result does not really tell us how different is the size of the predicted interval compared with the oracle one. To obtain finite-sample upper bound on this difference, we must consider some regularity assumption on the distribution of S, and more particularly on its quantile function.
Importantly, notice that the conformal step of the original split CP in fact solves an empirical version of the previous problem, but with a slightly increased coverage:
Assumption 3.2. (Regularity condition). Let S IY f(X)]. vf E F. Va (0, Br, E (0, and L > 0 such that Q(::S) is locally (v, L)-Hölder continuous, i.e. Vql. 12 E [1 a r, a + r]:
min 2t $20
(6)
<1> (1 - (ne h + 1)
- ne
s.t.
The
1Q(1: - ((2::)) < L/q -gal"
with solution = +1(mm++)(1-a))) and associated set de- noted Cl (x) [f(x) - f() + f As mentioned above, f is the quantity computed during the calibration step of the split CP method (see Section 2.1). It corre- sponds to the empirical quantile function of S, defined by Q(q: (S, := inf[t: : Ee, 1(S; & t} 2 g). eval- uated at (1 - (ne + 1)/ne instead of 1 - a to be slightly more conservative. In other words, this means that, when
This type of regularity condition can notably be found in Lei et al. (2013); Yang & Kuchibhotla (2024), where it is used to obtain finite-sample bounds on the volume of the returned set. Given this assumption, we can derive the following corollary.
Corollary 3.3. Let the conditions of Proposition 3.1 and Assumption 3.2 hold. If ne is large enough so that 1-a +
ne
4

---

On Volume Minimization in Conformal Regression
1og(2/5)
2n < r, then with probability greater than 1 - 6:
admits a symmetric density with one mode at O, then taking f = ja is optimal, i.e. the minimizer of the MSE matches the minimizer of the (1 - -)-QAE However, this kind of assumptions can be quite strong in practice, reason why it is preferable to keep the minimization of the (1 - a)-QAE as the main objective, since it is optimal on Cz no matter the distribution of (X,Y)
A s s (CO,,)) + 2L +
log(2/6)
?
(8)
2nc
Proof. Direct application of Prop 3.1 with Assumption 3.2 and using the fact that - - 1.
3.3. Effort: UFFicieney-ORieeniie Split Conformal Regression
The previous corollary provides an excess volume upper- bound for C) compared to the oracle f.t"' This bound does not only confirm the asymptotic optimality of the con- formal procedure when f is given, but also provides a rate of convergence dominated by (n) when we get rid of constants and log factors. Although simple to be obtained, to our knowledge this type of bound has never been shown. Remark 3.4. When the base predictor is given, all the previ- ous study can be easily extended to the general CP nested set view of Gupta et al. (2022). For simplicity of exposition, this analysis is deferred to Appendix B.1
In this section, we propose a methodology to approach the oracle prediction set C/- ;- (x) = [f (x) - t", fz)) +*},
with f the minimizer of the (1 - -a)QAE (Problem (10)) and 1" = Q(1 - a; IY (X))), We place ourselves in the split conformal framework of Section 2.1, having access to learning data set D'rn used to learn f. and calibration data set Deal, With slight abuse of notation we will write E Dírn or Deal to indicate (X;, Y;) E D' or Deal
The proposed methodology. referred to as Effort, consists in the following steps:
3.2. Base Predictor f E F is Not Given: Sub-Optimality of the Least-Square Regressor
1. Learn f E arg min ब(1 - - a; {|X; - (Xx))leee))
fEF i.c. minimize the empirical version of the (1 (1-a)-QAt
In the previous section we saw that, when / is fixed, the calibration step of the split CP method corresponds to the minimization of the size of the interval, up to some statistical error. Now, we investigate how f should be learned during the learning step to obtain a prediction interval of minimal size. Let us consider Problem (4) over Cyuna
2. Proceed to the calibration step, i.e. take 8= Q(((1-
a) nctt The : :(0Y= - f(X)))l
For any test point X E X, output the prediction inter- val x = [f(X) - f()) +
min 2t s.L. P(Y - f(X) (t) (9)
SEF
In Effort, the main difficulty is in the first step, where the empirical (1 - a--QAE must be minimized. Indeed, does not have closed-form solution, and if we want to use gradient-based optimization algorithm, we must compute the gradient of the empirical (1 aa) --A-EE which not trivial, or might even not be clearly defined. In the following, we present gradient- based optimization procedure inspired by Pena-Ordieres et al. (2020).
By replacing with its optimal value as function of f, i.e.
1- Q(1 a; IV - s(X)),, we obtain what we call the
- -A-)-QAEE problem (Quantile Absolute Error):
min Q( a1 f(X))) PEF
(10)
In words, this optimization problem tells us that I should minimize the (1 - a)) ))-qunntlle of the distribution of S = [()]( This quite natural, since this quantile is the one selected to build the prediction interval, and the smaller it is, the smaller the interval will be.
3. OPTIMIZATION OF THE EMPIRICAL (1 aA-QAE
We assume that f E F is parametrized by 0 E θ, and for the sake of generality, we consider the problem:
What this optimization problem also tells us is that taking f as the minimizer of the Mean Squared Error (MSE) E[(Y- - f())) denoted μ(x)) E| x)). like is suggested in classical split CP, is not generally optimal in terms of volume minimization, and one should rather take the minimizer of the (1 -AF. Notice that, while in general the minimizer of the MSE does not match the one of the (1 -AE,, it does in some settings. For instance, in Lei et al. (2018, Section 3), the authors claim that if the residual distribution Y - ((X) is independent of X and
min @(1 or; (E(0; Zi) 2:)
(11)
Here, e x 2 + R is a loss function, taking as input a parameter and data point Z,. In the step of ffftrt, Z, (X,, Y.) and l(O: Z.) |Y/ - (x(,)))
To solve this problem, one natural idea is to use a gradient descent algorithm on Q(1 - a: (E(0; 2,) this function is not differentiable in O. We therefore follow the strategy of Pena-Ordieres et al. (2020) and consider a
However,
5

---

On Volume Minimization in Conformal Regression
smooth approximation it. More precisely, we first approx- imate the empirical cumulative distribution function (edf) F(t, == Diva [{((0; Z,) I t) by another function Fg where the indicator is replaced by a smooth version of it:
Theorem 3.7. Let the conditions of Prop. 3.1 hold, with the
points in Dira and Deal being i.i.d., and C f.t (x) be the
prediction interval output by Effort. If Assumption 3.2 and 3.5 are satisfied, the distribution of Y is atomless, ne
and ne are large enough so that 1-a + log(2/5)
S r and
0c(
Σ iEDi
-t),
2nc
@(F 8, me) Sr, then:
1. P(Y E f C) 21-aas a.s.
where 5 > is a parameter of the approximation. One possible choice for I'g is given in Pena-Ordieres et al. (2020, Eq. (2.6)) and is detailed in Appendix C. Then, we define the smooth empirical quantile function by:
2. With probability greater that 1 288:
A xC,x,))
S (c/-3-
f.8
(13)
Qe (q: (e(0; (ED))) = inf(t (t, 2 9) (12)
1 2T. +27
1og(2/01 V
For a given g and > 0, under mild assumptions on the loss function f(-), one can show that the gradient of Eq. (12) is well-defined and has closed-form that can be used in gradient descent algorithm. The full procedure is detailed in Appendix C.
+
+
+ 4LL((F ne))
n2
2nc
srooch sketch - Details in Appendix A.2. The first result is classical (Lei et al., 2018). Let us focus on the second one, proved with the following steps.
3.4. Theoretical Analysis
Step 1: In the first step of Effort, we are actu- ally solving the empirical objective min {t s.t. ni E DiE 1 - s(X.)) I 1 2 1 a), with so- lutions denoted by f and firn. Using the theory of MVS estimation (Scott & Nowak, 2005), we can compare this solution to the oracle one. Indeed, by adapting the proof of Scott & Nowak (2005, Theorem 1), can show that with probability greater than 1 1-66 5:
In this last subsection, we theoretically analyze the perfor- mance of the prediction output by fort. We are interested in two types of guarantees: (i) coverage guaran- tee and (ii) an excess volume loss guarantee like the one in Eq. (8). To this aim, we require the following assumption. Assumption 3.5. There exists 6FF ō, n) < +oo such that with probability at least 5:
IP Cl-a (X)]DIm) 2 1 (FFFFF,,,n) (14) fitmm
sup 120 fEF
P (Y - f(x) S
10 f(X.) s s0)
1=1
and
A (c))aa) Jitten)
S (c/-ato
S 5, m)
(15)
where é (F, de) and C fi-ato-i--at denotes the op- timal oracle interval with coverage increased by #FF n.)). This tells us that after the learning step we already have some guarantees: (i) a high probability coverage guaran- tee, with a looser coverage decreased by o(F, d, ne), (i) an excess volume guarantee, ensuring that the volume of the learned interval is smaller than the optimal one with coverage increased by Φ. Interestingly. this also means that the conformal step allows to obtain an almost sure cover- age guarantee, and to get rid of the statistical error due to (F, 5, ne) in the coverage.
Cl-a+o
In this assumption, o(F, n) bounds the worst-case esti- mation error of IP(YY - s(X) < () using the empirical estimate- 1 E 1 (ly--f(Xj) f(X.) < f over the whole func- tion class F and for any value of t. Typically, Φ(F, 5, n) will decrease with an increasing number of data points n and increase as the complexity of F gets larger. In the following proposition, we explicitly derive a closed-form expression for ofF, 5, n) when the function class F is finite.
Proposition 3.6. (Finite class F). If [F] < oc, then Assumption 3.5 is verified with $(F 8, n) = 1og(2 Fl/8)
2n
Similarly to the "classical" statistical learning framework, where is possible obtain generalization bounds for infinite hypothesis classes, it is possible derive other closed-forms for 4(F,6 5. n)) in the infinite case by involving complexity measures like VC dimensions or Rademacher complexities. This, along with the proof of Prop. 3.6, is discussed in Appendix B.2. We can now present our main theoretical result.
Step 2: From (15) we have ii I ti-ato and therefore i S t +8 888-f firn + tiiato" tt"
With (7) in Prop. 3.1, we have i S Q(1 a I-a + log 2/8) | - (Dr))) Moreover, from (14), firn Z 2nc
no
Q(1 $(F ne); ); I8 f(X)) Hence, thanks to Assumption 3.2, { - bern S L 1
[og(2/8)
V
+
ne
2nc
6

---

On Volume Minimization in Conformal Regression
LØ(F, 6, ng)". It remains to bound -i- 1". By defini- tion, we have i i-- = Q(1 + o: 1 fi-a+o (X)I,, and t" Q(1 - a: Y - (X)).. Moreover, we notice that fi-ato S Q(1 - a a |Y (X)]) since by definition fi-a+ minimizes Q11-a+0; Y (X))) over all f E F.
oracle close-form solution, which is given by the (1 a)-
quantile of - [XX] conditioned X = x, denoted by s" (2x) := Q(1 a; |Y f(x)) Interestingly, the function s* (az is the quantile regression function of [X)] given X = I. and corresponds to the solution of ms Bipi-a - - -(()) - s(x))] where P1-a is the pinball loss. Hence, natural solution is to use an empirical plug-in estimator of s*, i.c. minimizing an empirical version of the pinball risk, suggested in the next section.
Hence, 17- + 1- S LO(F, 6, ne ) by Assumption 3.2. We conclude by combining everything.
To the best of our knowledge, Theorem 3.7 is one of the first to provide such a finite-sample upper bound on the excess- volume loss. explicitly reveals the impact of the two split conformal steps of Effort. The two first error terms (in- volving n2,) match the bound of Corollary 3.3, and can be seen the volume loss due to the calibration step. While the third term, with o(F, 6, ng), is the error due to the learn- ing step. If we omit the dependence in ó, (FF ne) will [Compl(F)) where CF) typically be in the form of V R4
Remark 4.1. Another strategy could be to directly solve an empirical version of min [B[[(XX) s.t. IP(|Y f(X)l S s(X)) 2 1 aa. This would allow deriving results similar to those of the previous section (see Appendix B.3), but solving it in practice can be challenging, notably because of the empirical coverage constraint. No- tice that, although their objective is different from ours, Bai et al. (2022) face a similar optimization problem, where they propose a smooth and differentiable relaxation to solve it.
measures the complexity of F (see Prop. 3.6 and Appendix B.2). In most settings, we have Co) >> log(1/5)- Hence, the rate in Eq. (13) supports the important intuition that the learning step remains more important than the con- formal step, at least in the sense that more data-points are needed to reach convergence. It is thus preferable to assign more points to the learning than the calibration.
4.2. Ad-Effort
We now describe our second method, Ad-EffOrt, which extends Effort to prediction intervals with adaptive size. Like in Effort, we consider the split CP framework, hav- ing access to a learning dataset Dirn used to learn the base predictors s and 8, and calibration data set Deat Ad-Effore consists in the following steps:
4. Extension to Intervals with Adaptive Size
We now consider the case of prediction intervals whose size adapts the value of X. Formally, we consider the class of prediction sets Carlng
1. f E arg min Ū(1 a0 (V, - ((Xx(())))))m)))) fer
= [f(x) (x) s(x)): f E F, E S), where S is a class of non-negative functions. Importantly, this class of prediction sets encap- sulates the Socally-Weightee Conformal Inference and the CQR methods (see Examples 1.2 and 1.3).
s(x), f fxx) +
2. $ E arg min 1 ni sES
PI-a - f(Xi)) - s(x)))
3. = a) nott (iy -
f f(X.)) - (Xx))iEDDa))
4. For any test point X E X, output /)) (X) = [f(x)
4.1. Oracle Prediction Set and Conditioning over X x
/
-( f(x)) + +(X) + f]
Following a similar reasoning as in Section 3, we could first consider f fixed and derive closed-form oracle expression for s by solving Problem (4) with CRorel replaced by cylis Unfortunaelly, contrary to the previous section, the solution of this problem does not have a direct expression.
In the first two steps of Ad-Effort, we learn the model I as in ffrr and then fit the residuals using a quantile regression or order 1 - a. Note that, in those two steps, the same data are used to learn both the prediction model f and the quantile regressor s, but we also might split the learning set in two. Then, in the third step (calibration), we take the quantile of { f(X.)l s(X.)) This comes from the fact that the final prediction interval is in the form [f(x)) - =(x) - 1, fxx) + s(x) + t). and, given the base predictors (f, s). the smallest t such that we satisfy the coverage is Q(11 a);; Y - f(X) - sX)). This claim is easily proved by following the analysis of Section 3.1.
For this reason, we propose to modify the problem so that s admits an oracle closed-form expression which can be naturally estimated empirically. More precisely, we condi- tion the optimization problem over the event X = x, where E X. In that case, the problem becomes:
(16) This problem is more difficult than (10) as a conditional coverage constraint is now required, which is known to be harder to obtain in practice (Vovk, 2012; Lei & Wasserman, 2014). If S is sufficiently complex, Problem (16) has an
min s() s.t. -(I - #ES
The main limitation of Ad- Effort is the difficulty of pro- viding a theoretical guarantee similar to that of Theorem 3.7. This is notably due to the fact that while is learned in order to obtain conditional g guarantees, f is learned as in Ef fort,
7

---

On Volume Minimization in Conformal Regression
During the learning step of Ef fOrt, we solve the (1 a)- QAE Problem (10) using the gradient descent strategy of Section 3.3.1. The smoothing parameter e is set to 0.1, Nitter 1000, and the step-size sequence is {11/t)00) Je-r. Furthermore, the space of research F is restricted to the space of linear functions (see Appendix for additional re- sults with Neural-Networks (NN)). For the split CP method, the regression function is either estimated using a linear regression or, in order be fair in our comparisons, using robust linear regression with Huber loss with parameter 8 = 1.35. For all methods, the score function is the absolute value of the residuals, i.c., s(x, y) = by - f(x) and we set a = 0.1.
EffOrt
0.6
Standard
Length
Robust
0.3
Normal
2.25
Ad-EffOrt
2.00
LW-CP
COR
1.75
1.50
1.25
1.00
Normal
Normal estremes
Pareto
Pereto + extremes
Figure/ 1 (top) displays the boxplots of the 50 test lengths obtained in the 4 scenarios (the coverage can be found in Appendix D and is, as expected, near 0.9). Overall, Errt produces more efficient marginally valid sets than those obtained with the split CP method, in all scenarios. Interestingly, when the noise follows normal distribution (Figure top left panel), Effort and the split CP method with standard or robust linear regressor return similar sets. This was expected because with this type of distribution, the least- regressor is supposed to be as good as the minimizer of the QAE. This is as opposed to the mixture of Gaussians, where extreme points brings asymmetry and makes the linear least square regression not suitable anymore. When the noise follows a Pareto distribution (Figure top right panel), its heavy tail also makes the Split CP with robust regression output larger prediction sets. This could be explained by the fact that, in the learning step, the robust regression somehow gets rid of extreme points that should be kept, enforcing the calibration step to make a larger correction. the last scenario, both baselines are outperformed by Effort
Results:
Figure 1. Boxplots of the 50 empirical expected lengths obtained by evaluating EffOrt in Section 5.1 (top) and Rrr in Section 5.2 (bottom). The white circle corresponds the mean.
i.c. in order to obtain marginal guarantees. When f is fixed, one could actually derive guarantees on and its ability to solve (16) by providing a setting under which the quantile regressor is consistent, making (16) asymptotically verified. Last but not least, it is worth mentioning that, thanks to the calibration step, the marginal coverage guarantee is verified.
5. Experiments
In this section we compare methods, Effort and Ad-Effort, to the standard and locally adaptive ver- sions of split CP on synthetic data. Due to lack of space, additional results on real data are deferred to Appendix D.2. Code to run all methods is available at https: //github. http://eeeeettt/aaEeeeeee.eee.ee
5.1. Evaluation of Effort
5.2. Evaluation of Ad-EffOrt
We first show the ability of Effort to return valid predic- tion sets of smaller size than those returned by standard split CP methods. More precisely, we consider asymmetric and taive distribution, illustrating the robustness of our method to a wide range of realistic situations.
We now compare Ad-Effort to the Locally Weighted CP (LW-CP) and CQR methods (see Example 1). We consider a simple heteroscedastic linear regression model Y = X + E(X) where X ~ .N(0, 1) and E(x) follows the 4 distributions of the previous section and with variance multiply by x². During the learning step of Ad-EffOrt: solve the (1 - -AE Problem (10) using the gradient descent strategy of Section 3.3.1. The space of research JF is restricted to the space of linear functions. We then learn s(.) (second step of Ad-Effort) using a Random Forest (RF) quantile regressor. For the LW-CP method, the regression function is estimated using a linear regression and o(-) using a RF. Finally, for CQR, also use RF quantile regression. We set 0.1. More details on the experimental setup are available in Appendix D.1.
We consider linear regression model Y = = E where 0 ~ (4(0, 1)83 is fixed, X ~ (0, 13) with 13 the identity matrix of size 3 x 3, and È follows 4 different distributions: standard normal, a mixture distribution 0.95 (O 1) + 0.05 (2, 1). Pareto distribution with shape and scale parameters equal and 1, and another mixture equals to 0.95 Pareto(22 (2, 1) 0.05 (-,20 1). In the two mixtures, the additional normal distributions allow simulating extreme values. For each scenario, we generate Air = Nea = 1000 pairs (X,, Y,). as well as Ntest = 1000 test points to compute the empirical marginal coverage and the average size of the returned set. We repeat this procedure 50 times.
Results: Figure/ (bottom) displays the boxplots of the length for the 3 methods. The coverages can be found in
8

---

On Volume Minimization in Conformal Regression
Appendix D and are near 0.9. Furthermore, an illustration
Learning, 16(4))494-591, 2023.
of the returned sets is given in Figure of Appendix D. We see that Ad Effort returns valid marginal sets with length, on average, smaller or similar that the two other methods. Furthermore, the size of the boxplots are much smaller for our method than for the others. This means that Ad-Effoo Efrort returns sets with more consistent sizes. Finally, we would like to point out that, although CQR gives similar results to our method in some situations (e.g., with the Pareto distribution), it has the drawback to not assess the uncertainty of a particular prediction model f.
Bai, Y., Mei. S., Wang, H., Zhou, Y., and Xiong, C. Efficient and differentiable conformal prediction with general func- tion classes. In International Conference on Learning Representations, 2022.
Biau, G. and Patra, B. Sequential quantile prediction of time series. IEEE Transactions on Information Theory, 57(3):
1664-1674, 2011.
Chernozhukov, V., Wüthrich, K., and Zhu, Y. Distribu- tional conformal prediction. Proceedings of the National Academy of Sciences, 118 (((48))21007791118 2021.
6. Conclusion
Correia, A., Massoli, F. V., Louizos, C., and Behboodi, A. An information theoretic perspective on conformal prediction. Advances in Neural Information Processing Systems, 111100000111411 2024.
This paper explicitly analyzes split conformal prediction through the lens of an MVS estimation problem and show that, in order to minimize the length of the prediction in- terval, the base predictor should minimize the (1 a)- QAE, This motivates two new methods, F.f fort and Ad-EffOrt, that are both empirically shown to be more robust than baselines over a significant spectrum of data- distributions. For Effort, a detailed theoretical analysis highlights how the complexity of the prediction function classes impacts the prediction interval's length. It also re- veals that the calibration step allows to provide an almost sure coverage guarantee, at the cost of slightly increasing the excess volume loss, with term dominated by the statistical error due to the learning step.
Curtis, F. E.,, Wachter, A., and Zavala, V. M. A sequential algorithm for solving nonlinear optimization problems with chance constraints. SIAM Journal on Optimization, 28(1) 28(1):93--558 2018.
Dhillon, G. S., Deligiannidis, G., and Rainforth, T. On the expected size of conformal prediction sets. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1549-1557 PMLR, 2024.
Dvoretzky, A., Kiefer, J., and Wolfowitz, J. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp. 642-669, 1956.
In the future, would be interesting to explicitly control the error due to the approximation used in Section 3. and see its impact Theorem 3.7. It would also be relevant to con- sider more complex classes of prediction sets, such as union of intervals, and to propose extensions of our framework to multivariate outputs. On a more general aspect, linking the volume of CP with more classical Uncertainty Quantifica- tion frameworks (Sale et al., 2023) is an interesting research direction.
Fontana, M., Zeni, G., and Vantini, S. Conformal prediction: unified review of theory and new challenges. Bernoulli, 29(1):1223, 2023.
Gupta, C., Kuchibhotla, A. K., and Ramdas, A. Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496, 2022.
Acknowledgements
Harrison Jr, D. and Rubinfeld, D. L. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1):81-102, 1978.
P. Humbert gratefully acknowledges the Emergence project
MARS of Sorbonne Université.
Howard, S. R. and Ramdas, A. Sequential estimation of quantiles with applications to a/b testing and best-arm identification. Bernoulli, 28(3):1704-1733 2022.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Huber, P. J. Robust Estimation of Location Parameter.
The Annals of Mathematicall Statisties, 35(1):73 101, 1964. doi: 10. 10011114/00m//1177773322222 URL https: //ooi. /10 1211/22mm/111777///
References
Humbert, P., Le Bars, B., Bellet, A., and Arlot, S. Marginal and training-conditional conformal prediction. arXiv preprint arXiv:2405. 12567, 2024.
Angelopoulos, A. N. and Bates, S. Conformal prediction: A gentle introduction. Foundations and Trends in Machine
conditional guarantees in one-shot federated

---

On Volume Minimization in Conformal Regression
Izbicki, R., Shimizu, G., and Stern, R. B. Cd-split and hpd-split: Efficient conformal regions in high dimen- sions. Journal of Machine Learning Research, 23(87); 1-32, 2022.
Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression. In European Conference on Machine Learning, pp. 345-356. Springer, 2002.
Kiyani, S., Pappas, G., and Hassani, H. Length op- timization in conformal prediction. arXiv preprint arXiv:2406.18814 2024.
Papadopoulos, H., Gammerman, A., and Vovk, V. Normal- ized nonconformity measures for regression conformal prediction. Proceedings of the IASTED International Conference on Artificial Intelligence and Applications (AIA 2008), pp. 64-69, 2008
Koenker, R. and Bassett Jr, G. Regression quantiles. Econo- metrica: journal of the Econometric Society, pp. 33-50, 1978.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P.. Weiss, R., Dubourg, V.. Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Koenker, R. and Hallock, K. F. Quantile regression. Journal of economic perspectives, 15(4):143-156, 2001.
Lei, J. and Wasserman, L. Distribution-Fii free prediction bands for non-parametric regression. Journal of the Royal Sta- tistical Society Series B: Statistical Methodology, 76(1): 71-96, 2014.
Mena-Ordieres, A., Luedtke, J. R., and Waachter, A. Solving chance-constrained problems via smooth sample-based nonlinear approximation. SIAM Journal on Optimizution, 30(3):2221-2500, 2020.
Lei, J., Robins, J., and Wasserman, L. Distribution-fies prediction sets. Journal of the American Statistical Asso- ciation, (08(501))278-288) 2013.
Polonik, W. and Yao, Q. Conditional minimum volume predictive regions for stochastic processes. Journal of the American Statistical Association. 554459) 2000.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution- free predictive inference for regression. Journal of the American Statistical Associa- tion, 113(623):009--1111 2018
Romano, Y., Patterson, E., and Candes, E. Conformalized quantile regression. Advances in neural information pro- cessing systems, 32, 2019.
Liang, R., Zhu, W., and Barber, R. F. Conformal prediction after efficiency-oriented model selection. arXiv preprint arXiv:2408.0 07066, 2024.
Sale, Y., Caprio, M., and Höllermeier, E. the volume of a credal set a good measure for epistemic uncertainty? In Uncertainty in Artificial Intelligence, pp. 1795-1804. PMLR, 2023.
Luo, F. and Larson, J. An empirical quantile estimation approach to nonlinear optimization problems with chance constraints. arXiv preprint arXiv:2211.0000 11/22221.00000 100065, 2022.
Schölkopf, B., Platt, C., Shawe-Taylor, J., Smola, A. J.,
Manokhin, V. Awesome conformal prediction. apr 2022. doi: www.://1eennnne w4w.eeeoooooo6666..... 6467205. /1///1..00
and Williamson, R. C. Estimating the support of high- dimensional distribution. Neural computation, 13(7): 1443-1471, 2001.
URL https://doi:
org/ 10.
Massart, P. The tight constant in the Dvoretzky-Kiefer Wolfowitz inequality. The Annals of Probability, pp. 1269-1283, 1990.
Scott, C. and Nowak, R. Learning minimum vol- ume sets. In Weiss, Y., Schölkopf, B., and Platt, J. (eds.), Advances in Neural Information Pro- cessing Systems, volume 18. MIT Press, 2005. URL
Mohri, M. Foundations of machine learning, 2018.
attps://proceedingg neuripp.... cc/ hesppaper__fie /cc//ppee.fillee/pppr////////// 1B8806562295000033333312b22 Paper. pdf.
Munoz, A. and Moguerza, J. M. Estimation of high-density regions using one-class neighbor machines. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 28 (3):476 480, 2006.
Sharma, A., Veer, S., Hancock, A., Yang, H., Pavone, M., and Majumdar, A. Pac-bayes generalization certificates for learned inductive conformal prediction. Advances in Neural Information Processing Systems, 36:46807- 46829, 2023.
Nash, W., Sellers, T., Talbot, S., Cawthorn, A., and Ford, W. Abalone. UCI Machine Learning Repository, 1994. DOI: https://co.orr//022442//CCCC
10

---

On Volume Minimization in Conformal Regression
Stutz, D., Cemgil, A. T., Doucet, A., al. Learning optimal conformal classifiers. ICLR, 2022.
Vovk, V. Conditional validity of inductive conformal pre- dictors. In Asian conference on machine learning, pp- 475-490. PMLR, 2012.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
Yang. Y. and Kuchibhotla, A. K. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, pp. 1-13, 2024.
Yeh, I.C. Modeling of strength of high- high-performance con- crete using artificial neural networks. Cement and Con- crete research, 28(12):1977-1888, 1998.
Zecchin, M., Park, S., Simeone, O., and Hellström, F. Gen- eralization and informativeness of conformal prediction. In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 249-249. IEEE, 2024.

---

On Volume Minimization in Conformal Regression
Appendix
A. Proofs of Main Results
In this section give the proofs of the main results of the paper, starting with reminder of the Dvoretzky Sieerkky-Keeee----ee Ciefer-Wollowiie (DKW) inequality used several times in the proofs.
Lemma A.1. (DKW inequality (Dvoretzky et al., 1956; Massart, 1990)) Let X1, X2,..., Xn be real-valued independent and identically distributed random variables with cumulative distribution function F(). Let F. denote the associated empirical distribution function defined by Fn(x)= = - S x.). For all >>
sup F(x) - Fx(z)) > 8) Σ 2e 2ne? #ER
A.1. Proof of Proposition 3.1
We have that 2 x())=²) 2f. Let the events E1 == { 8 Q (1 (1-at
L-a
+
1og(2/6)
2nc ; ..) } and EDKW ==
mo
suprzo [t(() - Fs(())
log(2/6)
where Es(t) = P(S S t) and Ps(t)
1
2i=1 115; S t). The main ob-
2nc
no
jective of the proof is to show that the event EJ F.DKW.
We first recall that = @((1 -a) n (S.) then E₁ is equivalent to:
@(1-a0 a+ L-a (S: @(11 Q(11ar a+ 1-a log(2/0)
The /
+
nh
2nc
which then implies that
1 > fs((0(1-0)) - -a a +
log(2/6)
:s))
1 - a
The
2nc
Where the last implication can be found for instance in the left-hand side of Eq. (34) in Howard & Ramdas (2022). It comes from the fact that (1 (n, + 1) is not an integer and, in that case, Q: ((.) acts as an inverse of Fs.
Moreover, by definition of the quantile function and its relation with the cumulative distribution function (edf), have that
Es (0(1-at noe
1-a +
log(2/0)
2 (
:s))
1 1- a
log(2/8)
aa nee
+
2nc
2n
Hence,
Fs (e((011-0 a a 1-a + EDKW.
log(2/0), 2n
.s) F's (0((0(1 (0((1-a+ a
1-a ne
+
log(2/6),
5))
log(2/8)
which implies
ne
2nd
2n.
In the end, we have P(E,) S F(EnKW), and we conclude the proof by applying the DKW inequality from Lemma A. with
log(2/8)
2ne
A.2. Proof of Theorem 3.7
We now detail the proof of our main result, which follows the sketch provided in the main text.
The first point of Theorem 3.7, on the almost sure coverage guarantee, is a classical result the conformal prediction literature, see e.g. Lei et al. (2018, Theorem 2.2). Let us focus on the second result, which can be proved by following the two steps described hereafter.
12

---

On Volume Minimization in Conformal Regression
Step 1: We first notice that in the first step of fort, we are actually solving the empirical minimization objective:
min t
SEF,
1
Σ
110 ((X))
s.t.
TE
iEDiEn
with solutions denoted by and firm.
Using the theory of MVS estimation (Scott & Nowak, 2005), we can compare this solution to the one of the oracle problem and show that with probability greater than - 8:
P(Y E J, (X)]D)/)) 1 OFF 8, ne)
(17)
and
(C)ra (x)) S SA(C <x(C/rato fo (x))
(18)
Jdim
where ((F,8,n)) ne) and 0/ fiiato:fi-oto -00 6(F, ne). In other word, li-ato and l-ato the solutions of:
Cl-ato
(X) denotes the optimal oracle interval with increased coverage
+
min
JEF
s.t. P( - ((x)((X] (1)) ((F,0,m))
Proof of (17) and (18).
Let:
Up = {P(Y E C (X)|Dim)) < 1 a ((F,6,
. {a (cl-a (x)) > (C, al0 al0 (x))
fiter
0 { supizo..ER [ f(x) 5) +e Σ 11|1; f(x)) s < > oFF oF, mene)
The objective to show that Op U c O₂ since this would be mean that P(eş n 0 2 P(Og), where O is the complementary of θ. Then, applying Assumption 3.5 gives the desired result.
θ C Og Consider Op is verified, i.e.
IPYY Jo.. (X)lD(m)
1 6(F,8,n))
IP(Y E Cl-a
(X))D(m)
1
1(Y; f(x:) S fim) <1 a $FF nz)
Σ 1=1
a - f(x,)) s shra
fhio
n
1=1
- IP(Y E Cl-a (X))D(m)
1(11; f(xi) S bmnn < $6(F, nz)
i=1
> F(Y C) (X))D(m)
1[m f(x,)) & 6mm) > $(F,8,,m nz)
Th
O
Where the second implication is obtained using the fact that by construction
1 Σ 1(J2: f(X.)] S fimp a. Ny
Ox C O::
Let us first show that O₂ implies that:
13

---

On Volume Minimization in Conformal Regression
1
H( - (( S 1--0 <1
<1-a -a
(19)
n2g
1=1
Indeed, if we had ne E
(x.) s 2 a,a, then would necessarily have firn + since (c)
frrn is minimal over the empirical coverage constraint, which would imply that (C fition (x)) s A (c/, (Cl-at
aa- (x))
L.e. that Ox is not verified.
remains to show that (19) implies og. By (19), and using the fact that IP IP(1 - Si Si-ato(X] S ti ti 2 a+
(FF 5, ne):
ne fi (X,)] P(Ir fi-ata (X)]
St)1stj.. sti-ato) (FFF,o,nd
Thg
fi-a+o (xx))) - -P(1-- (xa-o(()) (X)s ti- $0F I(Y,
nt
O
This concludes the proof that θ₂ U Ox C Og and therefore Eq. (17) and (18).
Step 2: From Eq. (7) in Prop. 3.1 we have that with probability greater than 1 - 6:
1-a
log log(2/8) 2nc
isQ 1 1-
V
Y - f(X)(
(20)
With an abuse of notation, we therefore have P([(20))) 2 1 - 5 and P(((17) n ((18)) 2 - 5. Therefore, using the union bound over the complementary events, we get that P([(20)) n {(17) n ((18)) 1 25. In the following, we show that if (20). (17) and (18) are true, we have our final upper-bound, which will conclude the proof.
The size of the intervals being equal 2 times their radius the objective here provide high probability upper-bound on f. Thanks to (18), we have that birn I ti and therefore:
f Eirn + fi S fir + ti-ato = =t + firn + + ttiato -t"
We first control f firn-
Applying the quantile function Q(:/Y- - (((X) on (17) gives lo 2 Q(1 - - (FF - -(()) Hence, thanks to (20) and to Assumption 3.2, we have:
i- fim S @ a
1-a a a1
a
+
log(2/5)
. -(X)) - QQ(1 - a - -FFF 6, n.
- f(X))i
nee
2nc
< L 1 a
1og(2/0)
+ HFF 8, no))
+
2n
1og(2/5)
< L +
+ LÓ(F (ob(F,6,m4) k,
T1e
2n
It remains to bound ti- t². By definition, we have ti-a+o = Q(1 a d: Y (x)x++((())) and t = Q(1 a: Y f())).. Moreover, we notice that Q(1 - a + di l fi (X)) < Q(1 - a oi | - fx))) since by definition fi-tto minimizes Q(1 a + Φ; - f(X)) over all f E F. In the end, by Assumption 3.2 we have:
14

---

On Volume Minimization in Conformal Regression
f--00-- - t' 1 Q at at - - Q(1 - a: - - & LØ(F,o,ne))
We conclude the proof using the fact that J[ (X)) 2 and XCC (X)) = 2t"
ftt
B. Additional Results
B.1. The Nested Sets View
The split CP method described in Section 2.1 can also be described through the notion of nested sets (Gupta al., 2022), which encapsulates many types of prediction sets, base predictors and scoring functions considered in the literature. As claimed in Remark 3.4, this framework will allow us to generalize the results of Section 3.1 to a wider class of prediction sets.
In the nested set view, we consider the class of prediction sets Cuested {C),(())) nested; if E F R), where 'nested" means that for any fixed f E F and X, Cςa(x) C (z)( soon t'. Here, consider fixed base predictor S, but as usual, f is learned during the learning stage of the split method. In this setting, we can define the following general scoring function:
8y(2, v) = inf E T E Cra(t))
Then, the procedure is the same as in Section 2.1: compute the nonconformity scores S, == 8X(,,, Y,), i E [n.]] and find Finally, for any X, the prediction set C.9i- (z).
the [n, + (1 - ] smallest one qi == S (1(0 As usual, the marginal guarantee satistied (Gupta al., 2022, Prop. 1).
As mentioned above, an interesting aspect of this nested set framework is that it encapsulates many split CP approaches (Gupta et al., 2022, Table I) such as the ones of Example I, as shown in the following Example. Example 2. (Nested sets view of Example 1).
1. The original Split CP (Papadopoulos et al., 2002) is recovered in the nested set framework by taking f = {N}, (x) = (u(x) - ((()) + 1] and T = [0, oo).
2. In Locally-Weightte Weighted Conformal Inference (Papadopoulos et al., 2008), f (x)({ and T = [0, oo).
= -
3. In Conformalized Quantile Regression (CQR) (Romano et al., 2019), we have f = (Qa: 22-022aaaa C,,(x) = 1Qa(z)
1; (xQ)a(()) + and T TR.
We can now extend our results from Section 3.1 to the nested framework, aiming at showing that, when f is given, the conformal step indeed minimizes the size of the prediction set, to an error that vanishes as ne grows.
To this aim, need the following additional assumption the way the size of the nested grows with 4.
Assumption B.1. (Linear growth of the size.) Vf E F, Ea, b >> such that E ([)(C,,(X)) = at + b.
If we take the three previous examples, we have in 1) a = 2 and 0. 2) a (X)) and b = 0, and 3) a = 2 and
b (X) - (X)).
Over Chested and under Assumption B.1, when f is fixed the optimization problem (4) becomes:
min at + b 120
s.t. P(Y E Cx,(X)) 2 1-a,
which has the same solution as:
min
120
s.t. P(s 21)
15

---

On Volume Minimization in Conformal Regression
with solution 1" Q11 038 (X, Y)). Similarly, the conformal step solves empirical version of the previous problem:
min (20
1 The
s.t.
18, Y.) 2 (1 - (n) + 1)/nc
2m1
with solution & = @(L ( ((11())nn + 1)/mci (X, ())))) As in Section 3.1, controlling the volume sub-optimality is equivalent to control the error of an empirical quantile estimate, and we can provide a very simple extension of Proposition 3.1 and Corollary 3.3.
Proposition B.2. Ler = @((1 a) : (X,, XO) and (2)(() the corresponding (nested) prediction set. If Assumption B.I holds, the points in Deal are i.id,, and (me + 1)(1 - a)) is not an inleger, then with probability greater than 1 8 we have:
E {[((C)(())) [p saxQ
1-a a
log(1/0),
+
S + b.
ne
2nc
Moreover, if A'ssumpption 3.2 is true for S 8 (X,Y) and if ne is large enough so that L-a + probability greater than 1 we have:
log(1/8)
S r, then with
2nc
B B ab
1-a The
1og(1/6)
+
2n
Proof.
The proof is essentially the same as the one of Proposition 3.1 and Corollary 3.3, and is therefore omitted.
B.2. Closed-Fore Expressions for (FF 6, n)
In Proposition 3.6 we give closed form expression for o(F, 8, n) in the case of finite function class F. The proof is given hereafter.
Proof of Proposition 3.6. Let 0,
P
sup
P(YY f((x) -t) - Σ
111 - f(x)) f(x))
120.FET
P (|Y f(x) 5t) Σ 1[8, 1(x)) ((x))ss x0))
P
U
sup 120
SEF
P
sup
P P(Y [(x) 51) - 1 Σ 1(1 ((x,) 50/
-(x))
120
FEF
$ F 2ne"
where the last inequality we use the DKW inequality, and the fact that F is finite. Finally, taking e concludes the proof.
1on(2|FF//
2n
Other closed-form expressions can be obtained for infinite function classes using the classical notions of Rademacher complexity and VC dimension, as shown below.
Let _ [(x 3) + 1fly f(x) tt f F, 0}. The Rademacher complexity of the function class F is the quantity
1 - - f(x,) s
R₂ (F. =E,
Ep,c
sup
fEF
16

---

n) and (S, 8, n) can be obtained similarly as in On Volume Minimization in Conformal Regression
where e Cn Rademacher random variables. Then, direct extension of the proof of Theorem 3.3 in Mohri (2018) gives the closed-form o(F, 6, nt) = (F)
2n
is also possible bound the Rademacher complexity of F. first in terms of its associated Growth function (Massart's Lemma), and then in terms of its VC dimension, denoted VC(F) (Sauer's Lemma). Applying Corollary 3.8 and Corollary
3.18 in Mohri (2018) gives the closed-fome (() logee//ooge///v((F))
(1/8)
should be noted that more informative close-forms could be obtained by specifying the function class of F. For instance we could fix F to be the set of linear functions.
B.3. Algorithm with Excess Volume Loss in the Adaptive Size Setting
In Section 4.1, if Vs S and & 2 0 we have + t S (stability with addition of scalar), then the oracle problem is equivalent to:
min se,,s
[[x( +
s.t. P( - f(X) - s s(X) S 2
In practice, we propose to use Ad-EffOrt, however in order to obtain theoretical results similar to that of Theorem 3.7, another possibility would be to solve, during the learning step, an empirical version of the previous oracle problem, which complicated apply practice:
min 12 ne
Σ
s(X,) +t
(21)
iEDirn
s.t.
Σ
-
f(x.)) - s(x) --0
iEDIm
where 6,F,S, me) a penalty term relaxing the coverage constraint in order to obtain smaller prediction set. This term corresponds the statistical error of the empirical coverage, explicitly defined in the following assumption, which is necessary to derive result similar to that of Theorem 3.7.
Assumption B.3. There exists two quantities D(F,S,,, < too and (88,6 n) too such that:
P
sup fEF.2E
P(Y f(X)) s(X)
10% [(x)) s(x,) s $0) S $FF, 21-8
and
P sup #ES
E (X)
1
(Xx)) (S.88.)) 21-6.
In words, this assumption generalizes Assumption 3.5 the adaptive size setting, least for the first equation. Since in this setting we also estimate the expectation of the size, need the second equation make sure that its worst-case estimation error is bounded w.h.p. Closed-form expressions for Appendix B.2.
Denote by s,t) the solutions of the empirical problem, (f*' the solutions of the oracle one, and V(f, s, t), denote () (f) s(x) t, fx:)) s(x) + t). Under Assumption B.3, derive the following lemma, which is an extension of the result obtained at the end of Step I in the proof of Theorem 3.7.
Lemma B.4. Under Assumption B.3, have with probability greater than 26:
P(Y (X)(()) 21-a-2 -1-a-2
(22)
and
E a (c)aa()) ptr)]
(ct (x)) + (5, 6.))
< E
(23)
17

---

On Volume Minimization in Conformal Regression
Proof. The proof closely follows the one of Step I in Appendix A.2. Let:
U- = {P(Y E (22(()))Dm)) < 1- 1 -
O - {RR X (x)) [Dim)) > E | (C) (C)oo))))))) + 41b(5, &,ee),
0 ={ { sup
P( - ((X) x() s - the CiEDim 1112 - -(x:) - s (xx)) ((F
FETTNES,120
o - ={supees B[s(X)] - 1 Ni
EiEDim ((xi) 6()
The objective is to show that (0p U c ( U Indeed, using the union bound and Assumption B.3, this would imply that P(Op U Ox)= & P U+) & 26, concluding the proof.
O₂ C (O& )): Proved by showing that Op Os using the same arguments as in the proof of the main result. O C (0 J
Let the event Ω L E - f - -x S {*} < 1 - -6F, We first show that
me
O₂ c (SU by proving that (9P n ( c G. Indeed, under (I2 n (%)) we have:
Σ 1( - (xxi) (X,) 1t) 2 1 (F.S,8,
Tg
iEDien
8(X.) + is 1 Σ sx:+
Σ
nt
iEDImn
iEDim
+1 1 Σ si-a+o(X.) - B[si-a+o(X)) (X)]
([S(X) Fm +8+
Σ
8(X.) - B(5(X)|D! S Blsi-ato(X)]
TME
nie iEDio
iED!e
+ E[s(X) pm + B(si-a+o [X)] + + suu E[s(X)]
Σ s(Xi)
iEDio
E[ + < a [X) +t" + 28,68,8 ne)
2E(3(X)| + 21 < 2E is o X)) + 21 + 4,,(S 6, nz)
= -9
It remains prove that Ω O. Under Ω and using the fact that P (I fx(xx - s'(X) st) ((())
21-a 21-a:
s - -Xx) -xx) < <, Σ 1| - - (xx)
Thg
Di
Σ
1[ - (xx)) - (x,)) st) - P(I - (-)) -xx) 6(F,S,6mm.
nE
iEDiM
Os.
Hence Ω c Os, i.c. O^ c (QUD)) c (O)) which concludes the proof.
Like after step of Effort, with Lemma B.4 have probabilistic guarantees on the coverage and on the expected size of the returned set. Using conformal prediction, we can now obtain an almost guarantee on the coverage, at the cost of slightly increasing the size of the set by f. = @ @ a) m { - f(x)) - 8(X.))ie
Theorem B.5. Consider that Assumption 3.2 is satisfied for S = IY - f(x)] - s(X). Assume further that Assumption B.3
is verified, that the distribution of Y is atomless, that ne and ne are large enough so that not1 ((F, U,S.6 6, ne) S r, then we have:
[og(1/8)
< r and
18

---

On Volume Minimization in Conformal Regression
1. P(Y C.
f.ado (X))Dmm)
a a.s.
2. With probability greater that 36:
B
[xChte f.s.o (x)) Dirn, Deal I E ( (x)) +40(5, (4)
log log(1/5) ne +
+20(F,
1
(24)
Proof. Like in Theorem 3.7, the first point of Theorem B.5, on the almost sure coverage guarantee, is classical result of the conformal prediction literature.
We start the proof of the second point by recalling that since the distribution of Y is assumed atomless, we have with probability greater than 1 ó: 6:
log(1/6) Th +
P(Y- - f(x))
- 8(X)= S fe D'm DDal) $ -1-a+ Te
(25)
See Section 2.1 and Proposition 24 in Humbert al. (2024) for details this result. Like in the proof of Theorem 3.7, have P(((25) n ((22)) n {(23))) N 16,6, and it suffices to show that if (25), (22) and (23) are true, we have our final upper-bound.
We have E
[ (x(c) (x)) Dinn D = fale
-E (x((()aa(())
2f 2f. With (23) we have an upper-bound on Dirm
[ (Cl-o f.a.t
(x)
/ and remains show that fe 8 S T. (mc+1)F 2bb(F 8, n1)²)
Applying the quantile function
- -(x) pir.)
on (25), we get that i, s Q(1 - -a + not1 + log 1/66)
Y
not1
f(x) S ()) Dip)). ). Similarly, applying it on (22) gives / 2 Q(1 - - 26 nz): f((x) - 8( (()) (ppro Hence, thanks to the regularity condition, we have:
1
log(1/5)
i. 1-- iis
+ 26 (,) ne +1
me +1
C. Detailed Implementation of the Empirical (1 (1-a) a))-AQQ Minimization
As explain in Section 3,3.1, solve Problem (11) we use gradient descent strategy. However, because the empirical quantile is not differentiable, we replace Q in Problem (11) by the following smooth approximation:
Qe (f(0; Z))) = inf : Fe(t, 0) 2 q}
where F. is an approximation of the empirical distribution of the loss-values (e(0; Ze)) defined for s >> 0 by
(t, Σ (e(e((;; Z,) f)
iEDioa
with
2 5 -E
[e(2) = 72(2)
-5 < 2 <E
2 2
and [-,, - [0, 1] symmetric and strictly decreasing function such that it makes I, differentiable. One possible choice for Y/ is given in Ceda-Orrieres et al., 2020, Eq. (2.6)):
(=(=)=
15
2
+
2
+
8
(26)
16
3
15
19

---

On Volume Minimization in Conformal Regression
For given y and 0, under some assumptions the loss (see Pena-Ordieres et al. (2020)), the implicit function theorem implies that:
EiEDim (e((0 Zi) Q-(g: (f(0; 2.)) Vol(O;;
Vo Voleelas
(27)
EiEDioa (e(((( 2,) Q5(g: (E(0; (.)).e)
where Va denotes the gradient with respect to $ and I" is the differential of r. We can therefore use a gradient descent algorithm to solve an approximation of the QAE Problem (11) given by:
min ee(1 a; {e(0; Z:) hepDi))
To this end, starting from an initial guess 81, we simply make the iterates:
0x+1 02 Th Vol o; (c(0s; (e)))
where 7/ > 0 is the step-size. The full procedure summary in Algorithm when % is an in Eq. (26).
Algorithm 1 Gradient descent to solve the QAE problem (step 1 of Effort and Ad-Bffort)
1: Inputs: E, 01, Riter, (mh) SkSmmer
2: for k = 1, 1,... Mater do
3: A Q-(1 a: (E(Os: 2,) Zi))
4: i E Dirn do
B; + (f(0n; Zi) - A) = 15
(82- (22((10m::4)) 2,) 2))
185 11 < (1(06; A) <
5:
16
6:
C Zi)
7: end for
8: Os+1 c On Th L.b.C.DEE,BB
9: end for
10: Output: 0 0n
Remark C.I. In our setting, E is not differentiable because of the absolute value function. In practice, we therefore replace the gradient by a subdifferential (this is what we do the experiments). Another possibility could be to replace the absolute value function with smooth approximation, such as the Huber loss (Huber, 1964). Furthermore, as also done in Luo & Larson (2022), in Eq (27) we replace Qe (E(0: (eD))) by the empirical quantile for computation efficiency. Remark C.2. (Link with other formulations) Problem (11) is in fact similar to the single chance constraint problem (see e.g. (Curtis et al., (0))). can also be reformulated as the following bi-level optimization problem:
min t(0) #
s.t. t(0) arg
argmin min
Σ
P1-a(((() 2.) -t)
IEDIE
where P1-a is the pinball loss. Indeed, from (Koenker & Bassett Jr. 1978; Biau & Patra, 2011) know that ((0) Q(1 - a; [E(0; He))e)).
D. Additional Results
D.I. Synthetic Data
Experimental setup details for Section 5.2:
During the learning step of Ad-Effort, solve the (1 a)-QAE
Problem (10) using the gradient descent strategy of Section 3. The smoothing parameter e is set to 0.1, Miter 1000. and the step-size sequence is {(1/t)0.6 pateer paweer The space of research JF is restricted to the space of linear functions. The function s(-) (second step of Ad-Effort) and the two quantile regression functions of CQR are learned by using Random The function in LW-CP is learned
Forest (RF) quantile regressor, implemented in the Python package Aklearn-quantin using the RF regression implementation of scikit-learn (Pedregosa et al., 2011) Each time, the max-depth of the RF is set to 5 and the other parameters are the default ones of the sklearn-quantile and scikit-learn packages.
20

---

On Volume Minimization in Conformal Regression
Additional experiments: We now present additional results on synthetic data:
In Figure 2, we display the coverage obtained on the scenarios Section 5.1. We see that, as expected, all methods return sets with average coverage of 1 0.9 (white circle) regardless of the distribution of the noise.
In figure 3, we present additional results obtained when the base predictor is a Networks (NNs) and not a linear regressor as made in the main paper. We consider the model = X with & following the same distributions as presented in Section 5.1. In detail, we learn NNs with one hidden layer of size 10 and with ReLU activation function. In Effort, the NN is learned using the gradient descent strategy of Section 3.3.1. The smoothing parameter is set to 0.1, Aatte 1000 and the step-size sequence is {(1/1)09))= 1 The gradient with respect to the NN weights involved in the gradient descent is calculated using automatic differentiation. For split CP, the NN is learned using an ADAM optimizer and the loss either a Huber loss (robust NN) or least squares loss. Again, all scenarios, Effort returns marginally valid sets in general smaller than those split CP method. This confirms that learning model via the (1 a:) -AB problem better way obtaining small prediction sets during the calibration step.
In Figure 4, we display the coverage obtained on the scenarios of Section 5.2 when using Ad-Er Effor.. We see again that, as expected, all methods return sets with average coverage of 1 - a 0.9 (white circle) regardless of the distribution of the noise. Finally, Figure shows examples of prediction sets returned by Ad-Effort. Locally weighted CP (LW-CP) and CQR when the noise is Gaussian.
A different a between learning and calibration: In our theoretical analysis, and in all the previous experiments, the chosen to solve the QAE problem and the used for the calibration step are the same. To highlight the impact of differently chosen values, conduct additional experiments for Ef Effort, with the linear regressor used in the main paper, when the QAE problem is solved with &QAE = 0.05, 0.1 and 0.9 and the a of the calibration is 0.1. Results are shown in Figure 6.
From Figure top panels, we observe that QAE with oQAE 0.1 produces the smallest prediction sets. However, when no extreme values are present, the choice of (QQAE appears to have little impact. In contrast, when extreme values exist in the distribution, selecting QQ 0.05 significantly deteriorates the final prediction sets. This is expected, as the dataset constructed such that 5% of the values are extreme. Consequently, QAE with AQAE 0.05 attempts find f that minimizes the error for these extreme values, which is the opposite of being "robust." Figure 6 bottom panels confirm that the calibration step ensures the final coverage remains close to 0.9. Notice that similar sensitivity to a can be observed in other conformal prediction methods, such as CQR, when the acQR values for the quantile regressors are poorly chosen.
0.94
EffOrt
Standard
0.92
0.92
Robust
Coverage
Coverage
0.90
0.90
0.88
0.88
0.86
Normal
Normal + extremes
Pareto
Pareto + extremes
Figure 2. Synthetic data: Boxplots of the 50 empirical coverages obtained by evaluating EffOrt (see Section 5.1). The white circle corresponds the mean.
D.2. Real Data
We finally compare Ad-EffOrt with Locally Weighted CP (LW-CP) and CQR on the following public-domain real data sets also considered e.g. (Romano et al., 2019): abalone (Nash et al., 1994), boston housing (housing) (Harrison Jr
21

---

On Volume Minimization in Conformal Regression
25
1.2
EffOrt
1.0
Standard
20
Robust
Length
Length
15
0.8
10
0.6
5
0.4
Normal
Normal + extremes
Pareto
Pareto + extremes
0.94
0.92
0.92
Coverage
Coverage
0.90
0.90
0.88
EffOrt
0.88
Standard
0.86
Robust
0.86
Normal
Normal + extremes
Pareto
Pareto + extremes
Figure 3. Synthetic data: Boxplots of the 50 empirical expected lengths (top) and coverages (bottom) obtained by evaluating EffOrt (see
Section 5.1). The white circle corresponds to the mean.
Ad-EffOrt
0.92
LW-CP
0.92
Coverage
CQR
Coverage
0.90
0.90
0.88
0.88
Normal
Normal + extremes
Pareto
Pareto + extremes
Figure Synthetic data: Boxplots 50 empirical coverages obtained by evaluating Ad-EffOrt (see Section 5.2). The white circle corresponds to the mean.
Rubinfeld, 1978) and concrete compressive strength (concrete) (Yeh, 1998).3 We randomly split each data set 10 times into a training set, a calibration set and test set of respective "size" 40%, 40%, and 20%. The training and calibration
hhups:/www.es.eee http:///wwwww..tooooooooooo hhteee/cheeeeeeeeeooooooooooooon hhtp://archive.in uci aad.dddeeelllsssoomeeeeeeeeeeess
22

---

On Volume Minimization in Conformal Regression
3
AD-Effort
CQR
Regression
2
Set
Set
1
0
-1
-2
LW-CP
-2
-4
Regression
-3
Set
-2
Figure 5. Synthetic data: Example of sets returned by Ad-Effort (left), LW-CP (middle), and CQR (right).
2.0
20
1.5
Length
AQAE 0.05
Length
15
aQAE = 0.1
1.0
AQAE = 0.9
10
5
0.5
Normal
Normal extremes
Pareto
Pareto + extremes
0.94
0.94
0.92
0.92
Coverage
Coverage
0.90
0.90
AQAE = 0.05
0.88
0.88
aQAE 0.1
0.86
ØQAE 0.9
0.86
Normal
Normal + extremes
Pareto
Pareto + extremes
Figure 6. Synthetic data: Boxplots of the 50 empirical expected lengths (top) and coverages (bottom) obtained by evaluating EffOrt (see
Section 5.1) for different values of arq are when solving the QAE problem. The white circle corresponds to the mean.
sets are used to upply Ad-EffOrt, LW-CP, and CQR, and the to compute the coverage and length metrics. For Ad-Effort and LW-CP the base prediction function f is Neural-Network (NN) with one hidden layer of size 10 and ReLU activation function. The function in the step of Ad-EffOrt and the two quantile regression functions of CQR are learned with a Random Forest (RF) quantile regressor, implemented in the Python package sklearn-quantee The function ē in LW-CP is learned using the RF regression implementation of scikit-learn (Pedregosa et al., 2011). Each time, the mex-depth of the RF set to and the other parameters are the default ones of the sklearn- -utettileuanelleeee and scikit-learn packages. To illustrate the robustness our approach, we finally add, in all the data sets, 5% of outliers to the values to be predicted, using Gaussian distribution whose mean is equal to 2 times the maximum value of the original data.
23

---

On Volume Minimization in Conformal Regression
Figure 7 displays the length and the normalized length (i.e. the length divided by the maximal length obtained with the three methods in the 10 splits) obtained each data We marginally valid sets (see figure 8 for coverage) of smaller similar size to at least one of the other two methods, This is in line with the results obtained on synthetic data (Section 5 and Appendix D.1). Note also that the variability of the coverage metric (represented by the length of the boxes in Figure 8) is much smaller for Ad-E Eort t than LW-CP. Overall, these results show that Ad- Effort is empirically competitive with the main existing CP methods, while enjoying a strong theoretical grounding. It is therefore a method of choice for practical applications.
that Ad-Ef fort is competitive,
generally returns
250
1.0
Ad-EffOrt
LW-CP
Normalized length
200
0.8
XX
CQR
Length
150
0.6
100
0.4
50
0.2
Abalone
Concrete
Housing
Abalone
Concrete
Housing
Figure 7. Real data: Boxplots of the lengths (left) and normalized lengths (right) obtained with Ad aal-Efoort,o LW-CP, and CQR real data sets. The white circle corresponds to the mean.
0.95
Coverage
0.90
0.85
Ad-EffOrt
LW-CP
CQR
0.80
Abalone
Concrete
Housing
Figure Real data: Boxplots of the coverages obtained Effort, LW-CP, and CQR on data sets. The white circle
corresponds to the mean.
24


Reviews:
[{"review_id": "lMSUDyXiET", "reviewer": "Reviewer_gwDX", "summary": "Conformal prediction is a framework to construct label sets such that the marginal probability of coverage is guaranteed to be above a desired level $(1 - \\alpha) \\in (0, 1)$. This paper studies the conformal label intervals (one contiguous set) for unidimensional regression problems. The motivation is to minimize the marginal interval width (inefficiency) while maintaining the conformal coverage guarantee.\n\nIn doing so, the paper first considers fixed-width label intervals. Under this setting, the optimal regressor that predicts the center of the label interval is the one that minimizes the $(1 - \\alpha)$-th quantile of the residual distribution. The paper proposes EffOrt, a regressor trained to minimize an empirical approximation of the same. Additionally, the paper derives a bound on the difference in interval widths between the proposed method and an oracle, where the bound depends on the number of training and calibration data and the complexity of the function class.\n\nThe paper also proposes to learn to predict the interval widths to allow adaptivity. The optimal regressor is the one that minimizes the $(1 - \\alpha)$-th quantile of the conditional residual distribution. The paper proposes Ad-EffOrt, a conditional quantile regressor atop EffOrt, to approximate an empirical approximation of the same.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their constructive feedback and insightful questions. Below, we address each point in detail. We also appreciate the suggestions regarding our real-world data experiments and the approximation of the indicator function—these will be included in the final version using the extra page.\n\n**Questions:**\n\n- *For Theorem 3.7, what does the distribution of $Y$ being atom less imply? Why is that required? In Proposition 3.1, what happens when $(n_c+1)(1-\\alpha)$ is an integer? Will the same proof not extend to this setting?* \n\nWe address both questions together, as they are closely related. In both Theorem 3.7 and Proposition 3.1, at least one of the two conditions must hold. This requirement stems from a technical detail in our proofs, where we rely on an inversion property of the quantile function with the cumulative distribution function (e.g., line 583). This inversion does not behave well when the distribution has atoms, requiring careful handling. In the context of regression, assuming that $Y$ is atomless is a reasonable and often natural assumption.\n\n- What are the differences between the analysis done in this paper and that of Romano et al. [2019] to develop conformal quantile regression? \n\nThere seems to be a misunderstanding. In Romano et al. [2019], the authors construct prediction intervals by performing quantile regression of $Y$ given $X$ at levels $\\alpha/2$ and $1-\\alpha/2$, without learning a scalar prediction function. In contrast, our approach first learns a prediction function $f$ by minimizing the empirical $(1-\\alpha)$-QAE, and then (for Ad-EffOrt) estimates the quantile function of the residuals $|Y-f(X)|$ given $X$ to construct the prediction interval. While both methods involve quantile regression, their objectives differ. Additionally, Romano et al. [2019] do not theoretically analyze the size of the resulting prediction sets. \n\n- *What are the differences between the algorithmic choices in this paper and that of [Stutz et al. [2022]](https://arxiv.org/pdf/2110.09192)?*\n\n\nStutz et al. [2022] propose a method to incorporate conformalization directly into the learning phase by minimizing inefficiency through a differentiable loss. Key differences with our work include:\n\n1. Their focus is on classification, while we consider regression with residual scores.\n\n2. Our method directly optimizes the $(1-\\alpha)$-quantile of the scores, whereas they define and minimize an efficiency loss, necessitating an additional data split. Additionally, we use a different technique for the smoothing of the quantile function.\n\n3. Their approach requires a more complex algorithm, making theoretical analysis of prediction set sizes more challenging, whereas we provide explicit theoretical results on set sizes.\n\nOverall, while both approaches share conceptual similarities (e.g., smooth quantile computation), the methodologies differ significantly.\n\n- *How is Collarary 3.3 different from other bounds like Lei and Wasserman [2013]?*\n\nCould the reviewer be more precise by providing an equation to which he/she refers to in Lei and Wasserman [2013]? After a carefull check, it seems that this paper contains mostly asymptotic results, holding for their specific KDE-based estimator, but we might have missed something. \n\n- *Is it possible to experimentally validate the theoretical results?* \n\nWe made additional experiments to validate the theoretical result of Prop. 3.1. In the two following figures: https://ibb.co/G4MPB244, https://ibb.co/MDJDG33J, we illustrate the bound when $\\delta=.2$ and $\\alpha=0.5$. The first figure displays the evolution of one realisation of $\\lambda(\\hat{C})$ (in blue) and the rhs term of Eq. (7) (denoted $2Q$, in orange) with respect to the number of calibration points $n_c$. The second figure displays an histogram of the distribution of $\\lambda(\\hat{C})$ when $n_c=200$. The red line corresponds to $2Q$, the rhs term of Eq. (7).\n\n- *Isn't splitting the data across steps 1 and 2 of Ad-EffOrt better to avoid overfitting?* \n \nThis is a valid point. Splitting the data could improve generalization and reduce the prediction interval size. Theoretically, this could also facilitate deriving a bound similar to Theorem 3.7. However, even if overfitting occurs during training, the calibration step naturally corrects it by increasing the size of the prediction intervals.\n\n- *Is there a proof for Proposition 3.6?*  Yes, the proof is provided in Appendix B.2.\n\n**Other Related Work:** We appreciate the additional references. As our work focuses on regression, we had not included classification-specific papers; however, we will incorporate them in the final version. Most of the other cited works are already referenced in our paper, except for Dhillon et al. [2024], for which we refer the reviewer to our response to Reviewer d77L.", "claims_and_evidence": "Yes, the claims are supported.", "methods_and_evaluation_criteria": "Yes, they make sense. However, an additional baseline would be the methods by Stutz et al. [2022] and Kiyani et al. [2024]. They minimize the marginal label set size (an empirical approximation of it) with approximations and derivations similar to the ones in this paper. For instance, approximating the indicator function, minimizing the $(1 - \\alpha)$-th quantile of the residual distribution, etc.", "theoretical_claims": "1.\tI checked the proofs for Proposition 3.1, Corollary 3.3, and Theorem 3.7.\n2.\tFor Theorem 3.7, what does the distribution of $Y$ being atom less imply? Why is that required?\n3.\tIs there a proof for Proposition 3.6?", "experimental_designs_or_analyses": "Yes, the experimental design is sound. However, during the analysis, the paper highlights that Ad-EffOrt constructs label sets with more consistent interval widths (compared to the other baselines). This property is not necessarily beneficial because varied interval widths can signify adaptivity and help achieve (approximate) conditional coverage.", "relation_to_broader_scientific_literature": "The analysis and techniques used are very similar to existing works, notably Romano et al. [2019] and Stutz et al. [2022]. Because of this, the contribution of this paper feels limited to Theorem 3.7 only.", "essential_references_not_discussed": "There are works on the marginal size of the conformal label sets, termed inefficiency. Most show that conformal inefficiency asymptotically converges to that of an oracle under different settings: unsupervised learning [Lei et al., 2013, 2015], regression [Lei and Wasserman, 2013], binary classification [Lei, 2014], and multi-class classification [Sadinle et al., 2019]. Similarly, Vovk et al. [2014, 2016] and Sadinle et al. [2019] provide results under per-class/label coverage. Additionally, Dhillon et al. [2024] quantify conformal inefficiency in the finite-sample setting.\n\nThe paper includes some but not all references.\n\nReferences\n\nG. S. Dhillon, G. Deligiannidis, and T. Rainforth. On the expected size of conformal prediction sets. In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 1549–1557. PMLR, 02–04 May 2024.\n\nJ. Lei. Classification with confidence. Biometrika, 101(4):755–769, 10 2014.\n\nJ. Lei and L. Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71–96, 07 2013.\n\nJ. Lei, J. Robins, and L. Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278–287, 2013.\n\nJ. Lei, A. Rinaldo, and L. Wasserman. A conformal prediction approach to\nexplore functional data. Annals of Mathematics and Artificial Intelligence, 74(1):29–43, Jun 2015.\n\nM. Sadinle, J. Lei, and L. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223–234, 2019.\n\nV. Vovk, I. Petej, and V. Fedorova. From conformal to probabilistic prediction. In L. Iliadis, I. Maglogiannis, H. Papadopoulos, S. Sioutas, and C. Makris, editors, Artificial Intelligence Applications and Innovations, pages 221–230, Berlin, Heidelberg, 2014.\n\nV. Vovk, V. Fedorova, I. Nouretdinov, and A. Gammerman. Criteria of efficiency for conformal prediction. In A. Gammerman, Z. Luo, J. Vega, and V. Vovk, editors, Conformal and Probabilistic Prediction with Applications, pages 23–39, Cham, 2016.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper is well-written and easy to follow. The ideas progress well, making the function class progressively more flexible.\n\n2.\tThe area of research is well-motivated for practical impact.\n\nWeaknesses:\n\n1.\tThe analysis and techniques used are very similar to existing works. Conformal quantile regression [Romano et al., 2019] also uses conditional quantile predictors. The method by Stutz et al. [2022] makes similar approximations to define an optimization procedure.", "other_comments_or_suggestions": "1.\tIncluding the experimental results on real-world data in the main paper, over the synthetic ones, will help.\n\n2.\tIncluding a brief description of approximating the indicator function in the main paper will help.\n\n3.\tThe term \"the space of research\" is used many times but does not sound correct. The \"search space\" or \"function class\" might be better.\n\nTypos:\n\n1.\t\"This would allows deriving...\" $\\rightarrow$ \"This would allow deriving...\" (line 364, column 1).\n\n2.\t\"...while $s$ in learned in order...\" $\\rightarrow$ \"...while $s$ is learned in order...\" (line 368-369, column 2).\n\n3.\t\"...both empirically showed to be...\" $\\rightarrow$ \"...both empirically shown to be...\" (line 422-423, column 2)", "questions_for_authors": "1.\tWhat are the differences between the analysis done in this paper and that of Romano et al. [2019] to develop conformal quantile regression? The paper states \"...although CQR gives similar results to our method in some situations [...], it has the drawback to not assess the uncertainty of a particular prediction model $\\hat{f}$.\" (lines 411-414, column 2). Why is this a drawback? Arguably, learning end-to-end adds benefits.\n\n2.\tWhat are the differences between the algorithmic choices in this paper and that of Stutz et al. [2022]?\n\n3.\tHow is Collarary 3.3 different from other bounds like Lei and Wasserman [2013]?\n\n4.\tIn Proposition 3.1, what happens when $(n_{c} + 1)(1 - \\alpha)$ is an integer? Will the same proof not extend to this setting?\n\n5.\tIs it possible to experimentally validate the theoretical results?\n\n6.\tIsn't splitting the data across steps 1 and 2 of Ad-EffOrt better to avoid overfitting?\n\nRefereces\n\nJ. Lei and L. Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71–96, 07 2013.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dRIDfFrUw5", "reviewer": "Reviewer_J4Qu", "summary": "**Post-rebuttal edit:** The authors wrote convincing answers to my two grounds and questions. I keep my positive score. \n\n&nbsp;\n\nThe submission considers (split) conformal prediction for univariate data, with scores given by absolute values of the residuals, and with prediction regions given by intervals of the form $C(x) = \\hat{f}(x) - \\hat{t_\\alpha}, \\hat{f}(x) + \\hat{t_\\alpha}$ in the main case (Section 3), where $\\hat{f}$ is learnt on the learning set and where the $\\hat{t}_\\alpha$ are learnt on the calibration set, as quantiles of the empirical distribution of scores. The coverage level of these $C(x)$ are approximately $1-\\alpha$, under an exchangeability condition, as follows from a well-known analysis. The regression functions belong to some set $\\mathcal{F}$. The focus of this article is to relate the length of $C(x)$ to the length obtained by using the ground-truth quantile of the underlying distributions (depicted as the ideal length) and picking the optimal element in $\\mathcal{F}$ in this respect.\n\nThe main results are the final problem statement in Section 3.2 and the upper bound on the interval length given by Theorem 3.7 in Section 3.4: under natural assumptions (regularity of the quantile function, bound on the complexity of $\\mathcal{F}$), the length of the $C(x)$ is smaller than the ideal length plus two closed-form terms, both converging to 0 as, respectively, the sizes of the training and calibration sets increase (and where the term due to the learning set is larger; thus the learning set should feature more data points than the calibration set). \n\nThese main results are stated for an ideal version of the procedure (with a computational bottleneck); but simulations report effective results for a computationally more tractable version of the procedure. Also, an extension (without theoretical results) to intervals with lengths depending on the features $x$ is considered.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and constructive feedback. We are especially grateful for their recognition of the clarity and novelty of our contribution, particularly our use of statistical learning theory in the context of split conformal prediction. We will incorporate the suggested writing improvements in the final version of the manuscript. Below, we address the reviewer’s main questions and remarks.\n\n**Questions**\n\n- *Q1. The assumptions to obtain Theorem 3.7 are not clearly stated: are the training and the calibration data assumed to be i.i.d.?*\n\nYes, our theoretical analysis, including Theorem 3.7, assumes that both the training and calibration data are i.i.d. We will explicitly state this assumption in the manuscript.\n\n- *Q2. I guess that unfortunately, there are no theoretical guarantees for the computationally more efficient procedure described in Section 3.3? This looks like a critical limitation, which my score takes into account (I would raise it if I misunderstood this).* \n\nThe reviewer is correct—our theoretical guarantees currently apply only to the idealized procedure, and we do not yet have formal guarantees for the computationally efficient variant. We acknowledge this as a limitation and appreciate the reviewer bringing it to our attention. We will explicitly discuss this in the manuscript and highlight it as an important direction for future theoretical research.\n\n- *Q3. Could you clarify the statement \"theoretical analysis highlights how the complexity of the prediction function classes impacts the prediction interval's length\"? From my understanding the upper bound (13) given in Theorem 3.7 is only an upper bound, and can only give some insights, especially as both its first and third terms depend on the complexity of the prediction function classes.*\n\nThe reviewer is absolutely right that Theorem 3.7 provides an upper bound rather than a precise characterization of the true interval length. Our goal was to emphasize that this bound offers insights into how the complexity of the function class influences the gap between the constructed interval length, $\\lambda(C_{\\hat{f},\\hat{t}}^{1-\\alpha})$, and the optimal one $\\lambda(C_{f^*,t^*}^{1-\\alpha})$. Specifically, as the complexity of the function class increases, more training data is required for the bound on this difference to converge.   \n\n- *Q4. Did you consider the length minimization problem for another non-conformity score? If you did, do you know if similar results hold for signed non-conformity scores (such as the residuals), which seem more adapted to the asymmetric heavy-tailed distribution you considered in Section 5?*\n\nTo clarify, our framework does not explicitly rely on a chosen non-conformity score. Instead, the choice of score function is implicitly determined by the class of prediction sets, $\\mathcal{C}$, that we consider—namely, intervals of constant (Section 3) or adaptive (Section 4) lengths. Conversely, in standard split conformal prediction, one can view the choice of non-conformity score as implicitly defining a class of prediction sets. \n\nIn Section 3, the scores used in the calibration step correspond to absolute residuals $|y-f(x)|$, whereas in Section 4, they take the form $|y-f(x)| - s(x)$, which are signed scores. To answer the reviewer’s question, since we have not considered alternative classes of prediction sets, we have not explored other types of score functions. However, as emphasized in our conclusion, extending our framework to other classes of prediction sets (and therefore score functions) is an important direction for future work.\n\n- *Q5. I am surprised that the empirical coverages given in Figures 2-3-4 are, on average, slightly below the nominal coverage of 90%. How did you implement the SCP procedure in your experiments?* \n \nWe appreciate the reviewer pointing out this observation. After re-running our experiments, we found that the slight undercoverage was due to the limited number of repetitions in our empirical evaluation—averaging over 50 trials was not sufficient to smooth out random fluctuations. Indeed, due to the inherent stochasticity of different random datasets, finite-sample variability can cause slight deviations from the coverage. We will clarify this in the appendix.", "claims_and_evidence": "Yes, as far as the setting and the results of Sections 3-4-5 are concerned; see the detailed discussions below, both for theoretical claims and simulations.", "methods_and_evaluation_criteria": "The setting considered makes sense.", "theoretical_claims": "I checked in details the proofs of Proposition 3.1 and Theorem 3.7 (located in Appendix A), and could spot no issue.", "experimental_designs_or_analyses": "I read Section 5, which looks to me like a decent set of experiments on artificial data.", "relation_to_broader_scientific_literature": "The submission discusses well the broader literature, like the minimum volume estimation problem, typically dealt with through density estimation.", "essential_references_not_discussed": "No issue spotted.", "other_strengths_and_weaknesses": "The problem of interval-length-minimization is natural in (split) conformal prediction, yet, few results were available. This submission provides an elegant approach for this: the additional length due to calibration is handled through the DKW inequality (on empirical cdfs), while the additional length due to learning is bounded through the theory of suprema of empirical processes (hidden in Assumption 3.5). These classic tools of statistical learning are well used in the context of split conformal prediction. This is the first strength of the submission.\n\nThe other strength is the clarity of the exposition and writing. In particular, it was a nice idea to discuss first the error due to calibration (in Section 3.3) and add later (in Sections 3.2 and 3.4) the error due to learning. Also, the final paragraph of Section 3.4, about the respective importances of the train and calibration sets, is an important take-home message.", "other_comments_or_suggestions": "Sections 1 and 2 could perhaps focus faster on the specific class of problems studied in Section 3; they take quite some space to discuss the problem in generality, but the problem is later not studied at this degree of generality. Also, results like the rewriting of the optimization problem as Equation (10) could fit earlier in the article. \n\nIn particular, in Section 2.2, the optimization problem (4) is stated in great generality whereas the optimization problem (5) corresponds to a specific (yet legitimate) choice of non-conformity score. This dependence shoud have been emphasized, as in practice, the choice of the non-conformity score usually has a larger impact on the efficiency than the loss used in the training step.\n\nSection 5.1: Could you detail what a 'robust linear regression with Huber loss' is, and why it helps for a fair comparison?\n\nIn Section 5, you take $n_{lrn} = n_{cal} = 1000$. Are these values large enough for the conditions in Theorem 3.7 to be met?\n\nTypos\n- 044:1 \"miscoverage\" instead of \"coverage\"\n- 055:2 drop the \"for any $x$\" \n- 403:2 \"coverages\" instead of \"coverage\"\n- 699 \"thanks to (20)\"\n\nSuggestions\n- State Assumption 3.5 and Proposition 3.6 with a $n_l$ instead of a $n$?", "questions_for_authors": "Q1. The assumptions to obtain Theorem 3.7 are not clearly stated: are the training and the calibration data assumed to be i.i.d.? \n\nQ2. I guess that unfortunately, there are no theoretical guarantees for the computationally more efficient procedure described in Section 3.3? This looks like a critical limitation, which my score takes into account (I would raise it if I misunderstood this). \n\nQ3. Could you clarify the statement \"theoretical analysis highlights how the complexity of the prediction function classes impacts the prediction interval's length\"? From my understanding the upper bound (13) given in Theorem 3.7 is only an upper bound, and can only give some insights, especially as both its first and third terms depend on the complexity of the prediction function classes.\n\nQ4. Did you consider the length minimization problem for another non-conformity score? If you did, do you know if similar results hold for signed non-conformity scores (such as the residuals), which seem more adapted to the asymmetric heavy-tailed distribution you considered in Section 5?\n\nQ5. I am surprised that the empirical coverages given in Figures 2-3-4 are, on average, slightly below the nominal coverage of 90\\%. How did you implement the SCP procedure in your experiments?\n\n&nbsp;\n\n**Post-rebuttal edit:** The authors wrote convincing answers to my two grounds and questions. I keep my positive score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AJBjElViz8", "reviewer": "Reviewer_d77L", "summary": "The paper theoretically studies the efficiency of CP sets, providing bounds for the specific task of regression. The bounds are given assuming a fixed base predictor, or in the case where the predictor is learned on held-out data (split CP). For the latter case, the authors also highlight the importance of minimizing the Quantile Absolute Error (QAE) in order to reduce inefficiency at calibration time. This insight is then used to propose two algorithms, EffOrt and Ad-EffOrt, which minimize a surrogate of the QAE. The solution is tested for regression tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s thoughtful feedback and the references provided. We acknowledge that some relevant prior works were overlooked, and we will incorporate them into the related work section to ensure a more comprehensive discussion. While we recognize that this may slightly refine the novelty claims of certain aspects of our work, we firmly believe that our contribution remains **distinct and complementary** to these existing efforts.  \n\nIn particular, while most of the cited works (except [5], which focuses on linking CP set size to the conditional entropy $H(Y|X)$) aim to theoretically analyze the size of conformal prediction (CP) sets, **none explicitly study the notion of \"excess volume loss\"** introduced in our work. This metric quantifies the gap between the CP set size and an oracle reference, offering a more precise measure of inefficiency. For instance, while [4] provides a PAC-Bayesian upper bound on CP set size, their analysis does not incorporate an oracle baseline, preventing an explicit characterization of suboptimality.  \n\nBelow, we present a new paragraph that will be added to the related work section, directly addressing the reviewer’s concerns.  \n\n---\n\n **New Paragraph: Comparison with Missing Related Works**  \n\n*Recent studies [1,2,3] have analyzed the expected size of split CP sets, highlighting key factors such as the impact of the score function choice [1] and the generalization properties of the base predictor [2,3]. In [4], the authors take a step further by deriving a PAC-Bayesian upper bound on the expected CP set size, involving an empirical estimate of the size and a KL divergence term. They also propose an algorithm that modifies the calibration step of split CP to minimize their bound; however, they do not explicitly instantiate their bound for their proposed algorithm, leaving the practical implications unclear.*  \n\n*Our work differs from these approaches in several fundamental ways. First, our theoretical guarantees are PAC-based rather than PAC-Bayesian, eliminating the need for restrictive assumptions such as boundedness of the score function or target variable $Y$. More crucially, our analysis introduces an upper-bound on the excess volume loss, explicitly quantifying how much larger the CP set is compared to an oracle reference. This perspective is absent in prior works, which focus only on bounding the expected CP set size without reference to an optimal baseline. Finally, it is worth mentioning [5], which provides an information-theoretic perspective by linking CP set size to conditional entropy.*  \n\n---\n\n**$\\alpha$ different between learning and calibration**\n\n\nThis is an interesting question. To address it, we conducted additional experiments where the QAE problem was solved with $\\alpha_{QAE} = 0.05, 0.1$ and $0.9$. The results are presented in the following anonymous figures:\n(1) [Figure 1](https://ibb.co/fYR6MDgy) – Length for Normal and Normal + Extreme,\n(2) [Figure 2](https://ibb.co/5gdtRJ0t) – Length for Pareto and Pareto + Extreme,\n(3) [Figure 3](https://ibb.co/HTLb2DS4) – Coverage for Normal and Normal + Extreme,\n(4) [Figure 4](https://ibb.co/S488nwK6) – Coverage for Pareto and Pareto + Extreme.\n\nFrom Figures 1 and 2, we observe that QAE with $\\alpha_{QAE}=0.1$ produces the smallest prediction sets. However, when no extreme values are present, the choice of $\\alpha_{QAE}$ appears to have little impact. In contrast, when extreme values exist in the distribution, selecting $\\alpha_{QAE}=0.05$ significantly deteriorates the final prediction sets. This is expected, as the dataset is constructed such that 5% of the values are extreme. Consequently, QAE with $\\alpha_{QAE} = 0.05$ attempts to find $\\hat{f}$ that minimizes the error for these extreme values, which is the opposite of being \"robust.\" Figures 3 and 4 confirm that the calibration step ensures the final coverage remains close to 0.9. \n\nNotice that a similar sensitivity to $\\alpha$ can be observed in other conformal prediction methods, such as CQR, when the $\\alpha_{CQR}$ values for the quantile regressors are poorly chosen.", "claims_and_evidence": "The paper claims to contribute to the existing literature by deriving upper bounds on the size of split CP and proposing a training step for split CP aimed at minimizing the set size of prediction sets.", "methods_and_evaluation_criteria": "The problem is tested on synthetic data; it would be better to test it on actual benchmarks used in CP.", "theoretical_claims": "I haven't carefully checked the proofs but the results are coherent with existing ones.", "experimental_designs_or_analyses": "Experiments are carried out on simple synthetic data; however, the Appendix contains more extended evaluation.", "relation_to_broader_scientific_literature": "There is a quite a lot of missing literature. There already exists works that study the expected set size or informativeness of split CP in standard settings as well as under covariate shift.", "essential_references_not_discussed": "I believe that the current literature review misses many existing works.\n\nTo the best of my knowledge, the first paper to theoretically study the expected set size of CP sets was [1]. This paper studies the set size for different tasks, including the regression task considered here. It examines the expected size under a fixed predictor. This analysis has been extended to split CP, where the learner is not fixed but learned, both under the i.i.d. setting and covariate shift [2-3]. While these works have not proposed algorithmic solutions to minimize the expected inefficiency of CP sets, [4] and [5] proposes a training algorithm starting from the PAC-Bayes bound on the efficiency of split CP and information-theoretic tools.\n\n[1]. Dhillon, Guneet S., George Deligiannidis, and Tom Rainforth. \"On the expected size of conformal prediction sets.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n[2] Zecchin, Matteo, et al. \"Generalization and informativeness of conformal prediction.\" 2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024.\n[3] Zecchin, Matteo, et al. \"Generalization and Informativeness of Weighted Conformal Risk Control Under Covariate Shift.\" arXiv preprint arXiv:2501.11413 (2025).\n[4] Sharma, Apoorva, et al. \"PAC-Bayes generalization certificates for learned inductive conformal prediction.\" Advances in Neural Information Processing Systems 36 (2023): 46807-46829\n[5] Correia, Alvaro, et al. \"An information theoretic perspective on conformal prediction.\" Advances in Neural Information Processing Systems 37 (2025): 101000-101041.", "other_strengths_and_weaknesses": "I think the paper does a nice job of leveraging insights from theoretical results to propose a new training algorithm. The proposed methods seem to have advantages over existing ones. However, the paper overlooks many existing works, which I believe undermines its originality claims and experimental results. For example, how would the algorithms in [4]-[5] compare to EffOrt?\n\nFrom my understanding, when using EffOrt, one commits to a coverage level $\\alpha$, assuming that the same \\alpha will be used for calibration. However, standard CP is a post-hoc calibration method, and the training of the base predictor is independent of $\\alpha$. I suggest including experiments to evaluate the performance of EffOrt when $\\alpha$ at calibration time differs from the one used for training. In many instances, retraining a model is not feasible.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X3HnsNxMON", "reviewer": "Reviewer_jRxu", "summary": "The authors present a method that minimizes the volume of a conformal prediction region, subject to the coverage being the desired one (1- alpha). They show its theoretical properties, and its empirical validity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable feedback and for pointing out relevant related work. Below, we address each of their questions and comments.\n\n\n- *Q1 In https://link.springer.com/book/10.1007/b106715, Theorem 2.10, the authors provide a proof by construction, that can be used to derive the narrowest possible (in the sense of diameter or volume) conformal prediction region. How does the authors' work relate to that result?.* \n \nWe appreciate the reviewer for highlighting this result. After carefully examining Theorem 2.10 and its proof, we find that our work does not explicitly relate to it. From our understanding, the proof constructs a theoretical conformal set that is guaranteed to be at least as efficient as a given conservatively valid confidence predictor. However, it is not evident that this result can be leveraged to construct a conformal predictor of minimal size in practice. In contrast, our approach explicitly formulates and empirically solves the length minimization problem.\n\n- *Q2 In https://proceedings.mlr.press/v216/sale23a.html, the authors show that the volume is not a good measure for (epistemic) uncertainty for classification problems with more than 2 classes. How does this result compare with what the authors present in their paper?.* \n \nThe referenced paper differs significantly from our work. First, it does not explicitly address Conformal Prediction (CP) but rather focuses on credal sets as a means of quantifying uncertainty. Additionally, their analysis is centered on classification, whereas our work focuses on regression (extending to high-dimensional settings is left as future work by the authors). That being said, the authors do show that, in dimensions greater than two, measuring uncertainty through the volume of the credal set is inadequate—at least with respect to the axioms they propose (Section 3 of [1]). To draw a direct comparison between our work and the one mentioned by the reviewer, one would need to establish a precise connection between credal sets and conformal prediction and investigate whether the results in [1] extend to the volume of conformal prediction sets. We find this to be an interesting open question for further analysis of CP as an Uncertainty Quantification (UQ) technique.\n\n[1] https://proceedings.mlr.press/v216/sale23a.html\n\n- *Q3 Despite the ubiquitous claim that [...] for future research.* \n \nWe thank the reviewer for bringing these references to our attention. We fully agree that CP is better described as an uncertainty representation tool rather than a UQ technique, which is why we deliberately avoided making such a claim in our work. It appears that this comment, like the previous question, highlights a general limitation of CP rather than a specific limitation of our contribution. Nevertheless, we find that linking CP with more classical UQ frameworks (e.g., credal sets) presents an exciting research direction. We will mention this in the conclusion of our paper as a promising avenue for future work.\n\n- *Q4 It is also worth to notice that CP is not entirely model-free, since the volume (and diameter) of the resulting conformal prediction region depends on the choice of the non-conformity score. This was already pointed out in https://www.arxiv.org/abs/2502.06331. The authors are suggested to include this fact in their work.* \n \nWe fully agree with the reviewer, as this observation aligns with one of the conclusions of our paper: the choice of the prediction set class $\\mathcal{C}$, which depends on $\\mathcal{F}$ in Section 3, has a significant impact on the volume of the conformal prediction region. We will clarify this point in the final version of our manuscript and include a reference to the mentioned paper (noting that it was made available after the ICML submission deadline).", "claims_and_evidence": "The claims are clear and convincing. I'd like the authors, though, to address all my questions (see below).", "methods_and_evaluation_criteria": "The proposed evaluation criteria are apropos for the authors' goal.", "theoretical_claims": "The theoretical claims seem largely correct.", "experimental_designs_or_analyses": "The experimental designs and analyses seem sound and valid.", "relation_to_broader_scientific_literature": "The paper advances the state of the art on conformal prediction region methods, even though some related works are not considered. Please refer to the Questions section.", "essential_references_not_discussed": "Some references to known problems and results are missing. Please refer to the Questions section.", "other_strengths_and_weaknesses": "The paper is well-written, and studies an interesting problem. I gave it a score of 3, with the willingness to increase it if the authors are able to address the questions I raise.", "other_comments_or_suggestions": "Please refer to the Questions section.", "questions_for_authors": "**Q1** In https://link.springer.com/book/10.1007/b106715, Theorem 2.10, the authors provide a proof by construction, that can be used to derive the narrowest possible (in the sense of diameter or volume) conformal prediction region. How does the authors' work relate to that result?\n\n**Q2** In https://proceedings.mlr.press/v216/sale23a.html, the authors show that the volume is not a good measure for (epistemic) uncertainty for classification problems with more than 2 classes. How does this result compare with what the authors present in their paper?\n\n**Q3** Despite the ubiquitous claim that conformal prediction (CP) is an uncertainty *quantification* tool, it is actually not. CP is an uncertainty *representation* tool. Indeed, CP *represents* uncertainty via the conformal prediction region. It does not quantify it: there is no real value attached to any kind of predictive uncertainty (aleatoric or epistemic, AU and EU, respectively). Some claim that the diameter (or the volume, like in the authors' work) of the conformal prediction region quantifies the uncertainty, but even in that case, it is unable to distinguish between AU and EU. Indeed, the diameter (and the volume too) is a positive function of both: it increases as both increase, and hence it cannot be used to distinguish between the two. This was already pointed out in https://openreview.net/forum?id=4NHF9AC5ui. I'd appreciate a discussion by the authors on this matter. I also briefly mention that a recent paper merged CP with imprecise probabilistic tools to obtain a \"proper\" AU and EU disentanglement https://openreview.net/forum?id=L7sQ8CW2FY. The authors may find it interesting, and possibly useful for the discussion section and/or for future research.\n\n**Q4** It is also worth to notice that CP is not entirely model-free, since the volume (and diameter) of the resulting conformal prediction region depends on the choice of the non-conformity score. This was already pointed out in https://www.arxiv.org/abs/2502.06331. The authors are suggested to include this fact in their work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This paper theoretically studies the efficiency of prediction sets/intervals in the context of conformal prediction. In the case of split CP, the paper highlights the importance of the quantile absolute error (QAE) to reduce the set size at calibration phase, leading to two algorithms,
EffOrt and Ad-EffOrt. Reviewers agree that the paper does a nice job of leveraging insights from theoretical results to propose a new algorithm.
One critical concern is that the paper overlooks many existing works. The authors did a nice job in responding to reviewers' comments, leading to increased overall scores.
Decision: Accept (poster)