Sample-Conditional Coverage in Split-Conformal Prediction
Authors: John Duchi
Venue: NeurIPS 2025 poster ()
Keywords: Conformal prediction
predictive inference
coverage
Primary area: theory
TL;DR: Develops split conformal methods that achieve approximately conditional coverage on new predictions

Abstract: We revisit the problem of constructing predictive confidence sets for which we wish to obtain some type of conditional validity. We provide new arguments showing how ``split conformal'' methods achieve near desired coverage levels with high probability, a guarantee conditional on the validation data rather than marginal over it. In addition, we directly consider (approximate) conditional coverage, where, e.g., conditional on a covariate $X$ belonging to some group of interest, we seek a guarantee that a predictive set covers the true outcome $Y$. We show that the natural method of performing quantile regression on a held-out (validation) dataset yields minimax optimal guarantees of coverage in these cases. Complementing these positive results, we also provide experimental evidence highlighting work that remains to develop computationally efficient valid predictive inference methods.

Sample-Conditional Coverage in Conformal Prediction
John Duchi
Departments of Statistics and Electrical Engineering Stanford University
jduchi@stanford.comm
Abstract
We revisit the problem of constructing predictive confidence sets for which we wish obtain some type of conditional validity. We provide new arguments showing how "split conformal" methods achieve near desired coverage levels with high probability, a guarantee conditional on the validation data rather than marginal over it. In addition, we directly consider (approximate) conditional coverage, where, e.g., conditional on covariate X belonging to some group of interest, we seek a guarantee that predictive set covers the true outcome Y. We show that the natural method of performing quantile regression on a held-out (validation) dataset yields minimax optimal guarantees of coverage in these cases. Complementing these positive results, we also provide experimental evidence highlighting work that remains to develop computationally efficient valid predictive inference methods.
1 Introduction and background
In conformal prediction [31, 21, 22, 4], we wish to perform predictive inference on the outcome Y coming from pairs (X,Y) X' x y. The basic approach yields confidence sets C(x) C V, where
given a sample (X,, Yo)_ an estimated confidence Ò provides the (marginal) coverage
PP (Yn+1 (((x+11) 2 a.
(1)
Typically, this, we assume the existence of a scoring function s x y
and define confidence sets of the form Cr(r) = {y s(x, y) I T). For example, when predicting Y E R in regression, given a predictor f X' + the absolute error s(x, y) = [f(x) yl yields the familiar confidence set (+r) = (v E R ly [xx) S TT = [f(x) T, ((x) + of values y near f(x).
The classical sppittconformma) approach [31, 4] uses the sample to find the threshold larger than the observed scores on about - a fraction of the data, then notes that s(X s(Xn11, Yn+1) is likely to be smaller than this threshold. More formally, if (X,, Yi) are exchangeable and we let S; s(X, Yi). then for the order statistics S()) I S(2) < ... I S(n+1), we have
P (S (((1-))+1))) Sa.
because the probability that Sa+1 is in the a-largest fraction of the observed scores is most Then bit bookkeeping [e.g. 27, Lemma 2) shows that the slightly enlarged empirical quantile
= Quant ( Sn))
provides the guarantee
IP (S > 7) a.
Written differently, the confidence set
Ō(x) = (v E y s(x, 9) S
satisfies
P(Y+1 E Č(X P(s Y, < = (S S 2 1 a.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 On X-conditional coverage
Instead of the marginal guarantee (I), we could target conditional coverage, where we say set valued mapping Cn X = y achieves distribution- free conditional (1 - a) coverage if for any P, when (X,, Y.) üdd P and Č₁ is function of (X,, X1) then for P-almost-all x. P(Y++1 E Cx (X X x: 2
(2)
Vovk [30] shows this is impossible. For example, when y = I. the Lebesgue measure Leb(C(z)) is almost always infinite [30, Proposition 4] (see also extensions in [4] and [10, Corollary 7.1]): Corollary 1.1 ([30, 4, 10). Let X be metric space and assume X E X has continuous distribution. If C provides distribution free (1 a) conditional coverage, then for P-almost all E X,
P(Leb(E(x)) = +0o) 2 1
These failures motivate relaxing the conditional coverage condition (2). The simplest approach considers conditoon coverage, where for groups G c X, one targets the guarantee
P(Y+11 Ö(Xx+1)) Xn+1 G) 2 a.
Barber et al. [4, Sec. 4] achieve the coverage (3) by considering worst-case coverage over groups G; Jung et al. [17] provide variations. Gibbs, Cherian, and Candès [12] extend this idea, beginning by observing that conditional coverage P(Y E C(x) X x) = 1 holds if and only if
IE (XX) (1fr E Ō(x)) - (1--a)) =0
(4)
for all bounded Similarly, the one-sided inequality (2) holds if and only if
E [[(()) E E(x)) {[
(1 (X)]](X))
for all nonnegative bounded w. Taking w(xx) f-x G) for groups G X implies the group-
conditional coverage (3); relaxing the condition (4) by considering subclasses of weighting functions W C (X + RR leads to the following definition [12]:
Definition 1.1 (Gibbs et al. [12]). confidence C X y achieves W-weighted ((1 a), c)
coverage if
| (x)) (HYY C(X)) - (1 - a))l S for all w E W.
Gibbs et al.'s 's main two examples take W of the form W {w w(()) (u, ((x)){ for some feature mapping & X - Rd correspond to a reproducing kernel Hilbert space. On example Xn+1 they perform full conformal inference [31], where implicitly for each & R, they solve
hn = argmin heW
(h(,.) S.) + (b((n+1))) -t)
i=1
for the quantile loss (1) = a 14, + (1 a:) [-1] 1 then define the implicit confidence set
Cx(2n+1) = {1 y s(Xn+1,8) S Teatssattaan R (X
(5)
A careful duality calculation [12, Sec. 4] shows how compute O, by solving linear program
Onn + d) variables using (x and ST (Si...., S.). and Gibbs et al. show the set (5) satisfies
E ([ (Ytz (x(())))) w(X.+1) - at)
(m)(w)
for w E W, where (wr) [A))/////r(a [r[(w(X)] to be the w-weighted probability of an event A for w 2 0, this in-
small interpolation error term. Defining (A)
equality strengthens inequality (1) to imply that for all w 2 0, w E W.
P. (Y C(Xn+1)) >
Eint (w).
(6)

---

Computing this prediction set C₂ requires solving sometimes costly optimization. This suggests split-conformal approaches that provide adaptive confidence sets of the form
Cx(xx) = {u E y s(2, v) S (r)(
where ii is chosen based only on the sample (X,, Yo) making the set Cn easy to compute [27, 8). In spite of their case computation, it has been challenging to demonstrate that these sets can achieve coverage; for example, Romano et al. [27] and Cauchois al. [8] apply another level of conformalization to fit constant threshold in and (x) (y E y s(x, v) S Tin()) F.). We show new coverage guarantees for these sets, including new optimality guarantees.
1.2 Sample-conditional coverage
Inequalities (1) and (6) provide guarantees marginal over the entire procedure drawing (X,, Yi) lid P. l 1. While conditional coverage (on x is impossible, is possible to achieve sample- conditional-coverage Letting P. denote the empirical distribution of (X,, Y:) and recalling the weighted probability (6), our results demonstrate that with high probability over the sample Pn.
a(1- a) doo Ep[w(X)] T
(P))
simultaneously for all 2 0 d-dimensional classes of functions W. Because of their reliance on individual examples, full-conformal procedures cannot achieve such conditional guarantees [6].
Sample-conditional results do hold for split-conformal procedures in the special case that W consists of the constant function w 1, which we now review. To state things formally, let S; = (X,, Y.). P. Let a E (0, 1) be a desired confidence level, and define the empirical (1 a)
where (X,, Y,) iid quantile
f = inf (t E R Pa(S < t) a
where P,, denotes the empirical distribution. Given this quantile, define the confidence
(x) = (y E s(x, S S.
Proposition (Vovk [30], Proposition 2). Let the construction above hold. Then for any 0, with probability least 22ng over the sample P..
P(Yn+1 Cx((n)1) PP) 12)1--a7
Jung et al. [17] consider attaining sample- and group-conditional coverage (3), showing that it is
approximately achievable when one assumes quantitative smoothness of the distribution of s(x, Y) given X = Section 2 revisits their approach, providing sharper guarantees without any assumptions on the underlying distribution, yielding approximate conditional analogues of the guarantee (7).
1.3 Sample conditional coverage revisited
We begin by revisiting the sample-conditional coverage guarantees of Proposition 1. In the appendices (see Appendix A), we provide an elementary proof relying only on Hoeffding's concentration inequality, along with two other proof's reposing on uniform convergence to form the point of departure for our more sophisticated coverage guarantees. the interest of brevity, we foeus on new results, beginning with a Bernstein-tyre guarantee that more carefully tracks the desired coverage a: Proposition Let 8 10 and define
(5) = 4log
+
1
2a(1 ax) log <
8 8log
2a(1 a)
3n
+
3n
log
5)
3n
n
log 8
Then with probability at least 1 over the draw of the sample P..
a - (0) < P(Y,+1 E (n((Xn)1) Pw).
additionally the scores S have a density, then with probability at least 28,
1 1- a-a-1 (8) < P(Yn+1 E Cn P.) S a (6).
3

---

We see that the quantile- based confidence set achieves coverage 1 + a When small-which the typical case-this is always sharper than the naive guarantee (7). The central limit theorem shows this is as accurately as we could hope even estimate the coverage level of predictor; moreover, as we discuss following Theorem 3, minimax (rate) optimal. Appendix A, we provide two proofs of Proposition using Appendix A.3 to prove Proposition 2.
2 Approaching conditional coverage
Keeping in mind the ideas in Sections 1.1 and 1.2, we revisit conditional coverage, but we do so conditional on the sample Pn as well. To do this, we consider Jung et al. and Gibbs et al.s approaches [17, 12], considering quantile estimation via the quantile loss [18], which for 0s
(a(1) = [4] (1 (1-
For a random variable Y, the quantile Quant (Y) == inf{t P(Y < 2 1-a} minimizes L(t) == (t (T))) Now (ef. [12, 17]), consider quantile regression of attempting predict $ R from X X. Let Φ X + [ be feature mapping and consider L(0) = (10, o(X)) S)]
Then (for motivation) assuming that S has density conditional on X 2, we see that
VL( = IE [[145 < (0, (x,)())) - (1 a)) (x)]
Now E argmin L(0) be a population minimizer. Then, as Gibbs et al. [12] note, for any E IRd, we have
(u, VL())) = E [(P(S- < (0", o(X)) x)- - (1 a)) (u, ((X))
This connects transparently to confidence set mappings [12, 17]: taking
$ == s(X,) and (z) = {y E y s(x, y) S o(X)))
we have
0 = [(P(Y E C(X) X) - (1 a)) (u, x(X)) for all a E Rd
In turn, Gibbs et al. [12] show this implies the population coverage guarantee
Corollary 2.1 (Gibbs et al. [12], Thm. 2). Assume the distribution of S | X is continuous. Let 6*
minimize L(0) ((), o(X)) )) sXX, Y) Then Cg- provides ((1 a), -e-ihhtee coverage
(Definition 1. 1.1) for the class W == (w(x) = {u, ( of linear functions of o(x).
We extend these guarantees to provide sample-conditional coverage by adapting the arguments we use to prove Proposition 1.
2.1 An estimated confidence set
The population-level confidence set Co- (I) = {v s(x, v) s ((x)) immediately suggests the empirical analogue
On E argmin Ep, (10, x(X)) S)],
(8)
which Jung et al. [17] consider for the special case that the feature mapping ((x) [1 G)] is an indicator vector for groups G C X. This gives the confidence set
(x(x)= = { E s(x, v) < (0, d(xr))
This set indeed provides sample-conditional coverage. To see this, assume for simplicity that d(x) satisfies [|Ø(x))]z by for all æ, and let IB, (u Rd ||ul|y 1} be the balb....
Theorem 1. Assume the boundedness conditions above and that 2 d. Let 0 be the empirical minimizer (8) of the a-quantile loss, let h((x) (0))())) and define the confidence set
Ca(x)= = { E ) 6( v) S Ta())

---

Then there exists a constant e S 2+ a/ d such for 2 0, with probability at least 1 - - over the draw of the sample Pn.
E (u, ((xx+))) (K E (x(( (1 -a)) Pm 2 -bb
(V n +t
simultaneously for all u E I2 satisfying (u, x(x)) with probability 1, then with the same probability,
2 0 all x E X. the scores S, are distinct
(u, o(Xn+1)) (1 E (u(Xn+1) a)) Pm S 3bd
n log +++ (V
d 3n
E
simultaneously for all E 1B2.
We defer the proof of Theorem Section 2.2. We also note in passing that by randomizing, is possible to make the scores distinct without sacrificing coverage [ef. 12].
As corollary Theorem assume that g {G1,.... Ga) partitions X, and define the feature indicator 0gg (x) = (1, Gi), 1fx E Ga})- ) With this choice, we obtain
Corollary 2.2. Let be in Theorem I and ø og be the group feature function. Then simultane- ously for all groups Gj,
(V log +t
P(Y.+1 (n(Xn+1)) Xn+1 E G
P(Xn+1 G2)
with probability al least ent"
We will sharpen this inequality via more sophisticated arguments in the sequel.
It is instructive, however, to compare this guarantee to that the full-conformal approach (5) provides. The construction (5) appears to obtain better coverage than the more basic approaches here [12, Fig. 3], but it can be more computationally challenging [12, Fig. 6]. Gibbs et al. [12] show that randomized version of their procedure (5) achieves
P(Y++1 (Xn41) Xx+1 E G - for all G G.
This can be substantially sharper than the guarantee Corollary 2.2 provides, as our sample-conditional coverage guarantees are not quite so exact; we revisit these points in experiments.
2.2 Proof of Theorem
By convexity, 0 E Σi= (0,((0((())) - (x)), which is equivalent the statement that for some scalars (really, dual variables) Ji satisfying
(0, o(x))) S,
a
- (1 a.)
if (0, <(x.)) < S;
(9)
(1(11a),,a
(0, ((.)) = S,
we have = Ei= (x)( We use the empirical process notation = = hand. Recall that for convex function f. the directional derivative f'(:; u) limægo f(x+tu)
+ S(X,) for short-
exists and satisfies fl(2; u) sup( (g. u) g E 0f()). Thus, by definition of optimality,
P. (0, ((X)) S;u) 0
for all Let be such that (u, ((=)) 2 0 for all X. Then
(10, ((z)) s: u) (d(z), u) [ad d(x)) 2 $} - (1- (1-0)1((0.0(z)) sH By the first-order optimality condition we obtain
0 < u, (u,aPro(X)1 ((x)) 2 - (1 - -1-)
< <s})
((,,PPb(X)) Pa Pn)(X)) (0,0()) < <s))
5

---

dog Suppose that we demonstrate that
Σ (x.)){( > (0, ((.)()))))) ( (0,6(x)) Se
uniformly over 0 E Rdd Then we would obtain for all u E B2 with (u, v(x)) 2 ffo x E X,
S (u, (x (a - iss> (xx())))) S Er (())(()) (a 1(s> (0, (0,0())))) tc.
That is, y & ((x) if and only if sa, v) > (0, 0()))
Ep (1n (()) (i{y Ō(p) a)]
o))s se.
(10)
With appropriate e, this will give the first claim of the theorem.
We abstract a bit and let C {x + R] be a collection of functions, and consider the process
(h) n Σ
x((x))(ss>x(x h(X)))
When H. is a VC-class, for each coordinate j. functions of the form Φ (z)]{{s > h(z)3 are VC- subgraph [29, Lemma 18]. The following technical lemma, whose proof we provide in Ap- pendix C.I, shows that Z, concentrates.
Lemma 2.1. Let B2 = {u: ||ull2 = 1} and H have VC-dimension Then
log &
TE k
1
1/2
E
sup kEH.uEBg
(u. (n) ((2)(()))
22V
E
1+(x))1
Trivially, Elsupeez, (u,
< A (ll XI 1/2 addressing (x))((X) terms.
We can extend the lemma by homogeneity to capture arbitrary vectors. Note that if we change single example S.), then (u, Zn (h)) changes by at most n supa (u, d(x)) S n ||lll supa [|0(z)]l2 By homogeneity, for any scalar t there exists u E æ such that (u, Z,(h) EIZ.. Z ||u]|2 L if and only if there exists E sd-1 such that (u, Zn (h) EL (h)]) 2 L. So if bs supsex [0(x)]]2 we obtain by bounded differences (Lemma A. and homogeneity that
(u, Zn (h)
- E (,, (h)))
(u, Zh) - 1EZZ((01)
)
S mn
P sup NEH
2 bal +
sup
|w/12
HES4
1.NEH
Summarizing, we have proved the following proposition. Proposition 3. Let H have VC-dimension k. Thrn 0.
(u, (h) [[)n(h)] 2b
h kog 2 E
P
sup uF0,NE
bab se-
|/u122
By taking H = (h: h(x) thus shown that inequality (10) holds with
(0, ((x)) ((x)))oER< hoRRd, which has VC-dimension d, in Proposition 3, we have
bax Vn
c= 2b
+ +bat +
n
with probability at least en which is the first claim of Theorem 1.
We turn to the second claim of Theorem 1, which applies when are distinct with probability 1.
Recall the definition (9) of the subgradient terms 9i and define the sets I_ {il (0, o(X.)) > St}.
I_ = (il (0, ((X))) < S.). and Io = {i (0, (xx))) = S.). Then
a
Σ ((x)) (1(5) 5, (0,((x))) - aa)
Σ ((X:)9 Σ 5(Xi))
Σ
x(Xi) (a gi) Σ - - o(Xi))
IEI
iEIo
ieIn
ieIn

---

where we used that 1 9i0(X;) 0 by construction. Now. we leverage our assumption that S are distinct with probability We see immediately that card(In) S d. because with distinct values S we may satisfy (at most) d linear equalities, and so
n Σ
(x,) (1(5: (0, ((x(
a)({ card
d be -
bo.
n
n
Because Proposition 3 controls the fluctuations of the process 0 - ((x)1{s>> (d(x), 8)}, obtain that with probability at least ----t -nt?
E ((x)) s> (x,(x))]]] -
Σ ox,, (IsS,> > 00 (0,())))) - -a)
d
bya
+ +bb
log +
+ bot
n
d
vni
d
n d log
b + 3bo
+ bot.
Sharper and rate-optimal approximate conditional bounds
The bounds Theorem provides do not reflect the sharpest coverage possible. By leveraging empirical process variants of the Bernstein concentration inequalities we use to prove Proposition 2, we can achieve sharper bounds weighted coverage that adapt to the linear functionals (u, <(x:)) As consequence our results, in terms of achieving approximate conditional coverage (i.e., weighted coverage in Definition 1.1), the empirical estimator (8) is minimax rate optimal; discuss this after Theorem 3.
w(x)
To state results, assume that B Rd is arbitrary but bounded set of vectors, and define
bo(u) (u) == sup Ku, ((x)) and by == sup bas (u).
=EX
welf
We can then extend Proposition to weighted conditional coverage (Def. 1.1), conditional on the sample. We defer their proofs. presenting the building blocks common to both in Appendix B.I, then specializing in Appendicess B.2 and B.3, respectively.
Theorem 2. Let Kn, + log2 Then there exists numerical constant c < oo such that for all t 2 O, with probubility at least 2K e -ologn--
E (u, o(Xn+1)) (1(Y=144 ((x++)) -a) P
Sc Voo(u)a Blu, (x))]
dloog +t dlog +t bb n
n
simultaneously for all IB such that (u, o(x)) for all æ. If additionally the scores S; distinct with probability 1, then with the same probability,
I (u, ((x++))) (1(Yn=1 & C(X aa) Pr
2 - (Vooebre EiKu, e(X))ly dlogn +t
dlogn + + bo
n
simultaneously for all E B such that (u, d(x)) 2 for all x.
Simplifying the statement and ignoring higher-order terms, we can obtain a guarantee for weighted coverage (6): for the class W =[((x) = (u, ((x))) meRe, with probability 1 -e-t
d log n -
Pu E Cnt1l P.)) 2 - a -
B[w(X)]
n
simultaneously for w 2 0 with the normalization that w(x) (u, ((x)) for a satisfying bo(u) = 1.
Applying the theorem to group indicators, meaning that we have a collection of groups G C 2 and the feature mapping o(x) (1fz GG) we have the following sharpening of Theorem 1.
7

---

Corollary 3.1. Assume that ((z) = (1{x G))egg and let d = cgr Then with probability at least 1 - -3log ne"
P(Y++1 & O(X++1) Xn+1 E G,P,) S atc
sate
[V
(V
a
d llogn. +1
dog n +
p(X E EG) n
P(Xn+1 E G) .1
simultaneously for all G E G.
The result follows immediately upon considering the standard basis vectors v = 6j.
When the scores S = s(X, Y) are distinct with probability 1, we achieve two sided bounds extending Theorem 2, as in Proposition The next theorem provides an exemplar result.
Theorem Let the conditions of Theorem hold, except assume that S; are distinct with probability 1, and that the mapping Φ(x) includes a constant bias term Φ1 (x) = 1. Then there exists a numerical
constant e < oo such that for all 2 O, with probability at least - 2K - e- log n-t simultaneously for all E lB
E (u, o(x)) (1(Yut1 & ((Xatz)) - a) |Pa c
bs ba(
dlog n +
+ bs
d dloog n +
The conclusion is weaker than that of Theorem 2, it replaces
(b [(X) with (u).
3.1 Minimax optimality
The convergence guarantees in Theorems and are sharp to within logarithmic factors, and capture the correct dependence on and the weight functions W. Indeed, Areces et al. [1] develop a set of lower bounds that apply to VC-classes of functions W, where they show the following. Assume that the estimated confidence set On takes the form C₂ (xx = {y s(x, v) S M(x) or (x) = (y ((x)= S s(x, v) < b(x)) for some estimated functions h, ā, or b. Corollary 3.2 (Areces et al. [1], Thm. 1). Let W be any class of functions mapping X' to {+1} with VC-dimension d, Cn take either of the forms above. Then there exists sampling distribution P for which S X has continuous bounded density and such that with constant probability over the draw of Pr.
da(1 - a)
E
[((x++)11 (Yu & (x(xx)1)) w(X Pa 2 2cp
where c is a universal constant.
To compare this with Theorems 2 and 3, let (GI...., Gj C X, be partition of X into d groups, and define the group feature mapping Φ(x) [1fx G, Then the class of linear functionals W [w w(xx) (u, Φ(x)) huRR has VC-dimension d, as does its restriction Wi {w w(x) = (u, ((x)) we (+))a, where w E W1 satisfies w(x) E {=1}. Theorems and 3, conversely, demonstrate that for B1 = {u ||u||| I 13, we have
a(1 o:) E (X (I (X. - a) P.. S sey
log n +
n
with probability at least - e simultaneously for all w of the form w(x) (u, o(x)) for some B1, as long as a 1 (where we use 1 a 2 and wrap constants together for cleaner statement). In contrast to existing results [17, 1]. these new guarantees are evidently optimal.
4 Experimental Results
Our main purpose has been to investigate conditional quantile estimation procedures, providing theo- retical bounds for their performance; there is already practical experience with these methods [12]. We thus provide an exploratory experiment on the CIFAR-100 dataset [20], a 100-class image classi- fication dataset consisting of 60,000 training examples and 10,000 example test set, highlighting

---

Coverage
Figure 1. Coverage of full conformal, split conformal, and static split conformal meth- ods random 20% "slices" of CIFAR-100 data.
0.90
Type
Split
Static
0.84
2
marginal
Data slice
that these conditional approaches can provide better coverage than using static threshold, i.e., (x))) (y 3' sxr, 7.). In Appendix D provide few further simulations to investigate heuristic corrections to the nominal level a that may yield better realized coverage.
We use the output features of 50 layer ResNet, pre-trained ImageNet [13, 14], d 2048- dimensional input to 100 class logistic regression. We repeat the following experiment times:
Uniformly randomly split the training examples into a validation set of size 10,000 and model training set of size 50,000, on which we fit a linear classifier s: IRd + Rt, where 8y (x) = (3y, x) the assigned to class y, using multinomial logistic regression.
Draw a random matrix W [dddo, where dg = 10 and Way lid N(O, 1), and use the validation data with score function 5(x, 3) sx( and the lower-dimensional mapping d(x) W WTa x to predict quantiles via i(()) = (0, ((x)).
3. Compare the coverage of the full-conformal method, standard split conformal with static threshold, meaning confidence sets of the form C(x) {y E [k] s(x,)) v) I 7), and split conformal with the threshold function (x()) fit on the validation data. To perform the comparison, we draw subsamples from the test Ziest {(x; )i)) by defining groups G of the form
G5 {((,,)) Zisst (w,, 2) Quant (L(w,, xz) yest and G = {(x,)) E Zuest (w) 2) Quant 2(1 (wy, 2x)) (im))
for each row w. of the random dimension reduction matrix W from step 2.
Figure displays the results of this experiment. In the figure, we notice three main results: first, the static thresholded sets (zz) {y s(x, y) < f} have substantially more variability in coverage the random slices of the dataset. Second, the split conformal method and full conformal methods have similar coverage on each of the slices, with some slices exhibiting more variability of the full conformal methodology and some with the split conformal methodology, but all around the nominal (desired) 90% coverage level. Finally, the split conformal methods slightly undercover marginally, while the full conformal method slightly overcovers marginally.
5 Conclusion and discussion
The results in our experiments, though they are relatively small scale, appear to be consistent with other experiments on regression that we present Appendix D, where we also investigate the appropriate choice of the level to obtain a desired coverage level coverage. In brief: split conformal methods with confidence sets using adaptive thresholds of the form C(x) {y s(x, v) < h(x)) can indeed provide stronger coverage than non-adaptive thresholds. Moreover, they are much faster to compute with than full conformal methods- -n the experiment in Figure the split conformal

---

method was roughly 8000 faster than the full conformal method. Additionally, they enjoy strong sample-conditional stability as well as minimax optimality.
In spite of this, when the adaptive threshold M(z) comes from a class of functions that is high- dimensional relative to the size of the data available for calibration, these methods can undercover, as they exhibit downward bias in their coverage. This bias is easy to correct for a static threshold C(x) = {y s(z, y) S î by simply using a slightly larger quantile, however, it is unclear how to address it in adaptive scenarios. This makes obtaining data-adaptive way to compute coverage bias an open and important research question: can we avoid the / error in each of the conditional coverage guarantees? As Gibbs et al. [12, Thm. 2] show, "full conformal" methodshave errors scaling as O(d/n) in these cases, while the methods in the current paper have a downward coverage bias that appears to scale with vd/n. This is, of course, worse, and delineating the extent to which this bias matters remains open.
Certainly, the minimax lower bounds that Areces et al. [1] demonstrate show that it is impossible to achieve anything improving on /d/n error for two-sided guarantees, but if we only wish to demonstrate weighted coverage lower bounds P... (Y,+1 CX P.,) 2 1-a-0(1) (11)do00 dlog(1/88) then it may be possible to achieve one-sided guarantees without such errror, One approach, which Cauchois et al. [8] adopt, is to split the validation sample "re-conformalize" the confidence sets, so that the only concentration one needs is on a single threshold being learned. This would mean fitting a confidence set C(x) = {v szz y) S ]xx) on one validation sample, and on the second, modifying single threshold F to fit Ō(x) = {v s(x, y) < M(x) + 7): this, however, would not provide any approximate conditional guarantees. It seems plausible that one might instead be able to use leave-one-out sampling to estimate this downward bias [11, 3]. Identifying such an offline correction without relying on asymptotic error calculations, as our heuristic development in Appendix D does, could make these procedures substantially more practical, by both enjoying the test-time speed of split conformal methods and the coverage accuracy of full-conformal procedures.
A second set of open questions relates to the experiments. While have been careful to identify them as "exploratory" (because the main focus of this paper is theoretical), they do not directly address the sample-conditional aspects (i.e., coverage given P,,) of the guarantees much as the "od-conditional" guarantees (or, perhaps, group-wise guarantees), as in Theorem 3 and Corollary 3.1. would be (to the author at least) quite interesting to understand whether sample-conditional coverage is practically relevant, especially relative to the marginal coverage guarantees full-co full-conformal inference provides. Bian and Barber [6] provide counterexample showing that there exist cases where full-conformal methods are quite unstable. But understanding the extent to which this is practically meaningful would require experimental work that is beyond the current focus of this paper.
Acknowledgments
This research was supported in part by the National Science Foundation under grant IIS 2006777 and the Office of Naval Research under grant ONR N00014-22-1-266 12669.. I also wish to thank John Cherian for many stimulating conversations about this paper, the students in the Statistics 315a at Stanford in the winter of 2025, whose questions inspired this work, and several anonymous reviewers, whose investigation of the paper improved its presentation, helped to identify open questions, and (hopefully) led clearer paper.
References
[1] F. Areces, C. Cheng, J. Duchi, and R. Kuditipudi. Two fundamental limits for uncertainty quantification in predictive inference. In Proceedings of the Thirty Seventh Annual Conference on Computational Learning Theory, 2024.
[2] Y. Bai, S. Mei, H. Wang, and C. Xiong. Understanding the under-coverage bias in uncertainty [cs. 2021.
estimation. orXiv:2106.053
[3] R. F. Barber, E. Candès, A. Ramdas, and R. Tibshirani. Predictive inference with the Jackknife+. Annals of Statistics, 49(1):486-500 2021.
[4] R. F. Barber, F. J. Candès, A. Ramdas, and R. J. Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference, 10(2):455-48) 2021.
10

---

[5] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics, 33(4):1497-1537 2005.
[6] M. Bian and R. F. Barber. Training-conditoone coverage for distribution-free predictive infer- ence. arXiv:2205.0364) [math.T], 2022.
[7] O. Bousquet. Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms. PhD thesis, L''Eclle Polytechnique, 2002.
[8] M. Cauchois, Gupta, and Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22(81):
1 1-42, 2021.
[9] Duchi and Ruan. Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval. Information and Inference, iay015, 2018.
[10] J. C. Duchi, S. Gupta, K. Jiang, and P. Sur. Predictive inference in multi-environment scenarios. Statistical Science, to appear, 2024.
[11] B. Efron and C. Stein. The jackknife estimate of variance. Annals of Statisties, 9(3):586-59) 1981.
[12] I. Gibbs, J. Cherian, and E. Candès. Conformal prediction with conditional guarantees. Journal of the Royal Statistical Society, Series B, 8704):100- 2025.
[13] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Patlern Recognition, pages 770-778, 2016.
[14] K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings deep residual networks. In European Conference Computer Vision, pages 630-645, 2016.
[15] J. Hiriart-Urruty and C. Lemaréchal. Convex Anulysis and Minimization Algorithms I. Springer, New York, 1993.
[16] Howard, Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[17] C. Jung, G. Noarov, R. Ramalingam, and A. Roth. Batch multivalid conformal prediction. In Proceedings of the Eleventh International Conference on Learning Representations, 2023.
[18] R. Koenker and Bassett Jr. Regression quantiles. Econometrica: Journal of the Econometric Society, 46(11:33-550 3:3-50, 1978.
[19] V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. Annals of Statistics, 34(6):2593-22) 2656, 2006.
[20] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[21] J. Lei and L. Wasserman. Distribution prediction bands for non parametric regression. Journal of the Royal Statistical Society, Series B, 76(1):71-96, 2014.
[22] J. Lei, M. Gelll, A. Rinaldo, R. J. Tibshirani, and Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 1134523):1094-1111, 2018.
[23] Massart. The tight constant in the Dvoretaky-Kiefe--ooloo inequality. Annals of Probability, 1269):126 1990.
[24] C. McDiarmid. On the method of bounded differences. Surveys in Combinatorics, pages 148-188, 1989.
[25] Mendelson. Learning without concentration. In Proceedings of the Twenty Seventh Annual Conference Compulational Learning Theory, 2014.
[26] I. Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. Annals of Probability, 22(4):1679-1706 1994.
[27] Y. Romano, Patterson, and E. J. Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems 32, 2019.
[28] S. van de Geer. Empirical Processes in M-Estimation. Cambridge University Press, 2000.

---

[29] A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applications Statistics. Springer, New York, 1996.
[30] V. Vovk. Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pages 475-490, 2012.
[31] V. Vovk, A. Grammenman, and G. Shafer. Algorithmic Learning in Random World. Springer, 2005.
[32] M. J. Wainwright. High-Dimensional Statistics; A Non-Asymplotic Viewpoint Cambridge University Press, 2019.
12

---

A Sample conditional coverage revisited: proofs
As mentioned in Section 1.3, Proposition I provides a natural point of departure for developing more sophisticated coverage guarantees. We thus provide this elementary proof, then demonstrate the result using uniform convergence techniques. These uniform convergence guarantees- which form the basis for providing guarantees for approximate weighted coverage (Definition 1.1) also provide two-sided bound on sample-conditions coverage:
Corollary A.1. Assume the scores S; s(Xi, Yi) are distinct with probability 1. Then for any y with probability least 1 -2 2 over the sample Pn.
1 a-a-1 7 S (n(xn+1)) Px) S
+ %
11
A.1 An elementary proof of Proposition
For the scalar random variable S, define the B-quantile
(3) inf {t E R PPS (($ 8)
(11)
Because the CDF right continuous, we have P(S S (²)) 2 3, and PPSSPP (3)) = P
4º (8)) < 1 - B. For 7 > 0 and any E R. the inequality
PSS++ > >) > a 7. i.c. P(S.+1 1) a a-
implies that r < 9* (1 - a - 7)-
Consider the event that Fn < 9" (1
a 7). For this to occur, it must be the case that
iss, < 9- 7)} 2 a.
(12)
But this event is unlikely: define the Bernoulli indicator variables B; = 1(S < <- a - -))
Then [[B,] < - a and Hoeffding's 's inequality implies that B, = Ei=1 B, satisfies
(S -)) 1 B, 21 a-a)
a- x))
IP (B, E[l,)] 27) S exp( 22m2))
That is,
Pf < a-11-a-11111-
a -
))) - exp (-2m²?)
for any y 0, and we must have
P (S > Fm Pa) a with probability least 1 2nn?
Rearranging and recalling that Yut1 & Cn(Xn+1)) if and only if s(xn+1, Mnt1) > Fno i.e., Sn+1 Tx gives the result.
A.2 proof of Proposition using uniform convergence
Our alternative approach to the proof of Proposition uses the bounded differences inequality and uniform concentration guarantee. First, for any estimated threshold F... we have the trivial inequality
IPSS Fm Pw) P(S > fn P.) - PA Fr.) + P. > Fm)
< sup P(S > r) - P. + > 7.).
TER
Then because choose F.. that (S < F.)
a, obtain
P(S.+1 > 7n Pa) < a + sup TER
P(S > - Ps r)
(13a)
the values S, are distinct, then (S < +.) $ 1 yields
a
+ 1 n
and so a completely similar calculation
P(SS+1 > Pn P 2 a
sup TER
P(S 7) P.(S > +)-.
(13b)
7
13

---

In either case, if we can control the deviation P(S Pa > r} uniformly across 7, we will have evidently proved the desired result.
We consider two arguments, the first yielding sharper constants, while the second generalizes to weighted coverage. For the first, we apply the Siinek---Keefe-Wofooooo inequality [23]:
P(S (S r) 2) I 2e- 22nt
sup FEB
for all 1 2 0. Combining the equations (13), we thus obtain that
PPS 7y P.) S a + with probability least 2e 2n7?
the scores are distinct, the corresponding lower bound is immediate, giving Corollary A.1.
The final alternative argument to control the uniform deviations in the bounds (13) underpins our more sophisticated guarantees in the sequel, relying on uniform concentration guarantees and the Vapnik- Chervonenkis (VC) dimension. First, recall the classical bounded differences inequality [24, 32], where we say function
X - satisfies cy-bounded differences if
(f I.a 24, 11+1 f(aî-' -1 224,27+)) S c for all xं 2l41 Ti, x E X.
Lemma A.1 (Bounded differences). Let X,...,, X, be independent random variables and satisfy ey-bounded differences. Then for all t 2 0,
21 EE
max (P(S(XT) -ELS(XTM 2 P(((((
B[((X)) S -1)) S exp
We then observe that f(P.) == suPrER PPS > T) PS > r) trivially satisfies bounded
differences. Indeed, let P differ from Pn in single observation. Then defining |P PP Pall sup, PPS (S > 7) for shorthand, obtain
P - Po - IP ll Pr, P ll S
by the triangle inequality and that only one example may change. Lemma A. I then implies
P (IIP Pxlloc 2 | P- - Pollool + S 2nt
fort 2 0, so that need only control B||| Pa loc.). For this, perform a standard symmetriza- s,
tion argument [e.g. 29, Ch. 2.3]: let P 1 >リ , where e; iid Uni{#1} are i.i.d. Rademacher variables and 1s; denotes point mass on S.. By introducing independent copies of S; and applying Jensen's inequality [29, Lemma 2.3.1], we have the bound
E P| - Plaad < 2E
2E
sup TER
a ( > T}
Because the class of functions + 1(s 7) has VC-dimension most 1, Dudley's entropy integral (see, e.g. [29, Corollary 2.2.8 and Thm. 2.6.7] or [32, Eq. (5.5. shows that
E
Vn
for a numerical constant We then obtain that for any 7 2 0.
P(S.11 > Fm Pa) aat Vn + r w.p. 22n?
by the inequalities (13), where c is numerical constant.
A.3 Proof of Proposition 2
Recall the quantile mapping g" from the definition (11) and that for fixed E [0, a), the event Fn < q1(1 & - 7) can occur only if (S < g0(1 - -)) 2 1 - a. Then defining B; =
(S < q² (1 - - and recalling inequality (12), obtain
Pff, <1 - >) s P(B, 2 1 - a) P(B,. - E[B,] > 1 - E(Ba)).
14

---

Define p(7) - E[B.] = P(S < - 7)) < - so that t t()) 1 p(7) >
Then (a) = ((7)(1-p(1)) (a+ t) a - -). and Bernstein's inequality implies
nt2
P(B, - BBB 2 t) - exp
2(1 (
- 1)(a + 1) (11
nt²
nt²
= exp
S eexp
2(1 a.a + (3 - 4a - +2
2(1 - a) + 3
8
Notably, 1 1
at? 2(1-o)a+ f
is increasing in t, that
ny?
Pf < (1 -1 -1)) - cxp 2(1 a) + 53
the scores S have a density, (SS S (3)) 3 for any E (0, 1). Then we may also consider the event that F, > 4* (1 - a + 7). For this to occur, require
(S (1 (1-a+ 7)) S 1 a, }) have E[B:]
and defining B; = 1(8; < (1
7 and so
m²²
P(BB, 1 - = BBB.. - B. v -7) S exp
2(1 7)(a +
ny?
exp
2(1 ( a)a + 33
for E a). Combining the two cases, for y 2 0 we have
ny?
max (P (fn < g" - a P() > q² (1 + a +))) exp
2a a) + 8
37
Solving guarantee the right hand side most yields
4 1og A
4 3n
2 ))
2a(1 a)
Tn
log 5)
log
3n
n
Applying a union bound implies Proposition 2.
B Proof of Theorems and
We split the proof into three sections, first giving the shared building blocks, then specializing.
B.1 Proof of Theorems 2 and 3: building blocks
Our proof leverages combination of Talagrand's 's concentration inequalities for empirical processes, a VC-dimension calculation, and localized Rademacher complexities [5, 19]. We begin with the form of Talagrand's 's empirical process inequality with constants due to Bousquet [7].
Lemma B.1 (Talagrand's 's empirical process inequality). Let F be countable class of functions with P = 0 and || < b for f E F. Let = sup Pul and o² o²(F) = sup P. Define 2 = 2² + 2b Z Then for 2 O,
P
7
E + 22 +1² nn
Because will consider functions of the form f(x, (u, (xx)) (10, (xx)) s), we also require some control over the complexity of such rank-one-like products.
Lemma B.2. Let H and be classes of functions with VC-dimensions di and d2, respectively. Then the classes of functions
F F= = 9(x)1 > 0}} and F+ = {S1 = (xx)1(1(2)) 0} - -c(x))
where is constant have VC-dimension ((1)(d; + d2).
15

---

Proof For a set of points Fi..... 2n. let S(z M.) {1fh(z,) 0] be the set of "sign" vectors that h realizes. By definition of the VC-dimension and the Sauer-Shelah lemma, this has cardinality at most Σ (7) - d1 ( Similarly, the set of signs
S(r F) = (sign (4)) (((())) 12
has cardinality at most
Σ1= (1)
ΣS ==
(7)
S
BE
If is large enough that
d1
d2
me dj
nE
2"
d2
then certainly F cannot shatter points; this occurs once 2 c. (di + d2) for some numerical constant c. For the second class the argument similar.
For the next lemma, our main technical building block for convergence, we consider the class of functions F indexed by B and h E H. where H is a class with VC-dimension at most d, with
fxx 8) (2,, 8) (u, (x))) Mx))-
(14)
Each of these functions evidently satisfies (1, 8)1 S bø. The variance proxy
2 (u, h) v² (fu,)) = Pl PSu,
u\) x()))
(15)
and empirical variant o (u, h1) Pala, - 1 Σ (X₂), 115 h(X.))
will allow to bound deviations of Paf from Pf relative u² (f). For later use, we recall the empirical Rademacher complexity of function class F,
RR
E
sup JEF 1=1
Exf(X) |
where iid Uni( [1} are random signs. In some cases, we will require localized Rademacher complexities [5, 19] around a class F, = (f pf S r2). which contains functions of small variance, allowing us to "relativize" bounds. Bartlett et al. [5, Proof of Corollary 3.7] demonstrate the following.
Lemma B.3. Let F be star-convex collection of functions, meaning that F implies Xf F for x E [0, 1}. and assume that sup, [f(z) I and F has VC-dimension d. Then
E [R (F.))
by + crr log
cr
d
ba
if 2 > 62 log
n
(16)
d'
where c < 0o is a numerical constant.
We will combine the VC-bound in Lemma B.2, the version of Talagrand's empirical process inequality in Lemma B. and localization argument on Rademacher complexities via inequality (16) to prove the following lemma in Appendix C.2.
Lemma B.4. Let be the class of functions (14). Let K,, = 1 + log, n. Then all 2 0, with probability least Kre over the draw of the sample P..
(Pn - PPSSs vny 1
ddogg +t
dloon+t +t
+ by
n
n
simuitaneously for all f F, where e < oo is numerical constant. In addition, with the same probability,
dlog n + + b
log v +
IPa - P)(, s /Puu,
simultaneously for all e B.
16

---

Next we present version of a result appearing as [32, Theorem 14.12] (the result there assumes functions are mean-zero, but an inspection of the proof shows this unnecessary); see also the results of [25] and [9, Proof of Proposition 1.. These show that second moments satisfy one-sided concentration bounds with high probability as soon as we have the fourth moment condition
(X, S) S
for all E F.
(17)
For the setting we consider, where F consists of product functions (14), inequality (17) immediately holds with b = bg. though tighter constants may be possible.
Lemma B.5. There exist numerical constants < с and C < oo such that the following holds. Let inequality (17) hold and for F, = (f Pf z r²), let r satisfy (Fr) oa probability least e-ons2/1
Tg. Then with
Paf 2 simultaneously for all f s.t. v(f) 2r.
Inequality (16) shows the conclusions of of Lemma B.5 hold if the radius satisfies
r²
d
log
p²
log
by
n d
We then obtain the following consequence:
Lemma B.6. Let 22 2 b2 d log a- Then with probability least e." - 268
n
1 (()))(()))1{{>>>>//))))))))))))> h(X)) 2
(())
A(X)}
simultaneously over E IB and h such that P(u, (()) h(X) 2
Now, let h (0, o(-)). where solves the problem (8). Then simultaneously for all B, with probability at least 1 Kne
[Pr o m(x) s w dlogn +l
dloog l + b
(18)
n
n
by Lemma B.4. Moreover, for 2 > b log J. either vhh, u) S rro
8 2h, u) s 2P. (0(),, 2 { n(x)}
by Lemma B.6 (with the appropriate probability 1 - e -or 112).
B.2 Proof of Theorem 2: nonnegative weights
We now specialize our development to the particular cases that (u, o(x)) 2 for all x E X. First, leverage the particular structure of the quantile loss to give non-probabilistic bound on the empirical weights.
Lemma B.7. Let u be such that (u, ((x)) 2 0 for all x E X. Then
Pa (x() u) iss s> Tu(x)) s (())))
If additionally S; are all distinct, then
Pa (a(o(X), 1 S m(x)} 2 aPr(o(X). bo(4) d n
Proof
The directional derivative (t( = limoso Eo(1+0))--10 = 1lt 2 0} (1- - at). Then
(r(((X). u))( > T((x)] = (,()(X), u) (1-a- - { Pr x(X))a (a()(X), u)
(-ca(((x- - 5;1)) -s:1)))ss1)))))
(x.,(u,(X)).
17

---

Letting L, (h) = (hla(h(X) S), we now use that directional derivatives are positively homo-
geneous [15] and that by assumption h minimizes (h()( S) over functions of the form
h(x)= = =00, (()) to obtain
(b()),, u) (-e(((x) ( 5: (x( S; (x(X)) u)) (()())));:
But of course, as h minimizes L,, we have L' (h()):) 2 for all u, and so
(x()) w) h(x) S aP (u. o(X))
If S, are all distinct, then considering the left directional derivative, we also have
Pr (x()), u) 1 { m(x) (())),((()))
I | [Xx)) =. then card (To) 2 d, and
0 2 (o) u) (1{s> [[>>)(x)}- 1{ s {(x))) - a) u - ) (s) d
Rearranging and performing bit of algebra, we obtain the second claim of the lemma.
From the lemma, we see that
P(u,o(X) x(x)) (1{8 ( [()) -a)
= = - -P-PPn)(u (u, 2b (X)) (1s8> <<(mx(xx)))) -a) + Pu (X)) (1f5> [xx) -a)
$ (P-P,) o (x))){(s>> i(x)) a(P - o(X))
(19)
by Lemma B.7. Additionally, the lemma implies that
((x) < (u)a (o(X), u). (x()) { >> h(x)) s by (o w) u/)
We use this to control the first term in the expansion (19) by combining these bounds with inequal- 3 d log 2. In the latter, we have (h, u) S cbs (u) (6(X), u). We have therefore shown that for any x2 2 log a. with probability at least 1 - KnE
ity (18) and considering that v(h, u) S or v(h, u) > where r (1))b²
for all u E with (u, o(x)) 2 0.
[Pe, P) o()u,(X))1ss>>>>> x{x)}
(20)
so (Voostwaarratuu ((X)) + bor)
dlog n +t d doo n + by
n
Applying Lemma B.4 the quantity Pa Pa o(X)) shows that simultaneously for all B,
IPa, - (),, x(x)) c (balw) (())
d d n +t
b dloog n + n
π
with probability least 1 - Kt Substituting this into the bounds (19) and (20), and ignoring
lower-order terms (because - 1), we obtain the guarantee that for all 2 O and 22 2 log 2. then with probability at least 1 -2
-nn? for all u such that P(u, o(X)) 2 bo dllogntt
(u, ((X)) (1{5> [(x)] - a) PP sc (V((abb(w))Piu ((x)) + bor) /
/dlogn +t
d +
+ b,
71
n
and for all such that P(u, o(X)) < 60 dlugn-t
"
E B( (())) (1f5> T(x)] } -a) PP S cba
dllg n +t
d d +
rv
18

---

Combining the inequalities and replacing r with dlogntt gives the first claim of Theorem 2. For the second claim, when the scores S; are distinct, note simply that may replace inequality (19) with
p(u,o(X) ((x) [()]= -a)
= - - (u, o(x)) (1s5> [x))m(x}}}} -a)
-a) + Pa (()) xx5)>xxx--- -a) a))
2 (P- - (u) of x))1 (s>> i(x) aa( Pa)(u, x(X)) by (m)
The remainder of the argument is, mutatis mutandis, identical to the proof of the first claim of the theorem.
B.3 Proof of Theorem 3: distinct scores
Because of the distinctness S; and that we assume Φ1(x) = offset), the optimality conditions for the quantile loss imply that
(that is, we include the constant
d
Σ Css,
[(Xa]]
d n
So if (u) = suprex (eu, ((x)) then
Ps (x(6 > m(x)) s Bg(u) (a d n #)
Applying inequality (18), we find that with probability at least 1 - Kne- - car? 162.
(P, (X)) m(x)
>>>>)>>><<>>>>>>> sc [1scovatt)
dlogn+ bg
dlog +
n
n
The deviations aPP. (u, x(X)} are of smaller order than this by Lemma B.4.
C Technical proofs
C.1 Proof of Lemma
When B2 is the b2-ball,
(u, (h) - (h))) NE
sup
sup (Z,, E[Z,, (h)]l2
LCHH
Performing a typical symmetrization argument, we let P. = e, be the symmetrized
empirical measure, where &; lid Uni are i.i.d. Rademacher variables, and define the symmetrized process (h) Σ cxo(Xx)1 h(X,)). Then for the (random) set of vectors V.
((1(S) > h(x,)) ...., ISS > ((x))))mex C {0,1) 13"
E
sup | 1, (h) (1))ll NEH
< 2E
sup
7 (h)
< 2E
max VEV.
Ea X, X.)
NEH
Now, we recognize that because the vectors & lie Hilbert space, we enjoy certain dimension free concentration guarantees. In particular, we have for any fixed v E {0. 1) that
a
P
Σ
exd(X.))o
2 21 XT
S 2exp
2Φ2
19

---

where & == Ei= | by Pinelis [26, Theorem 3.5] (see also [16, Corollary 10]). In particular,
using that for U nonnegative random variable [E[U]
Su PPU 2 u)du, we obtain
E
max VEV,
Σ (x
|X
I
max BEVn
Σ
2t xi
2
00 /
1²
I to + carrd(v,)
exp
dt.
2Φb
Recognizing the Gaussian tail bound that
20 dt 2TT2
2/ dz S 2TT min
1 o
1
exp
c²
a/a V2
122
20
by Mills' ratio, we see that for any to 2 O.
$ exp
max BEV
Σ (x))
x
I to + 2card(Vn)
to
2Φ
Finally, recognize that Vn has cardinality most ( ) by the Sauer-Shelah lemma because H. has VC-dimension Consequently, we may take to log card(V,, $2 to obtain the bound
max VVV.
Σ
(X))) x < v log car + /2 log card S 2
k log
ne
k
2
Take expectations over X
C.2 Proof of Lemma B.4
For 2 define the localized class
F, = { E | ((, (()))
Note that F, always includes the O function and star-convex, because if f E Fr, then Af E F, for
A [0, 1]. Recalling inequality (16), the second term dominates the first, and so
d log 71
E 1R (F,) er
log if 2
d
Define the random variable (r) == sup (P. P)f = sup I(P, P)fl. the equality following by symmetry of F,,, Then Talagrand's concentration inequality (Lemma B. implies that
P (r(r) 2 (() + 2(22 + 26,,E/Z((r))t++ b
Se
for all > 0. Applying standard symmetrization argument and inequality (16), we thus obtain that for 2 2 12 log a 4, with probability at least 1 - -r
dlog n
22 12 dlog n
bet 3n
(r) S crv
+ +c
+
Vt +
n²
As the last step, apply peeling argument [32, 28]: consider the intervals
F₁. gk- b% log
dog m 24
6
k 1,2,..... Kn = logg dloog m
n
n
Let Fk = E Pf² E Ex), where F0 F
{f E Pf² S dllogn) Then evidently
n
- = F, and letting 7 = 22 dlag we have Fr C Fk, So by union bound, with
probability least 1 - (Kn + l)e
dlog
r2
by
r ridlogn n
by for t: = 1, 1,..., Kn
ZT(rx) S CTAY
+ c
+
Vt +
(2la)
122
3n
20

---

and
d dlog n
To 122
by dlog n
but
Zn (ro) S
vt +
(21b)
3n
Recall the definition (f) == Pf = Var(f) + (Pf)². Then f F implies 2 S v(f) S rk-
so that on the event that all the inequalities (21) hold, then simultaneously for all satisfying (f) z dlog then
d llo n (P,, PISI cfl))
(f( +oV n² + be
d log V (f)
be 3n
Vi
n
n
n
while for f with (f) S dlog
we have
n
d dlog
d dlog n n²
b& d dlog Vt bø 3n
I(P - P)5 S
ov
t.
n
(To obtain the absolute bounds, have used that ʃ E F implies -5 F and each set F, and 5 is symmetric.) Finally, we note that
(f) n²
be
dllog
vf( n²
1 bgllogn
xf(
(
n
2n
2n
b v dlogn e(f)
22n
Vn
which implies the first statement of Lemma B.4. The second statement follows via the same argument.
D Further simulations
We can incorporate a few recent theoretical results to enhance the practical performance of the proposed conformalization procedures, allowing some additional performance gains, while simul- taneously exhibiting the need for future work. We consider mostly the difference between the full conformal approach that Gibbs al. [12] develop and the split-conformal approaches that sim- ply minimize the empirical loss (8). Our theoretical results provide no guidance to lower-order corrections to the desired level to guarantee (exact) marginal coverage rather than approximate sample-conditional coverage, and so we proceed a bit heuristically here, using theoretical results to motivate modifications of the level that do not change the sample-conditional coverage results provide, but which turn out to be empirically effective.
To motivate our tweaks, recall the classical (unconditional) conformal approach to achieve exact finite- sample marginal coverage P(Y n+1 E C, (X), where the confidence confidence set C,, (x) {y ssx,, v) S F. Setting 7, = Quant (ST). the slightly enlarged quantile, guarantees (1 - a) coverage; this follows by letting S(r,.) the order statisties of ST and S(,, those of ST and noting that the score Sa+1 < S(k.n) if and only if Sx+1 S S(k, [27, Lemma 21, the inflation by atl is necessary. Equivalently, if we wish to achieve coverage (1 Oldes)
using the estimator (8) with feature mapping (xx) fit at level a, then a must solve (1 - a) =
(1+ 21 (1+))(11 under-covers.
ades), that is, 1 (1+ )] ades) (1 Jades 1. That is, quantile regression
When ø : X' + Rd, it is then natural to heuristically imagine that the order statistics ought to "swap orders" by at most roughly d items and so we ought to target coverage n-dd (1 ades); unfortunately. it escapes our ability to prove such result eurrently. Nonetheless, we consider a "naive" adaptation of the confidence level, setting a to solve
nn
()
(1
d
d
(1 (1
(1 Oldes),
Oldes
(22)
72
and then choosing 0 minimize (8) with this a, which we term the "naive" choice. Bai et al. [2] give an alternative perspective, where they show that the actual marginal coverage achieved by quantile
21

---

regression at level a in the high sigh-dimensional scaling d,n - 00 with d/n - E (0,1) is
[ -0-a) - o(d/n)
d
(1 -
for a < 2. at least when the covariates are Gaussian. Solving this and ignoring the higher-order term, we recognize that to achieve desired coverage a, we ought (according to this heuristic) to compute the estimator (8) using a solving
(1 Oides (1 d
Odes
2n
d
(23)
72
We call the choice (23) the "scaling" choice. Neither the rescalings (22) or (23) have any effect on the convergence guarantees theory provides, they are of lower order.
We perform two synthetic experiments that give sense of the coverage properties of the methods we have analyzed. These exploratory experiments help provide justification for the heuristic corrections to the desired level a we set the real data experiments.
D.1 Level rescaling on a simple synthetic dataset
For our first experiment, consider the simple setting of standard Gaussian linear model, where we observe
iid y: = (w= + EE ~ N(O, and x; iid We mimic the experiment Gibbs et al. [12, Fig. 3] provide, but we investigate the coverage properties of the coverage set from the estimator (8) with uncorrected and level a corrected either naively (22) or via the scaling correction (23). In all cases, we use the feature map 6(x) = (1, 1 > 0} ..... Haa 0}) {0, 1]d+1 indicating nonnegative coordinates. Figure displays the results of this experiment for 1000 trials, where in each trial, draw w* Uni(gd-1), fit regression estimator T on training dataset of size Ahmin = 100 using least squares, then confor- malize this predictor using validation set of size n and evaluate its coverage
~ N(O, La).
dataset of size Plest = 10m 1000. We vary the ratio n/d of the validation dataset, keeping d = 20 fixed. From the figure, it is clear that the uncorrected confidence set using ades undercovers, especially when the ratio n/ d < 20 or so. The naive correction (22) appears to be a bit conservative, while the scaling correction (23) more effective.
3.5
00
0.0
880
0.25
3.0
20
Miscovenge
0,20
Correction None
Lenglh
Correction None Naive
0.15
Naive
$000
Scaling
Scaling
1.5
0.00
10
20
40
3
10
20
40
Ratio
(a)
(b)
Figure 2. Impact of the correction to a used in fitting the conformal predictor (8) for a desired level
Odes = .1. i... 90% coverage. The "None" correction uses a = Ocks. "Naive" uses the correction (22), and "Scaling" uses the correction (23). (a) Coverage rates with the desired coverage marked as the red line. (b) Width predictive intervals C(x) = {u E [f(z) vl S ØT d(x))-
22

---

Miscovet
Index
Group Index
(a)
(b)
Langan
Group
Group
(c)
(d)
Figure 3. Comparison of full- and split-conformal methods the simulated sinusoidal data of Sec. D.2 Plots and (c) use validation
with Mezai 200 training examples and target miscoverage
sample sizes Tival 20k 100, while (b) and (d) use Téval 160k 800. Plots (a) and (b) show
miscoverage P(Y ((x) x B.) by group B;: plots (c) and (d) prediction interval lengths.
D.2 Full conformal versus split-conformal predictions
We briefly look the coverage properties of the full conformalization method (5) from the paper [12]. comparing with split-conformal methods (8), asymmetric mean-zero heteroskedastic noise. We generate pairs (X,, Y2) R22 according to
synthetic regression dataset we design to have
f(z) + Exx), discretizing [0, into bins B, = {a S < (+1 }.
......... k 1, for
Within each experiment, we draw Uo. U1 iid Unil- 1, 1] and Φo, Φ1 Unil g 4m] to define
sid
[(x) Un cos(Øn x) U1 sin(d) x))-
Within the ith region! & < i+1 set λu exp(3 t) and d1,i exp(4 20), ie., evenly spaced in fea , e)) and (ea (e".....ee! .....,,)). and draw
No.a with probability EExp(A1..) otherwise,
Exp(Ao,i)
E(x)
AA,
I+6
so that E[s(x) x]] 0 but the noise is skewed upward, with variance increasing in i.
Figure shows the results of this experiment over 200 independent trials, where in each experiment we draw a new mean function f and fit it using a degree 5 polynomial regression on a training set of size Train 200. The conformalization methods use group-indicator featurization 6(z)
(1, 1xx B1) ..... 1(x B&)) and confidence sets C(x) = =y 6g ((x) S y S 0 o(x)). Within each trial, we compute miscoverage proportions P(Y & [(x)
B.) for each bin i on test set of size 500, drawing new function f. We vary the size of the validation data fhal = (10k, 20k, 40k, 80k, 160k). and use the scaling correction (23) to set a for the split-conformal method. The figure plots results for validation sizes 40k and 160k; from the fiiche-which is consistent with our other sample sizes and experiments-ww see that when the validation size is large relative to the dimension of the mapping o, both methods are similar; for smaller ratios, the offline method undercovers slightly within the groups, though its marginal coverage remains near perfect in spite of the very non- Gaussan data.
We remark in passing that the full conformal method requires roughly 10x the amount of time to compute predictions as the split conformal method requires to both fit quantile prediction model and make its predictions. Once the split-conformal quantile model is available-it has been fit-this difference becomes roughly factor of 2000-4000 in experiments. For some applications, this
23

---

may be immaterial; for others, it may be substantial expense, suggesting that a decision between the offline method and the online procedure may boil down to one of computational feasibility.
24

---

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

---

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

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is available, along with the paper, at the public repository https:
//github com/ jduchi/ cond/ conf conformal.. ormal.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ httppsscccppbccccceeeeceeecc www./guisssee/eee CoodeSubmis ssi aesionPooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The code reproduce the experiments is available httpa://github.com com/ j sduchi/conds ctt.//oodddooooooooooooooooooooo ormal.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments are runnable on a laptop in an hour or so.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp//eerssp..e// cwwurpps.c/puuuee httpppulicc/hiccauuidddeeec
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The authors view this paper having limited significant societal impact, its main focus is foundational research. It provides valid confidence sets for predictions, which presumably can be used improve any predictive ML algorithm, but the focus of the paper is theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

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

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
30

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: http:///nnuuueeeeeeee heaprrppssce//ooneeeenneeee///// for what should or should not be described.
31


Reviews:
[{"review_id": "0LVGvXC8nU", "reviewer": "Reviewer_D6i1", "summary": "This paper analyzes split conformal methods with confidence sets using adaptive thresholds of the form $\\hat{C}(x) = \\\\{y | s(x, y) \\leq \\hat{h}(x)\\\\}$, where $\\hat{h}$ is learnt via quantile regression on the calibration/validation data. It derives high-probability bounds for achieving approximate covariate-conditional coverage, while being conditioned on the calibration/validation data. Additionally, such methods are minimax rate optimal.", "questions": "__Questions and Comments__\n\n1.\tDid the authors run evaluations on regression tasks as well?\n\n2.\tIt is not easy to demarcate existing theoretical results from new ones. Doing so will help with the presentation of the paper.\n\n3.\tWhat is $S_{1}^{n}$ in line 52?\n\n__Typos__\n\n1.\tThe equation in the panel under line 106 has two equalities with 0.\n\n2.\t\"The construction (5) appears appears to obtain better...\" $\\rightarrow$ \"The construction (5) appears to obtain better...\" (line 136)", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths__\n\n1.\tStudying the conditional coverage of split conformal methods is an important research area. In practice, the calibration/validation is fixed, and covariate-conditional guarantees are ideal.\n\n2.\tThe theoretical claims provide high-probability bounds for achieving approximate covariate-conditional coverage, while being conditioned on the calibration/validation data\n\n3.\tThe paper is well written and has a good flow to it.\n\n__Weaknesses__\n\n1.\tWhile the experimental results provide some evidence supporting the theoretical claims, is there a way to verify their correctness more concretely? For instance, by checking if the empirical coverage lies within the derived bounds?", "was_revised": true, "final_justification": "As suggested, the authors have run additional experiments on verifying the theoretical claims.\n\nI remain in support of the paper!", "rebuttal": "Thank you for the constructive review. Let me attempt to answer the reviewer's questions below:\n\n1. While the experimental results provide some evidence supporting the theoretical claims, is there a way to verify their correctness more concretely? For instance, by checking if the empirical coverage lies within the derived bounds?\n\nAssuming the theorems are true (we all make mistakes, but I'm pretty confident on these), the empirical coverage will like within the derived bounds. While I cannot submit figures, I have done as the reviewer suggests--the bounds are conservative.\n\nPerhaps the more important question--which remains an open research question--is whether the \\sqrt{n} error can be avoided. \"Full conformal\" methods have errors scaling as O(d/n) in these cases, while the methods in the current submission have a downward coverage bias that appears to scale with \\sqrt{d/n}. This is, of course, worse. I ought to have noted this more carefully as an open question in the discussion. (It seems plausible that one might be able to *use* leave-one-out sampling to estimate the bias, but this needs more work.) Of course, the minimax lower bounds that Areces et al. (ref [1] in the submission) provide show that this is impossible for two-sided guarantees; if we only cared about coverage then it may be possible to achieve one-sided guarantees without the \\sqrt{d/n} penalties.\n\nOther questions:\n1. Did the authors run evaluations on regression tasks as well?\nYes, though these appear only in appendices. The big-picture take-homes remain identical.\n\n2. It is not easy to demarcate existing theoretical results from new ones. Doing so will help with the presentation of the paper.\nApologies. In revision I'll make sure to incorporate known results *in* the result statements. To clarify briefly: Corollary 1.1, Proposition 1, and Corollary 2.1 are known; each other result in the paper is new. These new results include Proposition 2, Theorems 1--3, and their attendant lemmas and corollaries.\n\n2. What is $S_{1}^{n}$ in line 52?\nIt's supposed to stand for $S_1^n = (S_1, \\ldots, S_n)$ where $S_i = s(X_i, Y_i)$, but I must've missed defining it... sorry!\n\nI'll fix all the noted typos."}, {"review_id": "GSRQvDDqyW", "reviewer": "Reviewer_C1kY", "summary": "The paper studies Conformal Prediction under sample-conditional coverage, where the coverage holds with high probability conditional on the training and calibration data. The authors show that split conformal prediciton, including adaptive thresholds via quantile regression, can achieve approximate sample-conditional coverage. Theoretically results are established under standard i.i.d. assumptions, with minimax-optimal bounds in certain settings. The paper also includes a small empirical study to illustrate conditional coverage performance.", "questions": "- The theoretical guarantees for the threshold function depend on the VC dimension of the function class. In practice, if the model class is complex and the calibration sample is small, do the guarantees still hold meaningfully?\n\n- The theory assumes i.i.d. data. In practical applications (e.g., covariate shift or posterior drift), how robust is the proposed method to deviations from this assumptions? Could the sample-conditional perspective extend to covariate shift scenarios?\n\n- What does the empirical section actually validate? I don't see how this is related to the theoretical analysis.", "limitations": "No. Please refer to the weaknesses and questions above.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The theoretical results are solid and well-justified. Although i did not read all the proofs, they look good to me and the assumptions are reasonable.\n- Conditional coverage is a meaningful and realistic goal to study, and the motivation behind focusing on it in this work is well explained.\n- The presentation is mostly clear, and the theoretical contribution can be followed for readers familiar with the area.\n\nWeaknesses:\n- I don't quite get the idea of the empirical section. It is not connected to the theory. The setup is limited and does not clearly demonstrate the practical advantages of the proposed guarantees.\n- While the viewpoint of this paper is well motivated, the method is based on existing works and conformal tools, and the novelty lies mainly in pure analysis rather than methodology.\n- The paper may be hard to appreciate for readers unfamiliar with the conformal literature.\n\nTypos:\n- Line 136: duplicate \"appears\".\n- Line 250: typo \"slighlty\"\n- Line 261: typo \"downard\"\n- Line 398: typo \"shsared\"\n- The format of the reference part is inconsistent.", "was_revised": true, "final_justification": "I have read through the rebuttal and will maintain my score.", "rebuttal": "Thanks to the reviewer for the thoughtful and careful review. A few responses here, focusing on the weaknesses the reviewer notes:\n\nThe main feedback of the reviewer was to ask about the experiments. I could have been clearer in these. As the reviewer notes, the contributions of this paper are mostly on the theoretical side--giving optimal guarantees for predictive validity and sharp analyses--rather than empirical. Nonetheless, the point of the experiments was twofold:\n1. To demonstrate that the offline conformal method (using X-dependent thresholds via $\\hat{C}(x) = \\\\{y \\mid s_y(x) \\le \\hat{\\theta}^T \\phi(x)\\\\}$) could provide closer to the target coverage of 90% than a single thresholded confidence set of the form $\\hat{C}(x) = \\\\{y \\mid s_y(x) \\le \\hat{\\tau}\\\\}$ would. (So in Figure 1 of the submission, note that across random slices of the data, the split conformal method achieves much closer to 90% coverage than the static, i.e., single threshold confidence set.)\n\n2. To see that an offline method could be computationally much more scalable than a full conformal method. The offline methods are about 8000x faster (at prediction time) than full conformal methods (see the comment in the discussion on page 9).\n\nThe theoretical guarantees for the threshold function depend on the VC dimension of the function class. In practice, if the model class is complex and the calibration sample is small, do the guarantees still hold meaningfully?\n\nBluntly, no. But to be fair, we wouldn't expect that to be the case: these methods provide distribution-free coverage, and so we cannot hope to do too much better (as the minimax lower bounds in reference [1] of the paper show). With that said, it would be interesting--I can include this as an open question--to give data-dependent guarantees. Another option, probably empirically as effective but which does not provide the same approximately conditional guarantees, is to split the validation sample to \"re-conformalize\" the confidence sets. Then the only concentration one needs is on the single threshold being learned. This would mean fitting a confidence set $C(x) = \\\\{y \\mid s_x(y) \\le \\hat{h}(x)\\\\}$ on one validation sample, then on the second validation split, fitting $\\hat{C}(x) = \\\\{y \\mid s_x(y) \\le \\hat{h(x)} + \\hat{\\tau}\\\\}$, where only $\\tau$ is fit on this second sample to correct for mistakes in $\\hat{h}(x)$. (This is similar to the approach, e.g., in the paper \"Knowing what You Know: valid and validated confidence sets in multiclass and multilabel prediction\" by Cauchois et al., JMLR 2021.) \n\nThe theory assumes i.i.d. data. In practical applications (e.g., covariate shift or posterior drift), how robust is the proposed method to deviations from this assumptions? Could the sample-conditional perspective extend to covariate shift scenarios?\n\nGood question. It depends on the structure of the covariate shift and the fidelity of the functionals being learned to the covariate shift. So, for example, if one fits a confidence set of the form $\\hat{C}(x) = \\{y \\mid s(y, x) \\le \\hat{\\theta}^T \\phi(x)\\}$, and the conditional distribution of $y$ is specified reasonably well by a linear functional of $\\phi(x)$, then yes--the learned $\\hat{C}(x)$ should transfer. If not, then we would expect failure. To be clear, this is the same strength/weakness of typical work on covariate shift: it really only makes sense insofar as there is no hidden confounding, that is, $x$ specifies the conditional distribution of $y$ completely. If it doesn't, for example, because of some unobserved variable $U$ with graphical structure $U \\rightarrow Y \\leftarrow X$, then frankly, covariate shift makes no sense anyway.\n\nAlso, thanks for pointing out the typos; will address them. Though I confess I am not sure what the reviewer refers to when they write that \"The format of the reference part is inconsistent.\" ?"}, {"review_id": "CXk4pKEHPY", "reviewer": "Reviewer_tt8B", "summary": "This paper revisits the problem of constructing predictive confidence sets, aiming to achieve near desired coverage levels with high probability, a guarantee conditional on the validation data rather than marginal over it. The authors show that the natural method of performing quantile regression on a held-out dataset yields minimax optimal guarantees of coverage. In addition, the authors specifically consider coverage conditional on a covariate $X$ belonging to some group of interest. Numerical experiments are provided that are consistent with the positive theoretical results.", "questions": "1. I would appreciate it if the authors could further clarify the motivations and key contributions of this work, as this would help readers better appreciate these rigorous theoretical results in this paper.\n2. I have some reservations regarding the experimental results. Could the authors clarify whether the demonstrated performance reflects sample-conditional coverage properties? From my perspective, these results appear to demonstrate group-conditional coverage properties rather than the claimed sample-conditional coverage. \n\nOther minor comments: \n● Typo: double appears in Line 136\n● Typo: $\\mathbb{S}^{d-1}$might be $\\mathbb{B}^{d-1}$?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**: \nThis work investigates the theoretical analysis of conditional coverage properties within the framework of split conformal prediction, and the authors demonstrate rigorous results and establish tighter bounds with solid theoretical proofs. \n\n**Weaknesses**: \n1. The authors presented lots of theoretical results as well as prior findings in related works, though the presentation might be a little confusing and could be more focused and clearer to highlight the key contributions better. \n2. The authors focus on the sample-conditional coverage. A more thorough discussion of the underlying motivations could potentially enhance the applicability and practical value of this work. \n3. This work appears to focus primarily on theoretical contributions (tighter bounds), while it doesn't include a new algorithm or approach. \n4. The authors might consider providing more comprehensive elaboration on certain essential technical concepts. For example, the key results concerning minimax rate optimality may require additional explication for readers less familiar with this specialized framework.", "was_revised": true, "final_justification": "I have read through the responses and will maintain my score since the connection to sample-conditional coverage guarantees appears insufficiently developed in the experimental section.", "rebuttal": "Thanks to the reviewer for the comments and feedback. Let me address the main points below (I will of course fix typos the reviewer notes):\n\n1. Presentation. I'll do my best to tighten up the results; see also the response to reviewer D6i1. In brief, adding citations to existing corollaries should help make things clearer. If the reviewer thinks this would help, moving the proof of Theorem 1 later in the paper is certainly an option.\n\n2. On sample conditional coverage, both experimental and philosophical (i.e., \"Why do this at all?\") questions: totally fair. As to the philosphical, I find Bian and Barber's [BB] paper \"Training-conditional coverage for distribution-free predictive inference\" instructive. Basically, in most ML applications, we wish to know that *given the training data we have,* we are likely to generalize well. Full-conformal methods cannot guarantee this, as [BB] shows; they only guarantee generalization in an average sense over both training and test data. As [BB] writes, \"In practice, we are often interested in the coverage rate for test points once we fit a regression algorithm to a particular training set.\" I ought to have been clearer on that.\n\nOn the experimental side, hoo-boy. The reviewer is absolutely right to point that out. The experiments--which, as I note, one ought to take more as \"exploratory\" (because the main focus of the paper is theoretical)--do not directly address the sample-conditional aspects of the guarantees so much as the \"$\\phi(x)$-conditional\" guarantees (or, perhaps, group-wise guarantees). At this point, I will perhaps appeal to the mercy of the reviewers: it would be supremely interesting to understand whether sample-conditional coverage is practically relevant, especially relative to the marginal coverage guarantees full-conformal inference provides. [BB] provide a counterexample showing that there exist cases where full-conformal methods are quite unstable. But understanding the extent to which this is practically meaningful would require a slew of experimental work that is beyond the current focus of this submission. I'm of the (perhaps biased) opinion that a theoretically-focused paper should be allowed to be theoretical so as to keep the paper focused rather than spread too thin.\n\n3. On the key technical underpinnings: I will (in revision) include more on the minimax optimality material. This is a good idea, and will hopefully help highlight more motivation for this paper. The paper by Areces et al. [1] is not so well-known. Basically, it states that if one wants to obtain $\\mathcal{W}$-weighted conditional coverage, one must pay a factor involving both the desired confidence level $\\alpha$ and VC-dimension $d$ of the class $\\mathcal{W}$. Rewriting this material to highlight it as a lower bound--and connecting, e.g., to earlier work that does not achieve these optimal rates--will help the presentation, and I'll do that in revision."}, {"review_id": "GrwCLIoVpV", "reviewer": "Reviewer_538x", "summary": "This paper presents new theoretical results demonstrating that split conformal methods can achieve near-nominal coverage with high probability.", "questions": "1. In line 245, please clarify the statement: \"the static thresholded sets have more variability in coverage on the random slices of the dataset.\" A more intuitive explanation of the experiments results, especially in relation to the theoretical results, would be very helpful for understanding how the theory connects to the experimental observations.\n\n2. Aside from group-conditional coverage, are there other types of conditional coverage that split conformal prediction can guarantee?", "limitations": "Yes, limitations are discussed in the last section of paper.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper offers a fresh perspective on sample-conditional coverage for split conformal prediction methods, supported by strong theoretical guarantees and clear exposition.\n\nWeaknesses:\n- The experimental results are not sufficiently intuitive or easy to interpret.", "was_revised": true, "final_justification": "Thank you for these clarifications. And I keep my positive score of 4.", "rebuttal": "I thank the reviewer for the review and feedback.\n\nAs the reviewer notes, the main purpose of this paper is theoretical, in that I attempt to provide the sharpest possible results on coverage and predictive inference with conformal-like methods. (Indeed, the results are minimax-optimal, so there is little room for improvement without further assumptions!)\n\nWith regards to the experimental results, these are fair points. (See also my responses to the other reviewers, especially C1kY). Essentially, the experiment is showing that confidence sets of the form\n$$\n\\hat{C}(x) = \\\\{y \\mid s_y(x) \\le \\hat{\\tau} \\\\}\n$$\ndo not achieve coverage as close to the desired level $1 - \\alpha$ (where $\\alpha = .1$, i.e., 90% coverage) as do the adaptive sets\n$$\n\\hat{C}(x) = \\\\{y \\mid s_y(x) \\le \\hat{\\theta}^T \\phi(x)\\\\}.\n$$\nI will clarify this in revision. The latter sets--see Fig. 1--and the related sets that full-conformal inference gives appear to have coverage much closer to the desired 90% level.\n\nThe reviewer also asks whether one can achieve things beyond group-conditional coverage. At some level, all conditional coverage is group-conditional (just with very small groups), but I think this is too pat an answer. By looking at linear combinations $\\phi(x)^T \\theta$ of group indicators, one can obtain coverage over unions of groups--still group-conditional, of course--or even more exotic setwise operations. Understanding the tradeoffs between pure distribution-free coverage and the types of conditional-like coverage one can achieve remains a tantalizing but active area of research (cf. the cited papers [10, 3, 28])."}]

Author rebuttal:

Meta-review: The goal of this paper is to analyze split conformal prediction methods where the prediction sets/intervals are constructed using input-conditioned conformity score threshold, \hat{\tau}(x)), which learned using quantile regression on a calibration/validation set. The key contribution is to derive high-probability bounds for achieving approximate covariate-conditional coverage conditioned on the calibration/validation data.  Also, such methods have minimax optimal guarantees of coverage. The paper also provides sample experiments on a classification task in the main paper and regression tasks in the appendix to verify theory.

The paper had mixed ratings (two positive and two negative). The main concerns of the two negative reviewers' are:
1. Lack of methodological contribution
2. Lack of more experiments to demonstrate practical significance

The first one is minor as the focus of the paper is on theory. I acknowledge that the paper could be improved on the experiments side, but I'm convinced by the authors' response (which I found very refreshing and quite scientific in the current publication enterprise) to multiple reviewers' including D6i1 where they pointed to the fact that results on regression tasks are in the Appendix.

By considering all the factors, I'm leaning towards accepting the paper -- It is a solid theory paper on an important problem. I strongly encourage the authors' to make the following changes in the paper.
- Improve exposition of the paper to clearly articulate the motivation and take home message for practitioners.
- Clearly separate the known results and new results as suggested by one of the reviewer.
- Add more experiments as per the reviews and discussion using the extra page. Clearly articulate the goal and main findings of the experiments as done in your response.
Decision: Accept (poster)