Source-linked AI summary
Conformal Inference for Online Prediction with Arbitrary Distribution Shifts
Isaac Gibbs, Emmanuel Candès
TL;DR
The paper studies online prediction sets under arbitrary distribution shifts, where existing procedures can overweight historical data and react slowly. It modifies adaptive conformal inference by tuning its step size over time, obtaining local coverage guarantees and robust adaptivity on stock-volatility and COVID-19 prediction tasks.
Problem
Online prediction sets need to remain useful when the data-generating distribution changes over time, but prior methods may overweight historical data and react slowly.
Method
The method modifies ACI with exponential expert reweighting to tune its gradient-descent step size over time.
Results
The method controls coverage locally over time and adapts well to distribution shifts in stock-market volatility and COVID-19 case-count prediction.
Takeaways & Limitations
The procedure can combine with baseline predictors producing point estimates or estimated quantiles without distributional assumptions.
Takeaways & Limitations
The procedure introduces two unknown weight parameters, η and σ, although the paper gives a procedure for choosing them without unknown quantities.
Abstract
from arXiv · showhide
We consider the problem of forming prediction sets in an online setting where the distribution generating the data is allowed to vary over time. Previous approaches to this problem suffer from over-weighting historical data and thus may fail to quickly react to the underlying dynamics. Here we correct this issue and develop a novel procedure with provably small regret over all local time intervals of a given width. We achieve this by modifying the adaptive conformal inference (ACI) algorithm of Gibbs and Candès (2021) to contain an additional step in which the step-size parameter of ACI's gradient descent update is tuned over time. Crucially, this means that unlike ACI, which requires knowledge of the rate of change of the data-generating mechanism, our new procedure is adaptive to both the size and type of the distribution shift. Our methods are highly flexible and can be used in combination with any baseline predictive algorithm that produces point estimates or estimated quantiles of the target without the need for distributional assumptions. We test our techniques on two real-world datasets aimed at predicting stock market volatility and COVID-19 case counts and find that they are robust and adaptive to real-world distribution shifts.
1 Introduction
The paper addresses online prediction sets when data distributions vary over time, extending conformal inference beyond exchangeable settings. It introduces an adaptive procedure that tunes ACI’s step size and evaluates it on real-world prediction tasks.
- Problem: Online prediction sets must use past observations and current covariates while accommodating time-varying data distributions.The setting allows both individual observations and subsequences to have distributions that vary over time.
- Background: Prediction sets transform black-box point or quantile estimates into uncertainty sets without requiring a specific predictive model.Conformal inference provides flexible methods for converting outputs from models such as neural networks or random forests into prediction sets.
- Limitations of prior work: Classical conformal methods typically require exchangeable, often i.i.d., training and testing data, limiting their applicability under distribution shift.Earlier extensions beyond exchangeability exist, but their applicability is described as limited.
- Limitations of prior work: ACI adapts prediction-set width to changing uncertainty, but its performance depends critically on specifying an appropriate step-size parameter.The optimal step size depends on the variation in the underlying data-generating mechanism.
- Contribution: The proposed method selects ACI’s step size through an alternative expert-selection scheme and controls coverage deviations locally over time.The paper bounds local coverage using the local rate of change of an underlying optimal target parameter.
- Evaluation: The method is evaluated on stock-market volatility and COVID-19 case-count prediction tasks, where it adapts to real-world dynamics.The authors report examples in which alternative methods show worse adaptivity to local dynamics.
2 Methodology
The methodology adapts conformal prediction to temporally changing data by learning both coverage parameters and the ACI step size online. DtACI emphasizes recent performance, supports updating predictive components over time, and provides local-time guarantees without several assumptions required by earlier theory.
- Conformal inference: Conformal inference forms prediction sets by comparing a test conformity score with scores from observed data.The standard guarantee requires exchangeability and permutation-invariant conformity scores.
- Conformal inference: Under temporal dependence, conformity scores need not be permutation invariant because treating all observations symmetrically may be inappropriate.The paper therefore allows scores that reflect the data’s temporal structure.
- Adaptive conformal inference: ACI learns the conformity-score quantile online by updating a parameter whose target is the value achieving the desired coverage.Its coverage can nonetheless arise from reactive corrections that make the parameter oscillate around the optimum.
- Adaptive conformal inference: The critical ACI limitation is choosing γ: its theoretically suitable scale depends on the unknown temporal variation of the optimal target parameter.A fixed γ can perform poorly when the magnitude of distribution shift changes over time.
- Theory and comparison: DtACI controls deviations from optimal parameters over every local time interval without assumptions on the conformity-score distribution or data-generating process.The method also permits these quantities to be updated over time, while MVP lacks comparable adaptivity to local changes.
- Dynamically-tuned adaptive conformal inference: DtACI runs ACI experts with candidate γ values in parallel and selects among them using exponentially reweighted historical losses.Its weighting scheme gives greater effective importance to recent observations than cumulative-history approaches such as AgACI.
- Dynamically-tuned adaptive conformal inference: DtACI is not completely parameter free because it introduces η and σ, although the paper provides a procedure for choosing them without unknown distribution-shift quantities.Unlike γ, a single choice of η and σ is reported to work across varied environments.
3 Coverage properties of DtACI
DtACI’s coverage guarantees are expressed through dynamic regret and hold locally over fixed-length intervals, with long-term exact coverage under decaying hyperparameters. In practice, constant or slowly varying hyperparameters are preferred because decaying values require stationary shift size and may introduce small bias.
- Local coverage guarantees: Theorem 3.1 applies to arbitrary intervals under conditions on candidate step sizes, their geometric spacing, and the mixing parameter σ.The stated assumptions include γk ≥ 1 + 1/|I|, adjacent ratios γi+1/γi ≤ 2, and σ ≤ 1/2.
- Local coverage guarantees: DtACI’s analysis bounds dynamic regret on every fixed-length interval and connects that regret to local coverage error.The bound depends on the interval’s local rate of change in the optimal target parameter.
- Local coverage guarantees: Coverage bounds transfer from pinball loss to distance from the optimal target α∗, and a Lipschitz condition converts this distance into local coverage deviation.The density lower bound on conformity-score variables supports the loss-to-target connection.
- Long-term coverage: If ηt and σt tend to zero, DtACI achieves exact long-term average coverage of 1 − α while increasingly weighting older historical data.This limiting behavior makes DtACI closer to AgACI and MVP; exact long-term coverage was previously established for MVP but only observed empirically for AgACI.
- Long-term coverage: Decaying ηt and σt are recommended only when the distribution-shift size is known to be stationary; constant or slowly varying values are preferred otherwise.With practical hyperparameter choices, the method can exhibit asymptotic coverage bias, although experiments find it sufficiently small for limited practical consequence.
- Algorithmic variant: The randomized procedure can be replaced by a deterministic alternative that retains the same regret bound, and both algorithms produce nearly identical empirical results.Subsequent experiments therefore report results using Algorithm 2 under the DtACI name.
4 Empirical results
The experiments compare DtACI with AgACI and MVP under stationary, smooth-shift, and jump-shift simulations, then evaluate stock-volatility and COVID-19 prediction. DtACI generally adapts more precisely to changing environments, while competitors can slightly outperform it in stationary settings.
- Simulated examples: The simulations use stationary, smoothly drifting, and discontinuously jumping mean trajectories, with larger shifts confined to the middle jump regime.In the jump setting, µt oscillates between −1.5 and 1.5 in the middle interval but between −0.075 and 0.075 in the first and third intervals.
- Simulated examples: DtACI offers greater adaptivity and more precise coverage than AgACI and MVP in non-stationary settings, with only slight degradation under stationarity.The comparison measures coverage gaps relative to DtACI across simulated trials.
- Stationary setting: In stationary data, MVP and AgACI slightly outperform DtACI because they converge more precisely to the single optimal α∗t value.DtACI cannot set its step-size exactly to 0 and therefore retains minor fluctuations around α∗t.
- Smooth shift setting: Under smooth shifts, AgACI and DtACI approximately track α∗t and perform nearly identically, whereas MVP adapts little and performs significantly worse.A single step-size choice is sufficient for good performance in the smooth-shift environment.
- Sharp shift setting: Under sharp shifts, AgACI reacts slowly to changes in shift magnitude, fails to reduce its step-size in the final regime, and consequently suffers large coverage errors.DtACI adjusts its mean step-size more effectively when the distribution shifts jump between regimes.
- Real-world prediction: Across four stocks, DtACI maintains local coverage near 1 − α = 0.9, while AgACI is nearly identical when shift sizes are relatively constant.DtACI’s local coverage properties nearly align with those of an i.i.d. Bernoulli(α) sequence, including for unnormalized scores.
- Reactivity diagnostics: Conditional coverage diagnostics show most error bars cover 0.9 and most bins have conditional coverage nearly equal to 0.9, arguing against pathological reactivity.The same qualitative result was obtained with unnormalized conformity scores.
A.1 Detailed description of multivalid conformal prediction
The modified MVP implementation selects prediction thresholds from candidate values using historical performance and randomized output rules. Its output is calibrated to be comparable with the αt values produced by DtACI and AgACI.
- Method: The modified MVP constructs prediction sets as {y : St(Xt, y) ≤ q}, selecting q from candidate thresholds using historical performance.The implementation removes covariate-space subset conditioning to make MVP comparable with DtACI and AgACI.
- Comparison: The value 1 − q output by MVP is directly analogous to the αt values output by DtACI and AgACI.This correspondence makes coverage comparisons across the three methods possible.
- Algorithm: MVP’s output is randomized among neighboring candidate thresholds according to performance-based quantities and associated probabilities.The algorithm includes special cases when all candidate criteria have the same sign.
A.2 Details of the block bootstrap for Section 4.2.2
The block-bootstrap procedure estimates uncertainty for empirical conditional coverage by resampling contiguous blocks of stock-return data. It reports empirical quantiles across bootstrap runs for each conditioning bin.
- Bootstrap setup: The bootstrap uses M = 100 samples and block size b = 100 to generate error bars for conditional-coverage figures.These choices are used for Figures 4.7 and A.5.
- Resampling: Each bootstrap replicate samples data blocks uniformly with replacement and reruns the Section 4.2.1 procedure on the resampled sequence.The blocks partition the stock-return sequence into contiguous segments.
- Uncertainty summaries: For every conditioning bin, the procedure reports the empirical 0.05 and 0.95 quantiles of conditional coverage across bootstrap replicates.These quantiles form the displayed error bars.
A.3 Proofs for Section 3.1
This section provides proofs for the main results in Section 3.1, including a version of the theorem that permits the learning-rate parameter η to vary over time.
- Proof coverage: The proofs cover Lemmas 3.1 and 3.2 and Theorem 3.1 stated in Section 3.1.The section begins by proving the results introduced earlier.
- Time-varying parameter: A modified version of Theorem 3.1 is also proved for settings where η varies over time.This extends the theorem’s stated parameterization to time-varying η.
- Role in the paper: The proof section supplies the theoretical support for the results presented in Section 3.1.Its stated scope is limited to those lemmas and theorem, plus the time-varying-η modification.
A.3.1 Proof of Lemma 3.1
The proof derives the lemma by combining exponential inequalities and then applying a logarithmic bound valid when σ ≤ 1/2.
- The argument first bounds the relevant exponential terms using exp(−x) ≤ 1 − x + x^2 and 1 − y ≤ exp(−y).
- Combining the resulting inequalities and taking logarithms yields the intermediate bound needed for the lemma.
- The final step uses σ ≤ 1/2 together with log(1 − σ) ≥ −2σ.
A.3.2 Proof of Lemma 3.2
The proof establishes boundedness of the adaptive quantities and applies an online convex-optimization theorem to obtain the lemma’s result.
- Because β_t ∈ [0, 1], the loss satisfies |ℓ_t(β_t, α_i^t)| ≤ 1 + γ_i.
- The proof then invokes Theorem 10.1 of Hazan (2019) using this loss bound.
A.3.3 Proof of Theorem 3.1
The proof combines the bounds from Lemmas 3.1 and 3.2, then handles the remaining expression through a two-case analysis involving the step-size parameters.
- Applying Lemma 3.1 to the first term and Lemma 3.2 to the second term produces the central inequality.
- The proof considers separately whether condition (9) holds.
- When condition (9) fails, the argument substitutes γ_1 for γ_i to complete the bound.
A.3.4 Results for Variable η
The variable-η analysis extends DtACI’s regret guarantee to time-varying step sizes, while the experiments examine its behavior on volatility and COVID-19 forecasting data.
- Theory: A time-varying η_t retains the fixed-η regret guarantee when its variability is sufficiently small.This permits adaptive η_t values to minimize the regret bound.
- Theory: The resulting dynamic regret has size O(·) when the variation in η_t is of order L.
- Assumptions: The small-variability assumption is motivated by time-series settings in which the relevant process has a stationary distribution, including hidden-Markov-model examples under mixing assumptions.
- Theory: Theorem A.1 applies the variable-η construction on any interval I of fixed length L under the conditions of Theorem 3.1.
- Experiments: The appendix figures compare coverage, local coverage gaps, conditional coverage, and the underlying stock-price and COVID-19 case-count series.
- Experiments: For stock-market volatility, empirical conditional coverages remain close to the target level across values of ᾱ_t, and variable-η results are identical to the fixed heuristic choice.