Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction

Online conformal prediction is essential for uncertainty quantification in streaming data, yet existing methods like Adaptive Conformal Inference (ACI) often focus solely on long-run coverage. This paper addresses three critical limitations of current approaches: the masking of persistent miscoverage through signed error cancellation, the lack of explicit control over prediction-set size (efficiency), and the reliance on static benchmarks that fail to account for distribution shifts.

The author introduces a unified framework that treats online conformal prediction as an optimization problem. By defining a dynamic benchmark—the optimal threshold that would have been chosen in hindsight—the paper derives simultaneous guarantees for coverage and efficiency across three distinct settings:

1. Adversarial Setting: Uses the standard ACI update, showing it acts as projected online gradient descent on the pinball loss, providing guarantees without requiring convexity or distributional assumptions.
2. Stochastic Setting: Proposes a sliding-window quantile tracker to handle non-stationary distributions, establishing minimax optimal rates for tracking the oracle quantile.
3. Covariate-Dependent Setting: Develops a partitioned ACI algorithm (HP-ACI) that tracks a function-valued oracle threshold, allowing for conditional coverage that adapts to changing feature-response relationships.

This work provides the first rigorous framework for balancing the stability-adaptivity tradeoff in online conformal prediction. By proving that one can simultaneously minimize cumulative coverage violations and prediction-set size, the paper offers a principled way to ensure that prediction sets remain both valid and informative, even when the underlying data-generating mechanism evolves over time. This is particularly relevant for high-stakes applications like finance, autonomous systems, and healthcare where both reliability and precision are required.