Search papers, labs, and topics across Lattice.
This paper addresses online conformal prediction for non-stationary data streams by minimizing training-conditional cumulative regret, focusing on abrupt and smooth distribution shifts. They propose a split-conformal algorithm with drift detection for pre-trained non-conformity scores, achieving minimax-optimal regret. They also develop a full-conformal algorithm with drift detection for online training, relying on model stability instead of permutation symmetry, and establish non-asymptotic regret guarantees matching the minimax lower bound under certain conditions.
Forget permutation symmetry, stability is the new key to unlocking online conformal prediction under evolving environments.
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.
