Volume Optimality in Conformal Prediction with Structured Prediction Sets
Authors: Chao Gao
Liren Shan
Vaidehi Srinivas
Aravindan Vijayaraghavan
Venue: ICML 2025 poster (2025)
Keywords: Conformal Prediction
Volume Optimality
Structured Prediction Sets
Primary area: general_machine_learning
TL;DR: This work provides conformal prediction methods with restricted volume optimality in both the unsupervised setting and the supervised setting.

Abstract: Conformal Prediction is a widely studied technique to construct prediction sets of future observations. Most conformal prediction methods focus on achieving the necessary coverage guarantees, but do not provide formal guarantees on the size (volume) of the prediction sets. We first prove the impossibility of volume optimality where any distribution-free method can only find a trivial solution. We then introduce a new notion of volume optimality by restricting the prediction sets to belong to a set family (of finite VC-dimension), specifically a union of $k$-intervals. Our main contribution is an efficient distribution-free algorithm based on dynamic programming (DP) to find a union of $k$-intervals that is guaranteed for any distribution to have near-optimal volume among all unions of $k$-intervals satisfying the desired coverage property. 
By adopting the framework of distributional conformal prediction (Chernozhukov et al., 2021), the new DP based conformity score can also be applied to achieve approximate conditional coverage and conditional restricted volume optimality, as long as a reasonable estimator of the conditional CDF is available. 
While the theoretical results already establish volume-optimality guarantees, they are complemented by experiments that demonstrate that our method can significantly outperform existing methods in many settings.

Volume Optimality in Conformal Prediction with Structured Prediction Sets
Chao Gao 1
Liren Shan
Vaidehi Srinivas
Aravindan Vijayaraghavan
Abstract
1. Introduction
Conformal inference has emerged as a powerful black-box method for quantifying uncertainty in model predictions, providing confidence sets prediction sets that contain the true value with a specified probability (Gammerman et al., 1998; Vovk et al., 2005). Consider prediction prob- lem where X' is the covariate space (feature space), and y is the label space. Given a dataset of n labeled samples (X1, Yi), (Xn. Yn) E X x 3, a conformal prediction algorithm uses these samples (often called calibration samples) construct for test Xn+1 X' with (unknown) true value Yn+1 E V, a prediction set that we will denote by C(Xn+1) y satisfying the coverage requirement for some desired parameter (0,
Conformal Prediction is a widely studied tech- nique to construct prediction sets of future ob- servations. Most conformal prediction methods focus on achieving the necessary coverage guaran- tees, but do not provide formal guarantees on the size (volume) of the prediction sets. We first prove impossibility of volume optimality where any distribution-fee free method can only find a trivial solution. We then introduce a new notion of vol- ume optimality by restricting the prediction sets to belong to set family (of finite VC-dimension)), specifically a union of k-intervals. Our main con- tribution is an efficient distribution-free algorithm based on dynamic programming (DP) to find a union of k-intervals that is guaranteed for any dis- tribution to have near-optimal volume among all unions of k-intervals satisfying the desired cover- age property. By adopting the framework of dis- tributional conformal prediction (Chernozhukov et al., 2021), the new DP based conformity score can also be applied to achieve approximate condi- tional coverage and conditional restricted volume optimality, as long as reasonable estimator of the conditional CDF available. While the theoreti- cal results already establish volume-optimality guarantees, they are complemented by experi- ments that demonstrate that our method can sig- nificantly outperform existing methods in many settings.
( E ((Xx+1)) 2 1 a.
(I)
Here the probability IP refers to the joint dis- tribution over all + pairs of observations (X1, Vi)...., (X,;: Yn), (Xn+1, Yn+1) including the test sample (Xu+1, Yn+1). Unlike traditional approaches, conformal inference is distribution-free, relying only on the assumption of exchangeability of the joint distribution IP over the (n + 1) samples.
While most conformal methods provide guarantees on coverage, they do not provide any control on the size volume of the prediction sets. In fact, the choice of Č(X,+1)) y also satisfies the coverage requirement. Consequently, the size of these sets is often validated empirically, without formal guarantees. This raises the important question of volume optimality, which is the focus of this paper:
Question: Given calibration samples (X1, Yi)........ (Xn,Y.) drawn i.i.d. from distribution P. we find among all data-dependent sets C c satisfying the desired coverage requirement for (Xn+1, Vn-1) P. the one with
'Equal contribution 'Department of Statistics, University of Chicago, Chicago, Illinois, USA 'Toyota Technological Institute at Chicago, Chicago, Illinois, USA 'Department of Computer Science, Northwestern University, Evanston, Illinois. USA. Correspondence to: Chao Gao <chaa- gao @ @cchicago.edu>> Liren Shan <lirenshan@ltic @itteneuui....>..... Vaidehi Srinivas <vaidchi n.northwestemmeduu Aravindan Vijayaragha- van <aravindy @ northwestemm.ddu.
may be more accurate to use Yi.,, Y........... Yn, Xa+1) instead of C(Xn+1) to re- flect that Ō is function of the calibration samples and Xa+1.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'Although conformal prediction ensures that the coverage prob- ability does exceed + 1/n, it does not prevent overly conservative predictions.

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
the smallest volume, as quantified by the Lebesgue measure vol(C)= = =XC)?
As long as C. has bounded VC-dimension, for any distri- bution P we can obtain good empirical estimates of the probability measure of any set C' E C via a standard uni- form concentration inequality, which allows us to overcome the impossibility result in Theorem 2.1. In the rest of the paper, we focus on the setting when y = IR and C = C which the collection of unions of k intervals.
The volume of the prediction set in conformal prediction is also sometimes referred to as 'efficiency" has been stated as an important consideration in many prior works (see e.g- Shafer & Vovk, 2008; Vovk et al., 2016; Angelopoulos & Bates, 2023). However, most works that we are aware of do not give theoretical guarantees of volume optimality, and mainly reason about volume control through empirical evaluations.
Conformalized Dynamic Programming. Equipped with our new notion of volume optimality, we propose new conformity score based on dynamic programming. The pro- posed method is shown to not only achieve approximate conditional coverage as in Chernozhukov et al. (2021) and Romano et al. (2019), but also conditional volume opti- mality with respect to unions of l: intervals, as long as a reasonable estimator of the conditional CDF is available. Our method of learning predictive set via CDF can be regarded an extension of the framework of Izbicki al. (2020); Chernozhukov et al. (2021).
There are few works that provide guarantees of volume opti- mality.² 3 Notable exceptions include Lei et al. (2013) in the unsupervised setting, Lei (2014); Vovk et al. (2016); Sadinle et al. (2016) in the classification setting, Lei et al. (2015) for functional data and recent works of Izbicki et al. (2020; 2022) and Kiyani et al. (2024) in the regression setting. As summarized by Angelopoulos et al. (2024), sufficient condition that leads to volume optimality of conformal pre- diction is consistent estimation of the conditional density function of Y given X. This is essentially the strategy adopted by previous work (Lei al., 2013; Izbicki et al., 2020; 2022). In comparison, our method, by incorporating a framework of Chernozhukov et al. (2021), builds the estimation of the conditional CDF via new conformity score computed by dynamic programming, and thus also works in settings where good conditional density estimation is impossible or density does not even exist.
1.2. Paper Organization
We will start with the unsupervised setting with label-only data in Section 2. The extension of the theory and algorithm to the supervised setting is given in Section 3. The numer- ical comparisons between our proposed methodology and existing methods in the literature are presented in Section 4. Due to the page limit, all technical proofs and additional numerical experiments will be presented in the appendix.
1.1. Our Results
2. Unsupervised Setting
An Impossibility Result. We first prove an impossibility re- sult in a one-dimensional setting where any distribution- method that satisfies the coverage requirement can only find trivial solution whose volume is sub-optimal. See Theo- rem 2.1 for formal statement. This result provides an planation for the lack of such volume-optimality guarantees in the conformal prediction literature, and also motivates our new notion of volume-optimality that we introduce in
2.1. Approximate Volume Optimality
Suppose YI, ... Yn, Yn+1 are independently drawn from a distribution P on R. The goal is to predict Yn+1 based on the first n samples Vi...., Yn- To be specific, we would like to construct a data-dependent set C = C( Yn) such that
this work.
P(Y,+1 E EO)
2 1 a.
(3)
Among all data-dependent sets that satisfy (3), our goal is to find the one with the smallest volume, quantified by the Lebesgue measure Col(C) = x()). When the distribution P is known, one can directly minimize X(C)), subject to P(C) 2 1 a without even using the data. In particular, when P & X, an optimal solution is given by the density
Structured Prediction Sets and Restricted Volume Opti- mality. Motivated by the impossibility result, our goal is to find prediction set C E C c 2 whose volume is com- petitive with the optimum volume of any set in the family C as given by
level set
(PT inf (vol(C) P(C) 2 1 1- a3. (2) Cee
Copt = {aP -
3 SSoe works also guarantee that the coverage is not much more
than 1 1-a a, e.g., P (Ya+1 E Ō((++1) Xa+1)
< 1 - a + o(1) to argue that the prediction set is not too big. However, smallness according to the measure F does necessarily reflect small
for some t > 0 and D is some subset of (dP/d> = =].
In general, P may not be absolutely continuous and the density need not exist. Nonetheless, we can still define the
volume (or Lebesgue measure) for the set.
2

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
optimal volume by
be established in distribution-free way. Perhaps not sur- prisingly, this goal is too ambitious. The theorem below rigorously proves the impossibility of the task. The detailed proof is deferred to Appendix D.1.
OPT(P,1 - inffvll( PPC) 2 a).
Note that without any assumption on P. the above optimiza- tion problem may not have a unique solution. Moreover, is possible that the infimum cannot be achieved by any measurable set. Therefore, a natural relaxation is con- sider upproximate volume optimality. For some E (0, a),
Theorem 2.1. Consider observations Y1. Y2. Yn. Yn+1 sampled i.i.d. from distribution P on R. Suppose C C(Y,..... .Y)) satisfies P(Y,+1 E C. 2 1- for all distribution P. Then, for any E (0, a), there exists some distribution P on R. such that the expected volume of the prediction set is at least
a prediction set C is called c-optimal if
vol(Ō) & -
(4)
E vol
-.)
either in expectation or with high probability.
The above impossibility result can be regarded as a conse- quence of a nonparametric testing lower bound. Consider the following hypothesis testing problem,
The notion of volume optimality defined by (4) is quite dif- ferent from those considered in the literature. A popular quantity that has already been studied the volume of set difference vol (psCopt) (Lei et al., 2013; Izbicki et al., 2020; Cheroohukkv et al., 2021). However, this much stronger notion requires that the optimal solution Copt must not only exist but also be unique. Usually additional as- sumptions need to be imposed the neighborhood of the boundary of Copt in order that the set difference vanishes in the large sample limit. In comparison, the definition (4) only requires the volume to be controlled, which can be achieved even if Ò is not close to Copt. or when Capt does not even exist. Indeed, from a practical point of view, any set with coverage and volume control would serve the purpose of valid prediction. Insisting the closeness to a questionable target Cpt comes at the cost of unnecessary assumptions on the data generating process.
Ho: :
P H1: PE
It is well known that testing procedure with both vanish- ing Type-1 and Type-2 errors does not exist without fur- ther constraining the alternative hypothesis, even when 5 is arbitrarily close to 0 (LeCam & Schwartz, 1960; Barron, 1989). In the setting of distribution free inference with si- multaneous coverage and volume guarantees, two different probability measures naturally arise. The coverage guaran- tee is defined with respect to the joint distribution p=+1, which governs the full dataset of training samples and one test point. In contrast, the expected volume of the predic- tion set is measured under the product distribution pa @ X, where pm represents the joint distribution of n training sam- ples. When restricting the support of P to the unit interval [0, 1]. becomes the uniform probability, and thus both p=+1 and p" @ X are probability distributions. It turns out achieving approximate volume optimality is related to hypothesis testing between pa+1 and pn @ À with total variation separation.
Another notion considered in the literature is close to our formulation (4). Instead of relaxing the coverage probability level from a to - a tE one can consider the following approximate volume optimality,
vol(Ō) s OPT
(5)
Results of interval length optimality in the sense of (5) have been studied by Chernozhukov et al. (2021); Kiyani et al. (2024). However, the e in (5) is usually proportional to the scale of the distribution P. or may depend on in some other ways. In comparison, the bility, and as we will show later, can be made independent of the distribution P, which leads to more natural and cleaner theoretical results with fewer assumptions.
2.3. Distribution-Free Restricted Volume Optimality
The impossibility result implies volume lower bound OPT 1 a + E), where the coverage level 1 - a + e can be arbitrarily close to 1. This means that, at least in the worst case, the volume cannot be smaller than that of the support of
(4) has the unit of proba-
To avoid this triviality, in this section, we consider a weaker notion of volume optimality by only considering prediction sets that are unions of & intervals. We use Cs to denote the collection of all sets that are unions of k intervals. The restricted optimal volume with respect to the class C₁ is defined by
2.2. Impossibility of Distribution-Free Volume Optimality
It is known that conformal prediction achieves the cover- age property (3) in a distribution- sense, meaning that (3) holds uniformly for all distributions P. One naturally hopes that the approximate volume optimality (4) can also
OPT inf (vol(C): :PC) 2 1--a) -aj. (6)
CEC,
3

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Remark 2.2. We remark that we are still in a distribution- free setting, since assumption is imposed on P. Instead, the restriction only constrains the shape of the prediction set. From a practical point of view, it is reasonable to require that C E Cs. since a more complicated prediction set would be hard to interpret. Moreover, as long as P admits a density function with at most modes, the two notions match,
Algorithm Dynamic Programming Solving (7)
1: Input: data points .i...., Yn E R. coverage level
1-a E (0, 1) and slack 7 E (0, a)), number of intervals k
2: Output: k intervals that cover [(1 - a)) points with minimum volume
Sort data in non-decreasing order Y()) .... ....5 <Y())
Set (.. oo for all i [k].] j E [n].1 [1/h]
OPT&(P,1 a) -
to n. 1 = 1 to [1/7] do 6: for i do
5: for i = 1 to k.
More generally, it can be shown that
7:
to j' - do for =i - ji
OPT - a) I OPT(P,1--- +e)).
8:
Set -' = [(j -j 4/+10 10i--1+1)/mm0 [mm]]
9:
if < 0 and i == then
for some E E (0, a). whenever P can be approximated by a distribution with most i modes. This, in particular,
10:
Di(i,,,1 min(DP(i....) - -Ym) end if
11:
includes the situation where the density of P can be well es- timated by kernel density estimator. A rigorous statement will be given in Appendix C.
12:
if DP(i-1,5" 1,)", then DP(i, min - Yon DP(i - DP(i-1,,"",1)
13:
end if 15: end for
14:
Given the observations YI,... Yn we define the empiri- cal distribution P,, n Σx=1 8y, To achieve restricted volume optimality, one can use
16: end for
17: end for
18: Find the minimum volume among all DP j. [(L
Ö = argmin :P.))))))(C)))))))))) CEE,
a)/?1) for j = 1, ,,..., and backtrack to construct the prediction set Cpr.
According to its definition, the prediction set (7) satisfies both (C) 2 1 - a and CC) = ( - ar). The coverage and volume guarantees under P can be obtained via
19: Return the CDP.
Proposition 2.3. For any Y E [1/n, a), Algorithm 1 com- putes a prediction set CD E C2 by dynamic progrumming with time complexity O(1²k) ((/2)//7)) such that
Pr (VVClC)/) (8)
(C) - = CEC₂
sup
1. IP (CDP) 2 - aF
with VC(C) Ok)) Therefore, approximate optimality can be achieved by (7) whenever (8) holds.
2. vol(Cnr) - OPTx a++a)) +7). 7).
A naive exhaustive search to find (7) requires exponential computational time. We show that an efficient dynamic programming algorithm (Algorithm 1) can solve (7) approx- imately with some additional slack 7 E [I/n,a), which controls the trade-off between volume approximation accu- racy and the computational complexity.
Together with (8), the coverage and volume guarantees of the dynamic programming can also be generalized from P., to P.
2.4. Conformalizing Dynamic Programming
The dynamic programming table D) stores the minimum volume of i intervals that cover lyn points in Yu),...,Y Yu) and the right endpoint of the rightmost inter- val is at Yog. where Y(I)...., M(n) are training data points Yi,... Yn sorted in non-decreasing order. For each state in DP table, we enumerate all possible left endpoint of the rightmost interval and the right endpoint of the previous interval (if it exists). After filling the table, standard back- tracking procedure is used to construct the final prediction set CDP.
Having understood the generalization ability of dynamic programming, we are ready to conformalize the procedure to achieve a finite-sample coverage property. For simplicity, we will adopt the framework of split conformal prediction, though in principle full conformal prediction can also be applied here.
In the split conformal predicition framework, the data set is split into two halves. The first half is used to compute a conformity score, and the second half determines the quantile level. For convenience of notation, let us assume, from now on, that the sample size is 2n. The split conformal procedure outlined below.
Theoretical guarantees of Algorithm are given in the fol- lowing proposition.
4

---

Volume Optimality in Conformal Prediction with Structured Prediction Sets
1. Compute score function q(+) using "1,"",, Yn-
in the prediction set. Applying the standard split conformal framework, our prediction set based conformalized dy- namic programming is defined by (9) with the conformity score (10).
2. Evaluate ((Y++1), .M. .((Yn)), and order them as
q1 S .... S 9n-
3. Output the prediction set
observations ",,'.. Y2a, Y25+1 generated by some distribution
Theorem 2.5. Consider i.i.d.
Č = {u u(v)> 2 [[m+t)aa
(9)
P on R. Let CCP-DP be the split conformal prediction set defined by the score (10) based on nested system {Sj]je(m) satisfying Assumption 2.4. Suppose the parame-
By the exchangeability of 1n+1."., Yens Y2 the pre-
diction set C satisfies
ter 8 in Assumption 2.4 satisfies > following properties hold.
v |ktlog
Then the
n
(22+11 E ē 21-a,
where the above probability is over the randomness of (Y,,--- .Y.,, that of (Yn41,"" Y, and that of 22
1. Coverage: P (Yzn+1 E CCP-DP) 2 21-a a.
Restricted volume optimality:
To conformalize the dynamic programming that approxi- mately computes (7), we will first compute a nested system S C... C Sm, C R using the data YI,.. .Y., The nested system required to satisfy the following assumption.
vol(Ccp-DP) I OPT (P, a + 4 + +8 with probability at least 26.
We emphasize that Theorem 2.5 guarantees both distribution-fee coverage and distribution-fies volume op- timality properties. practice, k is usually chosen to be a constant for prediction interpretability. By setting
Assumption 2.4. The sets S C... C Sm C R are mea- surable with respect to the o-iilld generated by Y1, Yn- ,y.
Moreover, for some positive integer ki, some (0,1) and some 6, y such that 35 +
a. we have
==
log
the volume sub-optimality is at most
1. P,,( j. and S, C₁ for all j [m]. mn
(V
1 "
+ 48 + 0
logn
2. There exists some j" E [m], such that (S,() 2 1 - a + + + 36 and vo S (P - a + 36 + 7).
3. Supervised Setting
3.1. Problem Setting
Here, Pn denotes the empirical distribution the first half of the data.
Ei oy, of
In this section, we consider conformal prediction with labeled data. Suppose data points (X1, xi)..... (X2ns (X, bution P on X' x xY with y = R. Using the first 2n samples, our goal is to compute a prediction set ((x) for each æ X. We will study the following properties for the prediction set.
To construct a nested system (Sijetm, that satisfies the above assumption, one only needs to make sure that there exists one subset S,- in the system that computed by the dynamic programming (Algorithm 1) with confidence level
are i.i.d. drawn from distri-
35 and slack parameter y. The rest of the sets in the system can be constructed just to satisfy (S,) = 2. In Section 4.1, we will present greedy m expansion/contractio algorithm that satisfies Assumption 2.4.
1. Marginal Coverage:
IP (Yen+1 E ((Xee+1)) 2 1 - a,
With a nested system {5y)şemm satisfying Assumption 2.4, we can define the conformity score
where the probability IP is jointly over all 2n + pairs of observations.
2. Conditional Coverage:
(vv) = Σ 1 E St}.
(10)
P PYaatt ((X2n11) (2nt1) 2 a, (11)
The equivalence between nested system and conformity score was advocated by (Gupta et al., 2022). Intuitively, q(y) quantifies the depth of the location A higher score implies that y is covered by more sets in the nested system, and thus the location should be more likely to be included
with high probability.
It is well known that the conditional coverage property can- not be achieved without additional assumptions on P (Vovk,
5

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
2012; Lei & Wasserman, 2014; Foygel Barber al., 2021).
2021) that asymptotic conditional coverage also holds. How- ever, in general, CDcr-(X2+)) (X2n+1) is not optimal in terms of its volume. A modification was also proposed in (Cher- nozhukov et al., 2021) to achieve volume optimality within the class of intervals. Though not explicitly stated in (Cher- nozhukov et al., 2021), we believe that the DCP procedure essentially achieves (12) for = 1. Our goal is to achieve the conditional restricted volume optimality for a general k by combining the ideas of DCP and dynamic programming (DP).
Therefore, some form of relaxation of (11) is necessary.
In addition to the coverage properties listed above, we will also extend the notion of restricted volume optimality (6)
from the unsupervised setting to the supervised setting. De- fine the conditional CDF by
Fly x) = P (Y2n+1 y X2n+1 = =))
The conditional restricted optimal volume is given by
OPT2 (F(. xx)11_11) aa)
3.3. DCP meets DP
=inf vol((): inf(volCC): : S( dF(- | (z))==1 (CC)
To achieve (12) for a general k we will modify the DCP pro- cedure by considering different conformity score that gen- eralizes (10) to the supervised setting. Recall that Fly x) is an estimator of the conditional CDF, and it is computed from the first half of the data (1), first step is to construct a nested system for each æ E X. To be specific, for each æ E X' we will construct collec- tion of sets (1) [E(] based the function F(. xt). The requirement of the nested system is summarized the following assumption.
With this definition, we can list the following volume re- quirement.
(X,,, Y.). Our
3. Conditional Restricted Volume Optimality:
vol(((X2n+1)) OPT (F(-IX2nt1);11 - a E)), (12)
with high probability, for some E (0,
The sets (zx) C C... C (m(( C R are measurable with respect to the o-field generated by F(- x)) Moreover, for some positive integer k, some a E (0, 1) and some 5, y such that 35 + 7 + n S a, we have
Assumption 3.1.
Similar to the conditional coverage property (11), the con- ditional restricted volume optimality (12) is only required for a typical value of the design point. We will show that based on an extension of distributional conformal prediction (Chernozhukov et al., 2021), these two properties can be achieved under the same assumption.
1. Ss,(o) dF(- ())
i and S E C. for all j E [m]- m
2. There exists some j* E [m]. such that
3.2. Distributional Conformal Prediction
f s,((x)
aF(- x) 1 1- an
Conformal prediction based on estimating the conditional CDF has been considered independently by (Izbicki et al., 2020; Chernozhukov et al., 2021). We will briefly review the version by Cheroozuukov et al. (2021), and then extend to serve our purpose. Suppose Fly x²) is an estimator of the conditional CDF, which is computed from the first half of the data Yi), (Xn, Yn). The prediction set proposed by Chernozhukov et al. (2021) is
and vol(S)))) - OPTT x), 1 a 36 + 77). #6
The construction of nested systems satisfying Assumption 3.1 is similar to that in the unsupervised setting. That is, one can apply dynamic programming (Algorithm 1) and obtain ())(x), and the rest of the sets can be constructed via the greedy expansion/connraction procedure described in Section 4.1 satisfy Jss(a) d' x)) 1. The main difference here is that Algorithm 1 is directly applied to the data in the unsupervised setting, while we only have access to F(- x) in the supervised setting. This issue can be easily addressed by computing quantiles (I),,... (2(x) from F( I) on grid, and then apply Algorithm I with (z), (z()) as input. Indeed, since the distance be- tween F( x) and F( x) can be controlled by the size of the grid with Fly x)) = E'=, (x)(x) S y). Assump- tion 3.2, which will be stated later in Section 3.4, is also satisfied by Fly z) (with a slightly larger value of 6) by triangle inequality.
1 CDer(Xan+1)+ = { E R: F(y) X2n+1) -
<7
2
where fis an appropriate quantile of
F(Yut Xn+1) - 1 1 2 :0""
F(Y22))
Xzn) - 2/1
Since ÜDCP(X2n+1) is in the form of split conformal pre- diction, the marginal coverage property is automatically satisfied. When Fly x) is close to Fly | x) in some appropriate sense, it was proved by (Chernozhukov et al.,
6

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
The computational cost of constructing (E)mm) for single E X' is ((T²k/7). Note that there is no need to repeat the construction for each indi- vidual E X. Since the split conformal frame- work only requires evaluating the conformity score at (Xa+1, Xa+1),-. (..,)....... (X2zn Xzn), (X2n+11 v), is sufficient to compute (S, (X.)) for = n+1, ...... 2n+1, 1, which leads to the total computational cost ((nL*k/7).
Approximate conditional coverage,
IP (Yoni E CDCPP -ppp--Dpde -Dp---Pp(PP (2p(Xxm1))) 21-0-36,
with probability at least 1 8.
3. Conditional restricted volume optimality,
vol (CDer-Dr br((xx++))
With nested systems satisfying Assumption 3.1, the confor- mity score in the supervised setting is defined as
SOPT [F() X2n+1), -x + 1 + 48 +7).
(y,xx) E Hy S,(x)).
with probability at least 1 25.
Let 21 ... S On be the order statistics computed from the
Note that the marginal coverage does not depend on ō, which reflects the estimation error of the conditional CDF in As- sumption 3.2. Therefore, the marginal coverage guarantee always holds and does not rely on Assumption 3.2. Theo- rem 3.3 can be regarded as generalization of Theorem 2.5. Indeed, when F(- x)) does not depend on x and F( x)) is defined as the empirical CDF of YI.... Yn. Theorem 3.3 recovers Theorem 2.5. Moreover, since the volume optimality is over all sets that are unions of k intervals, it also covers the length optimality of intervals considered by (Chemoozukkv et al., 2021). The case k 2 2 will be impor- tant if the conditional density of Y given X has multiple modes; Gaussian mixture a leading example.
set
{g(Xn+1, Yn+1), ... : 2((2n, Y2n))- The prediction set for Y2 is constructed as
DOCP-DP(X2n+11) {y= aly, X2n+1) 2 [((+1)aa]
3.4. Theoretical Guarantees
satis- fies marginal coverage. Moreover, when Fly) z) is close to Fly 2)) in some appropriate sense, it also satisfies ap- proximate conditional coverage and conditional restricted volume optimality. Given two CDFs F and F, we define the (k, oo) norm of the difference by
We will show in this section that
4. Numerical Experiments
|| 1T-FFle, Fl
sup | dF
da- dF
We complement theoretical guarantees with evalu- ation of our methods for both the unsupervised setting of Section 2 and the supervised setting of Section 3.
CEC.
Assumption 3.2. The estimated conditional CDF Fly) xx) satisfics
4.1. Construction of Nested Systems
PP (1 (22+1) - F(: X2m+1)lls,cs <6) 2 1 5,
We first describe procedure that generates nested system {Sj Jemi that satisfies Assumption 2.4. The construction involves the following steps:
where 5 takes the same value as the one in Assumption 3.1.
The theoretical properties of DOcC--DD(X2nt1 are given by the theorem below.
Generate Sy- by Dynamic Programming. For j [(1 + n + 35)m], generate Sy- by ap- plying Algorithm 1 with coverage level 1 j /m and slack = 1/m. The discretization level m and statistical tolerance are chosen as m = 50 and 8 V(k + logn)/n, /n," where k is the number of inter- vals in the prediction set.
Theorem 3.3. Consider i.idd observations (X1, Yi),
(X2n, Yen), (X2n41, Y2n41) generated by some dis- tribution P on X R. The conformal prediction set
is computed from nested systems (S)())m and F(- 1) satisfying Assumption 3.1 and Assumption 3.2. Suppose the parameter 8 in the two assump- tions satisfies 82 log(2/m) Then the following properties hold.
2. Generate Sy.+1,'.. Sm by Greedy Expansion. For each j > j", we iteratively identify the closest un- covered data point to the boundary of the current k
2n
1. Marginal coverage,
*We can choose m E (1/a, n), where larger m yields finer discretization of the nested system. The parameter 8 reflects the statistical error in estimating the (conditional) CDF.
PP (Yaanti E CDCP-DP Dr (P(22-1)) 21 21-a

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
intervals and expand the nearest interval cover it. Once the intervals cover [jn/m] data points, we de- fine the union as Sj and move on to the construction of SJ+1.
given by [KDB(2) = dp Ei= y-Y;
K
where (-)) is
up
the standard Gaussian kernel and p is the bandwidth param- eter. Both methods involve a single tuning parameter, & for conformalized DP and p for conformalized KDE.
3. Generate Si, SS.....,S..11 .S..- by Greedy Contraction. For each < j", iteratively remove boundary point of the current k intervals that results in the maximum volume reduction. Once the intervals after contraction cover exactly [jn/m]] data points, we define the union as S3 and move on to the construction of S3-1-
Figure 1, Tables 1 and 2 summarize the results using data generated from a mixture of Gaussians j NN 0.0001) + 3 [N, 1) + 3 (8, 0.25). We report the mean and standard deviation of the results over 20 independent runs. Additional experiments on other distributions, including standard Gaus- sian, censored Gaussian, and teLU-transformed Gaussian, will be presented in Appendix B.
In the supervised setting, the above procedure will be ap- plied to quantiles Y1 (z),... ... (Y((a) computed from F(- r) with L = m for all a E {X=+1," ).
Table I. Conformalized KDE on the mixture of Gaussians data
4.2. Comparison in Unsupervised Settings
Bandwidth
Volume
Coverage
0.01
3.8929 + 0.2504
0.7899 = 0.0258
0.25
3.8747 0.2673
0.7963 # 0.0231
175
Prediction Set
Prediction Set
0.5
4.3663 + 0.3388
0.7938 = 0.0244
Frequencs
Density
0.75
4.7162 + 0.3681
0.7931 = 0.0224
0
4.9462 + 0.5119
0.7933 + 0.0231
600
055
50
75
ido
Data Value
Data Value
(a) The histogram of the dataset and the prediction set given by conformalized DP with le intervals (The first interval is at [-6.03,- -5.97].) The volume of the prediction sets 3.1438.
(b) The kernel density estimation with handwidth p = 0.25 and the prediction set given by conformalized KDE (Lei et al., 2013). The volume of the predie- 3.7944.
Table 2. Conformalized DP on the mixture of Gaussians data
k
Volume
Coverage
13.9017 + 0.1112
0.7947 # 0.0309
Prediction Set Valume
Prediction Volume
Optimal Volume (3 73.01781
Optimaal Volume (3.00 33.0188)
7.5980 0.2159
0.7883 0.0373
20.
3.1888 0.3403
0.8024 0.0356
4
3.3459 0.3003
0.8174 + 0.0278
12
5
3.4250 + 0.3818
0.8202 + 0.0306
25
Number of Intervals (c)
Bandwidth (p)
(c) Volumes of prediction sets by confor-
(d) Volumes prediction sets by confor. malized KDE is highly sensitive to the choice of p.
malized DP is not sensitive to the choice of k.
The two methods are also evaluated on two real-world datasets (Acidity and Enzyme) used in density estimation literature (Richardson & Green, 1997). The experiments target a coverage level of 0.8. We report the means and standard deviations of the results over 50 independent runs. As shown in Tables 3 and 4, our conformalized DP outputs smaller volume prediction set than the conformalized KDE with the best bandwidth for almost all h 2 2. The results for the Enzyme dataset are given in Appendix B.
Figure 1. Conformal prediction sets the mixture of Gaussians data from P = 1 (N((-6, 0.0001) + (O,, 1)+ NS, 0.25). The target coverage is 0.8. The theoretically optimal volume for this target coverage is 3.0178.
The algorithm in Section 2 is compared against the method based on kernel density estimation due to Lei et al. (2013) and evaluated on several different distributions. Though the original conformalized KDE was proposed in the full conformal framework, we will consider its split conformal version for direct comparison. We believe the comparison between the full conformal versions of the two methods will lead to the same conclusion. For the conformalized DP method, the conformity score is constructed based on the nested system described in Section 4.1. The conformalized KDE is also in the form of (9), with the conformity score
Table 3. Conformalized KDE on Acidity Datasct
Bandwidth
Volume
Coverage
0.1
2.4927 # 0960
0.8401 + 0.0226
0.3
2.3934 # 0.2044
0,8092 = 0,0261
0.5
2.5749 + 0.2571
0.8133 + 0.0315
0.7
2.7617 + 0,2038
0,8013 + 0.0256
0.9
2.8196 + 0.2587
0.8021 + 0.0294
8

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
intervals. However, since these methods rely on consistent estimation of the conditional density, conformalized DP still produces prediction sets with smaller volumes. The comparison is more pronounced on the first dataset (see Figure and Table 5), where it would be inappropriate to as- sume a smooth conditional density, but our method is based on conformalizing the estimation of conditional CDE, and thus works in much more general settings. Table 6 shows results where the conditional density is smooth and can be accurately estimated, favoring density-based methods. Even in this case, the conformalized DP with k = 2 is still competitive against CD-split and HPD-split.
Table 4. Conformalized DP on Acidity Dataset
k
Volume
Coverage
1
2.5999 + 0,1937
0.8121 + 0.0476
2
2.3627 = 0.1755
0.8507 = 0.0224
3
2.4099 # 1812
0.8552 # 0.0245
4
2.3615 = 0. 0.1452
0.8582 = 0.0196
5
2.2172 + 0.1349
0.8341 = 0.0253
4.3. Comparison in Supervised Settings
The algorithms for the supervised setting are compared against conformalized quantile regression (CQR) (Romano et al., 2019), distributional conformal prediction methods (DCP-QR and DCP-QR*) of Chernozhukov et al. (2021), and CD-Split and HPD-Split methods (Izbicki et al., 2022) against benchmark simulated datasets in Romano et al. (2019); Izbicki et al. (2020) (Figures 2 and 3). The imple- mentation details of all methods given in Appendix B.
Table S. Comparison on simulated data in Romano al. (2019).
Method
Average Volume
Coverage
CQR
1.4237 0.0743
0.7036 0.0146
DCP-QR
1.4218 0.0647
0.7021 + 0.0100
DCP-QR*
1.8854 = 0.9772
0.7054 = 0.0124
CD-split
1,7118 = 0.1934
0.6330 + 0.0166
HPD-split
1.7557 = 0.1115
0,6874 + 0.0165
C-DP (k=1)
1.0897 = 00.0792
0.7119 = 0.0171
dbarrstoon
Ooea verdary
Interve
C-DP (k=5)
0.4660 0.0218
0.7152 0.0177
Table 6. Comparison on simulated data in Izbicki al. (2020).
Method
Average Volume
Coverage
CQR
4.0428 = 0.0992
0.7060 + 0.01
DCP-QR
3.9933 0.0854
0.6987 + 0.0160
Figure 2. Results in the supervised setting on a synthetic data from Romano et al. (2019) for target coverage 0.7. The left plot shows the output of DCP-QR*, the state of the art method by Cher- nozhukov al. (2021), which outputs prediction sets with average volume 1.29 and empirical coverage 0.7106. The right plot shows the output of our method with k intervals, which achieves a significantly improved average volume of 0.45 with empirical coverage 0.7236.
DCP-QR*
4.0701 0.1141
0.7004 + 0.0162
CD-split HPD-split
3.6320 = 0.1126
0.7002 = 0.0161
3.6084 = 0.1121
0.7014 0.0133
C-DP (k 1)
4.1450 + 0.1150
0.7126 + 0.0165
C-DP (k = 2)
3.6774 + 0.1298
0.7152 + 0.0138
5. C.nnclusio
IPO stavia
We study conformal prediction with volume optimality in both the unsupervised setting and the supervised setting, by proposing a new conformity score computed via dynamic programming. In the supervised setting, when consistent estimation of the conditional CDF is available, we prove that the proposed method not only achieves conditional cov- erage, but the output of prediction set also has approximate conditional volume optimality with respect to the class of unions of k intervals.
2.5
2.0
-00
2.5
Figure 3. Results in the supervised setting on a synthetic data with 20 dimensional feature from Izbicki et al. (2020) for target cov- erage 0.7. The left plot shows the output of HPD-Split method by Izbicki et al. (2022), with average volume 3.60. The right plot shows the output of our methad with A = 2 intervals, which has an average volume 3.55.
Our method is especially suitable to settings where the data generating process is multi-modal has mixture structure. The numerical experiments show that the performance of the method is quite insensitive to the choice of k; whenever it is not smaller than the number of modes of the distribution. For future work, it would be interesting to study restricted volume optimality in more general response settings and under other notions of coverage in conformal prediction.
As shown in Tables 5 and 6, our method outperforms previ- ous methods by outputting prediction sets that are unions of intervals. Among all other methods, the CD-split and HDP- split (Izbicki al., 2020) are also able to produce unions of

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Acknowledgments
Chernozhukov, V., Wüthrich, K., and Zhu, Y. Distribu- tional conformal prediction. Proceedings of the National Academy of Sciences, 118(4)))22107794118 2021.
This research project was supported by NSF-fuuded Institute for Data, Econometrics, Algorithms and Learning (IDEAL) through the grants NSF ECCS-22 2222221677 16970 and ECCS-22169) 1221612 The research started part of the IDEAL special program on Reliable and Robust Data Science. Chao Gao was sup- ported by NSF Grant DMS-2310769 and an Alfred Sloan fellowship. Vaidehi Srinivas was supported by the North- western Presidential Fellowship. We also acknowledge the support of the NSF-Simons SkAl institute and the NSF- Simons NITMB institute, and thank Rina Barber and Jing Lei for helpful discussions.
Devroye, L. and Lugosi, G. Combinatorial methods in density estimation. Springer Science Business Media, 2001.
Dhillon, G. S., Deligiianiiis, 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.
Foygel Barber, R., Candes, E. J., Ramdas, A., and Tibshirani, R. J. The limits of distribution free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455 482, 2021.
Impact Statement
This paper presents improved methods for quantifying un- certainty in predictions produced by a machine learning algorithm. Such conformal prediction methods can make machine learning models more reliable by providing valid confidence sets or prediction sets. This has potential for positive societal consequences when accurate estimates of uncertainty are useful in making more informed and reliable downstream decisions.
Gammerman, A., Vovk, V., and Vapnik, V. Learning by transduction. In Proceedings of the Fourleenth Confer- ence on Uncertainty in Artificial Intelligence, 9AI'98, pp. 148-155, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.
Ghosal, S. and van der Vaart, A. Posterior convergence rates of dirichlet mixtures at smooth densities. Annals of Statistics, 35(2):697-723, 2007.
References
Gupta, C., Kuchibhotla, A. K., and Ramdas, Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496, 2022.
Angelopoulos, A. N. and Bates, S. Conformal prediction: A
gentle introduction. Found. Trends Mach. Learn., 16(4):
494-591, March 2023. ISSN 1935-8237. doi: 10.1561/ 2200000101. URL https:: /dt::///oii/// wwg.oogg//...... 1561/ 2200000101.
Izbicki, R. and Lee, A. B. Converting high-dimensional regression to high-dimensional conditional density esti- mation. Electronic Journal of Statistics, 1 11:2800-289 2831, 2017.
Angelopoulos, A. N., Barber, F., and Bates, S. Theoreti- cal foundations of conformal prediction. arXiv preprint arXiv:2411.11824, 2024.
Izbicki, R., Shimizu, G., and Stem, R. Flexible distribution- free conditional predictive bands using density estimators. International Conference on Artificial Intelligence and Statistics, pp. 3068-301 -077. PMLR, 2020.
Bai, Y., Mei, S., Wang, H., Zhou, Y., and Xiong, C. Efficient and differentiable conformal prediction with general fune- tion classes. In International Conference on Learning Representations, 2022.
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.
Barber, R., Candès, E., Ramdas, A., and Tibshirani, R. Con- formal prediction beyond exchangeability. The Annals of Statistics, 51, 04 2023. doi: 10.1214/23-A052276
Barber, R. F., Candes, J., Ramdas, A., and Tibshirani, J. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507, 2021.
Kim, B., Xu, C., and Barber, R. Predictive inference is free with the mecknnffe--afeerboottsrr Advunces in Neural Information Processing Systems, 33:4138-4149 2020.
Barron, A. R. Uniformly powerful goodness fit tests. The Annals of Statistics, 107--1407- 1989.
Kiyani, S., Pappas, G., and Hassani, H. Length optimization in conformal prediction, 2024. URL https: //axxiv..vvv/ org/ / abs 2400 18814.
Murreia-PPeppinaa M. A. and Williams, C. K. On the num- ber of modes of a gaussian mixture. In International Conference on Space Theories in Computer Vision, pp. 625-640. Springer, 2003.
Kruijer, W., Rousseau, J., and van der Vaart, A. Adaptive bayesian density estimation with location scale mixtures. Electronic Journal of Statistics, 4:1225-1257, 2010.
10

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Kumar, B., Lu, C.-C., Gupta, G., Palepu, A., Bel- lamy, D. R., Raskar, R., and Beam, A. L. Confor- mal prediction with large language models for multi- choice question answering. ArXiv, abs/2305.18404, 2023. URL
Shafer, G. and Vovk, V. A tutorial conformal predic- tion. Journal of Machine Learning Research, 9(1))371 421, 2008. URL http:// http:///mmmrrrrtee/eeeeeeeeeeeee www.rorrg//..o.......oo..oo.oooa weagg/apers//ve s shafer08a, html.
Stutz, D., Dvijotham, K. D., Cemgil, A. T., and Doucet, A. Learning optimal conformal classifiers. In In- ternational Conference Learning Representations, 2022. URL httpp:://ppeeeeeeeeeeee id=t80-41AM 4LKFVX.
xtt/CozpusID:2589677
LeCam, L. and Schwartz, L.
A necessary and sufficient condition for the existence of consistent estimates. The Annals of Mathematical Statistics, 31(1):140-150, 1960.
net. /orum?
Lei, J. Classification with confidence. Biometrika, 101 755-769, 2014.
Vovk, V. Conditional validity of inductive conformal pre- dictors. In Asian conference on machine learning, pp. 475-490 PMLR, 2012.
Lei, J. and Wasserman, L. Distribution-fre free prediction bands for non-parametric regression. Journal of the Royal Sta- tistical Society Series B: Statistical Methodology. 76(1): 71-96, 2014.
Vovk, V. Cross-conformal predictors. Annals of Mathemat- ics and Artificial Intelligence, 74:9-28, 2015.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learming in a Random World. Springer- ppringer-Verlag, Berlin, Heidelberg, 2005, ISBN 0387001522.
Lei, Robins, J. M., and Wasserman, L.. A. Distribution- free prediction sets. Journal of the American Statistical Association, 108:278- - 287, 2013. URL https://aa/aa semanticscholes org azgg/CorpsIID:: 17499899.
Vovk, V., Fedorova, V., Nouretdinov, I., and Gammerman, A. Criteria of efficiency for conformal prediction. In Confor- mal and Probabilistic Prediction with Applications: Sth International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 5, pp. 23-39. Springer, 2016.
Lei, J., Rinaldo, A., and Wasserman, L. A conformal pre- diction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74:29-43, 2015.
Liang, R., Zhu, W., and Barber, R. F. Conformal prediction after efficiency-oriente oriented model selection, arXiv preprint arXiv:2408. 07066, 2024.
Vovk, V., Nouretdinov, I., Manokhin, V., and Gammerman, Cross-conformal predictive distributions. conformal and probabilistic prediction and applications, pp. 37-51. PMLR, 2018.
Meinshausen, N. Quantile regression forests. Jour- nal of Machine Learning Research, 7(35):983-99) 2006. URL http:// jmlr. caamlr.rrr//ooooo pttpg/ppprs/////// meinshausenO6e .hmm..
Xie, R., Barber, R. F., and Candès, E. J. Boosted confor- mal prediction intervals, 2024. URL URLtttts://aaat org/ abs/ /200 07449.
Richardson, and Green, P. J. On bayesian analysis of mixtures with unknown number of components (with discussion). Journal of the Royal Statistical Society Series B: Statistical Methodology, 5944)7731-792 1997.
Yang, Y. and Kuchibhotla, A. K. Selection and aggregation conformal prediction sets. Journal of the American Statistical Association, 120(549):435 447, 2025.
Roebrock, J. https: / ftttps:/sskeeareee http::///kkeaaaananninaaie readttheeedeeeddedeeeeoooo readthedocs. io/een/ateet//ides html.
skleamm- 2023.
URL
Romano, Y., Patterson, E., and Candès, E. J. Conformal- ized quantile regression. Advances in neural information processing systems, 32, 2019.
Sadinle, M., Lei. J., and Wasserman, L. A. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 11::223 - 234, 2016. URL https:/ api. wwwp.pseeaniii.....cceec.e..pese wesemnntiiccoollo org/ hteeCCrrpusDy 622583.
Scott, C. D. and Nowak, R. D. Learning minimum volume sets. Mach. Learn. Res., 7:665-704, December 2006. ISSN 1532-4435.

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
A. Related Work
Comparison to Lei et al. (2013) The influential work of Lei et al. (2013) gave the first theoretical guarantees of volume control or optimality to the best of our knowledge. In fact Lei et al. (2013) and subsequent follow-up works including Sadinle et al. (2016); Cheroozuukov et al. (2021) with theoretical guarantees on volume control study stricter quantity that corresponds to the volume of set difference vol (CsCops) (Lei et al., 2013; Sadinle et al., 2016; Chernozhukov et al., 2021). However, this much stronger notion requires that the optimal solution Copt must not only exist but also be unique. Usually additional assumptions need to be imposed in the neighborhood of the boundary of Copt in order that the set difference vanishes in the large sample limit. Specifically, the work of (Lei et al., 2013) assumes that the density is smooth, and in addition is strictly increasing or decreasing significantly. In comparison, our notion of volume optimality only requires the volume to be controlled, which can be achieved even if C' is not close to Capt. or when Copt does not even exist. Moreover, we do not need to make any assumptions on the smoothness of the density. In fact, the density may not even exist, and can have discrete point masses or ó functions as shown in the experiments. Indeed, from a practical point of view, any set with coverage and volume control would serve the purpose of valid prediction. Insisting the closeness to a questionable target Copt comes at the cost of unnecessary assumptions on the data generating process.
Comparison to Izbicki et al. (2020; 2022) The work of Izbicki et al. (2020; 2022) provided conformal prediction methods that can produce a union of intervals in a supervised setting. Specifically, their methods, CD-split and HPD-split, are designed to leverage level sets of an estimated conditional density function. CD-split achieves local and marginal validity by partitioning the feature space adaptively but does not guarantee conditional coverage in general. In contrast, HPD-split simplifies tuning by using a conformity score based on the cumulative distribution function of the conditional density. Under certain assumptions of density estimation accuracy and the uniqueness of the optimal solution, HPD-split achieves asymptotic conditional coverage and converges to the highest predictive density set which is the smallest volume set with the desired coverage. In comparison, our method outputs union of intervals with the smallest length from a direct estimator of the conditional CDF, which only requires the accuracy of conditional CDF estimation. Estimating the conditional CDF is statistically simpler than estimating the conditional density, which usually requires additional smoothness or regularity conditions.
Comparison to Kiyani et al. (2024) In very recent independent work, Kiyani et al. (2024) considered min-max approach for conformal prediction in the covariate shift setting with a view towards length optimality of their intervals. They proposed a new method based on minimax optimization to optimize the average volume of prediction sets in the context of covariate shift, which generalizes the marginal or group-conditional coverage setting. Their method uses a given (predefined) conformity score, and optimizes the choice of the thresholds I(X) for different covariates X E X to minimize the average prediction interval length, while maintaining the marginal or group-conditional coverage. Under certain assumptions that the conformity score is consistent with volume optimal prediction set, they show that solving their minimax optimization will give volume-optimal solution. However the problem of finding the best threshold function h(X) is non-convex problem that may be computational inefficient in theory; but they use SGD to find good heuristic solution in practice. This work is incomparable to this paper in multiple ways. While Kiyani et al. (2024) considers the covariate shift setting with a specific focus on marginal coverage and group coverage, we focus more on the unlabeled setting, and the conditional coverage setting of Chernozhukov et al. (2021). In contrast to their method that uses an off-the-shelf conformity score (and optimizes the thresholds h())), our method introduces new conformity score function based on dynamic programming to find volume-optimal unions of intervals. This also suggests that our methods and the methods of Kiyani et al. (2024) may potentially be complementary. Finally, by restricting the prediction sets to unions of k intervals, we got theoretical guarantees of volume optimality and get polynomial time algorithms based on dynamic programming to achieve them. Hence, while both their work and our work try to address the important consideration of volume optimality, they are incomparable in terms of the setting, the results and the techniques.
Other Related work In the non-conformal setting, the work of (Scott & Nowak, 2006) studied the problem of finding minimal volume sets from a certain set family given samples drawn i.i.d from distribution, with at least 1 a fraction of probability mass. However this work mostly focused on statistical efficiency, and did not consider the conformal inference setting. In the past few years, there has been an explosion of literature in conformal inference that develops new conformal methods for various settings (see e.g., Barber et al., 2021; Stutz et al., 2022: Kumar et al., 2023; Barber et al., 2023; Xie et al., 2024, and references therein).
12

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
While work is focused on the framework split conformal prediction, one interesting future extension is consider various other frameworks, especially the class of cross-validation-styy. aggregation of split conformal sets (Vovk, 2015; Vovk et al., 2018; Barber et al., 2021; Kim et al., 2020). Another related direction to volume optimality is model selection or prediction set selection based on efficiency (Liang et al., 2024; Yang & Kuchibhotla, 2025).
B. Additional Numerical Experiments
B.1. Construction of Nested Systems
Recall the construction of the nested system described in Section 4.1. It immediately follows Proposition 2.3 that the construction satisfies Assumption 2.4 in the unsupervised setting.
In the supervised setting, the construction of the nested system is based on Fly x). For each {Xn+1s" 12n-1 we generate Y1 (zx,,... (z) according to the quantile level
Y (a) = argmax/yy Fly 1/LL].
Then, the greedy expansion and contraction procedure described in Section 4. is applied on (I)), ,Yı Effectively, this is equivalent to using F(y æ) 1 T(Yi(a) < y) input. By its definition, Fly x)) is uniform approximation to Fly 2)) with error L/L. Thus, Assumption 3.1 is still satisfied for Fly z). In all of our experiment, we set = m. Remark B.1. It is clear that the details of the greedy expansion step and the greedy contraction step do not matter much for Assumption 2.4 or 1 to be satisfied. However, different choices will indeed affect practical performance, especially in the supervised setting when Fly) z) is not close to Fly z). To be more specific, sensible choices of expansion and contraction sets from the Sy- generated by DP will serve as a safety net against model misspecification. We discuss this in more detail in Section B.3, see e.g. Figure 17.
B.2. Unsupervised Setting
Given i.i.d. observations V1, Yg,..., Y2n R drawn from some distribution P, the goal is to find a prediction set C = CYY..... ,22) such that P E C) 2 11-a a for an independent future observation Y2++1 drawn from the same P. We implement the proposed conformalized dynamic programming (DP) method ČCP-DP. and compare it with the conformalized kernel density estimation (KDE) proposed by (Lei al., 2013) on the following synthetic datasets: (1) Gaussian; (2) Censored Gaussian; (3) Mixture of Gaussians; (4) ReLU-Transformm Gaussian.
Though the original conformalized KDE was proposed in the full conformal framework, will consider its split conformal version for a direct comparison. We believe the comparison between the full conformal versions of the two methods will lead to the same conclusion. For the conformalized DP method, the conformity score is constructed based on the nested system described in Section B.1 with m = 50 and = V(k + log n)/n. The conformalized KDE is also in the form of (9), with the conformity score given by
Y P
[KDE(I)= = np
K
where K()) is the standard Gaussian kernel and p is the bandwidth parameter. Both methods involve single tuning parameter, k for conformalized DP and p for conformalized KDE.
Gaussian: Our first distribution is P = N NO, 1). which is benign example for sanity check. We consider sample size being 100, and set the coverage probability conformalized DP is computed with number of intervals i ranging from 1 to 10. It turns out that the output of the prediction set is quite stable when varies (Figure 5). Even for = 10, our method still produces single interval this unimodal distribution.
a 30% for a more transparent comparison between the two methods. The
The conformalized KDE is implemented with bandwidth p ranging from 0.001 to 0.005. We observe that the quality of the prediction set is quite sensitive to the choice of the bandwidth. As is shown by Figure 4, if the bandwidth of KDE is too small, the conformal prediction will output almost the entire support of the data set. This is because if the KDE overfits the training samples, the level set of the KDE will likely not cover the future observation. Therefore, a conformal procedure, which guarantees finite sample coverage, has to be conservative by outputting the entire support. Figure shows that this issue will be alleviated as the bandwidth gets larger.
13

---

Volume Optimality in Conformal Prediction with Structured Prediction Sets
Data Prediction Set
KDE
Prediction Set
Frequency
Density
4
0 2.0
-155
-1.0
-0.5
0.5 Data Value
0.0
1.0
1.5
2.0
Data Value
Figure 4. Conformal prediction sets on the Gaussian dataset. The left plot shows the histogram of the dataset and the prediction set produced by conformalized DP with & = 1; right plot shows kernel density estimation with bandwidth = 0.001 and the prediction given by the conformalized KDE.
Prediction Set Volume
Prediction Set Volume
6-
Optimal Volume (0.7706)
Optimal Volume (0.7706)
Volume
Volume
4-
3-
1
10
0.001
0.002
0.003
0.004
0.005
Number of Intervals (k)
Bandwidth (p)
Figure Volumes of prediction sets of the two methods on Gaussian dataset (bluc) and the benchmark OPT; 1),0.3 0.7706 (red). The blue curves computed averaging 100 independent experiments.
Censored Gaussian: We next consider P being censored Gaussian distribution. We take the sample size be 100, and each sample be generated according Y; a (Z; 1) oZ4; 1) with Z; NO, 1) and (t)) max(t, 1) being the ReLU transform. This is equivalently truncated Gaussian distribution, which has standard Gaussian density (0, 2) and point mass at 0 with probability P Z2 < -1) and another point mass at 2 with probability P(Z, 2 1). Again, for the sake of comparison, we set the coverage probability to be 1 - = 30%.
Since P(|Z,) < 1) 2 1 1 a. the population optimal volume OPT 0.3) OPT: = due to the point masses (0, 2). By setting
for the conformalized DP procedure, the prediction set concentrates on the two point masses (Figure 6). Moreover, it produces very similar results as increase up 10. Figure shows that the only exception k 1, since short interval obviosly cannot cover two points that far away from each other.
We also run conformalized KDE with bandwidth ranging from 0.001 to 1. Since the distribution does not even have density function on the entire support, KDE is not really suitable for this setting. Not surprisingly, for typical choice of bandwidth that is not too small, the conformalized KDE will not identify the two point masses due to smoothing (Figure 6). Figure 7 reports the volume of the prediction set as we vary bandwidth, and the volume the prediction set is close to optimal only when the bandwidth extremely close to 0.
14

---

Volume Optimality in Conformal Prediction with Structured Prediction Sets
35
Data
0.525
KDE
Prediction Set
0.500
Prediction Set
30
Frequency
25
Density
0.475
0.450
20
0.425
15
0,400
0.375
0.350
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.0
0.5
1.0
2.0
Data Value
Data Value
Figure 6. Conformal prediction sets the censored Gaussian dataset. The left plot shows the histogram of the dataset and the prediction set given by conformalized DP with 2 intervals (The prediction set is two zero-length intervals 0.0 2.0). The right plot shows the kemel density estimation with bandwidth p 0.2 and the prediction set conformalized KDE.
1.4
1.4
Prediction Set Volume
Prediction Set Volume Optimal Volume (0.0000)
1.2
1.2
Optimal Volume (0.0000)
1.0
Volume
Volume
0.8
0.6
0.4
0.2
0.0
0.0
10
0.0
0.2
0.4
1.0
Number of Intervals (k)
Bandwidth (p)
Figure 7. Volumes of prediction sets of the methods the censored Gaussian dataset (blue) and the optimal volume (red). The blue curves are computed by averaging 100 independent experiments.
Mixture of Gaussians: In this experiment, we consider P = size and coverage probability are set as 600 and a = 80%, respectively. The two methods are compared with k ranging from 10 conformalized DP and bandwidth p ranging from 0.001 in conformalized KDE.
+ (0, N 0.25). The sample
200
200
200
Prediction Set
Prediction Set
Prediction
Frequency
150
Frequency
150
150
Frequency
125
125
325
75
75
50
50
-6
-4
-2
0
10
-2
10
-0
10
Data Value
Data Value
Data Value
(a)
3
(e)
Figure 8. Prediction sets provided by the conformalized DP method with the number of intervals k 2, 2, 6 on the mixture of Gaussians dataset.
15

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
KDE
Prediction
Prediction
Density
Density
Density
0 9.040
0.035
Prediction
0.625
-75
0.0
25
-75
0.0
5.0
10.0
-2.5
69
7.5 10.0
Data
Value
Data Value
Data Value
(a) p 0.01
(b) p 0.5
(e) p 5.0
Figure 9. Prediction sets provided by the conformalized KDE using bandwidth 0.01, 0.5, 5.0 the mixture of Gaussians dataset.
We report typical results of conformalized DP with & E 32 in Figure 8 and report those of conformalized KDE with p E {0.01, 0.5, 5.0} in Figure 9. The proposed method based on DP produces similar prediction close to optimal as long as k 2 3 (Figure 10). This is because OPT(P, 0.8) (PTs(P, 0.8) with P being Gaussian mixture of three components. In comparison, the results based on KDE are quite sensitive to the bandwidth choice, since different bandwidths lead to kernel density estimators with completely different numbers of modes. Figure 10 shows that for the optimal choice of bandwidth around 0.5, the KDE successfully identifies the three modes of the Gaussian mixture. However, even with the optimal bandwidth, the volume of the prediction set is in general still greater than that of the conformalized DP. This is partly because the three components of the Gaussian mixture not have the same variance parameters, and thus cannot be optimally estimated by KDE with single bandwidth.
20.0
Prediction Set Volume
Prediction Set Volume
17.5
Optimal Volume (3.0178)
17.5
Optimal Volume (3.0178)
Volume
15.0
Volume
12.5
12.5
10.0
7.5
7.5
5.0
2.5
2.5
0.0
2
10
0.0
4
Number of Intervals (k)
Bandwidth (p)
Figure Volumes of prediction sets the two methods on mixture of Gaussians dataset (blue) and the optimal volume OPT(P,0.8) 3.0178 (red). The blue curves are computed by averaging 100 independent experiments.
Reaan-eranto Gaussian: The Rel.U-Transformed Gaussian is generated according X; = Σ aj owwy Z, + b,) with Z, (0, 1). includes the censored Gaussian special case. Here, we take 7 and take randomly generated set of coefficients. The resulting density function is plot in Figure 11 (a). The sample size and coverage probability are taken as 600 and
80%, respectively.
Figure 11 also shows typical prediction set produced by conformalized DP with A = 4 and one produced by conformalized KDE with bandwidth o 0.02. Figure 12 gives a more thorough comparison. The proposed conformalized DP achieves near optimality when & 2 4, since the distribution has modes. The KDE solutions are sensitive to the choice of bandwidth for this complicated distribution.
16

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
KDE
Optimal Coverage Set (80%)
Prediction Set
0.30
Frequency
0.4
Density
0.3
0.15
60
0.10
20
0.1
0.00
0.0
-12.5-10.5--1
-5.
6.0
5.0
15.0
10.0 -75
-5.
2.5
0.0
2.5
5.0
7.5
-12.5
10.0
-75
Data Value
Data Value
Date Value
(a) Optimal Coverage Set
Conformalized DP with
(c) Conformalized KDE with 0.02
Figure 11. (a) Density of The SeLU-Transfomme Gaussian and prediction set with optimal volume; (b) Conformalized DP with & 4; (c) Conformalized KDE with p 0.02.
25.0
25.0
22.5
Prediction Set Volume Optimal Volume (5.1361)
22.5
Prediction Set Volume
20.0
20.0
Optimal Volume (5.1361)
Volume
17.5
Volume
17.5
15.0
15.0
12.5
12.5
10.0
10.0
7.5
7.5
5.0
5.0
6
B
10
1
2
3
Number of Intervals (k)
Bandwidth (p)
Figure 12. Volumes of prediction sets of the methods the ReLu-tranffrrmed Gaussian dataset (blue) and the optimal volume OPT(P,0.8) = 53661 (red). The blue curves are computed by averaging 100 independent experiments.
Finally, we study the effects of sample sizes and coverage probabilities for the two methods. Specifically, we examine how the volume of the prediction set decays as the sample size increases and how it varies with different coverage probabilities. The experiments will be conducted with data generated from the following two distributions:
Effects of Sample Sizes and Coverage Probabilites:
1. |N( + (N. ( N((
2. The ReLU--Trasformed Gaussian Y; Ej= aj oow,, * Z, + by) with Z, ~ N(0, 1), and coefficients are the same as in the previous experiment.
For conformalized DP, we will set & 3 for the first distribution and A: = 4 for the second one to match the number of modes in the two cases. For conformalized KDE, since the method is sensitive to the choice of bandwidth, we will scan the bandwidth from 0.001 to 0.2, and only report the one with the smallest volume. We also benchmark the performances the two methods by the optimal volume and a standard split conformal procedure with conformity score Σ Yi
Istandard (y)
17

---

Volume Optimality in Conformal Prediction with Structured Prediction Sets
14.75
8.0
14.50
7.8
4.5
Conformalized (k=3)
Conformalizes lized DP (k=4)
Conformalized KDE (best p)
Conformalized KDE (best
Volume
Standard Split Conformal
Volume
Standard Split Conformal
4.0
Optimal Volume (3.0178)
Optimal Volume (5.1362)
3.5
5.0
200
300
400
500
700
800
900
1000
200
300
400
500
600
700
800
900
1000
Number of Samples
Number of Samples
Figure 13.. Volume of prediction against sample size. Left: 2N(-6,000001) + M(, (8, Right: Rel.U-Transforee Gaussian. curves are plotted by averaging results from 100 independent experiments.
Conformalized KDE (best
17.5
Conformalized KDE (best p)
Conformalized (K=3)
Conformalized DP (k=4)
Standard Split Conformal
Standard Split Conformal
Optimal Volume
Optimal Volume
Volume
Volume
8-
10.0
7.5
4
5.0
2
2.5
0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.B
0.9
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Coverage Probability
Coverage Probability
Figure 14. Volume of prediction against coverage probability. Left: [N666,, 0.0001) N 1) (N,, 0.25). Right: ReLU- Transformed Gaussian. All curves are plotted by averaging results from 100 independent experiments.
Figure 13 shows the results with sample size ranging from 200 to 1000 with the coverage probability fixed by - a 80%. Both conformalized DP and conformalized KDE produce smaller prediction sets as sample size increase. Even with the bandwidth optimally tuned for conformalized KDE, which is not feasible in practice, the proposed conformalized DP tends to achieve smaller volumes in most cases. In setting of the ReLU-Transformed Gaussian, we observe that the volume of conformalized KDE prediction set barely decreases after sample size 600, since in this case density estimation is very hard for KDE.
Figure 14 considers coverage probability ranging from 0.1 to 0.9, with sample size fixed at 600. The conformalized DP constantly achieves smaller volume than the conformalized KDE even though the later is computed with optimally tuned bandwidth. This demonstrates the robustness of the conformalized DP handling varying coverage requirements while maintaining efficiency in volume.
We compare the performance of conformalized KDE and conformalized dynamic programming (DP) methods on the Enzyme dataset in Table 7 and 8. For conformalized KDE, we report results across range of bandwidths from 0.1 to 0.9; for conformalized DP, we vary the number of intervals = 1........ .5. We output the average and standard deviation for volume and empirical coverage over 50 trials and 80% target coverage. We observe that conformalized DP achieves higher coverage with lower volume, indicating more efficient coverage compared to conformalized KDE.
Real-World Dataset:
18

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Table Conformalized KDE Enzyme Dataset
Bandwidth
Volume
Coverage
0.1
0,9826 + 0.0969
0.8081 0.0217
0.3
1.4640 0.0940
0.8056 0.0231
0.5
1.5218 # 0.1332
0.7999 0.0268
0.7
1.4526 0.1809
0.7962 0.0272
0.9
1.3867 0.1799
0.7971 0.0236
Table Conformalized DP Enzyme Dataset
k
Volume
Coverage
1.2207 0.1188
0.8101 0.0461
2
0.8997 0.1414
0.8144 #
3
1.0118 0.1975
0.8416 0.0390
4
1.0131 = 0.1878
0.8458 0.0379
5
1.0520 0.2002
0.8558 0.0353
B.3. Supervised Setting
In the supervised setting, we validate our results on the simulated datasets in Romano et al. (2019) and Izbicki et al. (2020). We compare against the methods of Conformalized Quantile Regression (CQR) of Romano et (2019) and Distributional Conformal Prediction (DCP) of Chernozhukov et al. (2021) and CD-split and HPD-split of Izbicki et (2022).
Simulated Dataset (Romano al., 2019): We first describe the simulated dataset in Romano al. (2019). In this data, each one-dimensional predictor variable X; is sampled uniformly from the range 5). The response variable is then sampled according to
Y Pois(sin (X,) + 0.1) + 0.03 X; E1,: + 25 1(U, < 0.01} E2.
where Pois(A) is the Poisson distribution with mean X, C1,; and E2, are independent standard Gaussian noise, and U; is drawn uniformly on the interval [0, 1]. The first component the distribution, Pois(sin?((X)) 0.1), generates distribution that is clustered around positive integer values of Y. with variance that changes periodically in X. The second component of the distribution, 0.03 X; E, adds some additional variance to each of the integer centered elusters, where the magnitude of the variance inereases with X. The final component, 25 IUU, 0.01) E2,i. adds small fraction of outliers to the distribution. We generate 2000 training examples, and 5000 test examples, in the work of (Romano et al., 2019). The same subset of training and test examples are used in the illustration of each of these methods. The set of test examples is visualized in Figure 15, with the full range of Y values including the outliers. In the plots associated with our conformal output, we zoom in on the Y axis for readability, leaving the outliers off the chart.
Simulated Dataset (Izbicki et al., 2020): We now describe the simulated dataset in Izbicki et al. (2020). In this data, the predictor variables X (X,,..., Xa) with d = dimensions are independently and uniformly sampled from the range [-1.5, 1.5). The response variable then generated according to the following bimodal conditional distribution:
Y X 0.5N((()) ,(X), xx))) + - ox)),
where the functions f(X), g(X), and o² are defined as:
1 +|x]]
- -XI
+1, s(X) 21((X -0.5) X1 0.5, o²(X)
Here, (p, d²) denotes a normal distribution with mean μ and variance o², and the indicator function I(X; 2 -0.5) accounts for the bimodal nature of the data, introducing piecewise behavior in the response variable. The first term f(X)
19

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
40
Observations
20
-20
00
-40
X
Figure 15, Simulated data Romano et al. (2019), including outliers.
Observations
00
2
1000
:20
-1.5
-1.0
-0.5
0.0
15
X1
Figure Simulated data from Izbicki (2020), illustrating the bimodal distribution of response variable.
captures polynomial relationship with X1, while the second term g(X) introduces an asymmetric bimodal effect depending on the value of X,. The variance (X) increases linearly with [1]], adding heteroscedasticity to the distribution.
We generate 2000 training examples and 5000 test examples. The same training and test sets used consistently across all experiments to ensure reproducibility. The test set is visualized in Figure 16, showcasing the full range of Y values, including the effects of bimodality and variance heterogeneity.
Methods: We compare our conformalized DP with the following methods: Conformalized Quantile Regression (CQR) of Romano et al. (2019) and Distributional Conformal Prediction via Quantile Regression (DCP-QR) and Optimal Distributional Conformal Prediction via Quantile Regression (DCP-QR* " of Chernozhukov et al. (2021) and CD-split and HPD-split of Izbicki al. (2022).
We now describe the implementation of these methods. The compared methods, CQR, DCP-QR, DCP-QR*, and our conformalized DP rely quantile regression. For simulated dataset (Romano et al., 2019) with single dimensional predictor variable, we use the package aklearn-quante which implements the method of Quantile Regression Forests, due to Meinshausen (2006). The CD-Split and HPD-Split methods require the conditional density estimation, which is achieved by the package FlexCoDE (Izbicki & Lee, 2017). For simulated dataset (Izbicki et al., 2020) with high dimensional predictor variables, the quantile regression by sklearn welearn-quar reaaanntuanti is not informative. For CQR, DCP-QR, DCP-QR*, and our conformalized DP, we first use the
(Roebroek, 2023) to implement the quantile regression,
20

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
package FlexCoDE generate the conditional density estimation and then integrate the conditional density estimation to get quantile regression and conditional CDF. The CD-Split and HPD-Split methods again use the conditional density estimation provided by FlexCoDE, All methods are implemented within the split conformal framework, where the training data is randomly divided into two equal parts. Specifically, half of the data is allocated for model training, while the remaining half is used as the calibration set to ensure valid coverage guarantees.
For convenience, we will refer to the gth estimated quantile of Y given = x as Q x)). Some of the following methods use quantile regression to estimate the whole conditional c.d.f. of Y given X, by estimating a set of quantiles from a fine grid. This gives us an estimate of the conditional c.d.f., which gives us access to Fly x),, the inverse of Q. (That is, Fly 2) = q. such that y = ((, Since we only have Q for values of y in the grid, we set Fly x)) to be the smallest q in the grid such that y S 2)),
Conformalized Quantile Regression (CQR), (Romano et al., 2019): This method fits a model to two quantiles of the data, Now S and quigh 1 g. On a new test example Xvest, CQR uses the model to estimate the low and high quantile, and the conformal procedure will output the interval
(Qqyooe Xtest) b, Qignight Xtest) + +b]
where b is buffer value chosen in the calibration step of the conformal procedure to guarantee coverage.
Distributional Conformal Prediction via Quantile Regression (DCP-QR), (Chernozhukov et al., 2021): In this frame- work, we assume access to a model F that can estimate the conditional c.d.f. of the distribution of Y given X, which we estimate via quantile regression. Similar CQR, we start with ylow = 2 and Thigh
2. In DCP, instead of adding the buffer in the Y space, the buffer is added in the quantile space. That is, on new test example X DCP will output the interval
@Qqiin - b, Xtest), (ghigh + b, X
where b is buffer value chosen in the calibration step of the conformal procedure guarantee coverage.
Optimal Distributional Conformal Prediction via Quantile Regression (DCP-QR*), (Chernozhukov et al., 2021): The optimal DCP is very similar to DCP, except that Qoo and qhigh need not be symmetric around the median (q = 2) Instead, they are chosen to provide the minimum volume interval that achieves the desired coverage. We note that the buffer still applied symmetrically in the quantile space. That is, the lower quantile lowered by some value b, and the upper quantile is raised by the same value b.
CD-Split (Izbicki et al., 2020; 2022): This method provides prediction sets based on the conditional density estimation and a partitioning of the feature space. The conformity score in CD-split is based on a conditional density estimator, which allows the method to approximate the highest predictive density (HPI) set. The feature space is partitioned based on the profile of the conditional density estimator, and the cut-off values are computed locally within each partition. This approach enables CD-split to achieve local and asymptotic conditional validity while providing more informative prediction sets, especially for multimodal distributions.
HPD-Split (lzbicki et al., 2022): The HPD-split method outputs prediction sets based on the highest predictive density (HPD) sets of the conditional density estimation. Unlike CD-split, which partitions the feature space, HPD-Split uses the conformity score based on the conditional CDF of the condition density estimator. Since this conditional CDF is independent of the feature variable, HPD- upD-Split does not require the partition of the feature space and tuning parameters for that as in CD-Split. When the conditional density estimation is accurate, HPD-Split converges to the highest predictive density (HPD) sets.
Conformalized Dynamic Programming, A: = 1 and k 5: We implement a modification of the procedure described in this work. In the unsupervised setting, we described the dynamic programming procedure that outputs the minimum volume set of l: intervals that contain a desired fraction of samples. In this setting, given a new test example X, we do not have access to samples. Instead, we have access to grid of estimated quantiles of Y given X. We implement a version of the dynamic programming procedure that operates on this quantile grid instead of a set of points, to output the minimum volume set of l intervals that cover at least the desired probability mass. We can also modify our greedy contraction and expansion procedures to provide a nested system of sets for different coverage levels.
21

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Discussion: The results of our experiments are illustrated in Figure 18. Our experiments show that Conformalized Quantile Regression (CQR) and Distributional Conformal Prediction via Quantile Regression (DCP-QR) perform approximately as well as each other on this dataset, achieving average volume 1.42 and 1.48 respectively (see Figures 18a, 18b).
Optimal Distributional Conformal Prediction via Quantile Regression (DCP-QR*) achieves a significant improvement over DCP-QR on this data, achieving average volume 1.29 (see Figure 18c). This is due to the fact that the distribution of Y values is not symmetric around, or peaked at the median Y value. Thus, DCP-QR suffers a disadvantage, because outputs intervals that are centered around the median in quantile space, and does not take into account the relative volumes of the quantiles in Y space. DCP-QR- * on the other hand, is able take advantage of the fact that, for this data, quantiles close to 0 have very low volume, and output intervals that use these quantiles.
While DCP-QR* uses information about the relative volume of the quantiles to choose (low and Thigh. which define the output intervals before conformalization, it does not take the volume into account during the conformalization step. Expanding the interval by a buffer value that is small in quantile space, can lead to a large difference in Y space, increasing the volume of the output interval significantly. For example in Figure 18c, the intervals for X just larger than stretch very far into the negative Y region, as small adjustment in quantile space is a large adjustment Y space.
This issue is avoided by our Conformalized Dynamic Programming (Conformalized DP) method with greedy expansion and contraction for k = 1 interval. Before conformalization, the interval output by Conformalized DP and DCP-QR* is the same: it is the volume optimal interval that achieves given coverage according to the estimated c.d.f.. However, our method takes the relative volume of different quantiles into account in the conformalization step, and avoids the issue of expanding the interval in quantile space in directions that add too much volume in Y space. This allows the method to achieve an improved average volume of 1.14 (see Figure 18f).
An illustration of this issue is given in Figure 17. Suppose that for a new test example X, the estimated conditional distribution of Y is skewed. (In this illustration it is x² (5).) Suppose that target coverage was 0.5, and in the calibration phase we are required to expand coverage to 0.7. Both ConformalizedDPP and DCP-QR* will start by calculating the minimum volume interval that captures 0.5 of the probability mass. In this case it is the red region from x = 1.58 to x = 5.14 (i.e., the set of x such that f()) > 0.12, where f(x is the p.d.f. of the distribution). Then, each method must expand this interval to capture 0.7 of the probability mass. DCP-QR* does this by adding two blue regions, each of which capture an additional 0.1 probability mass. This results in expanding the interval significantly to the right, even though the density is low. ConformalizedDP takes the volume (i.e., density) into account when expanding the interval, and produces the minimum volume interval that captures 0.7 of the distribution (i.e., the set of such that f(x) > 0.085), in this example. (We note that the expansion and contraction procedure of ConformalizedDP does not always result in the volume optimal prediction set for the adjusted coverage, only the original target coverage. However, in this case, since the distribution is unimodal and A = 1, we do indeed recover the volume optimal set even for the adjusted coverage.)
Finally, we also implement Conformalized DP with intervals. This allows us to fit to the multimodal shape of the Y data, and achieve a much lower average volume of 0.45 (see Figure 18g).
22

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
0.16
0.16
0.14
0.14
0.12
0.12
0.00
0.00
0.06
0.06
0.04
0.04
0.00
0.00
(a) When expanding from the red region, coverage 0.5, to region of coverage 0.7, (b) When expanding from the red region, coverage 0.5, to region of coverage 0.7, Conformalized DP chooses the blue region additional volume
DCP-QRR chooses region with additional 2.56.
Figure 17. We illustrate the difference between DCP-QRR and Conformalized DP for & = 1, on the example where the estimated conditional distribution of Y for new Xumt is x" (5). We plot the intervals that chosen by the methods against the p.d.f. of the estimated distribution.
Observations
CQR prediction interval
1
2
3
X
Conformalized Quantile Regression (CQR). 2019), achieves average volume 1.42 and empirical coverage 70.62%.
23

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Observations
Observations
DCP-QR prediction interval
DCP-QR prediction interval
4
00
00
0
6
10
00
00
0
1000
2
50
2
0.0
90
00
000000
Booo
80
0.0000
-2
-2
X
X
(b) Distributional Conformal Prediction (DCP), (Chemozhukov et al., 2021), achieves average volume empirical coverage
(e) Optimal Distriburional Conformal Prediction (DCP-QR ) (Chernozhukov et al,, achieves average volume 1.29 and empirical coverage 71.06%.
Observations
Observations
CD-split prediction interval
HPD-split prediction interval
00
000
0
000
-2
-2
2
3
X
X
(d) CD split Conformal Prediction, (Labicki et al., 2022), achieves average vulume 1.83 and empirical coverage
(e) spPDtsplit Conformal Prediction, (lobicki et al., 2022), achieves average volume empirical cnvernge 69.44%.
Observations
Observations
ConformalizedDP prediction interval
ConformalizedDP prediction interval
00
0000
90
00
90 0
0.0
2
0-0-0-00
29009.08
-2
-2
0
1
2
0
1
2
3
4
5
X
X
Conformalized Dynamic Programming empirical coverage 74.04%.
1). achieves average volume 1.14 and
(g) Conformalized Dynamic Programming (k 5), achieves average volume 0.45 and empirical coverage 72.36%.
Figure 18. Comparison of supervised conformal prediction methods simulated data from (Romano al., 2019). All results are for target coverage of 0.70.
24

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Observations
CQR prediction interval
2
88
8
-2
-1.5
-1.0
-0.5
0.0
1.5
X1
(a) CQR, achieves average volume 4.10 and empirical coverage 71.54%.
Observations
Observations
DCP-QR prediction interval
DCP-QR* prediction interval
4-
-2
-2
-4
-4
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
X1
X1
DCP-QR, achieves average volume 4.04 empirical coverage 70.85%
(c) DCP-QR achieves average empirical coverage 69.66%.
Observations CD-split prediction interval
8
Observations HPD-split prediction interval
6-
6-
4-
4-
2
2
-2-
-2
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
X1
X1
(d) CD-Spli, achieves avemge volume 3.69 and empirical coverage 69.36%.
(e) HPD-Split, achieves average volume empirical coverage 59.64%.
25

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Observations
Observations
ConformalizedDP prediction interval
ConformalizedDP prediction interval
2
2
8
8
-2
-2
66
-1.5
-1.0
-0.5
0.0
1.5
-1.5
-1.0
-0.5
0.0
0.5
1.5
X1
X1
(f) Conformalized Dynamic Programming (k= 1) achieves average volume 4.00 and empirical coverage 68.98%.
(g) Conformalized Dynamic Programming (k= = 2), achieves average volume 3.55 and empirical coverage 69.42%.
Figure 19. Comparison of supervised conformal prediction methods on simulated data from (Izbicki et al., 2020). All results are for a target coverage of 0.70.
Dataset (Dhillon et al., 2024). We evaluate our method along with several baselines on two real-world regression datasets from the UCI UCI repository: AirFoil and WineQuality. These two datasets were previously considered in the conformal prediction study by Dhillon et al. (2024). For each dataset, we compare the empirical coverage, average volume, and runtime of the prediction sets output by different methods, with a shared preprocessing time (for conditional CDF estimation using FlexCoDE) excluded from reported runtimes. For AirFoil and WineQuality, we repeat each experiment 20 times and report the mean and standard deviation of all results with target coverage 0.8.
Recall that our method for the supervised setting requires a conditional CDF estimator. When the feature space is high- dimensional in experiments, this is constructed by using black-box the conditional density estimator of Izbicki & Lee (2017) that underlies CD-split and HPD-split. When the conditional density estimate is used as black-box, the optimal volume set is produced by taking an appropriate level set of the conditional density as taken by CD-split and HPD-split; hence we do not expect our method to outperform CD-split and HPD-split in these experiments. However, we observe that our method is still competitive in these experiments, as described below.
Among the competitive methods, CQR, DCP-QR. DCP-QR* all output a single interval and are more suitable for unimodal distributions. On the other hand, CD-split and HPD-split output union of intervals and are suitable for data generated by multimodal distributions. The experiments show that our proposed framework of Dynamic Programming is competitive against both settings with different values of k. To be specific, for the dataset in Table 9, DP with k: 1 is competitive with the DCP-QR and DCP-QR* which achieves the smallest volume, while in Table 10, DP with k = 5 is competitive with HPD-split and CD-split which achieve the smallest volume. In practice, the value of k: can be tailored based on the distribution, or chosen adaptively using the ideas in Bai et al. (2022).
Interpretation:
Table Comparison methods on the dataset AirFoil. Reported runtimes exclude a shared preprocessing time 6.3819 0.1445(s) for estimating the conditional CDF using I'1 eXCODE common to all methods.
Method
Average Volume
Empirical Coverage
Runtime (s)
CQR
7.1167 + 0.4479
0.8061 + 0.0266
0.3536 + 0.0528
DCP-QR
6.4662 + 0.4478
0.8032 = 0.0268
0.8185 + 0.0613
DCP-QR* *
6.4612 + 0.4078
0.7953 1:2 0.0240
0.9003 + 0.0555
CD-split
7.5517 + 0.5343
0.7962 = 0.0269
0.1311 + 0,0110
HPD-split
7.3650 + 0.6549
0.8013 = 0.0278
1.8243 + 0.0556
DP (I: = 1)
6,8287 + 0.3548
0,8065 = 0.0245
32.3420 + 0.1109
DP (k: = 5)
7.5002 + 0.5302
0.8032 + 0.0211
206.3317 + 196.6624
26

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Table 10. Comparison of methods the dataset WineQuality. Reported runtimes exclude shared preprocessing time of 68.3879 +
2. 2.8636(s) for estimating the conditional CDF using TeeCooE common to all methods.
Method
Average Volume
Empirical Coverage
Runtime (s)
CQR
1.1251 = 0.2066
0.8058 = 0.0135
5,0441 + 0.5437
DCP-QR
0.9980 + 0.0771
0.8042 = 0.0122
7.2799 + 0.7250
DCP-QR*
0.9514 = 0.0721
0.8030 = 0.0115
7.6734 + 0.9398
CD-split
0.5066 + 0.7077
0.7759 = 0.0368
2.6191 + 0.1664
HPD-split
0.2694 + 0.0163
0.8010 = 0.0154
9.0277 + 0.0973
C-DP(k 1)
0.9389 = 0.0555
0.8074 = 0.0134
191.8998 + 213.9385
C-DP(k 5)
0.2947 + 0.0215
0.8048 = 0.0127
704.8169 + 40.4745
C. KDE Optimality Implies DP Optimality
Suppose distribution P on R admits a density function p. The kernel density estimator depending on k i.i.d. samples Zi..... Z is defined by
1 kp
2ー2 Zj P
y
(v)
K
(13)
where (.) is a standard Gaussian kernel and p a bandwidth parameter. The conformal prediction method by (Lei et al., 2013) is based on the idea that the level pk is close to that of p as long as pę is close to p. In this section, we will show that as long as Pı is close p, the dynamic programming also finds prediction set whose volume is nearly optimal compared with the level set of p. This implies that DP always requires stronger assumption to achieve volume optimality.
The existence of a KDE close to can be even weakened into the following assumption.
Assumption C.1. For any positive integer k there exists some E > and some Gaussian mixture P3 = 1 03) such that TV(Pk, P) Ek.
In particular, the KDE (13) based on k samples is a special case of the Gaussian mixture, given that Gaussian kernel used. Though the characterization of the closeness between Pk and p through &o norm by (Lei et al., 2013), similar error bounds also apply to the &, norm, which is the total variation distance. For example, suppose P has bounded support and the Hölder smoothness is 3 E (0, 2]. Then, one can take E = θ k - with an appropriate choice of the bandwidth, where θ hides some logarithmic factor of k:
Theorem C.2. Consider i.idd observations YI,'.., "1,..,,,n.. Ya, Ya+1 generated by some distribution P on R. that satisfies Assump- tion C.I. For any ar 5, y E (0, 1) such that 5 >>> / k log />llogg and + 25 + 2 < a, let ODP E Ck be the output of Algorithm I with coverage level 1 a + and slack 7, Then, with probability least 1 8, we have
1. P (Yn+1 E Cor ,,, Yx) 2 a0;
2. vol(Cpr) < OPT(P, + +5 ) 2=x).
The result of Theorem C.2 can also be conformalized as in Section 2.4, so that the restricted volume optimality OPTx(P,.) in Theorem 2.5 can be strengthened to (P.(P,.) without restriction whenever P satisfies Assumption C.I, which, in particular, includes the situation where the density of P can be well estimated by KDE.
The volume sub-optimality given by Theorem C.2 is 7 + 25 + 25g- When the distribution P is 3-smooth, the sub-optimality 8 is of order é (V++ + - 2 by taking E = 5 k 2F41 ) =
and y sufficiently small. Thus, optimizing
this bound over l leads to the rate θ ( In comparison, the KDF achieves a faster rate θ n उ0न
(Lei et al.,
2013) for smooth densities. This is actually a technical artifact by specializing Assumption C. to the KDE (13). In fact, when the density of 3-smooth, is well known that Assumption C. is satisfied with a better e = @(k--) (Ghosal
27

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
van der Vaart, 2007; Kruijer et al., 2010), which then leads to the volume sub-optimality T (V + k-)
that leads to the
near optimal rate θ n 2F41 with k = ((1254r))
C.1. Proof of Theorem C.2
We first state a lemma that shows that level set of Gaussian mixture with ls components must belong to the class Ck-
Lemma C.3. For Gaussian mixture Pk E wy (1,,, and any E (0,
O a) OP a).
The proof of the lemma will be given Appendix D.4, Now we are ready to state the proof of Theorem C.2.
Proof of Theorem C.2. By Proposition 2.3, we know that ÖPP satisfies (CpP) 2 a + 6 and vol(Cnp)) - (PT + 8 + r). The condition on implies that supcec, [C, - P(C) S with probability at least 1 (Devroye Lugosi, 2001). Therefore, the coverage probability
P (Vatz CDr Yi,".. ,Y,) 2 (CDD)) -82 1 a,
and the volume be bounded by
COpr)
1
-P Ek) O - E
- 28 25x),
where the identity above is by Lemma C.3.
D. Additional Proofs
D.I. Proof of Theorem 2.1
The proof relies on the following technical lemma, whose proof will be given in Appendix D.4. Lemma D.1. For any 8, E > 0 and any integer 0, there exists some distribution supported on
Pe = (P: supp( c 1
such that TV (X", pddlI)= 6.
Now we are ready to state the proof of Theorem 2.1.
Proof of Theorem 2.1. By Lemma D.I, there exist II,5 and I supported on Ps, such that TV (X*, pd 8 and TV (x=+1, I pat1 dlI 8.
Since pu+1 (Yn+1 E Ō(Y,, Yn)) 2 1 1- for all P. we have
/ p O(Y,,... Y2) 2 1 a.
By TV (x+t1, I pn- pn-Idlm++isl < 8, we have
(N( ,Y))) = x 30+1(Yn+1 E CY Kn)) 2 1 aa a-8.
Y Yi..,,yaa Yand
28

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
By TV (A", pnd S 6, we have
(CC(Y, ..)d 2 - a 26.
Then, there must exists some P E supp([[n,6) C Po. such that
E
X(O(,, ,,),,,"))))))))""""" 2 a- 26.
Y Pm
The fact that E Pa implies TV(P, A) 2 1 - 6. By the definition of total variation, there exists some set such that
P(B) - X() 2 1 - 6, which implies P(B) 2 and (BB) s Therefore, OPT 6) 8.
We finally have for any (0, at,, the expected volume prediction set is
vol( .Y))
1- a-
IV IV
8
OPT(P,1 -6
OPT(P, =),
as long as 5 sufficiently small so that min((1 a)/3, -}.. The proof is complete.
D.2. Proof Theorem 2.5
Theorem 2.5 is a special case of Theorem 3.3 in the setting where F(- 2) does not depend on x and F(. x) is defined as the empirical CDF of ",,".,, Y,. Then, Assumption 3.2 is automatically satisfied by standard VC dimension bound (Devroye & Lugosi, 2001).
D.3. Proof of Theorem 3.3
We will prove the three properties of Theorem 3.3 separately. We note that the marginal coverage property holds without Assumptions 3.1 and 3.2. It is standard consequence of applying the split conformal framework, but we still include proof here for completeness.
Proof of Theorem 3.3 (marginal coverage). By the construction of CDCP- (X224+1)), have
P (V2nt1 Drcr-Dr(X2nn1)) P (((22++1, X2n+1) 2 [[(++)aa])
Since the conformity score y constructed from F(: ) independent from the second half of the data. Thus,
1 is exchangeable with q(Yn+1, Xn+1), ..- (Y2m, X2n). which implies the desired conclusion by the definition of [[++)o]]
Next, establish the conditional coverage property. We need the following property of the conformity score that is computed based on nested system.
Lemma D.2. For any E [m + 1}, Sy(z) if and only if 9/.. x) 2 m 1, where the set Sm+1(a) is defined as IR
The proof of the lemma will be given Appendix D.4.
Proof of Theorem 3.3 (approximate conditional coverage). We first note that Assumption 3,2 implies
E| [1 X2n+1) F(: X2n+1)lle,o S 25.
(14)
We use F2n to denote the offilld generated by the random variables (X₁, Y1), ... (X2ns Yen). Let Ex and E,,, be the expectation operators under the marginal distributions of X2a+1, and of (X1, Yi), (X2n, Y2n), respectively. Then, we have
(g(Ven41, X2n+1) 2 [((+1ja])
E
E P (g((Y2241, X2n+1) 2 (((+1aa]] ( (, Xan-1
Fin
29

---

Volume Optimality in Conformal Prediction with Structured Prediction Sets
By Lemma D.2, 2 X2n+1) 2 [[n=1)aa] is equivalent to Y2n+1 E (x(=2+1) for some 3 measurable with respect Fz Then, have
E P (((X2n+1,X2n+1) 2 (m++1aa |2 F2n) EF Exant1 IP (Yau+1 Sy(X2n+ 1))2m+1)1X22111.1 F2n)
Jan X2a+1
BFg Ex Sy(Xonts)
dF X2n+1).
Since Sz(X2n11) E Ck. by (14), we have
Ex Exaut I
dF X2n+1) Exent / (x22++)))
dF X2n+1)
(X(22))))
+ El| X2nt1) - F(:) X2n+1)llk,oo
LEz Exau11 8y(22=+1)
dF(y X2n+1) + +
dF(y X2n+1) 2. which is independent of X2 since 3 measurable with By Assumption 3.1, have Jsy (Xen+1)
respect to Fen. Thus, we have
Bxn, Ex
dF(2)) X2n+1) - 28 = Byan
df(y X2n+1) + 25.
S5(Xen+s))
(7(
By Assumption 3.2, we have with probability at least 1 -,
Byz Sy(Xam+1)
dF(y) (2n+1) +6 SEF s7(Xent1)
dF (2a+1) 38
=P (q(Y2n+ X2n41) 2 [[(+1]] (22+1) 35.
Therefore, with probability at least 1 - 6, the approximate conditional coverage holds
PP (g(Y2n+1, X2n+1)= [[(a+1)a] (22+1)
(a (g(Y2n+1, X2n+1) 2 ([(+1)aa]) -38 38
33.
Finally, we prove the last property on volume optimality.
Proof of Theorem 3.3 (conditional restricted volume optimality). By Assumption 3.1, there exists some j E [m]], such that
E
dF(y) Xent1) 2 1 - a + + 38.
Sy- (X2n41)
Assumption 3.2 implies that
P PY2n+1 E (x-2x1)))
= E
dF X2n+1)
J (Xant)))
E
dF (2nt1)
FE| (12+1)))) F(: X2n+1)lla,00
1
> 1 - a +
By Hoeffding's inequality and the condition on 6, we have
2n
Σ
I(Y, E Sy (x.)) P (Y2n-1 E (XxnNt))2)
1
30

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
with probability at least -- Combining the two inequalities above and Lemma D.2, get
1
1
T(a(Y, 2 - + - ++ n'
1=n+1
with probability at least 1 6. 8. This immediately implies | = in(a-n-')+1 2 mm-j - + 1 by the definition of order
statistics. Therefore, the volume of the prediction set CDcr- Dr (X x2 is at most
vol (1y y R q(v, X2n+1) 2 [n++1aa)
<vol (1 y R (31, X2n+1) 2 Q[aa| })
Svol (fy E R: q(v, x2n+1) 2 m -3- j + 1}) (Xx(()-(X22+11))
where the last identiy is by Lemma D.2. The volume of S5+ ( (X24+1) can be controlled by Assumption 3.1,
vol(5,-(X2.+ ( OPT
(( X X2 1
a +
1
38
72
1
SPPT
[(. X2o+1);
+ 46 +
n
where the last inequality, which holds with probability at least 1 - 8, is by Assumption 3.2. Combining the inequalities above with union bound, we get the conclusion.
D.4. Proofs of Proposition 2.3, Lemma C.3, Lemma D.1 and Lemma D.2
Dynamic Programming Algorithm. The dynamic programming table DP j. stores the minimum volume of intervals that collectively cover lyn points from the sorted training data Yi))...,, X(y), where the right endpoint of the rightmost interval is fixed at Ygy) Here, Y(i)..., ((n) are the training data points .y,....y,, sorted in non-decreasing order. For each state in the DP table, we iterate over all possible left endpoints of the rightmost interval, as well as the right endpoint the preceding interval (if exists). This allows us systematically compute the optimal solution for each state by the following formula:
1, DP(i,J,) Y (V--(mmm]+
fi>l 1, DP(i.,,1) "-g"" (16) - Y69 + 1.5",
min
where 1' - 11--(0-j'+ 1)/mm)] Finally, we find the minimum volume solution among all entries DP j, [[1 [[1- a/1l) for و S n. Then, we use the standard backtrack approach on the DP table to find the prediction set CDP.
Proof of Proposition 2.3. Without loss of generality, we assume that 1/7 is an integer, otherwise, we can decrease 7 to make this hold. For any E [K]. [m], E [1/7]. we use the dynamic programming table entry ji.)j. to store the minimum volume of i intervals that cover [Z -yn] points in Yay.-.., YG) and the right endpoint of the rightmost interval is at Yoy, If there is no feasible solution for this subproblem, we set DP(i,j,1) = co. This dynamic programming is shown in Algorithm 1. This dynamic programming runs in time (n²kk/7)
We then find the solution with the minimum volume among all subproblems DP(K, [(1 - /)/11) for $ j n. It easy to see that there exists feasible solution. Let ÖDP E C2 be a union of k intervals in this solution. This solution covers at least [11 a1/r- [nn)] [[1 - =a) points in .I,...,.8 Thus, we have
P (pp)) 2
If the restricted optimal volume OPT, (P,,, cannot have the minimum volume among all subproblems (P,,, [[1 a)/v1) for < j n. Thus, the volume of this solution must satisfy
((1 1)- (ny)/n) is smaller than the volume of ČDP. then this solution
< <1
= (Pa,
The proof is thus complete.
31

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
Proof of Lemma C.3. By (Carreira-Perpinal & Williams, 2003), there are k' S k local maxima for the density function Pke We will use k' intervals and define the rest of the intervals to be empty. Suppose un S U2 S .... S ukk' IR are the local maxima of ps- The density pv(y) is differentiable, and its local minima and local maxima have to alternate. Hence there are exactly k' -1 1 local minima, denoted by é1, f2..... - with é, E [uj, Uy++]] for all j E {1, 2.... k' - 1}. (Note that there are no local minima less than in or greater than uge since pk (y) + 0 as y + +oo). For notational convenience let t = -o, 4. = oc. Let C C R satisfies Pa(C*)) 2 1 - a and vol(C** = OP aa).
We now show that there exist I,..... .Ix C₁ such that u, I, C 11)11, {,] for all j E [|<]. Pu((U ( 2 21aa, a, and vol(J S vol(C*). ). This would imply the desired conclusion. Consider Sj 5 n [ for all j E [K']. Next we observe for all j E [K'), pæ is monotonically increasing in the interval [ 4y] and is monotonically decreasing in the intervals (ug, Egl. with local maximum at uy. Hence if Sj comprises multiple disjoint intervals within [ej-1, Eg], we can pick one interval with the same volume within [ Ey] that also includes ú and covers at least as much probability mass. This establishes the property of " and hence the lemma.
Proof of Lemma D.I. First, we construct a family of distributions supported on subsets of [0, 1]. Consider an integer m. We partition the interval [0, 1] into m intervals with length 1/m each and define the subinterval A₁ = 1-1 ) for j E [m]] We next define a family of distributions supported on these subintervals. For any vector E {0, 10, let Az = Uj.z, -1 Aj
denote the union of intervals corresponding to the indices where Z, 1. Then, we define the density function
1l E Az} 1 2 Zj
pz (v)
where is the indicator function. Let Pz be the corresponding distribution.
We then construct the weight distribution II. Given any 0, we now provide a restricted set of vectors Z E {0, 1)m such that the distribution Pz has at least
total variation distance to the uniform distribution X. We pick a parameter 3 E (0, 1) depending on and m. Then, we define a set of vectors Z with Az covering approximately 3 fraction of [0, 1].
m
3 m
1/3
2= 10,11
Σ
43 j=1
3
<
For any 7 E 2, we have the total variation distance
1
B
1/3
TV(P2, A) 2 X(42)= =
Ej 1- 3
1/3
Therefore, as long as B
[
S s, we have Pz Pe for all Z Z. We construct the weight distribution IT supported
m
on the PP2 7 E 2}. Let = @i_ (emoulli(3)) be the product distribution on (0, 1mmm such that each coordinate is 1 ii(ZZ))
with probability B. Then, we define IT to be the distribution π1 conditioning on 2, [[)) Ii(2)
We bound TV(X", P2))((2) by chi-squared divergence,
TV \x". f { S "1 SOAr (DpzamzZ))
2 dx 1.
2
Since f (Z) is mixture of product distributions over {P Z E 2} with weights II, we can expand the first term in the right-hand side as
JAAI (DD2aTIZ)) dr = E 2,2 2.2 (J (z(w)ezz (w)de)
By taking the density pz())=
[(rEAz) into the equation, we have I -ET12 2,
(fzlwiez = =
1
1 m7
E Win
=, 2
I
-===1
Zi
1
-
Zz
m 1=1
Z
32

---

Volume Optimality in Conformal Prediction with Structured Prediction Scts
According to the construction of 2, for any vector E 2, we have ブド= Zz 2 3 - (0)) Since Ii is the product of
1/3
Bernoull distribution with probability 3. by the Chernoff bound, we have II E 2) 2 1 - (8/m)4/3. Thus, have
(f
(z(u)ozzw)dzr)
13 z.
8
1/3
2n
m 1
n
8
Z
7 II
m
m j=1
8
1/3
E
7.2' 2
2,77)
T( 2) E 22
=
8 -
ii(2 E 2)
1/3
3
1/3
1 Σ Z3
K
1
E 2
j=1
The last term on the right-hand side can be bounded by
1
1/3
132
1/3
2/2
ZzZ
8² +
+
Σ
Z3
>
8² +
m j=1
m
3=1
B2
1/3
B2
1/3
8² +
+
where the first inequality is using 1 プラ= from the Chernoff bound on the sum of m Bernoulli variables with probability B Combining all bounds above, we have
Z3 <
for m
Zz
>
32 +
[2a
1/3
and the second inequality is
ga
+
92
1/3
g
1/3
TV \r, ( Prau(z))
s
2 1.
1/3
2n
1
1/3
8
is clear that the above bound tends to zero when m - cc. Therefore, for any 5 > O, we have TV TV (X", P2)IT(Z)) < 8
for a sufficiently large m.
Proof of Lemma D.2. The result is a direct consequence of the nested property of (S, (S)(m))im())
33


Reviews:
[{"review_id": "q5wrGKfEPr", "reviewer": "Reviewer_7GWr", "summary": "Conformal prediction is a technique that produces prediction sets with marginal $(1-\\alpha)$-coverage guarantees; in general there are many subsets of the label space that may satisfy this coverage guarantee, and conformal methods do not necessarily produce the smallest such set (by measure) that satisfies this guarantee, or even a set close in measure to the optimal one. This paper studies the problem of obtaining prediction sets that achieve these coverage guarantees while also being the best in terms of size – formally, this is any prediction set whose volume equals the infimum of volumes over sets that satisfy the coverage guarantee – called volume-optimality.\n\nFirstly, the authors prove that there is no distribution-free method that can achieve fully volume-optimal prediction sets, that is, for any conformal predictor $\\hat{C}$ that achieves the marginal coverage guarantee on all distributions, there is some distribution for which it does not produce a volume-optimal prediction set. They move to trying to achieve an approximate version of volume optimality, and restrict themselves to achieving this over the collection $\\mathcal{C}_k$ of unions of $k$ intervals. The high-level idea is to achieve approximate volume-optimality over the empirical distribution defined by the calibration set (which converges in total variation to the true distribution since $\\mathcal{C}$ has finite VC dimension). This can be done by using a dynamic programming approach to efficiently find a union of $k$ intervals that includes at least $(1-\\alpha)$ of the empirical probability weight while satisfying the approximate volume-optimality property. The approach can be generalized in settings with context to achieve conditional coverage guarantees with approximate volume-optimality if you are able to get a good estimate the conditional distribution over the label space. Experiments show that the paper’s approach achieves smaller prediction set size than existing approaches.", "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": "Thank you for your constructive suggestions and insightful questions.\n\n- Since the guarantees are in expectation over the calibration set and the data is being simulated anyway, it could be good to get also the results averaged over multiple draws of the calibration data.\n\nWe appreciate this suggestion. You are right, it is important to get the results averaged over multiple draws. In the revision, we will ensure that all numerical experiments include both the average and standard deviations. In the additional experiments, we show the averages and standard deviations of repeated tests (See our response to Reviewer Ubed for details).\n\n- Question: What is the issue (if any) generalizing this approach to prediction sets in $\\mathbb{R}^n$? Does it blow up the DP space too much? \n\nThis is an excellent question. The DP approach can potentially be extended to low-dimensional spaces, such as dimension $d=2$ or $d=3$, to construct prediction sets that are unions of disjoint rectangles. However, as the dimension $d$ increases, the time and space complexity of DP grow exponentially, making it impractical for high-dimensional settings. Furthermore this is unavoidable; this problem is NP-hard in high-dimensions even for simple generalizations of intervals like Balls (even for one ball). However, we can use our framework with any algorithm that can find low-volume confidence sets (from a prescribed family) in high dimensions. More broadly, finding low-volume confidence sets in high-dimensional settings is an important and challenging task in high-dimensional statistics. Naturally, this is out of the scope of this work. In a followup project, we are currently working on computing approximately small volume prediction sets in high-dimensions like balls and ellipsoids, and unions of them.", "claims_and_evidence": "The theoretical claims all make sense, and the experiments show improvement in terms of prediction set size over existing methods.", "methods_and_evaluation_criteria": "Yes, it seems fine.", "theoretical_claims": "I did not check the proofs in the appendix, but the DP algorithm works and the arguments in the main paper look sound.", "experimental_designs_or_analyses": "The experiments looked good. Since the guarantees are in expectation over the calibration set and the data is being simulated anyway, it could be good to get also the results averaged over multiple draws of the calibration data.", "relation_to_broader_scientific_literature": "This work is concerned with theoretical guarantees / optimality on the size of prediction sets generated by conformal prediction, a relatively less-explored part of the CP literature. It is related to work like Lei et al. 2013, Isbicki et al. 2020, Kiyani et al. 2024, which all similarly consider conformal prediction for regression, though it defines a slightly different kind of volume-optimality, and uses the unique dynamic programming approach to optimize for the prediction set’s volume and define a non-conformity score.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths:\n\nA good deal of work in the CP literature is aimed essentially at making incremental improvements in terms of prediction set size (through empirical testing) without providing theoretical guarantees, so I think the topic of this paper is very relevant and interesting. The technique seems general enough in the sense that if you can come up with an expressive enough collection of prediction sets $\\mathcal{C}$ that you can also efficiently optimize over and use to construct a non-conformity score one could perhaps construct other kinds of useful convex prediction sets in higher dimension.\n\n\nWeaknesses:\n\nDue to considering a more expressive collection of potential prediction sets and optimizing through the DP algorithm, there is probably tradeoff in terms of runtime during the calibration process with more lightweight procedures, and it’s not clear how this runtime performance compares against the other approaches with volume-optimality guarantees.", "other_comments_or_suggestions": "Couple of typos:\n\nLine 083: should be “sets” instead of “set”\n\nFigure 1 (d): should be “sensitive”", "questions_for_authors": "1.\tWhat is the issue (if any) generalizing this approach to prediction sets in $\\mathbb{R}^n$? Does it blow up the DP space too much?", "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": "utJWmSdbXN", "reviewer": "Reviewer_hJ91", "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. This paper studies the conformal label sets for unidimensional regression problems, where the conformal label sets are restricted to be a union of $k$ intervals. The motivation is to minimize the set sizes while maintaining the conformal coverage guarantee.\n\nThe paper first considers the unsupervised setting. It defines the optimal size as the minimum achievable size for label sets restricted to be a union of $k$ intervals. It proposes using dynamic programming to empirically approximate label sets close to the optimal size. Together with the conformal framework, the paper proposes a non-conformity score that achieves close to optimal label set sizes with high probability (quantifying the distance from the optimal and the high probability).\n\nNext, the paper extends similar arguments to the supervised setting. It defines the conditional optimal sizes (conditioned on the covariate) with the same restriction. It proposes using dynamic programming (similar to before) to empirically approximate label sets close to the conditionally optimal sizes. Together with the conformal framework, the paper proposes a non-conformity score that achieves close to conditionally optimal label set sizes with high probability (quantifying the distance from the conditionally optimal and the high probability). It also achieves conditional coverage with high probability.\n\nLastly, the paper includes experimental results to validate their proposed method.", "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": "Thank the reviewer for constructive suggestions and providing comprehensive references. We will make sure to implement these changes and include all related works in the revision.\n\n- It would help to see a similar analysis done on real-world data. \n\nWe evaluated our experiments on various real-world datasets as well for the rebuttal, please see our response to Reviewer UBed for details.\n\n- How does the proposed method compare to the baselines on computational cost?\n\nWe will include the running time comparison. Due to the time complexity of dynamic programming, our method is naturally slower than the baselines. But as we have shown in additional real dataset experiments, the running time of our method while larger is still comparable with that of baselines. Furthermore the running time of our method is dominated by the method for producing the conditional CDF estimate. \n\n- The analysis does not include the standard deviations of the reported quantities. Since \"outperforming\" is a strong word (lines 407-408, column 2), one should consider the statistical significance of the results.\n\nYou're absolutely right that statistical significance is crucial when claiming \"outperformance,\" and we will incorporate the averages and standard deviations of repeated tests to validate the results. For the unsupervised experiments on real-world datasets, we include the average and standard deviations in the result. Please see our reply to Reviewer UBed for details. The standard deviation for volume and empirical coverage is at most 10% and 2.5% respectively. We will make sure to report the standard deviations in all numerical experiments in the revision.\n\n- Since Fig. 1a depicts the best proposed model, Fig. 1b should illustrate the best baseline model (I believe $\\rho=0.25$ is the optimal hyperparameter from the search space chosen).\n\nWe agree that it makes sense for Fig. 1b to show the KDE method with the best bandwidth. We implement the baseline KDE method with $\\rho=0.25$, and we will update the figure accordingly. We wanted to point out that for $\\rho=0.25$, KDE still uses a relatively large interval to cover the left Gaussian, resulting in a total volume of 3.7049, much larger than our method. While the KDE method is very sensitive to the choice of bandwidth, our proposed DP is very stable with the choice of $k$ as long as it exceeds a certain threshold.\n\n- Theorem 2.5 and 3.3 both assume i.i.d. data. How does the statement change if the calibration and test data are exchangeable and not i.i.d.?\n\nIf the data are only exchangeable, we still have the marginal coverage guarantee in Theorem 2.5 and 3.3. The volume optimality and the conditional coverage will not hold since the volume optimality is not well-defined in this case and the conditional coverage is generally impossible without additional assumptions.\n\n- How is the index that satisfies the second requirement in Assumptions 2.4 and 3.1 chosen? Or, how is the index for step 1 in Section 4.1 chosen?\n\nIn Step 1 of Section 4.1, the index $j^*$ depends on $m$, $\\alpha$, $n$ and $\\delta$. The choices of $n$ and $\\alpha$ are clear. For the other two parameters, $m$ stands for the discretization of $[0,1]$ in the nested system, and we typically need $m>1/\\alpha$. Larger $m$ provides finer discretization for the nested system, and $m \\leq n$. The number $\\delta$ stands for the statistical error of estimating the (conditional) CDF. In later numerical experiments, we chose $m=50$ and $\\delta=\\sqrt{(k+\\log n)/n}$ with $k$ being the number of intervals.\n\n- When is the bound in Eq. 8 satisfied?\n\nEq. 8 is always satisfied with high probability, since the VC dimension of $\\mathcal{C}_k$ is $O(k)$.\n\n- Why is $P \\ll \\lambda$ required for the initial analysis in Section 2.1 (lines 76-93, column 2)?\n\nHere, we intend to provide an example of the optimal-volume solution (the display after (3)) under the condition of $P \\ll \\lambda$, which means $P$ is absolutely continuous w.r.t. $\\lambda$. When we introduce the notation of volume optimality in the next display, we emphasize that the condition $P \\ll \\lambda$ is no longer needed.", "claims_and_evidence": "The claims are supported for the most part. I have questions about the experiments and the results (see below).", "methods_and_evaluation_criteria": "1.\tIt would help to see a similar analysis done on real-world data.\n\n2.\tHow does the proposed method compare to the baselines on computational cost?", "theoretical_claims": "I briefly checked the proofs.", "experimental_designs_or_analyses": "1.\tThe analysis does not include the standard deviations of the reported quantities. Since \"outperforming\" is a strong word (lines 407-408, column 2), one should consider the statistical significance of the results.\n\n2.\tFigures 1, 2, and 3 are not easy to see in the main paper.\n\n3.\tSince Fig. 1a depicts the best proposed model, Fig. 1b should illustrate the best baseline model (I believe $\\rho=0.25$ is the optimal hyperparameter from the search space chosen).", "relation_to_broader_scientific_literature": "This paper adds to the previous work on optimal conformal prediction sets. Specifically, this paper looks at the unidimensional setting and studies optimal prediction sets where the sets are a union of $k$ intervals.", "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 explore 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 area of research is well-motivated for practical impact.\n\n2.\tThe theoretical and empirical results demonstrate the benefits of the proposed algorithm.\n\nWeaknesses:\n\n1.\tThe paper is not easy to parse. For instance, the dynamic programming algorithm, one of the key features of the proposed method, is not described well.\n\n2.\tThe experiments are missing real-world data and reporting of statistical significance.\n\n3.\tSeveral important references are missing.", "other_comments_or_suggestions": "1.\tExplain the proposed dynamic programming algorithm (Algorithm 1) in the main paper. It is not easy to follow without any explanations.\n\n2.\tMentioning that the paper deals with unidimensional regression tasks in the abstract and the introduction would help.\n\n3.\tUsing \"structured prediction sets\" in the title is misleading as the structure is limited to the union of $k$ intervals.\n\n4.\tThe coverage, as detailed in lines 193-198, column 2, depends on the exchangeability of the calibration and test data while being independent of the training data.\n\n5.\tThe threshold in Eq. 9 is not defined.\n\n6.\tSimilar to Eq. 6, it would help to write the definition of conditional restricted optimal volume with $\\inf_{C \\in \\mathcal{C}_{k}}$ (in Section 3.1).\n\n7.\tThe paper denotes the constructed label set as a strict subset of the label space, $\\hat{C}(X_{n + 1}) \\subset \\mathcal{Y}$. However, it is not a strict subset and $\\hat{C}(X_{n + 1}) \\subseteq \\mathcal{Y}$.\n\n8.\tThe set value setting is not defined (lines 57-58, column 1).\n\n9.\t\\citet is for textual citations, and \\citep is for parenthetical citations.\n\nTypos:\n\n1.\t\"...score based on dynamic programming, the proposed method...\" $\\rightarrow$ \"...score based on dynamic programming. The proposed method...\" (lines 102-103, column 1)\n\n2.\t\"Among all data-dependent set that satisfies (3), ...\" $\\rightarrow$ \"Among all data-dependent sets that satisfy (3), ...\" (line 83, column 2)\n\n3.\t\"...conformalized KDE is highly densitive to the choice...\" $\\rightarrow$ \"...conformalized KDE is highly sensitive to the choice...\" (caption of Fig. 1d)\n\n4.\tThe citation for Barber et al. [2021] is incorrectly written as Foygel Barber et al. [2021]", "questions_for_authors": "1.\tTheorem 2.5 and 3.3 both assume i.i.d. data. How does the statement change if the calibration and test data are exchangeable and not i.i.d.?\n\n2.\tHow is the index that satisfies the second requirement in Assumptions 2.4 and 3.1 chosen? Or, how is the index for step 1 in Section 4.1 chosen?\n\n3.\tWhen is the bound in Eq. 8 satisfied?\n\n4.\tWhy is $P \\ll \\lambda$ required for the initial analysis in Section 2.1 (lines 76-93, column 2)?", "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": "JgUTaOel0F", "reviewer": "Reviewer_UBed", "summary": "This paper studies the problem of providing guarantees regarding the efficiency (ie, small size/volume and thereby informativeness) of conformal prediction (CP) sets. The paper first presents an impossibility result for volume optimality where any CP method can only find a trivial solution. Then, the paper introduces a definition of “restricted volume optimality” where the CP sets are restricted to belong to a set family of finite VC-dimension, specifically sets that are a union of $k$ intervals. The main algorithm presented leverages dynamic programming and a conformity score based on distributional conformal prediction (Chernozhukov et al., 2021) and nested prediction sets; analysis is given regarding approximate conditional coverage and conditional restricted volume optimality when a ‘good’ estimator of the conditional CDF is available.\n\n## update after rebuttal \n\nMy primary concern was the lack of real-data results--the authors addressed this in their rebuttal with some experimental results on standard UCI tabular datasets, so I raised my score to weak/borderline accept. Unfortunately, the authors did not respond to the remaining secondary questions/concerns I had, so I'll restate those here, to highlight that they were *not* resolved--while I decided to raise my score before hearing back from the authors because I overall think reasons to accept outweigh those to reject, it would have been nice to get clarity on these, to feel more certain about my recommendation....\n\nA couple follow-up questions: (a) Can you confirm what the target coverage was for the supervised setting UCI datasets? It looks like it was 70%, but just checking. (b) If so, why are the new experiments being run with different target coverage levels? **One might worry that multiple target coverage levels were tried for each, and only the best results are reported. In a final version, I think it'd be helpful/important to provide at least a couple examples where the experiments are repeated with a grid of different target coverages (or, even a calibration plot over these values), to see how results vary (or not) accordingly.** Especially since end-users are typically most interested in higher target coverage levels, eg, 90-95%.\n\n**My last remaining concerns were regarding the title (see Claims and Evidence) and references (see Essential References Not Discussed and Relation To Broader Scientific Literature).** These have not been address by the authors' response, though perhaps due to character limits. I hope that the authors will (1) consider updating the title as have suggested, especially as reviewer hJ91 had a similar concern about the title being misleading and (2) incorporating further discussion of some related work on other approaches to improving efficiency of prediction sets.", "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 you for the detailed and constructive feedback and the additional references that we missed. We will implement these changes in the revision of the paper.\n\nWe evaluated our method and different baseline methods on several real-world datasets in both unsupervised and supervised settings, and observed improved or competitive volumes in both settings. \n\nFor the unsupervised setting, we implement our conformalized DP method and the baseline conformalized KDE method on two real-world datasets (Acidity and Enzyme) used in density estimation literature (Richardson and Green (1997)). We set the target coverage at 80%, and repeat the experiments 50 times. We output the average and s.d. for volume and empirical coverage. We observe that our conformalized DP outputs a smaller volume prediction set than the KDE with the best bandwidth for almost all k>=2. \n\n### Acidity Dataset\nConformalized KDE Results\n\n| Bandwidth | 0.1   | 0.3   | 0.5   | 0.7   | 0.9   |\n|-----------|-------|-------|-------|-------|-------|\n| **Volume**              | 2.4927 ± 0.1960 | 2.3934 ± 0.2044 | 2.5749 ± 0.2571 | 2.7617 ± 0.2038 | 2.8196 ± 0.2587 |\n| **Empirical Coverage**  | 0.8401 ± 0.0226 | 0.8092 ± 0.0261 | 0.8133 ± 0.0315 | 0.8013 ± 0.0256 | 0.8021 ± 0.0294 |\n\nConformalized DP Results\n\n| k       | 1     | 2     | 3     | 4     | 5     |\n|---------|-------|-------|-------|-------|-------|\n| **Volume**              | 2.5999 ± 0.1937 | 2.3627 ± 0.1755 | 2.4099 ± 0.1832 | 2.3615 ± 0.1452 | 2.2172 ± 0.1349 |\n| **Empirical Coverage**  | 0.8121 ± 0.0476 | 0.8507 ± 0.0224 | 0.8552 ± 0.0245 | 0.8582 ± 0.0196 | 0.8341 ± 0.0253 |\n\n---\n### Enzyme Dataset\nConformalized KDE Results\n\n| Bandwidth | 0.1   | 0.3   | 0.5   | 0.7   | 0.9   |\n|-----------|-------|-------|-------|-------|-------|\n| **Volume**              | 0.9826 ± 0.0969 | 1.4640 ± 0.0940 | 1.5218 ± 0.1332 | 1.4526 ± 0.1809 | 1.3867 ± 0.1799 |\n| **Empirical Coverage**  | 0.8081 ± 0.0217 |  0.8056 ± 0.0231 | 0.7999 ± 0.0268 | 0.7962 ± 0.0272 | 0.7971 ± 0.0236 |\n\nConformalized DP Results\n\n| k       | 1     | 2     | 3     | 4     | 5     |\n|---------|-------|-------|-------|-------|-------|\n| **Volume**              | 1.2207 ± 0.1188 | 0.8997 ± 0.1414 | 1.0118 ± 0.1975 | 1.0131 ± 0.1878 | 1.0520 ± 0.2002 |\n| **Empirical Coverage**  | 0.8101 ± 0.0461 | 0.8144 ± 0.0353 | 0.8416 ± 0.0390 | 0.8458 ± 0.0379 | 0.8558 ± 0.0353 |\n\nFor the supervised setting, we implement our method and the baseline methods on four UCI datasets Abalone, AirFoil, WineQuality, Superconductivity. These four real-world datasets are used in conformal prediction by Dhillon, Deligiannidis, and Rainforth (2024). We observe that our method outputs prediction sets with smaller volumes than baselines on two datasets WineQuality, Superconductivity. It provides competitive results on the other two datasets Abalone and AirFoil.\nThe most prominent example showing the advantage of using unions of several intervals is the dataset WineQuality. In this dataset, the label Y space is integers from 0 to 10 for the quality of wine. The conformalized DP with 5 intervals clearly dominates all other methods including our own with k=1 due to the multimodality of prediction.\n\n### Abalone\n\n| Method                  | Emp Cov | Avg Vol  | Runtime (s) |\n|-------------------------|--------|---------|-------------|\n| CQR                     | 70.694 | 3.820   | 44.119      |\n| DCP-QR                  | 69.737 | 3.788   | 46.851      |\n| DCP-QR*                 | 68.780 | 3.579   | 48.201      |\n| ConformalizedDP (k = 1) | 69.737 | 3.692   | 166.875     |\n| ConformalizedDP (k = 5) | 68.182 | 3.611   | 659.637     |\n\n### AirFoil\n\n| Method                  | Emp Cov | Avg Vol  | Runtime (s) |\n|-------------------------|--------|---------|-------------|\n| CQR                     | 74.751 | 5.895   | 10.509      |\n| DCP-QR                  | 74.086 | 5.388   | 9.667       |\n| DCP-QR*                 | 72.425 | 5.416   | 9.205       |\n| ConformalizedDP (k = 1) | 70.764 | 5.289   | 51.588      |\n| ConformalizedDP (k = 5) | 74.086 | 6.275   | 224.675     |\n\n### WineQuality\n\n| Method                  | Emp Cov | Avg Vol  | Runtime (s) |\n|-------------------------|--------|---------|-------------|\n| CQR                     | 71.000 | 1.130   | 104.084     |\n| DCP-QR                  | 69.538 | 0.826   | 109.458     |\n| DCP-QR*                 | 69.538 | 0.732   | 109.746     |\n| ConformalizedDP (k = 1) | 72.154 | 0.786   | 302.068     |\n| ConformalizedDP (k = 5) | 73.385 | 0.186   | 1031.165    |\n\n### superconductivity\n\n| Method                  | Emp Cov | Avg Vol  | Runtime (s) |\n|-------------------------|--------|---------|-------------|\n| CQR                     | 70.397 | 13.722  | 3160.658    |\n| DCP-QR                  | 71.197 | 13.803  | 2998.426    |\n| DCP-QR*                 | 71.197 | 12.070  | 3206.956    |\n| ConformalizedDP (k = 1) | 70.938 | 11.808  | 3809.463    |\n| ConformalizedDP (k = 5) | 70.774 | 12.632  | 6163.017    |", "claims_and_evidence": "The main claims appear to be reasonable and supported by evidence. However, I think that the title (which can be viewed as a claim itself) is perhaps too broad for the scope of the paper, in two ways: \n\n(1) Given that other a number of other works have studied optimizing for CP efficiency (e.g., by selection, designing conformity scores, aggregating prediction sets, analyzing efficiency, etc), and given that the main contributions of the paper focus on the notion of “restricted volume optimality,” I think it would be more accurate if “Restricted” were added to the title, eg either as “Restricted Volume Optimality in …” or “Volume Optimality in Conformal Prediction with Restricted Prediction Sets.” \n\n(2) Secondly, in my view I’d suggest removing “Structured” from the title, or at the very least it should be clarified in the paper what is meant by structured (i.e., it seems that it means “restricted,” in the sense defined). That is, it appears that the word “structure/structured” is only ever used in the title and in one subheading--it appears to never be used in the main text of the paper even to explain what is meant by it. When I first saw the paper’s title, I had thought that “Structured” meant multidimensional labels as in structure-prediction tasks, and I think that others could similarly mis-aligned expectations.", "methods_and_evaluation_criteria": "A main limitation of the paper’s evaluation is that the experiments appear to only evaluate on synthetic datasets (e.g., Gaussian data, Censored Gaussian, Mixture of Gaussians, ReLU-Transformed Guassians). The paper’s evaluation would be strengthened by also including real datasets, even real but simple tabular datasets e.g., from the UCI ML repository. Including evaluation on real data is arguably especially important for this paper as some of the methods rely on kernel density estimation (KDE), which will be expected to perform well for synthetic Gaussian or mixture-of-Gaussian data, but could perform worse on data with more complex distributions.", "theoretical_claims": "I briefly looked over the proofs for the main theoretical claims, ie, for the impossibility result (Theorem 2.1), marginal coverage and restricted volumn optimality (Theorem 2.5), and approximate conditional coverage/conditional restricted volume optimality (Theorem 3.3). They seem reasonable, leveraging some standard CP arguments and concentration inequalities.", "experimental_designs_or_analyses": "I reviewed the main experiment settings. As I mentioned previously, a main limitation of the paper is that the experiments appear to only evaluate on synthetic datasets (e.g., Gaussian data, Censored Gaussian, Mixture of Gaussians, ReLU-Transformed Guassians). Evaluation on real datasets would strengthen the evaluation.", "relation_to_broader_scientific_literature": "Whereas the majority of the conformal prediction literature focuses on proving guarantees for coverage with efficiency (volume optimality) only evaluated empirically, this paper focuses on providing theoretical analysis for a restricted form of volume optimality. There are several prior works that study the question of volume optimality in CP, which the authors mention in the introduction and discuss more thoroughly in the Related Work (Appendix A). \n\nIt should be noted that the authors focus on split conformal prediction, and thus their algorithms and main results (Theorem 2.5) and (Theorem 3.3) should be noted to provide optimality only within the split conformal framework, although as they note it seems that much of the analysis could extend to full conformal. (I.e., the restricted volume optimality results include the size of the calibration set $n$ in the guarantee; in full conformal, the data are used more efficiently and so the calibration set would effectively be larger; relatedly, cross-validation-style CP methods also make efficient use of the data, but would likely require further analysis.) \n\nIt may be relevant for the authors to mention in the “Other Related work” section (or may simply be of interest to the authors for future work) the literatures on (1) aggregating prediction sets to achieve greater efficiency, which often takes a form of cross-validation-style CP, and on (2) selecting prediction sets based on efficiency. The following are relevant references that the authors may be interested in looking at or mentioning to acknowledge this broader literature on improving the efficiency of CP sets: \n\n*Papers on cross-validation-style aggregation of split CP sets (which empirically tend to be more efficient than split CP sets):*\n- Vovk, V. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74(1):9–28, 2015.\n- Vovk, V., Nouretdinov, I., Manokhin, V., and Gammerman, A. Cross-conformal predictive distributions. In Conformal and Probabilistic Prediction and Applications, pp. 37–51. PMLR, 2018.\n- Barber, R. F., Cand`es, E. J., Ramdas, A., and Tibshirani, R. J. Predictive inference with the jackknife+. The Annals of Statistics, 49(1), 2021.\n- Kim, B., Xu, C., & Barber, R. (2020). Predictive inference is free with the jackknife+-after-bootstrap. Advances in Neural Information Processing Systems, 33, 4138-4149.\n- Prinster, D., Liu, A., and Saria, S. Jaws: Auditing predictive uncertainty under covariate shift. Advances in Neural Information Processing Systems, 35:35907–35920, 2022.\n- Prinster, D., Saria, S., and Liu, A. Jaws-x: addressing efficiency bottlenecks of conformal prediction under standard and feedback covariate shift. In International Conference on Machine Learning, pp. 28167–28190. PMLR, 2023.\n\n*Other papers on aggregating/selecting CP sets based on efficiency:*\n- Liang, R., Zhu, W., & Barber, R. F. (2024). Conformal prediction after efficiency-oriented model selection. arXiv preprint arXiv:2408.07066.\n- Yang, Y., & Kuchibhotla, A. K. (2024). Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, 1-13.\n\n*Miscellaneous other paper with length optimality result:* \n- Teneggi, J., Tivnan, M., Stayman, W., & Sulam, J. (2023, July). How to trust your diffusion model: A convex optimization approach to conformal risk control. In International Conference on Machine Learning (pp. 33940-33960). PMLR.", "essential_references_not_discussed": "In my view, a more comprehensive related work section would cite many of the references I provided in the “Relation To Broader Scientific Literature” section to at least acknowledge this related literature on designing CP sets for efficiency (i.e., either by aggregating, selecting, or optimizing). However, among those references, perhaps the most relevant is Liang et al. (2024), as well as a couple references on cross-validation-style CP/aggregating prediction sets, to acknowledge that literature.", "other_strengths_and_weaknesses": "*Other strengths:* Overall, the paper provides an interesting perspective on the efficiency of CP sets, with potentially promising methods.\n\n*Other weaknesses:* Occasionally the language is a bit informal in a way that can distract or be ambiguous, for instance the authors state that they “believe” XYZ rather when perhaps “conjecture” would be more appropriate. For instance, they state “Though not explicitly stated in (Chernozhukov et al., 2021), we believe that the DCP procedure essentially achieves (12) for k = 1” and “We believe the comparison between the full conformal versions of the two methods will lead to the same conclusion.”", "other_comments_or_suggestions": "NA", "questions_for_authors": "Overall, as I’ve mentioned, my main concern for this paper is that I think some experiments on real datasets (even simple tabular UCI datasets) should be provided, in addition to the synthetic-data experiments. Secondarily, addressing my comments on mentioning other related literature on combing CP sets, as well as revising certain informalities in the writing, would improve it in my view. \n\nIf some real-data experiments (e.g., on say 3 UCI datasets) were added with results that supported those of the current experiments, I would consider improving my evaluation of the paper; addressing the secondary concerns around mentioning related literature and revising the writing would further help.", "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": "UBrHJevByd", "reviewer": "Reviewer_PPwk", "summary": "The submission studies volume minimization in conformal prediction. It proposes a dynamic programming algorithm to construct prediction sets with marginal (and approximate conditional) coverage. The sets returned by the method have provably optimal volume within the class of union of k intervals. Experiments on synthetic datasets support the claim that the proposed method minimizes the interval length compared to existing alternatives.", "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 thank the reviewer for detailed suggestions and providing more related works. We will ensure to make these changes to improve our paper and include discussions to related works. \n\n- Experiments on real-world datasets would strengthen the utility of the proposed method\n\nWe implement our method and baselines on real-world datasets (See response to Reviewr Ubed for details). We also include the runtime comparison.\n\n- A comparison of runtimes would help practitioners understand the tradeoffs between the different methods.\n\nWe will include the runtime comparison in the revision.\n\n- Kiyani et al, 2024 \"Length Optimization in Conformal Prediction\" also studies optimality of prediction sets with an efficient algorithm for hypothesis classes with bounded complexity. It would be important to discuss the relation between the theoretical findings in this submission and this previous work. Furthermore, comparing the two algorithms would strengthen evidence.\n\nWe have a discussion about Kiyani et al, 2024 in Appendix A. We will include the comparison with them in the revision. \n\n- Teneggi et al, 2023 \"How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control\" also considers mean interval length minimization for conformal risk-control in high-dimensional settings.\n\nWe will discuss Teneggi et al, 2023 in the related work section. \n\n- Connections with hypothesis testing: Could the authors expand on this connection?\n\nSince both coverage and volume are two measures of sets (one is the data generating probability and the other is the Lebesgue measure), the volume optimality problem subject to coverage property is naturally connected to hypothesis testing between the two measures. This is exactly how we prove the impossibility result in the unsupervised setting.\n\nSuch a connection also holds when one considers conditional coverage and conditional volume optimality, and a similar impossibility result would hold.\n\nMore generally, one could consider (conditional) coverage and (conditional) restricted volume optimality. This is exactly the conformal prediction framework that we consider in the paper. While we proved that the proposed DP method satisfies both guarantees, it would be interesting to also study the sample complexity of the problem. To be more specific, one could ask if the coverage slack of order $\\sqrt{(k+\\log n)/n}$ in Theorem 2.5 is optimal or not. We believe the lower bound approach for this problem could also be tackled via the hypothesis testing connection. This will be a very interesting direction to explore in the future.\n\n- Is this algorithm optimal in terms of complexity? Or could, for example, the last step of selecting the solution with minimum volume be avoided?\n\nThe final step of selecting the minimum volume solution can indeed be avoided by maintaining the best solution directly within the DP table. However, this does not improve the overall time complexity since the last step takes only $O(kn/\\gamma)$ time. \nIn practice, it is still possible to approximately implement this algorithm more efficiently through various tricks, for example by bucketing the samples.\n\n- In Proposition 2.3, what is the role of point 1. ? How does this property of the algorithm play a role in the rest of the contributions?\n\nPoints 1 & 2 jointly guarantee that the output of the DP algorithm achieves the coverage and the restricted volume optimality with respect to the empirical distribution. Then, together with the uniform concentration, it leads to the restricted volume optimality with respect to the distribution of the testing sample in Point 2 of Theorem 2.5.\n\n- Lines 27-30, right column: CP also provides a coverage upper-bound, which guarantees the sets are not trivial.\n\nYou are correct. We will change the wording here in the revision.\n\n- Lines 119-127, right column: I understand $P^{n+1}$ is the measure of the test point. For $P^{n} \\times \\lambda$, does $P^{n}$ mean the measure of all previously observed points?\n\nWe have training data $X_1, …, X_n$ and testing data $X_{n+1}$. The $P^{n+1}$ is the joint distribution of all $n+1$ samples. In $P^{n} \\times \\lambda$, $P^n$ means the joint distribution of the training data with $n$ samples.\n\n- Lines 292-294, right column: it is true that the construction is only needed for the calibration points, but it also needs to be performed for each new point at inference, which can be expensive.\n\nThe computational bottleneck is the construction of the nested system $\\{S_j(x)\\}{j\\in[m]}$. It needs to be constructed for all calibration points $\\{X_{n+1},...,X_{2n}\\}$, together with the testing point $X_{2n+1}$. The $n+1$ nested systems are sufficient to evaluate the conformity score at each $y\\in\\mathbb{R}$.\nOn the other hand, if one has more than one testing point, say $X_{2n+1}, …, X_{2n+r}$, then the nested systems will need to be computed for each individual one, and you are correct that it may be expensive when $r$ is large.", "claims_and_evidence": "Evidence supports claims.", "methods_and_evaluation_criteria": "Experiments support the theoretical claims made in the paper. \nExperiments on real-world datasets would support the practical utility of the proposed method.", "theoretical_claims": "Proofs of Theorem 2.1 and Proposition 2.3", "experimental_designs_or_analyses": "Experiments use synthetic distributions published in existing literature.", "relation_to_broader_scientific_literature": "Volume optimization is a topic that has gained significant attention in conformal inference literature. The submission bridges concepts of dynamic programming with distributional conformal prediction, which are well-established in their respective sub-areas.", "essential_references_not_discussed": "All essential references are discussed.", "other_strengths_and_weaknesses": "**Strenghts**\n* The paper is well-written\n* The topic of volume optimization in conformal inference is timely\n* Being able to construct sets that are union of intervals is important for multimodal distributions\n\n**Weaknesses**\n* Experiments on real-world datasets would strengthen the utility of the proposed method\n\nI will expand on a few comments and questions and I am looking forward to discussing with the authors!", "other_comments_or_suggestions": "**Prior works on volume minimization**\n\n*Kiyani et al, 2024 \"Length Optimization in Conformal Prediction\"* also studies optimality of prediction sets with an efficient algorithm for hypothesis classes with bounded complexity. It would be important to discuss the relation between the theoretical findings in this submission and this previous work. Furthermore, comparing the two algorithms would strengthen evidence.\n\n*Teneggi et al, 2023 \"How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control\"* also considers mean interval length minimization for conformal risk-control in high-dimensional settings.\n\n**Connections with hypothesis testing**\n\nCould the authors expand on this connection?\n\n**Proposed algorithm**\n\nA brief high-level description of the intuition behind the DP algorithm in the main text would increase accessibility of the submission to a broader audience.\n\nIs this algorithm optimal in terms of complexity? Or could, for example, the last step of selecting the solution with minimum volume be avoided?\n\nIn Proposition 2.3, what is the role of point 1. ? How does this property of the algorithm play a role in the rest of the contributions?\n\n**Experiments**\n\nA comparison of runtimes would help practitioners understand the tradeoffs between the different methods.\n\n--\n\n**Minor Comments**\n* Lines 27-30, right column: CP also provides a coverage upper-bound, which guarantees the sets are not trivial.\n* Lines 119-127, right column: I understand $P^{n+1}$ is the measure of the test point. For $P^{n} \\times \\lambda$, does $P^{n}$ mean the measure of **all** previously observed points?\n* Lines 292-294, right column: it is true that the construction is only needed for the calibration points, but it also needs to be performed for each new point at inference, which can be expensive.", "questions_for_authors": "I do not have any further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Conformal prediction is a general uncertainty quantification framework which can produce prediction sets from a given black-box predictive model. Coverage (whether the true output is present within the set or not) and prediction set size (efficiency) are two important metrics. Although there is a lot of theoretical work on coverage guarantees, there is relatively less work on guarantees for prediction set size. The focus of this paper is on this later challenge for single-target regression tasks where prediction sets are restricted to be a union of intervals. It gives an impossibility result for volume optimality followed by an algorithm based on dynamic programming to achieve restricted volume optimality. The paper also presents analysis for approximate conditional coverage and conditional restricted volume optimality when a good estimator for the conditional CDF is available.

All the reviewers' were positive about the paper but also asked constructive questions. The author rebuttal answered their questions satisfactorily. Therefore, I recommend accepting this paper.
Decision: Accept (poster)