betaFeedback

WorksMathematics

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

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.

Introduction

Consider an online uncertainty quantification problem in which each data point consists of a feature Xt∈XX_t \in\mathcal{X} and a response Yt∈YY_t \in\mathcal{Y}. For each time t≥1t \ge1, let Ct\mathcal{C}_t denote any prespecified construction that maps from an observed data stream to a prediction set for the data point at time tt. Concretely, we write

Ct(Xt)=Ct(Xt;(X1,Y1),…,(Xt−1,Yt−1))⊆Y(1)\mathcal{C}_t(X_t) = \mathcal{C}_t\left(X_t;(X_1,Y_1),\ldots,(X_{t-1},Y_{t-1})\right) \subseteq\mathcal{Y} \tag*{(1)}

to denote the prediction set at time tt, when trained on data points (X1,Y1),…,(Xt−1,Yt−1)(X_1, Y_1), \ldots, (X_{t-1}, Y_{t-1}). The current outcome YtY_t is not available when the set is constructed. Throughout this paper, we use the notation C=(Ct)t≥1\mathcal{C} = (\mathcal{C}_t)_{t \ge1} to denote the online algorithm producing the sequence of prediction sets (Ct(Xt))t≥1(\mathcal{C}_t(X_t))_{t \ge1}.

After YtY_t is revealed, the performance of the prediction set can be summarized by a binary miscoverage indicator

et=1{Yt∉Ct(Xt;(X1,Y1),…,(Xt−1,Yt−1))}.e_t = 1\{Y_t \notin\mathcal{C}_t(X_t; (X_1, Y_1), \ldots, (X_{t-1}, Y_{t-1}))\}.

We expect the prediction sets to frequently cover the true response YtY_t, quantified by the nominal coverage level 1−α∈(0,1)1 - \alpha\in(0, 1). To quantify this, we may require that the probability of coverage at each time point is calibrated—that is, that P(et≠1)\mathbb{P}(e_t \ne1) or the coverage rate conditional on the history is ≈1−α\approx1 - \alpha, at each time tt. This type of guarantee can only be achieved with some assumptions on the data stream, however. More generally, we can instead aim for a weaker guarantee, requiring that the empirical average coverage rate is ≈1−α\approx1 - \alpha over a period of time. We formally define and discuss these two guarantees in the following subsections.

The i.i.d. setting: instantaneous training-conditional coverage

When the data points (Xt,Yt)(X_t, Y_t) are independent and identically distributed (or exchangeable), split conformal prediction uses past scores to calibrate prediction sets. The score is fixed or fitted to independent data, and higher scores indicate greater deviation from the fitted model. Concretely, with a fixed score function s:X×Y→Rs : \mathcal{X} \times\mathcal{Y} \to\mathbb{R}, the split conformal prediction set can be defined by

CtCP(x)={y∈Y:1+∑r<t1{s(Xr,Yr)≥s(x,y)}t>α}.(2)\mathcal{C}^{\mathrm{CP}}_t(x) = \left\{y \in\mathcal{Y} : \frac{1 + \sum_{r<t} 1\{s(X_r, Y_r) \ge s(x,y)\}}{t} > \alpha\right\}. \tag*{(2)}

Exchangeability gives a finite-sample marginal coverage guarantee, i.e., P(Yt∈CtCP(Xt))≥1−α\mathbb{P}(Y_t \in\mathcal{C}^{\mathrm{CP}}_t(X_t)) \ge1 - \alpha. A more local requirement asks whether coverage is close to 1−α1 - \alpha given the observed past at each time tt. For i.i.d. observations and a nonatomic score distribution,1 the split conformal prediction set in (2) satisfies the following bound (Vovk, [39]; Angelopoulos et al., [3]):

EP[∣P{Yt∈CtCP(Xt)∣(Xs,Ys)s<t}−(1−α)∣]≤12t+1+1t.(3)\mathbb{E}_{\mathbb{P}}\left[\left|\mathbb{P}\{Y_t \in\mathcal{C}^{\mathrm{CP}}_t(X_t) \mid(X_s, Y_s)_{s<t}\} - (1-\alpha)\right|\right] \le\frac{1}{2\sqrt{t+1}} + \frac{1}{t}. \tag*{(3)}

Thus, under these assumptions, the instantaneous training-conditional coverage of split conformal prediction, i.e., its coverage at time tt given the history (Xs,Ys)s<t(X_s, Y_s)_{s<t}, deviates from the target level 1−α1 - \alpha by O(t−1/2)O(t^{-1/2}) in expectation. To measure this deviation over TT rounds, for any online algorithm C\mathcal{C} we define

ΔTinst(C):=∑t=1TEP[∣P{Yt∈Ct(Xt)∣(Xs,Ys)s<t}−(1−α)∣].(4)\Delta^{\mathrm{inst}}_T(\mathcal{C}) := \sum_{t=1}^{T} \mathbb{E}_{\mathbb{P}}\left[\left|\mathbb{P}\{Y_t \in\mathcal{C}_t(X_t) \mid(X_s, Y_s)_{s<t}\} - (1-\alpha)\right|\right]. \tag*{(4)}

With C=CCP\mathcal{C} = \mathcal{C}^{\mathrm{CP}}, summing (3) over tt gives ΔTinst=O(T)\Delta^{\mathrm{inst}}_T = O(\sqrt{T}).

The adversarial setting: long-run empirical coverage

When exchangeability is not assumed, one widely adopted quantity that measures the adversarial performance of online algorithms is the long-run cumulative coverage deviation (Gibbs and Candès [17]):

∑t=1T[1{Yt∈Ct(Xt)}−(1−α)]=∑t=1T(α−et).(5)\sum_{t=1}^{T} [\mathbf{1}\{Y_t \in\mathcal{C}_t(X_t)\} - (1-\alpha)] = \sum_{t=1}^{T}(\alpha-e_t). \tag*{(5)}

Here, we denote ET=∑t=1T(et−α)E_T = \sum_{t=1}^{T}(e_t-\alpha), where ∣ET∣/T|E_T|/T tracks how far the long-run empirical coverage rate departs from 1−α1-\alpha. A well-calibrated algorithm keeps ∣ET∣|E_T| small relative to TT. This guarantee can be achieved by a large class of algorithms without imposing distributional assumptions on the data sequence {(Xt,Yt), t≥1}\{(X_t,Y_t),\ t \ge1\}. To quantify the long-run empirical coverage guarantee in the adversarial setting, we say the algorithm satisfies a (β,κ)(\beta,\kappa)-constraint if

∣ET∣/T≤κT−βfor all T≥1.(6)|E_T|/T \le\kappa T^{-\beta} \quad\text{for all } T \ge1. \tag*{(6)}

Throughout this paper, β∈[0,1]\beta\in[0,1] and κ≥1/2\kappa\ge1/2, so the interval has width at least one and a feasible error outcome exists at every round. Note that if β=0\beta=0 and κ≥max⁡{α,1−α}\kappa\ge\max\{\alpha,1-\alpha\}, then the constraint holds trivially for any sequence (et)t≥1(e_t)_{t\ge1}. For β>0\beta>0, this implies that the long-run empirical coverage rate converges to 1−α1-\alpha. A larger β\beta requires tighter control over the long-run empirical coverage rate. We use Aβ,κ\mathcal{A}_{\beta,\kappa} to collect all algorithms that satisfy (6).2

Our central question is how close an algorithm in Aβ,κ\mathcal{A}_{\beta,\kappa} can stay to exact coverage given the history when the data are i.i.d. By (3), the instantaneous training-conditional coverage of split conformal prediction is within O(t−1/2)O(t^{-1/2}) of 1−α1-\alpha in expectation at round tt, so its cumulative deviation sum to O(T)O(\sqrt{T}) over TT rounds, i.e., ΔTinst=O(T)\Delta_T^{\mathrm{inst}}=O(\sqrt{T}) for C=CCP\mathcal{C}=\mathcal{C}^{\mathrm{CP}}. For a nontrivial constraint, split conformal prediction, however, need not belong to Aβ,κ\mathcal{A}_{\beta,\kappa}. We show that the smallest cumulative error in the instantaneous training-conditional coverage that an algorithm in Aβ,κ\mathcal{A}_{\beta,\kappa} can guarantee for i.i.d. data is of order

Tmax⁡{1/2,β}={T,0≤β≤1/2,Tβ,1/2<β≤1.(7)T^{\max\{1/2,\beta\}} = \begin{cases} \sqrt{T}, & 0 \le\beta\le1/2,\\ T^\beta, & 1/2 < \beta\le1. \end{cases} \tag*{(7)}

Thus, the constraint incurs no cost in rate when β≤1/2\beta\le1/2, whereas for β>1/2\beta>1/2 the rate is dominated by the constraint, yielding a phase transition at β=1/2\beta=1/2.

Adaptive conformal inference (ACI) revisited)

Adaptive Conformal Inference (ACI), introduced by Gibbs and Candès [17], is one way to enforce long-run empirical coverage on every data sequence. We consider its quantile-threshold form [2 b], which uses a fixed score s:X×Y→Rs : \mathcal{X} \times\mathcal{Y} \to\mathbb{R} and constructs CtACI(x)={y:s(x,y)≤qt}C_t^{\mathrm{ACI}}(x) = \{y : s(x,y) \le q_t\}. After observing the outcome, ACI updates its threshold by

qt+1=qt+ηt(et−α),(8)q_{t+1} = q_t + \eta_t(e_t - \alpha), \tag*{(8)}

where ηt>0\eta_t > 0 is the step size. We note that the original ACI procedure [17] updates the nominal coverage level. Here we analyze the quantile-threshold update (8). The threshold increases after miscoverage and decreases after coverage. The step sizes determine how tightly ACI controls the cumulative coverage deviation in the adversarial case. More concretely, when s(x,y)∈[0,B]s(x,y) \in[0,B], ηt≡η\eta_t \equiv\eta (i.e., a constant step size), and q1∈[0,B]q_1 \in[0,B], ACI has the long-run empirical coverage guarantee in the adversarial setting [17, 2]

References

  1. [1]Angelopoulos, A., Candès, E., and Tibshirani, R. J. (2023). Conformal PID control for time series prediction. In Advances in Neural Information Processing Systems, volume 36, pages 23047–23074.arxiv.org/abs/2307.16895
  2. [2]Angelopoulos, A. N., Barber, R., and Bates, S. (2024a). Online conformal prediction with decaying step sizes. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 1616–1630. PMLR.arxiv.org/abs/2402.01139
  3. [3]Angelopoulos, A. N., Barber, R. F., and Bates, S. (2024b). Theoretical foundations of conformal prediction. arXiv preprint arXiv:2411.11824.arxiv.org/abs/2411.11824
  4. [4]Angelopoulos, A. N., Jordan, M. I., and Tibshirani, R. J. (2025). Gradient equilibrium in online learning: Theory and applications. Journal of Machine Learning Research, 26(305):1–68.arxiv.org/abs/2501.08330
  5. [5]Areces, F., Cheng, C., Duchi, J., and Kuditipudi, R. (2024). Two fundamental limits for uncertainty quantification in predictive inference. In The Thirty Seventh Annual Conference on Learning Theory, pages 186–218. PMLR.
  6. [6]Areces, F., Mohri, C., Hashimoto, T., and Duchi, J. (2025). Online conformal prediction via online optimization. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 1604–1649. PMLR.
  7. [7]Barber, R. F., Candès, E. J., Ramdas, A., and Tibshirani, R. J. (2023). Conformal prediction beyond exchangeability. The Annals of Statistics, 51(2):816–845.arxiv.org/abs/2202.13415
  8. [8]Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. (2022). Practical adversarial multivalid conformal prediction. In Advances in Neural Information Processing Systems, volume 35, pages 29362–29373.arxiv.org/abs/2206.01067
  9. [9]Bhatnagar, A., Wang, H., Xiong, C., and Bai, Y. (2023). Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learning, pages 2337–2363. PMLR.arxiv.org/abs/2302.07869
  10. [10]Candès, E., Lei, L., and Ren, Z. (2023). Conformalized survival analysis. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(1):24–45.pubmed.ncbi.nlm.nih.gov/33758770
  11. [11]Cauchois, M., Gupta, S., Ali, A., and Duchi, J. C. (2024). Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, 119(548):3033–3044.DOI
  12. [12]Chernozhukov, V., Wüthrich, K., and Zhu, Y. (2021). Distributional conformal prediction. Proceedings of the National Academy of Sciences, 118(48):e2107794118.DOI
  13. [13]Chung, K. L. (1954). On a stochastic approximation method. The Annals of Mathematical Statistics, pages 463–483.
  14. [14]Duchi, J. C. (2025). A few observations on sample-conditional coverage in conformal prediction. arXiv preprint arXiv:2503.00220.arxiv.org/abs/2503.00220
  15. [15]Durrett, R. (2019). Probability: theory and examples, volume 49. Cambridge university press.
  16. [16]Fabian, V. (1968). On asymptotic normality in stochastic approximation. The Annals of Mathematical Statistics, pages 1327–1332.DOI
  17. [17]Gibbs, I. and Candès, E. J. (2021). Adaptive conformal inference under distribution shift. In Advances in Neural Information Processing Systems, volume 34, pages 1660–1672.arxiv.org/abs/2106.00170
  18. [18]Gibbs, I. and Candès, E. J. (2024). Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1–36.
  19. [19]Gui, Y., Barber, R., and Ma, C. (2023). Conformalized matrix completion. Advances in Neural Information Processing Systems, 36:4820–4844.arxiv.org/abs/2305.10637
  20. [20]Gui, Y., Barber, R. F., and Ma, C. (2026). Distributionally robust risk evaluation with an isotonic constraint. Information and Inference: A Journal of the IMA, 15(3):iaag025.arxiv.org/abs/2407.06867
  21. [21]Gui, Y., Hore, R., Ren, Z., and Barber, R. F. (2024). Conformalized survival analysis with adaptive cut-offs. Biometrika, 111(2):459–477.DOI
  22. [23]Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30.
  23. [24]Jiang, H., Barber, R. F., Pananjady, A., and Xie, Y. (2026). Leave a window out: Modifying the jackknife for predictive inference in time series. arXiv preprint arXiv:2605.30292.arxiv.org/abs/2605.30292
  24. [25]Jin, Y., Ren, Z., and Candès, E. J. (2023). Sensitivity analysis of individual treatment effects: A robust conformal inference approach. Proceedings of the National Academy of Sciences, 120(6):e2214889120.DOI
  25. [26]Lei, J., G’Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. (2018). Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094–1111.arxiv.org/abs/1604.04173
  26. [27]Lei, L. and Candès, E. J. (2021). Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):911–938.arxiv.org/abs/2006.06138
  27. [28]Liang, J., Ren, Z., and Chen, Y. (2026). Optimal training-conditional regret for online conformal prediction. arXiv preprint arXiv:2602.16537.arxiv.org/abs/2602.16537
  28. [29]Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. (2002). Inductive confidence machines for regression. In Machine Learning: ECML 2002, volume 2430 of Lecture Notes in Computer Science, pages 345–356. Springer.
  29. [30]Podkopaev, A. and Ramdas, A. (2021). Distribution-free uncertainty quantification for classification under label shift. In Uncertainty in artificial intelligence, pages 844–853. PMLR.arxiv.org/abs/2103.03323
  30. [31]Podkopaev, A., Xu, D., and Lee, K.-C. (2024). Adaptive conformal inference by betting. arXiv preprint arXiv:2412.19318.arxiv.org/abs/2412.19318
  31. [32]Ramalingam, R., Kiyani, S., and Roth, A. (2025). The relationship between no-regret learning and online conformal prediction. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 51060–51078. PMLR.arxiv.org/abs/2502.10947
  32. [33]Ramsey, F. P. (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286.
  33. [34]Romano, Y., Patterson, E., and Candes, E. (2019). Conformalized quantile regression. Advances in neural information processing systems, 32.arxiv.org/abs/1905.03222
  34. [35]Shafer, G. and Vovk, V. (2008). A tutorial on conformal prediction. Journal of Machine Learning Research, 9(12):371–421.arxiv.org/abs/0706.3188
  35. [36]Srinivas, V. (2026). Online conformal prediction with efficiency guarantees. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6696–6726. SIAM.
  36. [37]Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. (2019). Conformal prediction under covariate shift. Advances in neural information processing systems, 32.arxiv.org/abs/1904.06019
  37. [38]Van der Vaart, A. W. (2000). Asymptotic statistics, volume 3. Cambridge university press.
  38. [39]Vovk, V. (2012). Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475–490. PMLR.arxiv.org/abs/1209.2673
  39. [40]Vovk, V., Gammerman, A., and Shafer, G. (2005). Algorithmic learning in a random world. Springer.
  40. [43]Yang, Z., Huang, Y. M., Candès, E., and Lei, L. (2024). Bellman conformal inference: Calibrating prediction intervals for time series. arXiv preprint arXiv:2402.05203.arxiv.org/abs/2402.05203
  41. [44]Zaffran, M., Dieuleveut, A., Josse, J., and Romano, Y. (2023). Conformal prediction with missing values. In International Conference on Machine Learning, pages 40578–40604. PMLR.arxiv.org/abs/2306.02732
  42. [45]Zaffran, M., Féron, O., Goude, Y., Josse, J., and Dieuleveut, A. (2022). Adaptive conformal predictions for time series. In International Conference on Machine Learning, pages 25834–25866. PMLR.arxiv.org/abs/2202.07282
  43. [46]Zhang, Z., Bombara, D., and Yang, H. (2024). Discounted adaptive online learning: Towards better regularization. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 58631–58661. PMLR.arxiv.org/abs/2402.02720

Paper details

vlnc:W_qven8pe7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents