PaperlayerView exact revision on arXiv

Source-linked AI summary

The limits of distribution-free conditional predictive inference

Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, Ryan J. Tibshirani

arXiv:1903.04684v2math.ST

TL;DR

The paper addresses the gap between marginal coverage, which can fail for subgroups, and exact conditional coverage, which is impossible distribution-free without assumptions. It explores approximate and restricted conditional coverage. Broad approximate conditional coverage is essentially no better than a trivial marginal construction in expected interval length, while restricted classes such as similarity-based sets remain a possible direction.

  • Problem

    Marginal coverage can be inaccurate for particular subgroups, while exact distribution-free conditional coverage is impossible without assumptions on P.

  • Method

    The paper analyzes approximate conditional coverage and studies restricted versions that require guarantees only over selected classes of subgroups, such as metric balls.

  • Results

    Broad approximate conditional coverage is essentially no better than obtaining the guarantee through stronger marginal coverage, in terms of expected prediction-interval length.

  • Takeaways & Limitations

    Meaningful distribution-free conditional guarantees require weaker or restricted notions than coverage over every sufficiently large subgroup.

  • Takeaways & Limitations

    The restricted-coverage procedure may produce intervals that are too wide, and its supremum may be computationally difficult to calculate efficiently.

Abstract

from arXiv · show

We consider the problem of distribution-free predictive inference, with the goal of producing predictive coverage guarantees that hold conditionally rather than marginally. Existing methods such as conformal prediction offer marginal coverage guarantees, where predictive coverage holds on average over all possible test points, but this is not sufficient for many practical applications where we would like to know that our predictions are valid for a given individual, not merely on average over a population. On the other hand, exact conditional inference guarantees are known to be impossible without imposing assumptions on the underlying distribution. In this work we aim to explore the space in between these two, and examine what types of relaxations of the conditional coverage property would alleviate some of the practical concerns with marginal coverage guarantees while still being possible to achieve in a distribution-free setting.

1 Introduction

The paper seeks prediction guarantees that are more individualized than marginal coverage but remain distribution-free, despite exact conditional coverage being impossible without assumptions. It examines approximate and restricted relaxations of conditional coverage.

  • Problem setup: Predictive inference uses training pairs and a new feature vector to construct a prediction interval for the test response.The interval is a subset of R intended to contain the new response value.
  • Marginal versus conditional coverage: Conditional coverage instead requires coverage at least 1 −α for almost every fixed feature value, but distribution-free exact guarantees are impossible in meaningful finite-length procedures.At almost all nonatomic feature values, the expected prediction-interval length is infinite.
  • Marginal versus conditional coverage: Marginal coverage averages accuracy over test features, so inaccurate predictions for an entire subgroup can be offset by higher coverage elsewhere.For example, a method could have 0% accuracy for patients under 25 while maintaining 95% average coverage.
  • Relaxing conditional coverage: Approximate conditional coverage requires at least 1 −α coverage for every subgroup containing at least a δ fraction of the population.With α = 0.05 and δ = 0.1, every subgroup comprising at least 10% of the population must receive at least 95% coverage.
  • Relaxing conditional coverage: The paper finds that approximate conditional coverage is no better than obtaining it through stronger marginal coverage, whose intervals become extremely wide when δ is small.Theorem 2 establishes this comparison in terms of expected interval length.
  • Restricted relaxations: Restricted conditional coverage considers only selected sets, such as metric balls representing patients similar to the individual of interest.This restriction is motivated by the view that arbitrary subgroups may contain highly dissimilar patients.

2 Background

The background contrasts split conformal prediction's distribution-free marginal guarantee with the impossibility of exact conditional coverage. It motivates approximate conditional guarantees while noting that asymptotic approaches rely on smoothness assumptions.

  • Split conformal prediction: Split conformal prediction achieves distribution-free marginal coverage under exchangeability, without assumptions on the data distribution beyond that requirement.The i.i.d. setting is a special case of exchangeability.
  • Split conformal prediction: Split conformal partitions the sample, fitting a regression function on one portion and calibrating prediction-interval width from residuals on the other.The calibration quantile is computed from the residuals in the second portion.
  • Split conformal prediction: The method's marginal guarantee is unaffected by the regression algorithm, and some settings yield intervals asymptotically no wider than the best possible oracle interval.Thus marginal distribution-free prediction need not incur overly wide intervals in those settings.
  • Impossibility of conditional coverage: Marginal coverage can leave entire regions of test points with inaccurate predictions, motivating guarantees conditional on the test feature rather than averaged over it.The resulting question is whether conditional coverage can be achieved without unnecessarily enlarging intervals.
  • Impossibility of conditional coverage: Without assumptions on P, exact distribution-free conditional coverage forces infinite expected interval length at almost all nonatomic feature values.This makes the guarantee impossible to attain meaningfully.
  • Asymptotic conditional coverage: Asymptotic conditional coverage can use smoothness assumptions and vanishing bandwidths, whereas this paper targets finite-sample distribution-free guarantees without such assumptions.The distinction separates the reviewed asymptotic literature from the paper's setting.

3 Approximate conditional coverage

Approximate conditional coverage interpolates between marginal and exact conditional guarantees, but distribution-free methods cannot achieve it meaningfully beyond a stringent marginal-coverage construction. A lower bound shows this construction is essentially optimal in interval length, yet typically produces impractically wide intervals.

  • Approximate conditional coverage: Approximate conditional coverage approaches exact conditional coverage as δ tends to zero and recovers marginal coverage when δ = 1.These equivalences define the relaxation’s relationship to the two endpoint guarantees.
  • The inadequacy of reducing to marginal coverage: Lemma 1 shows that any method with (1−αδ)-MC also satisfies (1−α, δ)-CC.The result obtains approximate conditional coverage by imposing a more stringent marginal miscoverage rate.
  • The inadequacy of reducing to marginal coverage: For small δ, the marginal-coverage construction generally yields extremely wide intervals, such as 99.5%-coverage intervals instead of 95% when α = 0.05 and δ = 0.1.The paper therefore concludes that this naive reduction is not satisfactory in practice.
  • Hardness of approximate conditional coverage: The main theorem proves that distribution-free (1−α, δ)-CC remains impossible to attain meaningfully and establishes a lower bound on interval width.The bound applies to distributions whose marginal feature distribution has no atoms.
  • Hardness of approximate conditional coverage: The lower bound implies that applying marginal coverage at level 1−αδ is essentially optimal in interval length, although it is usually much wider than intervals designed with known P.For small constant δ, LP(1−αδ) is generally substantially larger than the length needed when the distribution is known.

4 Restricted conditional coverage

The paper relaxes approximate conditional coverage by restricting the collection of feature subsets, then studies when split conformal prediction can achieve useful intervals. The collection’s VC dimension determines whether restricted conditional coverage is impossible or yields nearly optimal intervals.

  • Restricted conditional coverage: Approximate conditional coverage becomes less stringent when guarantees are required only over a restricted collection of measurable feature subsets.Examples include sufficiently probable ℓ2 balls for local coverage and predefined patient subgroups.
  • Split conformal construction: A split conformal construction attains approximate conditional coverage, and it also satisfies the stronger exchangeable version of the guarantee.The construction is based on split conformal prediction; the coverage proofs require exchangeability rather than specifically i.i.d. sampling.
  • VC-dimension hardness: If the set class is sufficiently complex, with VC_a.e.(X) ≥ 2n + 2, conditional coverage cannot improve on the trivial lower bound.The lower bound matches the one obtained by requiring marginal coverage at a stricter level; analogous results for ordinary approximate conditional coverage require VC_a.e.(X) ≫ n^2.
  • VC-dimension hardness: If VC(X) ≪ δn / log^2(n), split conformal prediction produces nearly optimal-length intervals under a location-family model.The result identifies low VC dimension as a regime where restricted conditional coverage can be meaningfully attained.
  • Location-family efficiency: For a location-family model with a consistent mean estimate, the proposed interval satisfies restricted conditional coverage while asymptotically matching the oracle interval length.This holds as n0, n1 → ∞ under the stated conditions on the collection’s VC dimension and the model assumptions.

5 Discussion

The paper finds that unrestricted approximate conditional coverage is too strong for meaningful distribution-free intervals, while restricting the subgroup class can permit nontrivial intervals. It leaves the most meaningful classes and efficient computation as open questions.

  • (1−α, δ)-conditional coverage is too strong because it forces prediction intervals to be too long for meaningful distribution-free procedures.The main result establishes a lower bound on interval length under this property.
  • Restricting coverage to subgroups X ∈ X with probability at least δ allows nontrivial prediction intervals when X is sufficiently limited.
  • The paper seeks approximate conditional guarantees that improve personalized accuracy concerns while remaining achievable without distributional assumptions.
  • Meaningful choices of subgroup classes X remain an open question for restricted approximate conditional coverage.
  • Computing predictive intervals for the split conformal method may be seriously challenging for nearly any class X.
  • Adaptive tolerance levels δ(P) for selected distributions P are another proposed direction for relaxing approximate conditional coverage.

A Proof of main impossibility result (Theorem 2)

The proof strengthens approximate conditional coverage from feature-defined subgroups to arbitrary measurable events jointly involving features and responses. Extreme conditional-response events then drive the impossibility argument.

  • Lemma 3 extends (1−α, δ)-conditional coverage from feature-only events X × R to measurable events B defined jointly in (X, Y).
  • The lemma applies to every measurable set B with P(B) ≥ δ when the marginal distribution PX has no atoms.
  • The proof constructs B from responses in the extreme conditional tails outside the δ/2 and 1−δ/2 conditional quantiles.
  • This tail-based construction formalizes why approximate conditional coverage can impose strong constraints on prediction intervals.

A.2 Proof of Theorem 2

The theorem proof combines coverage inequalities, integration identities, convexity, and Jensen’s inequality to derive the required interval-length bound and complete the impossibility result.

  • The argument represents prediction intervals through fixed coverage and residual quantities, including the marginal miscoverage rate of CP,s(x).
  • The proof uses Fubini’s theorem repeatedly to relate conditional coverage quantities to their marginal counterparts.
  • The proof establishes s⋆ ≥ 1−α > 0, with s⋆ ≤ 1, and selects c ∈ [0,1] accordingly.
  • Jensen’s inequality and convexity of α ↦ LP(1−α) provide the key inequality used to combine the proof bounds.
  • The resulting bound proves the theorem.

A.3 Proof of Lemma 3

The proof of Lemma 3 constructs a finite approximation using samples from B and its complement, then compares sampling with and without replacement. This transfers coverage from feature-defined sets to arbitrary joint events.

  • The construction draws M samples from the conditional distributions on B and its complement, assuming PX has no atoms so feature values are distinct almost surely.
  • Sampling indices without replacement from the constructed finite population yields data that are i.i.d. from P after marginalizing over the population draw.
  • Sampling with replacement instead produces Q(L)^{n+1}, a discrete distribution over the constructed points.
  • When M is large relative to n, collisions are unlikely and the total variation distance between the two sampling schemes is bounded by n^2/M.
  • The constructed feature set X(L) corresponds exactly to B under Q(L) and has probability δ′ ≥ δ.
  • Applying the assumed conditional coverage guarantee to X(L), then taking M arbitrarily large, completes the lemma.

B.2 Proof of Theorem 3

The proof establishes conditional coverage on any measurable set X with probability at least δ by exploiting exchangeable residuals among held-out points falling in X.

  • For a fixed distribution P and set X with P_X(X) ≥ δ, the procedure analyzes the residual of the test point conditionally on X_{n+1} ∈ X.
  • The held-out indices I collect training points whose covariates lie in X, so |I| equals the corresponding count N_{n1}(X).
  • A multiplicative Chernoff bound controls the probability that too few held-out covariates fall in X.
  • Conditioning on I and X_{n+1} ∈ X makes the relevant residuals exchangeable, allowing the test residual to be compared with the smallest residual values.
  • The resulting conditional exceedance probability is bounded by α^{-1} after marginalizing over I.

B.3 Proof of Theorem 4

Theorem 4 is proved by extending the earlier construction to arbitrary measurable prediction-error events B, using exchangeability under a conditionally generated distribution.

  • Lemma 4 reduces the theorem to distributions with continuous covariate marginals and events B having probability at least δ.
  • The proof samples n+1 points conditional on B and n+1 conditional on B^c, then combines them using a random permutation and Bernoulli variables.
  • After conditioning on the constructed data L, the resulting n+1 observations are exchangeable under the conditional distribution.
  • Applying the conditional coverage property to X(L) yields the lemma and, by the preceding reduction, Theorem 4.
  • A set X(L) is selected so that membership corresponds to the event B, with probability P(B)=δ′ ≥ δ under the conditional distribution.

B.4 Proof of Theorem 5

The proof of Theorem 5 establishes uniform high-probability bounds for the selected set class and empirical quantiles, then uses these bounds to verify the theorem’s defining conditions.

  • The argument conditions on the initial n0 training points, treating the fitted model as fixed while bounding randomness from the n1 holdout points.
  • The proof targets two uniform bounds and combines concentration events that hold with probability at least 1 − 1/n1.
  • The selected class bX_{n1} is sandwiched between classes defined by lower and upper probability thresholds, establishing condition (23).
  • The empirical quantile bq_{n1}(X) is defined through an order statistic of the observed count and is bounded using concentration inequalities.
  • Combining the verified bounds establishes both conditions and completes the theorem’s proof.
  • A VC-dimension reduction lemma relates thresholded subsets in R^d × R to the original set class, supporting the required uniform concentration.

B.5 Proof of Corollary 1

The corollary follows by comparing the oracle interval with the estimated interval through quantile bounds under the paper’s location-family and density assumptions.

  • The proof begins from the oracle interval and bounds its relevant quantile for every set X with P_X(X) ≥ δ−.
  • The location-family assumption is used to express the relevant quantities through the error distribution and its quantile.
  • The remaining discrepancies are bounded deterministically and then controlled with high probability.
  • Theorem 5 supplies the high-probability control needed for this quantile comparison.
  • Under the density assumptions on ε,α, the bounds combine to complete the corollary.
Loading 1903.04684v2…