math.STNov 16, 2026

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

Authors: Yu Gui, Rina Foygel Barber, Cong Ma

Organizations: Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · Department of Statistics, University of Chicago

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 ≥1−α\geq 1-α at each time tt. 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−α1-α by at most O(T−β)\mathcal{O}(T^{-β}), for some β∈[0,1]β\in[0,1]. We prove that this family of conditions can be described with a phase transition. For β∈[0,12]β\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 β∈(12,1]β\in(\frac{1}{2},1], this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

Figures & tables

Explore similar work

CardsList
  1. The Price of Hard Coverage Constraints in Online Conformal Prediction

    Nov 17, 2026Mingrui LiuConformal PredictionSet-Valued Prediction