Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection

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.

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.

Conformal prediction provides a principled framework for uncertainty quantification with finite-sample coverage guarantees. While recent work has extended conformal prediction to online and sequential settings, existing methods typically focus on a single coverage level and do not ensure consistency across multiple confidence levels. In many real-world applications, such as weather forecasting, macroeconomic prediction, and risk management, different users operate under heterogeneous risk tolerances and require calibrated uncertainty estimates across a range of coverage levels. In such settings, it is desirable to produce prediction sets corresponding to different coverage levels that are nested and valid simultaneously. In this paper, we propose two novel online conformal prediction methods that output nested prediction sets across a range of coverage levels, enabling simultaneous uncertainty quantification across the entire risk spectrum. Beyond interpretability, jointly estimating multiple coverage levels is known to improve statistical efficiency in classical quantile regression by enforcing non-crossing constraints and sharing information across quantiles. Our approaches leverage an online optimization perspective with small regret that translates to quantile estimation error control while enforcing nestedness of prediction sets. Empirical results on synthetic and real-world datasets, including applications in forecasting tasks with heterogeneous risk requirements, demonstrate that our method achieves stable coverage across all levels, strictly nested prediction sets, and improved efficiency compared to existing online conformal baselines.