Probabilistic Conformal Prediction with Approximate Conditional Validity
Authors: Vincent Plassier
Alexander Fishkov
Mohsen Guizani
Maxim Panov
Eric Moulines
Venue: ICLR 2025 Poster (2025)
Keywords: Conformal Prediction
Conditional coverage
Probabilistic method
Uncertainty Quantification
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We introduce a method that effectively integrates conformal approaches with an estimate of the conditional distribution to ensure the approximate conditional validity.

Abstract: We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution $\textup{P}_{Y \mid X}$. Existing methods, such as conformalized quantile regression and probabilistic conformal prediction, usually provide only a marginal coverage guarantee. In contrast, our approach extends these frameworks to achieve approximately conditional coverage, which is crucial for many practical applications. Our prediction sets adapt to the behavior of the predictive distribution, making them effective even under high heteroscedasticity. While exact conditional guarantees are infeasible without assumptions on the underlying data distribution, we derive non-asymptotic bounds that depend on the total variation distance of the conditional distribution and its estimate. Using extensive simulations, we show that our method consistently outperforms existing approaches in terms of conditional coverage, leading to more reliable statistical inference in a variety of applications.

Published as a conference paper at ICLR 2025
PROBABILISTIC CONFORMAL PREDICTION WITH APPROXIMATE CONDITIONAL VALIDITY
Vincent Plassier Alexander Fishkoy 1.4+ Mohsen Guizani'
Maxim Panov! Eric Moulines
"Mohamed bin Zayed University of Artificial Intelligence ?CMAP, École Polytechnique
'Lagrange Mathematics and Computing Research Center
*Skolkovo Institute of Science and Technology maxim. w
@mbz uai ac.ae
eri..moouLneeepppptrechii.eeeee edu
ABSTRACT
We develop a new method for generating prediction sets that combines the flexi- bility of conformal methods with an estimate of the conditional distribution PYIx- Existing methods, such as conformalized quantile regression and probabilistic con- formal prediction, usually provide only marginal coverage guarantee. In contrast, our approach extends these frameworks to achieve approximate conditional cov- erage, which is crucial for many practical applications. Our prediction sets adapt to the behavior of the predictive distribution, making them effective even under high heteroscedasticity. While exact conditional guarantees are infeasible without assumptions on the underlying data distribution, we derive non-asymptotic bounds that depend on the total variation distance between the conditional distribution and its estimate. Using extensive simulations, we show that our method consistently outperforms existing approaches in terms of conditional coverage, leading to more reliable statistical inference in a variety of applications.
INTRODUCTION
Conformal prediction methods are widely used to construct prediction sets because they provide finite- sample validity under minimal distributional assumptions (Vovk et al., 2005; Shafer & Vovk, 2008). The split-conformal approach leverages calibration dataset of size n, denoted as {(X,, Y2) hRejo]
with X E Rd and Yz E y, to construct prediction sets Car at a specified confidence level
(0, 1). Given a conformity score function V: IRd y - IR the conformal prediction set for test point æ E Rdd is defined as:
C. (x)) y ((x S Q1 n (n+1 E" K 8v(X..))) +
1 n n+1 [x)
(I)
where 5, denotes the Dirac mass I, and Q1-a( represents the (1 -qqunntllle of the probabil- ity measure μ.. This formulation guarantees valid marginal coverage while being computationally efficient. However, its performance may degrade under distributional heterogeneity, motivating extensions to adapt to varying noise levels. If the calibration data {(X,, Ye) is drawn i.i.d. from a population distribution Px,y, then for any new data point (Xn+1. Yn+1) ~ Px, sampled in- dependently of the calibration data, the conformal theory ensures the marginal validity of C. (Xn+1), meaning that IP (Yn+1 C. (X.+1)) 2 1- 1 a. This marginal guarantee can hide significant discrep- ancies the coverage of different regions of the input space Rdd, see e.g. (Izbicki et al., 2022; Hore & Barber, 2024). Conditional validity is a more desirable guarantee than marginal validity: for any Rdd, the set C, (x) conditionally valid
IP (Yn+1 C. (Xn+1) X = x) 2 1-a.
However, this property cannot be achieved without further assumptions about the data distribution; see (Vovk, 2012; Lei & Wasserman, 2014). For practical purposes, it is enough to construct sets C, which approximate (2), and ideally achieve it asymptotically under suitable conditions in the limit of large sample size n.
Equul contribution

---

Published as a conference paper at ICLR 2025
RELATED WORK
Conformal prediction with conditional guarantees. Much research has been devoted to this problem, starting with the case where y R: see (Foygel Barber et al., 2021). For example, Romano et al. (2019) and Kivaranovic et al. (2020) proposed methods based on estimates of the lower and upper conditional quantile functions which are then conformalized. Sesia & Candès (2020) have shown that the constructed interval converges to the narrowest possible interval that achieve conditional coverage. We stress that these methods are specifie to the case y = R. In addition, when the conditional distribution Py|x is multimodal, restricting prediction to intervals is suboptimal; see (Wang et al., 2023) for a discussion.
Conformal prediction based on estimates of conditional distribution. A number of studies have focused on the construction of prediction sets using an estimator of the conditional distribution J In the case where y = IR, Cai et al. (2014) and Lei & Wasserman (2014) have constructed prediction intervals based on a conditional density estimator and have established their asymptotic validity under appropriate conditions. More recently, Han et al. (2022) have employed kernel density estimation to construct asymmetric prediction bands. However, this method is inherently limited as it produces a single interval and thus cannot effectively capture the multimodality of the predictive distributions. On the other hand, Sesia & Romano (2021) partition the domain of Y into bins, forming a histogram- based approximation of Py|x. The authors demonstrated that their method satisfies marginal validity while achieving asymptotic conditional coverage; see also (Lei et al., 2018). Asymptotic conditional coverage is also obtained using cumulative distribution function estimators (Izbicki et al., 2020; Chernozhukov et al., 2021). Guha et al. (2024) introduced an approach that reformulates regression tasks as classification problems by discretizing the output space into bins. This discretization enables the approximation of the conditional density, facilitating the construction of prediction sets that align with the highest posterior density (HPD) regions. However, a key limitation of this method is the computational cost associated with fine- -enaiidi discretization, as the number of labels required for complex scenarios can become prohibitive. In a complementary direction, Kiyani et al. (2024) proposed a method enhance adaptive coverage by learning family of weights that dynamically adjust the quantile of the conformity score based on the covariate x. Their approach ensures that the conditional coverage remains close to the target level 1 a. (Guan, 2023; Alaa et al., 2023; Hore & Barber, 2024) develop a localized conformal inference approach that partitions feature space and applies conformal prediction within neighborhoods, aiming to achieve doser-to-conditions. validity by accounting for conditional distribution; see (Romano et al., 2020a; Melki et al., 2023).
Conformal prediction for multi-output regression. Very few studies have explored the setting where the prediction target is dimeni-dimessoonal, i.e., y = H2 with q > 1. Wang et al. (2023) proposed the PCP method, which leverages implicit conditional generative models (CGMs) to generate samples from the conditional distribution. The method constructs prediction sets as unions of balls centered at -GMggenerated samples. However, a key limitation of PCP lies in using a fixed-radius ball across the space. This design can lead to over-coverage in low-variability regions, where a smaller radius would suffice, and under-coverage in highly dispersed areas, where a larger radius is needed capture the conditional distribution fully. This underscores the need for more adaptive methodology to adjust the size of prediction sets in response to local variability in the data.
Our work addresses these challenges through the following main contributions.
We propose new CP2 method for constructing confidence sets that adapt to the local struc- ture of the data distribution, capable of addressing complex multi-dimeesional prediction tasks where y = RR. Our approach is versatile in accommodating scenarios involving either an explicit conditional density estimator or an implicit generative model; see Section 2.
We develop a thcoretical framework to analyze the propertics of the proposed CP2 method, establishing both its marginal and approximate conditional validity. Furthermore, we demonstrate that asymptotic conditional coverage is attainable under a weak consistency assumption on the predictive distribution; see Section 3.
We demonstrate the effectiveness of the proposed method through series of experiments on synthetic and real-world datasets. The results indicate that our approach consistently outperforms existing methods in terms of conditional coverage. Specifically, it excels in handling classical regression problems, effectively addressing multimodality. and proves robust in the more challenging setting of multidimensional prediction tasks; see Section 4.
2

---

Published as a conference paper at ICLR 2025
2 THE CP² FRAMEWORK
2.1 CONFORMAL. PREDICTION ASSISTED WITH DISTRIBUTION ESTIMATOR
Problem setup. Our goal is to construct marginally valid predictive sets with approximate conditional validity. To achieve this, we adopt the split-conformal approach to conformal inference (Papadopoulos et al., 2002; Papadopoulos, 2008; Romano al., 2019; Plassier et al., 2024). Specifically, partition the data into two disjoint subsets: training set, T {(X,, ) and calibration set, C C= {(X,, Y=) We assume that the training and calibration samples are mutually independent and i.i.d. according to the distribution Px,y over the feature space R2 and response space y The target space y/ may be either discrete or continuous, allowing for broad applicability of the method.
Conditional distribution estimator. We assume that an estimator [yy xx of the conditional probability Pyix is learned from the training data T. A well-established body of research exists on nonparametric conditional density estimation, with classical approaches relying on smoothing techniques such as kernel smoothing and local polynomial fitting; see e.g. (Rosenblatt, 1969; Hyndman et al., 1996; Fan & Yim, 2004). An alternative strategy reformulates conditional density estimation as regression task, enabling the use of nonparametric regression methods to approximate the conditional density. More recently, generative approaches based on deep neural networks have been proposed, allowing for efficient sampling from the conditional distribution; see (Abadi et al., 2016; Zhou et al., 2021) for examples. In what follows, we treat the choice of this estimator / generator as black box.
Probabilistic Conformal Prediction (PCP). Having access to samples from the conditional distribution, one, following Wang al. (2023), may define the prediction set as R2(x;;) == M B(Y,,t), t), where B(y, t) is ball of radius in Y centered at y. The set R2 t) and depends on exogenous variables Z (f....., YM,), where each Y; is sampled condi- tionally independently from the conditional generative model x= Now one can define a confidence score Vz(z,8) y) = inf (t 2 0: y E Rz(x; (x; {)). In the case of PCP the score becomes M (z,2,,) = =in 1ly - Y.ll- The conformity scores Vz, (X2, Yx) can be used in Split-CP frame- work straight ahead. The resulting confidence sets C. (1x) given by (1) satisfy marginal coverage guarantees if marginalization is done over all the random variables involved, i.e. X,Y and Z. This confidence set adapts to the conditional distribution at a given point as depends on samples from this distribution. However, still the sets at different points share the same radius parameter t. The further adaptation of pointwise radius can improve conditional coverage.
Motivation:
Towards conditional coverage. Conditional coverage is automatically satisfied for methods based on confidence scores of the form (2 9) = inf (t 2 0 | y E R2(x;t)], provided that one considers the oracle set:
(x {y E where t, is defined using the true predictive distribution Py|x=r as:
E in 2 0 (R2 (z: 2 a1.
(4)
The oracle set (3) guarantees both conditional and marginal validity. However, in practical settings, the true conditional distribution Py is unknown, and only estimate Hy|x== is available. Substituting x= directly into (4) and (3) introduces estimation errors, which can compromise both marginal and conditional coverage guarantees.
2.2 CP2 FRAMEWORK
There are several main ingredients for our approach:
1. In classical conformal prediction, the shape of the prediction set is determined by the score function V(x, y); see (1). Our approach builds on this framework by introducing family of confidence sets (x;; t), explicitly parameterized by E T, where T C R and E 2 represents a vector of auxiliary variables. In most cases, the index set can be chosen as either T I or T R.. For these confidence sets to be well-defined and meaningful, we impose the following key assumptions: (a) Monotonicity: The size of (x; increases with t for any 2 Z. Furthermore, the entire output space y is covered by JLeT (æ; t); (b) Continuity: The mapping t + R2 (x; t) exhibits a suitable form of continuity. Specifically, we assume the following mathematical property:
3

---

Published as a conference paper at ICLR 2025
Table I: Confidence sets [x; t) found in the literature and also discussed in (Gupta et al., 2022).
Lei et al. (2018)
Lei al. (2018)
Kivaramovic et al. (2020)
[pred(2) f, pred(a)) (x)) +]
[pred(at) - ta(()) pred(z) + ta(x))
(a, 9t-u/2(a)] ////2(a))
Chemozhukov et al. (2021)
Romano ct al. (2019)
Sesia & Candés (2020)
(((())
Moya(a) 4, (,0)0/2(2) 1
911 1 ((9)-//2())) 9,/2(1))
H1. For any (x I2 Z, the confidence sets (2; are non-decreasing. =1 (1; = O, (x; = V. In addition, for any E T, (2;t)) (2;1)).
Example 2.1. For instance, (x;;; t) can be chosen conditional mean Py|x with radius t. There is no auxiliary variables then an we remove subscript Examples of confidence intervals specialized the case where y = R are given in Table 1. Example 2.2. If the predictive distribution is multimodal, ball centered around the predictive mean often fails to provide an informative prediction set. Ideally, (x; t) should correspond to the set with the highest predictive density (HPD) of Pyjx. However, HPD regions are difficult to determine in practice, even when Py|x is available. One of the viable options is given by PCP approach (Wang et al., 2023) for which prediction set (z L) = L B(Y,,) () with = (Ýi,... Yus) E 2 and each Y; being an independent sample from -yy|x=
ball centered around an estimate of
2. As diseussed above, natural choice for the confidence score is the minimal size of the set required to cover the observation y at the input x for the auxiliary variables 2: Vz(x, y) = inf (t T: y Rx(x;))}
3. The key step within the proposed approach is to adapt conformal prediction method by pointwise adaptation of the confidence set radius While the oracle radius (4) is not achievable, we will develop data-driven procedure to approximate it. First, it is convenient to introduce a function fv) parameterized by т. Such function aims to transform the conformity score v and was introduced (albeit in slightly different form) in (Han et al., 2022; Deutschmann et al., 2024; Plassier et al., 2025). Examples of such a function are (v) = Tu and fr = T + v. We assume that:
H2. There exists E T such that r E T + f+(()) is increasing and bijective. In addition, T + (v) is increasing for any 7 E T.
We define Ta, using the estimated predictive density Iyy]x== according to
Tx = inf {- E T: (R,
2 1- a).
(5)
It is easily shown that for any a E (0, x E Rd. 2 E Z, it holds Te.s T and Ty|x== (Rz fr. (s))) 2 1 a; see Lemma A.3.
4. The resulting procedure works follows. Let Z define probability distribution on Z. The standard choice is to use conditional distribution as a sampler: 11 2 IT Y|X==' For & E (1.....,) n we set Tk == Txx.2. and V == Vz, (Xx, Yss,, where {Zx 1m k= are sampled con- ditionally independently from Il2|x=X, Given X E Rd we sample Zn+1 11 independently from {(XR, YR, Zu) ZR]]k=r- and construct the resulting CP2 prediction set
Ca(Xn+1) Rz. (Xn+1i STm (1)a))))))
(6)
where (u)) the (1 - a) -uqantie of the distribution fhn given by
Σ 6
+ n n+11 6x
1
In
The transformation fu + (u)) balances the following two factors: (a) The optimal parameter V=(x,)) y) ensuring that y is included in the confidence set R2 Vz v)); (b) The parameter Tu,z obtained from the probabilistic model Ny|x==.
We stress that Cp2 is general framework that can be adapted to many choices for conditional predictive density estimates, constructing the family of confidence sets, and selecting the calibration function (v). However, we start with the simple example that shows that CP² is more general than the classical split-conformal CP approach.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 CPP-PCP
Input: dataset ((Xx, kejm)) significance level a, conditional distribution Tyy,,, function ft- I/ Compute the (1 quauntile
for k = 1 to do
Sample { MM and { MM from -xxxx=X=
Set V/2 min M || Ykll
Set Tы (t (()) [Q (Q
miink 18,, -8.111111)
Q1-a (kx) - [1 (n + 1) smallest value in {sr (Ve) foot // Compute the prediction set for a new point x E Rd
Sample = = [ and { 1M from -lyx==
Set T=.= = (t + f((l)) {Qi- (0h-aMMM11 Σ)= miin 11',- -v11
Output: Cx) = , BY,,, (4...(1-1101 (Qn-)(un))).
Simple example of CP² We begin with a simple application of CP² to highlight its differences from the basic conformal approach, with y = I. The calibration sets are defined as: R(x;)) = {u e )): ly (x) t} for E R+. There no auxiliary variables z in this case, so we omit from the notation. Assumption H1 is easily isfied with = R+. We then take f+(w) = TV, T E IR, and p = 1: H2 also satisfied. Note that (. = v/T for E Ri. Using the Cp² approach, we find that v2 = ly pr))(=)). which corresponds to a standard conformity score. The classical conformal prediction method defines the (1 a) quantile based on the associated em- pirical measure Un = n+1 Ek= Sv, + 0zc
data
Cp2
CP
0.0
0.2
0.4
0.6
0.8
1.0
Figure I: Predictions sets obtained via the stan- dard CP and CP2 methods.
where V = Y prre((x)]-- CP² differs from the basic conformal approach by introducing 7)) a- as in (5), where [pred(z) = r] [pred (x) T, pred(x)) r). The prediction set becomes (xr) + Sr,
To arg min(f E T: myjx ([pred(z)
where x+1 1==1 Ov,/T + n O To illustrate the advantage of our method, in Figure we present the prediction sets obtained with the classical CP method and CP2 in the case of Neal's funnel-shaped distribution in 2 dimensions; see (Neal, 2003, Section 9).
Mn
CP² with Highest Predictive Density regions: CP2-HPD. The natural approach for the general case is to use the conditional distribution Pyix== or its estimate Tyyxx= to find Highest Predictive Density (HPD) regions and calibrate their size with the help of CP². We develop the respective general algorithm CP2 in Appendix C. However, the procedures find HPDs are usually highly non- trivial and we only investigate this approach experimentally for synthetic data; see Section 4.1. Next, we provide a specific implementation of our general CP² framework that is universally applicable.
CP² with Implicit Conditional Generative model: CPP-PCP. We also develop second instance of the Cp2 algorithm, inspired by Wang et al. (2023). Unlike CP²-HPD, this approach does not require the conditional density. It is designed for cases where the conditional generative model (CGM) Iy is implicit: we cannot evaluate it pointwise while being able to sample from For each calibration point Xg, we draw M random variables ( M from Iy|x==X= We denote Z (Vr.,..... VE,M) and consider the confidence sets as the union of balls centered around the sample points Rz, (Xa; t) = 1(M,,, ()) t). With such choice, we get V42 = min
M || Yx,ill
We then draw a second sample { and compute тr- = infft E R4; M 2= 1(yke E Rz, 2 1 - a}. It is casily seen that
T = (1 + (()) {e
E1z 6 mini? Mr, ||8r, -P..1-P...1)
5

---

Published as a conference paper at ICLR 2025
Given new imput X E R sample Zn+1 (Yn+11,,.... Yn+1,Ms) and obtain prediction set Ca (x = E y: min lly Yatisl S STA+I 1 (Qi-a (
where pn given in (7). The CP2-PCP method employs the same type a confidence set R= t) as the one used by PCP and corresponding confidence score V= y). However, the key distinction between the two algorithms lies in the additional parameter Ta. for CP2-PCP, which requires the generation of second random sample from Ily |X=]x=== This method is especially useful when solving equation (5) is intractable. We summarize CP² CP²-PCP in Algorithm
3 THEORETICAL GUARANTEES
In this section, we provide both marginal and conditional guarantees for the prediction set C, (ar) given in (6). The validity of these guarantees is ensured by the exchangcability of the calibration data, with the exception of Theorem 3.3 which relies on a concentration inequality and thus requires i.i.d. calibration data.
Marginal and conditional validity of CP² The following theorem establishes marginal validity of the predictive set defined by CP²
Theorem 3.1. Assume H1-H2. Then, for any a E (0, 1), it holds - (Yn+1 E Co (X 1)). Moreover, if the conformity scores {.5 (V+)) 1 are almost surely distinct, then also holds that (Yn+1* E CXn+1)))
a+ (n +)=1.
This is the standard conformal prediction result applied to the scores {f== (V)) and its proof is postponed to Appendix A. Importantly, the upper bound on the coverage always holds when the distribution of f (V&) ) is continuous.
Now, we will investigate the conditional validity. Denote by drv the total variation distance and by pT the conditional probability given the training data.
Theorem 3.2. Assume H IHH and let (0, 1). For any Red and 2, it holds
TPT (Yn-1 E Ca (Xn+1, (X++1,Zn1)) = (xx 2 1 - a drv ( Illyl=lxx - Pn-1 12,22, 2), (V,+VV++)) ( S (X Zn+1) = (I, (1,
where Pa+1 (z. 2) = TT (Q1-a(Pm) < fr.1
The proof is postponed to Appendix A.1. This result shows the role of the accuracy of conditional distribution estimator: the more accurately the estimator Iy x= approximates the true conditional distribution Py|x==, the closer the result will be to 1 - The second term in the lower bound is Pa+ z). Its expected value is upper bounded by Elpx+1 2)] & a, and non-asymptotic bounds for this error term are developed in Appendix A.2.
Asymptotic conditional coverage for CP". In the following theorem, we examine the asymptotic conditional conformal validity as the size of the training dataset, my, goes infinity with n. To make the dependency of the estimator on the size of the training set explicit, we will denote the conditional distribution
II y Consider the following assumption.
H3. There exists sequence (rw) such that lim P(dry (Px.y;Px 1x S rx) =xx)=1. =. 100000
In most interesting case, we have lim, Fn = Such types of bounds can be deduced from (De- vroye & Lugosi, 2001, Chapter 9). Let (X, Y, 2) and (x, Z) be random variables distributed according to Px,Y Iīzz and Px x II I 22z respectively.
Theorem 3.3. Assume HI-H2-H3 hold.
If the distributions of STL (V2((V) and
f (x, are continuous, then, it holds PTT (Yn+1 E (X(x1))) | Zu+1) 1 (0OOVVnnnooo rrm)
In (Lei et al., 2018; 80 Izbicki et al., 2020; Sesia & Candès, 2020), the asymptotic conditional validity is demonstrated by assuming the consistency of their methods' estimators. For instance. Romano et al. (2019) assume that the conditional quantile regressor converges in L towards the true quantile with high probability.

---

Published as a conference paper at ICLR 2025
3F
0173
30
(a) Data and MDN estimate
(b) Conditional coverage
(c) Length of the prediction set
Figure Experimental results on synthetic data in the multimodal case.
4 NUMERICAL EXPERIMENTS
In this section, we conduct comprehensive analysis demonstrating the advantage of CP² compared to standard and adaptive split conformal algorithms. Specifically, we benchmark our algorithm against several state-of-the-an methods: Conformalized Quantile Regression (Romano et al., 2019), Conformalized Histogram Regression (Sesia & Romano, 2021), Probabilistic Conformal Predic- tion (Wang al., 2023) and several others. All these methods share some key aspects: they built on top of the pre-trained models and do not require access to training data or the model's internals on both calibration and prediction steps. We aim answer these specific questions: how does Cp² performs in terms of coverage, conditional coverage and predictive set volume when compared to state-of-the-are methods on synthetic and real data
4.1 SYNTHETIC DATA EXPERIMENT
In this example, (Xg. Yie) is sampled from mixture of Gaussians; see Figure 2a. The number of training and calibration samples is m = 10s and n = 10 respectively. We fit Mixture Density Network (MDN) as explicit generative model, x (v) E Te(x) (e( where (e{-), ae(-) and ne(-) are all modeled by fully connected 2-layers neural networks (the condition Σe = (x( 1 is ensured by using softmax activation functions). We use Cp2-HPD (the calculation of the HPD rates as well as and Vaz, y) is explicit in this case) with fe(u) = tv. The parameters of the MDN are trained by maximizing the likelihood on the training set.
We compare the plain HPD- PCP (with the same MDN as CP² HHDD and M = 50 draws) and CQR. All methods achieve the desired marginal coverage 1 a 0.9. We illustrate the conditional coverage in Figure 2b and the lengths of the predictive sets in Figure 2c. CP with predictive set performs poorly this multimodal example, both in terms of the size of the confidence set and the conditional coverage CP2-HPD and CQR perform similarly in terms of conditional coverage (which remains close to --a a = 0.9). The conditional coverage of PCP varies between 0.85 and 0.95. CPP-HPD produces smaller prediction sets compared to CQR and PCP as HPD confidence set is more suitable for multimodal applications than the interval produced by CQR.
fxed-width
4.2 REAL-WORLD REGRESSION DATA EXPERIMENTS
Datasets. We use publicly available regression datasets, which are also considered in (Romano al., 2019; Wang et al., 2023). Some of them come from the UCI repository: bike sharing (bike), protein structure (bio), blog feedback (blog), Facebook comments (fb1 and fb2).. Other datasets come from US Department of Health surveys (meps19 meps20 and meps21), and from weather forecasts (temp; Cho et al. (2020)).
Methods. We compare the proposed CP2-PCP method with Probabilistic Conformal Prediction (PCP; Wang et al. (2023)), Conformalized Quantile Regression (CQR; Romano et al. (2019)), Con- formalized Histogram Regression (CHR; Sesia Romano (2021)), Conformal Prediction with Conditional Guaranties (CPCG; Gibbs et al. (2023)), Localized Conformal Prediction (LCR; Guan
Code of experiments he found https::////// //gi giggttubb....... wwwpwott.ttt.cecccooooooo..t...t wttaatttmmmcmmitiieeee /condi coandition tinatlooonaggg
7

---

Published as a conference paper at ICLR 2025
Hoyx
CP FCF-D
CqR2 CD-eplat
0.95
Wondt-al ovantay
0.85
0.80
0.75
bale
bio
blog f1.1
merp41 mmpper0 Torge21
terop
Figure 3: Worst-slab coverage on real data. Results averaged over 50 random splits of each dataset. Calibration and test set sizes set 2000, 50 conditional samples for PCP, CP² and [yy]x- Worst-slab coverage parameter (1 8) 0.1. Nominal coverage level is (1 a) 0.9 and is shown in dashed black. Methods with conditional coverage below 0.75 shown as cross- cross-hatched on horizontal axis.
CF
FCP
1byxx
CP FCP
CP PCP.L
CHR
CDR
CqR2
CPCO
LCP
CD-opli1"
2.5
2.0-
1.5
Iriloo
Inio
Blog
firl
traege:
meppo7)
meppe221
trmppp
Sizes of the prediction sets real data. We divide the size of the set by the standard deviation response to present the results on the same scale.
Figure 4:
(2023)) and CDSplit" (Izbicki et al. (2022)). We also consider COR2 which is modification of CQR that uses inverse quantile as conformity score. For our method and PCP we use a Mixture Den- sity Network (Bishop, 1994) to estimate the conditional distribution PyІx that was perf-perf stands for
in (Wang al., 2023). We also consider different choices of fe for method:
CP2-PCP with fe(v) = tu and CP2 CP2-PCP-D stands for CP² Cp2-PCP PCC with ft(v) = I + v. Additionall, we consider Iyyxx which is special case of CP2-PCP with (v) =t.
Metrics. Empirical coverage (marginal and conditional) is the main quantity of interest for prediction sets. We evaluate worst-slab conditional coverage (Cauchois et al., 2020; Romano et al., 2020b) in our experiments, see details in Appendix B.2. We also measure the total size of the predicted sets, scaled by the standard deviation of the response Y.
Experimental setup. Our experimental setup largely follows the approach outlined in ( (Wang et al., 2023). Specifically, we split each dataset into training, calibration, and testing sets. A Mixture Density Network (MDN) with 10 components is then trained to approximate the conditional distribution PYJx- For each calibration and test point, we first compute the Gaussian Mixture parameters, forming Πy and subsequently draw M = 5, 20, samples from these distributions, which yield R2, t). This process is repeated across 50 different random splits of each dataset.
Results of experiments for M 50 samples are presented in Figures and additional results are available in Appendix B. All methods achieve the target 1 marginal coverage, except for Iy
Standard conformal prediction fails to maintain the conditional coverage as expected. We can also observe that PCP consistently struggles with conditional coverage. On all the datasets CP2-PCP provides valid conditional coverage, while CQR fails on b blog and temp, CHR method shows unsta- ble performance not achieving conditional coverage more often than other methods but sometimes providing narrower predictions sets. Additionally, CP2-PCP significantly outperforms quantile regression- based methods in terms of size of the prediction sets bike, bio and temp datasets. CPCG is a strong baseline, but our method shows better performance still. For example, on b blog, fb1 and f2 datasets conditional coverage of cP2-PCP is close to nominal, while prediction set size
8

---

Published as a conference paper at ICLR 2025
00.00
Clasr
Figure 5: Conditional coverage for different clusters, fbl dataset. We have used HDBSCAN algorithm with minimum cluster size of 100, min samples syper-paramete of 20 and l2 metric. Cluster label corresponds to the outliers. Sample size for sampling-bass based methods was set to 50. Nominal coverage equals (1 a) = 0.9 and is shown by dashed black line.
CP
PCP
Tlyxx
CP PCP D
CP PCP-L
CHR
CQR
CQR2
1.00
Marginal coverage
0.95
0.90
0.85
0.80
indoor
rf1
r12
semld 1d
Scm20d
sgemm agelllsmall
Figure 6: Marginal coverage for multi-target datasets, 50 replications. Sample size was set to 1000. Nominal coverage equals (1 a) = 0.9 and is shown by dashed black line.
are roughly the same between two methods. On meps datasets, conditional coverage is close, while the CP8-PCP sets are smaller. Computational complexity of the prediction is the highest for CPCG, about 10 times that of our approach. LCP shows significantly lower conditional coverage than most methods on larger datasets. CDSpl it + shows good conditional coverage but also large variance between runs. We also noticed that it consistently overcovers marginally, again with large variance. Set sizes for this method are usually small but often comparable to CP². Overall we consider this method highly unstable on real datasets, requiring additional investigation or hyperparameter tuning.
Finally, we assess conditional coverage with the help of clustering. We apply HDBSCAN (Campello al., 2013; McInnes & Healy, 2017) method to cluster the test set and then compute coverage within clusters. Results for fb1 dataset are presented Figure 5. We again observe that CP and PCP do not achieve conditional coverage and CHR and CQR performance is unstable. CP2-PCP the other hand maintains valid conditional coverage on all clusters and even on outliers (cluster label -1). Note that these all outliers combined and they may lie the same region of the input space.
4.3 REAL-WORLD REGRESSION DATA WITH MULTI-DIMENSIONAL TARGETS
We also study CP2 family of algorithms on the multi- taalettttrgtttt regression problems. Since selecting the threshold т for our methods is not dependent on the number of dimensions in their application is straightforward. On the other hand, most other methods require the use the Bonferroni correction (Dunn, 1961). Each coordinate is treated independently with miscoverage level adjusted a/d, where d is the number of targets. As result, for quantile regression-based methods prediction sets are formed as a product of the corresponding intervals.
inherently one-dimensional thus
Datasets. We consider open-source multidimensional regression datasets: river flow data rf1 and rf2 (Xioufis et al., 2012), supply chain management scmld and scm20d (Xioufis et al., 2012), indoor localization indoor (Torres-Sospedra et al., 2014), GPU computation time sgemn_smal (Ballester-Riplll et al., 2019).
"The full dataset contains 241600 examples. Due to computational constraints we randomly subsample 10000 examples for each replication of our experiment.

---

Published as a conference paper at ICLR 2025
Worst-slab eovergae, d 0.1
Typx
DPS-CCDDD
CCP-
CQR
CUR2
0.90
0.75
0.60
0.45
indoor
rfl
rf2
scm ld
scm20d
sgemm small
Figure 7: Conditional coverage for multi-target datasets targets, 50 replications. Sample size set to 1000. Nominal coverage equals (1 a) = 0.9 and shown in dashed black. Worst-slab coverage parameter 8) 0.1.
Aborgg ral
Ladlxe
Figure 8: Average rank of the projected set size. For each pair of targets area of the corresponding 2D projection of the prediction set is calculated. For each test point and each pair of targets methods ranked. Lower rank smaller area. This graph shows averaged results of 10 replications.
We use the same metrics as before: marginal coverage and worst-slab coverage. Evaluating the difference in prediction set size is more complex case of multiple dimensions. Due computational constraints we perform pairwise comparisons between our methods and selected baselines, measuring approximate areas of 2D projections of the prediction sets (Wang et al., 2023). These results can be found Figure 8. We approximate areas using grid and fewer samples.
Since our methods naturally extend beyond one dimension, the experimental setup is almost identical. We use the same underlying model for PyІx the prediction set is now union of d-dimensional balls of the same radius around the sampled centers. The number samples is increased to 1000.
Results. In Figure 6 we show marginal coverage attained by different algorithms. As expected, naive application of ID techniques CQR, CQR2 and CHR to multiple outputs produces significant overcover. PCP and CP2 methods naturally extend to multidimensional targets and provide correct marginal coverage. In Figure we present the conditional coverage estimates for multi-target datasets. PCP significantly undercovers on rfl, rf2 and scmld d datasets, while CP² comes very close to the nominal coverage of 0.9. In case of CQR, CQR2 and CHR, they still overcover (scm2 dd, sgemm) or perform comparably our approach. Figure 8 shows the aggregated results of the set size comparisons in multidimensional target setting. For each test point and each pair of axes we rank methods by the area of the projection of the corresponding prediction set. The plot shows average rank for each method, aggregated across all axes pairs and replications. Lower rank corresponds to smaller area, which is our goal. For datasets indoor, scm1 and sgemm__sm sammm_smalll our approach performs better, while also providing sharper conditional coverage. On the remaining datasets CP² performs similarly to the competitors.
CONCLUSION
address the challenge of conditional coverage in CP, and overcome previous negative results by assuming the knowledge of good estimator of Pylx. Our proposed mechanism conformalizes the conditional distribution estimator Iy x to ensure marginal validity while maintaining approximate conditional coverage guarantees. Specifically, if experts provide accurate conditional estimator, our algorithm generates nearly conditionally valid multidimensional prediction sets. This approach offers practical solution for tackling heteroscedastictyy in machine learning applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This research was partially supported by RSF grant 20-71-10135. V.P. has been supported by grant of the Lagrange Mathematics and Computing Research Center. E.M. is Funded by the European Union (ERC, Ocean, 101071601) Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 808--18,72 2016.
Ahmed M Alaa, Zeshan Hussain, and David Sontag. Conformalized unconditional quantile regression. In International Conference Artificial Intelligence and Statistics, pp. 16690-10702 PMLR, 2023.
Rafael Ballester-Ripoll, Enrique G Paredes, and Renato Pajarola. Sobol tensor trains for global sensitivity analysis. Reliability Engineering & System Safery, 183:311-322 2019.
Christopher M Bishop. Mixture density networks. Technical Report. Aston University, Birmingham, 1994.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pp. 208-240. Springer, 2003.
T Tony Cai, Mark Low, and Zongming Ma. Adaptive confidence bands for nonparametric regression functions. Journal of the American Statistical Association, 109(507):0054-1000 2014.
Ricardo G. B. Campello, Davoud Moulavi, and Jörg Sander. Density- based clustering based on hierarchical density estimates. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2013.
Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. J. Mach. Learn. Res., 12:11:1-81:2,, 2020.
Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Academy of Sciences, 18(48):2210799411 18, 2021.
Dongjin Cho, Cheolhee Yoo, Jungho Im, and Dong-Hyun Cha. Comparative assessment of various machine learning-bast based bias correction methods for numerical weather prediction model forecasts of extreme air temperatures in urban areas. Earth and Space Science, 7()):2001EA000044) 2020.
Nicolas Deutschmann, Mattia Rigotti, and Maria Rodriguez Martinez. Adaptive conformal regression with jackknife+ rescaled scores. TMLR, 2024.
Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2001.
Olive Jean Dunn. Multiple comparisons among means. Journal of the American Statistical Associa- tion, 56(293):52-64, 1961.
Jianqing Fan and Tsz Ho Yim. A crossvalidation method for estimating conditional densities. Biometrika, 91) 834, 2004.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-frree conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455 4825 2021.
Isaac Gibbs, John J. Cherian, and Emmanuel J. Candès. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305. /2616, 2023.

---

Published as a conference paper at ICLR 2025
Leying Guan. Localized conformal prediction: A generalized inference framework for conformal prediction. Biometrika, 110(1):33-35) 50, 2023.
Etash Kumar Guha, Shlok Natarajan, Thomas Möllenhoff, Mohammad Emtiyaz Khan, and Eugene Ndiaye. Conformal prediction via regression-al as cllasssiiiaiii.i. In The Tweifth International Conference on Learning Representations, 2024.
Chirag Gupta, Arun K Kuchibhotla, and Aaditya Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496, 2022.
Xing Han, Ziyang Tang, Joydeep Ghosh, and Qiang Liu. Split localized conformal prediction. arXiv preprint arXiv:2206. 2..iv:2220.1399990 13092, 2022.
Rohan Hore and Rina Foygel Barber. Conformal prediction with local weights: randomization enables robust guarantees. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp- qkae103, 2024.
Rob J Hyndman, David M Bashtannyk, and Gary K Grunwald. Estimating and visualizing conditional densities. Journal of Computational and Graphical Statistics, 5(4):315-336, 1996.
Rafael Izbicki, Gilson Shimizu, and Rafael Stern. Flexible distribution free conditional predictive bands using density estimators. In International Conference on Artificial Intelligence and Statistics, pp. 3068-3077. PMLR, 2020.
Rafael Izbicki, Gilson Shimizu, and Rafael B Stern. Cd-split and hpd-split: Efficient conformal regions in high dimensions. The Journal of Machine Learning Research, 23(1):3722-3803, 2022.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In International Conference Artificial Intelligence and Statistics, pp. 4346-4356. PMLR, 2020.
Shayan Kiyani, George J Pappas, and Hamed Hassani. Conformal prediction with learned features. In Forty-first International Conference Machine Learning, 2024.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series Statistical Methodology, 76(1):71-96. 2014.
Jing Lei, Max Sell,, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 1 113(523): 1094-1111) 2018.
Michael Li, Matey Neykov, and Sivaraman Balakrishnan. Minimax optimal conditional density estimation under total variation smoothness. Electronic Journal of Statistics, 16(2):3937-3972. 2022.
Leland McInnes and John Healy. Accelerated hicrarchical density based clustering, 2017 IEEE International Conference Data Mining Workshops (ICDMW), pp. 33-42, 2017.
Paul Melki, Lionel Bombrun, Boubacar Diallo, Jérôme Dias, and Jean-Pierre Da Costa. Group- conditional conformal prediction via quantile regression calibration for crop and weed classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 614 623, 2023.
Radford M Neal. Slice sampling. The Annals of Statistics, 31(3):705-767, 2003.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools artificial intelligence. Citeseer, 2008.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pp. 345-356. Springer, 2002.
12

---

Published as a conference paper at ICLR 2025
Vincent Plassier, Nikita Kotelevskii, Aleksandr Rubashevskii, Fedor Noskov, Maksim Velikanov, Alexander Fishkov, Samuel Horvath, Martin Takac, Eric Moulines, and Maxim Panov. Effi- cient conformal prediction under data heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 4879-4887. PMLR, 2024.
Vincent Plassier, Alexander Fishkov, Victor Dheur, Mohsen Guizani, Souhaib Ben Taieb, Maxim Panov, and Eric Moulines. Rectifying conformity scores for better conditional coverage. arXiv preprint arXiv:2502. 2025.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2(2):4, 2020a.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3500 2020b.
Murray Rosenblatt. Conditional probability density and regression estimators. Multivariate analysis II, 25:31, 1969.
Jonas Rothfuss, Fabio Ferreira, Simon Walther, and Maxim Ulrich. Conditional density estimation with neural networks: Best practices and benchmarks. arXiv preprint arXiv:1903.00954. 2019.
Matteo Sesia and Emmanuel Candès. A comparison of some conformal quantile regression methods. Stat, 9 21)62,,,, 2020.
Matteo Sesia and Yaniv Romano. Conformal prediction using conditional histograms. Advances in Neural Information Processing Systems, 34:6304-6315, 2021.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
Joaquín Tosres-Sospedra, Raúl Montoliu, Adolfo Martínez-Usó, Joan P. Avariento, Tomás J. Arnau, Mauri Benedito Bordoonau and J Joaquín Huerta. Ujiindoorloc: A new multi- building and multi- floor database for wlan fingerprint-bast indoor localization problems. In 2014 International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 261-270, 2014.
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference machine learning, pp. 475-490. PMLR, 2012.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world, volume 29, Springer, 2005.
Zhendong Wang, Ruijiang Gao, Mingzhang Yin, Mingyuan Zhou, and David Blei. Probabilistic conformal prediction using conditional random samples. In International Conference on Artificial Intelligence and Statistics, pp. 8814-8836. PMLR, 2023.
Eleftherios Spyromitros Xioufis, Grigorios Tsoumakas, William Groves, and Ioannis P. Vlahavas. Multi-target regression via input space expansion: treating targets inputs. Machine Learning, 104:55 - 98, 2012.
Xingyu Zhou, Yuling Jiao, Jin Liu, and Jian Huang. A deep generative approach to conditional sampling. Journal of the American Statistical Association, 118:1837 1848, 2021.
13

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RESULTS AND CALCULATIONS
In this section, we analyze the theoretical results of Section 3. First, let's recall the definition of the quantile function for any distribution fln living in R. For any (0, 1), the quantile Q1-a(11n) is defined by
(14) inf {t E R: (n t)) ---a) a}. Given a measure x= defined on o))), we consider for all a E RR, x E 2, the parameters Ta.a and Va v) given by
T2, = inf [n T: (R 21-a)
(8)
(z = inf e T: E (x;t))
where yp is chosen as in H2, and by convention we set inf 0 = co. We denote by d, the Dirac measure at E IR, and write тh Tx and V&= Vz. (X&, Yτ). In this Appendix, we study the coverage of the prediction set given V(x, 2) E R x 2 by
C. (x) R (x: fra.. (Qi-a(un)).
where the distribution pa is defined as
Σ 8 (v, ++11 8cc.
The key idea behind the choice of Th is to ensure that the conditional coverage of the prediction set (X,) is approximately 1 a when the empirical distribution Xyy]x=X, is close to Pyjx=Xx- In other words, Tę is chosen such that the probability of the observed value Ys: given X₃ falling inside the prediction set C. (Xx) ) is close to 1 a. On the other hand, the parameter V& is used to ensure that the prediction set Rz, (Xx;
; Vi.) contains the observed value Y₁. Moreover, note that Th only depends on the input data (Xx, Zz), while V/2 depends on (X&, Yı, Zt). Thus, the i.i.d. property of {(X,, YR, Z & E [n + 1]} ensures that the {(Tk, Vx) I are also i.i.d.
A.1 PROOF OF THEOREMS 3.1 AND 3.2
Lemma A.1. Assume HI hold. For any (x, 2, IRd x xyz Z. Ve y) exists in T, and we have y E (2; vz)
Proof. Let (x, U. E Rd x y' x Z be fixed. Since DeT (x; 1) = 0 and UITTR = y deduce the existence of to and l such that y & R2; to) and y E (=(x;;1), Therefore, (t T: y (2; })} is non-empty and lower-bounded by to. Thus, the infimum V2 y) exists. Now, let's prove that y E R. (a, v)). Since Vz y) inf T: y E R2 (2; we deduce the existence of decreasing sequence (An such that E (r An) and lim, An = V2(x, v). By definition of (A,hnen, we have y E OnENR (2; An). However, using HI, remark that
OneR (z; An) ONEN DE>A, (z;
= lim >, RR
(x; t)
((s)) (x;t) = (2 (z v)).
Since y E OneNRZ(1; >n)) implies that y R. (2; V V=(x,))) y))
We will now present the proof for Theorem 3.1, which establishes the marginal validity of our proposed method.
Theorem A.2. Assume HI-H2 hold, if (s= (V))) are almost surely distinct, then it follows
1 a F (Yat1 E (X(42))) < a n n11
Proof. Using Lemma A, we have
T (Yn+1 E C. (Xn+1)) = TT (Yn+1 E RZns (Xnt1s Stres (Q))))))))) TT (Vn+1 I Fraee (Q (Mn)))
14

---

Published as a conference paper at ICLR 2025
Since fr..1 (v) is increasing by H2, we deduce that pd (Vn+1 I f (Q1-a = =PT - (Frne (Vo+1) I Q1-a((n))
Denote by Vv = f (V&), the exchangeability of the data {(XR, Yk: Zu): k E In + 1]} implies that
)) -PT n
800
n+1
8v2
pJ Vn+1 SQ1aa
Vn11 S &Q1aa
Σ
+
Tu +
n+1
n+1
T
1v: S Q1-a
ōv
n2
km
km
E
E
1v, S Qi
ōv2
V1, Vi....,
Vn+1
n
where 1 ~ ~unis().... n- 1). Therefore, the definition of the quantile function implies the lower bound (9). Moreover, if there are no ties between the {Vx [ then
1st (Friss (Va+1) S Qi-a(uu)) < <1-a+ n n+1
The following lemma provides conditions under which [ly]x== (R, fra.: (p))) 2 1
Lemma A.3. Assume H1-H2 hold, and let a E (0, x E Rd, Z. Iflly|== a probability measure, then Tz,z is defined and I1
(v)) a.
Proof. Let E Rd be such that xy is probability measure, and fix Z. Since f+(1) is increasing and bijective by H2, we have
= -Iyxx== (UreTTa sup Ilyxx= (R, TET
= (
=
The previous equality shows the existence of 7 E T such that (Rz S (v))) 2 - Therefore {r E T: (R, 2 1 a} is non-empty. This proves the existence of Tz.: = inf(r E T: otherwise we would have
2 a} in Tu Moreover, Tx,= > -0,
1 inf Ty|x= (R. (+ I (1; 0. TET
Therefore, we deduce that Tx. E T. Lastly, remark that
(p))) = (yxx==a(Or>>,,,R(11 fx(1)) inf
(R, (+())) - a.
<>Te.4
Now, we prove Theorem 3.2. This result guarantees that the conditional confidence intervals
constructed by our method approximately satisfy the desired coverage of 1-a. Given (z, y) E Rd x let's introduce
Pa+1 2) = PT (Qi-a(um) < ffl (V2(z, Yn+1)) S X = x, Zn+1 =2)
(x) (p S=! Ve( s Q1-0 (Mx) Xn+1 x. 2n+1 2)
15

---

Published as a conference paper at ICLR 2025
Theorem A.4. Assume HI-H2 hold, let R be such that Nyyxx= is probability measure. For any & E 2, it follows that
1-a-drv(Pylx=an) - Po+ 2) PpT (Vn-1 E Ca (Xx+1)) Xn+1 I, 7n+1 2) [1y||== (z; fiz.. (f))) + drv (Pyxxxii -yyx==>)))))))))))))) 9n+ (zz 2).
Proof. First, recall that C. (x) is given in (6), and V. (ar, Y1+1) is defined in (8). Applying Lemma A.I, we know that (I, Xx+1) is defined in T, and also that Yn+1 E (2; (z, Xn+1)). Hence, it holds
pT (Yn+1 Cx 1) Xa+1 = xz Zn+1 = =P7 n+1 E R. (1:I |xn+1 = I; Zn+ = =2)
=PT (Ve Yn+1)= S ST... (Q1-a((n)) Xx+11 = x, 7n+1 = (10)
Let's introduce the term PT (V=(2z Yn+1) S ST,, (4) Xn+1 2, Zu+1 2) follows:
PJ (V= Y2+11) S ST.., (Q1-a((m) | |xa+1 = F, Zut1 = 2)
=IP" (Va Yn+1) S ST... (Qi=a(un)) |x++1 I, 1n-1=1)
1PT (Vs Yn+1) S fr... (P) Xn+1 I, Zn+1 =2) (II)
Now, we will control the difference between the two terms of the previous equation. Let A and B be defined as
A= P" (F
( (V2 (1 S Q1 < x = =2 Zn+1 =2)
= PT (J.. (Va Yn+1)) S
o o S Qi-a(um) Xn+1 = x, 2n+1 =
We have
pd (Vi(I, Yn+1) S ft., (Q1-a(pn)) |xn+1 2, 1n+1=1=0 =2)
= A+++P (4 ( ST. (V2(2, Yn+))) s (QI-a(un)| = x, Zn+1 =z)
and also
PT (V, (((1, 1n+ S fTa, (p) Xu+1 x, Zn+1 2)
-+ B + PT (1)- < S (V,(2,YY41)) S X x. 7n+1 =2)
Therefore, the difference between the terms introduced in (11) can be rewritten
PJ (V=(I, Yx+1)= S fra.. (Q1-a | = =x, Zn+1 2) =2)
PTT (V Yn+1) $ ( X x+11 |
x. Zn+1 =2) 2)
PT E < fTll (V2(1, Ynt1)) < Q1-)()4n) Xx+1 x. 7n =
-P" (QI-a(um) f (Vs Yn+1)) S Xx+1 x, ZnZn+ =z). (12)
1. By definition of the total variation distance, we have
pt (V2(z, Yu+1) S fr.. (v) |x+11 = x, Zn- = 2)
2 2PT (V= (n41) S STe.. (1p Xn+1 Ir, Znn1 = Zn+1=2) Crr(Pryx=xillyxxxe
Moreover, Lemma A.3 implies that Knt1) &n+z) =T (Ynt1 E LuE (VED: V2(2. S Sta, (1)) |Nn+1 x,, Zn+1 =2)
pT (Valo,, S fTea(19) (x)1 = 22,4+1 )
=PT E R2( ST... (4)) Xn+1 = x, Zn+1 =z) (T (Rx
= -lyy x=
fraiffrrr.. (p))) 21-221100 a
16

---

Published as a conference paper at ICLR 2025
Therefore, deduce that
p" (Ve(a, Yx+1) I (p) Xn+1 = I, Zn+1 = =2)
= 2 21-a- dyy(
Combining the previous result with (11) and (12) shows that
PT (Va 1n+1)= S fr... (Q1-a (pn)) |n+1 = z, Zn+1
- -P" (Qi-a < F (Va Xn+1)) s Xn11++1= - x, Zn+1 =z)
Finally, using (10) gives lower bound on PPT (Yn+1 (X Xn+1 = 2, Zn+1 2).
2. By definition of the total variation distance, we have
Pd (Va(a, Yu+1) S ( Xn+1 2. Zn =2)
SPT (V (nt1)) S STa.. (p) Xn+1 Ir, 7u =z) -drv(Py)x=siTyxxxe (y|Ixa))
Moreover, Lemma A.3 implies that
Pd (V, Pnt1) S frz.. (40) |X]11 2. Zn+1 = (R, (v))) Therefore, we deduce that
pd (Va(z, Yn+1) S (1) Xn+1 = 2x, 2n+1 =
S & ( (+))) - drv Iy)xx=))
Finally, combining the previous result with (11) and (12) shows that
pJ (Va Yat1) S fr... (Qi-a(Mn)) [xn+1 = x, 22+2+==2 =)
s 1lyxx= (R, frz.. (4))) + (Pv(Pr llyx==)) + (0+1(2,2).
(a.:) A.2 BOUND ON (z.z) AND 4.+1
The objective of this section is to study the conditional guarantee obtained in Theorem A.4. Under some assumptions, we have demonstrated that the conditional coverage is controlled as follows:
1-a-drv (Prix=i
Pn S PTT ( Ca Xn+1 = I, Zn+1 = =)
S (R, STE.. (v))) + drv (Pr -lyxx==) 9m+ 00+111222 (2,, z),
In the following, we consider the cumulative density functions F: t + PT (fz1 (Vz Y)) S1) and P: L + IPT (Srl2 (V)( l). where (X, Y, Z) Px Pr|x x l2z and (X, V, Z) Px x Hylx x Z We denote by μ and j the law of the random variables fix (V2 Y)) and folz (V2 (X, F)). Moreover, recall that μ4, n+1 E 5 n+1 820. Note, the quantile Q1-o (Px) is order statistic with known distribution that converges to the true quantile Q1) The quantile defined for any t E 1) by
Q,(v) = innffu E I: v(( (((ooo,u) ul) 2 f},
where v E (H, R.)
(13)
Theorem A.5. Assume HI-H2 hold, and let Rdd be such that my|x== is a probability measure. For any e E [0, 161--0 a), if PT (f PT
(X, < Q1-a-c(H)) < a. then follows that
Pat1(0,2) 2) T (Qi-a-c(4) < f-zl (V Yu+1)= I Qi-a(A) |nn+1 = x, Zn+1 = =2)
+ cexp (-mpa(1 - -pc)h
1 - a- Pe ( Pc(1- (p)) ))
where b: u (1 + u) log(1 u)
17

---

Published as a conference paper at ICLR 2025
Proof. C [0, - a:, IR, and consider
= (QI-a(Hn) < Q Q1-a-((4))
Bz.= {u E y: Sa., (Q1-a-((1) < V=(1,v) S (
We have
pT
(Trza (Q 10 (Q)))(())) VV(a, Yn+1 S ST Xn+1 = 2. Zn+1 =
I PT (A Xx+1 = x, 2n+1 =)) + PTT (Yn+1 E Be,x Xn+1 = v. Zu+1 = =z).
Now, let's upper bound the first term of the right-hand side equation. First, remark that
"
{Qi-a < Q1-a- +>
Fe (v))
ag.
n1 n+1
Thus, we deduce that
1)(1 -a) 11(1
IpT (A Xa+1 2, 1n+1 = =2) STT
1 Jr (1) 2 2
Recall that P. = PT (f=x) (V2(X,Y)) < Q1-a-e (4)), and also that we assume P. S - a. Therefore, the Bennett's incquality (Boucheron et al., 2003, Theorem 2) implics that
PT (A Xx+1 = x. 7n =) S exp (-mpa(1- - -p:) (n 1)(1 (x) -1pe) )) (14)
Tip
npp(1 - -Pc)
where u (1 + u) log(1 + u) - u. Moreover, define
a Pe
(n + 1)(1 a)) repe
U Pc - p.)
ū.
npp - Pc)
We have u. S Ue, from the increasing property of h it follows that
pT (A Xn+1 = x. Zu+1 = 2) S exp (-mp. - Pc pc)c)
Furthermore, the definition of BR, gives
P (Yn+1 E B [n++ = x, In+1 - =
=PT -J,, (Q1-a-c(1)) < V2 Yat1 S (p))(() Xat1 = x, 2n+1 = =z).
Moreover, for any t E (-00, (p), we have
F(() = PT (V2X, 81) $1)
1 PT (VZ 8)) S x = xx =z) (1z]x=x(=)) Px
-f (FE (t))
x = x, == πz (dz))))))) Px (dr).
Using H2, the bijective property of t + f+(() implies the existence of T, such that (x( fr.. (t). Note that, Tu. otherwise would lead (x) 2 f (4) Sra.. (t). The definition
of Ta shows that
TTT (2,
x 2 == =x) <1-a.
Therefore, deduce that Q1-a (f) 2 p. and we can conclude that
PT (Yn+1 Br, Xn+1 I, Zn+1 2)
<PT (Q1-a-e(H) f.ス (Vz(z, Ynt1) S Q1-a(fi) Xn41 Z, = =z). (15)
Finally, combining (14) and (15) concludes the proof.
18

---

Published as a conference paper at ICLR 2025
Given E (0, 1), define the threshold
8a(1 0. logn
Cn
(16)
n
Lemma A.6. If the distribution of Fx,2 (Vz(XX,))) is continuous, then all e [0, 1 a),
have Pe 18T (Frx2 (Vz(X, < <Q1-a-e(4)) 1 a Moreover if a(l-a) then follows
1-a a - Pen Pen
Pen
exp
-npen (1 - Pen )
where b: u u (1 + u) log(1 + u)
Proof. First, recall that Q1-a-e(1) is defined in (13). If the distribution of f (Vz(X,Y)) is continuous, then we have
1 a-a-e5 F((1-(---(()) = sup 8>0
-
I T
[ (Vz((x,))) < Q1-a-r(1) = < -
Therefore, we deduce that p.
Let's denote
(n + 1)(1 - (x) rppc.. npen (1 Pe..)
8n = (n + 1)(1 -a) -PPe..
For any 2 0, remark that log(1 + u) 2 1--dd u2 w2/2. /2. Thus, deduce
(1 + un log(1 un) Un
npe, (1 Pe,, h (un) 5n
Un
2 8n Un (1 - Un)
(17)
2
Now, let's show that un $ 1/4. We have
Uh (n + 1)(1 - aa) MPen
npe, (ppt..)
1-a a
+ 1 - - Pen
nPe, (1 Pea)
Pea (1 -Pen)
1-a
m(a+ (n) a - En)
(a+ - 6n)
Therefore, u, S 1/4 if and only if
1 n
(a+ (n(
+ S
4
The function e E [0, 1021/2-l) + (a+e) -a- is increasing, Since en S a(1 aa)88 < 1/2 1 a. it is sufficient to prove that
1 1
en a(1 - a)
4
Since en 5 <a(1 a)/8, we just need to show that
a(1 at)
8a(11-0 a)
i.e.
< n² ox)
(18)
n
n
Again, using the fact that 6n S a(1 - -0/8, we deduce that
8a(1 a)
2 a² aa2 = a² a) x (1-a) a)
log
8 llg
8 8
19

---

Published as a conference paper at ICLR 2025
Since (I-a) llog I 1, we deduce that (18) holds. This concludes that un S 1/4. Moreover, for any
E [0, 0.25), we have
u)
udn 4
8n
Plugging the previous line in (17) implies that
[(n + 1)(1 (2) -mpp.. 12
exp -ppe. (1 - Pe,.) ) h (un)) 1 cxp
Ampen (1 - Pen)
(1 + nenn)
S exp
4n(a + tn)
a En
ne
< exp
(19)
4(a + (1) 0 - Cn)
Lastly, since En a, it follows that
nc.
2a - a) log
2 log
4(a e1 en)
(a + e. En)
Combining the previous line with (19) completes the proof.
For any e [0, a), define
qe = (Vz(X, Q1-ate(1)).
Theorem A.7. Assume HI-H2 hold, and let x E Rd be such that Iyyxx= is a probability measure. If the distribution of fix. (Vz(X, (o.Y)) is continuous and n n- log S 8-83a(1 - o.), then, it holds
ant1(2, 2) s -PT (Q1-a(() < f- (Va(x, (n,1) 1) S Q1-ate, (4) Xn+1 2, Zn+1 =
(20)
where en is defined in (16).
Proof. Let's consider
A = (Q1-ate, (n) < (u))
BR = {yE D: fr.. (Q1-a < Vz(I,y) S (Q1-0(01--
We have
P (fr.. (Q1-a()) V2(a, Yn41 S (Q1-a Xn+1 = Zn+1 =2) SPT (A X x, Zn+1 2) PT (Ynt1 Br, Xn+1 x, Zn+1 2) (21)
Now, let's upper bound the first term of the right-hand side equation. First, remark that
(QI-aten(4 (P) Q1-a(Hm))
sed 1n <
n
Thus, deduce that
TT (A Xa+1 = T. Zn+1 2) S ST PT
Σ
1 (V) < (n a)
Recall that gr,, = (T (Vz(X, < <i (u)), and also that ge,. < since the distribution of f=1 (Vz(X, is continuous with a + en 1. Therefore, the Bennett's inequality (Boucheron al., 2003, Theorem 2) implies that
(V
(n + 1)(1 a) -n9cn )) ng., (1 ge..)
T (A X = x, Z = =) S exp (-nqen. (1 ge.,)
20

---

Published as a conference paper at ICLR 2025
where h u+ (1 + u) log(1 + u) u. Moreover, define
1 4r,
(n + 1)(1 aa) ngc..
Wen qe, (1 - gen))
ndc, (1 (ce)
We have ue. I Me.. from the increasing property of h combined with Lemma A.6, it follows that
pT (A X I, Zn+1 =2 S exp (-nqe.. (1-9e,)h(uu,
The previous inequality combined with (21) concludes the proof.
A.3 PROOF OF THEOREM 3.3
Oracle asymptotic conditional coverage. Before proving the result, start by briefly discussing the asymptotic conditional coverage guarantee. Assuming the availability of an oracle for the predictive distribution, i.e., Py|x== IIy [ get under HI and H2, that for any E R,
IP (Vz(X,Y) S fxx.2 (t) x= = x, x, IP (Y E Ro fra.. (t)) | = 2 =
-x|x== (R2 ST, (t)))
where (X.Y.2) follows the same distribution than (Xx, Ys, Zx), k E (I.....n.. Note that I (x; T.... (1)) 2 1 a if and only if 40, which implies that PP (V2(X, Y)) St |
(X, (X,
(x,
if and only if g.
(22)
From (22) it is easily seen that the (1 -q-annlee of f (V2(, is s. The Glivenko Cantelli Theorem (Van der Vaart, 2000, Theorem 19.1) demonstrates that suPIER ( (-o, P( (Vz(X,Y) Y)) S ()] + almost surely n - co, where Hr, is defined in (7). Since the convergence of the c.d.f. implies the convergence of the quantile function (Van der Vaart, 2000, Lemma 21.2), we deduce that (14)) + & almost-surely as n - co. Under weak additional conditions this implies that lim Pn+1 (zx, =) 2l x Px-almost everywhere, where ll x is the distribution used to draw the auxiliary variables 2; see Appendix A.4. In this case, Theorem 3.1 implies the asymptotic validity of CP2.
Now we can prove a precise result that takes into account that only an estimate IIy of the conditional distribution Py|x=s available.
Theorem A.8. Assume HI-H2 and suppose the distributions of Six,2 (Vz(X,Y) and
fix.2 (V,(X, ))) are continuous. For any a E (0, and p > holds
PT ((ET (Yn+1 E (x 1xn11 Zn+1) - 1 a > p)
2n + 1128aa1 - a)n log n + 4drv x Hylx)
p
Proof. Let p > 0 be fixed. Applying Theorem 3.2, we obtain that
2) T (Yn-1 Ca(Xnt1) Xn+1 x, Znt1 2) fyyx== (Rs fr... (+))) + drv (Prix=zi Sexxxxillyper lyyx==) (241 2). (23)
Step 1: Lower bound. Using the Markov's 's inequality implies that
T (PT (Yn+1 E Ca(Xx)1) X Zn+1) < 1 a p) s PT
+ Pnp1iiX <)
ET ddd [lyxx) + E [po+ 1 (X,Z)) Z)]
<
(24)
Moreover, using Theorem A.5 with (cc) = c((u=1-1) holds
- log( and = c(att))-(110))
ET (X, IPT (Qi-a(mm)
( < f (Vz (Vz(X, k))
$ <exp + PT (Qi-a-c(1) < Jon (Vn+1) S Qi-a(A) Xn+1 x. Zn+1 =2)
21

---

Published as a conference paper at ICLR 2025
By Lemma A.6, nf logn S a a)), then, setting en v 8a(11 an log ensures that exp(-n0(<n)) I n-1 We assume in the following that n log I a a), because, if it not the case, the final upper bound obtained at the end of the proof is still valid. Thus, we get
E? B" (Pn+1(X,
s nn- 1PT (Qi-0-e (4) S (V++1) S Q1-o(2)).
(25)
Let's define 7 by
a 8= a llyxx)).
We now show that Qi-a & Qz(1). By continuity of the cumulative density function of fxx, (V2 Y),, we have
a-a=Pa PT
FiN (V2 Q1)a(a))
PT ( (Vxx( s (Q) ddv((xx.;;xx x xl(x).
Hence, it follows that
PTT (J=x 1 Q)-a(()) S STSP' (V222(2((XX)) s Q+(1)).
Thus, the previous line implies that Q1-a(p) - (1()). Once again, using the continuity of the distribution of fixz (Vz(X,Y) we can write
PT (0i-a(m) < fin. (V (2, Yn+1)) S SQi (1)) SPT TTT (01-a-c, (M) < fin (Vo+1) S Q+(m))
= (Q, - F 100 (4)) = +6n - 11 1+a
=n Sa(a a)n logn + dIv lllx)).
Plugging the previous inequality inside (25) yields
ET [P (X, Z)] -n + V8a(1 ann- logn + drv drv(Px,y:Px Il(x)).
Therefore, (24) implies that
X PT (P" (Yn+1 E (xn, Zn+1) <1-a-p)
n + +''+188(11 a)n log n + drv PP lllxx) + E (dy (yy(((y) (26)
Step 2: Upper bound. Using (23), we obtain
P (PT (Yn+1 E ca((Xn+1) Xn+1, Zn+1) > > a p)
S SP' (RxIxxx(R2(X))) fxx (+))) + drv (Prjx= xxxxxxx + (X,2)
aap)) >
The continuity the distribution of f=-1 (Vz 8)) implies
1-a= 1P (V2
( /
(V2 8)) s < = -
(dxx).
Since Iy almost surely. Therefore, using the Markov's inequality gives
(p))) 2 a, deduce that Iy|xx= (2; f (+)))
ET [ddv(Pyyxx' Tyxx)] + BT (X.2)
(
p (PT (Yn+1 E Cx(+111) Xn+1s 1n+1) > aa pp)
[n++1
(27)
Moreover, applying Theorem A.7 shows that
(n+1(x, 2) S n +PT (Q1-a(A) f (V, Xn+1)) < Q1 (4) Xat1 = x, Un+1 =
(28)
22

---

Published as a conference paper at ICLR 2025
Let's define y
7 min dIv(Pxxr;Px llyxx)).
We now show that (2(4) - Q1-a(i). By continuity of the cumulative density function of fTx,2 (V2(X, F)), we have
- a-a= PT (
Q1-a
S IPT (STX, (Vz(, s <QI-a( + dTv((xxy;;Pp x llyx)).
Hence, it follows that
2 7SP' P" (Frx. (F=x2(V2(XXX) (V) Qi-a
Thus, we deduce that (A) 2 Qz(u). Using the continuity of the distribution of Fix (V2(X, we can write
pT (Q1-a(A) < f (V, Yn+1)) - Q1 Qai (1)) SPT (2r(w) < f (V, Ynt1)) S Q1- Q1-a-ea (1)
F (Q1 (1)) F (Q2(1))
+ -
=n + /8a(1 - a) logn + d πlyx))
Plugging the previous inequality inside (28) yields
B" 2x 5n- + V8a(1 log dTv(Px,y;xx Ilyxx).
gat1
Therefore, (27) implies that
P (PT (Yn+1 E Ca(Xx)1) Xn+1, Zn+1) a1
n- + 188(1 a)m logn + drv(Pxxx:Ps llyxx) + E (d (29)
Step 3: Bound on ET ddr (Pyix: [y Let's denote Vyjx=r 2- (Pyix=== + - Since Py|x== < =y and Hy|x== & Vyjx=z there exists two Radon-Nikodyn derivatives 91 (z. )) and ø1 (z. :) of Py|x== and Hyjx== with respect to Vyjx-=r- Moreover, and 92 are also the
derivatives Px,y and Px x Jlyxx with respect to Px x zyjx. By definition of the total variation distance, we have
E7 (drv(Pyixillyxx) = drv(Pyyxx
2 / 191 v) g2(1 by
ddv (pxx: Px Hylx))
(30)
Step Combination. Finally, using (26)-(29) and (30), follows that
PT ((PT (Yat1 E Ca 1 Zn-1) - 1 + a > p)
-1 + 1280(1 - ann log n + 4drv(Px.y:Ps x Il(x))
P
Note that the proof assumes - logn < 8-3a(1 - a). To ensure the validity the previous bound even when this assumption does not hold, we increased the term /32a(1 - a)n log n to / 1128a(1 - a)n logn. n.
Now are ready to prove the result of Theorem 3.3.
23

---

Published as a conference paper at ICLR 2025
Theorem A.9. Assume HI-H2-H3 hold. If the distributions of fix (Vz(X,Y)) and F (Vz(X, Y)) are continuous, then, Ve E (0,1) there exists (An) nEE such that lim inf p(( Zn+1)= E All) 2 and also Ip (Yn+1 E Cx(Xn+1) (Xn+1. Zn+1) (z,, 2)) - 1 + Op (Vn- logn + rra)
sup (1,=)EA!)
Proof.
First of all, define the following variables
cn+1 (z) 2) 1T (Yn+1 (n((ntz)l Zn+1) (2, 1 1+ a
d, = drv dpv((xxy;Ps) x )
Applying Theorem A.8, we obtain
P P(cn+1(Xn11 Zn+1) > p) Pd, > rn) + +((n+t1(An11 ( > p: dn I rn)
< PP (dn > Tn) + [r. IpT (G++1(Xn+1) Zn+1) > p)]
2n v 1188a(1 a) log n + 4r,
S P (d, rn)
Finally, using H3, we get lim P(dn > rn) = 0. Therefore, for any > 0, there exist M, > 0 and ne E N such that, Vn 2 ne. it holds
P (Cn+1(Xn+1 Zn+1) Me x (Vn-+logn + +ra)) Se
(31)
Given E (0, 1), let's consider the following set
S Me x (Vn=~logm + A/(0 = { (Xn+1(w), Znt In+1(w))= we E 92 Ca (w)
Equation (31) implies that
lim Zx+1) E E 21 21-6,
and by definition of A also have
(x) =0p==pppp =Op (Vn- log + tra)
sup (a.))
Note that, (31) also shows that
IPT (Yn+1 E C. (Xn4z)) | X - 1 + al = Oz (n-1/2/oogm + ru)
=0;
Vlo
A.4 ADDITIONAL RESULTS
Let's denote the conditional c.d.f of f-xlz (V2(X, by
Fa,z(-) = { S IP (F Y)) - (x, )))
Lemma A.10. Assume that Q1 + &p almost-surely as n + xc. If Fx.z is continuous almost-surely, then lim Pat1 O. s x Px--almsst everywhere.
Proof. First, define the following sets:
A = w E Ωi lim Q1-a (w)(() +). 2=000
B fw Ωi Fx(e),(()) is continuous).
24

---

Published as a conference paper at ICLR 2025
For all An B, it holds
lim (w) (Q1-a ([m(WW) Ag) = (w) (p). 1-+00
Moreover, note that we can write
Potl F2,)(1) - F2, Q1-a(Hu))
Hence, deduce that
= P (AA
SP
w ::: lim (x(w))z(W) (Qi-a ((m((w)) Ag) = (x( (p)
=P lim (x,2)
Putl =0)
P lim (a.2)
Put1 = 0 (X, = (x,2)) Px
Jdx
The last line implies that P px41 + 0 almost Pz|x x Px-everywhere.
The prediction set, defined in (6), is derived from the (1 a) -quantlle of the conformity scores {f= (V+) U foo). However, {oo} can be removed from these conformity scores. Inspired by Romano al. (2019); Sesia Candès (2020), we prove corollary of Theorem 3.1. Its result demonstrates the marginal validity of the prediction set defined as
(x(x) = R2 (x: JTu.. (Q(1-a)(++=>)) Ei (=)))))) (
(32)
While the prediction set C. (z) relies on the quantile of the distribution A Ek /, (V)) its proof reveals that this prediction set equivalent to C. (2.).
Corollary A.11. Under the same assumptions in Theorem 3.1, for any E [1/(n + 1}, have
1 1- S (Yn41 Co (Xn+ <
n
where the upper bound only holds if the conformity scores ( are almost surely distinct.
Proof.
Let E R such that (n 1)-1 S 1, and recall that
Σ 6 b. (v6) + + 8xc k=1
pn
Since a 2 (n + 1)-1, the quantile Q1-a (Mx) ) is the hi-th -th order statistic of Vi,..., Vn, where
Ve (Vk), and ho = [(1 (n) +
However, V3 (Ka-1 ka), we have
Qa ( En 8v.) V(K.. Since (X,+1) Rzmni (Xn+1i fram, (V(n,))), Theorem 3.1 implies that
1 a (Yn+1 Rz.11 (Xati (Qx (1 ( <1 1
Setting 3 (1 (1 +n+ 11) in the previous inequality and using the definition of C, (Xn+1) given in (32) concludes the proof.
25

---

Published as a conference paper at ICLR 2025
B EXPERIMENTAL SETUP AND RESULTS
B.1 DETAILS OF THE EXPERIMENTAL SETUP
We use the Mixture Density Network (Bishop, 1994) implementation from CDE (Rothfuss et al., 2019) Python package' as a base model for CP, PCP and CP². The underlying neural network contains two hidden layers of 100 neurons each and trained for 1000 epochs for each split of the data. Number of components of the Gaussian Mixture was set to 10 for all datasets.
For the CQR (Romano al., 2019) and CHR (Sesia & Romano, 2021) implementation". The underlying neural network that outputs conditional quantiles consists of two hidden layers with 64 neurons each. Training was performed for 200 epochs for batch size 250.
the original authors'
For the CPCG (Gibbs et al., 2023) we also use the original authors' implementation" We use the same splits and preprocessing steps as for other methods. The underlying prediction model neural network with of two hidden layers of 64 neurons and is trained for 1000 epochs with early stopping. Embeddings from the last layer are collected to form feature maps, denoted as ((X) in the original paper. A linear functional class F is used. We fixed some minor bugs in the authors code to avoid an infinite loop and decreased maximum number of iterations to lower the computational cost.
For LCP (Guan, 2023) we once again used the original author's 's implementation" The only change was that we supplied our own preprocessed and split data, the same for all the methods discussed. Most datasets had to be subsampled for training the model since the method computes full Hessian on the train set, its SVD decomposition, and also uses cross- validation estimates the residuals (scores). We kept all the hyperparameter values in the original implementation.
For CDSplit* we use the implementation from Wang et al. (2023) 7. The same repository also pro- vides implementation of datasets preprocessing, Mixture Density Network training and an adaptation of CQR that we built upon. The number of clusters for CDSplit" was set to 20, the profile density distance was estimated by partitioning y space into grid of size 100.
We replicated the experiments for 50 random splits of all nine datasets. To lower noise in calculated performance metrics, we reuse trained networks and samples across different top-level algorithms for each replication.
B.2 WORST-SLAB COVERAGE
Here present some additional experiments related to conditional coverage achieved by different methods. We have used Worst Slab Coverage metric, which is sensitive to the set of labs considered during the search. Following (Cauchois et al., 2020; Romano et al., 2020b), recall that slab is defined as
Sy = {x E R < of x < b).
where v E IR' and a, E R. such that a < b. Now, given the prediction set C. (x) and 5 E [0, 1]. the worst-slab coverage is defined as:
P(Y E Cx(X) X E Sp.a,)) s.t. P(X E So,a,)) 2 8. WSC(Ca,, 5) bEBER
inf
In our experiments we follow (Romano et al., 2020b) in our implementation of this metric. Namely, we use 25% of the data to find the worst slab and the use the remaining 75% to calculate the final value on this slab. We use 5000 randomly sampled directions, that are the same for each algorithm and change for each replication.
B.3 EXTENDED RESULTS OF REAL DATA EXPERIMENTS
Table 3 summarizes all metrics from our real-world data experiments. For conditional coverage we report worst-slab coverage with (1 - 6) = 0.1. On six out of nine datasets CF2 method achieves the
'https: http://thhbbcccmmm/ess////aa
c Predi ct
26

---

Published as a conference paper at ICLR 2025
best result in conditional coverage. In terms of interval width PCP method produces the narrowest intervals.As we can see, it happens at the expense of conditional coverage: PCP often achieves significantly lower values.
We also present a more detailed view of set size differences between the methods. In the main part we reported average rank of each method in Figure 8. We ranked the algorithms by their projected area at each test point and averaged the ranks. Here we show raw areas of the projections onto each pairs of axes for s sgemm_small standard deviation so that different projections will be in the same scale. We see that PCP produces smaller set sizes like in one-dimensional case. Quantile-rggressoon based methods have the largest sets, even larger than the fixed-sized sets of CP. Our approach demonstrates only modest increase in prediction set size compared to PCP while achieving sharper conditional coverage.
small 1 dataset in Table 4. All targets were standardized zero mean and unit
Table 2: Summary results of experiments on real data.
Dataset
Metric
CP
PCP
1lyxx
CP²-D
CP²-1,
CHR
CQR
CQR2
CPCG
1CP
CDS
M. Cov.
0,90
0.90
0.93
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.92
bike
C. Cov.
0.79
0.85
0.92
0.89
0.89
0.88
0,90
0.87
0.90
0.87
0.90
Wad
0.71
0.71
0.83
0.80
0.79
1.94
2.25
2.31
0.76
1.58
0.61
M. Cov.
0.90
0.90
0.91
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.90
bio
C. Cov.
0.88
0.89
0.91
0.90
0.90
0.90
0.89
0.89
0.89
0.89
0.89
Wadd
2.34
1.89
1.95
1.95
1.97
1.92
2.13
2.10
2.04
2.25
1.54
M. Cov.
0,90
0.90
0.91
0.90
0.90
0.90
0.90
0.90
0.89
0.90
0.96
blog
C. Cov.
0.60
0.74
0.91
0.90
0.89
0.87
0.87
0.86
0.87
0.74
0.93
Wad
0.60
0.30
0.72
0.71
0.72
0.31
0.44
0.39
0.71
0.59
0.67
M. Cov.
0.90
0.90
0.93
0.90
0.90
0.90
0.90
0.90
0.89
0.90
0.96
fb1
C, Cov.
0.49
0.64
0.92
0.89
0.88
0.87
0.90
0.87
0.86
0.66
0,90
Wed
0.47
0.28
0.58
0.59
0.56
0.26
0.37
0.33
0.60
0.42
0.61
M. Cov.
0,90
0.90
0.93
0.90
0.90
0.90
0.90
0.90
0.89
0.90
0.96
fb2
C. Cov.
0.50
0.61
0.91
0.88
0.88
0.88
0.89
0.89
0.87
0.65
0.90
Wed
0.53
0.32
0.65
0.65
0.62
0.33
0.43
0.37
0.54
0.44
0.76
M. Cov.
0.90
0.90
0.89
0.90
0.90
0.90
0.89
0.90
0.90
0.90
0.92
meps19
C. Cov.
0.54
0.78
0.89
0.89
0.90
0.90
0.88
0.89
0.89
0.68
0.88
1.05
0.73
1.02
1.07
1.19
0.76
1.14
1.19
1.19
0.98
0.71
M. Cov.
0,90
0.90
0.89
0.90
0.90
0.90
0.90
0.90
0.90
0.90
0.92
meps20
Cov.
0.58
0.80
0.89
0.90
0.90
0.91
0.88
0.89
0.89
0.71
0.89
Wed
1.06
0.75
0.98
1.04
1.15
0.77
1.09
1.17
1.29
1.05
0.74
M. Cov.
0.90
0.90
0.89
0.90
0.90
0.90
0.90
0.90
0.90
0,90
0.92
meps21
C. Cov.
0.54
0.81
0.89
0.89
0.89
0.90
0.89
0,88
0.88
0.68
0.88
Wed
1.04
0.72
0.99
1.04
1.16
0.79
1.13
1.21
1.24
1.04
0.71
M. Cov.
0.90
0.90
0.82
0.90
0.90
0.900
0.90
0.90
0.90
0.90
0.91
temp
Cov.
0.87
0.89
0.81
0.89
0.88
0.86
0.85
0.86
0.89
0.87
0.89
Wad
0.87
0.92
0.78
0.93
0.96
1.31
1.48
1.30
1.18
1.25
0.86
Table 3: Summary results of experiments on real data. "M. Cov." stands for marginal coverage, "C.
Cov." is the worst-slab coverage (here (1 d) = 0.1), and wad average total length of the prediction sets, scaled by standard deviation of Y. Nominal coverage level is set to (1 a) = 0.9. For Iy PCP, CP2-PCP we use the same underlying mixture density network model with 50 samples. CHR and (2) also share the same base neural network model. We average results of 50 random data splits. For each dataset, we highlighted the algorithm achieving conditional coverage closest to the nominal level.
B.4 OTHER PERSPECTIVE ON CONDITIONAL COVERAGE
The worst-slab coverage metric used in the previous section is not always helpful: (1) it provides a single number for each method, and (2) the selected slab is different for each algorithm. In practice might be interested in how sharp the coverage is along the portion of the input space spanned by the test data. To explore this, used two approaches: dimensionality reduction and clustering. Results
27

---

Published as a conference paper at ICLR 2025
Hepp
CQRZ
CD-eplat"
0.930
0.000
0.875
Wousselah coweage,
0.850
0.825
0.775
bdle bdo
blog
fbl Es2 moppl19
mnsp21
tetap
Figure 9: Worst-slab coverage on real data (mean and stdev.). Results averaged over 50 random splits of each dataset. Calibration and sizes set to 2000, 50 conditional samples for PCP, CP² and x Worst-slab coverage parameter (1 6) 0.1. Nominal coverage level is (1 a) = 0.9 and shown in dashed black. Methods with conditional coverage below 0.75 are shown.
Table 4: Prediction set size comparison for @yjmm__smal dataset. Rows correspond to different pairs of targets (dataset has targets). For each method the reported value is the mean area of the 2D projection of the prediction set to the corresponding axes pair.
Cp²
Axes
PCP
Hy
PCP-L
PCP-D
CHR
CQR
CQR2
(0, 1)
2.137
0.435
0.517
0.576
0.560
2.290
2.550
2.436
2)
2.145
0.435
0.518
0.577
0.561
2.267
2.506
2.358
(0.3)
2.145
0.436
0.519
0.578
0.561
2.086
2.366
2.172
(1
2.146
0.435
0.517
0.576
0.560
2.388
2.622
2.546
3)
2.146
0.435
0.517
0.576
0.560
2.166
2.461
2.314
(2, 3)
2.154
0.436
0.519
0.578
0.562
2.153
2.430
2.255
for clustering with HDBSCAN are presented in the main part in Figure 5, here turn to dimensionality reduction.
First apply UMAP algorithm to project data to two dimensions and then construct heatmap plot to show coverage in each bin the histogram. Results for meps_1s 9 dataset are presented in Figure 10. Nominal coverage is set to (1 a) = 0.9 and corresponds to gray part of the color scale. We can see that our method and baseline Hylx perform better than CP and PCP across the space.
B.5 ADDITIONAL SYNTHETIC DATA EXPERIMENTS
B.5.1 UNIMODAL SETTING
To extend our toy one-dimensional example from the main part, we also test out our algorithm and other methods a synthetic dataset with multiple input dimensions. We generate dataset with 10000 instances, 10 input features and one output as follows: first we sample features from multivariate normal distribution with random full rank covariance and then compute values of target variable using the Rosenbrock function. We follow the same evaluation protocol as for our main experiments and results summarized in Figures 11 and 12.
28

---

Published as a conference paper at ICLR 2025
Date
CF
PCP
CPI-POPLL
CHR
CER
C052
CP--PCP-
02
01
Figure 10: Conditional coverage after dimensionality reduction, meps_ 21 dataset. Data projected to two dimensions using UMAP algorithm with Canberra metric, with the n__neighbors hyperpa- rameter set to 2. Nominal coverage is set to (1 a) = 0.1, corresponds to gray on the color scale.
0.9
0.7-
Woest-slbb covarage
PCP
CP--PCP-L.
0.5
cp1-PCP-D
CHR
CQR
CUR2
CPCG
L.PP
roeen_10d
Figure 11: Conditional coverage for synthetic data. Nominal coverage is set to (1 - a) 0.1, shown in dashed red.
On this data most methods provide adequate results with the exception CP. which significantly undercovers. The sharpest conditional coverage is demonstrated by our methods with CPCG following close behind. Size of the intervals is also smaller for methods, although CP and PCP produce even shorter intervals. Methods based on NN quantile regression produce largest intervals, even though we in the unimodal setting, where expect the opposite.
29

---

Published as a conference paper at ICLR 2025
2.5
CP
Blyx CP-PCP-1.
PCP-D
CQR CQR2
CPCG
POP
CHR
LCP
1.5
1.0-
0.5
0.0
roeen 10d
Figure 12: Sizes the prediction sets on synthetic data. We divide the size of the set by the standard deviation of response to present the results on the same scale.
1.0
PCP
1yyx
CSR-PCPDD
0.8
Worst-elab coverage
0.6
0.5
0.4
0.3-
0.2
10P
10a
Number of features
Figure 13: Conditional coverage for high-dimensional synthetic data. Nominal coverage is set
(1 (x) = 0.1, shown dashed black.
B.5.2 HIGH DIMENSIONAL SETTING
In this experiment we employ the same procedure to generate the datasets. This time we generate multiple datasets with varying number of input features ranging from 10 to 20000 on a log scale. We keep the size of training data fixed at 10000 instances, use 2000 samples for calibration and testing and all other settings like in our previous setup. Due to computational constraints we consider limited number of methods. Results are shown in Figures 13 and 14, As shown by our baseline lly conditional coverage performance of the base model decreases with the number of features, similar results can be seen in set size plot. Other methods all increase the set size dramatically as well. We do not any performance benefits of our approach in this setting, perhaps due to the simplicity of the underlying function. Generating complex multidimensional regression datasets and continuing this line of analysis will continue in future work.
30

---

Published as a conference paper at ICLR 2025
PCP
1bpx
CP--PCPDD
2.5
2.0-
3 1.5-
1.0-
0.5
10
Number of features
Figure 14: Sizes of the prediction for high-dimensional synthetic data. We divide the size of the set by the standard deviation of response to present the results on the same scale.
C ADDITIONAL DISCUSSIONS
C.I HIGHEST PREDICTIVE DENSITY (HPD) REGIONS
CP2 with Explicit Conditional Density estimate: CR2-HPD. Assume that an estimator the conditional density function is known, denoted by 7Y]X=2- The confidence set is defined as R( = {y E y: (y) 2 -t}. We omit the variable from the notation, as we do consider exogenous randomization in this case. The parameter T₂ obtained by solving
T2 = arg min {
R: (R(E:T) (xxx dy 2 a)
(33)
We then compute V(z,8) v) > (v) and derive the prediction set
Cx(x)= = {y y: ( 2 -fr, (Q1-a (pa))}
If we take (v) and 90 the method shares similarity with the CD-spl method, proposed in (Izbicki et al., 2020). While op-sppitt uses V(z, y) as the conformity score, our method uses (V 3)), which incorporates the information from TN to modify (y) The C22-HPD workflow is summarized in Algorithm 2.
Of course, the computation (33) is in general highly non-trivial. Izbicki al. (2020) suggested to use binning, therefore approximating the conditional predictive distribution with histograms. The method is restricted to case where the dimension y the response is small; see (Izbicki et al., 2020) for the case of y R. When the dimension becomes larger, then the estimation of HPD is typically based on Monte Carlo methods, thus requiring the introduction of auxiliary variables.
The HPD set is theoretically the optimal confidence region in terms of size. Izbicki al. (2022) developed two algorithms, CD-split and HPD-split, which converge to the HPD set; see Theorem 27
and Theorem 28. In HPD-split, the conformity score is (f x) ()) rather than f(y x)), where
((2 æ) approximates the conditional CDF of f(Y IX). This ensures that H(f(Y X) X)
UO0 1) given X, which implies that H(f(Y | X) Xx) is independent of X. Consequently, if f(y æ) converges f(y 2),, is expected that (f(Y X)) becomes approximately independent of X. However, computing H H(f(Y X) X) requires integrating the conditional density, which can be challenging in high-dimensional spaces.
31

---

Published as a conference paper at ICLR 2025
Our CP²-PCP method offers more practical approach for digensinmnsio settings by generating balls centered at sampled points with radii set in function of z. This adaptive radius helps mitigate the issues of under-coverage over-coverage often encountered with PCP. Additionally, the prediction set being union balls, is particularly beneficial when dealing with multimodal data.
Algorithm 2 CP² CP2-HPD
Input: dataset {(X,, Yx) he|Mj significance a, conditional density xr|x. function ft. I/ Compute the (1 a) -quuuutnneleeeeee
for k = to do
Set V = - - (Yx)
Set F. Tx, as given in (5)
Q1-a (kn) - [[1 (n + 1)]-th smallest value in (V)) foo)
I/ Compute the prediction set for new point E Rdd Compute Ta (5).
Output: C. (x) = {y E y: (xIx= fr. (Q1--(())))) (110
C.2 DISCUSSION ON ASSUMPTIONS
HI: Assumption on the shape of confidence regions. This assumption does not impose restrictive constraints on the shape of the confidence regions. It allows for a broad class of geometries, making it widely applicable. Most prediction sets proposed in the literature naturally satisfy this assumption. For instance, it permits level sets of a density function or unions of ellipsoidal regions.
H2: Monotonicity of T + (i)). We assume that the function T + fr is monotonic and specifically increasing. This property ensures that the region R(x: f-. (v)) expands as the parameter Tu increases. This assumption is crucial because we want the confidence region to grow in size as the parameter Ty increases.
H3: Convergence in total variation. This assumption ensures the convergence of Px & y to Px & Pyjx in total variation. While this condition is essential for the theoretical validity of our approach, it is also the most challenging to verify in practice. Kernel-based density estimators satisfy this condition under specific choices of the kernel function and the bandwidth parameter; see, for example, (Devroye & Lugosi, 2001, Chapter 9) and (Li et al., 2022).
C.3 DISCUSSION ON ADDITIONAL. METHODS
Kiyani et al. (2024) introduce Partition Learning Conformal Prediction (PI.C)), method designed to improve conditional coverage by leveraging learned partitioning of the covariate space into m groups. Key aspects of the methodology are as follows:
1. Optimization Framework. The optimization problem is framed minimize the empirical risk using the pinball loss function, a well- known loss metric for quantile regression. Specifically:
h" 4".4" = arg min
ex)
QERT. NEW
where h represents the partitioning function over the covariate space and represents quantile thresholds.
2. Prediction Set Construction. The optimal prediction set defined as:
C (z) = {y: S(z, y) S of h (x)).
We used the notation q: denote the random variable that takes the value qi with probability P;- change here.] This ensures that the prediction set provides conditional guarantees by dynamically adapting the learned partition.
32

---

Published as a conference paper at ICLR 2025
NAME Linear
(v) f+(0)
T v v
Difference
T T+ V
Table 5: Adjustment Functions fi, their inverses f and yp values used in our experiments.
3. Pinball Loss. The pinball loss, core component of the optimization problem, is defined as:
if 2 5, (g 5) (1 ()s if <
aa(g
By minimizing this loss, the method aligns quantile estimation with desired coverage levels.
4. Optimal Prediction Set. The proposed prediction set Cap guarantees full conditional coverage:
Capa (x) {v E y: 5(X,Y) S 9-a (S X = x))
Here, (z) is derived the minimizer of the pinball loss over the joint distribution of covariates X and outcomes
Q1 (-) E arg min (xx.))-Da(f(xx..)))
f: X
Theoretical results control the Mean Squared Conditional Error of PL.CP (Kiyani et al., 2024, Corollaries 3.7 and 3.12). measures the deviation the conditional coverage from the threshold 1 1-a.
Choice of fi. We present examples mappings ft and their inverses f- in Table The choice of the mapping fe is crucial for the performance of the method, and investigate their impact in Section 4. For instance, choosing f, (v) TU results in approximately conditionally valid prediction sets, long as Iy accurately estimates the conditional distribution y x=ri see Theorems 3. 3.2-3.3. Initially we also considered other adjustment functions based on exponent, sigmoid and tanh functions, but they all performed worse than linear and sum. As we show in Table 3, these two selected adjustment function perform similarly, showing only marginal differences on some datasets. Designing new adjustment functions is possible future research direction.
33


Reviews:
[{"review_id": "ZoJDNnasi6", "reviewer": "Reviewer_gFXs", "summary": "This paper looks at the central issue of covariate-conditional validity of conformal prediction methods. They propose a systematic and novel procedure of turning a black box estimation of conditional distributions (Y|X) into a valid conformity score which then can be used to construct prediction sets. They carefully design the procedure to make their prediction sets adaptive to the behavior of the conditional distribution. Their method effectively generalizes the previous literature on using conditional distribution estimation by 1) providing algorithmic and theoretical results targeting conditional coverage and 2) going beyond one-dimensional regression setting.", "questions": "No further questions. I might ask more once I got the authors response.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The issue of conditional coverage of conformal prediction methods is of particular interest in CP community. They expand the ideas of using an estimation of conditional coverage to enhance the covariate-conditional performance of CP to the more general setting of multi-dimensional prediction tasks.\n- They also provide theoretical guarantees on the relation between the quality of the conditional distribution estimation and the improvements in the conditional coverage property of CP, which was a missing flavor for most of the previous works in this line of thinking.", "weaknesses": "- In general, the whole line of work based on estimations of conditional density suffers from the curse of dimensionality (covariate dimension). Therefore, it is important to see some empirical evaluations of the proposed method on high dimensional tasks (in particular image classification), even if it doesn't work very well, it helps the follow-up works with having a more accurate understanding of your method. Another interesting experiment to see is a synthetic regression task that you can directly plot the (conditional) coverage properties vs. dimension of the input and showcase the degree of tolerance of your proposed method. \n- Focusing on the lower dimensional tasks, where conditional density estimation is more feasible, It is good to see the performance of your proposed method in comparison with recent methods like the one proposed by https://arxiv.org/abs/2305.12616. You can for instance set their function class to be a linear map form the data itself to a scalar threshold, or train a neural network regression model in the training time and then set the function class to be a linear head from the last layer of the trained neural network to a scalar threshold. In general, it is important to see whether using the conditional density estimation (when feasible) can actually beat the methods that does not rely on conditional density estimation.\n- Taking a step back, intuitively, it is obvious that the usage of an estimate of the conditional density estimation should improve the conditional coverage behavior of CP. However, it is not entirely obvious whether all the information in the density function is needed to construct perfect prediction sets. In other words, the key question is what parts of the information in the conditional density function are actually needed for constructing prediction sets. This question is very important to look at as the answer to it might reveal a way to beat the curse of dimensionality, as then you can only try to learn the useful information instead of the whole conditional density function. To this end, 1) it might be good (as a suggestion) to discuss this point of view (maybe as a future work) in your paper. In particular, how fundamental conditional density estimation is for your pipeline. 2) It is good to discuss the methods that are based on the described idea in your paper, for instance https://arxiv.org/abs/2404.17487, as that helps the reader to have a better understanding of the whole methodology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3JA3KxvBNu", "reviewer": "Reviewer_mpDN", "summary": "This paper achieves powerful conditional coverage via a technique that relies on sampling from an empirical estimate of the underlying conditional data distribution. Their method achieves impressive empirical benefits alongside powerful provable guarantees. \n\nOverall this paper has clear contributions and is very sound. I vote to accept this paper.", "questions": "It would be nice if the authors added in some analysis of how likely or under what conditions these assumptions tend to hold, or rather how restrictive they are. It seems they are not that restrictive, but some analysis here would be nice.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. the underlying approach of estimating the conditional distribution via sampling and proposing the conformal set using these samples (to my knowledge) is unique to this paper\n2. This paper has very nice asymptotic guarantees of performance under different underly data distributions\n3. The approach is very simple and applicable, making it generally useful in many fields. \n4. The empirical validation is very impressive", "weaknesses": "1. Some of the figures are not accessible. It is difficult to see for someone who is red-green colorblind. This includes Figure 1. \n2. Some of the presentation of the theoretical ideas, especially on page 6, is difficult to parse. Better formatting would increase readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4KBTmSoD8P", "reviewer": "Reviewer_PMEd", "summary": "The authors propose a $\\text{CP}^2$ framework for conformal prediction that aims to achieve approximately conditional coverage. The key difference from classical split CP is the introduction of a parameter, $\\tau$, defined through either the estimation of the conditional distribution $P_{Y|X}$ or the use of a conditional generative model, allowing for adaptive threshold adjustments. Theoretically, they provide a finite-sample marginal coverage guarantee as well as an asymptotic guarantee through a upper bound on conditional coverage. The framework's efficiency is demonstrated through experiments on both synthetic and real-world data.", "questions": "1. About the theoretical guarantees, there is a lack of rigorous theoretical discussion on the superiority of the size (length) of intervals. Is it possible to provide any properties about the superity in terms of size? Including some theoretical investigations would be appreciated.\n\n2. Regarding the experiments, I notice that the authors didn't compare with some important baselines about this problem, for example, the LCP in [1], RLCP in [2] and conditional calibration method in [3] should be considered. I'm curious about the performance of the CP^2 method in comparison to these works in this area, and additional experiments would be beneficial to provide further insights.\n\nReferences:\n\n[1]  Guan, L. (2023). Localized conformal prediction: A generalized inference framework for conformal prediction. Biometrika, 110(1):33–50.  \n\n[2]  Hore, R. and Barber, R. F. (2023). Conformal prediction with local weights: randomization enables local guarantees. arXiv preprint arXiv:2310.07850.  \n\n[3]  Gibbs, I., Cherian, J. J., and Candes, E. J. (2023). Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.12616.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper provides a specific approach to leverage information from the conditional distribution to improve conditional coverage. Besides estimating conditional distributions directly, the authors also consider alternatives using a conditional generative model when identifying HPDs is challenging.", "weaknesses": "1. The paper's writing could be improved, particularly in terms of clarity and presentation. For example, the literature review lacks clarity, and could benefit from a more comprehensive and topic-oriented discussion of related work.\n\n2. Regarding the experimental section, it is noted that several key baselines from existing literature have been overlooked. Additionally, it seems that the superiority of CP² in terms of worst-slab coverage is not particularly evident comparing with CQR/CQR2 in Figure 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zaerfNedBm", "reviewer": "Reviewer_azSK", "summary": "The paper offers a new score function for constructing conformal prediction sets to improve adaptivity and approximated conditional coverage.\n\nInstead of explicitly relying on a score function, they use a confidence set function---an idea that is known in the literature. The proposed construction of the prediction set suggests scaling the conformal scores \\lambda_k by \\tau_k, extracting the 1-alpha quantile Q, and then applying the \"inverse scaling\" of Q by using f_{\\tau}.  \n\nSince their method requires estimating Y|X which is generally hard---especially when Y is high dim.---they offer an approach to using a sampling generative model for constructing the prediction sets (Algorithm 1); inspired by Wang et al.\n\nThe authors provide a marginal guarantee, approximated conditional coverage (depending on the quality of the estimator), and an asymptotic conditional coverage guarantee.", "questions": "It would be great to provide some intuition on when PCP-D is preferred over PCP-L (and vice versa).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. A conformal framework to construct conformal prediction sets with improved adaptivity.\n\n2. Thorough theoretical study (marginal, conditional, asymptotic analysis for the coverage).\n\n3. Thorough experiments, comparing CP^2 to leading methods except the multi-dim. case; see comment below.", "weaknesses": "1. While the paper offers a general construction for prediction sets, it shares ideas with existing methods such as (1) local conformal---the scaling part; (2) HPD split or distributional conformal prediction by Chernozhukov et al.---both using the conditional distribution estimator; and (3) sampling using generative models, inspired by Wang et al. Of course, the paper nicely combines these ideas into one framework, which is great, but I am not sure it brings a novel concept. I would be happy to get the author's feedback here: what is the concrete edge of the proposed method compared to prior work that also builds on conditional distribution estimation to promote adaptive/conditional coverage?\n\n2. I suggest better explaining the role of Z. It was not clear to me what the variable Z is until reaching line 252. For example, in line 152, it is not clear at all what you mean by \"sampled according to a kernel Z|X\". Consider improving the exposition in line 152, e.g., by providing a concrete example.\n\n3. Section 4.1: how does the CP^2-HPD perform compared to HPD-split by Izbicki et al. (2022)? Such a comparison is missing, and it is important to include it to understand the advantages of the proposed method. Please clarify why you expect the proposed method to improve performance.\n\n4. The experiments with multi-dimensional response lack stronger baseline methods, such as the one by Feldman et al (reference below) and/or related techniques. If a full experimental comparison is not feasible, it is crucial to discuss the conceptual differences between the methods.\n\nS. Feldman, S. Bates, and Y. Romano, \"Calibrated Multiple-Output Quantile Regression with Representation Learning,\" JMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ivkXdM9sb4", "reviewer": "Reviewer_c5XA", "summary": "This paper proposes a conformal prediction method to enhance conditional coverage while still ensuring a finite-sample marginal coverage guarantee. The authors consider estimating the conditional distribution of $Y|X$ on the training data and use this estimator to define a localization parameter $\\tau$ for each calibration and test sample. These parameters are then used to adjust non-conformity score values. The authors prove the marginal validity of their method and give an inflation bound for the conditional coverage. They also prove the asymptotic conditional validity of their proposed interval in the oracle sense. Experimental results show slight superiority of the proposed method compared with other conditional conformal prediction methods.", "questions": "1. Since the proposed method is built on many existing works, could the authors explain more concretely their main contribution about the methodology (like in which step)? This would be helpful for the readers to get the main idea that do not exist in previous literature.\n\n2. As I have stated in the Strengths part, I believe the method will outperform most conditional conformal methods in multi-modal settings, which is shown in the synthetic experiment.  However, I'm still curious about the comparison result under the common unimodal case. It would be better to include some related experiments.\n\n3. I have noticed that an important reference [1] is missing. The LCP method [2] is cited but has not been considered in experiments. As important progress in conditional conformal prediction, these two methods should act as good baselines in the experiment. I will be willing to raise my score with either more experiments or more theoretical results showing superiority to the above two methods. \n\n\n[1]Gibbs, I., Cherian, J., and Cand`es, E. (2024), “Conformal Prediction With Conditional Guarantees,” arXiv preprint arXiv:2305.12616.\n\n[2]Guan, L. (2023), “Localized conformal prediction: A generalized inference framework for conformal prediction,” Biometrika, 110, 33–50.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The nonconformity score function proposed is similar to dividing the residual score by a conditional standard deviation estimator, which is replaced by a factor relating the conditional distribution of Y|X by the authors. In my opinion, the proposed method is especially suitable for multi-modal settings, in which directly characterizing the overall upper and lower prediction bound is not effective.", "weaknesses": "Despite reasonable, the proposed method only shows slight empirical improvement compared with existing methods. The theoretical results are also achievable by methods like the LCP (Guan, 2023). There is a lack of theoretical results regarding properties like optimality or superiority, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)