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 1 − α 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 ( ( Z t , Y t ) ) t ≥ 1 ((Z_t, Y_t))_{t \ge1} (( Z t , Y t ) ) t ≥ 1 arrive over time t = 1 , 2 , … t = 1, 2, \ldots t = 1 , 2 , … . At each round t t t , a base model produces a point forecast Y ^ t \hat{Y}_t Y ^ t for the response Y t Y_t Y t , using all the previously observed data points, as well as the current features Z t Z_t Z t . We say coverage is attained at t t t for the prediction set C ^ t ( Y ^ t , x ) \hat{C}_t(\hat{Y}_t, x) C ^ t ( Y ^ t , x ) , parameterized by a threshold x x x , iff it contains Y t Y_t Y t , i.e., Y t ∈ C ^ t ( Y ^ t , x ) Y_t \in\hat{C}_t(\hat{Y}_t, x) Y t ∈ C ^ t ( Y ^ t , x ) . We fix d d d target miscoverage levels A = { α 1 , … , α d } A = \{\alpha_1, \ldots, \alpha_d\} A = { α 1 , … , α d } , where 0 < α 1 < α 2 < ⋯ < α d < 1 0 < \alpha_1 < \alpha_2 < \cdots< \alpha_d < 1 0 < α 1 < α 2 < ⋯ < α d < 1 . The conformal predictor announces a vector of thresholds x t = ( x t , 1 , … , x t , d ) x_t = (x_{t,1}, \ldots, x_{t,d}) x t = ( x t , 1 , … , x t , d ) before Y t Y_t Y t is revealed, where x t , i x_{t,i} x t , i targets a long-run coverage rate of 1 − α i 1 - \alpha_i 1 − α i . Two properties are essential for multi-level forecasts:
Coverage: for any sequence of data ( ( Z t , Y t ) ) t ≥ 1 ((Z_t, Y_t))_{t \ge1} (( Z t , Y t ) ) t ≥ 1 , even adversarially chosen, the long-run observed coverage at each level should converge to the nominal target as the time horizon T T T grows:
lim T → ∞ MisCov T , i = 0 , ∀ i ∈ [ d ] , where MisCov T , i : = ∣ 1 T ∑ t = 1 T 1 { S t ≤ x t , 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|. T → ∞ lim MisCov T , i = 0 , ∀ i ∈ [ d ] , where MisCov T , i := T 1 t = 1 ∑ T 1 { S t ≤ x t , i } − ( 1 − α i ) .
Distributional consistency. Forecasts should be ordered across quantile levels, i.e., larger levels should give larger sets: x t , 1 ≥ x t , 2 ≥ ⋯ ≥ x t , d x_{t,1} \ge x_{t,2} \ge\cdots\ge x_{t,d} x t , 1 ≥ x t , 2 ≥ ⋯ ≥ x t , d , for all t = 1 , 2 , … t = 1, 2, \ldots t = 1 , 2 , … .
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 p p p -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} log d , improving over the d \sqrt{d} 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 d d d (rather than on the horizon T T T ; see Table 1 for the regime where MultiQT attains a faster rate in T T T ).
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.
Table 1. Comparison with the closest prior work. Rates are for max i MisCov T , i \max_i\operatorname{MisCov}_{T,i} max i MisCov T , i ; d A : = min i min { α i , 1 − α i } d_A:=\min_i\min\{\alpha_i,1-\alpha_i\} d A := min i min { α i , 1 − α i } (= α 1 =\alpha_1 = α 1 when α 1 + α d ≤ 1 \alpha_1+\alpha_d\le1 α 1 + α d ≤ 1 ).
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 R d \mathbb{R}^{d} R d [see, e.g., Rockafellar, 1997] for reference. For a function f : R d → R ∪ { + ∞ } f:\mathbb{R}^{d} \to\mathbb{R} \cup\{+\infty\} f : R d → R ∪ { + ∞ } , a vector g ∈ R d g \in\mathbb{R}^{d} g ∈ R d is a subgradient of f f f at x ∈ R d x \in\mathbb{R}^{d} x ∈ R d if f ( y ) ≥ f ( x ) + ⟨ g , y − x ⟩ f(y) \ge f(x) + \langle g, y-x \rangle f ( y ) ≥ f ( x ) + ⟨ g , y − x ⟩ for every y ∈ R d y \in\mathbb{R}^{d} y ∈ R d , and the set of all such g g g is the subdifferential ∂ f ( x ) \partial f(x) ∂ f ( x ) . The indicator function 1 { A } \mathbb{1}\{A\} 1 { A } is equal to 1 if A A A is true and 0 otherwise. The Fenchel conjugate of f : R d → [ − ∞ , + ∞ ] f:\mathbb{R}^{d} \to[-\infty,+\infty] f : R d → [ − ∞ , + ∞ ] is f ⋆ ( θ ) : = sup x ∈ R d ⟨ θ , x ⟩ − f ( x ) f^{\star}(\theta) := \sup_{x \in\mathbb{R}^{d}} \langle\theta,x \rangle- f(x) f ⋆ ( θ ) := sup x ∈ R d ⟨ θ , x ⟩ − f ( x ) , which is always convex and closed, i.e., its epigraph is a closed set (equivalently, f ⋆ f^{\star} f ⋆ is lower semicontinuous). The Euclidean projection onto a nonempty closed convex set C ⊆ R d C \subseteq\mathbb{R}^{d} C ⊆ R d is Π C ( x ) : = a r g m i n z ∈ C ∥ x − z ∥ 2 \Pi_{C}(x) := \mathop{\rm arg\,min}_{z \in C} \lVert x-z \rVert_{2} Π C ( x ) := arg min z ∈ C ∥ x − z ∥ 2 , which is well-defined and unique. We denote by [ d ] : = { 1 , … , d } [d] := \{1,\ldots,d\} [ d ] := { 1 , … , 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] C t ( Y t , x ) := [ Y t − x , Y t + x ] , defined as empty if x < 0 x<0 x < 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 S t ≥ 0 S_{t} \ge0 S t ≥ 0 denote the radius of the smallest prediction set that contains the true response Y t Y_{t} Y t , i.e., S t : = inf { x ∈ [ 0 , ∞ ) : Y t ∈ C ^ t ( Y ^ t , x ) } = ∣ Y t − Y ^ t ∣ S_{t} := \inf\{x \in[0,\infty): Y_{t} \in\widehat{C}_{t}(\widehat{Y}_{t},x)\} = |Y_{t}-\widehat{Y}_{t}| S t := inf { x ∈ [ 0 , ∞ ) : Y t ∈ C t ( Y t , x )} = ∣ Y t − Y t ∣ . With this choice, Y t ∈ C ^ t ( Y ^ t , x ) ⟺ S t ≤ x Y_{t} \in\widehat{C}_{t}(\widehat{Y}_{t},x) \Longleftrightarrow S_{t} \le x Y t ∈ C t ( Y t , x ) ⟺ S t ≤ x for x > 0 x>0 x > 0 , and the coverage event at level 1 − α i 1-\alpha_{i} 1 − α i collapses to the single threshold comparison 1 { S t ≤ x t , i } \mathbb{1}\{S_{t} \le x_{t,i}\} 1 { S t ≤ x t , i } . We will also refer to S t S_{t} S 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 Y t Y_{t} Y t , even when S t = 0 S_{t}=0 S t = 0 .
As we said in § 1 , we require per-level coverage and distributional consistency . For the second one, the increasing miscoverage levels α 1 < ⋯ < α d \alpha_{1}<\cdots<\alpha_{d} α 1 < ⋯ < α d should be matched by non-increasing thresholds x t , 1 ≥ ⋯ ≥ x t , d x_{t,1}\ge\cdots\ge x_{t,d} x t , 1 ≥ ⋯ ≥ x t , d . Equivalently, x t ∈ K x_{t}\in\mathcal{K} x t ∈ K for every t t t , where K : = { x ∈ R d : x 1 ≥ x 2 ≥ ⋯ ≥ x d } \mathcal{K}:=\{x\in\mathbb{R}^{d}:x_{1}\ge x_{2}\ge\cdots\ge x_{d}\} K := { x ∈ R d : x 1 ≥ x 2 ≥ ⋯ ≥ x d } is the isotonic cone .1
Pinball loss and its aggregate. As in the single-level case, we introduce the pinball (or quantile) loss for online quantile learning [16 , 29 ] , defined as
ℓ ( 1 − α ) ( x , S ) : = max { ( 1 − α ) ( S − x ) , α ( x − S ) } . (1) \ell^{(1-\alpha)}(x,S) := \max\{(1-\alpha)(S-x),\alpha(x-S)\}. \tag*{(1)} ℓ ( 1 − α ) ( x , S ) := max {( 1 − α ) ( S − x ) , α ( x − S )} . (1)
where S S S is the non-conformity score and x x x is the radius of the prediction interval. This loss is convex and L L L -Lipschitz in the first argument, where L : = max { 1 − α , α } L:=\max\{1-\alpha,\alpha\} L := max { 1 − α , α } . Intuitively, the pinball loss is a proper surrogate for the ( 1 − α i ) (1-\alpha_{i}) ( 1 − α i ) -th quantile, as under any distribution of S S S , the expectation of ℓ ( 1 − α i ) ( x , S ) \ell^{(1-\alpha_{i})}(x,S) ℓ ( 1 − α i ) ( x , S ) in x x x is minimized exactly at the ( 1 − α i ) (1-\alpha_{i}) ( 1 − α i ) -th quantile of S S S [18 ] .
To handle the d d d levels jointly, we work with the aggregate pinball loss L t ( x ) : = ∑ i = 1 d ℓ ( 1 − α i ) ( x i , S t ) \mathcal{L}_t(\boldsymbol{x}) := \sum_{i=1}^{d} \ell^{(1-\alpha_i)}(x_i, S_t) L t ( x ) := ∑ i = 1 d ℓ ( 1 − α i ) ( x i , S t ) , for x ∈ R d \boldsymbol{x} \in\mathbb{R}^d x ∈ R d . We select the subgradient g t ∈ ∂ L t ( x t ) \boldsymbol{g}_t \in\partial\mathcal{L}_t(\boldsymbol{x}_t) g t ∈ ∂ L t ( x t ) with coordinates
g t , i = 1 { x t , i ≥ S t } − ( 1 − α i ) , ∀ i ∈ [ d ] . (2) g_{t,i} = \mathbf{1}\{x_{t,i} \ge S_t\} - (1-\alpha_i), \quad\forall i \in[d]. \tag*{(2)} g t , i = 1 { x t , i ≥ S t } − ( 1 − α i ) , ∀ i ∈ [ d ] . (2)
Note that L t \mathcal{L}_t L t is Lipschitz in both the ℓ 2 \ell_2 ℓ 2 and ℓ 1 \ell_1 ℓ 1 (dual of ℓ ∞ \ell_\infty ℓ ∞ ) norms: ∥ g t ∥ 2 ≤ d \|\boldsymbol{g}_t\|_2 \le\sqrt{d} ∥ g t ∥ 2 ≤ d and ∥ g t ∥ ∞ ≤ max { 1 − α 1 , α d } ≤ 1 \|\boldsymbol{g}_t\|_\infty\le\max\{1-\alpha_1,\alpha_d\} \le1 ∥ g t ∥ ∞ ≤ max { 1 − α 1 , α d } ≤ 1 . These are favorable conditions for online learnability [see, e.g., Cesa-Bianchi and Orabona, 2021, Hazan, 2016, Orabona, 2019]. Performance on the aggregate loss is measured by the standard notion of regret . Against a fixed comparator u ∈ R d \boldsymbol{u} \in\mathbb{R}^d u ∈ R d , the regret of an algorithm producing ( x t ) t ≥ 1 (\boldsymbol{x}_t)_{t\ge1} ( x t ) t ≥ 1 is Regret T ( u ) : = ∑ t = 1 T L t ( x t ) − ∑ t = 1 T L t ( u ) \operatorname{Regret}_T(\boldsymbol{u}) := \sum_{t=1}^{T} \mathcal{L}_t(\boldsymbol{x}_t) - \sum_{t=1}^{T} \mathcal{L}_t(\boldsymbol{u}) Regret T ( u ) := ∑ t = 1 T L t ( x t ) − ∑ t = 1 T L t ( u ) .
Finally, we note that the subgradient (2) admits a direct interpretation as a miscoverage error:
MisCov T , i : = 1 T ∣ ∑ t = 1 T g t , i ∣ , ∀ i ∈ [ d ] . (3) \operatorname{MisCov}_{T,i} := \frac{1}{T}\left|\sum_{t=1}^{T} g_{t,i}\right|,\quad\forall i \in[d]. \tag*{(3)} MisCov T , i := T 1 t = 1 ∑ T g t , i , ∀ i ∈ [ d ] . (3)
We use a single, mild assumption on the polynomial growth of the score sequence.
Assumption 2.1. There exist constants D > 0 D > 0 D > 0 and γ ≥ 0 \gamma\ge0 γ ≥ 0 such that S t ≤ D T γ S_t \le DT^\gamma S t ≤ D T γ for every t ∈ [ T ] t \in[T] t ∈ [ T ] .
This assumption generalizes the bounded-score assumption S t ≤ D S_t \le D S t ≤ D used in much of the OCP literature (recovered by γ = 0 \gamma= 0 γ = 0 ), and accommodates non-stationary streams whose magnitudes grow with the horizon (e.g., financial returns with volatility clustering [25 ] ).
From regret to multi-level coverage: a black-box reduction
Our goal is to design a black-box reduction for an online algorithm: (1) to have iterates x t \boldsymbol{x}_t x t lie in the isotonic cone K \mathcal{K} K at every round; (2) to secure per-level coverage by controlling the cumulative subgradient G T : = ∑ t = 1 T g t \boldsymbol{G}_T := \sum_{t=1}^{T} \boldsymbol{g}_t G T := ∑ t = 1 T g t , via (3) . Linearized regret is the natural interface for (2): G T , i G_{T,i} G T , i is T T T times the signed coverage error at level i i i , and a bound on ∑ t ⟨ g t , x t − u ⟩ \sum_t \langle\boldsymbol{g}_t,\boldsymbol{x}_t-\boldsymbol{u}\rangle ∑ t ⟨ g t , x t − u ⟩ holding for every comparator u \boldsymbol{u} u is, by duality, a bound on G T \boldsymbol{G}_T G T . We resolve both issues through a single mechanism: a lazy isotonic projection layer , applied as a black-box wrapper around any unconstrained online learner Alg with a linearized-regret guarantee.
The lazy isotonic projection wrapper. Let Alg be a generic online learner. We make no assumption on its internal structure: Alg is a black box that, at each round, produces a vector of radii x ~ t ∈ R + d \tilde{\boldsymbol{x}}_t \in\mathbb{R}^d_+ x ~ t ∈ R + d and accepts an arbitrary subgradient. The wrapper inserts Alg with a single Euclidean projection step:
Algorithm 1 Lazy projection wrapper Alg → \to → multi-level OCP
Input: base learner Alg with outputs in R + d \mathbb{R}^d_+ R + d ; isotonic cone K \mathcal{K} K
for t = 1 , 2 , … t = 1, 2, \ldots t = 1 , 2 , … do
Receive hidden iterate x ~ t ∈ R + d \tilde{\boldsymbol{x}}_t \in\mathbb{R}^d_+ x ~ t ∈ R + d from Alg
Play projected iterate x t = Π K ( x ~ t ) \boldsymbol{x}_t = \Pi_{\mathcal{K}}(\tilde{\boldsymbol{x}}_t) x t = Π K ( x ~ t )
Observe S t S_t S t and compute g t ∈ ∂ L t ( x t ) \boldsymbol{g}_t \in\partial\mathcal{L}_t(\boldsymbol{x}_t) g t ∈ ∂ L t ( x t ) via (2)
Feed g t \boldsymbol{g}_t g t to Alg, which produces x ~ t + 1 \tilde{\boldsymbol{x}}_{t+1} x ~ t + 1
end for
The defining feature of this protocol is the asymmetry between the played iterate x t \boldsymbol{x}_t x t (projected onto K \mathcal{K} K ) and the gradient input g t \boldsymbol{g}_t g t to Alg (evaluated at the projected iterate, then routed back into the unconstrained dynamics). This pattern is known as lazy projection [44 ] . Despite being embedded in MultiOQT [14 ] , the generality of such a structure was largely unrecognized. Here, we treat the projection as a strictly external layer.
Any online learner on R d \mathbb{R}^d R d becomes a base learner with outputs in R + d \mathbb{R}^d_+ R + d through the convention of Section 2: whenever its raw radius z t , i z_{t,i} z t , i is negative, it outputs the empty set at level i i i , represented as x ~ t , i = max ( z t , i , 0 ) = 0 \tilde{x}_{t,i} = \max(z_{t,i},0) = 0 x ~ t , i = max ( z t , i , 0 ) = 0 . The learner’s update rule and internal state are unchanged. It also makes the input of the isotonic layer a valid vector of radii, which Section 4 exploits.
To start off, observe that, since x t ∈ K x_t \in\mathcal{K} x t ∈ K at every round, the empirical coverage rates inherit the same monotonicity: Coverage T , 1 ≥ Coverage T , 2 ≥ ⋯ ≥ Coverage T , d \operatorname{Coverage}_{T,1} \ge\operatorname{Coverage}_{T,2} \ge\cdots\ge\operatorname{Coverage}_{T,d} Coverage T , 1 ≥ Coverage T , 2 ≥ ⋯ ≥ Coverage T , d , where Coverage T , i : = ( 1 / T ) ∑ t = 1 T 1 { S t ≤ x t , i } \operatorname{Coverage}_{T,i} := (1/T)\sum_{t=1}^{T} \mathbf{1}\{S_t \le x_{t,i}\} Coverage T , i := ( 1/ T ) ∑ t = 1 T 1 { S t ≤ x t , i } . This is an automatic property from the algorithm, coherent to multi-level coverage, with no extra analysis.
Linearized regret preservation through inward flow. Two features of the wrapper need to be reconciled with the regret guarantee: (1) The projection step moves x ~ t \widetilde{x}_t x t inside K \mathcal{K} K before predicting, and (2) Alg is updated with g t ∈ ∂ L t ( x t ) g_t \in\partial\mathcal{L}_t(x_t) g t ∈ ∂ L t ( x t ) evaluated at the played iterate rather than at the iterate Alg produced. Both could in principle inflate the regret. The inward flow property of Ding et al. [ [14 ] ensures they do not. We restate it for any abstract loss-set pair, since this generality is essential below.
Definition 3.1 (Inward flow [14 ] ). A function f f f paired with a closed convex set C ⊆ R d C \subseteq\mathbb{R}^{d} C ⊆ R d satisfies the inward flow property if there exists a subgradient g ( x ) ∈ ∂ f ( x ) g(x) \in\partial f(x) g ( x ) ∈ ∂ f ( x ) such that − g ( x ) ∈ T C ( x ) -g(x) \in T_C(x) − g ( x ) ∈ T C ( x ) for every boundary point x ∈ bd ( C ) x \in\operatorname{bd}(C) x ∈ bd ( C ) , where T C ( x ) : = cl { v : ∃ δ > 0 , x + ε v ∈ C for ε ∈ ( 0 , δ ] } T_C(x) := \operatorname{cl}\{v : \exists\delta> 0, x + \varepsilon v \in C \text{ for } \varepsilon\in(0,\delta]\} T C ( x ) := cl { v : ∃ δ > 0 , x + ε v ∈ C for ε ∈ ( 0 , δ ]} is the tangent cone of C C C at x x x , bd ( S ) \operatorname{bd}(S) bd ( S ) denotes the boundary of a set S S S , and cl ( S ) \operatorname{cl}(S) cl ( S ) denotes the closure of S S S .
Geometrically, the chosen subgradient at the boundary points outward, so the descent direction points inward, and a small step opposite g ( x ) g(x) g ( x ) stays feasible. For the isotonic cone, the meaning is clear: two tied levels x i = x i + 1 x_i = x_{i+1} x i = x i + 1 share the same coverage indicator, so g i = 1 { x i ≥ S t } − ( 1 − α i ) ≤ g i + 1 g_i = \mathbf{1}\{x_i \ge S_t\} - (1-\alpha_i) \le g_{i+1} g i = 1 { x i ≥ S t } − ( 1 − α i ) ≤ g i + 1 , and a descent step raises the radius at level i i i at least as much as at level i + 1 i+1 i + 1 , never creating a crossing. Ding et al. [ [14 ] verifies inward flow for the aggregated pinball L t \mathcal{L}_t L t paired with the (decreasing) isotonic cone K \mathcal{K} K under the choice of subgradient as in (2) ; we adopt this throughout. The structural consequence relevant to our analysis is the following projection-and-gradient inequality.
Lemma 3.2 (Projection inequality [14 ] ). Let f f f with subgradient g g g and a closed convex set C ⊆ R d C \subseteq\mathbb{R}^{d} C ⊆ R d satisfy inward flow. For every x ∈ R d x \in\mathbb{R}^{d} x ∈ R d , ⟨ g ( Π C ( x ) ) , x ⟩ ≥ ⟨ g ( Π C ( x ) ) , Π C ( x ) ⟩ \langle g(\Pi_C(x)), x\rangle\ge\langle g(\Pi_C(x)), \Pi_C(x)\rangle ⟨ g ( Π C ( x )) , x ⟩ ≥ ⟨ g ( Π C ( x )) , Π C ( x )⟩ .
A self-contained proof, which leverages the duality between the tangent cone (containing − g t -g_t − g t ) and the normal cone (containing the projection direction x ~ t − x t \widetilde{x}_t - x_t x t − x t ), is in Appendix § 8 .§ 1 . We state it for a general C C C because inward flow composes under intersection with polyhedral sets, so further polyhedral constraints can be layered on top of K \mathcal{K} K (Appendix § 8 .§ 5 ).
Lemma 3.2 converts a regret bound on the hidden iterates of Alg into a regret bound on the played iterates and allows us to prove the following regret guarantee for Algorithm 1.
Proposition 3.3 (Linearized regret preservation). Suppose Alg admits a linearized regret bound F T ( u ) F_T(u) F T ( u ) on the gradient sequence ( g t ) t ∈ [ T ] (g_t)_{t\in[T]} ( g t ) t ∈ [ T ] , that is, ∑ t = 1 T ⟨ g t , x ~ t − u ⟩ ≤ F T ( u ) \sum_{t=1}^{T}\langle g_t,\widetilde{x}_t-u\rangle\le F_T(u) ∑ t = 1 T ⟨ g t , x t − u ⟩ ≤ F T ( u ) for every u ∈ R d u \in\mathbb{R}^{d} u ∈ R d . The played iterates x t = Π K ( x ~ t ) x_t = \Pi_{\mathcal{K}}(\widetilde{x}_t) x t = Π K ( x t ) produced by Algorithm 1 satisfy
LinRegret T ( u ) : = ∑ t = 1 T ⟨ g t , x t − u ⟩ ≤ F T ( u ) , ∀ u ∈ R d . (4) \operatorname{LinRegret}_T(u) := \sum_{t=1}^{T}\langle g_t,x_t-u\rangle\le F_T(u), \qquad\forall u \in\mathbb{R}^{d}. \tag*{(4)} LinRegret T ( u ) := t = 1 ∑ T ⟨ g t , x t − u ⟩ ≤ F T ( u ) , ∀ u ∈ R d . (4)
A consequence that is worth highlighting is that (4) holds for every u ∈ R d u \in\mathbb{R}^{d} u ∈ R d , not just for u ∈ K u \in\mathcal{K} u ∈ K , so the projection is free of charge against any comparator the base learner could compete with. The proof in Appendix § 8 .§ 2 is a direct combination of Lemma 3.2, the assumption on linearized regret, and convexity of L t \mathcal{L}_t L t .
Characterization of miscoverage level sets. We now translate the regret guarantee into a finite-time bound on the cumulative subgradient. We show a sketch of the reasoning, while the full argument is given in Appendix § 8 .§ 2 .
For notational convenience, define G T : = ∑ t = 1 T g t ∈ R d G_T := \sum_{t=1}^{T} g_t \in\mathbb{R}^{d} G T := ∑ t = 1 T g t ∈ R d . First, note that (4) , by regret–reward duality [27 ] , is equivalent to
F T ⋆ ( − G T ) = F T ⋆ ( − ∑ t = 1 T g t ) ≤ − ∑ t = 1 T ⟨ g t , x t ⟩ ≤ ∑ t = 1 T ( L t ( 0 ) − L t ( x t ) ) ≤ ∑ t = 1 T L t ( 0 ) . F_T^{\star}(-G_T) = F_T^{\star}\left(-\sum_{t=1}^{T} g_t\right) \le-\sum_{t=1}^{T}\langle g_t,x_t\rangle\le\sum_{t=1}^{T}\bigl(\mathcal{L}_t(0)-\mathcal{L}_t(x_t)\bigr) \le\sum_{t=1}^{T}\mathcal{L}_t(0). F T ⋆ ( − G T ) = F T ⋆ ( − t = 1 ∑ T g t ) ≤ − t = 1 ∑ T ⟨ g t , x t ⟩ ≤ t = 1 ∑ T ( L t ( 0 ) − L t ( x t ) ) ≤ t = 1 ∑ T L t ( 0 ) .
where in the second and third inequality we used the convexity and non-negativity of L t \mathcal{L}_t L t . Define B T : = ∑ t = 1 T L t ( 0 ) B_T := \sum_{t=1}^{T}\mathcal{L}_t(0) B T := ∑ t = 1 T L t ( 0 ) . Since S t ≥ 0 S_t \ge0 S t ≥ 0 , L t ( 0 ) = ∑ i = 1 d ( 1 − α i ) S t ≤ d S t \mathcal{L}_t(0) = \sum_{i=1}^{d}(1-\alpha_i)S_t \le dS_t L t ( 0 ) = ∑ i = 1 d ( 1 − α i ) S t ≤ d S t , so under Assumption 2.1 , B T ≤ d D T 1 + γ B_T \le dDT^{1+\gamma} B T ≤ d D T 1 + γ . Putting all together, we have the following theorem.
Theorem 3.4 (Miscoverage level set). Suppose Alg admits the linearized regret bound F T F_T F T on the gradient stream produced by Algorithm 1, and that each ( L t , K ) (\mathcal{L}_t,\mathcal{K}) ( L t , K ) satisfies inward flow. Then
F T ⋆ ( − G T ) ≤ B T , (5) F_T^\star(-G_T) \le B_T, \tag*{(5)} F T ⋆ ( − G T ) ≤ B T , (5) where F T ⋆ F_T^\star F T ⋆ is the Fenchel conjugate of F T F_T F T on R d \mathbb{R}^d R d . Equivalently, G T G_T G T lies in the level set
Z T ( F T ) : = { z ∈ R d : F T ⋆ ( − z ) ≤ B T } . (6) \mathcal{Z}_T(F_T) := \left\{z \in\mathbb{R}^d : F_T^\star(-z) \le B_T\right\}. \tag*{(6)} Z T ( F T ) := { z ∈ R d : F T ⋆ ( − z ) ≤ B T } . (6)
The proof follows that of Liu et al. [ [25 ] with Lemma 3.2 and convexity of L t \mathcal{L}_t L t in place of their Lemma A.1; the direct benefit of this combination is the generality of our results (Table 1 ). The geometry of the coverage-error region is characterized entirely in F T ⋆ F_T^\star F T ⋆ , and, through (3) , it dictates how the values M i s C o v T , i \mathrm{MisCov}_{T,i} MisCov T , i for i ∈ [ d ] i \in[d] i ∈ [ d ] are controlled. One implication is immediate: Smaller regret implies tighter coverage. In particular, optimizing the dependence of a regret bound on problem parameters directly tightens the coverage-error region. We show it formally in Appendix § 8 .§ 6 .
Remark 3.5. Ding et al. [ [14 ] demonstrated that naive approaches to combining single-level coverage with ordering constraints can fail: both post-hoc isotonic projection of independently coverage-controlled quantiles and (non-lazy) projected OGD on the aggregate pinball loss can break per-level coverage. Our results do not contradict their result. Instead, Algorithm 1 and Theorem 3.4 generalize their result by showing that any generic online learning algorithm can be used directly to obtain multi-level coverage . In fact, we can convert any regret bound for Alg into a deterministic constraint on the miscoverage components M i s C o v T , i \mathrm{MisCov}_{T,i} MisCov T , i , while guaranteeing distributional consistency too.
The next two subsections instantiate algorithms based on Algorithm 1 and Theorem 3.4.
Online mirror descent in the p p p -norm
Fix p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] and let q = p / ( p − 1 ) ∈ [ 2 , ∞ ) q = p/(p-1) \in[2,\infty) q = p / ( p − 1 ) ∈ [ 2 , ∞ ) . Take Alg to be Online Mirror Descent with regularizer ψ ( x ~ ) = 1 2 ∥ x ~ ∥ p 2 \psi(\widetilde{x}) = \frac{1}{2}\lVert\widetilde{x}\rVert_p^2 ψ ( x ) = 2 1 ∥ x ∥ p 2 and constant step size η > 0 \eta> 0 η > 0 , initialized at x ~ 1 = 0 \widetilde{x}_1 = 0 x 1 = 0 . The resulting wrapped algorithm has a standard mirror-descent dual-update form with an isotonic projection at prediction time; we defer the explicit pseudocode (Algorithm 3) to Appendix § 10 .§ 2 .
Standard mirror-descent analysis gives the regret bound and its conjugate [see, e.g., Orabona, [27 ] , Sec. 6.7]
F T ( u ) = ∥ u ∥ p 2 2 η + η 2 ( p − 1 ) ∑ t = 1 T ∥ g t ∥ q 2 , F T ⋆ ( θ ) = η 2 ∥ θ ∥ q 2 − η 2 ( p − 1 ) ∑ t = 1 T ∥ g t ∥ q 2 , F_T(u) = \frac{\lVert u\rVert_p^2}{2\eta} + \frac{\eta}{2(p-1)}\sum_{t=1}^{T}\lVert g_t\rVert_q^2,\qquad F_T^\star(\theta) = \frac{\eta}{2}\lVert\theta\rVert_q^2 - \frac{\eta}{2(p-1)}\sum_{t=1}^{T}\lVert g_t\rVert_q^2, F T ( u ) = 2 η ∥ u ∥ p 2 + 2 ( p − 1 ) η t = 1 ∑ T ∥ g t ∥ q 2 , F T ⋆ ( θ ) = 2 η ∥ θ ∥ q 2 − 2 ( p − 1 ) η t = 1 ∑ T ∥ g t ∥ q 2 ,
where the conjugate uses ( 1 2 ∥ ⋅ ∥ p 2 ) ⋆ = 1 2 ∥ ⋅ ∥ q 2 \left(\frac{1}{2}\lVert\cdot\rVert_p^2\right)^\star= \frac{1}{2}\lVert\cdot\rVert_q^2 ( 2 1 ∥ ⋅ ∥ p 2 ) ⋆ = 2 1 ∥ ⋅ ∥ q 2 . Substituting into Theorem 3.4 and bounding ∥ g t ∥ q ≤ d 1 / q \lVert g_t\rVert_q \le d^{1/q} ∥ g t ∥ q ≤ d 1/ q (since ∥ g t ∥ ∞ ≤ 1 \lVert g_t\rVert_\infty\le1 ∥ g t ∥ ∞ ≤ 1 ) yields the following ℓ q \ell_q ℓ q coverage-error ball.
Corollary 3.6 (ℓ q \ell_q ℓ q coverage-error ball). Algorithm 3 with step size η > 0 \eta> 0 η > 0 satisfies
max i ∈ [ d ] M i s C o v T , i ≤ ∥ G T ∥ q T ≤ 1 T 2 B T η + d 2 / q T p − 1 . (7) \max_{i\in[d]} \mathrm{MisCov}_{T,i} \le\frac{\lVert G_T\rVert_q}{T} \le\frac{1}{T}\sqrt{\frac{2B_T}{\eta}+\frac{d^{2/q}T}{p-1}}. \tag*{(7)} i ∈ [ d ] max MisCov T , i ≤ T ∥ G T ∥ q ≤ T 1 η 2 B T + p − 1 d 2/ q T . (7)
The bound (7) interpolates between the Euclidean case (q = 2 q=2 q = 2 , dependence d / T \sqrt{d/T} d / T ) and the geometry of the unit hypercube (q → ∞ q\to\infty q → ∞ ). We optimize the parameter pair ( p , η ) (p,\eta) ( p , η ) . Assuming d ≥ 3 d \ge3 d ≥ 3 and choosing q : = 2 log d q := 2\log d q := 2 log d (so p = 1 + 1 / ( 2 log d − 1 ) p = 1 + 1/(2\log d - 1) p = 1 + 1/ ( 2 log d − 1 ) and d 2 / q = e d^{2/q} = e d 2/ q = e ), the second term inside the square root becomes e ( 2 log d − 1 ) T e(2\log d - 1)T e ( 2 log d − 1 ) T . The right-hand side of (7) is strictly decreasing in η \eta η , so (7) alone would favor an arbitrarily large step size. We instead balance its two terms by setting η = 2 B T / ( e ( 2 log d − 1 ) T ) \eta= 2B_T/(e(2\log d - 1)T) η = 2 B T / ( e ( 2 log d − 1 ) T ) , which gives the η → ∞ \eta\to\infty η → ∞ limit up to a factor 2 \sqrt{2} 2 at a finite step size, and yields
max i ∈ [ d ] M i s C o v T , i ≤ ∥ G T ∥ 2 log d T ≤ 2 e ( 2 log d − 1 ) T = O ( log d T ) . \max_{i\in[d]} \mathrm{MisCov}_{T,i} \le\frac{\lVert G_T\rVert_{2\log d}}{T} \le\sqrt{\frac{2e(2\log d-1)}{T}} = O\left(\sqrt{\frac{\log d}{T}}\right). i ∈ [ d ] max MisCov T , i ≤ T ∥ G T ∥ 2 l o g d ≤ T 2 e ( 2 log d − 1 ) = O ( T log d ) .
A detailed derivation, including verification that the balanced η \eta η is well-defined under Assumption 2.1 , is in Appendix § 8 .§ 4 .
We emphasize that the log d \sqrt{\log d} log d dimension dependence represents an exponential improvement over the d \sqrt{d} d dependence of OGD, i.e., of MultiQT, which our analysis recovers as the p = 2 p = 2 p = 2 case. The improvement lies in d d d , not T T T : for a common point forecast with bounded scores, (our setting with γ = 0 \gamma= 0 γ = 0 ), Ding et al. [ [14 ] prove a fast O ( 1 / T ) O(1/T) O ( 1/ T ) rate for a fixed step size, for which the regret bound grows linearly in T T T , as for any constant step size; balancing the two yields O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) for both Ding et al., [14 ] . Appendix § 8 .9 states both regimes with constants.
The optimal step size η \eta η in p p p -norm OMD, as in MultiQT, depends on B T B_T B T , hence on the unknown polynomial-growth parameters D D D and γ \gamma γ . In Appendix § 10 .§ 5 , we give a heuristic and a doubling-trick variant with provable guarantees.
Coordinate-wise Universal Portfolio
The cleanest way to remove the dependence on B T B_T B T in the choice of step size is to replace OMD by a parameter-free algorithm Orabona, [27 ] . Since the aggregate pinball loss decomposes coordinate-wise, L t ( x ) = ∑ j = 1 d ℓ ( 1 − α j ) ( x j , S t ) \mathcal{L}_t(x) = \sum_{j=1}^{d} \ell^{(1-\alpha_j)}(x_j, S_t) L t ( x ) = ∑ j = 1 d ℓ ( 1 − α j ) ( x j , S t ) , a natural instantiation is to run an independent copy of the scalar universal-portfolio learner UP-OCP Liu et al., [25 ] at each level α j \alpha_j α j , with no shared state between levels, and to apply Algorithm 1 on the joint vector. We refer to this composed algorithm as coordinate-wise UP-OCP and defer the complete pseudocode (Algorithm 2) to Appendix § 10 .§ 2 .
The total regret of d d d independent instances is the sum of their per-coordinate regrets Orabona, [27 ] : F T ( u ) = ∑ j = 1 d F T ( j ) ( ∣ u j ∣ ) F_T(u) = \sum_{j=1}^{d} F_T^{(j)}(|u_j|) F T ( u ) = ∑ j = 1 d F T ( j ) ( ∣ u j ∣ ) , where F T ( j ) F_T^{(j)} F T ( j ) is the linearized-regret bound of UP-OCP at level α j \alpha_j α j Liu et al., [25 ] . The Fenchel conjugate factorizes accordingly, F T ∗ ( θ ) = ∑ j = 1 d ( F T ( j ) ) ∗ ( ∣ θ j ∣ ) F_T^*(\theta) = \sum_{j=1}^{d} (F_T^{(j)})^*(|\theta_j|) F T ∗ ( θ ) = ∑ j = 1 d ( F T ( j ) ) ∗ ( ∣ θ j ∣ ) , and Theorem 3.4 becomes
∑ j = 1 d ( F T ( j ) ) ∗ ( ∣ G T , j ∣ ) ≤ B T . (8) \sum_{j=1}^{d} (F_T^{(j)})^*(|G_{T,j}|) \le B_T. \tag*{(8)} j = 1 ∑ d ( F T ( j ) ) ∗ ( ∣ G T , j ∣ ) ≤ B T . (8)
The Fenchel conjugate of UP-OCP is non-decreasing in ∣ θ j ∣ |\theta_j| ∣ θ j ∣ and ( F T ( j ) ) ∗ ( 0 ) ≥ − 1 (F_T^{(j)})^*(0) \ge-1 ( F T ( j ) ) ∗ ( 0 ) ≥ − 1 , so dropping all but one term in (8) yields a per-coordinate budget of B T + d − 1 B_T + d - 1 B T + d − 1 . Inverting the resulting Bernstein-type inequality Liu et al., [25 ] gives the following theorem.
Theorem 3.7 (Per-level coverage of coordinate-wise UP-OCP). Run Algorithm 2. For every j ∈ [ d ] j \in[d] j ∈ [ d ] ,
MisCov T , j ≤ ε ^ T , j + 2 α j ( 1 − α j ) ε ^ T , j , ε ^ T , j : = 1 T [ ln ( B T + d ) + 1 2 ln ( π ( T + 1 ) ) ] . (9) \operatorname{MisCov}_{T,j} \le\widehat{\varepsilon}_{T,j} + \sqrt{2\alpha_j(1-\alpha_j)\widehat{\varepsilon}_{T,j}}, \qquad\widehat{\varepsilon}_{T,j} := \frac{1}{T}\left[\ln(B_T+d) + \frac{1}{2}\ln\bigl(\pi(T+1)\bigr)\right]. \tag*{(9)} MisCov T , j ≤ ε T , j + 2 α j ( 1 − α j ) ε T , j , ε T , j := T 1 [ ln ( B T + d ) + 2 1 ln ( π ( T + 1 ) ) ] . (9) In particular, with Assumption 2.1 , max j ∈ [ d ] MisCov T , j = O ( ( 1 + γ ) log T + log d T ) \max_{j\in[d]} \operatorname{MisCov}_{T,j} = O\left(\sqrt{\frac{(1+\gamma)\log T+\log d}{T}}\right) max j ∈ [ d ] MisCov T , j = O ( T ( 1 + γ ) l o g T + l o g d ) .
The per-level rate matches the p p p -norm bound of Corollary 3.6 in its dependence on d d d , up to an additional log T \log T log T factor that is the price of being parameter-free. Crucially, no quantity used by the algorithm requires knowledge of D D D , γ \gamma γ , or T T T . The factor α j ( 1 − α j ) \alpha_j(1-\alpha_j) α j ( 1 − α j ) also guarantees a faster rate for extreme quantile levels.
Extensions to continuous quantile levels. An important advantage of our framework is that it can be easily generalized from a finite collection A = { α 1 , … , α d } \mathcal{A} = \{\alpha_1,\ldots,\alpha_d\} A = { α 1 , … , α d } to a compact interval I ⊆ ( 0 , 1 ) \mathcal{I} \subseteq(0,1) I ⊆ ( 0 , 1 ) by replacing R d \mathbb{R}^d R d with the Hilbert space H = L 2 ( I , μ ) \mathcal{H} = L^2(\mathcal{I},\mu) H = L 2 ( I , μ ) for a finite Borel reference measure μ \mu μ with full support, and replacing the isotonic cone by the cone of non-increasing functions. We collect the formal statements, including a coordinate-wise UP-OCP analogue obtained via Donsker–Varadhan change-of-measure, in Appendix § 8 .8.
Sharpness and coverage improvement of isotonic projection
Section 3 used the lazy projection structurally, to make the played iterate feasible without inflating the coverage bound. We now show that it does strictly more: whenever the hidden iterate x ~ t \tilde{x}_t x ~ t violates isotonicity, projecting it onto K K K strictly reduces a measure of prediction width while weakly reducing a measure of miscoverage, so the empirical Pareto frontier of width versus coverage shifts monotonically toward the ideal corner of small width and accurate coverage.
We frame our analysis in terms of the Weighted Interval Score (WIS) [9 ] , the standard scoring rule for assessing multi-level interval forecasts. WIS is an extension of the classical Interval Score [18 , 41 ] to the multi-level setting. For a collection of interval forecasts [ l α , u α ] [l_\alpha, u_\alpha] [ l α , u α ] , α ∈ A \alpha\in\mathcal{A} α ∈ A , the WIS is defined as
WIS A ( { [ l α , u α ] } α ∈ A , y ) : = ∑ α ∈ A α ( u α − l α ) + ∑ α ∈ A 2 ⋅ dist ( y , [ l α , u α ] ) , (10) \operatorname{WIS}_{\mathcal{A}}\left(\{[l_\alpha,u_\alpha]\}_{\alpha\in\mathcal{A}},y\right) := \sum_{\alpha\in\mathcal{A}} \alpha\left(u_\alpha-l_\alpha\right) + \sum_{\alpha\in\mathcal{A}} 2\cdot\operatorname{dist}\left(y,[l_\alpha,u_\alpha]\right), \tag*{(10)} WIS A ( {[ l α , u α ] } α ∈ A , y ) := α ∈ A ∑ α ( u α − l α ) + α ∈ A ∑ 2 ⋅ dist ( y , [ l α , u α ] ) , (10)
where dist ( y , [ l α , u α ] ) = inf x ∈ [ l α , u α ] ∣ y − x ∣ \operatorname{dist}(y,[l_\alpha,u_\alpha]) = \inf_{x\in[l_\alpha,u_\alpha]} |y-x| dist ( y , [ l α , u α ]) = inf x ∈ [ l α , u α ] ∣ y − x ∣ . For symmetric prediction sets 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] C t ( Y t , x ) = [ Y t − x , Y t + x ] at miscoverage levels A = { α 1 , … , α d } \mathcal{A} = \{\alpha_1,\ldots,\alpha_d\} A = { α 1 , … , α d } , a direct calculation (Appendix § 9 .§ 1 ) gives
L t ( x ) + S t ∑ i = 1 d α i = 1 2 WIS A ( { C ^ t ( Y ^ t , x i ) } i , Y t ) = ∑ i = 1 d α i x i + ∑ i = 1 d max ( S t − x i , 0 ) . (11) \mathcal{L}_t(x) + S_t \sum_{i=1}^{d}\alpha_i = \frac{1}{2}\operatorname{WIS}_{\mathcal{A}}\left(\left\{\widehat{C}_t(\widehat{Y}_t,x_i)\right\}_{i},Y_t\right) = \sum_{i=1}^{d}\alpha_i x_i + \sum_{i=1}^{d}\max(S_t-x_i,0). \tag*{(11)} L t ( x ) + S t i = 1 ∑ d α i = 2 1 WIS A ( { C t ( Y t , x i ) } i , Y t ) = i = 1 ∑ d α i x i + i = 1 ∑ d max ( S t − x i , 0 ) . (11)
This means that, up to an additive term that is constant in x t x_t x t , the aggregate pinball loss is half the WIS of our prediction sets. The sharpness term is an α \alpha α -weighted measure of total predicted width, with higher miscoverage levels (smaller intervals) weighted more; the coverage penalty ∑ i max ( S t − x i , 0 ) \sum_i \max(S_t-x_i,0) ∑ i max ( S t − x i , 0 ) is a one-sided ℓ 1 \ell_1 ℓ 1 residual that penalizes under-coverage at every level.
Our main result in this section is that the projection step in Algorithm 1 reduces both terms of (11) at every round (and hence WIS itself), and strictly so whenever the hidden iterate is not already isotonic.
Theorem 4.1 (Per-round reduction). For every round t t t , the hidden iterate x ~ t ∈ R + d \tilde{x}_t \in\mathbb{R}_+^d x ~ t ∈ R + d and the played iterate x t = Π K ( x ~ t ) ∈ K ∩ R + d x_t = \Pi_K(\tilde{x}_t) \in K \cap\mathbb{R}_+^d x t = Π K ( x ~ t ) ∈ K ∩ R + d satisfy L t ( x t ) ≤ L t ( x ~ t ) \mathcal{L}_t(x_t) \le\mathcal{L}_t(\tilde{x}_t) L t ( x t ) ≤ L t ( x ~ t ) . Moreover, both the α \alpha α -weighted prediction sum and the total coverage penalty are individually reduced:
∑ i = 1 d α i x t , i ≤ ∑ i = 1 d α i x ~ t , i and ∑ i = 1 d max ( S t − x t , i , 0 ) ≤ ∑ i = 1 d max ( S t − x ~ t , i , 0 ) . (12) \sum_{i=1}^{d}\alpha_i x_{t,i} \le\sum_{i=1}^{d}\alpha_i\tilde{x}_{t,i}
\qquad\text{and}\qquad
\sum_{i=1}^{d}\max(S_t-x_{t,i},0) \le\sum_{i=1}^{d}\max(S_t-\tilde{x}_{t,i},0). \tag*{(12)} i = 1 ∑ d α i x t , i ≤ i = 1 ∑ d α i x ~ t , i and i = 1 ∑ d max ( S t − x t , i , 0 ) ≤ i = 1 ∑ d max ( S t − x ~ t , i , 0 ) . (12) When x ~ t ∉ K \tilde{x}_t \notin K x ~ t ∈ / K , the sharpness reduction and the loss reduction are strict.
The proof hinges on the characterization of Pool-Adjacent-Violators (PAVA) algorithm used for the isotonic projection [30 ] . The full proof, including the supporting lemmas, is in Appendix § 9 .§ 2 . The inequalities hold for any x ~ t ∈ R d \tilde{x}_t \in\mathbb{R}^d x ~ t ∈ R d ; with valid hidden radii (§ 3 ), both sides are WIS components of genuine prediction intervals, since PAVA averages non-negative radii.
Ding et al. [ [14 ] obtained a decomposition analogous to (11) under the assumption that A \mathcal{A} A is symmetric about 1 / 2 1/2 1/2 , but they only used it as a motivation to minimize the regret with L t \mathcal{L}_t L t . In fact, they observed a better empirical performance of MultiQT compared to the naive forecasters , but they did not provide any explanation for it. Our Theorem 4.1 provides this missing explanation.
Experiments
Here, we evaluate our framework on both synthetic and real-world datasets.
Datasets. We follow the OCP literature [1 , 16 , 17 , 29 ] and use three categories of streams: (1) daily opening prices of major US stocks (AAPL, AMZN, GOOGL) from 2006 to 2017 [Nguyen, 2018]; (2) electricity demand records from New South Wales [20 ] ; and (3) synthetic environments following [1 App. F.5] that bypass forecasting and directly simulate the nonconformity scores S t S_t S t under three patterns (sinusoidal with Gaussian noise; constant and quadratic trends with sparse bumps), allowing repeated runs for error bars. Forecasting pipelines (daily-refit Prophet for stocks [38 ] , AR(3) for electricity) and full synthetic-stream specifications are in Appendix § 10 .§ 1 .
Methods. We compare four method families: UP-OCP (Algorithm 2, parameter-free), p -norm OMD (Algorithm 3, with p = 2 log d / ( 2 log d − 1 ) p=2\log d/(2\log d-1) p = 2 log d / ( 2 log d − 1 ) from Corollary 3.6 and a constant step size chosen per dataset by oracle grid search on a base-2 logarithmic grid), KT (Algorithm 4, parameter-free reference), and the OGD-based prior baseline MultiQT [14 ] (adaptive; uses a data-dependent learning-rate schedule). The first three are run both as vanilla learners and wrapped with the lazy projection of Algorithm 1 (suffix -Iso); MultiQT is by construction projected. Update rules, hyperparameter grids, and selected η \eta η values are in Appendix § 10 .§ 2 .
Metrics. We track, per method, (1) the empirical coverage Coverage T , j \operatorname{Coverage}_{T,j} Coverage T , j as a function of the target 1 − α 1-\alpha 1 − α ; (2) the per-round prediction-set width ∣ C ^ t ( Y ^ t , x t , j ) ∣ \lvert\widehat{C}_{t}(\widehat{Y}_{t},x_{t,j})\rvert ∣ C t ( Y t , x t , j )∣ , summarized by its mean (the standard sharpness measure), median, and 95th percentile; (3) the full distribution of widths at selected levels; and (4) the WIS ((10) ), summed over all d d d levels and averaged over rounds, with its two components.
The scores are the absolute residuals S t = ∣ Y t − Y ^ t ∣ S_t=\lvert Y_t-\widehat{Y}_t\rvert S t = ∣ Y t − Y t ∣ ; none is exactly zero (the smallest is about 10 − 5 10^{-5} 1 0 − 5 ), so the empty-set convention never changes a coverage indicator. In all cases we calibrate d = 100 d=100 d = 100 levels uniformly spaced in [ 0.001 , 0.5 ] [0.001,0.5] [ 0.001 , 0.5 ] for each method, with warm-up periods of T b u r n - i n = 100 T_{\mathrm{burn\text{-}in}}=100 T burn - in = 100 rounds (300 for elec2) during which the predictor outputs sets but is not updated. Results are reported on the practically interesting window α ∈ [ 0.03 , 0.25 ] \alpha\in[0.03,0.25] α ∈ [ 0.03 , 0.25 ] (target coverage 1 − α ∈ [ 0.75 , 0.97 ] 1-\alpha\in[0.75,0.97] 1 − α ∈ [ 0.75 , 0.97 ] ). We focus on the AAPL dataset and the synthetic sinusoidal stream; full results for the other datasets are in Appendix § 10 .
Calibration and Pareto frontiers
Higher coverage requires larger sets, but this trade-off varies across algorithms. Following Liu et al. [ [25 ] , we assess it through a Pareto frontier : Figure 1 shows, per dataset, a calibration curve (left) and the empirical coverage against the mean width (right) for α ∈ [ 0.03 , 0.25 ] \alpha\in[0.03,0.25] α ∈ [ 0.03 , 0.25 ] . We prioritize the mean width, which reflects the cumulative cost of uncertainty downstream and, unlike quantiles of the width, captures unreasonably large sets. We exclude KT, whose width is substantially larger at almost all levels and would compress every other curve; it is included in Figure 2 and Appendix § 10 . Several observations follow.
Figure 1. Calibration (left column: empirical versus target coverage 1 − α 1-\alpha 1 − α ) and Pareto frontiers (right column: empirical coverage versus mean prediction-set width), for AAPL (top row) and the sinusoidal dataset (bottom row, mean across 10 seeds). The solid diagonal implies perfect calibration y = x y=x y = x , the dotted lines are the ± 0.03 \pm0.03 ± 0.03 error band. Better performance is closer to the bottom-left corner.
Figure 2. Average per-round WIS over all d = 100 d = 100 d = 100 levels (post burn-in; sinusoidal: mean over 10 seeds), split into the sharpness (solid) and coverage-penalty (hatched) components of (10) . Percentages give the change of each projected variant relative to its unprojected counterpart.
Calibration is preserved by the projection. In each calibration panel, the projected (ISO) and unprojected curves are visually indistinguishable; the p p p -norm curves lie inside the ± 0.03 \pm0.03 ± 0.03 tolerance band over the entire α \alpha α window, and the UP-OCP curves leave it only slightly, at the lowest target coverages. This is consistent with Proposition 3.3 : the projection does not consume any regret, so it does not consume any coverage.
Sharpness is strictly improved by the projection, for almost all α \alpha α . On the right-hand panels, every solid (-Iso) curve sits on or to the left of its dashed (unprojected) counterpart, i.e., it is narrower at the same coverage, with the gap widening at small α \alpha α (high coverage), where the hidden iterate is most likely to violate isotonicity. The reduction is largest for p p p -norm OMD, whose unprojected mean width is up to 33% (AAPL) and 39% (sinusoidal) larger than the projected one near 1 − α = 0.97 1 - \alpha= 0.97 1 − α = 0.97 ; for UP-OCP it is about 7–8%.
Coordinate-wise UP-OCP uniformly improves over p p p -norm OMD and MultiQT in width. On AAPL, UP-OCP-ISO is narrower than both p p p -norm OMD variants and MultiQT at every α \alpha α . On AAPL, tuned p p p -norm OMD with the optimal p p p achieves the highest empirical coverage but pays for it with much wider sets. On both datasets, the constant step size selected from our grid by Pareto dominance is η = 64 \eta= 64 η = 64 . Oracle tuning gives p p p -norm OMD an advantage that is unavailable in practice, while UP-OCP and KT are parameter-free; still, the results are not fragile to it: every η ∈ [ 16 , 128 ] \eta\in[16, 128] η ∈ [ 16 , 128 ] stays within about 10% of the best WIS on both datasets, and a plug-in step size using only revealed scores comes within 4% (Appendix § 10 .§ 5 ).
Remark 5.1 (Slight miscoverage of the parameter-free and adaptive instances). There is a fundamental trade-off between marginal coverage and prediction set size in OCP, as shown in recent lower bounds arguments [37 ] : any algorithm whose prediction sets have size at most μ \mu μ times the optimal must incur Ω ( log ( 1 / ϵ min ) / log μ ⋅ α T ) \Omega(\log(1/\epsilon_{\min})/\log\mu\cdot\alpha T) Ω ( log ( 1/ ϵ m i n ) / log μ ⋅ α T ) coverage errors, where ϵ min \epsilon_{\min} ϵ m i n is the smallest relevant scale. As suggested by Liu et al. [ [25 ] , empirically, this can be fixed by a simple α \alpha α -correction technique.
Tables in Appendix § 10 .7 report the same comparison at three representative target-coverage levels 1 − α ∈ { 0.95 , 0.9 , 0.8 } 1 - \alpha\in\{0.95, 0.9, 0.8\} 1 − α ∈ { 0.95 , 0.9 , 0.8 } for every dataset, including KT and the median and 95th-percentile widths (Table 6 for AAPL).
Table 6. AAPL: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
Weighted Interval Score. The projection lowers the total WIS (Figure 2 ) of every base learner on both datasets, most for p p p -norm OMD (−10.9% on AAPL, −12.5% on the sinusoidal stream), and UP-OCP-ISO attains the smallest WIS on both. Since Figure 2 compares runs with different trajectories, we also checked Theorem 4.1 in its exact within-run form: the hidden iterate violates isotonicity in 99.6% of the rounds, and in every one of them the projection strictly reduced the WIS and its sharpness component without increasing the coverage penalty (Appendix § 10 .§ 4 , which also reports the WIS on every dataset).
Further results. The projection also removes the heavy right tail of the per-round width distribution (Appendix C.3). As d d d grows from 5 to 1,000 on the sinusoidal stream, the realized worst-level errors grow at most slowly, so the worst-case d \sqrt{d} d and log d \sqrt{\log d} log d scalings are not visible there; the methods designed through the tighter analysis are nonetheless more accurate at every d d d (Appendix § 10 .§ 6 ).
Conclusion, limitations, and future work
We presented a black-box reduction that turns any online learner with a linearized regret bound into a multi-level OCP algorithm with multi-level coverage , by wrapping the learner in a lazy isotonic projection layer. The reduction preserves regret (and therefore coverage) while strictly improving sharpness, formalized through the Weighted Interval Score. Instantiating the framework with p p p -norm OMD and coordinate-wise Universal Portfolio replaces the d \sqrt{d} d dependence in the per-level miscoverage rate of MultiQT with log d \sqrt{\log d} log d , with the coordinate-wise Universal Portfolio instantiation being parameter-free. Extensive experiments confirm that the projection wrapper is a free (in terms of order of computational complexity) per-round improvement on every base learner we tested, and that UP-OCP delivers smaller and better-behaved prediction sets than the tuned baselines.
Limitations and future work. Our guarantees concern long-run marginal coverage , the standard target in adversarial OCP. Coverage conditional on groups (attainable at a single level [6 ] ) or on time intervals remains open in the multi-level setting and would likely require multi-validity [5 ] or strongly adaptive online learning [7 ] .
Acknowledgements
ED’s work was supported in part by the US NSF, ARO, ONR, and the Sloan Foundation.
Deferred Proofs and supporting material for Section 3
This appendix collects the proofs and auxiliary results deferred from § 3 . We restate each statement before its proof. Throughout, we write
δ T : = G T T ∈ R d \delta_T := \frac{G_T}{T} \in\mathbb{R}^d δ T := T G T ∈ R d
for the time-averaged cumulative subgradient, so that δ T , i = G T , i / T \delta_{T,i}=G_{T,i}/T δ T , i = G T , i / T is the per-level coverage gap and (3) reads MisCov T , i = ∣ δ T , i ∣ \operatorname{MisCov}_{T,i} = \lvert\delta_{T,i}\rvert MisCov T , i = ∣ δ T , i ∣ .
Projection inequality (Lemma 3.2)
We first record an immediate consequence of inward flow, then prove Lemma 3.2 . The argument is in R d \mathbb{R}^d R d , but every step extends verbatim to a Hilbert space, which is exploited in Appendix § 8 .8. Recall the normal cone of a closed convex set C C C at x ∈ C x \in C x ∈ C , N C ( x ) : = { v ∈ R d : ⟨ v , y − x ⟩ ≤ 0 for all y ∈ C } N_C(x) := \{v \in\mathbb{R}^d : \langle v, y-x\rangle\le0\text{ for all }y \in C\} N C ( x ) := { v ∈ R d : ⟨ v , y − x ⟩ ≤ 0 for all y ∈ C } , is the polar of the tangent cone T C ( x ) T_C(x) T C ( x ) , i.e., ⟨ v , w ⟩ ≤ 0 \langle v,w\rangle\le0 ⟨ v , w ⟩ ≤ 0 for every v ∈ N C ( x ) v \in N_C(x) v ∈ N C ( x ) and w ∈ T C ( x ) w \in T_C(x) w ∈ T C ( x ) [31 Sec. 6] .
Lemma A.1. Let ℓ \ell ℓ with subgradient g g g and a closed convex set C ⊆ R d C \subseteq\mathbb{R}^d C ⊆ R d satisfy inward flow. For every x ∈ bd ( C ) x \in\operatorname{bd}(C) x ∈ bd ( C ) and v ∈ N C ( x ) v \in N_C(x) v ∈ N C ( x ) , ⟨ v , g ( x ) ⟩ ≥ 0 \langle v,g(x)\rangle\ge0 ⟨ v , g ( x )⟩ ≥ 0 .
Proof. By inward flow, − g ( x ) ∈ T C ( x ) -g(x) \in T_C(x) − g ( x ) ∈ T C ( x ) . By tangent–normal cone polarity, ⟨ v , − g ( x ) ⟩ ≤ 0 \langle v,-g(x)\rangle\le0 ⟨ v , − g ( x )⟩ ≤ 0 for every v ∈ N C ( x ) v \in N_C(x) v ∈ N C ( x ) , i.e., ⟨ v , g ( x ) ⟩ ≥ 0 \langle v,g(x)\rangle\ge0 ⟨ v , g ( x )⟩ ≥ 0 . □ \square □
Proof of Lemma 3.2 . If x ~ ∈ C \tilde{x} \in C x ~ ∈ C , then Π C ( x ~ ) = x ~ \Pi_C(\tilde{x})=\tilde{x} Π C ( x ~ ) = x ~ and the inequality is an equality. Otherwise, let x 0 = Π C ( x ~ ) x_0=\Pi_C(\tilde{x}) x 0 = Π C ( x ~ ) . By the variational characterization of Euclidean projection, there exists v ∈ N C ( x 0 ) v \in N_C(x_0) v ∈ N C ( x 0 ) such that x ~ = x 0 + v \tilde{x}=x_0+v x ~ = x 0 + v . Then
⟨ g ( x 0 ) , x ~ ⟩ = ⟨ g ( x 0 ) , x 0 ⟩ + ⟨ g ( x 0 ) , v ⟩ ≥ ⟨ g ( x 0 ) , x 0 ⟩ , \langle g(x_0),\tilde{x}\rangle=\langle g(x_0),x_0\rangle+\langle g(x_0),v\rangle\ge\langle g(x_0),x_0\rangle, ⟨ g ( x 0 ) , x ~ ⟩ = ⟨ g ( x 0 ) , x 0 ⟩ + ⟨ g ( x 0 ) , v ⟩ ≥ ⟨ g ( x 0 ) , x 0 ⟩ ,
where the inequality is Lemma A.1 with x = x 0 ∈ bd ( C ) x=x_0\in\operatorname{bd}(C) x = x 0 ∈ bd ( C ) . □ \square □
Regret preservation and the central inequality
Proof of Proposition 3.3. By convexity of L t L_t L t and g t ∈ ∂ L t ( x t ) g_t\in\partial L_t(x_t) g t ∈ ∂ L t ( x t ) , L t ( x t ) − L t ( u ) ≤ ⟨ g t , x t − u ⟩ L_t(x_t)-L_t(u)\le\langle g_t,x_t-u\rangle L t ( x t ) − L t ( u ) ≤ ⟨ g t , x t − u ⟩ . Summing over t t t gives Regret T ( u ) ≤ LinRegret T ( u ) \operatorname{Regret}_T(u)\le\operatorname{LinRegret}_T(u) Regret T ( u ) ≤ LinRegret T ( u ) , so the bound (4) proved below also bounds the regret. By Lemma 3.2 applied to C = K C=K C = K , ⟨ g t , x t ⟩ ≤ ⟨ g t , x ~ t ⟩ \langle g_t,x_t\rangle\le\langle g_t,\tilde{x}_t\rangle ⟨ g t , x t ⟩ ≤ ⟨ g t , x ~ t ⟩ for every t t t , so
∑ t = 1 T ⟨ g t , x t − u ⟩ ≤ ∑ t = 1 T ⟨ g t , x ~ t − u ⟩ ≤ F T ( u ) , \sum_{t=1}^{T}\langle g_t,x_t-u\rangle\le\sum_{t=1}^{T}\langle g_t,\tilde{x}_t-u\rangle\le F_T(u), t = 1 ∑ T ⟨ g t , x t − u ⟩ ≤ t = 1 ∑ T ⟨ g t , x ~ t − u ⟩ ≤ F T ( u ) ,
where the last step is the regret bound of Alg. □ \square □
Proof of Theorem 3.4. By regret-reward duality [27 Sec. 6.4] , the regret bound of Alg is equivalent to F T ∗ ( − ∑ t = 1 T g t ) ≤ − ∑ t = 1 T ⟨ g t , x ~ t ⟩ F_T^*(-\sum_{t=1}^{T}g_t)\le-\sum_{t=1}^{T}\langle g_t,\tilde{x}_t\rangle F T ∗ ( − ∑ t = 1 T g t ) ≤ − ∑ t = 1 T ⟨ g t , x ~ t ⟩ . Inward flow of ( L t , K ) (L_t,K) ( L t , K ) together with Lemma 3.2 gives ⟨ g t , x t ⟩ ≤ ⟨ g t , x ~ t ⟩ \langle g_t,x_t\rangle\le\langle g_t,\tilde{x}_t\rangle ⟨ g t , x t ⟩ ≤ ⟨ g t , x ~ t ⟩ , hence − ⟨ g t , x ~ t ⟩ ≤ − ⟨ g t , x t ⟩ -\langle g_t,\tilde{x}_t\rangle\le-\langle g_t,x_t\rangle − ⟨ g t , x ~ t ⟩ ≤ − ⟨ g t , x t ⟩ . Convexity of L t L_t L t at x t x_t x t with comparator 0 0 0 yields
L t ( 0 ) ≥ L t ( x t ) + ⟨ g t , 0 − x t ⟩ ⟹ − ⟨ g t , x t ⟩ ≤ L t ( 0 ) − L t ( x t ) ≤ L t ( 0 ) , L_t(0)\ge L_t(x_t)+\langle g_t,0-x_t\rangle\quad\Longrightarrow\quad-\langle g_t,x_t\rangle\le L_t(0)-L_t(x_t)\le L_t(0), L t ( 0 ) ≥ L t ( x t ) + ⟨ g t , 0 − x t ⟩ ⟹ − ⟨ g t , x t ⟩ ≤ L t ( 0 ) − L t ( x t ) ≤ L t ( 0 ) ,
where we used L t ( x t ) ≥ 0 L_t(x_t)\ge0 L t ( x t ) ≥ 0 since each pinball loss is non-negative. Summing over t t t gives
F T ∗ ( − G T ) ≤ − ∑ t = 1 T ⟨ g t , x ~ t ⟩ ≤ ∑ t = 1 T L t ( 0 ) = B T . F_T^*(-G_T)\le-\sum_{t=1}^{T}\langle g_t,\tilde{x}_t\rangle\le\sum_{t=1}^{T}L_t(0)=B_T. F T ∗ ( − G T ) ≤ − t = 1 ∑ T ⟨ g t , x ~ t ⟩ ≤ t = 1 ∑ T L t ( 0 ) = B T .
Inward flow for the isotonic cone
Verification of inward flow for the isotonic cone. Fix t t t and x ∈ bd ( K ) x \in\operatorname{bd}(\mathcal{K}) x ∈ bd ( K ) . Let I ( x ) : = { i ∈ [ d − 1 ] : x i = x i + 1 } I(x) := \{i \in[d-1] : x_i = x_{i+1}\} I ( x ) := { i ∈ [ d − 1 ] : x i = x i + 1 } be the set of tight constraints; I ( x ) I(x) I ( x ) is non-empty since x x x is on the boundary. Because K \mathcal{K} K is polyhedral with constraints x i − x i + 1 ≥ 0 x_i-x_{i+1} \ge0 x i − x i + 1 ≥ 0 , the tangent cone at x x x is
T K ( x ) = { v ∈ R d : v i − v i + 1 ≥ 0 for every i ∈ I ( x ) } . T_{\mathcal{K}}(x) = \{v \in\mathbb{R}^{d} : v_i-v_{i+1} \ge0 \text{ for every } i \in I(x)\}. T K ( x ) = { v ∈ R d : v i − v i + 1 ≥ 0 for every i ∈ I ( x )} .
Inward flow asks − g t ∈ T K ( x ) -g_t \in T_{\mathcal{K}}(x) − g t ∈ T K ( x ) , equivalently g t , i ≤ g t , i + 1 g_{t,i} \le g_{t,i+1} g t , i ≤ g t , i + 1 for every i ∈ I ( x ) i \in I(x) i ∈ I ( x ) . With the subgradient (2) , we have g t , i = 1 { x i ≥ S t } − ( 1 − α i ) g_{t,i} = \mathbb{1}\{x_i \ge S_t\}-(1-\alpha_i) g t , i = 1 { x i ≥ S t } − ( 1 − α i ) , where the coverage indicator follows the empty-set convention of Section 2; in particular, it depends on x i x_i x i only through its value, so tied coordinates share it. Take i ∈ I ( x ) i \in I(x) i ∈ I ( x ) so that x i = x i + 1 x_i=x_{i+1} x i = x i + 1 .
Case 1: both levels cover, i.e., x i = x i + 1 ≥ S t x_i=x_{i+1} \ge S_t x i = x i + 1 ≥ S t and x i > 0 x_i>0 x i > 0 . Then g t , i = α i g_{t,i}=\alpha_i g t , i = α i and g t , i + 1 = α i + 1 g_{t,i+1}=\alpha_{i+1} g t , i + 1 = α i + 1 . Since α i < α i + 1 \alpha_i<\alpha_{i+1} α i < α i + 1 , g t , i < g t , i + 1 g_{t,i}<g_{t,i+1} g t , i < g t , i + 1 .
Case 2: neither level covers, i.e., x i = x i + 1 < S t x_i=x_{i+1}<S_t x i = x i + 1 < S t , or x i = x i + 1 = 0 x_i=x_{i+1}=0 x i = x i + 1 = 0 (the empty set). Then g t , i = − ( 1 − α i ) g_{t,i}=-(1-\alpha_i) g t , i = − ( 1 − α i ) and g t , i + 1 = − ( 1 − α i + 1 ) g_{t,i+1}=-(1-\alpha_{i+1}) g t , i + 1 = − ( 1 − α i + 1 ) . Since α i < α i + 1 \alpha_i<\alpha_{i+1} α i < α i + 1 , 1 − α i > 1 − α i + 1 1-\alpha_i>1-\alpha_{i+1} 1 − α i > 1 − α i + 1 , hence g t , i < g t , i + 1 g_{t,i}<g_{t,i+1} g t , i < g t , i + 1 .
In either case g t , i ≤ g t , i + 1 g_{t,i}\le g_{t,i+1} g t , i ≤ g t , i + 1 , completing the proof.
Detailed derivation for Corollary 3.6: p p p -norm OMD
The regret bound for p p p -norm OMD with regularizer ψ ( x ) = ( 1 / 2 ) ∥ x ∥ p 2 \psi(x)=(1/2)\|x\|_p^2 ψ ( x ) = ( 1/2 ) ∥ x ∥ p 2 at constant step size η > 0 \eta>0 η > 0 is standard [27 Theorem 6.8] : ψ \psi ψ is ( p − 1 ) (p-1) ( p − 1 ) -strongly convex with respect to ∥ ⋅ ∥ p \|\cdot\|_p ∥ ⋅ ∥ p by [36 Lemma 6.36] , yielding
F T ( u ) = ∥ u ∥ p 2 2 η + η 2 ( p − 1 ) ∑ t = 1 T ∥ g t ∥ q 2 . F_T(u)=\frac{\|u\|_p^2}{2\eta}+\frac{\eta}{2(p-1)}\sum_{t=1}^{T}\|g_t\|_q^2. F T ( u ) = 2 η ∥ u ∥ p 2 + 2 ( p − 1 ) η t = 1 ∑ T ∥ g t ∥ q 2 .
The Fenchel conjugate of a ∥ ⋅ ∥ q 2 a\|\cdot\|_q^2 a ∥ ⋅ ∥ q 2 is ( 1 / ( 4 a ) ) ∥ ⋅ ∥ q 2 (1/(4a))\|\cdot\|_q^2 ( 1/ ( 4 a )) ∥ ⋅ ∥ q 2 . Applying this with a = 1 / ( 2 η ) a=1/(2\eta) a = 1/ ( 2 η ) and absorbing the additive T T T -dependent term gives
F T ∗ ( θ ) = η 2 ∥ θ ∥ q 2 − η 2 ( p − 1 ) ∑ t = 1 T ∥ g t ∥ q 2 . F_T^*(\theta)=\frac{\eta}{2}\|\theta\|_q^2-\frac{\eta}{2(p-1)}\sum_{t=1}^{T}\|g_t\|_q^2. F T ∗ ( θ ) = 2 η ∥ θ ∥ q 2 − 2 ( p − 1 ) η t = 1 ∑ T ∥ g t ∥ q 2 .
The central inequality (5) then becomes ( η / 2 ) ∥ G T ∥ q 2 − ( η / ( 2 ( p − 1 ) ) ) ∑ t = 1 T ∥ g t ∥ q 2 ≤ B T (\eta/2)\|G_T\|_q^2-(\eta/(2(p-1)))\sum_{t=1}^{T}\|g_t\|_q^2 \le B_T ( η /2 ) ∥ G T ∥ q 2 − ( η / ( 2 ( p − 1 ))) ∑ t = 1 T ∥ g t ∥ q 2 ≤ B T , i.e.,
∥ G T ∥ q 2 ≤ 2 B T η + 1 p − 1 ∑ t = 1 T ∥ g t ∥ q 2 . \|G_T\|_q^2 \le\frac{2B_T}{\eta}+\frac{1}{p-1}\sum_{t=1}^{T}\|g_t\|_q^2. ∥ G T ∥ q 2 ≤ η 2 B T + p − 1 1 t = 1 ∑ T ∥ g t ∥ q 2 .
Since ∥ g t ∥ ∞ ≤ 1 \|g_t\|_\infty\le1 ∥ g t ∥ ∞ ≤ 1 and ∥ g t ∥ q ≤ d 1 / q ∥ g t ∥ ∞ ≤ d 1 / q \|g_t\|_q\le d^{1/q}\|g_t\|_\infty\le d^{1/q} ∥ g t ∥ q ≤ d 1/ q ∥ g t ∥ ∞ ≤ d 1/ q by Hölder, ∑ t = 1 T ∥ g t ∥ q 2 ≤ d 2 / q T \sum_{t=1}^{T}\|g_t\|_q^2\le d^{2/q}T ∑ t = 1 T ∥ g t ∥ q 2 ≤ d 2/ q T .
For the optimization, set q = 2 log d q=2\log d q = 2 log d . Then p − 1 = 1 / ( q − 1 ) = 1 / ( 2 log d − 1 ) p-1=1/(q-1)=1/(2\log d-1) p − 1 = 1/ ( q − 1 ) = 1/ ( 2 log d − 1 ) and d 2 / q = d 1 / log d = e d^{2/q}=d^{1/\log d}=e d 2/ q = d 1/ l o g d = e . Plugging in,
∥ G T ∥ q 2 ≤ 2 B T η + e ( 2 log d − 1 ) T . \|G_T\|_q^2\le\frac{2B_T}{\eta}+e(2\log d-1)T. ∥ G T ∥ q 2 ≤ η 2 B T + e ( 2 log d − 1 ) T .
Setting η : = 2 B T / ( e ( 2 log d − 1 ) T ) \eta:=2B_T/(e(2\log d-1)T) η := 2 B T / ( e ( 2 log d − 1 ) T ) balances the two terms and gives ∥ G T ∥ q 2 ≤ 2 e ( 2 log d − 1 ) T \|G_T\|_q^2\le2e(2\log d-1)T ∥ G T ∥ q 2 ≤ 2 e ( 2 log d − 1 ) T . This choice of η \eta η is well-defined whenever B T > 0 B_T>0 B T > 0 ; the trivial case B T = 0 B_T=0 B T = 0 corresponds to S t = 0 S_t=0 S t = 0 for all t t t , where (7) holds for every η > 0 \eta>0 η > 0 and already gives ∥ G T ∥ q 2 ≤ e ( 2 log d − 1 ) T \|G_T\|_q^2\le e(2\log d-1)T ∥ G T ∥ q 2 ≤ e ( 2 log d − 1 ) T . Under Assumption 2.1, the upper bound B T ≤ d D T 1 + γ B_T\le dDT^{1+\gamma} B T ≤ d D T 1 + γ gives η ≤ 2 d D T γ / ( e ( 2 log d − 1 ) ) = O ( d D T γ / log d ) \eta\le2dDT^\gamma/(e(2\log d-1))=O(dDT^\gamma/\log d) η ≤ 2 d D T γ / ( e ( 2 log d − 1 )) = O ( d D T γ / log d ) as a function of T T T .
The per-level miscoverage bound follows from max i ∈ [ d ] ∣ δ T , i ∣ = max i ∣ G T , i ∣ / T ≤ ∥ G T ∥ q / T \max_{i\in[d]}|\delta_{T,i}|=\max_i|G_{T,i}|/T\le\|G_T\|_q/T max i ∈ [ d ] ∣ δ T , i ∣ = max i ∣ G T , i ∣/ T ≤ ∥ G T ∥ q / T , since ∥ ⋅ ∥ ∞ ≤ ∥ ⋅ ∥ q \|\cdot\|_\infty\le\|\cdot\|_q ∥ ⋅ ∥ ∞ ≤ ∥ ⋅ ∥ q .
On the choice of η \eta η . The right-hand side of (7) is strictly decreasing in η \eta η , with infimum 1 T d 2 / q T / ( p − 1 ) \frac{1}{T}\sqrt{d^{2/q}T}/(p-1) T 1 d 2/ q T / ( p − 1 ) as η → ∞ \eta\to\infty η → ∞ ; the balanced η \eta η above attains it up to a factor 2 \sqrt{2} 2 , at a finite step size. Small miscoverage alone is a weak target: the data-free predictor that outputs R \mathbb{R} R on the first ⌈ ( 1 − α i ) T ⌉ \lceil(1-\alpha_i)T\rceil ⌈( 1 − α i ) T ⌉ rounds and ∅ \varnothing ∅ afterwards attains MisCov T , i ≤ 1 / T \operatorname{MisCov}_{T,i} \le1/T MisCov T , i ≤ 1/ T (see [25 App. H.5] for a horizon-free variant). The regret bound is what controls efficiency; for instance, when the scores are i.i.d. (under regularity conditions), sublinear regret drives the average radius to the oracle quantile [25 Thm. D.3] . Finally, there is no contradiction with Proposition A.3 : for η ′ > η \eta' > \eta η ′ > η , the two OMD bounds satisfy F T η ′ ( u ) > F T η ( u ) F_T^{\eta'}(u) > F_T^\eta(u) F T η ′ ( u ) > F T η ( u ) if and only if ∥ u ∥ p 2 < η η ′ ∑ t ∥ g t ∥ q 2 / ( p − 1 ) \lVert u\rVert_p^2 < \eta\eta' \sum_t \lVert g_t\rVert_q^2/(p-1) ∥ u ∥ p 2 < η η ′ ∑ t ∥ g t ∥ q 2 / ( p − 1 ) , so neither dominates the other uniformly and the proposition does not apply.
Beyond the isotonic cone
The lazy-projection framework rests on a single geometric assumption—inward flow—and is therefore agnostic to the details of K K K . We record here a composition principle that allows additional polyhedral constraints to be layered on top of the isotonic cone without redoing the analysis.
Proposition A.2 (Inward flow under intersection). Let C 1 , C 2 ⊆ R d C_1,C_2 \subseteq\mathbb{R}^d C 1 , C 2 ⊆ R d be closed convex sets and ℓ \ell ℓ a loss with subgradient selection g ( ⋅ ) g(\cdot) g ( ⋅ ) . Suppose that
(i) ( ℓ , C 1 ) (\ell,C_1) ( ℓ , C 1 ) and ( ℓ , C 2 ) (\ell,C_2) ( ℓ , C 2 ) both satisfy inward flow with the same selection g g g ;
(ii) for every x ∈ bd ( C 1 ∩ C 2 ) x \in\operatorname{bd}(C_1 \cap C_2) x ∈ bd ( C 1 ∩ C 2 ) , T C 1 ∩ C 2 ( x ) = T C 1 ( x ) ∩ T C 2 ( x ) T_{C_1\cap C_2}(x)=T_{C_1}(x)\cap T_{C_2}(x) T C 1 ∩ C 2 ( x ) = T C 1 ( x ) ∩ T C 2 ( x ) .
Then ( ℓ , C 1 ∩ C 2 ) (\ell,C_1 \cap C_2) ( ℓ , C 1 ∩ C 2 ) satisfies inward flow with g g g . Condition (ii) holds whenever C 1 C_1 C 1 and C 2 C_2 C 2 are polyhedral.
Proof. Fix x ∈ bd ( C 1 ∩ C 2 ) x \in\operatorname{bd}(C_1 \cap C_2) x ∈ bd ( C 1 ∩ C 2 ) . For i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } , either x ∈ bd ( C i ) x \in\operatorname{bd}(C_i) x ∈ bd ( C i ) , in which case inward flow gives − g ( x ) ∈ T C i ( x ) -g(x) \in T_{C_i}(x) − g ( x ) ∈ T C i ( x ) , or x ∈ int ( C i ) x \in\operatorname{int}(C_i) x ∈ int ( C i ) , in which case T C i ( x ) = R d T_{C_i}(x)=\mathbb{R}^d T C i ( x ) = R d . Either way, − g ( x ) ∈ T C 1 ( x ) ∩ T C 2 ( x ) = T C 1 ∩ C 2 ( x ) -g(x) \in T_{C_1}(x)\cap T_{C_2}(x)=T_{C_1\cap C_2}(x) − g ( x ) ∈ T C 1 ( x ) ∩ T C 2 ( x ) = T C 1 ∩ C 2 ( x ) by (ii).
Example: bounded isotonic cone. Suppose Assumption 2.1 holds with γ = 0 \gamma=0 γ = 0 , so S t ≤ D S_t \le D S t ≤ D for all t t t , and let R ≥ D R \ge D R ≥ D . The set K R : = K ∩ { x ∈ R d : x j ≤ R for all j } K_R := K \cap\{x \in\mathbb{R}^d : x_j \le R \text{ for all }j\} K R := K ∩ { x ∈ R d : x j ≤ R for all j } enforces both isotonicity and an upper bound. To verify inward flow on K R K_R K R , by Proposition A.2 it suffices to verify it on the upper-bound polyhedron C R : = { x : x j ≤ R } C_R := \{x : x_j \le R\} C R := { x : x j ≤ R } . At a boundary point with x j = R ≥ D ≥ S t x_j=R \ge D \ge S_t x j = R ≥ D ≥ S t , the subgradient coordinate is g t , j = α j > 0 g_{t,j}=\alpha_j>0 g t , j = α j > 0 , so − g t , j < 0 -g_{t,j}<0 − g t , j < 0 , which lies in the half-space v j ≤ 0 v_j \le0 v j ≤ 0 defining the tangent cone of C R C_R C R along x j = R x_j=R x j = R . Both K K K and C R C_R C R are polyhedral, so (ii) holds, and Proposition A.2 applies. All bounds in Section 3 carry over with K K K replaced by K R K_R K R , with the additional benefit that the played radii are clipped at the largest plausible score.
Tighter regret implies tighter coverage
The following monotonicity formalizes the second corollary of Theorem 3.4 ; it generalizes the scalar argument of Liu et al. [ [25 ] , Sec. 4 to the vector setting and underlies the design of the case studies in § 3.1 –§ 3.2 .
Proposition A.3. Let F T A , F T B : R d → R F_T^A,F_T^B:\mathbb{R}^d\to\mathbb{R} F T A , F T B : R d → R be two valid linearized regret bounds for two base learners Alg A , Alg B \operatorname{Alg}_A,\operatorname{Alg}_B Alg A , Alg B that satisfy F T A ( u ) ≤ F T B ( u ) F_T^A(u)\le F_T^B(u) F T A ( u ) ≤ F T B ( u ) for all u ∈ R d u\in\mathbb{R}^d u ∈ R d . Then their Fenchel conjugates satisfy ( F T A ) ∗ ( z ) ≥ ( F T B ) ∗ ( z ) (F_T^A)^*(z)\ge(F_T^B)^*(z) ( F T A ) ∗ ( z ) ≥ ( F T B ) ∗ ( z ) for all z ∈ R d z\in\mathbb{R}^d z ∈ R d , and the coverage-error level sets (6) are nested:
Z T ( F T A ) ⊆ Z T ( F T B ) . \mathcal{Z}_T(F_T^A)\subseteq\mathcal{Z}_T(F_T^B). Z T ( F T A ) ⊆ Z T ( F T B ) .
Consequently, if Alg A \operatorname{Alg}_A Alg A admits a uniformly tighter regret bound than Alg B \operatorname{Alg}_B Alg B , the worst-case miscoverage region delivered by Theorem 3.4 for Alg A \operatorname{Alg}_A Alg A is contained in that for Alg B \operatorname{Alg}_B Alg B .
Proof. Fix z ∈ R d z\in\mathbb{R}^d z ∈ R d . By definition of the Fenchel conjugate,
( F T A ) ∗ ( z ) = sup u ∈ R d [ ⟨ z , u ⟩ − F T A ( u ) ] ≥ sup u ∈ R d [ ⟨ z , u ⟩ − F T B ( u ) ] = ( F T B ) ∗ ( z ) , (F_T^A)^*(z)=\sup_{u\in\mathbb{R}^d}\left[\langle z,u\rangle-F_T^A(u)\right]\ge\sup_{u\in\mathbb{R}^d}\left[\langle z,u\rangle-F_T^B(u)\right]=(F_T^B)^*(z), ( F T A ) ∗ ( z ) = u ∈ R d sup [ ⟨ z , u ⟩ − F T A ( u ) ] ≥ u ∈ R d sup [ ⟨ z , u ⟩ − F T B ( u ) ] = ( F T B ) ∗ ( z ) ,
using − F T A ( u ) ≥ − F T B ( u ) -F_T^A(u)\ge-F_T^B(u) − F T A ( u ) ≥ − F T B ( u ) pointwise. For every z ∈ Z T ( F T A ) z\in\mathcal{Z}_T(F_T^A) z ∈ Z T ( F T A ) , ( F T B ) ∗ ( − z ) ≤ ( F T A ) ∗ ( − z ) ≤ B T (F_T^B)^*(-z)\le(F_T^A)^*(-z)\le B_T ( F T B ) ∗ ( − z ) ≤ ( F T A ) ∗ ( − z ) ≤ B T , so z ∈ Z T ( F T B ) z\in\mathcal{Z}_T(F_T^B) z ∈ Z T ( F T B ) .
This makes precise the operational principle invoked in the main text: minimizing the linearized regret of the base learner directly tightens the coverage-error region of the wrapped algorithm.
Coordinate-wise UP-OCP: per-level and mean-absolute proofs
We first record the analytic facts about the Bernstein-type function used by UP-OCP, then prove Theorem 3.7 and Theorem A.6 . Throughout, the Fenchel conjugate of the UP-OCP regret bound at level α \alpha α has the form ( F T ( α ) ) ∗ ( ∣ θ ∣ ) = exp ( h α ( θ ) ) − 1 (F_{T}^{(\alpha)})^{*}(|\theta|)=\exp(h_{\alpha}(\theta))-1 ( F T ( α ) ) ∗ ( ∣ θ ∣ ) = exp ( h α ( θ )) − 1 with
h α ( θ ) : = θ 2 2 α ( 1 − α ) T + ( 2 / 3 ) θ − 1 2 log ( π ( T + 1 ) ) ; h_{\alpha}(\theta):=\frac{\theta^{2}}{2\alpha(1-\alpha)T+(2/3)\theta}-\frac{1}{2}\log(\pi(T+1)); h α ( θ ) := 2 α ( 1 − α ) T + ( 2/3 ) θ θ 2 − 2 1 log ( π ( T + 1 )) ;
s e e c i t e t ‘ L i u e t a l . , 2026 , T h e o r e m 4.3 a n d A p p . E .4 ‘ . see {citet}`Liu et al., 2026, Theorem 4.3 and App. E.4`. see c i t e t ‘ L i u e t a l . , 2026 , T h eor e m 4.3 an d A pp . E .4‘.
Lemma A.4 (Bernstein inversion). Let σ , θ ≥ 0 \sigma,\theta\ge0 σ , θ ≥ 0 and c > 0 c>0 c > 0 . If θ 2 2 σ T + ( 2 / 3 ) θ ≤ c \frac{\theta^{2}}{2\sigma T+(2/3)\theta}\le c 2 σ T + ( 2/3 ) θ θ 2 ≤ c , then $\theta\le\sqrt{2\sigma Tc}+2c/3.
Proof. Rearranging gives θ 2 − ( 2 c / 3 ) θ − 2 σ T c ≤ 0 \theta^{2}-(2c/3)\theta-2\sigma Tc\le0 θ 2 − ( 2 c /3 ) θ − 2 σ T c ≤ 0 . The quadratic formula yields θ ≤ c / 3 + c 2 / 9 + 2 σ T c ≤ c / 3 + c / 3 + 2 σ T c = 2 c / 3 + 2 σ T c \theta\le c/3+\sqrt{c^{2}/9+2\sigma Tc}\le c/3+c/3+\sqrt{2\sigma Tc}=2c/3+\sqrt{2\sigma Tc} θ ≤ c /3 + c 2 /9 + 2 σ T c ≤ c /3 + c /3 + 2 σ T c = 2 c /3 + 2 σ T c .
Lemma A.5. For every fixed σ > 0 \sigma>0 σ > 0 and T > 0 T>0 T > 0 , the map θ ↦ θ 2 / ( 2 σ T + ( 2 / 3 ) θ ) \theta\mapsto\theta^{2}/(2\sigma T+(2/3)\theta) θ ↦ θ 2 / ( 2 σ T + ( 2/3 ) θ ) is convex and non-decreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
Proof. Write f ( θ ) = θ 2 / ( a + b θ ) f(\theta)=\theta^{2}/(a+b\theta) f ( θ ) = θ 2 / ( a + b θ ) with a = 2 σ T a=2\sigma T a = 2 σ T , b = 2 / 3 b=2/3 b = 2/3 . Direct calculation gives f ′ ( θ ) = θ ( 2 a + b θ ) / ( a + b θ ) 2 ≥ 0 f'(\theta)=\theta(2a+b\theta)/(a+b\theta)^{2}\ge0 f ′ ( θ ) = θ ( 2 a + b θ ) / ( a + b θ ) 2 ≥ 0 and f ′ ′ ( θ ) = 2 a 2 / ( a + b θ ) 3 > 0 f''(\theta)=2a^{2}/(a+b\theta)^{3}>0 f ′′ ( θ ) = 2 a 2 / ( a + b θ ) 3 > 0 .
Proof of Theorem 3.7 . Substituting the form of ( F T ( j ) ) ∗ (F_{T}^{(j)})^{*} ( F T ( j ) ) ∗ into (8) , ∑ j = 1 d exp ( h α j ( ∣ G T , j ∣ ) ) ≤ B T + d \sum_{j=1}^{d}\exp(h_{\alpha_j}(|G_{T,j}|))\le B_T+d ∑ j = 1 d exp ( h α j ( ∣ G T , j ∣ )) ≤ B T + d . Each term is non-negative, so we may drop all but the j j j -th: exp ( h α j ( ∣ G T , j ∣ ) ) ≤ B T + d \exp(h_{\alpha_j}(|G_{T,j}|))\le B_T+d exp ( h α j ( ∣ G T , j ∣ )) ≤ B T + d , equivalently
∣ G T , j ∣ 2 2 α j ( 1 − α j ) T + ( 2 / 3 ) ∣ G T , j ∣ ≤ log ( B T + d ) + 1 2 log ( π ( T + 1 ) ) = T ϵ ^ T , j . \frac{|G_{T,j}|^{2}}{2\alpha_j(1-\alpha_j)T+(2/3)|G_{T,j}|}\le\log(B_T+d)+\frac{1}{2}\log(\pi(T+1))=T\widehat{\epsilon}_{T,j}. 2 α j ( 1 − α j ) T + ( 2/3 ) ∣ G T , j ∣ ∣ G T , j ∣ 2 ≤ log ( B T + d ) + 2 1 log ( π ( T + 1 )) = T ϵ T , j .
Lemma A.4 with σ = α j ( 1 − α j ) \sigma=\alpha_j(1-\alpha_j) σ = α j ( 1 − α j ) and c = T ϵ ^ T , j c=T\widehat{\epsilon}_{T,j} c = T ϵ T , j gives ∣ G T , j ∣ ≤ T 2 α j ( 1 − α j ) ϵ ^ T , j + ( 2 / 3 ) T ϵ ^ T , j |G_{T,j}|\le T\sqrt{2\alpha_j(1-\alpha_j)\widehat{\epsilon}_{T,j}}+(2/3)T\widehat{\epsilon}_{T,j} ∣ G T , j ∣ ≤ T 2 α j ( 1 − α j ) ϵ T , j + ( 2/3 ) T ϵ T , j . Dividing by T T T and using 2 / 3 < 1 2/3<1 2/3 < 1 yields (9) . The asymptotic claim uses B T ≤ d D T 1 + γ B_T\le dD T^{1+\gamma} B T ≤ d D T 1 + γ to give ϵ ^ T , j = O ( ( log d + log T ) / T ) \widehat{\epsilon}_{T,j}=O((\log d+\log T)/T) ϵ T , j = O (( log d + log T ) / T ) and hence max j ∣ δ T , j ∣ = O ( ( log d + log T ) / T ) \max_j|\delta_{T,j}|=O(\sqrt{(\log d+\log T)/T}) max j ∣ δ T , j ∣ = O ( ( log d + log T ) / T ) .
The per-level guarantee (9) can be aggregated into a mean-absolute coverage bound across levels. By dropping the variance budgets at individual levels in favor of their envelope σ A \sigma_A σ A and applying Jensen’s inequality to the resulting sum, one obtains a single ℓ 1 \ell_1 ℓ 1 -style bound whose rate depends on the level set only through σ A \sigma_A σ A and log d \log d log d . The bound below is a vector analogue of Liu et al. [ [25 ] and, by norm equivalence, improves any ℓ 2 \ell_2 ℓ 2 bound by a factor of 1 / d 1/\sqrt{d} 1/ d on the same quantity (cf. Remark A.7 below).
Theorem A.6 (ℓ 1 \ell_1 ℓ 1 miscoverage error of coordinate-wise UP-OCP). Run Algorithm 2, and let σ A : = max i ∈ [ d ] α i ( 1 − α i ) ∈ [ 0 , 1 / 4 ] \sigma_A:=\max_{i\in[d]}\alpha_i(1-\alpha_i)\in[0,1/4] σ A := max i ∈ [ d ] α i ( 1 − α i ) ∈ [ 0 , 1/4 ] and C T : = B T + d C_T:=B_T+d C T := B T + d . Then
1 d ∑ i = 1 d ∣ δ T , i ∣ ≤ 2 σ A Δ T T + 2 Δ T 3 T , Λ T : = log C T d + 1 2 log ( π ( T + 1 ) ) . (13) \frac{1}{d}\sum_{i=1}^{d}|\delta_{T,i}|\le\sqrt{\frac{2\sigma_A\Delta_T}{T}}+\frac{2\Delta_T}{3T},\qquad\Lambda_T:=\log\frac{C_T}{d}+\frac{1}{2}\log(\pi(T+1)). \tag*{(13)} d 1 i = 1 ∑ d ∣ δ T , i ∣ ≤ T 2 σ A Δ T + 3 T 2 Δ T , Λ T := log d C T + 2 1 log ( π ( T + 1 )) . (13) Under Assumption 2.1 , Λ T = O ( ( 1 + γ ) log T ) \Lambda_T=O((1+\gamma)\log T) Λ T = O (( 1 + γ ) log T ) , hence 1 d ∑ i = 1 d ∣ δ T , i ∣ = O ( σ A ( 1 + γ ) log T / T ) \frac{1}{d}\sum_{i=1}^{d}|\delta_{T,i}|=O(\sqrt{\sigma_A(1+\gamma)\log T/T}) d 1 ∑ i = 1 d ∣ δ T , i ∣ = O ( σ A ( 1 + γ ) log T / T ) .
Remark A.7 (Comparison with the ℓ 2 \ell_2 ℓ 2 -bound of Ding et al. [ [14 ] ). By norm equivalence, 1 d ∥ δ T ∥ 1 ≤ 1 d ∥ δ T ∥ 2 \frac{1}{d}\|\delta_T\|_1\le\frac{1}{\sqrt{d}}\|\delta_T\|_2 d 1 ∥ δ T ∥ 1 ≤ d 1 ∥ δ T ∥ 2 , so (13) delivers a 1 / d 1/\sqrt{d} 1/ d improvement over any ℓ 2 \ell_2 ℓ 2 bound on the mean-absolute miscoverage. Combined with Theorem 3.7 , this improves the dependence on d d d over the ℓ 2 \ell_2 ℓ 2 guarantee of MultiQT, at the price of a log T \log T log T factor; it is not uniformly tighter in T T T , since for a fixed step size the bounds of MultiQT carry no log T \log T log T factor and, for a common point forecast, decay as O ( 1 / T ) O(1/T) O ( 1/ T ) (Appendix § 8 .9).
Proof of Theorem A.6 . Substituting the form of ( F T ( j ) ) ⋆ (F_T^{(j)})^\star ( F T ( j ) ) ⋆ into (8) ,
∑ j = 1 d exp ( h α j ( ∣ G T , j ∣ ) ) ≤ B T + d = C T . \sum_{j=1}^{d} \exp\left(h_{\alpha_j}(|G_{T,j}|)\right) \le B_T+d=C_T. j = 1 ∑ d exp ( h α j ( ∣ G T , j ∣ ) ) ≤ B T + d = C T .
By definition of σ A \sigma_A σ A , α j ( 1 − α j ) ≤ σ A \alpha_j(1-\alpha_j)\le\sigma_A α j ( 1 − α j ) ≤ σ A for every j j j , so h α j ( θ ) ≥ h σ A ( θ ) h_{\alpha_j}(\theta)\ge h_{\sigma_A}(\theta) h α j ( θ ) ≥ h σ A ( θ ) for every θ ≥ 0 \theta\ge0 θ ≥ 0 (where we abuse notation and set h σ A ( θ ) : = θ 2 2 σ A T + ( 2 / 3 ) θ − 1 2 log ( π ( T + 1 ) ) h_{\sigma_A}(\theta):=\frac{\theta^2}{2\sigma_A T+(2/3)\theta}-\frac{1}{2}\log(\pi(T+1)) h σ A ( θ ) := 2 σ A T + ( 2/3 ) θ θ 2 − 2 1 log ( π ( T + 1 )) ). Hence
∑ j = 1 d exp ( h σ A ( ∣ G T , j ∣ ) ) ≤ C T . \sum_{j=1}^{d} \exp\left(h_{\sigma_A}(|G_{T,j}|)\right)\le C_T. j = 1 ∑ d exp ( h σ A ( ∣ G T , j ∣ ) ) ≤ C T .
By Lemma A.5 , θ ↦ h σ A ( θ ) + 1 2 log ( π ( T + 1 ) ) \theta\mapsto h_{\sigma_A}(\theta)+\frac{1}{2}\log(\pi(T+1)) θ ↦ h σ A ( θ ) + 2 1 log ( π ( T + 1 )) is convex; the exponential is increasing and convex; so the composition θ ↦ exp ( h σ A ( θ ) ) \theta\mapsto\exp(h_{\sigma_A}(\theta)) θ ↦ exp ( h σ A ( θ )) is convex. Jensen’s inequality applied to the uniform measure on [ d ] [d] [ d ] gives
d exp ( h σ A ( G ‾ T ) ) ≤ ∑ j = 1 d exp ( h σ A ( ∣ G T , j ∣ ) ) ≤ C T , G ‾ T : = 1 d ∑ j = 1 d ∣ G T , j ∣ . d\exp\left(h_{\sigma_A}(\overline{G}_T)\right)\le\sum_{j=1}^{d}\exp\left(h_{\sigma_A}(|G_{T,j}|)\right)\le C_T,\qquad\overline{G}_T:=\frac{1}{d}\sum_{j=1}^{d}|G_{T,j}|. d exp ( h σ A ( G T ) ) ≤ j = 1 ∑ d exp ( h σ A ( ∣ G T , j ∣ ) ) ≤ C T , G T := d 1 j = 1 ∑ d ∣ G T , j ∣.
Taking logarithms and rearranging,
G ‾ T 2 2 σ A T + ( 2 / 3 ) G ‾ T ≤ log C T d + 1 2 log ( π ( T + 1 ) ) = Λ T . \frac{\overline{G}_T^2}{2\sigma_A T+(2/3)\overline{G}_T}\le\log\frac{C_T}{d}+\frac{1}{2}\log(\pi(T+1))=\Lambda_T. 2 σ A T + ( 2/3 ) G T G T 2 ≤ log d C T + 2 1 log ( π ( T + 1 )) = Λ T .
Lemma A.4 with σ = σ A \sigma=\sigma_A σ = σ A , c = Λ T c=\Lambda_T c = Λ T gives G ‾ T ≤ 2 σ A T Λ T + 2 Λ T / 3 \overline{G}_T\le\sqrt{2\sigma_A T\Lambda_T}+2\Lambda_T/3 G T ≤ 2 σ A T Λ T + 2 Λ T /3 . Dividing by T T T and noting 1 d ∑ j ∣ δ T , j ∣ = G ‾ T / T \frac{1}{d}\sum_j|\delta_{T,j}|=\overline{G}_T/T d 1 ∑ j ∣ δ T , j ∣ = G T / T yields (13) . For the asymptotic claim, C T / d = B T / d + 1 ≤ D T 1 + γ + 1 C_T/d=B_T/d+1\le DT^{1+\gamma}+1 C T / d = B T / d + 1 ≤ D T 1 + γ + 1 by Assumption 2.1 , hence Λ T = O ( log T ) \Lambda_T=O(\log T) Λ T = O ( log T ) , and the right-hand side of (13) is O ( σ A log T / T ) O(\sqrt{\sigma_A\log T/T}) O ( σ A log T / T ) .
Continuous quantile levels
We extend the framework from a finite collection A \mathcal{A} A to a compact interval X ⊂ ( 0 , 1 ) \mathcal{X}\subset(0,1) X ⊂ ( 0 , 1 ) . Fix a finite Borel reference measure μ \mu μ with full support and work in the Hilbert space H : = L 2 ( X , μ ) \mathcal{H}:=L^2(\mathcal{X},\mu) H := L 2 ( X , μ ) with inner product ⟨ f , h ⟩ : = ∫ X f ( α ) h ( α ) d μ ( α ) \langle f,h\rangle:=\int_{\mathcal{X}}f(\alpha)h(\alpha)\,d\mu(\alpha) ⟨ f , h ⟩ := ∫ X f ( α ) h ( α ) d μ ( α ) . The radius forecast is now a function b t ∈ H b_t\in\mathcal{H} b t ∈ H , and the score S t S_t S t is a scalar with S t ≤ D T γ S_t\le DT^\gamma S t ≤ D T γ as in Assumption 2.1 . Define the integrated pinball loss
L t ( b ) : = ∫ X ℓ ( 1 − α ) ( b ( α ) , S t ) d μ ( α ) , L_t(b):=\int_{\mathcal{X}}\ell^{(1-\alpha)}(b(\alpha),S_t)\,d\mu(\alpha), L t ( b ) := ∫ X ℓ ( 1 − α ) ( b ( α ) , S t ) d μ ( α ) ,
which is convex on H \mathcal{H} H and has subgradient g t ( α ) : = 1 { b t ( α ) ≥ S t } − ( 1 − α ) g_t(\alpha):=\mathbf{1}\{b_t(\alpha)\ge S_t\}-(1-\alpha) g t ( α ) := 1 { b t ( α ) ≥ S t } − ( 1 − α ) in L ∞ ( X , μ ) ⊆ H L^\infty(\mathcal{X},\mu)\subseteq\mathcal{H} L ∞ ( X , μ ) ⊆ H . The isotonic constraint becomes the cone of non-increasing functions:
K : = { b ∈ H : b admits a non-increasing representative on X } . \mathcal{K}:=\{b\in\mathcal{H}: b\text{ admits a non-increasing representative on }\mathcal{X}\}. K := { b ∈ H : b admits a non-increasing representative on X } .
K \mathcal{K} K is a closed convex cone in H \mathcal{H} H , and the L 2 L^2 L 2 -projection Π K \Pi_{\mathcal{K}} Π K is well-defined by the Hilbert projection theorem. Continuous PAVA characterizes Π K ( b ) \Pi_{\mathcal{K}}(b) Π K ( b ) as − d F ^ d μ -\frac{d\widehat{F}}{d\mu} − d μ d F , where F ^ \widehat{F} F is the greatest concave majorant of F ( x ) : = − ∫ α min x b ( α ) d μ ( α ) F(x):=-\int_{\alpha_{\min}}^x b(\alpha)\,d\mu(\alpha) F ( x ) := − ∫ α m i n x b ( α ) d μ ( α ) [[30 ] ].
Inward flow, regret preservation, central inequality. The proofs of Lemma 3.2, Proposition 3.3, and Theorem 3.4 use only the inner-product structure of H \mathcal{H} H and so transfer verbatim. Inward flow of ( L t , K ) (L_t,\mathcal{K}) ( L t , K ) on H \mathcal{H} H is verified by the same case analysis as in Appendix § 8 .§ 3 , applied pointwise. The central inequality reads
F T ⋆ ( − G T ) ≤ B T , G T : = ∑ t = 1 T g t ∈ H , B T : = ∑ t = 1 T L t ( 0 ) . (14) F_T^\star(-G_T)\le B_T,\qquad G_T:=\sum_{t=1}^{T}g_t\in\mathcal{H},\qquad B_T:=\sum_{t=1}^{T}L_t(0). \tag*{(14)} F T ⋆ ( − G T ) ≤ B T , G T := t = 1 ∑ T g t ∈ H , B T := t = 1 ∑ T L t ( 0 ) . (14)
Under Assumption 2.1 , L t ( 0 ) ≤ μ ( X ) ⋅ S t ≤ μ ( X ) D T γ L_t(0)\le\mu(\mathcal{X})\cdot S_t\le\mu(\mathcal{X})DT^\gamma L t ( 0 ) ≤ μ ( X ) ⋅ S t ≤ μ ( X ) D T γ , so B T ≤ μ ( X ) D T 1 + γ B_T\le\mu(\mathcal{X})DT^{1+\gamma} B T ≤ μ ( X ) D T 1 + γ , depending on X \mathcal{X} X only through μ ( X ) \mu(\mathcal{X}) μ ( X ) and not through any notion of dimensionality.
L 2 L^2 L 2 coverage via OGD. Take Alg to be OGD on H \mathcal{H} H with regularizer ψ ( f ) = 1 2 ∥ f ∥ H 2 \psi(f) = \frac{1}{2}\lVert f\rVert_{\mathcal{H}}^2 ψ ( f ) = 2 1 ∥ f ∥ H 2 and step size η > 0 \eta> 0 η > 0 . The regret bound is F T ( u ) = ∥ u ∥ H 2 / ( 2 η ) + ( η / 2 ) ∑ t ∥ g t ∥ H 2 F_T(u) = \lVert u\rVert_{\mathcal{H}}^2/(2\eta)+(\eta/2)\sum_t \lVert g_t\rVert_{\mathcal{H}}^2 F T ( u ) = ∥ u ∥ H 2 / ( 2 η ) + ( η /2 ) ∑ t ∥ g t ∥ H 2 , with conjugate F T ∗ ( θ ) = ( η / 2 ) ∥ θ ∥ H 2 − ( η / 2 ) ∑ t ∥ g t ∥ H 2 F_T^*(\theta) = (\eta/2)\lVert\theta\rVert_{\mathcal{H}}^2-(\eta/2)\sum_t \lVert g_t\rVert_{\mathcal{H}}^2 F T ∗ ( θ ) = ( η /2 ) ∥ θ ∥ H 2 − ( η /2 ) ∑ t ∥ g t ∥ H 2 . Since ∥ g t ∥ H 2 = ∫ X g t ( α ) 2 d μ ( α ) ≤ μ ( X ) \lVert g_t\rVert_{\mathcal{H}}^2 = \int_{\mathcal{X}} g_t(\alpha)^2 d\mu(\alpha) \leq\mu(\mathcal{X}) ∥ g t ∥ H 2 = ∫ X g t ( α ) 2 d μ ( α ) ≤ μ ( X ) , Theorem 3.4 gives ∥ G T ∥ H 2 ≤ 2 B T / η + μ ( X ) T \lVert G_T\rVert_{\mathcal{H}}^2 \leq2B_T/\eta+\mu(\mathcal{X})T ∥ G T ∥ H 2 ≤ 2 B T / η + μ ( X ) T . Choosing η = 2 B T / ( μ ( X ) T ) \eta= 2B_T/(\mu(\mathcal{X})T) η = 2 B T / ( μ ( X ) T ) to balance the two terms yields
∥ δ T ∥ L 2 ( X , μ ) ≤ 2 μ ( X ) T , δ T : = G T / T . (15) \lVert\delta_T\rVert_{L^2(\mathcal{X},\mu)} \leq\sqrt{\frac{2\mu(\mathcal{X})}{T}}, \qquad\delta_T := G_T/T. \tag*{(15)} ∥ δ T ∥ L 2 ( X , μ ) ≤ T 2 μ ( X ) , δ T := G T / T . (15)
The bound is dimension-free: it depends on the size of the level set only through μ ( X ) \mu(\mathcal{X}) μ ( X ) .
L q L^q L q coverage via OMD. Take Alg to be OMD with regularizer ψ ( f ) = 1 2 ∥ f ∥ L p 2 \psi(f) = \frac{1}{2}\lVert f\rVert_{L^p}^2 ψ ( f ) = 2 1 ∥ f ∥ L p 2 for p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] , q = p / ( p − 1 ) q = p/(p-1) q = p / ( p − 1 ) . The regularizer is ( p − 1 ) (p-1) ( p − 1 ) -strongly convex with respect to ∥ ⋅ ∥ L p \lVert\cdot\rVert_{L^p} ∥ ⋅ ∥ L p [36 Sec. 4] , by the uniform convexity of L p L^p L p in this range. The regret bound is F T ( u ) = ∥ u ∥ L p 2 / ( 2 η ) + ( η / ( 2 ( p − 1 ) ) ) ∑ t ∥ g t ∥ L q 2 F_T(u) = \lVert u\rVert_{L^p}^2/(2\eta)+(\eta/(2(p-1)))\sum_t\lVert g_t\rVert_{L^q}^2 F T ( u ) = ∥ u ∥ L p 2 / ( 2 η ) + ( η / ( 2 ( p − 1 ))) ∑ t ∥ g t ∥ L q 2 , with conjugate F T ∗ ( θ ) = ( η / 2 ) ∥ θ ∥ L q 2 − ( η / ( 2 ( p − 1 ) ) ) ∑ t ∥ g t ∥ L q 2 F_T^*(\theta) = (\eta/2)\lVert\theta\rVert_{L^q}^2-(\eta/(2(p-1)))\sum_t\lVert g_t\rVert_{L^q}^2 F T ∗ ( θ ) = ( η /2 ) ∥ θ ∥ L q 2 − ( η / ( 2 ( p − 1 ))) ∑ t ∥ g t ∥ L q 2 . Since ∥ g t ∥ L q ≤ μ ( X ) 1 / q \lVert g_t\rVert_{L^q} \leq\mu(\mathcal{X})^{1/q} ∥ g t ∥ L q ≤ μ ( X ) 1/ q ,
∥ δ T ∥ L q ≤ 1 T 2 B T η + μ ( X ) 2 / q T p − 1 . (16) \lVert\delta_T\rVert_{L^q} \leq\frac{1}{T}\sqrt{\frac{2B_T}{\eta}+\frac{\mu(\mathcal{X})^{2/q}T}{p-1}}. \tag*{(16)} ∥ δ T ∥ L q ≤ T 1 η 2 B T + p − 1 μ ( X ) 2/ q T . (16)
Balancing the two terms gives ∥ δ T ∥ L q ≤ 2 ( q − 1 ) μ ( X ) 2 / q / T \lVert\delta_T\rVert_{L^q} \leq\sqrt{2(q-1)\mu(\mathcal{X})^{2/q}/T} ∥ δ T ∥ L q ≤ 2 ( q − 1 ) μ ( X ) 2/ q / T .
Remark A.8 (Optimal q q q depends on μ ( X ) \mu(\mathcal{X}) μ ( X ) ). Differentiating g ( q ) : = ( q − 1 ) μ ( X ) 2 / q g(q) := (q-1)\mu(\mathcal{X})^{2/q} g ( q ) := ( q − 1 ) μ ( X ) 2/ q in q ∈ [ 2 , ∞ ) q \in[2,\infty) q ∈ [ 2 , ∞ ) shows that g g g is non-decreasing on [ 2 , ∞ ) [2,\infty) [ 2 , ∞ ) unless μ ( X ) > e 2 \mu(\mathcal{X}) > e^2 μ ( X ) > e 2 (since q 2 / ( q − 1 ) ≥ 4 q^2/(q-1) \geq4 q 2 / ( q − 1 ) ≥ 4 there), in which case the unique stationary point in [ 2 , ∞ ) [2,\infty) [ 2 , ∞ ) satisfies q 2 = 2 ( q − 1 ) log μ ( X ) q^2 = 2(q-1)\log\mu(\mathcal{X}) q 2 = 2 ( q − 1 ) log μ ( X ) and is approximately 2 log μ ( X ) 2\log\mu(\mathcal{X}) 2 log μ ( X ) for large μ ( X ) \mu(\mathcal{X}) μ ( X ) . For the Lebesgue measure or any probability measure on X ⊆ ( 0 , 1 ) \mathcal{X} \subseteq(0,1) X ⊆ ( 0 , 1 ) , μ ( X ) ≤ 1 < e 2 \mu(\mathcal{X}) \leq1 < e^2 μ ( X ) ≤ 1 < e 2 , so g g g is increasing on [ 2 , ∞ ) [2,\infty) [ 2 , ∞ ) and the optimum is q = 2 q = 2 q = 2 , recovering the dimension-free L 2 L^2 L 2 bound (15) . So OGD on H \mathcal{H} H already delivers the optimal rate among L q L^q L q bounds.
This corrects the optimization in the discrete-to-continuous translation: the discrete-case choice q = 2 log d q = 2\log d q = 2 log d is beneficial only when the analogue μ ( X ) > e 2 \mu(\mathcal{X}) > e^2 μ ( X ) > e 2 holds, which fails under Lebesgue and any normalized probability measure on X \mathcal{X} X . In those cases, the L 2 L^2 L 2 bound (15) is the right answer.
Coordinate-wise universal portfolio on a continuum. Running an independent UP-OCP instance at each level α ∈ X \alpha\in\mathcal{X} α ∈ X with initial wealth 1, the regret factorizes as F T ( u ) = ∫ X F T ( α ) ( ∣ u ( α ) ∣ ) d μ ( α ) F_T(u) = \int_{\mathcal{X}} F_T^{(\alpha)}(|u(\alpha)|)\,d\mu(\alpha) F T ( u ) = ∫ X F T ( α ) ( ∣ u ( α ) ∣ ) d μ ( α ) , and similarly F T ∗ ( θ ) = ∫ X ( F T ( α ) ) ∗ ( ∣ θ ( α ) ∣ ) d μ ( α ) F_T^*(\theta) = \int_{\mathcal{X}}(F_T^{(\alpha)})^*(|\theta(\alpha)|)\,d\mu(\alpha) F T ∗ ( θ ) = ∫ X ( F T ( α ) ) ∗ ( ∣ θ ( α ) ∣ ) d μ ( α ) . The central inequality (14) becomes
∫ X exp ( h α ( ∣ G T ( α ) ∣ ) ) d μ ( α ) ≤ C T : = B T + μ ( X ) , (17) \int_{\mathcal{X}} \exp(h_\alpha(|G_T(\alpha)|))\,d\mu(\alpha) \leq C_T := B_T+\mu(\mathcal{X}), \tag*{(17)} ∫ X exp ( h α ( ∣ G T ( α ) ∣ )) d μ ( α ) ≤ C T := B T + μ ( X ) , (17)
where h α h_\alpha h α is as defined in Appendix A.7.
To control miscoverage along an arbitrary direction in the level set, we record the Donsker–Varadhan change-of-measure inequality and then derive a coverage bound for any probability measure ν \nu ν on X \mathcal{X} X .
Lemma A.9 (Donsker–Varadhan change-of-measure; [8 Sec. 2.1] ). Let ( X , B ) (\mathcal{X},\mathcal{B}) ( X , B ) be a measurable space, μ ˉ \bar{\mu} μ ˉ a probability measure on X \mathcal{X} X , and ν \nu ν a probability measure with ν ≪ μ ˉ \nu\ll\bar{\mu} ν ≪ μ ˉ . Then for every bounded measurable Φ : X → R \Phi:\mathcal{X}\to\mathbb{R} Φ : X → R ,
∫ X Φ d ν ≤ KL ( ν ∥ μ ˉ ) + log ∫ X e Φ d μ ˉ . \int_{\mathcal{X}}\Phi\,d\nu\leq\operatorname{KL}(\nu\Vert\bar{\mu})+\log\int_{\mathcal{X}}e^\Phi\,d\bar{\mu}. ∫ X Φ d ν ≤ KL ( ν ∥ μ ˉ ) + log ∫ X e Φ d μ ˉ .
Fix any probability measure ν ≪ μ ˉ \nu\ll\bar{\mu} ν ≪ μ ˉ on X \mathcal{X} X (with μ ˉ : = μ / μ ( X ) \bar{\mu} := \mu/\mu(\mathcal{X}) μ ˉ := μ / μ ( X ) ), and define the ν \nu ν -variance envelope σ ν : = sup α ∈ supp ν α ( 1 − α ) \sigma_\nu:= \sup_{\alpha\in\operatorname{supp}\nu}\alpha(1-\alpha) σ ν := sup α ∈ supp ν α ( 1 − α ) and the ν \nu ν -mean miscoverage G ‾ ν : = ∫ X ∣ G T ( α ) ∣ d ν ( α ) \overline{G}_\nu:= \int_{\mathcal{X}}|G_T(\alpha)|\,d\nu(\alpha) G ν := ∫ X ∣ G T ( α ) ∣ d ν ( α ) . Lemma A.9 with Φ ( α ) = h α ( ∣ G T ( α ) ∣ ) \Phi(\alpha) = h_\alpha(|G_T(\alpha)|) Φ ( α ) = h α ( ∣ G T ( α ) ∣ ) , combined with (17) (so log ∫ e Φ d μ ˉ ≤ log ( C T / μ ( X ) ) \log\int e^\Phi d\bar{\mu} \leq\log(C_T/\mu(\mathcal{X})) log ∫ e Φ d μ ˉ ≤ log ( C T / μ ( X )) ), yields
∫ X h α ( ∣ G T ( α ) ∣ ) d ν ( α ) ≤ KL ( ν ∥ μ ) + log C T μ ( X ) . (18) \int_{\mathcal{X}} h_\alpha(|G_T(\alpha)|)\,d\nu(\alpha) \leq\operatorname{KL}(\nu\Vert\mu)+\log\frac{C_T}{\mu(\mathcal{X})}. \tag*{(18)} ∫ X h α ( ∣ G T ( α ) ∣ ) d ν ( α ) ≤ KL ( ν ∥ μ ) + log μ ( X ) C T . (18)
Bounding h α ≥ h σ ν h_{\alpha} \ge h_{\sigma_{\nu}} h α ≥ h σ ν ν \nu ν -almost everywhere and applying Jensen’s inequality to the convex function h σ ν h_{\sigma_{\nu}} h σ ν (Lemma A.5 ) under the probability measure ν \nu ν gives h σ ν ( G ‾ ν ) ≤ ∫ X h σ ν ( ∣ G T ( α ) ∣ ) d ν ( α ) ≤ KL ( ν ∥ μ ˉ ) + log ( C T / μ ( X ) ) h_{\sigma_{\nu}}(\overline{G}_{\nu}) \le\int_{\mathcal{X}} h_{\sigma_{\nu}}(|G_T(\alpha)|)\,d\nu(\alpha) \le\operatorname{KL}(\nu\|\bar{\mu}) + \log(C_T/\mu(\mathcal{X})) h σ ν ( G ν ) ≤ ∫ X h σ ν ( ∣ G T ( α ) ∣ ) d ν ( α ) ≤ KL ( ν ∥ μ ˉ ) + log ( C T / μ ( X )) , i.e., G ‾ ν 2 / ( 2 σ ν T + ( 2 / 3 ) G ‾ ν ) ≤ R ν \overline{G}_{\nu}^{2}/(2\sigma_{\nu}T + (2/3)\overline{G}_{\nu}) \le R_{\nu} G ν 2 / ( 2 σ ν T + ( 2/3 ) G ν ) ≤ R ν with R ν : = KL ( ν ∥ μ ˉ ) + log ( C T / μ ( X ) ) + 1 2 log ( π ( T + 1 ) ) R_{\nu} := \operatorname{KL}(\nu\|\bar{\mu}) + \log(C_T/\mu(\mathcal{X})) + \frac{1}{2}\log(\pi(T+1)) R ν := KL ( ν ∥ μ ˉ ) + log ( C T / μ ( X )) + 2 1 log ( π ( T + 1 )) . Lemma A.4 then yields the general coverage bound
∫ X ∣ δ T ( α ) ∣ d ν ( α ) ≤ 2 σ ν R ν T + 2 R ν 3 T . (19) \int_{\mathcal{X}} |\delta_T(\alpha)|\,d\nu(\alpha) \le\sqrt{\frac{2\sigma_{\nu}R_{\nu}}{T}}+\frac{2R_{\nu}}{3T}. \tag*{(19)} ∫ X ∣ δ T ( α ) ∣ d ν ( α ) ≤ T 2 σ ν R ν + 3 T 2 R ν . (19)
Sub-interval coverage as a special case. Take I ⊆ X \mathcal{I}\subseteq\mathcal{X} I ⊆ X measurable with μ ( I ) > 0 \mu(\mathcal{I})>0 μ ( I ) > 0 and set ν = μ ∣ I / μ ( I ) \nu=\mu|_{\mathcal{I}}/\mu(\mathcal{I}) ν = μ ∣ I / μ ( I ) . Then KL ( ν ∥ μ ˉ ) = log ( μ ( X ) / μ ( I ) ) \operatorname{KL}(\nu\|\bar{\mu})=\log(\mu(\mathcal{X})/\mu(\mathcal{I})) KL ( ν ∥ μ ˉ ) = log ( μ ( X ) / μ ( I )) , σ ν = σ I : = sup α ∈ I α ( 1 − α ) \sigma_{\nu}=\sigma_{\mathcal{I}}:=\sup_{\alpha\in\mathcal{I}}\alpha(1-\alpha) σ ν = σ I := sup α ∈ I α ( 1 − α ) , and G ‾ ν = G ‾ I : = 1 μ ( I ) ∫ I ∣ G T ( α ) ∣ d μ ( α ) \overline{G}_{\nu}=\overline{G}_{\mathcal{I}}:=\frac{1}{\mu(\mathcal{I})}\int_{\mathcal{I}}|G_T(\alpha)|\,d\mu(\alpha) G ν = G I := μ ( I ) 1 ∫ I ∣ G T ( α ) ∣ d μ ( α ) , so (19) reads
1 μ ( I ) ∫ I ∣ δ T ( α ) ∣ d μ ( α ) ≤ 2 σ I R I T + 2 R I 3 T , R I : = log C T μ ( I ) + 1 2 log ( π ( T + 1 ) ) . (20) \frac{1}{\mu(\mathcal{I})}\int_{\mathcal{I}}|\delta_T(\alpha)|\,d\mu(\alpha)\le\sqrt{\frac{2\sigma_{\mathcal{I}}R_{\mathcal{I}}}{T}}+\frac{2R_{\mathcal{I}}}{3T},\qquad R_{\mathcal{I}}:=\log\frac{C_T}{\mu(\mathcal{I})}+\frac{1}{2}\log(\pi(T+1)). \tag*{(20)} μ ( I ) 1 ∫ I ∣ δ T ( α ) ∣ d μ ( α ) ≤ T 2 σ I R I + 3 T 2 R I , R I := log μ ( I ) C T + 2 1 log ( π ( T + 1 )) . (20)
Specializing further to I = X \mathcal{I}=\mathcal{X} I = X recovers the global mean-absolute miscoverage of Theorem A.6 ; specializing to a small interval near α = 0 \alpha=0 α = 0 or α = 1 \alpha=1 α = 1 exploits the smaller variance envelope σ I \sigma_{\mathcal{I}} σ I , mirroring the level-adaptive behavior of the discrete case.
Reduction to the discrete setting. Specializing X = A = { α 1 , … , α d } \mathcal{X}=\mathcal{A}=\{\alpha_1,\ldots,\alpha_d\} X = A = { α 1 , … , α d } and μ \mu μ the counting measure recovers μ ( X ) = d \mu(\mathcal{X})=d μ ( X ) = d and reduces every continuous bound to its finite analogue: (15) becomes the OGD bound, (16) becomes Corollary 3.6, (17) becomes (8) , and (20) with I = X \mathcal{I}=\mathcal{X} I = X recovers Theorem A.6 . In particular, the dichotomy in Remark A.8 explains why the discrete choice q = 2 log d q=2\log d q = 2 log d helps for many levels (the counting measure makes μ ( X ) = d \mu(\mathcal{X})=d μ ( X ) = d , and d > e 2 ≈ 7.4 d>e^2\approx7.4 d > e 2 ≈ 7.4 ) but does not transfer to Lebesgue.
Detailed comparison with prior work
Table 1 compares our results with the two works we build on, and this subsection details it. We state the results of Ding et al. [ [14 ] in our notation: with symmetric sets, every level shares the base forecast Y ^ t \widehat{Y}_t Y t , so in score space MultiQT runs on the scores ( S t ) (S_t) ( S t ) with the zero base forecast at every level, quantile levels 1 − α i 1-\alpha_i 1 − α i , and initialization x ~ 1 = 0 \widetilde{x}_1=0 x 1 = 0 . We write d A : = min i min { α i , 1 − α i } d_A:=\min_i\min\{\alpha_i,1-\alpha_i\} d A := min i min { α i , 1 − α i } , which equals α 1 \alpha_1 α 1 whenever α 1 + α d ≤ 1 \alpha_1+\alpha_d\le1 α 1 + α d ≤ 1 .
What the combination adds. The ingredients of § 3 are known, and Proposition 3.3 and Theorem 3.4 are short combinations of them (see the discussion after Theorem 3.4 ). The combination nonetheless changes what can be proved.
Black-box generality. The coverage proof of Ding et al. [ [14 ] is not a regret argument: it relies on the OGD update and on the restorativity of the aggregated pinball loss, which they derive from bounded residuals Ding et al. [ [14 ] , so it does not apply to other learners. The duality argument of Liu et al. [ [25 ] is scalar and unconstrained. Proposition 3.3 gives the played, projected sequence the regret bound of the base learner against every u ∈ R d \mathbf{u} \in\mathbb{R}^{d} u ∈ R d , which is exactly what the duality argument needs, so any learner with a linearized-regret bound can be used.
Naive combinations fail. Running independent single-level learners and sorting or projecting their outputs post hoc can break coverage, and so can (non-lazy) projected OGD Ding et al. [ [14 ] . Algorithm 1 avoids both failure modes because the projection is lazy and the subgradient is evaluated at the played iterate.
Two steps behind d → log d \sqrt{d} \to\sqrt{\log d} d → log d . The geometry of the coverage-error region is a design choice (q = 2 log d q = 2 \log d q = 2 log d in Corollary 3.6), and for coordinate-wise UP–OCP, a single aggregate budget B T B_T B T splits into d d d simultaneous per-level bounds at a log d \log d log d price (Theorem 3.7 ).
Continuous levels. Regret preservation transfers verbatim to a Hilbert space (Appendix § 8 .8), which gives coverage guarantees for a continuum of levels, an extension that Ding et al. [ [14 ] leave to future work.
Sharpness. Theorem 4.1 explains the empirical advantage of MultiQT over naive forecasters reported by Ding et al. [ [14 ] .
The two regimes of MultiQT. Under Assumption 2.1 with γ = 0 \gamma= 0 γ = 0 (residual bound D D D ) and a constant step size η \eta η , the general guarantee of Ding et al. [ [14 ] reads
max i ∈ [ d ] MisCov T , i ≤ d T + 2 D d 2 η d A T , \max_{i \in[d]} \operatorname{MisCov}_{T,i} \le\sqrt{\frac{d}{T} + \frac{2D d^{2}}{\eta d_A T}}, i ∈ [ d ] max MisCov T , i ≤ T d + η d A T 2 D d 2 ,
and, since all levels share the same point forecast, their fast rate for point forecasts Ding et al. [ [14 ] applies and reads
max i ∈ [ d ] MisCov T , i ≤ d T + d 3 / 2 2 d A T + D d 3 / 2 d A η T + d 3 / 2 3 T , \max_{i \in[d]} \operatorname{MisCov}_{T,i} \le\frac{\sqrt{d}}{T} + \frac{d^{3/2}}{2d_A T} + \frac{D d^{3/2}}{d_A \eta T} + \frac{d^{3/2}}{\sqrt{3}T}, i ∈ [ d ] max MisCov T , i ≤ T d + 2 d A T d 3/2 + d A η T D d 3/2 + 3 T d 3/2 ,
an O ( 1 / T ) O(1/T) O ( 1/ T ) rate for fixed η \eta η , d d d , d A d_A d A , and D D D (both bounds hold for the ℓ 2 \ell_2 ℓ 2 norm of the coverage-error vector, hence for its largest coordinate). Our analysis does not recover this fast rate. Three qualifications put it in context.
Coupling with regret. The regret bound of Ding et al. [ [14 ] reads D 2 d / ( η T ) + η d / 2 D^2d/(\eta T) + \eta d/2 D 2 d / ( η T ) + η d /2 for the average regret. For a fixed η \eta η it does not vanish, i.e., the cumulative regret bound grows linearly in T T T , and with it the control of the WIS, hence of the width, is lost. The same holds for any step size that does not decay with T T T , including the balanced one of Corollary 3.6 when γ = 0 \gamma= 0 γ = 0 . Balancing calibration against regret, Ding et al. [ [14 ] select η = O ( T − 1 / 2 ) \eta= O(T^{-1/2}) η = O ( T − 1/2 ) and obtain O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) for both; coordinate-wise UP–OCP attains the same rate in T T T up to a log T \sqrt{\log T} log T factor together with sublinear regret, without any tuning (Theorem 3.7 ).
Dependence on the levels. The constants scale as d 3 / 2 / d A d^{3/2}/d_A d 3/2 / d A . At our configuration (d = 100 d = 100 d = 100 levels down to α 1 = 10 − 3 \alpha_1 = 10^{-3} α 1 = 1 0 − 3 , T = 3,000 T = 3{,}000 T = 3 , 000 ), the second term alone equals 10 3 / 6 ≈ 167 10^3/6 \approx167 1 0 3 /6 ≈ 167 , so the bound is vacuous, whereas Corollary 3.6 with q = 2 log d q = 2 \log d q = 2 log d and the balanced η \eta η gives 2 e ( 2 log d − 1 ) / T ≈ 0.12 \sqrt{2e(2\log d - 1)/T} \approx0.12 2 e ( 2 log d − 1 ) / T ≈ 0.12 .
Score growth. Under Assumption 2.1 with γ > 0 \gamma> 0 γ > 0 , the residual bound is D T γ D T^\gamma D T γ , so for an η \eta η fixed independently of T T T the dominant terms degrade to O ( T γ − 1 ) O(T^{\gamma-1}) O ( T γ − 1 ) : slower than T − 1 / 2 T^{-1/2} T − 1/2 for γ > 1 / 2 \gamma> 1/2 γ > 1/2 , and no longer vanishing for γ ≥ 1 \gamma\ge1 γ ≥ 1 . Scaling η ∝ T γ \eta\propto T^\gamma η ∝ T γ restores the rates but requires knowing D D D and γ \gamma γ , as does the balanced step size of Corollary 3.6; coordinate-wise UP–OCP needs no such knowledge.
Our improvements are therefore in the dependence on d d d , parameter-free operation under polynomially growing scores, and black-box generality, not in the dependence on T T T .
Deferred proofs for Section 4
This appendix collects the proofs deferred from § 4 : the WIS–pinball identity (11) and the per-round structural reduction (Theorem 4.1 ).
Pinball loss as a Weighted Interval Score (Equation (11))
We verify the identity (11) . The WIS is a function of the interval endpoints; a zero radius, which encodes the empty set, has width (Lebesgue measure) 0 and is evaluated at the degenerate endpoints l = u = Y ^ t l = u = \hat{Y}_t l = u = Y ^ t . For symmetric central intervals [ Y ^ t − x t , i , Y ^ t + x t , i ] [\hat{Y}_t - x_{t,i}, \hat{Y}_t + x_{t,i}] [ Y ^ t − x t , i , Y ^ t + x t , i ] , x t , i ≥ 0 x_{t,i} \ge0 x t , i ≥ 0 , at miscoverage levels α 1 < ⋯ < α d \alpha_1 < \cdots< \alpha_d α 1 < ⋯ < α d evaluated at the realized response Y t Y_t Y t ,
WIS A ( { [ Y ^ t − x t , i , Y ^ t + x t , i ] } i = 1 d , Y t ) = 2 L t ( x t ) + 2 S t ∑ i = 1 d α i \operatorname{WIS}_{\mathrm{A}}\left(\left\{[\hat{Y}_t-x_{t,i},\hat{Y}_t+x_{t,i}]\right\}_{i=1}^{d},Y_t\right)=2\mathcal{L}_t(x_t)+2S_t\sum_{i=1}^{d}\alpha_i WIS A ( { [ Y ^ t − x t , i , Y ^ t + x t , i ] } i = 1 d , Y t ) = 2 L t ( x t ) + 2 S t i = 1 ∑ d α i
First of all, observe that WIS A ( { [ l α i , u α i ] } i = 1 d , y ) = ∑ i = 1 d α i IS α i ( [ l α i , u α i ] , y ) \operatorname{WIS}_{\mathrm{A}}\left(\left\{[l_{\alpha_i},u_{\alpha_i}]\right\}_{i=1}^{d},y\right)=\sum_{i=1}^{d}\alpha_i\operatorname{IS}_{\alpha_i}([l_{\alpha_i},u_{\alpha_i}],y) WIS A ( { [ l α i , u α i ] } i = 1 d , y ) = ∑ i = 1 d α i IS α i ([ l α i , u α i ] , y ) , where IS α i ( [ l α i , u α i ] , y ) : = ( u α i − l α i ) + 2 α i dist ( y , [ l α i , u α i ] ) \operatorname{IS}_{\alpha_i}([l_{\alpha_i},u_{\alpha_i}],y):=(u_{\alpha_i}-l_{\alpha_i})+\frac{2}{\alpha_i}\operatorname{dist}(y,[l_{\alpha_i},u_{\alpha_i}]) IS α i ([ l α i , u α i ] , y ) := ( u α i − l α i ) + α i 2 dist ( y , [ l α i , u α i ]) .
With D : = Y t − Y ^ t D := Y_t-\hat{Y}_t D := Y t − Y ^ t and S t = ∣ D ∣ S_t=|D| S t = ∣ D ∣ , we have
max ( l α i − Y t , 0 ) = max ( − D − x t , i , 0 ) , and max ( Y t − u α i , 0 ) = max ( D − x t , i , 0 ) . \max(l_{\alpha_i}-Y_t,0)=\max(-D-x_{t,i},0),\qquad\text{and}\qquad\max(Y_t-u_{\alpha_i},0)=\max(D-x_{t,i},0). max ( l α i − Y t , 0 ) = max ( − D − x t , i , 0 ) , and max ( Y t − u α i , 0 ) = max ( D − x t , i , 0 ) .
Because D D D has a definite sign and x t , i ≥ 0 x_{t,i}\ge0 x t , i ≥ 0 (all played and hidden radii are valid by the convention of § 3 ), exactly one of these two non-negative quantities can be non-zero, and it equals max ( ∣ D ∣ − x t , i , 0 ) = max ( S t − x t , i , 0 ) \max(|D|-x_{t,i},0)=\max(S_t-x_{t,i},0) max ( ∣ D ∣ − x t , i , 0 ) = max ( S t − x t , i , 0 ) . Hence
IS α i ( [ Y ^ t − x t , i , Y ^ t + x t , i ] , Y t ) = 2 x t , i + 2 α i max ( S t − x t , i , 0 ) , \operatorname{IS}_{\alpha_i}([\hat{Y}_t-x_{t,i},\hat{Y}_t+x_{t,i}],Y_t)=2x_{t,i}+\frac{2}{\alpha_i}\max(S_t-x_{t,i},0), IS α i ([ Y ^ t − x t , i , Y ^ t + x t , i ] , Y t ) = 2 x t , i + α i 2 max ( S t − x t , i , 0 ) ,
and therefore α i IS α i = 2 α i x t , i + 2 max ( S t − x t , i , 0 ) \alpha_i\operatorname{IS}_{\alpha_i}=2\alpha_i x_{t,i}+2\max(S_t-x_{t,i},0) α i IS α i = 2 α i x t , i + 2 max ( S t − x t , i , 0 ) . Summing over i ∈ [ d ] i\in[d] i ∈ [ d ] ,
WIS A = 2 ∑ i = 1 d α i x t , i + 2 ∑ i = 1 d max ( S t − x t , i , 0 ) . \operatorname{WIS}_{\mathrm{A}}=2\sum_{i=1}^{d}\alpha_i x_{t,i}+2\sum_{i=1}^{d}\max(S_t-x_{t,i},0). WIS A = 2 i = 1 ∑ d α i x t , i + 2 i = 1 ∑ d max ( S t − x t , i , 0 ) .
The pointwise identity ℓ ( 1 − α ) ( x , S ) = α ( x − S ) + max ( S − x , 0 ) \ell^{(1-\alpha)}(x,S)=\alpha(x-S)+\max(S-x,0) ℓ ( 1 − α ) ( x , S ) = α ( x − S ) + max ( S − x , 0 ) (a direct case analysis on x ⋛ S x\gtreqless S x ⋛ S ) gives, after summation,
L t ( x t ) = ∑ i = 1 d α i x t , i + ∑ i = 1 d max ( S t − x t , i , 0 ) − S t ∑ i = 1 d α i \mathcal{L}_t(x_t)=\sum_{i=1}^{d}\alpha_i x_{t,i}+\sum_{i=1}^{d}\max(S_t-x_{t,i},0)-S_t\sum_{i=1}^{d}\alpha_i L t ( x t ) = i = 1 ∑ d α i x t , i + i = 1 ∑ d max ( S t − x t , i , 0 ) − S t i = 1 ∑ d α i
that is, L t ( x t ) + S t ∑ i = 1 d α i = ∑ i = 1 d α i x t , i + ∑ i = 1 d max ( S t − x t , i , 0 ) \mathcal{L}_t(x_t)+S_t\sum_{i=1}^{d}\alpha_i=\sum_{i=1}^{d}\alpha_i x_{t,i}+\sum_{i=1}^{d}\max(S_t-x_{t,i},0) L t ( x t ) + S t ∑ i = 1 d α i = ∑ i = 1 d α i x t , i + ∑ i = 1 d max ( S t − x t , i , 0 ) , which, combined with the previous display, is (11) .
Per-round structural reduction (Theorem 4.1)
The proof of Theorem 4.1 relies on two structural lemmas about the PAVA decomposition of the isotonic projection. Throughout, fix x ~ ∈ R d \tilde{x}\in\mathbb{R}^{d} x ~ ∈ R d (the lemmas are algebraic and need no sign condition), let x : = Π K ( x ~ ) x:=\Pi_{\mathcal{K}}(\tilde{x}) x := Π K ( x ~ ) with PAVA blocks B 1 , … , B p B_1,\ldots,B_p B 1 , … , B p (each B k = { l k , l k + 1 , … , r k } B_k=\{l_k,l_k+1,\ldots,r_k\} B k = { l k , l k + 1 , … , r k } ), and let x ~ B k : = ∣ B k ∣ − 1 ∑ i ∈ B k x ~ i \tilde{x}_{B_k}:=|B_k|^{-1}\sum_{i\in B_k}\tilde{x}_i x ~ B k := ∣ B k ∣ − 1 ∑ i ∈ B k x ~ i denote the block average, so x j = x ~ B k x_j=\tilde{x}_{B_k} x j = x ~ B k for all j ∈ B k j\in B_k j ∈ B k .
Lemma B.1 (Partial-average property of PAVA). For every block B k = { l , … , r } B_k=\{l,\ldots,r\} B k = { l , … , r } and every j ∈ [ l , r ] j\in[l,r] j ∈ [ l , r ] ,
1 j − l + 1 ∑ i = l j x ~ i ≤ x ~ B k . \frac{1}{j-l+1}\sum_{i=l}^{j}\tilde{x}_i\le\tilde{x}_{B_k}. j − l + 1 1 i = l ∑ j x ~ i ≤ x ~ B k . Proof. Recall that x x x solves the quadratic program min z ∈ K 1 2 ∥ z − x ~ ∥ 2 2 \min_{z\in\mathcal{K}}\frac{1}{2}\lVert z-\tilde{x}\rVert_2^2 min z ∈ K 2 1 ∥ z − x ~ ∥ 2 2 , where K = { z : z 1 ≥ z 2 ≥ ⋯ ≥ z d } \mathcal{K}=\{z:z_1\ge z_2\ge\cdots\ge z_d\} K = { z : z 1 ≥ z 2 ≥ ⋯ ≥ z d } . Introducing non-negative Lagrange multipliers λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 for the constraints z i ≥ z i + 1 z_i\ge z_{i+1} z i ≥ z i + 1 , i ∈ [ d − 1 ] i\in[d-1] i ∈ [ d − 1 ] (with the convention λ 0 = λ d = 0 \lambda_0=\lambda_d=0 λ 0 = λ d = 0 ), the KKT stationarity condition at the optimum reads, for i ∈ [ d ] i\in[d] i ∈ [ d ] ,
x ~ i − x i = λ i − 1 − λ i . \tilde{x}_i-x_i=\lambda_{i-1}-\lambda_i. x ~ i − x i = λ i − 1 − λ i . Within block B k = { l , … , r } B_k=\{l,\ldots,r\} B k = { l , … , r } , the projected entries are constant, so the constraints x l − 1 > x l x_{l-1}>x_l x l − 1 > x l and x r > x r + 1 x_r>x_{r+1} x r > x r + 1 are strict at the boundary of the block (with the convention that x 0 = + ∞ x_0=+\infty x 0 = + ∞ and x d + 1 = − ∞ x_{d+1}=-\infty x d + 1 = − ∞ ).
Complementary slackness then forces λ l − 1 = λ r = 0 \lambda_{l-1}=\lambda_r=0 λ l − 1 = λ r = 0 . Summing the stationarity equation over i = l , … , j i=l,\ldots,j i = l , … , j and telescoping,
∑ i = l j ( x ~ i − x ~ B k ) = ∑ i = l j ( λ i − 1 − λ i ) = λ l − 1 − λ j = − λ j ≤ 0 , \sum_{i=l}^{j}(\tilde{x}_i-\tilde{x}_{B_k})=\sum_{i=l}^{j}(\lambda_{i-1}-\lambda_i)=\lambda_{l-1}-\lambda_j=-\lambda_j\le0, i = l ∑ j ( x ~ i − x ~ B k ) = i = l ∑ j ( λ i − 1 − λ i ) = λ l − 1 − λ j = − λ j ≤ 0 ,
where the last inequality uses dual feasibility λ j ≥ 0 \lambda_j\ge0 λ j ≥ 0 . Dividing by j − l + 1 j-l+1 j − l + 1 gives the claim.
Lemma B.2 (Weighted-sum reduction within a block). Let w l ≤ w l + 1 ≤ ⋯ ≤ w r w_l\le w_{l+1}\le\cdots\le w_r w l ≤ w l + 1 ≤ ⋯ ≤ w r be non-decreasing weights on a block B k = { l , … , r } B_k=\{l,\ldots,r\} B k = { l , … , r } . Then
∑ i ∈ B k w i x i = x ~ B k ∑ i ∈ B k w i ≤ ∑ i ∈ B k w i x ~ i . \sum_{i\in B_k}w_i x_i=\tilde{x}_{B_k}\sum_{i\in B_k}w_i\le\sum_{i\in B_k}w_i\tilde{x}_i. i ∈ B k ∑ w i x i = x ~ B k i ∈ B k ∑ w i ≤ i ∈ B k ∑ w i x ~ i . The inequality is strict whenever { x ~ i } i ∈ B k \{\tilde{x}_i\}_{i\in B_k} { x ~ i } i ∈ B k is non-constant and w w w is strictly increasing on [ l , r ] [l,r] [ l , r ] .
Proof. Let c i : = x ~ i − x ~ B k c_i:=\tilde{x}_i-\tilde{x}_{B_k} c i := x ~ i − x ~ B k , so ∑ i = l r c i = 0 \sum_{i=l}^{r}c_i=0 ∑ i = l r c i = 0 and, by Lemma B.1, ∑ i = l j c i ≤ 0 \sum_{i=l}^{j}c_i\le0 ∑ i = l j c i ≤ 0 for every j ∈ [ l , r ] j\in[l,r] j ∈ [ l , r ] . Abel summation yields
∑ i = l r w i c i = w r ⋅ ∑ i = l r c i ⏟ = 0 − ∑ j = l r − 1 ( w j + 1 − w j ) ∑ i = l j c i ⏟ ≤ 0 ≥ 0 , \sum_{i=l}^{r}w_i c_i=w_r\cdot\underbrace{\sum_{i=l}^{r}c_i}_{=0}-\sum_{j=l}^{r-1}(w_{j+1}-w_j)\underbrace{\sum_{i=l}^{j}c_i}_{\le0}\ge0, i = l ∑ r w i c i = w r ⋅ = 0 i = l ∑ r c i − j = l ∑ r − 1 ( w j + 1 − w j ) ≤ 0 i = l ∑ j c i ≥ 0 , which gives ∑ i = l r w i x ~ i ≥ x ~ B k ∑ i = l r w i = ∑ i = l r w i x i \sum_{i=l}^{r}w_i\tilde{x}_i\ge\tilde{x}_{B_k}\sum_{i=l}^{r}w_i=\sum_{i=l}^{r}w_i x_i ∑ i = l r w i x ~ i ≥ x ~ B k ∑ i = l r w i = ∑ i = l r w i x i . For strictness, observe that if { x ~ i } i ∈ B k \{\tilde{x}_i\}_{i\in B_k} { x ~ i } i ∈ B k is non-constant, then ∑ i = l j c i < 0 \sum_{i=l}^{j}c_i<0 ∑ i = l j c i < 0 for some j ∈ [ l , r − 1 ] j\in[l,r-1] j ∈ [ l , r − 1 ] ; if in addition w j + 1 > w j w_{j+1}>w_j w j + 1 > w j , the corresponding term in the Abel sum is strictly positive.
For convenience, we restate Theorem 4.1 below, attaching labels to its individual reduction inequalities so that the proof can refer to them.
Theorem B.3 (Per-round reduction; restatement of Theorem 4.1). For every round t t t , the hidden iterate x ~ t ∈ R + d \tilde{x}_t\in\mathbb{R}_{+}^{d} x ~ t ∈ R + d and the played iterate x t = Π K ( x ~ t ) ∈ K ∩ R + d x_t=\Pi_K(\tilde{x}_t)\in K\cap\mathbb{R}_{+}^{d} x t = Π K ( x ~ t ) ∈ K ∩ R + d satisfy the per-round sharpness and coverage reductions
∑ i = 1 d α i x t , i ≤ ∑ i = 1 d α i x ~ t , i , (21) \sum_{i=1}^{d}\alpha_i x_{t,i}\le\sum_{i=1}^{d}\alpha_i\tilde{x}_{t,i}, \tag*{(21)} i = 1 ∑ d α i x t , i ≤ i = 1 ∑ d α i x ~ t , i , (21) ∑ i = 1 d max ( S t − x t , i , 0 ) ≤ ∑ i = 1 d max ( S t − x ~ t , i , 0 ) , (22) \sum_{i=1}^{d}\max(S_t-x_{t,i},0)\le\sum_{i=1}^{d}\max(S_t-\tilde{x}_{t,i},0), \tag*{(22)} i = 1 ∑ d max ( S t − x t , i , 0 ) ≤ i = 1 ∑ d max ( S t − x ~ t , i , 0 ) , (22) and consequently the per-round loss reduction
L t ( x t ) ≤ L t ( x ~ t ) . (23) L_t(x_t)\le L_t(\tilde{x}_t). \tag*{(23)} L t ( x t ) ≤ L t ( x ~ t ) . (23) Both (21) and (23) are strict whenever x ~ t ∉ K \tilde{x}_t\notin K x ~ t ∈ / K .
Proof of Theorem 4.1. By the WIS decomposition (11) , the loss reduction (23) is implied by the sharpness reduction (21) and the coverage reduction (22), since the constant S t ∑ i α i S_t\sum_i\alpha_i S t ∑ i α i cancels. We prove each block by block.
Sharpness. On any block B k B_k B k , the miscoverage levels α l < α l + 1 < ⋯ < α r \alpha_l<\alpha_{l+1}<\cdots<\alpha_r α l < α l + 1 < ⋯ < α r are strictly increasing (by our convention). Lemma B.2 with w i = α i w_i=\alpha_i w i = α i then gives ∑ i ∈ B k α i x t , i ≤ ∑ i ∈ B k α i x ~ t , i \sum_{i\in B_k}\alpha_i x_{t,i}\le\sum_{i\in B_k}\alpha_i\tilde{x}_{t,i} ∑ i ∈ B k α i x t , i ≤ ∑ i ∈ B k α i x ~ t , i , with strict inequality whenever { x ~ t , i } i ∈ B k \{\tilde{x}_{t,i}\}_{i\in B_k} { x ~ t , i } i ∈ B k is non-constant. PAVA pools coordinates only when consecutive (sub-)block averages violate the order, which forces a strict difference between elements; hence any block of size ∣ B k ∣ ≥ 2 |B_k|\ge2 ∣ B k ∣ ≥ 2 has non-constant entries. Summing over k k k gives (21) , with strict inequality whenever x ~ t ∉ K \tilde{x}_t\notin K x ~ t ∈ / K (equivalently, whenever some block has size ≥ 2 \ge2 ≥ 2 ). Coverage. The map ϕ ( x ) : = max ( S t − x , 0 ) \phi(x) := \max(S_t - x, 0) ϕ ( x ) := max ( S t − x , 0 ) is convex on R \mathbb{R} R . Jensen’s inequality applied to x ~ t \tilde{x}_t x ~ t restricted to B k B_k B k gives
∑ i ∈ B k max ( S t − x t , i , 0 ) = ∣ B k ∣ ϕ ( x ~ B k ) ≤ ∑ i ∈ B k ϕ ( x ~ t , i ) = ∑ i ∈ B k max ( S t − x ~ t , i , 0 ) . (24) \sum_{i \in B_k} \max(S_t - x_{t,i}, 0) = |B_k| \phi(\tilde{x}_{B_k}) \le\sum_{i \in B_k} \phi(\tilde{x}_{t,i}) = \sum_{i \in B_k} \max(S_t - \tilde{x}_{t,i}, 0). \tag*{(24)} i ∈ B k ∑ max ( S t − x t , i , 0 ) = ∣ B k ∣ ϕ ( x ~ B k ) ≤ i ∈ B k ∑ ϕ ( x ~ t , i ) = i ∈ B k ∑ max ( S t − x ~ t , i , 0 ) . (24)
Summing over k k k gives (22).
Loss. Summing (21) and (22) and applying (11) gives (23) , which is strict whenever (21) is strict, i.e., whenever x ~ t ∉ K \tilde{x}_t \notin\mathcal{K} x ~ t ∈ / K .
Experimental details and additional results
This appendix collects the dataset descriptions, forecasting-pipeline configurations, and complete results referenced from § 5 .
Datasets and forecasting pipelines
Synthetic streams. All synthetic scores are non-negative trajectories, truncated at zero. Each trajectory is generated from a fixed base seed; the 10 seeds we use are 42, 43, … \ldots … , 51.
Sinusoidal: S t = max ( 0 , m + a sin ( 2 π t / p ) + ε t ) S_t = \max(0, m + a \sin(2\pi t/p) + \varepsilon_t) S t = max ( 0 , m + a sin ( 2 π t / p ) + ε t ) with center m = 11 m = 11 m = 11 and amplitude a = 9 a = 9 a = 9 (so that S t S_t S t oscillates between { 2 , 20 } \{2, 20\} { 2 , 20 } ), period p = 200 p = 200 p = 200 , ε t ∼ N ( 0 , 0.3 2 ) \varepsilon_t \sim N(0, 0.3^2) ε t ∼ N ( 0 , 0. 3 2 ) , T = 3,000 T = 3{,}000 T = 3 , 000 . Stresses cyclic non-stationarity.
Stationary and mixed regimes: a constant baseline or a quadratic trend overlaid with rare exponential spikes, smoothed by a 25-step rolling maximum (Appendices C.7.6 and C.7.7). Stresses heavy tails.
Real-world streams.
AAPL, AMZN, GOOGL: daily opening prices of the three stocks, from Nguyen [2018], covering the period 2006-01-03 to 2017-12-29 (T = 3,020 T = 3{,}020 T = 3 , 020 rounds: the 3,019 trading days of each stock plus one date of the panel missing for them, filled by interpolation). Forecasting model: Prophet Taylor and Letham, [38 ] re-fit at every step on log-prices using all data up to time t − 1 t - 1 t − 1 to produce a one-step-ahead forecast Y ^ t \hat{Y}_t Y ^ t . Nonconformity score S t = ∣ Y t − Y ^ t ∣ S_t = \lvert Y_t - \hat{Y}_t \rvert S t = ∣ Y t − Y ^ t ∣ .
Electricity (elec2): half-hourly New South Wales electricity demand from Harries [ [20 ] , restricted to a non-stationary regime; one-step-ahead forecasts produced by an autoregressive model.
Detailed update rules
This subsection records the explicit update rules of the four method families compared in § 5 : coordinate-wise universal portfolio, p p p -norm online mirror descent, coordinate-wise Krichevsky–Trofimov bettor, and MultiQT. The first three are base online learners that we run both in their vanilla form and through the lazy projection wrapper of Algorithm 1; MultiQT, which is by construction a projected algorithm, is presented in its single canonical form. All wrapped variants share the same outer loop: receive the hidden iterate x ~ t ∈ R + d \tilde{x}_t \in\mathbb{R}_{+}^{d} x ~ t ∈ R + d from the base learner, project to obtain x t = Π K ( x ~ t ) x_t = \Pi_{\mathcal{K}}(\tilde{x}_t) x t = Π K ( x ~ t ) , observe the score S t S_t S t , compute the subgradient g t g_t g t at x t x_t x t via (2) , and feed g t g_t g t back to the base learner. The unprojected variants are obtained by replacing the projected play x t = Π K ( x ~ t ) x_t = \Pi_{\mathcal{K}}(\tilde{x}_t) x t = Π K ( x ~ t ) by x t = x ~ t x_t = \tilde{x}_t x t = x ~ t throughout, leaving the rest of the update untouched. Every base learner, including MultiQT, outputs valid radii following § 3 : its raw radius x t , j x_{t,j} x t , j is replaced by x ~ t , j = max ( x t , j , 0 ) \tilde{x}_{t,j} = \max(x_{t,j}, 0) x ~ t , j = max ( x t , j , 0 ) , where 0 encodes the empty set, while its internal state and update rule are left unchanged Liu et al., [25 ] , App. F.2].
Coordinate-wise Universal Portfolio (UP-OCP)
Algorithm. Coordinate-wise UP-OCP runs an independent scalar UP-OCP instance Liu et al., [25 ] at each miscoverage level α j \alpha_j α j and synchronizes only at prediction time through the projection. At level α j \alpha_j α j , the scalar instance treats the betting game as a two-asset conformal market [25 Def. 4.1] with returns w t , 1 ( j ) = − g t , j / α j + 1 w_{t,1}^{(j)}=-g_{t,j}/\alpha_j+1 w t , 1 ( j ) = − g t , j / α j + 1 and w t , 2 ( j ) = 1 + g t , j / ( 1 − α j ) w_{t,2}^{(j)}=1+g_{t,j}/(1-\alpha_j) w t , 2 ( j ) = 1 + g t , j / ( 1 − α j ) , and chooses portfolio weight λ t ( j ) \lambda_t^{(j)} λ t ( j ) as the wealth-weighted average over [ 0 , 1 ] [0,1] [ 0 , 1 ] under the Beta( 1 / 2 , 1 / 2 ) (1/2,1/2) ( 1/2 , 1/2 ) prior. Specializing the universal-portfolio update to this market admits the closed form
λ t ( j ) = 1 t ( ∑ s = 1 t − 1 1 { g s , j = − ( 1 − α j ) } + 1 2 ) = N t − 1 ( j ) + 1 / 2 t , \lambda_t^{(j)}=\frac{1}{t}\left(\sum_{s=1}^{t-1}\mathbf{1}\{g_{s,j}=-(1-\alpha_j)\}+\frac{1}{2}\right)=\frac{N_{t-1}^{(j)}+1/2}{t}, λ t ( j ) = t 1 ( s = 1 ∑ t − 1 1 { g s , j = − ( 1 − α j )} + 2 1 ) = t N t − 1 ( j ) + 1/2 ,
where N t − 1 ( j ) N_{t-1}^{(j)} N t − 1 ( j ) counts past per-level miscoverage events. The hidden iterate is the wealth-to-radius mapping x ~ t , j = max ( W t − 1 ( j ) ( λ t ( j ) − α j ) / ( α j ( 1 − α j ) ) , 0 ) \widetilde{x}_{t,j}=\max\left(W_{t-1}^{(j)}(\lambda_t^{(j)}-\alpha_j)/(\alpha_j(1-\alpha_j)),0\right) x t , j = max ( W t − 1 ( j ) ( λ t ( j ) − α j ) / ( α j ( 1 − α j )) , 0 ) , clipped as in the scalar UP-OCP [25 App. F.2] , and the wealth recursion W t ( j ) = W t − 1 ( j ) ⋅ ( λ t ( j ) w t , 1 ( j ) + ( 1 − λ t ( j ) ) w t , 2 ( j ) ) W_t^{(j)}=W_{t-1}^{(j)}\cdot(\lambda_t^{(j)}w_{t,1}^{(j)}+(1-\lambda_t^{(j)})w_{t,2}^{(j)}) W t ( j ) = W t − 1 ( j ) ⋅ ( λ t ( j ) w t , 1 ( j ) + ( 1 − λ t ( j ) ) w t , 2 ( j ) ) simplifies, on the binary outcome g t , j ∈ { − ( 1 − α j ) , α j } g_{t,j}\in\{-(1-\alpha_j),\alpha_j\} g t , j ∈ { − ( 1 − α j ) , α j } , to the multiplicative updates in Algorithm 2. The coordinate-wise nature is essential: the per-level wealth and miscoverage counter make every level adapt to its own variance budget α j ( 1 − α j ) \alpha_j(1-\alpha_j) α j ( 1 − α j ) , which is what ultimately produces the log d \sqrt{\log d} log d rate of Theorem 3.7 .
Hyperparameters. UP-OCP is parameter-free; the initial wealth is fixed at 1 for every dataset and every level (see § 5 ), matching the theoretical analysis. No tuning is performed.
Projected vs. unprojected. The projected variant UP-OCP-Iso plays x t = Π K ( x ~ t ) x_t=\Pi_{\mathcal{K}}(\widetilde{x}_t) x t = Π K ( x t ) on Line 8 of Algorithm 2 below; the unprojected variant simply plays x t = x ~ t x_t=\widetilde{x}_t x t = x t . Both feed the gradient evaluated at the played iterate back into the per-level wealth recursions.
Algorithm 2 Coordinate-wise UP-OCP with lazy projection.
Input: miscoverage levels α 1 < ⋯ < α d \alpha_1<\cdots<\alpha_d α 1 < ⋯ < α d
Initialize W 0 ( j ) ← 1 W_0^{(j)}\leftarrow1 W 0 ( j ) ← 1 and miscoverage count N ( j ) ← 0 N^{(j)}\leftarrow0 N ( j ) ← 0 for each j ∈ [ d ] j\in[d] j ∈ [ d ]
for t = 1 , 2 , … t=1,2,\ldots t = 1 , 2 , … do
for j = 1 , … , d j=1,\ldots,d j = 1 , … , d (in parallel) do
λ t ( j ) ← ( N ( j ) + 1 / 2 ) / t \lambda_t^{(j)}\leftarrow(N^{(j)}+1/2)/t λ t ( j ) ← ( N ( j ) + 1/2 ) / t
x ~ t , j ← max ( W t − 1 ( j ) ⋅ ( λ t ( j ) − α j ) / ( α j ( 1 − α j ) ) , 0 ) \widetilde{x}_{t,j}\leftarrow\max\left(W_{t-1}^{(j)}\cdot(\lambda_t^{(j)}-\alpha_j)/(\alpha_j(1-\alpha_j)),0\right) x t , j ← max ( W t − 1 ( j ) ⋅ ( λ t ( j ) − α j ) / ( α j ( 1 − α j )) , 0 ) \quad (0 0 0 encodes ∅ \emptyset ∅ )
end for
x t ← Π K ( x ~ t ) x_t\leftarrow\Pi_{\mathcal{K}}(\widetilde{x}_t) x t ← Π K ( x t ) \quad (unprojected: x t ← x ~ t x_t\leftarrow\widetilde{x}_t x t ← x t ); observe S t S_t S t
for j = 1 , … , d j=1,\ldots,d j = 1 , … , d (in parallel) do
if C ^ t ( Y ^ t , x t , j ) \widehat{C}_t(\widehat{Y}_t,x_{t,j}) C t ( Y t , x t , j ) does not cover Y t Y_t Y t , i.e., S t > x t , j S_t>x_{t,j} S t > x t , j or x t , j = 0 x_{t,j}=0 x t , j = 0 then
N ( j ) ← N ( j ) + 1 N^{(j)}\leftarrow N^{(j)}+1 N ( j ) ← N ( j ) + 1 ; W t ( j ) ← W t − 1 ( j ) ⋅ λ t ( j ) / α j W_t^{(j)}\leftarrow W_{t-1}^{(j)}\cdot\lambda_t^{(j)}/\alpha_j W t ( j ) ← W t − 1 ( j ) ⋅ λ t ( j ) / α j
else
W t ( j ) ← W t − 1 ( j ) ⋅ ( 1 − λ t ( j ) ) / ( 1 − α j ) W_t^{(j)}\leftarrow W_{t-1}^{(j)}\cdot(1-\lambda_t^{(j)})/(1-\alpha_j) W t ( j ) ← W t − 1 ( j ) ⋅ ( 1 − λ t ( j ) ) / ( 1 − α j )
end if
end for
end for
p-norm Online Mirror Descent
Algorithm. p p p -norm OMD is online mirror descent on R d \mathbb{R}^d R d with regularizer ψ ( x ) = 1 2 ∥ x ∥ p 2 \psi(x)=\frac{1}{2}\lVert x\rVert_p^2 ψ ( x ) = 2 1 ∥ x ∥ p 2 for p ∈ ( 1 , 2 ] p\in(1,2] p ∈ ( 1 , 2 ] and conjugate exponent q = p / ( p − 1 ) q=p/(p-1) q = p / ( p − 1 ) . Maintaining a dual iterate θ t ∈ R d \theta_t\in\mathbb{R}^d θ t ∈ R d initialized at 0 0 0 , the primal mirror map is the gradient of the conjugate regularizer [27 , 36 ] , which yields the explicit closed form of the raw radius (clipped as x ~ t , j = max ( z t , j , 0 ) \widetilde{x}_{t,j}=\max(z_{t,j},0) x t , j = max ( z t , j , 0 ) , § 3 )
z t , j = ∥ θ t ∥ q 2 − q sign ( θ t , j ) ∣ θ t , j ∣ q − 1 , j = 1 , … , d , z_{t,j}=\lVert\theta_t\rVert_q^{2-q}\operatorname{sign}(\theta_{t,j})\lvert\theta_{t,j}\rvert^{q-1},\qquad j=1,\ldots,d, z t , j = ∥ θ t ∥ q 2 − q sign ( θ t , j ) ∣ θ t , j ∣ q − 1 , j = 1 , … , d ,
followed by the standard dual update θ t + 1 = θ t − η g t \theta_{t+1}=\theta_t-\eta g_t θ t + 1 = θ t − η g t . The choice p = 2 log d / ( 2 log d − 1 ) p=2\log d/(2\log d-1) p = 2 log d / ( 2 log d − 1 ) recommended by Corollary 3.6 interpolates between OGD (p = 2 p=2 p = 2 ) and ℓ ∞ \ell_\infty ℓ ∞ -style updates as d d d grows: it makes the regularizer ( p − 1 ) (p-1) ( p − 1 ) -strongly convex with respect to ∥ ⋅ ∥ p \lVert\cdot\rVert_p ∥ ⋅ ∥ p while keeping the conjugate gradient norm ∥ g t ∥ q 2 \lVert g_t\rVert_q^2 ∥ g t ∥ q 2 at most d 2 / q = e d^{2/q}=e d 2/ q = e , eliminating the polynomial dimension dependence of ℓ 2 \ell_2 ℓ 2 regret. The case p = 2 p=2 p = 2 recovers OGD with lazy isotonic projection, i.e., MultiQT with a constant step size, and is the closest direct comparison with it.
Hyperparameters and tuning. The constant step size η \eta η is the only tuned knob. Following standard practice for adaptive conformal baselines [14 , 29 ] , we run a per-dataset grid search over η ∈ { 2 − 2 , 2 − 1 , 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 } \eta\in\{2^{-2},2^{-1},1,2,4,8,16,32,64,128,256,512,1024\} η ∈ { 2 − 2 , 2 − 1 , 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 } and report the value whose mean-width vs. empirical-coverage Pareto frontier dominates the others on α ∈ [ 0.03 , 0.25 ] \alpha\in[0.03,0.25] α ∈ [ 0.03 , 0.25 ] . For both AAPL and the sinusoidal stream the selected η \eta η is 64. We emphasize that this oracle-style selection is a best-case, not realistic, deployment of the method: a practitioner without access to the full stream cannot select η \eta η this way. The exponent p p p is fixed at 2 log d / ( 2 log d − 1 ) 2\log d/(2\log d-1) 2 log d / ( 2 log d − 1 ) from theory and not tuned. Initialization is θ 1 = 0 \boldsymbol{\theta}_1=\mathbf{0} θ 1 = 0 .
Projected vs. unprojected. The projected variant p p p -norm-OMD-Iso plays x t = Π K ( x ~ t ) \mathbf{x}_t=\Pi_{\mathcal{K}}(\widetilde{\mathbf{x}}_t) x t = Π K ( x t ) on Line 4 below; the unprojected variant plays x t = x ~ t \mathbf{x}_t=\widetilde{\mathbf{x}}_t x t = x t . The dual update is identical in both cases.
Algorithm 3 p p p -norm online mirror descent with lazy projection.
Input: p ∈ ( 1 , 2 ] p\in(1,2] p ∈ ( 1 , 2 ] (with conjugate exponent q : = p / ( p − 1 ) q:=p/(p-1) q := p / ( p − 1 ) ), step size η > 0 \eta>0 η > 0 . Set θ 1 = 0 \boldsymbol{\theta}_1=\mathbf{0} θ 1 = 0
for t = 1 , 2 , … t=1,2,\ldots t = 1 , 2 , … do
x ~ t , j ← max ( ∥ θ t ∥ q 2 − q sign ( θ t , j ) ⋅ ∣ θ t , j ∣ q − 1 , 0 ) \widetilde{x}_{t,j}\leftarrow\max\left(\lVert\boldsymbol{\theta}_t\rVert_q^{2-q}\operatorname{sign}(\theta_{t,j})\cdot\lvert\theta_{t,j}\rvert^{q-1},0\right) x t , j ← max ( ∥ θ t ∥ q 2 − q sign ( θ t , j ) ⋅ ∣ θ t , j ∣ q − 1 , 0 ) for j = 1 , … , d j=1,\ldots,d j = 1 , … , d (0 0 0 encodes ∅ \varnothing ∅ )
x t ← Π K ( x ~ t ) \mathbf{x}_t\leftarrow\Pi_{\mathcal{K}}(\widetilde{\mathbf{x}}_t) x t ← Π K ( x t ) (unprojected: x t ← x ~ t \mathbf{x}_t\leftarrow\widetilde{\mathbf{x}}_t x t ← x t ); observe S t S_t S t ; g t ∈ ∂ L t ( x t ) \mathbf{g}_t\in\partial\mathcal{L}_t(\mathbf{x}_t) g t ∈ ∂ L t ( x t ) via (2)
θ t + 1 ← θ t − η g t \boldsymbol{\theta}_{t+1}\leftarrow\boldsymbol{\theta}_t-\eta\mathbf{g}_t θ t + 1 ← θ t − η g t
end for
Coordinate-wise Krichevsky–Trofimov bettor (KT)
Algorithm. Coordinate-wise KT [25 , 29 ] runs an independent KT bettor at each level α j \alpha_j α j , treating the per-level subgradients as the outcomes of a coin-betting game. At level α j \alpha_j α j , the bettor maintains wealth W t ( j ) W_t^{(j)} W t ( j ) and a betting fraction β t ( j ) = − Σ t − 1 ( j ) / t \beta_t^{(j)}=-\Sigma_{t-1}^{(j)}/t β t ( j ) = − Σ t − 1 ( j ) / t where Σ t − 1 ( j ) = ∑ s = 1 t − 1 g s , j \Sigma_{t-1}^{(j)}=\sum_{s=1}^{t-1}g_{s,j} Σ t − 1 ( j ) = ∑ s = 1 t − 1 g s , j is the cumulative subgradient [29 ] ; the hidden iterate is x ~ t , j = max ( β t ( j ) W t ( j ) , 0 ) \widetilde{x}_{t,j}=\max(\beta_t^{(j)}W_{t}^{(j)},0) x t , j = max ( β t ( j ) W t ( j ) , 0 ) and the wealth follows W t ( j ) = W t − 1 ( j ) ( 1 − β t ( j ) g t , j ) W_t^{(j)}=W_{t-1}^{(j)}(1-\beta_t^{(j)}g_{t,j}) W t ( j ) = W t − 1 ( j ) ( 1 − β t ( j ) g t , j ) . Unlike UP-OCP, the KT bettor uses a closed-form betting rule that is min-max optimal for symmetric coin-betting games (i.e., α j = 1 / 2 \alpha_j=1/2 α j = 1/2 ); it does not adapt to the asymmetry of the per-level pinball loss when α j \alpha_j α j is small. This is the source of the under-performance of KT at high target coverage in our experiments, and is the reason UP-OCP achieves the strictly tighter rate α j ( 1 − α j ) log T / T \sqrt{\alpha_j(1-\alpha_j)\log T/T} α j ( 1 − α j ) log T / T .
Hyperparameters. KT is parameter-free; the initial wealth is fixed at 1 across all datasets and levels, matching the theoretical analysis. No tuning is performed.
Projected vs. unprojected. The projected variant KT-Iso plays x t = Π K ( x ~ t ) \mathbf{x}_t=\Pi_{\mathcal{K}}(\widetilde{\mathbf{x}}_t) x t = Π K ( x t ) on Line 8; the unprojected variant plays x t = x ~ t \mathbf{x}_t=\widetilde{\mathbf{x}}_t x t = x t .
MultiQT
Algorithm. MultiQT [14 ] is the lazy-projection-wrapped instance of online gradient descent: in our notation it coincides with Algorithm 3 restricted to p = 2 p=2 p = 2 (so q = 2 q=2 q = 2 ), composed with the isotonic projection. Unlike p p p -norm OMD with constant step size, MultiQT uses the data-driven adaptive step-size schedule from Ding et al. [ [14 ] , Section 5: at each round t t t ,
η t = max ( 0.1 ⋅ Q 0.9 ( { S s : s ∈ [ max ( 1 , t − 50 ) , t − 1 ] } ) , 0.1 ) . \eta_t=\max\left(0.1\cdot Q_{0.9}\left(\{S_s:s\in[\max(1,t-50),t-1]\}\right),0.1\right). η t = max ( 0.1 ⋅ Q 0.9 ( { S s : s ∈ [ max ( 1 , t − 50 ) , t − 1 ]} ) , 0.1 ) .
i.e. a multiplicative factor of the empirical 90th-percentile of the most recent 50 scores, lower-bounded by 0.1 to prevent collapse early in the stream. This schedule effectively scales the step with the magnitude
Algorithm 4 Coordinate-wise Krichevsky–Trofimov bettor with lazy projection.
1: Input: miscoverage levels $\alpha_1 < \cdots < \alpha_d$
2: Initialize $W_0^{(j)} \leftarrow 1$ and cumulative gradient $\Sigma^{(j)} \leftarrow 0$ for each $j \in [d]$
3: for $t = 1, 2, \ldots$ do
4: for $j = 1, \ldots, d$ (in parallel) do
5: betting fraction $\beta_t^{(j)} \leftarrow -\Sigma^{(j)}/t$
6: $\tilde{x}_{t,j} \leftarrow \max(\beta_t^{(j)} \cdot W_{t-1}^{(j)}, 0)$ ($0$ encodes $\varnothing$)
7: end for
8: $x_t \leftarrow \Pi_K(\tilde{x}_t)$ (unprojected: $x_t \leftarrow \tilde{x}_t$); observe $S_t$; $g_t \in \partial L_t(x_t)$ via {xref}`(2)`
9: for $j = 1, \ldots, d$ (in parallel) do
10: $W_t^{(j)} \leftarrow W_{t-1}^{(j)} \cdot (1 - \beta_t^{(j)} g_{t,j})$; $\Sigma^{(j)} \leftarrow \Sigma^{(j)} + g_{t,j}$
11: end for
12: end for
of recent residuals, eliminating sensitivity to the score scale at the cost of introducing a sliding window and a multiplicative constant; both are inherited verbatim from Ding et al. [ [14 ] . Because MultiQT is by design a projected algorithm, we report only its projected form and use it as the prior baseline against which we compare every other (base learner, projection) combination.
Hyperparameters and tuning. The window length (50), tail quantile (0.9), multiplicative factor (0.1), and lower bound (0.1) are all taken from the public implementation of Ding et al. [ [14 ] without modification. The dual iterate is initialized at θ 1 = 0 \theta_1 = 0 θ 1 = 0 , matching p p p -norm OMD. As with p p p -norm OMD, this adaptive schedule is best understood as a tuned baseline: its constants reflect choices made by Ding et al. [ [14 ] on their own benchmarks rather than on ours.
Width distribution analysis
The mean and tail-quantile statistics in § 5 already give a rough picture of the projection’s effect on sharpness, but they do not capture how it reshapes the underlying distribution of widths. Figure 3 overlays the histograms of per-round predicted widths on the sinusoidal dataset at two representative levels, α = 0.03 \alpha= 0.03 α = 0.03 and α = 0.25 \alpha= 0.25 α = 0.25 , for the two base learners UP-OCP and p p p -norm OMD that have a meaningful projected/unprojected pair.
Figure 3. Distribution of per-round prediction-set widths on the sinusoidal stream, at α = 0.03 \alpha= 0.03 α = 0.03 (top row) and α = 0.25 \alpha= 0.25 α = 0.25 (bottom row). Each panel overlays the histogram of widths for the unprojected base learner (filled, solid color) against the projected variant (outlined, black border), at the same α \alpha α and base learner.
The qualitative pattern is consistent across the two base learners. The projection consistently concentrates the distribution onto a tighter range: the heaviest right-tail mass is removed, and the overall distribution conforms closer to two narrower modes (the lower and higher modes correspond to the extrema pattern of the sinusoidal wave). From a downstream-decision perspective, this reshaping is more useful than a small mean improvement, because the cost of an unusually wide set is non-linear for most users (e.g., capacity reservation, contract pricing).
Weighted Interval Score
Table 2 extends Figure 2 to every dataset. The projection lowers the WIS of UP-OCP and p p p -norm OMD on every dataset; for KT, whose isotonicity violations are small (Table 3 ), the two variants are within 0.3% of each other. These comparisons are across two different runs, whose trajectories differ, so they are not covered by Theorem 4.1 . Table 3 checks the theorem in its exact, within-run form: the hidden iterate violates isotonicity on 127,206 of the 127,680 post-burn-in rounds (99.6%) across both datasets and the four projected methods, and on every one of them the projection strictly reduced both the WIS and its sharpness component without increasing the coverage penalty.
Table 2. Average per-round WIS over all d = 100 d = 100 d = 100 levels (post burn-in; synthetic streams: mean over 10 seeds), and its sharpness and coverage-penalty components. Bold marks the smallest WIS on each dataset.
Table 3. Within-run check of Theorem 4.1 . For each projected method, the hidden iterate x ~ t \tilde{x}_t x ~ t and the played iterate x t = Π K ( x ~ t ) x_t = \Pi_K(\tilde{x}_t) x t = Π K ( x ~ t ) are logged at every post-burn-in round (sinusoidal: all 10 seeds). Columns: share of rounds with x ~ t ∉ K \tilde{x}_t \notin K x ~ t ∈ / K ; share of those rounds on which the WIS and its sharpness component are strictly reduced, and the coverage penalty is not increased (up to 10 − 12 10^{-12} 1 0 − 12 relative rounding); median and maximum per-round relative WIS reduction 1 − WIS ( x t ) / WIS ( x ~ t ) 1 - \operatorname{WIS}(x_t)/\operatorname{WIS}(\tilde{x}_t) 1 − WIS ( x t ) / WIS ( x ~ t ) ; average WIS of the hidden and of the played iterates.
Step-size sensitivity and adaptive step sizes for p p p -norm OMD
Corollary 3.6 favors η → ∞ \eta\to\infty η → ∞ , whereas F T ( u ) F_T(u) F T ( u ) diverges as η → ∞ \eta\to\infty η → ∞ for every u u u . The two measure different things: small miscoverage alone is a weak target, attained even by data-free predictors [25 App. H.5] , while the regret bound controls efficiency, since it bounds half the WIS (§ 4 ) of the played sets against every comparator. Our step-size sweep confirms the trade-off (Appendices § 8 .§ 4 and § 10 .§ 5 ).
Sensitivity. Table 4 reports, for projected p p p -norm OMD with p = 2 log d / ( 2 log d − 1 ) p = 2 \log d/(2 \log d - 1) p = 2 log d / ( 2 log d − 1 ) , the coverage error (mean over all d = 100 d = 100 d = 100 levels of ∣ Coverage T , i − ( 1 − α i ) ∣ |\operatorname{Coverage}_{T,i} - (1 - \alpha_i)| ∣ Coverage T , i − ( 1 − α i ) ∣ , post burn-in) and the average per-round WIS over the whole step-size grid. The coverage error decreases monotonically in η \eta η , as Corollary 3.6 suggests, while the WIS is minimized at a finite step size (η = 64 \eta= 64 η = 64 on AAPL and η = 32 \eta= 32 η = 32 on the sinusoidal stream) and roughly doubles between η = 64 \eta= 64 η = 64 and η = 1024 \eta= 1024 η = 1024 . Every η ∈ [ 16 , 128 ] \eta\in[16, 128] η ∈ [ 16 , 128 ] stays within about 10% of the best WIS on both datasets, and the same η = 64 \eta= 64 η = 64 is within about 2.2% of the best WIS on both streams, which are of very different nature (stock residuals and a synthetic wave).
Table 4. Projected p p p -norm OMD: coverage error (%, mean over all levels) / average per-round WIS, for each constant step size η \eta η of the grid and for the plug-in step size (25) .
A plug-in step size. The balanced step size of § 3.1 , η ⋆ = 2 ( p − 1 ) B T / ( d 2 / q T ) \eta^\star= 2(p-1)B_T/(d^{2/q}T) η ⋆ = 2 ( p − 1 ) B T / ( d 2/ q T ) , depends on the unknown average budget B T / T B_T/T B T / T . Replacing it by its running estimate gives the step size used for the update after round t ≥ 2 t \ge2 t ≥ 2 (in our experiments, updates start after the warm-up),
η t = 2 ( p − 1 ) d 2 / q ⋅ 1 t − 1 ∑ τ = 1 t − 1 L τ ( 0 ) , L τ ( 0 ) = S τ ∑ i = 1 d ( 1 − α i ) , (25) \eta_t = \frac{2(p-1)}{d^{2/q}} \cdot\frac{1}{t-1}\sum_{\tau=1}^{t-1}\mathcal{L}_{\tau}(0), \qquad\mathcal{L}_{\tau}(0) = S_{\tau}\sum_{i=1}^{d}(1-\alpha_i), \tag*{(25)} η t = d 2/ q 2 ( p − 1 ) ⋅ t − 1 1 τ = 1 ∑ t − 1 L τ ( 0 ) , L τ ( 0 ) = S τ i = 1 ∑ d ( 1 − α i ) , (25)
which uses only revealed scores. Its WIS is about 3.5% above the grid optimum on both datasets (Table 4 ); its coverage error on the sinusoidal stream (0.29%) matches that of the grid-selected η = 64 \eta= 64 η = 64 (0.30%), while on AAPL it shows a mild under-coverage of 3.3%, comparable to the parameter-free methods. This schedule is only a heuristic: ( η t ) (\eta_t) ( η t ) need not be monotone, so the standard analysis of OMD with non-increasing step sizes does not apply, and we claim no bound for it.
A doubling-trick variant with guarantees. Run Algorithm 3 in epochs k = 0 , 1 , … k = 0, 1, \ldots k = 0 , 1 , … , restarting the base learner at the beginning of each epoch (the projection layer is stateless), with the constant step size η k = 2 ( p − 1 ) b k / d 2 / q \eta_k = 2(p-1)b_k/d^{2/q} η k = 2 ( p − 1 ) b k / d 2/ q and b k = 2 k b 0 b_k = 2^k b_0 b k = 2 k b 0 , where b 0 = s 0 ∑ i = 1 d ( 1 − α i ) b_0 = s_0\sum_{i=1}^{d}(1-\alpha_i) b 0 = s 0 ∑ i = 1 d ( 1 − α i ) for some s 0 > 0 s_0 > 0 s 0 > 0 . Epoch k k k ends after the first round at which the average of L τ ( 0 ) \mathcal{L}_{\tau}(0) L τ ( 0 ) over the rounds of the epoch exceeds 2 b k 2b_k 2 b k . On the first n k − 1 n_k - 1 n k − 1 of its n k n_k n k rounds, the epoch’s budget is at most 2 b k ( n k − 1 ) 2b_k(n_k - 1) 2 b k ( n k − 1 ) , so Theorem 3.4 applied to them, as in Corollary 3.6 with q = 2 log d q = 2\log d q = 2 log d , gives
∥ G ( k ) ∥ q ≤ 3 e ( 2 log d − 1 ) n k + e , \lVert G^{(k)} \rVert_q \le\sqrt{3e(2\log d-1)n_k}+\sqrt{e}, ∥ G ( k ) ∥ q ≤ 3 e ( 2 log d − 1 ) n k + e ,
where the last term accounts for the last round. Summing over the K K K epochs and applying Cauchy–Schwarz,
max i ∈ [ d ] MisCov T , i ≤ 3 e ( 2 log d − 1 ) K T + e K T . \max_{i \in[d]}\operatorname{MisCov}_{T,i} \le\sqrt{\frac{3e(2\log d-1)K}{T}}+\frac{\sqrt{e}K}{T}. i ∈ [ d ] max MisCov T , i ≤ T 3 e ( 2 log d − 1 ) K + T e K .
Since L τ ( 0 ) = S τ ∑ i ( 1 − α i ) ≤ D T γ ∑ i ( 1 − α i ) \mathcal{L}_{\tau}(0)=S_{\tau}\sum_i(1-\alpha_i)\le DT^\gamma\sum_i(1-\alpha_i) L τ ( 0 ) = S τ ∑ i ( 1 − α i ) ≤ D T γ ∑ i ( 1 − α i ) under Assumption 2.1 , no epoch ends once 2 b k ≥ D T γ ∑ i ( 1 − α i ) 2b_k \ge DT^\gamma\sum_i(1-\alpha_i) 2 b k ≥ D T γ ∑ i ( 1 − α i ) , and hence K ≤ 1 + log 2 ( D T γ / s 0 ) = O ( γ log T + log ( D / s 0 ) ) K \le1+\log_2(DT^\gamma/s_0)=O(\gamma\log T+\log(D/s_0)) K ≤ 1 + log 2 ( D T γ / s 0 ) = O ( γ log T + log ( D / s 0 )) , independently of d d d (cf. [11 ] , Sec. 2.3). For bounded scores (γ = 0 \gamma= 0 γ = 0 ), this is the balanced rate up to a factor 3 K / 2 \sqrt{3K/2} 3 K /2 that depends only on D / s 0 D/s_0 D / s 0 ; under polynomial growth it pays a log T \sqrt{\log T} log T factor, multiplicatively, whereas Theorem 3.7 pays it additively. In both cases the step size stays bounded, so the regret bound does not diverge.
Varying the number of levels
Table 5 reports the realized worst-level miscoverage error max i MisCov T , i \max_i\operatorname{MisCov}_{T,i} max i MisCov T , i on the sinusoidal stream (T = 3,000 T = 3{,}000 T = 3 , 000 , levels uniformly spaced in [ 0.001 , 0.5 ] [0.001, 0.5] [ 0.001 , 0.5 ] , 10 seeds; unlike § 5 , these runs use no warm-up period, so the d = 100 d = 100 d = 100 column differs slightly from the main experiments) as the number of levels grows from d = 5 d = 5 d = 5 to d = 1,000 d = 1{,}000 d = 1 , 000 , for projected p p p -norm OMD with the balanced step size of § 3.1 , projected coordinate-wise UP-ÕCP, and MultiQT. The errors of UP-ÕCP-Iso and MultiQT are flat in d d d , and that of p p p -norm OMD grows slowly while staying an order of magnitude below that of MultiQT. The d \sqrt{d} d and log d \sqrt{\log d} log d rates are worst-case guarantees, and on this non-adversarial stream the ablation exhibits neither scaling; we do not claim that it does. What it shows is that the methods designed through the tighter analysis are more accurate at every d d d : p p p -norm OMD by an order of magnitude over MultiQT, and UP-OCP by about 40%, with no degradation over more than two orders of magnitude in d d d . Small coverage error is only half of the picture, since it can be bought with width: the mean widths of UP-OCP-Iso and MultiQT are within 1% of each other for d ≥ 100 d \ge100 d ≥ 100 , while p p p -norm OMD with the balanced step size pays 23–36% more mean width than MultiQT for its smaller error.
Table 5. Worst-level miscoverage error max i MisCov T , i \max_i \operatorname{MisCov}_{T,i} max i MisCov T , i on the sinusoidal stream as a function of the number of levels d d d (mean over 10 seeds; standard errors are at most 1.5 × 10 − 4 1.5 \times10^{-4} 1.5 × 1 0 − 4 ).
Additional results
This subsection collects, for every dataset, the full set of artifacts referenced from § 5 : the calibration curve and three sharpness–coverage Pareto frontiers (using mean, median, and Q75 widths) on a single 2×2 grid, and a coverage–width summary table at three target levels 1 − α ∈ { 0.95 , 0.9 , 0.8 } 1-\alpha\in\{0.95, 0.9, 0.8\} 1 − α ∈ { 0.95 , 0.9 , 0.8 } including KT and its projected variant. The conclusions of § 5 carry over qualitatively to every dataset; we record only the deviations from the AAPL baseline.
For each tuned baseline (p p p -norm OMD with p p p from Corollary 3.6), the constant step size η \eta η is selected by per-dataset grid search over η ∈ { 2 − 2 , 2 − 1 , 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 } \eta\in\{2^{-2}, 2^{-1}, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024\} η ∈ { 2 − 2 , 2 − 1 , 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 } , exactly as in § 5 . The per-dataset selected η \eta η is reported in each subsubsection.
AAPL (full results)
This is the same dataset and forecasting pipeline as in § 5 ; we extend Figure 1 with KT and KT-Iso (omitted there for scale) and add median and Q 75 Q_{75} Q 75 width Pareto frontiers (Figure 4 ). Tuned η = 64 \eta= 64 η = 64 for p p p -norm OMD with p p p optimal. Table 6 reports coverage and widths at three target levels.
Figure 4. AAPL: calibration (top-left) and three width Pareto frontiers (mean, median, Q 75 Q_{75} Q 75 ) versus empirical coverage. KT and KT-Iso are now included, exposing their wider mean and median widths but competitive Q 75 Q_{75} Q 75 tail.
Table 7. AMZN: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
AMZN
Same Prophet pipeline as AAPL ([38 ] , log-prices, daily refit). Tuned η = 256 \eta= 256 η = 256 for p p p -norm OMD with p p p optimal.
Figure 5. AMZN: calibration and three width Pareto frontiers. Behavior is qualitatively identical to AAPL.
Table 8. GOOGL: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
GOOGL
Same Prophet pipeline as AAPL. Tuned η = 256 \eta= 256 η = 256 for p p p -norm OMD with p p p optimal. The qualitative pattern matches AAPL/AMZN; the projection improves both tail and mean widths of UP-OCP and p p p -norm OMD without affecting calibration, while KT-Iso is marginally wider than KT in several cells.
Figure 6. GOOGL: calibration and three width Pareto frontiers.
Table 9. elec2: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
Electricity demand (elec2)
Half-hourly New South Wales electricity demand from [20 ] , with one-step-ahead forecasts produced by an autoregressive model (lag 3, refit at every step). Scores are absolute residuals on the demand variable, normalized to lie roughly in [ 0 , 1 ] [0,1] [ 0 , 1 ] — hence the smaller numerical scale relative to the stock datasets. Tuned η = 0.25 \eta=0.25 η = 0.25 for p p p -norm OMD with p p p optimal.
Figure 7. elec2: calibration and three width Pareto frontiers.
On this stream the relative ordering shifts slightly: KT-Iso attains the smallest mean, median, and Q 95 Q_{95} Q 95 widths in every column at 1 − α ∈ { 0.9 , 0.8 } 1-\alpha\in\{0.9, 0.8\} 1 − α ∈ { 0.9 , 0.8 } , while UP-OCP-Iso is within about 2% in median width but about 8% wider in mean and up to 22% wider in Q 95 Q_{95} Q 95 width. The reason is the small score range and the absence of fat tails on this stream: the variance budget α j ( 1 − α j ) \alpha_j(1-\alpha_j) α j ( 1 − α j ) that UP-OCP exploits is dominated here by the constant per-step quantization, which is precisely the regime where the simpler KT update rule is competitive with the universal-portfolio update.
Sinusoidal (synthetic)
We generate the nonconformity scores S t S_t S t as a sinusoidal wave distorted by Gaussian noise. With T = 3,000 T=3{,}000 T = 3 , 000 , α min = 2 \alpha_{\min}=2 α m i n = 2 , α max = 20 \alpha_{\max}=20 α m a x = 20 , period P = 200 P=200 P = 200 , noise scale σ = 0.3 \sigma=0.3 σ = 0.3 , and ε t ∼ i . i . d . N ( 0 , σ 2 ) \varepsilon_t \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathcal{N}(0,\sigma^2) ε t ∼ i.i.d. N ( 0 , σ 2 ) , define the centre and amplitude c : = ( α min + α max ) / 2 c := (\alpha_{\min}+\alpha_{\max})/2 c := ( α m i n + α m a x ) /2 and a : = ( α max − α min ) / 2 a := (\alpha_{\max}-\alpha_{\min})/2 a := ( α m a x − α m i n ) /2 and set
S t = max ( 0 , c + a sin ( 2 π t / P ) + ε t ) , t = 1 , … , T . S_t = \max(0, c+a\sin(2\pi t/P)+\varepsilon_t), \qquad t=1,\ldots,T. S t = max ( 0 , c + a sin ( 2 π t / P ) + ε t ) , t = 1 , … , T .
Concretely c = 11 c=11 c = 11 , a = 9 a=9 a = 9 . Reported quantities are means over 10 independent seeds (base seed 42, seeds 42, 43, … \ldots … , 51) with standard errors. Tuned η = 64 \eta=64 η = 64 for p-norm OMD with p p p optimal. This is the same stream as in § 5 ; we extend Figure 1 with KT and KT-Iso and the median and Q 75 Q_{75} Q 75 frontiers (Figure 8 ), and Table 10 reports the per-method coverage and width summary at three target levels.
Table 10. sinusoidal: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
Figure 8. Sinusoidal: calibration and three width Pareto frontiers. UP-OCP-Iso dominates in mean and median width across the entire α \alpha α range, while KT and MultiQT lead on Q 75 Q_{75} Q 75 , mirroring the bounded twin-extrema structure of the wave.
Table 11. stationary: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
Stationary trend with random waves (synthetic)
Nonconformity scores follow a constant baseline distorted by sparse, heavy-tailed multiplicative spikes and smoothed by a centred rolling maximum. With baseline C = 10 C=10 C = 10 , spike probability p = 0.1 p=0.1 p = 0.1 , exponential scale σ = 10 \sigma=10 σ = 10 , rolling window W = 25 W=25 W = 25 , and T = 3,000 T=3{,}000 T = 3 , 000 , we draw
B t ∼ Bernoulli ( p ) , E t ∼ Exponential ( 1 / σ ) , S ~ t = C ( 1 + B t E t ) , B_t \sim\operatorname{Bernoulli}(p), \qquad E_t \sim\operatorname{Exponential}(1/\sigma), \qquad\widetilde{S}_t = C(1+B_tE_t), B t ∼ Bernoulli ( p ) , E t ∼ Exponential ( 1/ σ ) , S t = C ( 1 + B t E t ) ,
and obtain S t S_t S t by a centered rolling-maximum smoother of half-width ⌊ W / 2 ⌋ \lfloor W/2\rfloor ⌊ W /2 ⌋ :
S t = max τ ∈ [ t − ⌊ W / 2 ⌋ , t + ⌊ W / 2 ⌋ ] S ~ τ . S_t = \max_{\tau\in[t-\lfloor W/2\rfloor,\;t+\lfloor W/2\rfloor]} \widetilde{S}_\tau. S t = τ ∈ [ t − ⌊ W /2 ⌋ , t + ⌊ W /2 ⌋] max S τ .
This stresses heavy tails without an underlying trend. We report means over 10 seeds (base seed 42). Tuned η = 1024 \eta=1024 η = 1024 for p p p -norm OMD with p p p optimal.
Figure 9. Stationary trend with random waves: calibration and three width Pareto frontiers.
The width scale on this stream is large (∼ 10 2 \sim10^2 ∼ 1 0 2 ), reflecting the rolling-maximum smoothing of exponential spikes. The projection still strictly improves the unprojected base learner on every cell of the table, and the parameter-free UP-OCP-Iso achieves the smallest mean and median widths at every target (KT-Iso has the smallest Q 95 Q_{95} Q 95 width at 1 − α ∈ { 0.9 , 0.8 } 1-\alpha\in\{0.9, 0.8\} 1 − α ∈ { 0.9 , 0.8 } ).
Table 12: mixed: empirical coverage and prediction-set widths at three representative miscoverage levels. Bold marks the best value in each column (closest empirical coverage to the target; smallest width).
Table 12.
Quadratic drift with random waves (mixed, synthetic)
Same multiplicative-spike-plus-rolling-max structure as the stationary stream, now overlaid on a quadratic drift. With T = 3,000 T=3{,}000 T = 3 , 000 , baseline trajectory T t = ( 20 / T 2 ) t 2 T_t=(20/T^2)t^2 T t = ( 20/ T 2 ) t 2 on t ∈ [ 0 , T − 1 ] t\in[0,T-1] t ∈ [ 0 , T − 1 ] , spike probability p = 0.1 p=0.1 p = 0.1 , exponential scale σ = 10 \sigma=10 σ = 10 , and rolling window W = 25 W=25 W = 25 , we draw
B t ∼ Bernoulli ( p ) , E t ∼ Exponential ( 1 / σ ) , S ~ t = T t ( 1 + B t E t ) , B_t\sim\operatorname{Bernoulli}(p),\qquad E_t\sim\operatorname{Exponential}(1/\sigma),\qquad\widetilde{S}_t=T_t(1+B_tE_t), B t ∼ Bernoulli ( p ) , E t ∼ Exponential ( 1/ σ ) , S t = T t ( 1 + B t E t ) ,
and again take S t = max τ ∈ [ t − ⌊ W / 2 ⌋ , t + ⌊ W / 2 ⌋ ] S ~ τ S_t=\max_{\tau\in[t-\lfloor W/2\rfloor,t+\lfloor W/2\rfloor]}\widetilde{S}_\tau S t = max τ ∈ [ t − ⌊ W /2 ⌋ , t + ⌊ W /2 ⌋] S τ . The deterministic trend T t T_t T t has quadratic shape in t t t and ranges over [ 0 , 20 ] [0,20] [ 0 , 20 ] across the horizon. We report means over 10 seeds (base seed 42). Tuned η = 1024 \eta=1024 η = 1024 for p p p -norm OMD with p p p optimal.
Figure 10. Quadratic drift with random waves: calibration and three width Pareto frontiers.