Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction

• URL: http://arxiv.org/abs/2607.26577v1
• Date: Wed, 29 Jul 2026 07:56:59 GMT
• Title: Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction
• Abstract summary: Adaptive conformal inference (ACI) of Gibbs and Cands and its variants are the standard approach to online conformal prediction under distribution shift.<n>Existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets.<n>We consider a unified online learning framework that simultaneously controls absolute, non-optimal coverage violation and prediction-set efficiency.
• Score: 5.533296779866529
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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 \emph{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 \emph{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.

Related papers

• Beyond Marginal Validity: Finite-Sample Guarantees for Localized Conformal Prediction [25.59471163637912]
  Conformal prediction endows arbitrary black-box predictors with finite-sample, distribution-free marginal coverage.<n>We provide finite-sample guarantees for the realized localized set that jointly control conditional validity and oracle efficiency.<n>We analyze data-split learned scores: when the score targets a pivotal score, uniform local guarantees decompose into fixed-score calibration and uniform score-estimation errors.
  arXiv  Detail & Related papers  (2026-08-06T15:59:57Z)
• Conformal Reliability: A New Evaluation Metric for Conditional Generation [62.761166941396844]
  Conditional generative models have recently remarkable success in various applications.<n>We propose a novel evaluation metric called reliability based on prediction set at a pre-specified confidence level.<n>We introduce Conformal ReLiability (CReL), a framework that can (i) construct a prediction set and (ii) accurately optimize the reliability score within the constructed prediction set.
  arXiv  Detail & Related papers  (2026-05-29T03:52:44Z)
• Efficient Online Conformal Selection with Limited Feedback [14.326282143930769]
  We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one success'' is identified.<n>We show that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid and efficient.
  arXiv  Detail & Related papers  (2026-05-14T15:22:46Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Error-quantified Conformal Inference for Time Series [55.11926160774831]
  Uncertainty quantification in time series prediction is challenging due to the temporal dependence and distribution shift on sequential data.<n>We propose itError-quantified Conformal Inference (ECI) by smoothing the quantile loss function.<n>ECI can achieve valid miscoverage control and output tighter prediction sets than other baselines.
  arXiv  Detail & Related papers  (2025-02-02T15:02:36Z)
• On the Role of Surrogates in Conformal Inference of Individual Causal Effects [0.0]
  We introduce underlineSurrogate-assisted underlineConformal underlineInference for underlineEfficient IunderlineNdividual underlineCausal underlineEffects (SCIENCE)<n>SCIENCE is a framework designed to construct more efficient prediction intervals for individual treatment effects (ITEs)<n>It is applied to the phase 3 Moderna COVE COVID-19 vaccine trial.
  arXiv  Detail & Related papers  (2024-12-16T21:36:11Z)
• The Benefit of Being Bayesian in Online Conformal Prediction [7.713245413733777]
  We study the online construction of confidence sets given a black-box machine learning model.<n>By converting the target confidence levels into quantile levels, the problem can be reduced to predicting the quantiles of a sequentially revealed data sequence.
  arXiv  Detail & Related papers  (2024-10-03T15:04:47Z)
• Conformal Thresholded Intervals for Efficient Regression [9.559062601251464]
  Conformal Thresholded Intervals (CTI) is a novel conformal regression method that aims to produce the smallest possible prediction set with guaranteed coverage.<n>CTI constructs prediction sets by thresholding the estimated conditional interquantile intervals based on their length.<n>CTI achieves superior performance compared to state-of-the-art conformal regression methods across various datasets.
  arXiv  Detail & Related papers  (2024-07-19T17:47:08Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.