CS Paper Radar

The Price of Hard Coverage Constraints in Online Conformal Prediction

Mingrui Liu

cs.LG math.STstat.ML ·submitted 2026-11-17 12:01 UTC · v1

Abstract

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over $T$ prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is $Θ(\log T)$ for expected cost at a fixed time known in advance, $Θ(T^{1/3})$ for the largest expected cost over all fixed times up to $T$, and $Θ(\sqrt{T})$ for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

Closest papers

Nearest neighbours by meaning across the whole index.

The cost of enforcing long-run coverage: a phase transition in online conformal prediction

cs.LG math.STstat.ML ·2026-11-16 ·Yu Gui, Rina Foygel Barber, Cong Ma
theory similarity 0.74
Abstract

Consider an online prediction setting, where at each time, we are given a new feature vector and asked to provide a prediction interval or prediction set that will likely contain the corresponding response. In this setting, if the data points are i.i.d. (or more generally, exchangeable), conformal prediction provides a mechanism for building valid prediction sets around the output of any trained model, offering coverage probability $\geq 1-α$ at each time $t$. In practice, however, issues such as distribution drift, changepoints, or other challenges may cause violations of the i.i.d. assumption. In this adversarial setting, online conformal prediction methods can still offer guarantees on long-run empirical coverage. However, there is a trade-off between these two types of goals: enforcing tight constraints on long-run empirical coverage to protect against the adversarial setting can lead to unstable oscillations in the instantaneous training-conditional coverage in the i.i.d. setting. In this work, we seek best-of-both-worlds algorithms that aim to minimize cumulative error in instantaneous training-conditional coverage when in the i.i.d. setting, while also offering long-run empirical coverage guarantees in the adversarial setting. Specifically, consider a condition that requires long-run empirical coverage to deviate from the target level $1-α$ by at most $\mathcal{O}(T^{-β})$, for some $β\in[0,1]$. We prove that this family of conditions can be described with a phase transition. For $β\in[0,\frac{1}{2}]$, it is possible to construct algorithms satisfying such a constraint in the adversarial setting, while offering the same instantaneous coverage performance as split conformal prediction if the data is in fact i.i.d. On the other hand, for $β\in(\frac{1}{2},1]$, this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

0.09

A Black-Box Reduction from Regret to Multi-Level Coverage

cs.LG stat.ML ·2026-11-09 ·Tuo Liu, Edgar Dobriban, Francesco Orabona
theory similarity 0.65
Abstract

Online Conformal Prediction (OCP) sequentially constructs prediction sets whose average empirical coverage converges to a target level over time, for arbitrary, potentially adversarial datasets. In the multi-level setting, prediction sets are produced at $d$ coverage levels at once. Prior work argued for the use of online gradient descent with isotonic projections, which produces sets nested across levels, but with a $\sqrt{d}$ dependence in the per-level coverage convergence rate. Here, we both generalize and improve prior work. First, we show that isotonic projections can be used for the construction of multi-level online conformal prediction sets from \emph{any} online learning algorithm (not just gradient descent). Then, through a black-box reduction, we show that the linearized regret of the online algorithm itself automatically gives control over both per-level coverage and distributional consistency of multi-level predictions via Fenchel duality. Finally, by using the Weighted Interval Score, a standard scoring rule for assessing multi-level interval forecasts, we prove that these projections reduce both the size of the sets and their under-coverage. We study two instantiations of our theory, $p$-norm Online Mirror Descent and coordinate-wise Universal Portfolio methods, both improving the dependence on the number of levels to $\sqrt{\log d}$ for the multi-level OCP problem. Experiments on several datasets show favorable performance compared to baselines.

0.32

Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection

cs.LG stat.ML ·2026-09-22 ·Jing Li, Haibin Zhu
similarity 0.65
Abstract

Modern conformal forecasting systems often maintain several adaptive pipelines that differ in base forecasters, conformity scores, calibration windows, and update rules. Comparing them is difficult because coverage is a hard constraint, whereas efficiency should be optimized only among feasible pipelines. We formulate this problem as sequential inference for a stochastic constrained argmin. At each time, the target is the set of minimum-cost pipelines satisfying multiple prefix-average conditional miscoverage constraints. We introduce Coverage-Constrained Sequential Model Confidence Sets (CC-SMCS), which separate certifiably feasible, possibly feasible, and possibly constrained-optimal pipelines. Using simultaneous martingale confidence sequences, CC-SMCS projects a rectangular confidence region onto the constrained argmin and admits an exact closed-form rule. With probability at least $1-δ$, it contains every constrained-optimal pipeline simultaneously over all times. This finite-sample guarantee requires no stationarity or mixing assumptions and remains valid under data-dependent stopping. We also establish an impossibility result for safe certification at the coverage boundary and extend the construction to delayed multi-horizon feedback and outcome-dependent efficiency objectives.

0.32

Conformal Prediction at Performative Equilibrium: The Price of Performativity

cs.LG math.ST ·2026-11-03 ·Ahmed Mahrous, Roberto Di Pietro
theoryhot direction similarity 0.65
Abstract · 45 pages, including supplementary material

Conformal prediction gives finite-sample coverage when calibration and test points are exchangeable, but exchangeability can fail when deployment changes the data distribution. We study conformal prediction in performative settings, where the deployed predictor affects the data distribution, and seek prediction sets valid at performative equilibrium: coverage must hold under $D(f^\star)$ for a performatively stable predictor $f^\star$. Under total-variation $L$-sensitivity of the distribution map, we prove a phase transition at $L=1$. If $L \ge 1$, no finite-sample procedure can uniformly guarantee both equilibrium-valid coverage and nontrivial prediction sets. If $L<1$, the minimax excess miscoverage over informative procedures is $\widetildeΩ(1/((1-L)\sqrt{n}))$, implying a sample-complexity inflation of order $1/(1-L)^2$ for fixed excess miscoverage. Our main technical tool is a transfer theorem: any procedure returning a predictor within $\varepsilon$ of equilibrium yields equilibrium-valid coverage up to an additive $L\varepsilon$ term after split-conformal calibration. We instantiate the theorem with two retraining algorithms: a model-free method for discretizable classes and a parametric tail-averaged method that matches the $n$- and $L$-dependence of this rate up to logarithmic factors. Experiments, including semi-synthetic credit scoring, demonstrate the predicted threshold behavior and scaling laws.

0.36

Rolling Conformal Prediction in Sequential Model Training

cs.LG math.STstat.MEstat.ML ·2026-09-22 ·Chen Cheng, Ruiting Liang, Rina Foygel Barber
similarity 0.64
Abstract · 42 pages, 5 figures

We introduce Rolling Conformal Prediction (rolling-CP), a distribution-free predictive inference method for the setting of sequential model training. Specifically, given a data stream $(X_1,Y_1),(X_2,Y_2),\dots$, at each time $n$ the trained model may depend on the observed history $\{(X_i,Y_i)\}_{i<n}$. This setting arises naturally in modern sequential training, including one-pass training over massive datasets and continual fine-tuning or test-time adaptation of language models during deployment. Rolling-CP first calibrates each incoming observation against the current predictor and then rolls it into future training. In this way, we avoid the need for data splitting. Remarkably, although the models at times $n=1,2,\dots$ may have entirely different properties and accuracy levels, for exchangeable data it is nonetheless possible to establish a guarantee of marginal coverage, with a familiar universal factor-two guarantee (a worst case guarantee of $1-2α$ coverage, as compared to the target level $1-α$), without any assumptions of stability or any restrictions on the model training process. For i.i.d. data streams, we further prove high-probability training-conditional validity uniformly over time; under stability conditions, coverage guarantees sharpen towards $1-α$. Numerical experiments on sequential regression, multiclass SGD, and one-pass neural-network training further demonstrate the practical effectiveness of rolling-CP.

0.33

Conformal Prediction for Time-Dependent PDEs

cs.LG stat.ML ·2026-11-05 ·Joshua Stiller, Annika Schneider, Eyke Hüllermeier
top venuetheory similarity 0.63
Abstract · Accepted at NeurIPS 2026

Uncertainty quantification is crucial in scientific machine learning, where models inform safety-critical tasks such as flood forecasting, financial risk management, and thermal control in machines. Conformal prediction provides distribution-free coverage guarantees, but in time-dependent settings common to physics and engineering, these guarantees can break down, leading to systematic undercoverage. We study this problem in the context of surrogate models for time-dependent physical systems described by partial differential equations. We prove that in a function space setting, distributions at arbitrarily close times can be mutually singular, making exact coverage guarantees impossible. We further show that in discretized settings, the total variation distance between distributions often saturates exponentially fast with the grid resolution, mandating restrictions on the spatial discretization to ensure coverage. Finally, for certain settings, we show how to use principled weighted conformal prediction to obtain finite-sample coverage guarantees over growing time horizons.

0.59

Post-Hoc Conformal Prediction for Reliable Wireless Communications

eess.SP ·2026-09-22 ·Xin Su, Meiyi Zhu, Osvaldo Simeone, Carlo Fischione
similarity 0.62
Abstract

Deploying artificial intelligence (AI) in high-stakes wireless applications such as autonomous transportation requires guarantees of reliable operation. Such guarantees can often be obtained by designing systems that act on a set of predictions via conservative policies catering to all possible outcomes within the set. For instance, in location-based beam selection, a base station may identify a set of plausible locations and select a beam that ensures high capacity over the set. The miscoverage probability of the set with respect to the true outcome (e.g., the true user location) then quantifies the outage probability, while the size of the set determines the final performance or resource budget (e.g., the transmission capacity). Conventional conformal prediction (CP) applies when the target miscoverage level is prescribed in advance. However, in practical wireless systems, prediction sets may instead be selected under prescribed operational constraints, requiring the resulting miscoverage probability to be quantified post hoc. This paper develops a formal statistical framework for the data-driven selection of prediction sets that provides a reliable estimate of the resulting miscoverage probability. The methodology builds on backward CP and probably approximately correct CP, yielding distribution-free reliability guarantees on the miscoverage probability. We apply the framework on three distinct wireless applications: narrowband interference detection, near-field localization, and codebook-based beam identification. Numerical results validate the reliability guarantees and show that the proposed post-hoc conformal methods achieve accuracy comparable to the naive probability-based approach across all considered applications.

0.39

Adaptive Calibration of Day-Ahead Flexibility Reserve Requirements Under Distribution Shift

eess.SY ·2026-10-12 ·Napoleon Costilla-Enriquez, Yang Weng, Miguel A. Ortega-Vazquez
theory similarity 0.62
Abstract

The increasing integration of variable renewable generation introduces weather-driven variability and uncertainty into power-system operations. System operators manage the resulting deviations between day-ahead forecasts and real-time net load by scheduling upward and downward flexibility reserves. These requirements have traditionally been set using simple deterministic rules. Newer data-driven methods tailor reserves to forecasts and operating conditions. However, their reliability may deteriorate when conditions depart from the historical data. We address this limitation with a sequential framework that updates day-ahead reserve requirements as operating outcomes become available. Within this framework, Adaptive Conformal Inference targets the frequency of insufficient reserve, whereas Rolling Risk Control targets expected uncovered deviation, the mean residual beyond the scheduled reserve. We prove finite-horizon bounds on realized miscoverage and capped uncovered-deviation loss. We test the framework on real ERCOT data in a chronological deployment simulation that respects operational timing: outcomes from one day first affect the reserve schedule two days later. Training and validation use 2022--2023 data; the uninterrupted test covers 2024--2025. Coverage calibration achieves approximately 90% coverage, with upward and downward miscoverage near 5%. Risk calibration brings expected uncovered deviations close to their budgets while using 5.3% less reserve than the uncalibrated requirements. The framework thus produces adaptive reserve requirements that provably control the selected reliability metrics over finite horizons without assuming stationarity or exchangeability.

0.22