PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Conformal Inference Under Distribution Shift

Isaac Gibbs, Emmanuel Candès

arXiv:2106.00170v3stat.MEcs.LGstat.ML

TL;DR

The paper addresses conformal prediction when data distributions vary over time, violating the exchangeability assumption used by standard methods. It introduces adaptive conformal inference, which continually estimates a shifting calibration parameter around black-box predictions. ACI achieves correct long-term coverage without assumptions on the data-generating distribution and performs robustly under visible shifts in two real-world domains.

  • Problem

    Conformal inference commonly relies on exchangeability, but many applications have nonstationary data distributions and require uncertainty estimates for high-stakes predictions.

  • Method

    ACI wraps black-box point-prediction or quantile-estimation methods and continuously updates a single parameter using observed miscoverage.

  • Results

    ACI achieves the correct coverage frequency over long time intervals irrespective of assumptions on the data-generating distribution.

  • Takeaways & Limitations

    Adaptive conformal inference provides prediction sets robust to changes in the marginal data distribution while remaining compatible with modern machine-learning predictors.

  • Takeaways & Limitations

    The theory is limited to a single data-generating model with a quantile function fixed across time, and experiments cover only two domains.

Abstract

from arXiv · show

We develop methods for forming prediction sets in an online setting where the data generating distribution is allowed to vary over time in an unknown fashion. Our framework builds on ideas from conformal inference to provide a general wrapper that can be combined with any black box method that produces point predictions of the unseen label or estimated quantiles of its distribution. While previous conformal inference methods rely on the assumption that the data points are exchangeable, our adaptive approach provably achieves the desired coverage frequency over long-time intervals irrespective of the true data generating process. We accomplish this by modelling the distribution shift as a learning problem in a single parameter whose optimal value is varying over time and must be continuously re-estimated. We test our method, adaptive conformal inference, on two real world datasets and find that its predictions are robust to visible and significant distribution shifts.

1 Introduction

The paper addresses the failure of exchangeability-based conformal coverage when data distributions shift, introducing adaptive conformal inference for online prediction sets. It combines black-box predictions with calibration while targeting long-run coverage under arbitrary data-generating processes.

  • High-stakes black-box predictions require tools that quantify uncertainty because wrong decisions can be costly.
  • Online prediction sets use past covariate-response pairs and current covariates to target coverage of at least 100(1 −α)% over time.
  • Standard conformal methods generally guarantee marginal coverage only when training and test data are exchangeable.
  • Nonstationary data distributions arise when market behavior responds to legislation, world events, or deployment in new environments.
  • Adaptive conformal inference tracks a single shifting parameter and can wrap black-box point-prediction or quantile-estimation algorithms.
  • Conformity scores measure how well a candidate response agrees with a fitted regression model, including point-prediction and quantile-based constructions.
  • A calibration-set score quantile accepts candidate y when S(Xt, y) ≤ˆQ(1 −α), producing the conformal prediction set.
  • Exchangeability makes the test score rank uniform, yielding marginal coverage; randomization can provide exact P(Yt ∈ˆCt) = 1 −α.

2 Adapting conformal inference to distribution shifts

ACI adapts conformal prediction to shifting distributions by repeatedly updating the calibration level from observed miscoverage. Experiments on market volatility show robust local coverage, while the step size controls adaptivity versus stability.

  • 2 Adapting conformal inference to distribution shifts: Under distribution shift, the score and quantile functions should be regularly re-estimated to reflect recent observations.
  • 2 Adapting conformal inference to distribution shifts: ACI updates αt online using prior miscoverage events, decreasing it after undercoverage and increasing it after overcoverage.
  • 2.1 Choosing the step size: The update step size γ trades adaptability against stability: larger γ responds more strongly to shifts but increases αt volatility.
  • 2.1 Choosing the step size: Theorem 4.2 supports choosing larger γ in environments with greater distributional shift; the experiments use γ = 0.005 for stable yet responsive trajectories.
  • 2.2 Real data example: predicting market volatility: ACI predicts realized volatility from past returns using a GARCH(1,1) point-prediction model and rolling five-year fitting windows.
  • 2.2 Real data example: predicting market volatility: Prediction intervals use conformity scores, their quantile function, and recursively updated αt initialized at α = 0.1.
  • 2.2 Real data example: predicting market volatility: Across four selected stocks, ACI performed well while the non-adaptive method clearly failed; the stocks came from twelve examined stocks.
  • 2.2 Real data example: predicting market volatility: ACI’s local coverage frequencies stay within i.i.d. Bernoulli variation, whereas the non-adaptive method makes large excursions from the 0.9 target.

3 Related Work

Prior work addresses a fixed calibration-to-test distribution shift, whereas this paper estimates an optimal calibration parameter online as the environment changes continuously.

  • Earlier methods reweight i.i.d. calibration data from P0 for a single test distribution P1 using their likelihood ratio.
  • ACI estimates the optimal α∗ satisfying M(α∗) = α and operates online while the distribution shifts continuously over time.

4 Coverage guarantees

Adaptive conformal inference provides distribution-free long-run coverage, while sharper guarantees under shifting environments depend on initialization and assumptions about the shift. In a hidden Markov model, its error concentration reflects both adaptive feedback and temporal dependence in the environment.

  • 4.1 Distribution-free results: Adaptive conformal inference achieves the target long-run coverage frequency without constraints on the data-generating distribution.The guarantee holds over long time intervals under the stated conditions on α1 and the fitted quantile functions.
  • 4.1 Distribution-free results: With probability one, the adaptive parameter αt remains within [−γ, 1 + γ] for every time t.The update prevents αt from decreasing further once it is below zero or increasing further once it exceeds one.
  • 4.1 Distribution-free results: Improved large-time coverage bounds require appropriate initialization and simplifying assumptions about the data-generating process.The paper presents these assumptions as representative of expected behavior rather than exact descriptions of every real-world setting.
  • 4.2 Performance in a hidden Markov model: In a hidden Markov model, the environment is a Markov chain and observations are conditionally independent given the environment state.The analysis further assumes a stationary joint process for the adaptive parameter, environment, and error.
  • 4.2.2 Large deviation bound for the errors: Theorem 4.1 bounds long-run deviations from target miscoverage by separating adaptive-feedback dependence from dependence caused by Markovian environment persistence.Adaptive feedback induces negative correlation, whereas persistent states can induce positive dependence when statewise errors are biased.
  • 4.2.2 Large deviation bound for the errors: When distribution shifts are small and fitted quantiles provide reasonable statewise coverage, the average realized marginal coverage is close to the target.The shift size is measured through changes in the state-specific optimal parameter α∗_At, with the bound also depending on regularity and approximation terms.

5 Impact of St St St(·) on the performance

Adaptive conformal inference depends on the conformity score: scores that are closer to stationary support better coverage, while poorly normalized scores produce larger deviations from the target.

  • Conformity-score design strongly affects adaptive conformal inference’s coverage properties.The performance is controlled by how the score behaves under distribution shift.
  • Adaptive conformal inference can combine with any conformity score S_t(·) and quantile function Q̂_t(·), including methods designed to shorten prediction intervals.Prediction-set length also depends directly on the fitted regression model’s quality.
  • Coverage depends on how close S_t(X_t,Y_t) is to stationary because α*_t corresponds to its 1 − α quantile.Thus, score normalization can affect the stability of the target being tracked.
  • Normalized score S̃_t leads to wider swings away from the target 0.9 coverage level in stock-volatility predictions.Figure 2 compares adaptive and non-adaptive methods using S̃_t against an i.i.d. Bernoulli(0.1) sequence.
  • Increasing γ can partially mitigate the poor coverage behavior caused by the less stationary score S̃_t.A larger step size provides greater adaptivity to the algorithm.

6 Real data example: election night predictions

The election-night experiment applies conformalized quantile regression to county-level Biden vote totals ordered to reproduce the east-to-west reporting shift. Adaptive conformal maintains approximate 90% local coverage, whereas the fixed method develops large troughs during time-zone changes.

  • The experiment predicts Biden’s 2020 county-level vote totals from demographic covariates across approximately 3000 counties.Covariates include ethnicity, age, sex, median income, and education; counties are observed sequentially during election night.
  • Counties are ordered by time zone, with eastern counties first and Hawaiian counties last, to reproduce the observed reporting bias.Within each time zone, counties are ordered uniformly at random.
  • The non-adaptive method fails to maintain the desired 90% coverage, with large troughs during time-zone changes.The comparison uses local coverage over the most recent 300 counties.
  • The adaptive method maintains approximate 90% coverage across all time points.Its local deviations are comparable to those observed in Bernoulli sequences.

7 Discussion

The discussion identifies delayed or batched responses, restricted theoretical settings, step-size selection, and limited experimental domains as open problems for adaptive conformal inference.

  • The methods require Y_t to be revealed at every time point, excluding delayed-response and large-batch settings.
  • Theoretical results in Section 4.2 are limited to one data-generating model and a quantile function Q̂_t(·) fixed across time.
  • Choosing γ currently relies on heuristic guidance based on distribution-shift size rather than an adaptive procedure without prior knowledge.
  • The experimental evaluation covers only two domains, leaving protection against a wider variety of real-world shifts unresolved.

A.1 Connection to online learning

The adaptive update can be viewed as online gradient descent on a convex pinball loss, but standard regret does not capture its goal of tracking a moving optimal parameter.

  • The update adjusts α_t using the previous prediction sets’ empirical miscoverage frequency.
  • The same update is obtained by applying online gradient descent to the pinball loss ℓ(α_t,β_t).The gradient form yields α_t + γ(α − err_t).
  • Convexity of the pinball loss places this update within a well-studied class of online-learning algorithms.
  • Standard regret is inadequate because it does not capture α_t adaptively tracking the moving target α*_t.The paper therefore develops alternative theoretical tools.

A.2 Stock prices

Figure 4 presents the daily open prices for the four stocks examined in Section 2.2.

  • Figure 4 shows daily open prices for the four stocks considered in Section 2.2.

A.3 Trajectories of αt

Figures 5–8 show realized trajectories of αt for stock-volatility and election-night forecasting under two update rules.

  • Figures 5 and 6 show realized αt trajectories for stock-volatility prediction under updates (2) and (3).Update (3) uses ws ∝ 0.95t−s.
  • Figures 7 and 8 show realized αt trajectories for election-night forecasting under updates (2) and (3).Update (3) uses ws ∝ 0.95t−s.

A.4 Coverage for additional stocks

The supplied passages combine additional market-volatility coverage material with theoretical conditions and concentration results for adaptive conformal inference.

  • Figure 9 reports local coverage for adaptive conformal, fixed-α non-adaptive conformal, and an i.i.d. Bernoulli(0.1) sequence.The figure covers market-volatility prediction for eight additional stocks or indices; dotted lines show average coverage and the black line marks 1 − α = 0.9.
  • Under finite-state, positive-transition assumptions, the joint Markov chain {(αt, At)}t∈N has a unique stationary distribution.The argument uses irreducibility and finiteness of the state space, with αt restricted to a bounded lattice.
  • The HMM-based bound decreases with the size of distribution shift, unlike the naive bound, which increases as the shift decreases.The comparison concerns the dependence of the bounds on ϵ1.
Loading 2106.00170v3…