PaperlayerView exact revision on arXiv

Source-linked AI summary

Conformal Prediction With Conditional Guarantees

Isaac Gibbs, John J. Cherian, Emmanuel J. Candès

arXiv:2305.12616v4stat.ME

TL;DR

Universal exact conditional coverage is impossible in finite samples, leaving common methods with marginal guarantees or coverage for limited target groups. The paper calibrates conformal prediction over classes of covariate shifts, obtaining exact finite-sample coverage for finite-dimensional targets and estimated coverage errors for richer classes. Its group-coverage guarantees improve on prior approaches in finite-sample tightness, distributional assumptions, and scope, while a continuity assumption remains relevant to some bounds.

  • Problem

    Universal exact conditional coverage is impossible in finite samples, and common methods provide marginal validity or cover only limited pre-specified groups.

    Source: §1 · pp. 1, 3

  • Method

    The method calibrates conformal prediction over a chosen function class, spanning finite-dimensional targets and richer classes for which it quantifies coverage error.

    Source: §1 · p. 2, §3 · p. 11, §3.1 · p. 12

  • Results

    The method improves on Jung et al. (2023) with tighter finite-sample coverage, no distributional assumptions, and guarantees beyond group targets.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The approach can adaptively recalibrate conformal outputs when initial prediction scores are inaccurate, targeting exact conditional guarantees.

    Source: §1 · pp. 2–3

    Some upper coverage bounds assume that the conditional distribution of conformity scores given covariates is continuous; randomization can yield exact coverage without this assumption.

    Source: §2.2 · p. 9

Abstract

from arXiv · show

We consider the problem of constructing distribution-free prediction sets with finite-sample conditional guarantees. Prior work has shown that it is impossible to provide exact conditional coverage universally in finite samples. Thus, most popular methods only guarantee marginal coverage over the covariates or are restricted to a limited set of conditional targets, e.g. coverage over a finite set of pre-specified subgroups. This paper bridges this gap by defining a spectrum of problems that interpolate between marginal and conditional validity. We motivate these problems by reformulating conditional coverage as coverage over a class of covariate shifts. When the target class of shifts is finite-dimensional, we show how to simultaneously obtain exact finite-sample coverage over all possible shifts. For example, given a collection of subgroups, our prediction sets guarantee coverage over each group. For more flexible, infinite-dimensional classes where exact coverage is impossible, we provide a procedure for quantifying the coverage errors of our algorithm. Moreover, by tuning interpretable hyperparameters, we allow the practitioner to control the size of these errors across shifts of interest. Our methods can be incorporated into existing split conformal inference pipelines, and thus can be used to quantify the uncertainty of modern black-box algorithms without distributional assumptions.

1 Introduction

The paper addresses the gap between marginal validity and exact conditional coverage, which is impossible to guarantee universally in finite samples. It proposes a calibration framework spanning finite group targets and covariate shifts to richer classes where coverage errors can instead be quantified.

1 Introduction

  • Finite-sample exact conditional coverage is impossible universally, while marginal validity can conceal substantial coverage variation across consequential subpopulations.The introduction notes potential underestimation of uncertainty for promising drug candidates and untrustworthiness for legally protected groups.Source: §1 · pp. 1–2

1.1.2 Coverage under covariate shift

  • For finite-dimensional shift classes, the method provides simultaneous coverage over all shifts in the class, including group coverage as a special case.A singleton shift class recovers settings focused on one known or estimated shift; non-singleton classes cover all included shifts simultaneously.Source: §1 · p. 2, §1.1.2 · p. 5

1 Introduction

  • The method wraps conformal inference with adaptive recalibration, making small adjustments for well-designed scores and correcting inaccurate models toward exact conditional guarantees.The authors describe this as an added protective layer that turns potentially poor marginally valid outputs into conditionally valid prediction sets.Source: §1 · pp. 2–3

1.1 Preview of contributions

  • The paper previews applications to group and shift coverage, then outlines finite- and infinite-dimensional theory, computation, and two dataset applications.The authors describe their applications as demonstrating tighter finite-sample conditional coverage and more predictable failure modes than competing alternatives.Source: §1.1 · p. 3, §1.2 · p. 6

1.1.1 Group-conditional coverage

  • For any finite collection of groups, randomized conditional calibration guarantees exact coverage without distributional or group-overlap assumptions; its unrandomized variant obeys finite-sample coverage bounds.The displayed lower and upper bounds are 1 − α and 1 − α + |G| / ((n + 1)P(X ∈ G)), respectively, for each group G.Source: §1.1.1 · p. 4

1.1.2 Coverage under covariate shift

  • For richer, potentially infinite-dimensional shift classes, exact coverage is unavailable, but the method estimates finite-sample coverage under shifts and reports expected performance.For the illustrated Gaussian tilts, the estimated coverage matches the empirically observed values.Source: §1.1.2 · p. 6

2 Protection against finite dimensional shifts

The section recasts split conformal as quantile regression, then extends its coverage target from marginal validity to finite-dimensional classes of covariate shifts. It also compares the resulting guarantees with standard quantile regression.

2.1 Warm-up: marginal coverage

  • Split conformal is recovered as intercept-only quantile regression, with an imputed candidate test score entering the augmented calibration quantile.The prediction set includes outcomes whose conformity scores fall below the resulting augmented-set threshold.Source: §2.1 · pp. 7–8

2.2 Finite dimensional classes

  • For finite-dimensional linear classes, augmented quantile regression extends coverage guarantees from a single threshold to every reweighting function in the class.The fitted quantile estimates use the same function class as the coverage target.Source: §2.2 · pp. 8–9
  • The finite-dimensional result gives distribution-free lower bounds, while its upper bounds require continuity of S | X; randomization can provide exact expected weighted coverage without that condition.The paper notes that this distinction between upper and lower bounds is typical in conformal inference.Source: §2.2 · p. 9
  • For i.i.d. data and a finite collection of groups, if S | X is continuous, the conditional coverage for any G is at most 1 − α + |G|/((n + 1)P(Xn+1 ∈ G)).Source: §2.2 · p. 9

2.3 Related work

  • Compared with Jung et al. (2023), the method's group guarantee has a faster d/n convergence rate, while their result targets stronger calibration-conditional concentration.The paper says the theoretical results are not directly comparable.Source: §2.3 · p. 11
  • In simulations, coverage stayed close to target across d/n values, while vanilla quantile regression showed undercoverage at d/n ∈ {0.05, 0.1}.The paper reports robustness to small sample sizes or large dimensions but does not provide a PAC guarantee for its method.Source: §2.3 · p. 11

3 Extension to infinite dimensional classes

For rich, potentially infinite-dimensional function classes, exact coverage is impossible, so the paper regularizes the fit and quantifies coverage error. RKHS and Lipschitz specializations yield different coverage controls and interpolation-error bounds.

3 Extension to infinite dimensional classes

  • With regularization, Theorem 3 bounds coverage over rich classes through a penalty-direction derivative and interpolation error; randomization removes the interpolation term.The derivative estimates coverage difficulty in a chosen tilt and adapts to that tilt and the data distribution.Source: §3 · pp. 11–12

3.1 Specialization to functions in a reproducing kernel Hilbert space

  • At n = 650, d = 5, and λ ≅ 1, the reported interpolation error ϵint E[|f(X)|] is approximately 0.005.The interpolation error is stated to decay at a faster-than-parametric rate.Source: §3.1 · p. 13
  • The RKHS interpolation bound uses discretization of the linear component, stability for the kernel component, and smoothing to extend across the function class.The authors note that this proof approach may also inform central limit theorems for quantile regressors of this type.Source: §3.1 · p. 13
  • For RKHS functions plus finite features, unpenalized reweightings obtain nearly exact coverage once interpolation error is removed; kernel-component shifts have plug-in-estimable coverage degradation.The kernel component is penalized by λ∥fK∥²K, while the finite-dimensional features are unpenalized.Source: §3.1 · pp. 12–13

3.2 Specialization to the class of Lipschitz functions

  • For Lipschitz reweightings, coverage deviation is bounded in terms of λ Lip(f), but interpolation error can make coverage highly conservative in moderate-to-high dimensions.The authors describe this bound as weaker than the RKHS bound and say the proof may not be tight.Source: §3.2 · p. 14

4 Computing the prediction set

The paper uses a dual formulation and monotonicity of its dual variable to compute prediction sets without fitting a quantile regression for every possible score. This makes updating substantially faster than fitting a separate quantile regression for each test point.

4 Computing the prediction set

  • The dual formulation addresses practical ambiguity from non-unique quantile-regression fits while preserving the original set’s coverage guarantees.The dual set can be mildly conservative; randomization is available when exact coverage is desired.Source: §4 · pp. 14–15
  • The dual prediction set retains the primal set’s coverage guarantees, while its randomized version has exact, non-conservative coverage.The dual set trims some points on the interpolation boundary of the primal set.Source: §4 · pp. 14–15
  • The dual variable is non-decreasing in the imputed score, making prediction-set membership monotone and enabling a cutoff search over scores.For unregularized finite-dimensional quantile regression, the cutoff can be computed more efficiently using linear-program sensitivity analysis.Source: §4 · p. 16
  • The updating procedure is substantially faster than fitting one quantile regression per test point across a wide range of calibration-set sizes and function-class dimensions.The reported computation time depends more on dimension than sample size, and most of the cost is fitting one calibration-set quantile regression.Source: Figure 6 · p. 16, §4 · pp. 16–17

5 Real data experiments

The real-data experiments examine coverage across racial groups, flexible covariate shifts, comparisons with existing methods, and learned groups in cell images. The results show settings where conditional calibration improves coverage or makes its deviations measurable, alongside comparisons that expose the limits of alternatives.

5.1 Communities and crime data

  • Across linear re-weightings for the overall data and four racial categories, conditional calibration reaches the target miscoverage, while split conformal provides only marginal validity.The method also improves coverage over split conformal across high-racial-representation subgroups, even without explicit subgroup indicators in the function class.Source: Figure 7 · p. 17, §5.1 · p. 18
  • Kernel re-weightings provide a way to inspect local coverage; at two highlighted points, estimated coverage closely matches realized coverage.The estimates are described as highly accurate, with an effective sample size of about 275 at those points.Source: §5.1 · p. 19, Figure 9 · p. 19

5.2.1 Comparison against conformalized quantile regression

  • Against conformalized quantile regression, the randomized method achieves exact coverage across linear re-weightings, while both quantile-regression baselines show deviations; prediction-set lengths are similar except for wider OLS split-conformal sets.The unrandomized method slightly overcovers; all three methods achieve exact marginal coverage except that variant, which can slightly overcover.Source: §5.2.1 · pp. 20–21, Figure 10 · p. 21

5.2.2 Comparison against localized conformal prediction

  • For kernel shifts, the randomized method and localized conformal prediction achieve exact marginal coverage, but only conditional calibration estimates its coverage deviations, which are well approximated.Localized conformal prediction shows notable deviations despite a theoretical expectation of exact coverage under these shifts.Source: §5.2.2 · p. 21, Figure 11 · p. 22

5.3 Rxrx1 data

  • On RxRx1, learned features support good coverage across cell types and experiments, unlike split conformal’s heterogeneous group coverage.Using top principal components of the neural-network feature layer produces nearly identical results.Source: §5.3 · p. 23, Figure 12 · p. 23

6 Choosing the function class and regularizer

The section considers how choices of function class and regularizer affect coverage and prediction efficiency. Empirically, cross-validation performs near-exactly in the tested setting, while larger function classes can increase prediction-set lengths and coverage errors.

Choosing the function class and regularizer

  • Although the theory requires fixed function class and regularizer choices, cross-validation on the training set does not significantly harm coverage empirically, and both fixed and cross-validated regularization give near-exact marginal coverage.The comparison uses linear and Gaussian-kernel quantile regression in a Gaussian linear-model experiment.Source: §6 · p. 24, Figure 13 · p. 24
  • As function-class dimension grows, worst-case coverage deviation and average prediction-set length increase, even though marginal coverage remains robust.In the experiment, all covariates are spurious; the increase is attributed to high-dimensional overfitting, and worst-case error grows substantially more for quantile regression.Source: §6 · pp. 24–25, Figure 14 · p. 24

A.1.1 Verification of the conditions of Section 4

The appendix verifies that the quantile-regression problems satisfy the conditions used in Section 4. It does so by establishing finite-dimensional representations and strong duality for the considered function classes.

A.1.1 Verification of the conditions of Section 4

  • Linear quantile regression has the required finite-dimensional representation and satisfies strong duality.The appendix states both properties are clear for the linear formulation.Source: §A.1.1 · p. 29
  • For RKHS functions, the primal problem has an equivalent finite-dimensional convex optimization representation, and Slater’s condition gives strong duality.The representation uses the kernel matrix and its rows.Source: §A.1.1 · p. 29
  • For Lipschitz functions, finite-dimensional proxies for function values can be extended to a complete function, yielding strong duality by Slater’s condition.The proxies can be extended using the methods of McShane (1934) and Whitney (1934).Source: §A.1.1 · p. 29

A.1.2 Additional algorithmic details

The appendix describes procedures for computing the prediction-set cutoff and a conservative alternative. For finite-dimensional quantile regression, LP sensitivity analysis can trace the dual solution to the target cutoff.

A.1.2 Additional algorithmic details

  • For finite-dimensional quantile regression, LP sensitivity analysis traces a piecewise-linear dual solution from the test-point score until it reaches the target cutoff.The algorithm starts from a known zero dual solution at the test-point score.Source: §A.1.2 · p. 30
  • Proposition 5 initializes the LP sensitivity procedure with a valid dual solution formed by appending zero to the training-data dual solution.This holds when strong duality holds for the stated optimization problem.Source: §A.1.2 · p. 30
  • When an upper bound M for the test-point score is known, a single quantile-regression fit yields a conservative prediction set with a conservative coverage guarantee.The stated result assumes M is a valid upper bound and uses a min-norm solution.Source: §A.1.2 · pp. 30, 32

A.2 Additional experiments on the Rxrx1 data

The PCA-based method achieves empirical coverage close to the target across cell types and experiments. The analysis uses the top 70 principal components of the neural-network feature layer.

A.2 Additional experiments on the Rxrx1 data

  • The PCA-based analysis uses the top 70 principal components of the neural-network feature layer, with other experimental steps unchanged.The number of components was selected by visual inspection of the scree plot.Source: §A.2 · p. 33
  • Empirical coverage is close to the target across cell types and experiments; Figure 16 compares the unrandomized method with split conformal around α = 0.1.The figure marks α = 0.1 as the target and shows 95% binomial confidence intervals.Source: §A.2 · p. 33, Figure 16 · p. 33
  • Figure 15’s horizontal line marks the value of the 70th-largest component in the feature-layer scree plot.Source: Figure 15 · p. 33

A.3 Proofs of the main coverage guarantees

The proofs establish a general coverage result and derive Theorem 2 and Corollary 1 as special cases. They use convex optimization, symmetry, exchangeability, and the stated continuity condition.

A.3 Proofs of the main coverage guarantees

  • The proof strategy first establishes Theorem 3 for a generic function class and penalty, then specializes the choices to obtain Theorem 2 and Corollary 1.Source: §A.3 · p. 34
  • For Theorem 3, the proof examines the convex optimization problem’s first-order conditions and uses symmetric fitting and exchangeability in its coverage argument.The passage states that the second claim follows by exchangeability.Source: §A.3 · pp. 34–35
  • For nonnegative f, the proof lower-bounds an empirical term by zero to derive Theorem 3’s first inequality.Source: §A.3 · p. 35
  • Theorem 2’s first statement follows from Theorem 3 when the penalty is zero; its second statement is proved under continuous S given X.Source: §A.3 · p. 35
  • Corollary 1 follows by applying Theorem 2 to a function class formed from group indicators and coefficients.Source: §A.3 · p. 36

A.4 Proofs for RKHS functions

The RKHS proof section states moment conditions used for its bounds, including bounds involving the feature functions and the conditional score distribution.

A.4 Proofs for RKHS functions

  • The RKHS bounds assume moment conditions on weighted feature functions and require the score S to have a finite second moment.The stated conditions include E[|f(X_i)|^2] ≤ C_f E[|f(X_i)|] and a positive lower bound on E[|Φ(X_i)^Tβ|] for unit β.Source: §A.4 · p. 36

A.4.1 Proof of Proposition 1

The Proposition 1 proof builds on RKHS stability results, including stability with respect to both data changes and the linear coefficient. It combines these tools with moment and feature conditions in its bound.

A.4.1 Proof of Proposition 1

  • The proof’s main idea is RKHS regression stability, with separate lemmas for changing one data point and changing the linear coefficient.Source: §A.4.1 · pp. 36–37
  • Lemma 1 bounds the change in the RKHS fit when a subset of observations is swapped, assuming the kernel is bounded.Source: §A.4.1 · p. 36
  • The proof also controls the feature-linear term using weighted feature-moment conditions; the weighting is chosen to fit later calculations.The text notes that f = 1 makes the expectation a tail probability.Source: §A.4.1 · p. 38
  • The auxiliary assumptions include finite score moments, a bounded kernel, and bounds on weighted feature and linear-predictor moments.Source: §A.4.1 · p. 39
  • The Proposition 1 argument uses exchangeability, an ε-net over coefficient vectors, and a bounded conditional score density to complete its bound.Source: §A.4.1 · pp. 40–42

A.4.2 Proof of Proposition 2

This part develops proof techniques for the paper’s results, including concentration and uniform-control arguments and optimization-based proofs. It connects stationarity and fitting procedures to coverage and provides technical lemmas for the analysis.

A.4.2 Proof of Proposition 2

  • For Proposition 2, local population strong convexity and moment conditions support concentration arguments that use Rademacher bounds and a two-step peeling procedure.The first peeling step places the empirical minimizer near the population minimizer with high probability; the next tightens control of their distance.Source: §A.4.2 · pp. 42, 44, 45

A.5 Proofs for Lipschitz Functions

  • The proof for Lipschitz functions combines weighted covering-number bounds and fit-norm controls to show uniform concentration of the fitted equality indicator around its expectation.The argument uses boundedness and moment assumptions, exchangeability, symmetrization, and a tent-function smoothing step.Source: §A.5 · pp. 46–49

A.6 Proofs for Section 4

  • The proof of Proposition 4 uses the Lagrangian’s optimality conditions to establish that the dual prediction set has the same coverage properties as the original set.The stated result is coverage equivalence between ˆCdual(Xn+1) and ˆC(Xn+1).Source: §A.6 · p. 51
  • The Proposition 2 proof uses strong duality and KKT stationarity, with complementary slackness determining the dual variables by residual sign and the first-order condition yielding the second part.It connects the stationary condition to coverage; at zero residual, the corresponding dual variable may take any value in [−α, 1−α].Source: §A.6 · pp. 51–52

A.7 Two-sided fitting

  • The two-sided dual set uses lower- and upper-quantile dual solutions, while its randomized analogue independently randomizes the two thresholds.The unrandomized set uses levels α/2 and 1−α/2; the randomized set draws independent uniform thresholds over the specified intervals.Source: §A.7 · pp. 52–53
  • Two-sided prediction sets have the same coverage properties as their one-sided analogues, with an interpolation error for the unrandomized bound that vanishes for the randomized set.The theorem assumes a vector space of functions and existence of the relevant risk derivatives; the interpolation error is bounded by a term involving observations at the fitted quantile.Source: §A.7 · p. 53

A.8 Proofs of additional technical lemmas

  • The pinball loss is 1-Lipschitz with respect to the difference between its two input residuals.The proof checks the four sign cases and obtains the reverse inequality by symmetry.Source: §A.8 · p. 53
  • Under the stated feature moment conditions, Lemma 12 establishes a uniform feature-count bound with failure probability at most c′d^2/(n + 1)^2.Its proof applies Mendelson’s theorem after checking bounded Rademacher complexity and a lower bound on the probability of exceeding a threshold.Source: §A.8 · p. 54
Loading 2305.12616v4…