betaFeedback

WorksMathematics

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

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 dd 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 d\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 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, pp-norm Online Mirror Descent and coordinate-wise Universal Portfolio methods, both improving the dependence on the number of levels to log⁡d\sqrt{\log d} for the multi-level OCP problem. Experiments on several datasets show favorable performance compared to baselines.

Introduction

Constructing prediction sets with reliable coverage guarantees is a central goal of uncertainty quantification. Conformal prediction provides a distribution-free framework for this task: it constructs a prediction set that contains the realized outcome with a user-specified probability, while making few assumptions about the underlying predictive model [28, 34, 35, 39, 40]. In the classical exchangeable setting, conformal methods have been developed for regression, classification, and structured prediction [see, e.g., Barber et al., 2021, Lei et al., 2013, 2018, Romano et al., 2020]. This assumption, however, can be violated in settings where the data distribution shifts, such as sequential decision-making and time-series forecasting.

Online conformal prediction (OCP) addresses these limitations by operating in a fully adversarial sequential setting, where the data may be generated by an arbitrary and possibly adversarial process. A growing body of work has developed algorithms for single-level OCP, in which the goal is to maintain long-run coverage at a single target level 1−α1-\alpha for any data sequence. These include Adaptive Conformal Inference (ACI) [16], an FTRL-based approach [43], conformal PID control [1], meta-algorithms [5, 7, 17, 42], and betting-based methods [25, 29]. Recently, Liu et al. [ [25] established a black-box reduction showing that any online learning algorithm with a linearized regret guarantee can be converted into a single-level OCP algorithm with provable coverage. This reveals a rich landscape of available algorithms for the single-level problem.

However, many real-world applications can benefit from prediction sets that have simultaneous validity at multiple different levels of coverage. This can allow users to inspect the prediction sets ex post facto and choose one of them that fits their needs in terms of coverage, length, as well as any potential downstream risk calculations.

Motivated by this, we consider the setting of multi-level online conformal prediction recently proposed by Ding et al. [ [14]. Observed data ((Zt,Yt))t≥1((Z_t, Y_t))_{t \ge1} arrive over time t=1,2,…t = 1, 2, \ldots. At each round tt, a base model produces a point forecast Y^t\hat{Y}_t for the response YtY_t, using all the previously observed data points, as well as the current features ZtZ_t. We say coverage is attained at tt for the prediction set C^t(Y^t,x)\hat{C}_t(\hat{Y}_t, x), parameterized by a threshold xx, iff it contains YtY_t, i.e., Yt∈C^t(Y^t,x)Y_t \in\hat{C}_t(\hat{Y}_t, x). We fix dd target miscoverage levels A={α1,…,αd}A = \{\alpha_1, \ldots, \alpha_d\}, where 0<α1<α2<⋯<αd<10 < \alpha_1 < \alpha_2 < \cdots< \alpha_d < 1. The conformal predictor announces a vector of thresholds xt=(xt,1,…,xt,d)x_t = (x_{t,1}, \ldots, x_{t,d}) before YtY_t is revealed, where xt,ix_{t,i} targets a long-run coverage rate of 1−αi1 - \alpha_i. Two properties are essential for multi-level forecasts:

  1. Coverage: for any sequence of data ((Zt,Yt))t≥1((Z_t, Y_t))_{t \ge1}, even adversarially chosen, the long-run observed coverage at each level should converge to the nominal target as the time horizon TT grows:

lim⁡T→∞MisCov⁡T,i=0, ∀i∈[d], where MisCov⁡T,i:=∣1T∑t=1T1{St≤xt,i}−(1−αi)∣.\lim_{T \to\infty} \operatorname{MisCov}_{T,i} = 0,\ \forall i \in[d],\ \text{where }\operatorname{MisCov}_{T,i} := \left| \frac{1}{T}\sum_{t=1}^{T} \mathbf{1}\{S_t \le x_{t,i}\} - (1-\alpha_i) \right|.
  1. Distributional consistency. Forecasts should be ordered across quantile levels, i.e., larger levels should give larger sets: xt,1≥xt,2≥⋯≥xt,dx_{t,1} \ge x_{t,2} \ge\cdots\ge x_{t,d}, for all t=1,2,…t = 1, 2, \ldots.

We will refer to these two properties as multi-level coverage.

Ding et al. [ [14] proposed the MultiQT algorithm, which wraps Online Gradient Descent (OGD) with a lazy isotonic projection step to enforce ordering. The algorithm provably achieves asymptotic multi-level coverage. However, their result applies to a single algorithm instance. Meanwhile, as said above, the single-level OCP literature offers a diverse toolbox of algorithms, provably better than OGD. It remains unclear how to migrate these algorithms to the multi-level setting (ideally, with a black-box reduction), while preserving multi-level coverage.

Contributions. In this work, we answer the above open questions with the following contributions:

  • In § 3, we present a general black-box reduction: any online learner satisfying a linearized regret bound properly wrapped with an isotonic projection layer yields a multi-level OCP algorithm that provably guarantees multi-level coverage.

  • Instantiating our framework with pp-norm Online Mirror Descent Gentile, [15] and coordinate-wise Universal Portfolio algorithms Cover and Ordentlich, [13] yields per-level miscoverage rates that depend on log⁡d\sqrt{\log d}, improving over the d\sqrt{d} dependence of the general guarantee in Ding et al. [ [14], and, for the latter, with no parameter tuning under polynomially growing scores. The improvement is in the dependence on dd (rather than on the horizon TT; see Table 1 for the regime where MultiQT attains a faster rate in TT).

  • In § 4, we show that when the isotonic projection acts, it strictly reduces the sharpness reward and weakly reduces the coverage penalty of the Weighted Interval Score (WIS) [9, 18, 41]. This gives a precise theoretical understanding for the empirical observation that projection improves the Pareto frontier of coverage-sharpness trade-offs.

  • In § 5, we evaluate our algorithms on synthetic and real-world datasets, demonstrating consistent improvements in the Pareto frontiers and in the WIS over existing baselines.

Liu et al. [ [25]Ding et al. [ [14] (MultiQT)This paper
ScoresSt≤DtγS_t\le Dt^\gammaSt≤DS_t\le DSt≤DTγS_t\le DT^\gamma (Ass. 2.1)
Algorithmsany scalar learner with linearized regretOGD with lazy isotonic projectionany learner on Rd\mathbb{R}^d with linearized regret (Alg. 1, Prop. 3.3)
Guaranteescalar Fenchel level setℓ2\ell_2 ball, via restorativitylevel set FT−(−GT)≤BT\mathcal{F}_T^{-}(-G_T)\le B_T (Thm. 3.4)
Rate, generalsingle level onlyO ⁣(d/T+dD/(ηdAT))\mathcal{O}\!\left(\sqrt{d/T}+d\sqrt{D/(\eta d_A T)}\right)O(log⁡d/T)\mathcal{O}(\sqrt{\log d/T}) (Cor. 3.6); parameter-free: O((log⁡d+(1+γ)log⁡T)/T)\mathcal{O}(\sqrt{(\log d+(1+\gamma)\log T)/T}) (Thm. 3.7)
Rate, common point forecastn/aO(d3/2(1+D/η)/(dAT))\mathcal{O}(d^{3/2}(1+D/\eta)/(d_A T)), fixed η\eta, linear regretnot recovered by our analysis
Other resultsnonesharpness gains (empirical)WIS reduction (Thm. 4.1); continuous levels (App. § 8.8)

Table 1. Comparison with the closest prior work. Rates are for max⁡iMisCov⁡T,i\max_i\operatorname{MisCov}_{T,i}; dA:=min⁡imin⁡{αi,1−αi}d_A:=\min_i\min\{\alpha_i,1-\alpha_i\} (=α1=\alpha_1 when α1+αd≤1\alpha_1+\alpha_d\le1).

Related Work. Our work sits at the intersection of online conformal prediction, online learning, and multi-level coverage. Adaptive conformal inference and its variants treat the conformal radius as a sequentially updated decision variable, often optimized through the pinball loss [16, 17, 42]. Strongly adaptive and control-based methods improve local responsiveness or empirical stability, but require method-specific choices such as expert grids, gain parameters, or range assumptions [1, 7]. Parameter-free approaches obtain optimal regret guarantees uniformly over all comparators, by avoiding explicit stepsize tuning [29, 43] (Li et al. 2026), and can be extended to group-conditional coverage at a single level [6]. Among these works, the closest one to our work is Liu et al. [ [25], which proves a black-box linearized-regret-to-coverage implication, but only for scalar OCP, i.e., a single coverage level. Related analyses distinguish standard regret from the stronger conditions needed for coverage, including gradient-equilibrium and proximal-regret viewpoints [3, 10].

The multi-level setting is connected to, but distinct from, simultaneous and multivalid forms of conformal inference, where one controls empirical coverage across groups or threshold families [5], while simultaneous conformal and conformal risk-control methods handle many inference targets or losses at once [2, 22]. Instead, our focus is an adversarial online protocol for an ordered family of conformal sets indexed by miscoverage levels. Finally, our sharpness interpretation is aligned with proper interval and quantile scoring rules [9, 18, 41]. Table 1 in Appendix § 8.9 compares our results with the two works we build on closely.

Problem setup

In this section, we formalize the multi-level OCP problem outlined in § 1.

Notation. We collect a few standard tools from convex analysis in Rd\mathbb{R}^{d} [see, e.g., Rockafellar, 1997] for reference. For a function f:Rd→R∪{+∞}f:\mathbb{R}^{d} \to\mathbb{R} \cup\{+\infty\}, a vector g∈Rdg \in\mathbb{R}^{d} is a subgradient of ff at x∈Rdx \in\mathbb{R}^{d} if f(y)≥f(x)+⟨g,y−x⟩f(y) \ge f(x) + \langle g, y-x \rangle for every y∈Rdy \in\mathbb{R}^{d}, and the set of all such gg is the subdifferential ∂f(x)\partial f(x). The indicator function 1{A}\mathbb{1}\{A\} is equal to 1 if AA is true and 0 otherwise. The Fenchel conjugate of f:Rd→[−∞,+∞]f:\mathbb{R}^{d} \to[-\infty,+\infty] is f⋆(θ):=sup⁡x∈Rd⟨θ,x⟩−f(x)f^{\star}(\theta) := \sup_{x \in\mathbb{R}^{d}} \langle\theta,x \rangle- f(x), which is always convex and closed, i.e., its epigraph is a closed set (equivalently, f⋆f^{\star} is lower semicontinuous). The Euclidean projection onto a nonempty closed convex set C⊆RdC \subseteq\mathbb{R}^{d} is ΠC(x):=arg minz∈C∥x−z∥2\Pi_{C}(x) := \mathop{\rm arg\,min}_{z \in C} \lVert x-z \rVert_{2}, which is well-defined and unique. We denote by [d]:={1,…,d}[d] := \{1,\ldots,d\}.

Multi-level OCP. We now describe the sequential protocol of OCP with multiple quantile levels. We choose to focus on symmetric prediction sets of the form C^t(Y^t,x):=[Y^t−x,Y^t+x]\widehat{C}_{t}(\widehat{Y}_{t},x) := [\widehat{Y}_{t}-x,\widehat{Y}_{t}+x], defined as empty if x<0x<0 [24]. Our methodology is applicable beyond this setting: it only needs a nested family of sets parameterized by one scalar per level; e.g., it can be used to adjust the prediction intervals based on conditional quantile regression models [32], but we avoid the details for brevity. We refer the reader to Gupta et al. [ [19] for more versions of the nested prediction sets for which our methodology is applicable. Let St≥0S_{t} \ge0 denote the radius of the smallest prediction set that contains the true response YtY_{t}, i.e., St:=inf⁡{x∈[0,∞):Yt∈C^t(Y^t,x)}=∣Yt−Y^t∣S_{t} := \inf\{x \in[0,\infty): Y_{t} \in\widehat{C}_{t}(\widehat{Y}_{t},x)\} = |Y_{t}-\widehat{Y}_{t}|. With this choice, Yt∈C^t(Y^t,x)⟺St≤xY_{t} \in\widehat{C}_{t}(\widehat{Y}_{t},x) \Longleftrightarrow S_{t} \le x for x>0x>0, and the coverage event at level 1−αi1-\alpha_{i} collapses to the single threshold comparison 1{St≤xt,i}\mathbb{1}\{S_{t} \le x_{t,i}\}. We will also refer to StS_{t} as the non-conformity score [39].

Note that a negative radius does not describe a valid interval, so our algorithms output the empty set instead, represented by a 0 radius, the Lebesgue measure of ∅\varnothing (§ 3). Accordingly, a played radius of 0 is read as ∅\varnothing, which never covers YtY_{t}, even when St=0S_{t}=0.

References

  1. [1]Anastasios Angelopoulos, Emmanuel Candes, and Ryan J Tibshirani. Conformal PID control for time series prediction. Advances in neural information processing systems, 36:23047–23074, 2023.arxiv.org/abs/2307.16895
  2. [2]Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXiv:2208.02814, 2022.arxiv.org/abs/2208.02814
  3. [3]Anastasios N Angelopoulos, Michael I Jordan, and Ryan J Tibshirani. Gradient equilibrium in online learning: Theory and applications. arXiv preprint arXiv:2501.08330, 2025.arxiv.org/abs/2501.08330
  4. [5]Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances in neural information processing systems, 35:29362–29373, 2022.arxiv.org/abs/2206.01067
  5. [6]Beepul Bharti, Ambar Pal, Jacopo Teneggi, and Jeremias Sulam. Parameter-free and group conditional online conformal prediction. arXiv preprint arXiv:2606.00419, 2026.arxiv.org/abs/2606.00419
  6. [7]Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learning, pages 2337–2363. PMLR, 2023.arxiv.org/abs/2302.07869
  7. [8]Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
  8. [9]Johannes Bracher, Evan L Ray, Tilmann Gneiting, and Nicholas G Reich. Evaluating epidemic forecasts in an interval format. PLoS computational biology, 17(2):e1008618, 2021.
  9. [10]Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. On tractable φ-equilibria in non-concave games. Advances in Neural Information Processing Systems, 37:140366–140404, 2024.arxiv.org/abs/2403.08171
  10. [11]Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
  11. [13]Thomas M Cover and Erik Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2):348–363, 2002.
  12. [14]Tiffany Ding, Isaac Gibbs, and Ryan J Tibshirani. Calibrated multi-level quantile forecasting. arXiv preprint arXiv:2512.23671, 2025.arxiv.org/abs/2512.23671
  13. [15]Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003.
  14. [16]Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660–1672, 2021.arxiv.org/abs/2106.00170
  15. [17]Isaac Gibbs and Emmanuel J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1–36, 2024.
  16. [18]Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359–378, 2007.
  17. [19]Chirag Gupta, Arun K Kuchibhotla, and Aaditya Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496, 2022.DOI
  18. [20]Michael Harries. Splice-2 comparative evaluation: Electricity pricing. Technical report, University of New South Wales, School of Computer Science and Engineering, 1999.
  19. [22]Yonghoon Lee, Edgar Dobriban, and Eric Tchetgen Tchetgen. Simultaneous conformal prediction of missing outcomes with propensity score ε-discretization. arXiv preprint arXiv:2403.04613, 2024.
  20. [24]Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094–1111, 2018.arxiv.org/abs/1604.04173
  21. [25]Tuo Liu, Edgar Dobriban, and Francesco Orabona. Online conformal prediction via universal portfolio algorithms. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 75891–75952. PMLR, 2026.arxiv.org/abs/2602.03168
  22. [27]Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
  23. [28]Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European conference on machine learning, pages 345–356. Springer, 2002.
  24. [29]Aleksandr Podkopaev, Darren Xu, and Kuang-chih Lee. Adaptive conformal inference by betting. In Proceedings of the 41st International Conference on Machine Learning, pages 40886–40907, 2024.arxiv.org/abs/2412.19318
  25. [30]Tim Robertson, F. T. Wright, and R. L. Dykstra. Order Restricted Statistical Inference. Wiley, 1988.
  26. [31]R Tyrrell Rockafellar. Convex analysis, volume 28. Princeton university press, 1997.
  27. [32]Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1905.03222
  28. [34]Craig Saunders, Alexander Gammerman, and Volodya Vovk. Transduction with confidence and credibility. In IJCAI, 1999.
  29. [35]Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3):371–421, 2008.arxiv.org/abs/0706.3188
  30. [36]Shai Shalev-Shwartz. Online Learning: Theory, Algorithms, and Applications. PhD thesis, Hebrew University of Jerusalem, 2007.
  31. [37]Vaidehi Srinivas. Online conformal prediction with efficiency guarantees. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6696–6726. SIAM, 2026.
  32. [38]Sean J Taylor and Benjamin Letham. Forecasting at scale. The American Statistician, 72(1):37–45, 2018.DOI
  33. [39]Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer Science & Business Media, 2005.
  34. [40]Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of algorithmic randomness. In Proceedings of the Sixteenth International Conference on Machine Learning, pages 444–453, 1999.
  35. [41]Robert L Winkler. A decision-theoretic approach to interval estimation. Journal of the American Statistical Association, 67(337):187–191, 1972.DOI
  36. [42]Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In International conference on machine learning, pages 25834–25866. PMLR, 2022.arxiv.org/abs/2202.07282
  37. [43]Zhiyu Zhang, David Bombara, and Heng Yang. Discounted adaptive online learning: towards better regularization. In Proceedings of the 41st International Conference on Machine Learning, pages 58631–58661, 2024.arxiv.org/abs/2402.02720
  38. [44]Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proc. of the International Conference on Machine Learning, pages 928–936, 2003.

Paper details

vlnc:W_zpc4nm24
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