We study online conformal prediction for non-stationary data streams subject to unknown distribution drift. While most prior work studied this problem under adversarial settings and/or assessed performance in terms of gaps of time-averaged marginal coverage, we instead evaluate performance through training-conditional cumulative regret. We specifically focus on independently generated data with two types of distribution shift: abrupt change points and smooth drift. When non-conformity score functions are pretrained on an independent dataset, we propose a split-conformal style algorithm that leverages drift detection to adaptively update calibration sets, which provably achieves minimax-optimal regret. When non-conformity scores are instead trained online, we develop a full-conformal style algorithm that again incorporates drift detection to handle non-stationarity; this approach relies on stability - rather than permutation symmetry - of the model-fitting algorithm, which is often better suited to online learning under evolving environments. We establish non-asymptotic regret guarantees for our online full conformal algorithm, which match the minimax lower bound under appropriate restrictions on the prediction sets. Numerical experiments corroborate our theoretical findings.
Figures & tables
Figure 1: The case with a single change point at t0 . (Left) pointwise coverage P(st≤q) vs. t ; (right) block coverage error cvg-errq⋆(1,t) vs. t along with a detection threshold σ .
Figure 2: Schematic illustration of a case with smooth, oscillating distribution shifts. (Left) pointwise coverage P(st≤q) vs. t ; (right) block coverage error cvg-errq⋆(1,t) vs. t .
Figure 3: Cumulative regret and calibration quantiles under four data-generating settings. Top row: cumulative regret trajectories. Bottom row: calibration-quantile evolution; the black dashed curve indicates an approximation to the ground-truth quantile obtained via repeated simulations at each time point. Across settings, ACI exhibits a clear stepsize trade-off: ACI with large constant stepsizes adapts quickly but produces volatile quantile updates and suboptimal performance under stationarity, whereas ACI with smaller or decaying stepsizes yields more stable updates at the cost of slower adaptation to distributional changes. In comparison, DriftOCP is stable within stationary time segments and adapts rapidly to distribution shifts, yielding consistently controlled regret. Curves are averaged over 20 runs; shaded bands indicate ±1 standard deviation.
Figure 4: Online conformal prediction with different score constructions. Top row: prediction-interval width over time. Bottom row: local coverage rate computed with a rolling window of 100 steps; the horizontal line marks the target level 1−α=0.9 . Vertical dashed lines indicate change points at t=3333 and t=6667 . Columns correspond to the four settings (well-specified vs. misspecified model, each under mean vs. variance drift). The adaptive-score method (online SGD) yields noticeably shorter intervals and more stable coverage under variance drift, whereas the pretrained-score method is sensitive to a mismatch between the pretraining and test covariate distributions. The model-free baseline ( st=∣Yt∣ ) is in general conservative and produces wide prediction intervals; it is also sensitive to distribution shift, exhibiting undercoverage at change points. Curves are averaged over 20 runs, with shaded bands indicating ±1 standard deviation.
Conformal prediction has emerged as a powerful framework for constructing distribution-free prediction sets with guaranteed coverage assuming only the exchangeability assumption. However, this assumption is often violated in online environments where data distributions evolve over time. Several recent approaches have been proposed to address this limitation, but, typically, they slowly adapt to distribution shifts because they update predictions only in a forward manner, that is, they generate a prediction for a newly observed data point while previously computed predictions are not updated. In this paper, we propose a novel online conformal inference method with retrospective adjustment, which is designed to achieve faster adaptation to distributional shifts. Our method leverages regression approaches with efficient leave-one-out update formulas to retroactively adjust past predictions when new data arrive, thereby aligning the entire set of predictions with the most recent data distribution. Through extensive numerical studies performed on both synthetic and real-world data sets, we show that the proposed approach achieves coverage close to the nominal level while reducing predictive interval width by up to approximately 30% compared to existing online conformal prediction methods, demonstrating improved statistical efficiency alongside faster adaptation.
Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the signed long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a fixed predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.
Uncertainty quantification is crucial in safety-critical systems, where decisions must be made under uncertainty. In particular, we consider the problem of online uncertainty quantification, where data points arrive sequentially. Online conformal prediction is a principled online uncertainty quantification method that dynamically constructs a prediction set at each time step. While existing methods for online conformal prediction provide long-run coverage guarantees without any distributional assumptions, they typically assume a full feedback setting in which the true label is always observed. In this paper, we propose a novel learning method for online conformal prediction with partial feedback from an adaptive adversary-a more challenging setup where the true label is revealed only when it lies inside the constructed prediction set. Specifically, we formulate online conformal prediction as an adversarial bandit problem by treating each candidate prediction set as an arm. Building on an existing algorithm for adversarial bandits, our method achieves a long-run coverage guarantee by explicitly establishing its connection to the regret of the learner. Finally, we empirically demonstrate the effectiveness of our method in both independent and identically distributed (i.i.d.) and non-i.i.d. settings, showing that it successfully controls the miscoverage rate while maintaining a reasonable size of the prediction set.