Accelerating Conformal Prediction via Approximate Leave-One-Out

Conformal prediction methods enjoy strong theoretical and empirical predictive inference performance, provided the data is exchangeable and is treated symmetrically during training. However, these assumptions are impractical in many settings, such as time series, where temporal dependence violates exchangeability and it is preferable to use predictors that leverage dependence by treating data asymmetrically. Recent work shows that split conformal prediction is robust to these issues, but sample splitting can reduce accuracy, motivating the study of methods that do not rely on data splitting in the time series setting. In this work, we show that the vanilla leave-one-out jackknife can suffer arbitrary loss of coverage even in canonical time series models with mild temporal dependence. As a remedy, we propose a modification tailored to such settings, which we term the leave-a-window-out (LWO) method, and show that it can achieve valid coverage provided that the model-fitting procedure satisfies mild stability properties. Our proofs are based on quantifying the degree to which the data departs from cyclic exchangeability, which we introduce new coefficients to measure. Experiments on time series demonstrate that our method often enjoys valid coverage when the vanilla jackknife fails to cover, while producing much narrower intervals than split conformal prediction.

Full conformal prediction is a framework that implicitly formulates distribution-free confidence prediction regions for a wide range of estimators. However, a classical limitation of the full conformal framework is the computation of the confidence prediction regions, which is usually impossible since it requires training infinitely many estimators (for real-valued prediction for instance). The main purpose of the present work is to describe a generic strategy for designing a tight approximation to the full conformal prediction region that can be efficiently computed. Along with this approximate confidence region, a theoretical quantification of the tightness of this approximation is developed, depending on the smoothness assumptions on the loss and score functions. The new notion of thickness is introduced for quantifying the discrepancy between the approximate confidence region and the full conformal one.

This article considers an online version of conformal inference, called adaptive conformal inference [ACI] and introduced by Gibbs and Candès (2021): prediction sets are issued sequentially, after observing features and before the outcomes are revealed. These sets are evaluated both in terms of validity (the fraction of rounds where the outcome was lying in the prediction set) and efficiency (the average lengths of the prediction sets). The two criteria point to different directions (validity favors larger sets). We also target a wide range of scenarios, with exchangeable data and arbitrary data (lack of any stochastic guarantees) as two extremes. A series of existing strategies for ACI typically guarantee that empirical coverage converges to the desired level for arbitrary sequences, but they generally lack simultaneous efficiency guarantees. To provide a unified study, we first formulate ACI as a repeated two-player game with finite action sets and vector-valued payoffs encoding validity and efficiency. Building on this reformulation, we introduce a strategy based on Blackwell approachability and on its opportunistic extension by Bernstein et al. (2014) that ensures validity while adapting the efficiency of the prediction intervals to the underlying degree of stochasticity of the opponent player. The resulting guarantee is "best of many worlds": it recovers the relevant efficiency guarantees in exchangeable and adversarial settings, and provides guarantees in intermediate settings that arise in typical applications such as the forecasting of time series.