A Few Observations on Sample-Conditional Coverage in Conformal Prediction

John Duchi · 2025

Read A Few Observations on Sample-Conditional Coverage in Conformal Prediction by John Duchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00220.txt.

Introduction

John Duchi revisited in 2025 a basic promise of conformal prediction: that its confidence sets should hold not just on average but for the case at hand. The paper gives fresh arguments for how split conformal methods nearly hit their target coverage with high probability, judged on the validation data itself rather than in expectation.

It then turns to group-conditional coverage, where the set must cover for patients, places, or classes of interest. Running quantile regression on held-out data, Duchi shows, gives guarantees that are optimal in the minimax sense. Experiments round out the picture with a warning: efficient, valid conditional methods are still unfinished business. The note is short but sharp. It separates what is proven from what is merely hoped.

Catalog record

CREATORJohn Duchi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00220

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Few Observations on Sample-Conditional Coverage in Conformal Prediction John Duchi 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 X belonging to some group of interest, we would like a guarantee that a predictive set covers the true outcome Y Y . We show that the natural method of performing quantile regression on a held-out (validation) dataset yields minimax optimal guarantees of coverage here. Complementing these positive results, we also provide experimental evidence that interesting work remains to be done to develop computationally efficient but valid predictive inference methods. 1 Introduction and background In conformal prediction [ 29 , 19 , 20 , 3 ] , we wish to perform predictive inference on the outcome Y coming from pairs (X,Y)\in\mathcal{X}\times\mathcal{Y} . The basic approach yields confidence sets C(x)\subset\mathcal{Y} , where given a sample (X_{i},Y_{i})_{i=1}^{n} , an estimated confidence set \widehat{C} provides the (marginal) coverage \mathbb{P}\left(Y_{n+1}\in\widehat{C}(X_{n+1})\right)\geq 1-\alpha. (1) Typically, to do this, we assume the existence of a scoring function s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R} and define confidence sets of the form C_{\tau}(x)\coloneqq\{y\mid s(x,y)\leq\tau\} . For example, when predicting Y\in\mathbb{R} in regression, given a predictor f:\mathcal{X}\to\mathbb{R} the absolute error s(x,y)=|f(x)-y| yields the familiar confidence set C_{\tau}(x)=\{y\in\mathbb{R}\mid|y-f(x)|\leq\tau\}=[f(x)-\tau,f(x)+\tau] of values y near f(x) . The classical (split-conformal) approach [ 29 , 3 ] uses the sample to find the threshold \widehat{\tau} larger than the observed scores on about 1-\alpha fraction of the data, then notes that s(X_{n+1},Y_{n+1}) is likely to be smaller than this threshold. More formally, if (X_{i},Y_{i}) are exchangeable and we let S_{i}=s(X_{i},Y_{i}) , then for the order statistics S_{(1)}\leq S_{(2)}\leq\cdots\leq S_{(n+1)} , we have \mathbb{P}\left(S_{n+1}>S_{(\left\lceil{(1-\alpha)(n+1)}\right\rceil)}\right)\leq\alpha, because the probability that S_{n+1} is in the \alpha -largest fraction of the observed scores is at most \alpha . Then a bit of bookkeeping [e.g. 25 , Lemma 2] shows that the slightly enlarged empirical quantile \widehat{\tau}\coloneqq\mathsf{Quant}_{(1-\alpha)(1+1/n)}(S_{1},\ldots,S_{n}), provides the guarantee \mathbb{P}\left(S_{n+1}>\widehat{\tau}\right)\leq\alpha. Written differently, the confidence set \widehat{C}(x)\coloneqq\left\{y\in\mathcal{Y}\mid s(x,y)\leq\widehat{\tau}\right\} satisfies \mathbb{P}(Y_{n+1}\in\widehat{C}(X_{n+1}))=\mathbb{P}\left(s(X_{n+1},Y_{n+1})\leq\widehat{\tau}\right)=\mathbb{P}\left(S_{n+1}\leq\widehat{\tau}\right)\geq 1-\alpha. 1.1 On X -conditional coverage We might ask for more than the marginal guarantee ( 1 ) in a few ways. The first is to target X - conditional coverage , where given a new datapoint X_{n+1} , we wish to achieve \mathbb{P}(Y_{n+1}\in\widehat{C}(X_{n+1})\mid X_{n+1})\geq 1-\alpha. But there are fundamental challenges here. Let us say a set valued mapping \widehat{C}_{n}:\mathcal{X}\rightrightarrows\mathcal{Y} achieves distribution-free conditional (1-\alpha) coverage if for any P , when (X_{i},Y_{i})\stackrel{{\scriptstyle\rm iid}}{{\sim}}P and \widehat{C}_{n} is a function of (X_{i},Y_{i})_{i=1}^{n} , then for P -almost-all x , \mathbb{P}(Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\mid X_{n+1}=x)\geq 1-\alpha. (2) Unfortunately, such a distribution-free guarantee is impossible. Focusing on the case that \mathcal{Y}=\mathbb{R} for simplicity, so that confidence sets \widehat{C}(x)\subset\mathbb{R} , Vovk [28, Proposition 4] shows that the Lebesgue measure \mathsf{Leb}(\widehat{C}(x)) is almost always infinite (see also Barber et al. [3] ): Corollary 1.1 . Let \mathcal{X} be a metric space and assume that X\in\mathcal{X} has continuous distribution. If \widehat{C} provides distribution free (1-\alpha) conditional coverage, then for P -almost all x\in\mathcal{X} , \mathbb{P}(\mathsf{Leb}(\widehat{C}(x))=+\infty)\geq 1-\alpha. Similar results apply when the marginals over X are not too discrete [ 10 , Corollary 7.1] . These failures motivate relaxing the conditional coverage condition ( 2 ). Perhaps the simplest approach considers group-conditional coverage , where for groups G\subset\mathcal{X} , one targets the guarantee \displaystyle\mathbb{P}(Y_{n+1}\in\widehat{C}(X_{n+1})\mid X_{n+1}\in G)\geq 1-\alpha. (3) Barber et al. [3, Sec. 4] show how to achieve the coverage ( 3 ) by considering worst-case coverage over all groups G of interest; Jung et al. [16] consider variations on this guarantee. Gibbs, Cherian, and Candès [11] develop a compelling relaxation extending this idea. To begin, note that conditional coverage \mathbb{P}(Y\in\widehat{C}(x)\mid X=x)=1-\alpha is equivalent to the condition \mathbb{E}\left[w(X)\left(1\!\left\{Y\in\widehat{C}(X)\right\}-(1-\alpha)\right)\right]=0 (4) for all bounded (measurable) functions w:\mathcal{X}\to\mathbb{R} . Indeed, the tower property of conditional expectations shows that equality ( 4 ) holds if and only if \mathbb{E}\left[w(X)\left(\mathbb{P}(Y\in\widehat{C}(X)\mid X)-(1-\alpha)\right)\right]=0,~~\mbox{i.e.}~~\mathbb{E}\left[\left|\mathbb{P}(Y\in\widehat{C}(X)\mid X)-(1-\alpha)\right|\right]=0, where we take w(x)=\mathop{\rm sign}(\mathbb{P}(Y\in\widehat{C}(X)\mid X=x)-(1-\alpha)) , so \mathbb{P}(Y\in\widehat{C}(X)\mid X)=1-\alpha with probability 1 . Similarly, we obtain the one-sided inequality ( 2 ) if and only if \mathbb{E}\left[w(X)1\!\left\{Y\in\widehat{C}(X)\right\}\right]\geq(1-\alpha)\mathbb{E}[w(X)] for all nonnegative bounded w . Taking w(x)=1\!\left\{x\in G\right\} for groups G\subset\mathcal{X} shows that this guarantee implies the group-conditional coverage ( 3 ); relaxing the condition ( 4 ) by considering subclasses of weighting functions \mathcal{W}\subset\{\mathcal{X}\to\mathbb{R}\} leads to the following definition [ 11 ] : Definition 1.1 . A confidence set C:\mathcal{X}\rightrightarrows\mathcal{Y} achieves \mathcal{W} -weighted ((1-\alpha),\epsilon) coverage if \big|\mathbb{E}\left[w(X)\left(1\!\left\{Y\in C(X)\right\}-(1-\alpha)\right)\right]\big|\leq\epsilon for all w\in\mathcal{W} . In Definition 1.1 , we take the confidence set mapping C to be fixed; Gibbs et al. allow \widehat{C} to be random, in which case (in their definition) the expectation is taken also over the \widehat{C} itself. Because we study coverage conditional on a sample used to construct \widehat{C} , we maintain Definition 1.1 . Gibbs et al. ’s main two examples are cases in which \mathcal{W} corresponds to a vector space of the form \mathcal{W}=\{w\mid w(x)=\langle v,\phi(x)\rangle\} for some feature mapping \phi:\mathcal{X}\to\mathbb{R}^{d} , and when \mathcal{W} corresponds to a reproducing kernel Hilbert space. At prediction time—on a new example X_{n+1} —they perform full conformal inference [ 29 ] , where implicitly for each t\in\mathbb{R} , they solve \widehat{h}_{n+1,t}=\mathop{\rm argmin}_{h\in\mathcal{W}}\sum_{i=1}^{n}\ell_{\alpha}(h(X_{i})-S_{i})+\ell_{\alpha}(h(X_{n+1})-t) for the quantile loss \ell_{\alpha}(t)=\alpha\left[{t}\right]_{+}+(1-\alpha)\left[{-t}\right]_{+} , then define the implicit confidence set \widehat{C}_{n}(X_{n+1})\coloneqq\left\{y\in\mathcal{Y}\mid s(X_{n+1},y)\leq\widehat{h}_{n+1,s(X_{n+1},y)}(X_{n+1})\right\}. (5) A careful duality calculation [ 11 , Sec. 4] shows how to compute \widehat{C}_{n} by solving a linear program over O(n+d) variables using (X_{i})_{i=1}^{n+1} and S_{1}^{n} , and Gibbs et al. show the set ( 5 ) satisfies \left|\mathbb{E}\left[w(X_{n+1})1\!\left\{Y_{n+1}\not\in\widehat{C}_{n}(X_{n+1})\right\}-w(X_{n+1})(1-\alpha)\right]\right|\leq\epsilon_{\textup{int}}(w) for all functions w\in\mathcal{W} , where \epsilon_{\textup{int}}(w) is an interpolation error term (which they control and is of typically small order in n ). Defining \mathbb{P}_{w}(A)=\mathbb{E}_{P}[w(X)1\!\left\{A\right\}]/\mathbb{E}_{P}[w(X)] to be the w -weighted probability of an event A for w\geq 0 , this inequality demonstrates that \mathbb{P}_{w}(Y_{n+1}\in\widehat{C}(X_{n+1}))\geq 1-\alpha-\epsilon_{\textup{int}}(w) (6) for all w\geq 0,w\in\mathcal{W} , a more nuanced guarantee than the marginal coverage ( 1 ). One challenge with this full conformal approach is that computing the prediction set \widehat{C}_{n} requires solving a sometimes costly optimization. This suggests split-conformal approaches that provide adaptive confidence sets of the form \widehat{C}_{n}(x)\coloneqq\left\{y\in\mathcal{Y}\mid s(x,y)\leq\widehat{h}_{n}(x)\right\}, where \widehat{h}_{n} is chosen based only on the sample (X_{i},Y_{i})_{i=1}^{n} —hence the name “split conformal”—making the set \widehat{C}_{n} easy to compute [ 25 , 8 ] . In spite of their ease of computation, it has been challenging to demonstrate that these sets can achieve coverage; for example, Romano et al. [25] and Cauchois et al. [8] apply another level of conformalization to fit a constant threshold \widehat{\tau}_{n} and use \widehat{C}_{n}(x)=\{y\in\mathcal{Y}\mid s(x,y)\leq\widehat{h}_{n}(x)+\widehat{\tau}_{n}\} . We revisit these types of sets and show a few new convergence and coverage guarantees for them, including new optimality guarantees. 1.2 Sample-conditional coverage Inequalities ( 1 ) and ( 6 ) provide guarantees marginal over the entire sampling procedure, drawing (X_{i},Y_{i})\stackrel{{\scriptstyle\rm iid}}{{\sim}}P for i=1,2,\ldots,n+1 . While conditional coverage (on X_{n+1} ) is impossible, it is possible to achieve sample-conditional -coverage. For this, let P_{n} denote the empirical distribution of (X_{i},Y_{i})_{i=1}^{n} (or simply the sample itself). Then we seek a guarantee of the form \mathbb{P}\left(Y_{n+1}\in\widehat{C}_{n}(X_{n+1})\mid P_{n}\right)\geq 1-\alpha-o(1) with high

Read the complete text