PaperlayerView exact revision on arXiv

Source-linked AI summary

Conformal prediction beyond exchangeability

Rina Foygel Barber, Emmanuel J. Candes, Aaditya Ramdas, Ryan J. Tibshirani

arXiv:2202.13415v5stat.ME

TL;DR

Conformal prediction needs exchangeability and algorithmic symmetry for its usual guarantees, but deployment data can drift and favor recent observations. The paper introduces weighted quantiles and randomization to handle these violations, retaining exchangeable-case coverage while reducing coverage loss in nonexchangeable settings. Experiments include electricity and election forecasting.

  • Problem

    Conformal prediction’s validity depends on exchangeable data and symmetric fitting algorithms, assumptions often violated by distribution drift and settings where recent observations matter more.

  • Method

    The paper generalizes conformal procedures with weighted residual distributions and a randomization technique supporting nonsymmetric algorithms.

  • Results

    The methods maintain approximately the desired 90% coverage on the electricity data while unweighted conformal prediction shows undercoverage.

  • Takeaways & Limitations

    The framework provides robustness to distribution drift and other exchangeability violations while preserving existing coverage guarantees when data are exchangeable.

  • Takeaways & Limitations

    Choosing weights optimally, and even defining optimality, remains an open question; poorly chosen small weights can produce uninformatively wide intervals.

Abstract

from arXiv · show

Conformal prediction is a popular, modern technique for providing valid predictive inference for arbitrary machine learning models. Its validity relies on the assumptions of exchangeability of the data, and symmetry of the given model fitting algorithm as a function of the data. However, exchangeability is often violated when predictive models are deployed in practice. For example, if the data distribution drifts over time, then the data points are no longer exchangeable; moreover, in such settings, we might want to use a nonsymmetric algorithm that treats recent observations as more relevant. This paper generalizes conformal prediction to deal with both aspects: we employ weighted quantiles to introduce robustness against distribution drift, and design a new randomization technique to allow for algorithms that do not treat data points symmetrically. Our new methods are provably robust, with substantially less loss of coverage when exchangeability is violated due to distribution drift or other challenging features of real data, while also achieving the same coverage guarantees as existing conformal prediction methods if the data points are in fact exchangeable. We demonstrate the practical utility of these new tools with simulations and real-data experiments on electricity and election forecasting.

1 Introduction

Conformal prediction traditionally relies on exchangeable data and symmetric fitting algorithms, assumptions often violated by drift, dependence, or time-varying relevance. The paper generalizes conformal methods using weighted procedures and new randomization, with guarantees that quantify coverage loss and recover standard validity under exchangeability.

  • Motivation: Conformal prediction calibrates predictive intervals for black-box models, with guaranteed coverage under exchangeable data.Split conformal uses empirical quantiles of holdout residuals to construct intervals.
  • Motivation: Distribution drift, temporal or spatial dependence, and other applied phenomena can substantially violate exchangeability and cause undercoverage.In the electricity experiment, standard conformal prediction intervals fell far below the target 90% coverage level over a substantial time span.
  • Motivation: Standard methods rely on both exchangeability of the data and symmetry of the model-fitting algorithm.Symmetry preserves exchangeability after fitting; nonsymmetric algorithms may instead emphasize recent observations.
  • Contributions: The paper generalizes split conformal, full conformal, and jackknife+ to handle nonexchangeable data and nonsymmetric regression algorithms.The procedures use weighted residual distributions and a new randomization approach while recovering original variants with symmetric algorithms.
  • Guarantees: Under exchangeability, the weighted procedures retain the same coverage guarantees as standard conformal methods, while suitable weights can reduce coverage gaps under drift.Geometrically decaying weights can downweight older observations when distances from the test distribution decrease over time.
  • Guarantees: Coverage loss is bounded by weighted total variation distances between the original and swapped data or residual distributions, without assumptions on the joint data distribution.The stronger residual-based bound can be tighter, especially in high-dimensional settings.

2 Background and related work

Conformal prediction provides distribution-free predictive inference, but standard guarantees rely on exchangeable data and symmetric model-fitting algorithms. Background methods include split, full, and jackknife+-style approaches, while prior nonexchangeable work addresses specific distribution-shift settings.

  • Conformal prediction methods rely on exchangeability of the data and symmetry of the underlying model-fitting algorithm.
  • Split conformal prediction: Split conformal constructs prediction intervals around a pre-trained model using residuals from a holdout set.The method computes an empirical quantile of holdout residuals and adds and subtracts it from the new prediction.
  • Full conformal prediction: Full conformal avoids data splitting and guarantees target coverage under exchangeability and a symmetric algorithm.Its potential statistical-efficiency benefit comes with higher computational cost because the model may need to be refit for each hypothesized response.
  • Split conformal prediction: Split conformal also guarantees distribution-free predictive coverage, but sample splitting can reduce accuracy by shrinking the effective holdout set.With n total labeled points, a practical split may use n/2 for training and n/2 for calibration.
  • Related methods: Jackknife+ and CV+ use cross-validation-style procedures to trade some of full conformal’s statistical efficiency for greater computational efficiency.Jackknife+ requires fitting leave-one-out models.
  • Related work: Prior reweighting work handles covariate shift using likelihood-ratio weights, requiring covariate-shift validity and known or accurately approximated high-dimensional ratios.The present work is described as methodologically distinct, with neither approach subsuming the other.

3 Nonexchangeable conformal prediction

The paper extends conformal prediction beyond exchangeable data by using fixed weights and weighted quantiles, then accommodates nonsymmetric algorithms through a random tag-swapping procedure. The framework covers weighted, changepoint-adaptive, autoregressive, and other ordered-data models.

  • 3.1 Weighted methods: The new methodology allows nonexchangeable data while initially retaining a symmetric model-fitting algorithm.It then generalizes the method to nonsymmetric algorithms.
  • 3.1 Weighted methods: Fixed weights assign greater trust to observations believed to come from nearly the same distribution as the test point.For temporal drift, weights may increase for more recent observations.
  • 3.1 Weighted methods: Weighted quantiles replace equal-weight quantiles in the split and full conformal procedures, recovering the original methods when all weights equal one.The weights are normalized over the n calibration points and the test point.
  • 3.2 Enhanced predictions with nonsymmetric algorithms: Nonsymmetric algorithms can use fixed tags to encode weights, time or spatial location, or the ordering of observations.Swapping tagged observations may change the fitted model, so symmetry in the untagged data points is not required.
  • 3.2 Enhanced predictions with nonsymmetric algorithms: The framework includes weighted regression, changepoint adaptation, and autoregressive models that use ordered or recent observations differently.Weighted least squares is one example of the supported weighted-regression algorithms.
  • 3.2 Enhanced predictions with nonsymmetric algorithms: To maintain predictive coverage with a nonsymmetric algorithm, the method randomly swaps the tags of one sampled data point and the test point.The sampled index follows the normalized weights and is drawn independently of the data; split conformal needs no such modification because its pre-fitted model is trivially symmetric.

4 Theory

The paper establishes coverage guarantees for nonexchangeable conformal prediction, bounding coverage loss using distributional discrepancies and showing robustness under mild exchangeability violations. The results also recover standard guarantees under exchangeability while highlighting trade-offs in weight selection and limits when distribution shift is severe.

  • Coverage guarantees: The nonexchangeable full conformal method satisfies a coverage guarantee under a sequence-based fitting algorithm, and the same result holds for nonexchangeable split conformal.The theory defines residuals from the full data sequence and treats split conformal as a special case.
  • Coverage guarantees: The coverage gap is bounded by a weighted sum involving total variation distances between the joint data distribution and distributions formed by swapping observations.The bound does not require an assumption on the joint distribution of the n + 1 points, but its usefulness depends on selecting fixed weights that make the bound small.
  • Robustness: If the effective sample size is large, mild exchangeability violations lead only to mild undercoverage or overcoverage.The relevant condition is that the normalized test-point weight ˜w_n+1 = 1/(w_1+···+w_n+1) is small.
  • Limitations: Coverage direction cannot be determined without further assumptions: increasing conditional variance can cause undercoverage, whereas decreasing conditional variance can cause overcoverage.If the test residual is larger than typical training residuals, undercoverage may result; the reverse pattern can produce overcoverage.
  • Exchangeable setting: Under exchangeability, fixed weighting causes no coverage loss, and the methods can handle nonsymmetric algorithms that existing conformal methods cannot.With a symmetric algorithm and unit weights, the proposed procedures reduce to usual conformal or jackknife+ methods.
  • Robustness: For independent data, the bounds provide robustness to mild violations of exchangeability and help explain why standard conformal methods can work on real data.The paper also gives examples where the coverage gap is small despite data that are not nearly exchangeable, including gradual drift and post-changepoint data.
  • Weight selection: Choosing very low weights reduces effective sample size and can widen prediction intervals, while optimal weight selection remains an open question.Setting all training weights to zero yields an uninformative interval equal to the entire real line, despite eliminating the coverage gap.
  • Limitations: The guarantee may be uninformative when the test distribution bears no resemblance to the training data, because neither the bound nor other methods ensures valid coverage without further assumptions.The paper suggests qualitative knowledge of distribution drift can guide weights, but determining coverage adaptively remains open.

5 Experiments

Experiments compare original and nonexchangeable conformal methods in simulations, electricity forecasting, and election forecasting. Weighting improves coverage under distribution changes, while nonsymmetric weighted least squares can produce narrower intervals without undercoverage.

  • Experimental design: The experiments compare original full conformal prediction with nonexchangeable variants using residual weights and, in one variant, weighted least squares.NexCP+LS uses least squares with decaying weights, while NexCP+WLS also uses the same decaying weights in weighted least squares.
  • 5.1 Simulations: The simulations include i.i.d. data, changepoints, and gradual distribution drift, using target coverage 1 −α = 0.9 and averages over 200 independent replications.Each method is run after a 100-point burn-in with training points 1 through n and test point n + 1.
  • 5.1 Simulations: All three methods achieve coverage ≈90% for i.i.d. data, whereas under changepoints and distribution drift the proposed methods maintain approximately the desired coverage and CP+LS undercovers.CP+LS drops sharply after changepoints and declines gradually as drift grows; NexCP+WLS briefly overcovers after changepoints because older residuals retain weight.
  • 5.1 Simulations: NexCP+WLS constructs narrower prediction intervals than CP+LS under changepoints and distribution drift while avoiding undercoverage.NexCP+LS produces wider intervals because it uses the same fitting algorithm as CP+LS while correcting its coverage loss; weighted least squares yields more accurate fitted models.
  • 5.2 Electricity data set: On the original ELEC2 data, CP+LS undercovers while both proposed methods reach nearly 90% coverage; on permuted data, all methods remain close to 90%.The original data track electricity usage and pricing over 2.5 years, while permutation restores exchangeability.

6 Proofs

The proofs establish standard conformal coverage through exchangeability and show why weighted quantiles and nonsymmetric algorithms require new arguments. The nonexchangeable analysis uses randomized index swapping and weighted control of unusually large residuals.

  • Background proof: Exchangeability of residuals depends on both exchangeable data and a symmetric fitting algorithm.Under these conditions, the fitted model and residuals remain symmetric across data points.
  • Background proof: Standard full conformal coverage follows by identifying noncoverage with the test point being among the largest residuals.At most an α fraction of points are strange, and exchangeability makes the test point uniformly representative.
  • Challenges for the new algorithms: Unequal weights break the symmetry needed by the original proof, even when the residuals themselves are exchangeable.Weighted quantiles are not generally symmetric functions of the residual vector.
  • Challenges for the new algorithms: Nonsymmetric algorithms can also destroy residual exchangeability because fitted models treat tagged training points differently.This issue arises even when the underlying data points are exchangeable.
  • Nonexchangeable proof: The new proofs address both nonsymmetric fitting and nonexchangeable data by combining randomized index permutations with weighted strange-point bounds.Noncoverage implies strangeness of a randomized index, while the weighted fraction of strange points is bounded by α.

7 Discussion

The discussion frames nonexchangeable conformal prediction as a generalization of split, full, and jackknife+ methods. It extends them to weighted calibration, tagged nonsymmetric algorithms, and broader nonconformity scores while retaining useful special cases.

  • Discussion: The paper modifies conformal prediction to handle nonsymmetric regression algorithms and weighted residual distributions under deviations from exchangeability.The proposed procedures provide coverage guarantees without assumptions on the joint data distribution, with gaps controlled by distributional discrepancies.
  • Discussion: The proposed framework motivates application-specific choices of tags and weights to downweight observations considered far from the target setting.The authors identify custom algorithm and weighting design as a direction for improving efficiency and robustness.
  • General nonconformity scores: General nonconformity scores extend the nonexchangeable split and full conformal constructions beyond real-valued residuals.The same theoretical result holds because the proof does not fundamentally rely on residual scores.
  • Jackknife+: Nonexchangeable jackknife+ uses leave-one-out models, randomized index selection, and optional weights, with the unweighted method recovered by setting every weight to one.Its nonsymmetric extension assigns the test point’s tag to a swapped training point.
  • Jackknife+: Jackknife+ offers a computational-statistical compromise, but its worst-case exchangeable guarantee is only 1 − 2α despite typically near-target practical coverage.CV+ generalizes the construction through K-fold cross-validation.

B.3 Theory

The nonexchangeable jackknife+ theory bounds coverage loss using total variation distances between residual matrices under swapped data configurations. A more interpretable data-level bound may be substantially looser.

  • Residual construction: Nonexchangeable jackknife+ constructs a residual matrix from leave-two-out models and uses it to analyze coverage under index swaps.The residual object differs from full conformal’s residual vector because jackknife+ compares pairs of leave-one-out fits.
  • Coverage guarantee: Theorem 5 bounds the coverage gap by a weighted sum of total variation distances between swapped jackknife+ residual matrices.The bound measures how the residual construction changes when a data point is exchanged with the test point.
  • Coverage guarantee: A corresponding bound using total variation distances between the data distributions is more interpretable but can be substantially looser.The residual-level bound is therefore potentially sharper for assessing jackknife+ coverage.
  • Relation to cross-conformal: Jackknife+ is specifically residual-based, whereas cross-conformal prediction supports arbitrary nonconformity scores.The two methods are closely related, but their score flexibility differs.

C Huber-robustness of conformal prediction

The Huber-robustness analysis studies conformal prediction when training points may be adversarially contaminated relative to a target-distributed test point. Under stronger independence and symmetry assumptions, multiplicative coverage bounds result.

  • Huber contamination: The contamination model treats most observations as drawn from the target distribution and an ε fraction as arbitrarily corrupted.The test point is required to come from the target distribution, while training points may follow mixtures with adversarial components.
  • Huber contamination: The mixture distance dmix measures the smallest contamination proportion needed to express one distribution as a mixture involving another.It is asymmetric and is not a metric.
  • Multiplicative bounds: Under independent data and a symmetric algorithm, weighted split, full, and jackknife+ methods admit multiplicative contamination-based coverage bounds.The theorem applies to nonexchangeable full conformal and includes split conformal as a special case.
  • Multiplicative bounds: α/(1 − ε) replaces the nominal noncoverage level α under ε-Huber contamination for split or full conformal prediction.The inflation is multiplicative, approximately α + αε, so the gap is proportional to α.
  • Comparison of bounds: The multiplicative bounds require independent data and symmetric algorithms, unlike the earlier additive bounds.Because dmix can exceed total variation substantially, the additive bounds may be tighter in some settings.
  • Cross-conformal extension: Nonexchangeable cross-conformal prediction accommodates arbitrary nonconformity scores and has the same guarantee as nonexchangeable jackknife+.With the standard regression score, its prediction set is contained within the jackknife+ interval.

E.1 Proof of Lemma 1

The proof constructs coupled versions of the data and uses their marginal equivalence to relate total variation distances involving the original and swapped samples.

  • A maximal coupling provides a joint distribution for paired random variables used to compare the original and modified samples.The construction is introduced through the maximal coupling theorem.
  • Independent draws form Z, while coupled variables are arranged so that the resulting samples have the same marginal distribution.The proof explicitly defines Z from independent draws and establishes matching marginals for the coupled constructions.
  • The swapped construction implies (Z′′)i has the same distribution as Zi.
  • The total variation distance between Z and Zi equals the distance between the coupled variables Z′ and (Z′′)i.This identity transfers the comparison to the coupling framework.

E.2 Proof of Theorem 3

The proof establishes Theorem 3 by reducing the relevant coverage statement to total variation comparisons and bounding the effect of swapping observations through normalized residual directions.

  • Reduction to full conformal: Nonexchangeable split conformal is treated as a special case of nonexchangeable full conformal, so proving the full-conformal result suffices.
  • Coverage characterization: The coverage event is characterized using residuals, and distinct residual values identify the relevant maximizing index.The proof invokes the distinctness assumption and defines the index attaining the maximum over a candidate set.
  • Algebraic bound: Terms in the remaining sum vanish except for cases involving the maximizing index or the new observation, yielding the required inequality.The proof handles k=k∗, k=n+1, and all other indices separately.
  • Total variation control: The argument bounds dTV(R, Ri) by dTV(U, Ui), separating each residual vector into a unit direction and its norm.Independence of direction and norm justifies removing the common norm from the total variation comparison.
  • Directional distribution: Conditional on the design subspace, U is uniform on the corresponding unit sphere, enabling density calculations for comparing U and Ui.The proof uses the joint and marginal densities together with determinant and matrix-norm bounds.
  • Exchangeable jackknife+ comparison: The exchangeable jackknife+ argument uses permutation invariance of its residual matrix and a deterministic bound on the strange-point set.Failure of coverage implies that the new point belongs to this set, which yields the desired probability bound.

E.4.2 Proof of Theorem 5

The proof of Theorem 5 represents nonexchangeability through independent contamination indicators, then applies weighted strange-point bounds and conditional conformal guarantees.

  • Weighted strange points: A weighted strange-point lemma bounds the weighted fraction of strange points by 2α.
  • Contamination representation: The data are generated using independent Bernoulli contamination indicators based on total variation distances from the target distribution.Uncontaminated observations and the new point are drawn independently from the target distribution.
  • Procedure-specific bounds: The resulting bounds control noncoverage for both nonexchangeable conformal prediction and nonexchangeable jackknife+.The proof derives separate bounds for the two procedures and identifies the jackknife+ argument as nearly identical.
  • Conditional conformal argument: For conformal prediction, conditioning on contamination indicators produces modified weights and a correspondingly adjusted significance level.The conditional total variation terms vanish for uncontaminated observations, simplifying the bound.
  • Conditional jackknife+ argument: The same conditioning and reweighting strategy verifies the jackknife+ bound, with the weighted error contribution equal to 2α times a summed distance term.The proof states that the next-to-last step follows the full-conformal argument exactly.

E.5.1 Proof of Lemma 3

Lemma 3 bounds a ratio involving weighted independent Bernoulli variables by analyzing equal-parameter cases, arbitrary weights, and an induction argument.

  • Lemma statement: The lemma concerns independent Bernoulli variables with probabilities pi and coefficients ai in [0, 1], allowing an additional nonnegative constant c.The claimed inequality compares an expected ratio with the ratio formed from expected weighted sums.
  • Extension to c≥0: A reduction using added variables extends the lemma from c=0 to arbitrary c≥0.The augmented vectors ˜p and ˜a transform the general claim into an application of the original lemma.
  • Case 1: The proof first handles equal coefficients and equal probabilities, including the binomial special case and the c=0 bound.The argument notes that the c=0 case is a known bound and treats p1=0 separately.
  • Case 2: When probabilities are equal but coefficients vary, conditioning on the total coefficient count reduces the weighted Bernoulli sum to a binomial distribution.Concavity and Jensen’s inequality then provide the required upper bound.
  • Case 3: For arbitrary coefficients and probabilities, the proof orders probabilities, introduces auxiliary Bernoulli variables, and applies induction on n.Random weights reduce the problem to the preceding equal-probability case.
  • Conclusion: The three cases together establish the claimed inequality.

F Simulations for split conformal and jackknife+

The simulations compare nonexchangeable extensions of split conformal and jackknife+ with their original methods across i.i.d., changepoint, and distribution-drift settings. Under violations of exchangeability, the extensions retain coverage closer to target, while weighted least squares yields narrower intervals.

  • Methods: The experiments compare SplitCP+LS, NexSplitCP+LS, NexSplitCP+WLS, and analogous Jack+LS, NexJack+LS, and NexJack+WLS methods.Split conformal assigns odd indices to training and even indices to holdout; jackknife+ methods are defined analogously.
  • Experimental protocol: After a 100-point burn-in, inference is run at each time n = 100, . . . , N −1 using observations 1, . . . , n and test point n + 1.Results are averaged over 200 independent simulation replications.
  • Results: For i.i.d. data in Setting 1, all three versions of each method have comparable performance.The comparison concerns mean coverage and prediction interval width.
  • Results: For changepoint and distribution-drift data, original methods lose coverage substantially, whereas nonexchangeable split conformal and jackknife+ remain closer to target coverage.Tables 4 and 5 summarize split conformal and jackknife+ results, respectively.
  • Results: Weighted least squares produces narrower prediction intervals in the changepoint and distribution-drift settings.This is the reported advantage of the nonsymmetric algorithm in the simulations.

G Election data set description

The election-data preparation combines county demographic covariates with 2016 and 2020 election vote counts. After matching and merging the sources, the analysis uses 3076 counties divided between training and test sets.

  • Covariates: County predictors include proportions of residents in specified race categories and the percentage of individuals with a bachelor’s degree or higher.The education measure uses Census data collected during 2015–2019.
  • Covariates: The study uses 2019 estimates for some covariates because that was the most recent year with available data.The source passage notes that Census figures can sometimes be updated later.
  • Covariates: For 2016 covariates, the researchers almost exclusively used figures published by 2016, while noting that some entries may have changed afterward.This preserves the distinction between information available at the time and later revisions.
  • Election data: 2016 vote counts come from MIT Election Data and Science Lab, while 2020 counts come from Leip.The passage identifies separate sources for the two election years.
  • Sample construction: Matching covariate and vote-count data cover 3111 counties; merging both election years leaves 3076 counties, with 1119 for training and 1957 for testing.The merged sample is the dataset used for the election analysis.
Loading 2202.13415v5…