Introduction
Consider an online uncertainty quantification problem in which each data point consists of a feature X t ∈ X X_t \in\mathcal{X} X t ∈ X and a response Y t ∈ Y Y_t \in\mathcal{Y} Y t ∈ Y . For each time t ≥ 1 t \ge1 t ≥ 1 , let C t \mathcal{C}_t C t denote any prespecified construction that maps from an observed data stream to a prediction set for the data point at time t t t . Concretely, we write
C t ( X t ) = C t ( X t ; ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ) ) ⊆ Y (1) \mathcal{C}_t(X_t) = \mathcal{C}_t\left(X_t;(X_1,Y_1),\ldots,(X_{t-1},Y_{t-1})\right) \subseteq\mathcal{Y} \tag*{(1)} C t ( X t ) = C t ( X t ; ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ) ) ⊆ Y (1)
to denote the prediction set at time t t t , when trained on data points ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ) (X_1, Y_1), \ldots, (X_{t-1}, Y_{t-1}) ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ) . The current outcome Y t Y_t Y t is not available when the set is constructed. Throughout this paper, we use the notation C = ( C t ) t ≥ 1 \mathcal{C} = (\mathcal{C}_t)_{t \ge1} C = ( C t ) t ≥ 1 to denote the online algorithm producing the sequence of prediction sets ( C t ( X t ) ) t ≥ 1 (\mathcal{C}_t(X_t))_{t \ge1} ( C t ( X t ) ) t ≥ 1 .
After Y t Y_t Y t is revealed, the performance of the prediction set can be summarized by a binary miscoverage indicator
e t = 1 { Y t ∉ C t ( X t ; ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ) ) } . e_t = 1\{Y_t \notin\mathcal{C}_t(X_t; (X_1, Y_1), \ldots, (X_{t-1}, Y_{t-1}))\}. e t = 1 { Y t ∈ / C t ( X t ; ( X 1 , Y 1 ) , … , ( X t − 1 , Y t − 1 ))} .
We expect the prediction sets to frequently cover the true response Y t Y_t Y t , quantified by the nominal coverage level 1 − α ∈ ( 0 , 1 ) 1 - \alpha\in(0, 1) 1 − α ∈ ( 0 , 1 ) . To quantify this, we may require that the probability of coverage at each time point is calibrated—that is, that P ( e t ≠ 1 ) \mathbb{P}(e_t \ne1) P ( e t = 1 ) or the coverage rate conditional on the history is ≈ 1 − α \approx1 - \alpha ≈ 1 − α , at each time t t t . This type of guarantee can only be achieved with some assumptions on the data stream, however. More generally, we can instead aim for a weaker guarantee, requiring that the empirical average coverage rate is ≈ 1 − α \approx1 - \alpha ≈ 1 − α over a period of time. We formally define and discuss these two guarantees in the following subsections.
The i.i.d. setting: instantaneous training-conditional coverage
When the data points ( X t , Y t ) (X_t, Y_t) ( X t , Y t ) are independent and identically distributed (or exchangeable), split conformal prediction uses past scores to calibrate prediction sets. The score is fixed or fitted to independent data, and higher scores indicate greater deviation from the fitted model. Concretely, with a fixed score function s : X × Y → R s : \mathcal{X} \times\mathcal{Y} \to\mathbb{R} s : X × Y → R , the split conformal prediction set can be defined by
C t C P ( x ) = { y ∈ Y : 1 + ∑ r < t 1 { s ( X r , Y r ) ≥ s ( x , y ) } t > α } . (2) \mathcal{C}^{\mathrm{CP}}_t(x) = \left\{y \in\mathcal{Y} : \frac{1 + \sum_{r<t} 1\{s(X_r, Y_r) \ge s(x,y)\}}{t} > \alpha\right\}. \tag*{(2)} C t CP ( x ) = { y ∈ Y : t 1 + ∑ r < t 1 { s ( X r , Y r ) ≥ s ( x , y )} > α } . (2)
Exchangeability gives a finite-sample marginal coverage guarantee, i.e., P ( Y t ∈ C t C P ( X t ) ) ≥ 1 − α \mathbb{P}(Y_t \in\mathcal{C}^{\mathrm{CP}}_t(X_t)) \ge1 - \alpha P ( Y t ∈ C t CP ( X t )) ≥ 1 − α . A more local requirement asks whether coverage is close to 1 − α 1 - \alpha 1 − α given the observed past at each time t t t . For i.i.d. observations and a nonatomic score distribution,1 the split conformal prediction set in (2) satisfies the following bound (Vovk, [39 ] ; Angelopoulos et al., [3 ] ):
E P [ ∣ P { Y t ∈ C t C P ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ∣ ] ≤ 1 2 t + 1 + 1 t . (3) \mathbb{E}_{\mathbb{P}}\left[\left|\mathbb{P}\{Y_t \in\mathcal{C}^{\mathrm{CP}}_t(X_t) \mid(X_s, Y_s)_{s<t}\} - (1-\alpha)\right|\right] \le\frac{1}{2\sqrt{t+1}} + \frac{1}{t}. \tag*{(3)} E P [ P { Y t ∈ C t CP ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ] ≤ 2 t + 1 1 + t 1 . (3)
Thus, under these assumptions, the instantaneous training-conditional coverage of split conformal prediction, i.e., its coverage at time t t t given the history ( X s , Y s ) s < t (X_s, Y_s)_{s<t} ( X s , Y s ) s < t , deviates from the target level 1 − α 1 - \alpha 1 − α by O ( t − 1 / 2 ) O(t^{-1/2}) O ( t − 1/2 ) in expectation. To measure this deviation over T T T rounds, for any online algorithm C \mathcal{C} C we define
Δ T i n s t ( C ) : = ∑ t = 1 T E P [ ∣ P { Y t ∈ C t ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ∣ ] . (4) \Delta^{\mathrm{inst}}_T(\mathcal{C}) := \sum_{t=1}^{T} \mathbb{E}_{\mathbb{P}}\left[\left|\mathbb{P}\{Y_t \in\mathcal{C}_t(X_t) \mid(X_s, Y_s)_{s<t}\} - (1-\alpha)\right|\right]. \tag*{(4)} Δ T inst ( C ) := t = 1 ∑ T E P [ ∣ P { Y t ∈ C t ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ∣ ] . (4)
With C = C C P \mathcal{C} = \mathcal{C}^{\mathrm{CP}} C = C CP , summing (3) over t t t gives Δ T i n s t = O ( T ) \Delta^{\mathrm{inst}}_T = O(\sqrt{T}) Δ T inst = O ( T ) .
The adversarial setting: long-run empirical coverage
When exchangeability is not assumed, one widely adopted quantity that measures the adversarial performance of online algorithms is the long-run cumulative coverage deviation (Gibbs and Candès [17 ] ):
∑ t = 1 T [ 1 { Y t ∈ C t ( X t ) } − ( 1 − α ) ] = ∑ t = 1 T ( α − e t ) . (5) \sum_{t=1}^{T} [\mathbf{1}\{Y_t \in\mathcal{C}_t(X_t)\} - (1-\alpha)] = \sum_{t=1}^{T}(\alpha-e_t). \tag*{(5)} t = 1 ∑ T [ 1 { Y t ∈ C t ( X t )} − ( 1 − α )] = t = 1 ∑ T ( α − e t ) . (5)
Here, we denote E T = ∑ t = 1 T ( e t − α ) E_T = \sum_{t=1}^{T}(e_t-\alpha) E T = ∑ t = 1 T ( e t − α ) , where ∣ E T ∣ / T |E_T|/T ∣ E T ∣/ T tracks how far the long-run empirical coverage rate departs from 1 − α 1-\alpha 1 − α . A well-calibrated algorithm keeps ∣ E T ∣ |E_T| ∣ E T ∣ small relative to T T T . This guarantee can be achieved by a large class of algorithms without imposing distributional assumptions on the data sequence { ( X t , Y t ) , t ≥ 1 } \{(X_t,Y_t),\ t \ge1\} {( X t , Y t ) , t ≥ 1 } . To quantify the long-run empirical coverage guarantee in the adversarial setting, we say the algorithm satisfies a ( β , κ ) (\beta,\kappa) ( β , κ ) -constraint if
∣ E T ∣ / T ≤ κ T − β for all T ≥ 1. (6) |E_T|/T \le\kappa T^{-\beta} \quad\text{for all } T \ge1. \tag*{(6)} ∣ E T ∣/ T ≤ κ T − β for all T ≥ 1. (6)
Throughout this paper, β ∈ [ 0 , 1 ] \beta\in[0,1] β ∈ [ 0 , 1 ] and κ ≥ 1 / 2 \kappa\ge1/2 κ ≥ 1/2 , so the interval has width at least one and a feasible error outcome exists at every round. Note that if β = 0 \beta=0 β = 0 and κ ≥ max { α , 1 − α } \kappa\ge\max\{\alpha,1-\alpha\} κ ≥ max { α , 1 − α } , then the constraint holds trivially for any sequence ( e t ) t ≥ 1 (e_t)_{t\ge1} ( e t ) t ≥ 1 . For β > 0 \beta>0 β > 0 , this implies that the long-run empirical coverage rate converges to 1 − α 1-\alpha 1 − α . A larger β \beta β requires tighter control over the long-run empirical coverage rate. We use A β , κ \mathcal{A}_{\beta,\kappa} A β , κ to collect all algorithms that satisfy (6).2
Our central question is how close an algorithm in A β , κ \mathcal{A}_{\beta,\kappa} A β , κ can stay to exact coverage given the history when the data are i.i.d. By (3), the instantaneous training-conditional coverage of split conformal prediction is within O ( t − 1 / 2 ) O(t^{-1/2}) O ( t − 1/2 ) of 1 − α 1-\alpha 1 − α in expectation at round t t t , so its cumulative deviation sum to O ( T ) O(\sqrt{T}) O ( T ) over T T T rounds, i.e., Δ T i n s t = O ( T ) \Delta_T^{\mathrm{inst}}=O(\sqrt{T}) Δ T inst = O ( T ) for C = C C P \mathcal{C}=\mathcal{C}^{\mathrm{CP}} C = C CP . For a nontrivial constraint, split conformal prediction, however, need not belong to A β , κ \mathcal{A}_{\beta,\kappa} A β , κ . We show that the smallest cumulative error in the instantaneous training-conditional coverage that an algorithm in A β , κ \mathcal{A}_{\beta,\kappa} A β , κ can guarantee for i.i.d. data is of order
T max { 1 / 2 , β } = { T , 0 ≤ β ≤ 1 / 2 , T β , 1 / 2 < β ≤ 1. (7) T^{\max\{1/2,\beta\}} =
\begin{cases}
\sqrt{T}, & 0 \le\beta\le1/2,\\
T^\beta, & 1/2 < \beta\le1.
\end{cases} \tag*{(7)} T m a x { 1/2 , β } = { T , T β , 0 ≤ β ≤ 1/2 , 1/2 < β ≤ 1. (7)
Thus, the constraint incurs no cost in rate when β ≤ 1 / 2 \beta\le1/2 β ≤ 1/2 , whereas for β > 1 / 2 \beta>1/2 β > 1/2 the rate is dominated by the constraint, yielding a phase transition at β = 1 / 2 \beta=1/2 β = 1/2 .
Adaptive conformal inference (ACI) revisited)
Adaptive Conformal Inference (ACI), introduced by Gibbs and Candès [17 ] , is one way to enforce long-run empirical coverage on every data sequence. We consider its quantile-threshold form [2 b] , which uses a fixed score s : X × Y → R s : \mathcal{X} \times\mathcal{Y} \to\mathbb{R} s : X × Y → R and constructs C t A C I ( x ) = { y : s ( x , y ) ≤ q t } C_t^{\mathrm{ACI}}(x) = \{y : s(x,y) \le q_t\} C t ACI ( x ) = { y : s ( x , y ) ≤ q t } . After observing the outcome, ACI updates its threshold by
q t + 1 = q t + η t ( e t − α ) , (8) q_{t+1} = q_t + \eta_t(e_t - \alpha), \tag*{(8)} q t + 1 = q t + η t ( e t − α ) , (8)
where η t > 0 \eta_t > 0 η t > 0 is the step size. We note that the original ACI procedure [17 ] updates the nominal coverage level. Here we analyze the quantile-threshold update (8) . The threshold increases after miscoverage and decreases after coverage. The step sizes determine how tightly ACI controls the cumulative coverage deviation in the adversarial case. More concretely, when s ( x , y ) ∈ [ 0 , B ] s(x,y) \in[0,B] s ( x , y ) ∈ [ 0 , B ] , η t ≡ η \eta_t \equiv\eta η t ≡ η (i.e., a constant step size), and q 1 ∈ [ 0 , B ] q_1 \in[0,B] q 1 ∈ [ 0 , B ] , ACI has the long-run empirical coverage guarantee in the adversarial setting [17 , 2 ]
∣ E T ∣ = ∣ ∑ t = 1 T ( e t − α ) ∣ ≤ B + η η , \lvert E_T\rvert= \left\lvert\sum_{t=1}^{T}(e_t-\alpha) \right\rvert\le\frac{B+\eta}{\eta}, ∣ E T ∣ = t = 1 ∑ T ( e t − α ) ≤ η B + η ,
indicating that ACI satisfies the constraint with β = 1 \beta= 1 β = 1 and a constant sufficiently large to dominate ( B + η ) / η (B+\eta)/\eta ( B + η ) / η .
Best-of-both-worlds algorithms?
Recall that split conformal prediction satisfies (3) but can violate (6) on some data sequences. Constant-step ACI satisfies (6) , but its threshold moves by at least η min { α , 1 − α } \eta\min\{\alpha,1-\alpha\} η min { α , 1 − α } after each observation, so its instantaneous training-conditional coverage continues to fluctuate even for i.i.d. data. Since it is rarely known in advance whether the data are i.i.d., we seek a single algorithm that satisfies the long-run constraint for every data sequence and, when the data are i.i.d., keeps its instantaneous training-conditional coverage as close as possible to 1 − α 1-\alpha 1 − α . We call such an algorithm best-of-both-worlds .
For ACI, this goal suggests preserving its long-run empirical coverage bound while reducing the size of each threshold update, that is, specifying decaying step sizes [2 ] . Concretely, when s ( x , y ) ∈ [ 0 , B ] s(x,y) \in[0,B] s ( x , y ) ∈ [ 0 , B ] , q 1 ∈ [ 0 , B ] q_1 \in[0,B] q 1 ∈ [ 0 , B ] , and η t = c t − ( 1 − β ) \eta_t = ct^{-(1-\beta)} η t = c t − ( 1 − β ) with c > 0 c > 0 c > 0 and 0 < β < 1 0 < \beta< 1 0 < β < 1 , the bound of Angelopoulos et al. [2 ] gives
∣ E T ∣ T ≤ B + c c T − β for every T ≥ 1. (9) \frac{\lvert E_T\rvert}{T} \le\frac{B+c}{c}T^{-\beta} \qquad\text{for every } T \ge1. \tag*{(9)} T ∣ E T ∣ ≤ c B + c T − β for every T ≥ 1. (9)
Thus ACI satisfies a ( β , κ ) (\beta,\kappa) ( β , κ ) -constraint with κ = ( B + c ) / c \kappa= (B+c)/c κ = ( B + c ) / c on every data sequence. Faster decay of the step sizes corresponds to smaller β \beta β and a weaker long-run empirical coverage guarantee. Under i.i.d. sampling with a fixed bounded score whose CDF is continuous and whose ( 1 − α ) (1-\alpha) ( 1 − α ) -quantile is unique, the steps η t = c t − ( 1 − β ) \eta_t = ct^{-(1-\beta)} η t = c t − ( 1 − β ) with 0 < β < 1 / 2 0 < \beta< 1/2 0 < β < 1/2 make the working quantile q t q_t q t converge almost surely to the population ( 1 − α ) (1-\alpha) ( 1 − α ) -quantile [2 Theorem 3] . Instantaneous training-conditional coverage then converges to 1 − α 1-\alpha 1 − α as well. Together with Equation (9) , this gives both guarantees asymptotically.
Each new observation changes ACI’s threshold by an amount proportional to η t \eta_t η t , even as the threshold converges to the population quantile. A larger β \beta β yields tighter long-run empirical coverage but causes these updates to decay more slowly, raising the question of how much error in the instantaneous training-conditional coverage accumulates over time. More concretely, for i.i.d. data under the score-density assumptions in § 3 , Proposition 3.1 quantifies this cost. With η t = c t − ( 1 − β ) \eta_t = ct^{-(1-\beta)} η t = c t − ( 1 − β ) and 0 < β < 1 0 < \beta< 1 0 < β < 1 , it gives
∑ t = 1 T E P [ ∣ P { Y t ∈ C t A C I ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ∣ ] ≍ T ( 1 + β ) / 2 . (10) \sum_{t=1}^{T} \mathbb{E}_{\mathbb{P}}\left[\left|\mathbb{P}\{Y_t \in\mathcal{C}^{\mathrm{ACI}}_t(X_t) \mid(X_s,Y_s)_{s<t}\}-(1-\alpha)\right|\right] \asymp T^{(1+\beta)/2}. \tag*{(10)} t = 1 ∑ T E P [ P { Y t ∈ C t ACI ( X t ) ∣ ( X s , Y s ) s < t } − ( 1 − α ) ] ≍ T ( 1 + β ) /2 . (10)
For every 0 < β < 1 0 < \beta< 1 0 < β < 1 , this rate exceeds the O ( T ) O(\sqrt{T}) O ( T ) bound for split conformal prediction in (3) . Split conformal prediction, however, does not itself enforce the long-run adversarial constraint on every sequence. Then it motivates us to ask the question: what is the smallest cumulative error in instantaneous training-conditional coverage achievable under the long-run empirical coverage constraints?
Figure Figure 1 illustrates the tradeoff in a synthetic dataset (§ 4 ), where the fixed score, by construction, is uniformly distributed on [ 0 , 1 ] [0,1] [ 0 , 1 ] . We compare η t = t − ( 1 − β ) \eta_t = t^{-(1-\beta)} η t = t − ( 1 − β ) for β ∈ { 1 , 0.8 , 0.6 , 0.4 } \beta\in\{1,0.8,0.6,0.4\} β ∈ { 1 , 0.8 , 0.6 , 0.4 } , including constant steps at β = 1 \beta= 1 β = 1 . In panel (c), we focus on a metric that quantifies the expected disagreement between ACI prediction sets and the population score oracle; a formal definition is presented in § 2 . In this experiment, a larger β \beta β keeps the cumulative coverage deviation closer to zero, but instantaneous training-conditional coverage fluctuates more, and the time-averaged oracle disagreement decreases more slowly. These observations leave open the extent to which ACI’s statistical cost is required by the coverage constraint and how much arises from its own algorithmic design.
Figure 1. Long-run empirical coverage versus oracle disagreement in ACI. We use the regression model in § 4 , with α = 0.1 \alpha= 0.1 α = 0.1 , q 1 = 0.9 q_1 = 0.9 q 1 = 0.9 , and step sizes η t = t − ( 1 − β ) \eta_t = t^{-(1-\beta)} η t = t − ( 1 − β ) . We define p t = P ( Y t ∉ C t A C I ( X t ) ∣ ( X s , Y s ) s < t ) p_t = \mathbb{P}(Y_t \notin\mathcal{C}^{\mathrm{ACI}}_t(X_t) \mid(X_s,Y_s)_{s<t}) p t = P ( Y t ∈ / C t ACI ( X t ) ∣ ( X s , Y s ) s < t ) and compute r ^ t \widehat{r}_t r t by averaging ∑ s ≤ t ∣ p s − α ∣ \sum_{s \le t} |p_s-\alpha| ∑ s ≤ t ∣ p s − α ∣ . Dashed guides are proportional to t − ( 1 − β ) / 2 t^{-(1-\beta)/2} t − ( 1 − β ) /2 for β < 1 \beta< 1 β < 1 , as predicted by Proposition 3.1.
Core question. Motivated by the aforementioned tradeoff, it remains an open question how much instantaneous training-conditional coverage error is unavoidable under the long-run empirical coverage constraint. Our goal is to find an algorithm that offers the best-of-both-worlds guarantee: it satisfies the prescribed long-run empirical coverage constraint on every data sequence and achieves the best statistical performance when the data are i.i.d.
To make this objective precise, we compare an algorithm with an oracle that knows the data distribution and has coverage exactly 1 − α 1-\alpha 1 − α given the past. Their cumulative disagreement counts the rounds on which the observed response belongs to exactly one of their prediction sets. Our central question is:
How closely can a single algorithm match an exact oracle under i.i.d. sampling while satisfying a prescribed long-run empirical coverage constraint on every data sequence?
In particular, can the T \sqrt{T} T cumulative rate of split conformal prediction be retained, and when does tighter long-run empirical coverage force a higher cost? We seek the smallest possible cost and an algorithm that attains it without knowing the data distribution or whether the observations are i.i.d.
Paper organization. § 2 formalizes oracle disagreement and separates the difficulty of approximating an oracle from the cost of the long-run empirical coverage constraint. For the family of all exact oracles, under i.i.d. laws with a nonatomic distribution for the fixed score, we prove a minimax rate of T max { 1 / 2 , β } T^{\max\{1/2,\beta\}} T m a x { 1/2 , β } and achieve it by truncating split conformal prediction only when needed to enforce the constraint. Thus the T \sqrt{T} T rate is retained for β ≤ 1 / 2 \beta\le1/2 β ≤ 1/2 , while tighter constraints necessarily increase the rate. § 3 shows that fixed-score ACI with steps proportional to t β − 1 t^{\beta-1} t β − 1 incurs a larger cost for 0 < β < 1 0<\beta<1 0 < β < 1 under the stated density assumptions.
Oracle disagreement under an adversarial constraint
Recall the setting introduced in § 1 . We use A \mathcal{A} A to denote the class of measurable online algorithms in (1) that are independent of the unknown data distribution. At round t t t , an online algorithm C \mathcal{C} C uses the past observations ( X r , Y r ) r < t (X_r,Y_r)_{r<t} ( X r , Y r ) r < t and the current feature X t X_t X t to construct a prediction set C t ( X t ) ⊆ Y \mathcal{C}_t(X_t) \subseteq\mathcal{Y} C t ( X t ) ⊆ Y before observing Y t Y_t Y t . Write e t C = 1 { Y t ∉ C t ( X t ) } e_t^{\mathcal{C}}=\mathbb{1}\{Y_t\notin\mathcal{C}_t(X_t)\} e t C = 1 { Y t ∈ / C t ( X t )} and E T C = ∑ t = 1 T ( e t C − α ) E_T^{\mathcal{C}}=\sum_{t=1}^{T}(e_t^{\mathcal{C}}-\alpha) E T C = ∑ t = 1 T ( e t C − α ) . With a fixed joint distribution P \mathbb{P} P for the data sequence ( X t , Y t ) t ∈ N (X_t,Y_t)_{t\in\mathbb{N}} ( X t , Y t ) t ∈ N and to make the conditioning clear, we define G t − 1 = σ ( ( X r , Y r ) r < t ) \mathcal{G}_{t-1}=\sigma((X_r,Y_r)_{r<t}) G t − 1 = σ (( X r , Y r ) r < t ) .3
In this section, we formally quantify the instantaneous training-conditional performance of an online algorithm. To define this metric, we compare each prediction set C t ( x ) \mathcal{C}_t(x) C t ( x ) at time t t t with an oracle whose instantaneous training-conditional coverage is exactly calibrated at each t t t . Concretely, an oracle C P ∗ \mathcal{C}_{\mathbb{P}}^* C P ∗ may know P \mathbb{P} P , uses the same available information as C \mathcal{C} C , and satisfies
Definition of an oracle:
P ( Y t ∈ C P , t ∗ ( X t ) ∣ G t − 1 ) = 1 − α almost surely for every t ≥ 1. (11) \mathbb{P}(Y_t\in\mathcal{C}_{\mathbb{P},t}^*(X_t)\mid\mathcal{G}_{t-1})=1-\alpha\quad\text{almost surely for every }t\ge1. \tag*{(11)} P ( Y t ∈ C P , t ∗ ( X t ) ∣ G t − 1 ) = 1 − α almost surely for every t ≥ 1. (11)
As an example, under i.i.d. sampling with a measurable score function s : X × Y → R s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R} s : X × Y → R , if the distribution of s ( X 1 , Y 1 ) s(X_1,Y_1) s ( X 1 , Y 1 ) is nonatomic, let F P , s F_{\mathbb{P},s} F P , s be its CDF and set
q P , s = inf { q : F P , s ( q ) ≥ 1 − α } , C P , s , t ∗ ( x ) = { y : s ( x , y ) ≤ q P , s } . (12) q_{\mathbb{P},s}=\inf\{q:F_{\mathbb{P},s}(q)\ge1-\alpha\},\qquad\mathcal{C}_{\mathbb{P},s,t}^*(x)=\{y:s(x,y)\le q_{\mathbb{P},s}\}. \tag*{(12)} q P , s = inf { q : F P , s ( q ) ≥ 1 − α } , C P , s , t ∗ ( x ) = { y : s ( x , y ) ≤ q P , s } . (12)
Independence of the data sequence and continuity of F P , s F_{\mathbb{P},s} F P , s give the oracle condition (11) . We note that, in general, the existence of C P ∗ C^*_{\mathbb{P}} C P ∗ requires regularity conditions on the joint distribution P \mathbb{P} P , and for simplicity, we assume P \mathbb{P} P is nonatomic throughout this paper unless otherwise specified.
To evaluate two online algorithms, we measure their cumulative disagreement on the same data sequence by
ℓ T ( C , C ′ ) = ∑ t = 1 T ∣ e t C − e t C ′ ∣ . (13) \ell_T(C,C') = \sum_{t=1}^{T} \left|e_t^C-e_t^{C'}\right|. \tag*{(13)} ℓ T ( C , C ′ ) = t = 1 ∑ T e t C − e t C ′ . (13)
This counts responses that belong to exactly one of the two sets. Then, the expected disagreement with an oracle C P ∗ C^*_{\mathbb{P}} C P ∗ , i.e., E P [ ℓ T ( C , C P ∗ ) ] \mathbb{E}_{\mathbb{P}}[\ell_T(C,C^*_{\mathbb{P}})] E P [ ℓ T ( C , C P ∗ )] , quantifies the instantaneous training-conditional performance of an algorithm C = ( C t ) t ∈ N C=(C_t)_{t\in\mathbb{N}} C = ( C t ) t ∈ N under a given data distribution P \mathbb{P} P . For p t C = P ( e t C = 1 ∣ G t − 1 ) p_t^C=\mathbb{P}(e_t^C=1\mid\mathcal{G}_{t-1}) p t C = P ( e t C = 1 ∣ G t − 1 ) , conditional Jensen’s inequality further gives
E P ℓ T ( C , C P ∗ ) ≥ ∑ t = 1 T E P ∣ p t C − α ∣ = Δ T i n s t (14) \mathbb{E}_{\mathbb{P}}\ell_T(C,C^*_{\mathbb{P}}) \ge\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}}\left|p_t^C-\alpha\right|=\Delta_T^{\mathrm{inst}} \tag*{(14)} E P ℓ T ( C , C P ∗ ) ≥ t = 1 ∑ T E P p t C − α = Δ T inst (14)
for every exact oracle C P ∗ C^*_{\mathbb{P}} C P ∗ .
Equality holds when two prediction sets are coupled, i.e., the sets are defined by two thresholds on the same score, whose cutoffs are determined by past data.
Hardness of matching an oracle under long-run empirical coverage constraints
Let Q ~ \widetilde{\mathcal{Q}} Q be the class of all i.i.d. joint laws on the data sequence ( X t , Y t ) t ∈ N (X_t,Y_t)_{t\in\mathbb{N}} ( X t , Y t ) t ∈ N . Fix a measurable score s : X × Y → R s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R} s : X × Y → R , and let
Q = { P ∈ Q ~ : s ( X 1 , Y 1 ) has a nonatomic distribution under P } . \mathcal{Q}=\{P\in\widetilde{\mathcal{Q}}:s(X_1,Y_1)\text{ has a nonatomic distribution under }P\}. Q = { P ∈ Q : s ( X 1 , Y 1 ) has a nonatomic distribution under P } .
We assume that Q \mathcal{Q} Q is nonempty. For each P ∈ Q P\in\mathcal{Q} P ∈ Q , let O α ( P ) \mathcal{O}_{\alpha}(P) O α ( P ) denote the set of algorithms that satisfy the oracle condition (11) . Particularly, this family includes the population score oracle defined in (12) .
We measure an algorithm’s performance by
sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( C , C P ∗ ) . (15) \sup_{P\in\mathcal{Q}}\inf_{C^*_P\in\mathcal{O}_{\alpha}(P)}\mathbb{E}_{P}\ell_T(C,C^*_P). \tag*{(15)} P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) . (15)
The infimum allows a separate oracle for each algorithm and law, without giving the algorithm access to the oracle or the distribution. Throughout, ≲ \lesssim ≲ , ≳ \gtrsim ≳ , and ≍ \asymp ≍ compare quantities up to positive constants for all sufficiently large T T T .
Matching an oracle is difficult for two reasons. The algorithm must learn from an unknown distribution and keep its realized errors within the prescribed bounds. The following result separates these two costs.
Theorem 2.1. Under the setup above, every C ∈ A β , κ C\in\mathcal{A}_{\beta,\kappa} C ∈ A β , κ satisfies
sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( C , C P ∗ ) ≥ C α , β , κ T max { 1 / 2 , β } , (16) \sup_{P\in\mathcal{Q}}\inf_{C^*_P\in\mathcal{O}_{\alpha}(P)}\mathbb{E}_{P}\ell_T(C,C^*_P)\ge C_{\alpha,\beta,\kappa}T^{\max\{1/2,\beta\}}, \tag*{(16)} P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) ≥ C α , β , κ T m a x { 1/2 , β } , (16) for sufficiently large T T T , where C α , β , κ > 0 C_{\alpha,\beta,\kappa}>0 C α , β , κ > 0 depends only on α \alpha α , β \beta β , κ \kappa κ .
More generally, the lower bound can be decomposed as
sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( C , C P ∗ ) ≳ inf C 0 ∈ A sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( C 0 , C P ∗ ) + { 0 , 0 ≤ β < 1 / 2 , T β , 1 / 2 ≤ β ≤ 1. (17) \sup_{\mathbb{P}\in\mathcal{Q}}\inf_{\mathcal{C}_{\mathbb{P}}^*\in\mathcal{O}_{\alpha}(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\ell_T(\mathcal{C},\mathcal{C}_{\mathbb{P}}^*)
\gtrsim\inf_{\mathcal{C}^0\in\mathcal{A}}\sup_{\mathbb{P}\in\mathcal{Q}}\inf_{\mathcal{C}_{\mathbb{P}}^*\in\mathcal{O}_{\alpha}(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\ell_T(\mathcal{C}^0,\mathcal{C}_{\mathbb{P}}^*)+
\begin{cases}
0, & 0\leq\beta<1/2,\\
T^\beta, & 1/2\leq\beta\leq1.
\end{cases} \tag*{(17)} P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) ≳ C 0 ∈ A inf P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( C 0 , C P ∗ ) + { 0 , T β , 0 ≤ β < 1/2 , 1/2 ≤ β ≤ 1. (17)
The first term is the unavoidable cost of learning from past data. Even without a long-run empirical coverage constraint, no algorithm can achieve disagreement smaller than order T \sqrt{T} T uniformly over Q \mathcal{Q} Q . This remains true when comparison is allowed with every exact oracle. Split conformal prediction attains this order by estimating the population score quantile.
The second term is the cost of enforcing the long-run empirical coverage constraint. Exact calibration does not prevent the oracle’s realized errors from fluctuating: its centered error sum has standard deviation α ( 1 − α ) T \sqrt{\alpha(1-\alpha)T} α ( 1 − α ) T . However, the constraint allows a deviation of only κ T 1 − β \kappa T^{1-\beta} κ T 1 − β . When β ≥ 1 / 2 \beta\geq1/2 β ≥ 1/2 , keeping the errors within these bounds requires repeated departures from the oracle. These departures force a cumulative disagreement with the order of at least T β T^\beta T β , even if the distribution is known.
The higher cost determines the lower-bound rate, which exhibits a sharp phase transition at β = 1 / 2 \beta=1/2 β = 1/2 . The cost of learning the unknown distribution dominates when β < 1 / 2 \beta<1/2 β < 1/2 , both costs have order T \sqrt{T} T at β = 1 / 2 \beta=1/2 β = 1/2 , and the long-run empirical coverage constraint dominates when β > 1 / 2 \beta>1/2 β > 1/2 . In the next subsection, we construct an algorithm that achieves this rate in both regimes.
If distributions are not nonatomic, there may be no oracle that satisfies the condition (11) , but we can approach the problem differently by considering relaxed oracles; see Section E.
Truncation attains the minimax rate
In this section, we present an explicit online construction of the online algorithm that has a matching upper bound in Theorem 2.1 . Fix a measurable score s : X × Y → R s:\mathcal{X}\times\mathcal{Y}\to\mathbb{R} s : X × Y → R . Recall that O α ( P ) \mathcal{O}_{\alpha}(\mathbb{P}) O α ( P ) denotes the set of oracle algorithms that satisfy (11) and under P ∈ Q \mathbb{P}\in\mathcal{Q} P ∈ Q , the distribution of score s ( X t , Y t ) s(X_t,Y_t) s ( X t , Y t ) is nonatomic.
To meet the long-run empirical coverage constraints, a straightforward way is to truncate the cumulative miscoverage error E T E_T E T and enforce the adversarial constraints at each step. Concretely, for any baseline C 0 \mathcal{C}^0 C 0 , define C ^ = Γ κ , β ∘ C 0 \widehat{\mathcal{C}}=\Gamma_{\kappa,\beta}\circ\mathcal{C}^0 C = Γ κ , β ∘ C 0 recursively, starting at E ^ 0 C ^ = 0 \widehat{E}_0^{\widehat{\mathcal{C}}}=0 E 0 C = 0 , by
( Γ κ , β ∘ C 0 ) t ( x ) = C ^ t ( x ) = { Y , E ^ t − 1 C ^ + 1 − α > κ t 1 − β , ∅ , E ^ t − 1 C ^ − α < − κ t 1 − β , C t 0 ( x ) , otherwise . (18) (\Gamma_{\kappa,\beta}\circ\mathcal{C}^0)_t(x)=\widehat{\mathcal{C}}_t(x)=
\begin{cases}
\mathcal{Y}, & \widehat{E}_{t-1}^{\widehat{\mathcal{C}}}+1-\alpha>\kappa t^{1-\beta},\\
\varnothing, & \widehat{E}_{t-1}^{\widehat{\mathcal{C}}}-\alpha<-\kappa t^{1-\beta},\\
\mathcal{C}_t^0(x), & \text{otherwise}.
\end{cases} \tag*{(18)} ( Γ κ , β ∘ C 0 ) t ( x ) = C t ( x ) = ⎩ ⎨ ⎧ Y , ∅ , C t 0 ( x ) , E t − 1 C + 1 − α > κ t 1 − β , E t − 1 C − α < − κ t 1 − β , otherwise . (18)
If a potential miscoverage at round t t t would push the cumulative deviation above its upper bound, we output Y \mathcal{Y} Y to ensure coverage. Similarly, if coverage would push E ^ t C ^ \widehat{E}_t^{\widehat{\mathcal{C}}} E t C below its lower bound, we output ∅ \varnothing ∅ to force a miscoverage. Otherwise, either outcome respects the bounds, so we keep the baseline prediction set. E t C ^ \mathbb{E}^{\widehat{\mathcal{C}}}_t E t C is computed from the errors of C ^ \widehat{\mathcal{C}} C , whereas the baseline C 0 \mathcal{C}^{0} C 0 continues to use every observation, including those from rounds in which its set is replaced by its truncated counterpart. For κ ≥ 1 / 2 \kappa\ge1/2 κ ≥ 1/2 , the two forcing conditions cannot hold simultaneously, and the resulting prediction sets satisfy (6) on every data sequence.
With split conformal prediction as the baseline, this truncation attains the minimax rate of expected oracle disagreement, as the following theorem shows.
Theorem 2.2. The single algorithm Γ κ , β ∘ C C P ∈ A β , κ \Gamma_{\kappa,\beta} \circ\mathcal{C}^{\mathrm{CP}} \in\mathcal{A}_{\beta,\kappa} Γ κ , β ∘ C CP ∈ A β , κ attains the upper bound:
sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( Γ κ , β ∘ C C P , C P ∗ ) ≲ T max { 1 / 2 , β } . (19) \sup_{\mathbb{P}\in\mathcal{Q}}\inf_{\mathcal{C}^{*}_{\mathbb{P}}\in\mathcal{O}_{\alpha}(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\ell_{T}(\Gamma_{\kappa,\beta}\circ\mathcal{C}^{\mathrm{CP}},\mathcal{C}^{*}_{\mathbb{P}})\lesssim T^{\max\{1/2,\beta\}}. \tag*{(19)} P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( Γ κ , β ∘ C CP , C P ∗ ) ≲ T m a x { 1/2 , β } . (19)
As an immediate corollary of Theorem 2.1 and Theorem 2.2 , given the score, class Q \mathcal{Q} Q , and full oracle families defined above, we obtain the minimax rate
inf C ∈ A β , κ sup P ∈ Q inf C P ∗ ∈ O α ( P ) E P ℓ T ( C , C P ∗ ) ≍ T max { 1 / 2 , β } . (20) \inf_{\mathcal{C}\in\mathcal{A}_{\beta,\kappa}}\sup_{\mathbb{P}\in\mathcal{Q}}\inf_{\mathcal{C}^{*}_{\mathbb{P}}\in\mathcal{O}_{\alpha}(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\ell_{T}(\mathcal{C},\mathcal{C}^{*}_{\mathbb{P}})\asymp T^{\max\{1/2,\beta\}}. \tag*{(20)} C ∈ A β , κ inf P ∈ Q sup C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) ≍ T m a x { 1/2 , β } . (20)
The rate in (20) reflects two distinct costs. The first is the cost of approximating an exact oracle from past data. For split conformal prediction, disagreement with the population score oracle equals the expected error in instantaneous training-conditional coverage. Summing (3) therefore yields an O ( T ) O(\sqrt{T}) O ( T ) upper bound. The lower-bound argument for Theorem 2.1 shows that this order is unavoidable over Q \mathcal{Q} Q , even without a long-run empirical coverage constraint and after taking the infimum over all exact oracles.
The second cost comes from enforcing the constraint, even if the population prediction set is already known. As we already see from Theorem 2.1 , even exactly calibrated prediction sets are forced to deviate from the oracle by the long-run empirical coverage constraint, and the resulting disagreement is at least of order T β T^{\beta} T β when β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 .
Truncation attains the combined rate by controlling both costs. By Lemma C.1, the disagreement between the truncated baseline and the truncated oracle is at most twice the baseline’s disagreement with the oracle. To compare with the original oracle, the triangle inequality adds the oracle’s own truncation cost. Since an exact oracle has i.i.d. Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) errors, Lemma C.2 bounds this additional cost in expectation. Thus, for any exact oracle C P ∗ \mathcal{C}^{*}_{\mathbb{P}} C P ∗ and baseline C 0 ∈ A \mathcal{C}^{0}\in\mathcal{A} C 0 ∈ A , truncation gives
E P ℓ T ( Γ κ , β ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K α , β , κ { 1 , 0 ≤ β < 1 / 2 , T β , 1 / 2 ≤ β ≤ 1. (21) \mathbb{E}_{\mathbb{P}}\ell_{T}(\Gamma_{\kappa,\beta}\circ\mathcal{C}^{0},\mathcal{C}^{*}_{\mathbb{P}})\le2\mathbb{E}_{\mathbb{P}}\ell_{T}(\mathcal{C}^{0},\mathcal{C}^{*}_{\mathbb{P}})+K_{\alpha,\beta,\kappa}
\begin{cases}
1, & 0\le\beta<1/2,\\
T^{\beta}, & 1/2\le\beta\le1.
\end{cases} \tag*{(21)} E P ℓ T ( Γ κ , β ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K α , β , κ { 1 , T β , 0 ≤ β < 1/2 , 1/2 ≤ β ≤ 1. (21)
The bound holds for every T ≥ 1 T\ge1 T ≥ 1 . For split conformal prediction and the population score oracle, the first term is O ( T ) O(\sqrt{T}) O ( T ) . When β < 1 / 2 \beta<1/2 β < 1/2 , the additional term is bounded uniformly in T T T , so enforcing long-run empirical coverage preserves the unconstrained statistical rate. At β = 1 / 2 \beta=1/2 β = 1/2 , the enforcement cost becomes T \sqrt{T} T , matching the cost of learning the target. For β > 1 / 2 \beta>1/2 β > 1/2 , the enforcement cost T β T^{\beta} T β dominates, and the optimal disagreement rate increases with the tightness of the constraint. This leads to the sharp transition in (20) : the optimal rate remains at T \sqrt{T} T up to β = 1 / 2 \beta=1/2 β = 1/2 , and becomes T β T^{\beta} T β beyond that threshold.
Comparing to ACI with decaying step sizes
We next compare truncation with ACI with decaying step sizes and a fixed score function, which adjusts its threshold after each observation. Fix B > 0 B>0 B > 0 , a measurable score s : X × Y → [ 0 , B ] s:\mathcal{X}\times\mathcal{Y}\to[0,B] s : X × Y → [ 0 , B ] , a deterministic initial threshold q 1 ∈ [ 0 , B ] q_1\in[0,B] q 1 ∈ [ 0 , B ] , and positive deterministic step sizes ( η t ) t ≥ 1 (\eta_t)_{t\geq1} ( η t ) t ≥ 1 . ACI constructs
C t A C I ( x ) = { y : s ( x , y ) ≤ q t } , q t + 1 = q t + η t ( e t A C I − α ) . (22) \mathcal{C}^{\mathrm{ACI}}_t(x)=\{y:s(x,y)\leq q_t\},\qquad q_{t+1}=q_t+\eta_t(e^{\mathrm{ACI}}_t-\alpha). \tag*{(22)} C t ACI ( x ) = { y : s ( x , y ) ≤ q t } , q t + 1 = q t + η t ( e t ACI − α ) . (22)
We study the adversarial guarantee of this update and its disagreement with the closest conditionally exact oracle defined in (11) .
Adversarial coverage guarantee. For nonincreasing step sizes, the coverage bound of Angelopoulos et al. [2 ] gives ∣ E T A C I ∣ ≤ ( B + η 1 ) / η T \lvert E^{\mathrm{ACI}}_T\rvert\leq(B+\eta_1)/\eta_T ∣ E T ACI ∣ ≤ ( B + η 1 ) / η T on every sequence of scores in [ 0 , B ] [0,B] [ 0 , B ] . In particular, for η t = c t − ( 1 − β ) \eta_t=ct^{-(1-\beta)} η t = c t − ( 1 − β ) with c > 0 c>0 c > 0 and β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] ,
∣ E T A C I ∣ T ≤ B + c c T − β for every T ≥ 1. (23) \frac{\lvert E^{\mathrm{ACI}}_T\rvert}{T}\leq\frac{B+c}{c}T^{-\beta}\qquad\text{for every }T\geq1. \tag*{(23)} T ∣ E T ACI ∣ ≤ c B + c T − β for every T ≥ 1. (23)
Thus ACI has a ( β , κ ) (\beta,\kappa) ( β , κ ) adversarial guarantee with κ = ( B + c ) / c \kappa=(B+c)/c κ = ( B + c ) / c , indicating that, for a prescribed κ > 1 \kappa>1 κ > 1 , choosing c = B / ( κ − 1 ) c=B/(\kappa-1) c = B / ( κ − 1 ) yields the long-run coverage constraint.
Disagreement with the oracle. Now suppose the observations are i.i.d. under P \mathbb{P} P and the score has a density satisfying
0 < λ − ≤ f s ( u ) ≤ λ + < ∞ for almost every u ∈ [ 0 , B ] . (24) 0<\lambda_-\leq f_s(u)\leq\lambda_+<\infty\qquad\text{for almost every }u\in[0,B]. \tag*{(24)} 0 < λ − ≤ f s ( u ) ≤ λ + < ∞ for almost every u ∈ [ 0 , B ] . (24)
Then we have the following result, where the infimum over C P ∗ \mathcal{C}_{\mathbb{P}}^* C P ∗ below ranges over all oracles satisfying (11) . The smallest expected disagreement is achieved by the population prediction set that uses the same score, as defined in (12) .
Proposition 3.1 (Disagreement of ACI). With P ∈ Q \mathbb{P}\in\mathcal{Q} P ∈ Q satisfying (24) , if η t → 0 \eta_t\to0 η t → 0 and ∣ η t + 1 − 1 − η t − 1 ∣ → 0 \lvert\eta_{t+1}^{-1}-\eta_t^{-1}\rvert\to0 ∣ η t + 1 − 1 − η t − 1 ∣ → 0 , then
inf C P ∗ ∈ O α ( P ) E P [ ℓ T ( C A C I , C P ∗ ) ] ≍ ∑ t = 1 T η t . (25) \inf_{\mathcal{C}_{\mathbb{P}}^*\in\mathcal{O}_\alpha(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\left[\ell_T(\mathcal{C}^{\mathrm{ACI}},\mathcal{C}_{\mathbb{P}}^*)\right]\asymp\sum_{t=1}^{T}\sqrt{\eta_t}. \tag*{(25)} C P ∗ ∈ O α ( P ) inf E P [ ℓ T ( C ACI , C P ∗ ) ] ≍ t = 1 ∑ T η t . (25)
ACI’s threshold fluctuates around the population quantile on the scale η t \sqrt{\eta_t} η t , which creates disagreement even as the step sizes decay. Specifically, for η t = c t − ( 1 − β ) \eta_t=ct^{-(1-\beta)} η t = c t − ( 1 − β ) with 0 < β < 1 0<\beta<1 0 < β < 1 , we have the following corollary.
Corollary 3.1. With P ∈ Q \mathbb{P}\in\mathcal{Q} P ∈ Q satisfying (24) , for η t = c t − ( 1 − β ) \eta_t=ct^{-(1-\beta)} η t = c t − ( 1 − β ) with 0 < β < 1 0<\beta<1 0 < β < 1 ,
inf C P ∗ ∈ O α ( P ) E P [ ℓ T ( C A C I , C P ∗ ) ] ≍ T ( 1 + β ) / 2 . (26) \inf_{\mathcal{C}_{\mathbb{P}}^*\in\mathcal{O}_\alpha(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\left[\ell_T(\mathcal{C}^{\mathrm{ACI}},\mathcal{C}_{\mathbb{P}}^*)\right]\asymp T^{(1+\beta)/2}. \tag*{(26)} C P ∗ ∈ O α ( P ) inf E P [ ℓ T ( C ACI , C P ∗ ) ] ≍ T ( 1 + β ) /2 . (26)
Since ( 1 + β ) / 2 > max { 1 / 2 , β } (1+\beta)/2>\max\{1/2,\beta\} ( 1 + β ) /2 > max { 1/2 , β } , this grows faster than the disagreement of truncated split conformal prediction in Theorem 2.2 under the same adversarial guarantee with κ > 1 \kappa>1 κ > 1 . Thus, with the same fixed score function, for these step sizes, ACI’s cumulative disagreement exceeds the minimax rate for every β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) . Truncated split conformal prediction attains the optimal rate by changing the baseline set only when the constraint forces coverage or miscoverage.
Numerical experiments
We study the cost of truncation and compare truncated split conformal prediction with ACI in a heteroscedastic regression model. Independently over time, let
X t ∼ Unif [ 0 , 1 ] , Y t = f ( X t ) + σ ( X t ) ε t , ε t ∼ Unif [ − 1 , 1 ] , X_t \sim\operatorname{Unif}[0,1], \qquad Y_t = f(X_t) + \sigma(X_t)\varepsilon_t, \qquad\varepsilon_t \sim\operatorname{Unif}[-1,1], X t ∼ Unif [ 0 , 1 ] , Y t = f ( X t ) + σ ( X t ) ε t , ε t ∼ Unif [ − 1 , 1 ] ,
where X t X_t X t and ε t \varepsilon_t ε t are independent, f ( x ) = sin ( 2 π x ) f(x) = \sin(2\pi x) f ( x ) = sin ( 2 π x ) , and σ ( x ) = 0.2 + 0.3 x \sigma(x) = 0.2 + 0.3x σ ( x ) = 0.2 + 0.3 x . We use the fixed score s ( x , y ) = min { ∣ y − f ( x ) ∣ / σ ( x ) , 1 } s(x,y) = \min\{|y-f(x)|/\sigma(x),1\} s ( x , y ) = min { ∣ y − f ( x ) ∣/ σ ( x ) , 1 } , which is uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] under this model. We set α = 0.1 \alpha= 0.1 α = 0.1 and compare all algorithms with the population prediction set C P , t ∗ ( x ) = { y : s ( x , y ) ≤ 0.9 } \mathcal{C}^{*}_{P,t}(x) = \{y : s(x,y) \le0.9\} C P , t ∗ ( x ) = { y : s ( x , y ) ≤ 0.9 } .
We use the split-conformal baseline C C P \mathcal{C}^{\mathrm{CP}} C CP defined in (2) . Each experiment in this section uses 500 independent replications over T = 250,000 T = 250{,}000 T = 250 , 000 time steps. We evaluate disagreement with the oracle using the known score distribution, which is not used to choose the conformal thresholds or update ACI. Since the prediction sets are nested score thresholds, their disagreement probability, conditional on past observations, equals the absolute difference between their instantaneous training-conditional miscoverage probabilities. We sum these probabilities within each replication and average the resulting totals to estimate expected cumulative disagreement.
Long-run empirical coverage and oracle disagreement. We first truncate the split conformal baseline with κ = 0.5 \kappa= 0.5 κ = 0.5 . The baseline continues to use all past scores, including observations from rounds in which truncation forces coverage or miscoverage. Figure 2 shows paths of the cumulative deviation and estimates of expected disagreement with the population oracle. All simulated paths satisfy the long-run empirical coverage constraint at every round, up to numerical precision. For β < 1 / 2 \beta< 1/2 β < 1/2 , disagreement remains close to that of the unconstrained baseline and follows the T \sqrt{T} T rate predicted by theory. For β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 , the curves are consistent with the T β T^\beta T β rate in Theorem 2.2 .
Figure 2. Long-run empirical coverage and oracle disagreement of truncated split conformal prediction. We use α = 0.1 \alpha= 0.1 α = 0.1 and κ = 0.5 \kappa= 0.5 κ = 0.5 . Panels (a)–(b) show the cumulative deviations for β = 0.3 \beta= 0.3 β = 0.3 and β = 0.7 \beta= 0.7 β = 0.7 , respectively: the first twelve paths, the mean over 500 replications, and the bounds ± κ t 1 − β \pm\kappa t^{1-\beta} ± κ t 1 − β . Paths are displayed every 100 rounds through t = 50,000 t = 50{,}000 t = 50 , 000 . Panels (c)–(d) compare estimated expected cumulative disagreement with the population oracle for the truncated and unconstrained conformal algorithms. Both panels have logarithmic horizontal axes; panel (c) has a linear vertical axis and panel (d) a logarithmic one. The theoretical rates are proportional to T \sqrt{T} T for β < 1 / 2 \beta< 1/2 β < 1/2 and T β T^\beta T β for β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 .
The cost of truncation. To measure how much truncation changes the baseline’s predictions, we compare Γ κ , β ∘ C C P \Gamma_{\kappa,\beta} \circ\mathcal{C}^{\mathrm{CP}} Γ κ , β ∘ C CP with C C P \mathcal{C}^{\mathrm{CP}} C CP on the same observations. Let p t C P = P ( Y t ∉ C C P ( X t ) ∣ G t − 1 ) p_t^{\mathrm{CP}} = \mathbb{P}(Y_t \notin\mathcal{C}^{\mathrm{CP}}(X_t) \mid\mathcal{G}_{t-1}) p t CP = P ( Y t ∈ / C CP ( X t ) ∣ G t − 1 ) be the baseline’s instantaneous training-conditional miscoverage probability. The training-conditional disagreement probability is p t C P p_t^{\mathrm{CP}} p t CP when truncation forces coverage, 1 − p t C P 1-p_t^{\mathrm{CP}} 1 − p t CP when it forces miscoverage, and zero otherwise. Summing these probabilities and averaging across replications estimates E P [ ℓ T ( Γ κ , β ∘ C C P , C C P ) ] \mathbb{E}_{P}[\ell_T(\Gamma_{\kappa,\beta} \circ\mathcal{C}^{\mathrm{CP}}, \mathcal{C}^{\mathrm{CP}})] E P [ ℓ T ( Γ κ , β ∘ C CP , C CP )] .
Figure 3 compares this truncation cost with the baseline and total disagreement for β = 0.3 , 0.5 , 0.7 \beta= 0.3, 0.5, 0.7 β = 0.3 , 0.5 , 0.7 . The baseline disagreement is consistent with T \sqrt{T} T growth in all three cases. For β = 0.3 \beta= 0.3 β = 0.3 , the truncation cost remains nearly zero over the plotted horizons, so the total stays close to the baseline. For β = 0.5 \beta= 0.5 β = 0.5 and β = 0.7 \beta= 0.7 β = 0.7 , the truncation cost grows approximately along the T \sqrt{T} T and T 0.7 T^{0.7} T 0.7 rates, respectively.
Figure 3. Baseline disagreement, truncation cost, and total disagreement. For κ = 0.5 \kappa= 0.5 κ = 0.5 , the three panels show β = 0.3 , 0.5 , 0.7 \beta= 0.3, 0.5, 0.7 β = 0.3 , 0.5 , 0.7 , respectively. Each compares E P [ ℓ T ( C C P , C P ∗ ) ] \mathbb{E}_{\mathbb{P}}[\ell_T(\mathcal{C}^{\mathrm{CP}}, \mathcal{C}^{*}_{\mathbb{P}})] E P [ ℓ T ( C CP , C P ∗ )] , E P [ ℓ T ( Γ κ , β ∘ C C P , C C P ) ] \mathbb{E}_{\mathbb{P}}[\ell_T(\Gamma_{\kappa,\beta} \circ\mathcal{C}^{\mathrm{CP}}, \mathcal{C}^{\mathrm{CP}})] E P [ ℓ T ( Γ κ , β ∘ C CP , C CP )] , and E P [ ℓ T ( Γ κ , β ∘ C C P , C P ∗ ) ] \mathbb{E}_{\mathbb{P}}[\ell_T(\Gamma_{\kappa,\beta} \circ\mathcal{C}^{\mathrm{CP}}, \mathcal{C}^{*}_{\mathbb{P}})] E P [ ℓ T ( Γ κ , β ∘ C CP , C P ∗ )] . The sum curve adds the first two estimates from paired replications and bounds the corresponding total estimate from above. All horizontal axes are logarithmic. Panel (a) uses a linear vertical axis to show values near zero; panels (b)–(c) use logarithmic vertical axes.
Comparison with ACI. We compare ACI with truncated split conformal prediction under the same ( β , 2 ) (\beta,2) ( β , 2 ) long-run empirical coverage guarantee, for β ∈ { 0.3 , 0.5 , 0.7 } \beta\in\{0.3, 0.5, 0.7\} β ∈ { 0.3 , 0.5 , 0.7 } . We initialize ACI at the population threshold q 1 = 0.9 q_1 = 0.9 q 1 = 0.9 and use step sizes η t = t − ( 1 − β ) \eta_t = t^{-(1-\beta)} η t = t − ( 1 − β ) . Since the score lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] , (23) gives κ = 2 \kappa= 2 κ = 2 for ACI; we use the same value for truncation. Within each replication, both algorithms receive the same observations and are evaluated against the same population oracle.
Under this model, ACI accumulates disagreement faster than truncated split conformal prediction in all three panels of Figure 4 . The ACI curves are consistent with the T ( 1 + β ) / 2 T^{(1+\beta)/2} T ( 1 + β ) /2 rate in Corollary 3.1.
Figure 4. ACI and truncated split conformal prediction under the same long-run empirical coverage guarantee. Both algorithms use α = 0.1 \alpha= 0.1 α = 0.1 and satisfy the ( β , 2 ) (\beta, 2) ( β , 2 ) constraint. Each panel uses logarithmic axes and shows estimated expected cumulative disagreement with the population oracle over 500 paired replications. ACI uses q 1 = 0.9 q_1 = 0.9 q 1 = 0.9 and η t = t − ( 1 − β ) \eta_t = t^{-(1-\beta)} η t = t − ( 1 − β ) . The theoretical rates are proportional to T ( 1 + β ) / 2 T^{(1+\beta)/2} T ( 1 + β ) /2 for ACI and T max { 1 / 2 , β } T^{\max\{1/2,\beta\}} T m a x { 1/2 , β } for truncated split conformal prediction.
Related work
Conformal prediction. Conformal prediction constructs prediction sets with finite-sample marginal coverage under exchangeability [40 , 35 , 3 ] . Inductive or split conformal prediction separates model fitting from calibration [29 , 26 ] . Conformalized quantile regression uses fitted conditional quantiles to adapt interval widths to heteroscedasticity [34 ] , while distributional conformal prediction builds scores from an estimated conditional distribution [12 ] .
Extensions address covariate shift [37 ] , label shift [30 ] , and coverage loss when exchangeability fails [7 ] . Cauchois et al. [11 ] construct prediction sets with finite-sample coverage bounds for test distributions within an f f f -divergence ball. Related work on robust risk evaluation incorporates isotonic constraints on density ratios [20 ] . Applications include inference for counterfactuals and individual treatment effects [27 , 25 ] , prediction with censored survival outcomes [10 , 21 ] , missing covariates [44 ] , and unobserved matrix entries [19 ] .
In the batch setting, Areces et al. [5 ] establish a minimax lower bound of order n − 1 / 2 n^{-1/2} n − 1/2 on the expected training-conditional coverage error after n n n i.i.d. observations, for prediction sets defined by thresholds or intervals on a fixed score. Duchi [14 ] develops sample-conditional coverage bounds for split conformal prediction and relates them to these lower bounds. We study cumulative error in online prediction and the additional cost of a long-run empirical coverage constraint.
Online conformal prediction and adaptive calibration. Adaptive calibration uses past coverage errors to adjust prediction sets as the data distribution changes. Adaptive conformal inference (ACI) adjusts the nominal coverage level and controls long-run empirical coverage on arbitrary data sequences ([17 ] ). Subsequent methods adapt learning rates with local dynamic-regret guarantees ([18 ] ), or aggregate ACI predictors with different learning rates ([45 ] ). Betting-based methods use parameter-free online optimization to avoid choosing a learning rate ([31 ] ).
Direct threshold updates connect long-run empirical coverage control with quantile estimation. Conformal PID control combines quantile tracking, correction for errors in cumulative coverage, and forecasts of future score quantiles ([1 ] ). For fixed bounded scores, appropriately decaying step sizes preserve long-run empirical coverage and yield quantile convergence under i.i.d. sampling and a unique target quantile ([2 ] ).
Time-series methods use past residuals and forecasts to adapt prediction intervals to temporal dependence. EnbPI uses bootstrap ensemble residuals and updates their empirical quantiles as new observations arrive (Xu and Xie, 2021). Sequential predictive conformal inference instead estimates conditional quantiles of future residuals from past residuals (Xu and Xie, 2023). Bellman conformal inference uses multi-step forecasts and dynamic programming to choose prediction intervals ([43 ] ). Jiang et al. [24 ] document severe undercoverage of the leave-one-out jackknife under short-range temporal dependence. Their leave-a-window-out modification omits blocks of observations and gives approximate marginal-coverage guarantees under stability of the fitting algorithm and quantitative bounds on temporal dependence.
Srinivas [36 ] studies the trade-off between empirical coverage and average interval length, measured relative to the shortest fixed interval that achieves the target coverage in hindsight. Areces et al. [6 ] formulate calibration as an online optimization problem, obtaining the long-run empirical coverage in the adversarial setting and convergence of instantaneous training-conditional coverage under assumptions that include a linear model for conditional score quantiles. When the data law changes, a central goal is to keep training-conditional coverage close to its target. Liang et al. [28 ] study Δ T i n s t \Delta^{\mathrm{inst}}_T Δ T inst , defined in (4) , for independent observations with unknown change points or bounded cumulative distribution drift. Their methods combine drift detection and recalibration and attain minimax rates up to logarithmic factors within the algorithm classes they study, but do not impose a long-run empirical coverage constraint that holds on every data sequence.
Regret, local coverage, and group coverage. Strongly adaptive online methods bound quantile-loss regret over all time intervals ([9 ] ), where, however, quantile-loss regret alone does not directly imply coverage guarantees. Multivalid methods control empirical coverage across groups and threshold ranges under smoothness conditions on the score distributions ([8 ] ). Ramalingam et al. [32 ] distinguish regret from coverage, relate swap regret to multivalidity, and develop group-conditional extensions of ACI. Other work studies exponentially discounted regret and coverage ([46 ] ), selection among candidate prediction models (Hajjihashemi and Shen, 2024), and gradient equilibrium, which relates vanishing average loss gradients to online calibration ([4 ] ).
Discussion
We seek a best-of-both-worlds online algorithm whose prediction sets satisfy the long-run empirical coverage constraint (6) on every data sequence and disagree as little as possible with oracles whose instantaneous training-conditional coverage is exactly 1 − α 1-\alpha 1 − α for i.i.d. data. We show that, over the class Q \mathcal{Q} Q of i.i.d. distributions with a nonatomic score, the minimax expected disagreement with the closest such oracle is of order T max { 1 / 2 , β } T^{\max\{1/2,\beta\}} T m a x { 1/2 , β } under this constraint. The constraint therefore leaves the unconstrained rate T \sqrt{T} T unchanged for β ≤ 1 / 2 \beta\le1/2 β ≤ 1/2 and raises it to T β T^\beta T β for β > 1 / 2 \beta> 1/2 β > 1/2 . Truncated split conformal prediction attains this rate. With the same fixed score, ACI with step sizes proportional to t − ( 1 − β ) t^{-(1-\beta)} t − ( 1 − β ) satisfies the same constraint, but its expected disagreement is of order T ( 1 + β ) / 2 T^{(1+\beta)/2} T ( 1 + β ) /2 when the score has a density bounded away from zero and infinity. This rate exceeds T max { 1 / 2 , β } T^{\max\{1/2,\beta\}} T m a x { 1/2 , β } for every 0 < β < 1 0 < \beta< 1 0 < β < 1 .
This paper also leaves the following questions open. Since the minimax-optimal construction may not be unique, it may be of interest to refine the optimality criterion by quantifying the accuracy of such prediction sets via the volume. Open questions include how to retain informative prediction sets and adaptive instantaneous training-conditional coverage under distribution drift while preserving a prescribed adversarial constraint.
Acknowledgement
R.F.B. was partially supported by the Office of Naval Research via grant N00014-24-1-2544. C.M. was partially supported by the National Science Foundation via the CAREER Award DMS2443867.
Disclosure of AI usage
GPT-6-Astra and Claude-Fable-5.1 models were used to produce numerical experiments, polish writing, suggest literature, and audit existing proofs; the authors take full responsibility for the contents of the paper.
Results under asymmetric constraints
The main text uses the symmetric constraint (6) . Here we allow its two sides to grow at different rates and prove the main results in this setting. The symmetric statements follow by taking b = d = β b=d=\beta b = d = β and c − = c + = κ c_-=c_+=\kappa c − = c + = κ . The ACI result is proved separately in Appendix § 14 .
Setting and notation
Fix α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , b , d ∈ [ 0 , 1 ] b,d\in[0,1] b , d ∈ [ 0 , 1 ] , and c − , c + > 0 c_-,c_+>0 c − , c + > 0 with c − + c + ≥ 1 c_-+c_+\ge1 c − + c + ≥ 1 . Write
L t = c − t 1 − d , U t = c + t 1 − b , β = min { b , d } , β ˉ = max { b , d } , t ≥ 1. L_t=c_-t^{1-d},\qquad U_t=c_+t^{1-b},\qquad\beta=\min\{b,d\},\qquad\bar{\beta}=\max\{b,d\},\qquad t\ge1. L t = c − t 1 − d , U t = c + t 1 − b , β = min { b , d } , β ˉ = max { b , d } , t ≥ 1.
Set L 0 = U 0 = 0 L_0=U_0=0 L 0 = U 0 = 0 .
Notations. We write σ = α ( 1 − α ) \sigma=\sqrt{\alpha(1-\alpha)} σ = α ( 1 − α ) , ν = min { α , 1 − α } \nu=\min\{\alpha,1-\alpha\} ν = min { α , 1 − α } , and x + = max { x , 0 } x_+=\max\{x,0\} x + = max { x , 0 } . Write Z t = ( X t , Y t ) ∈ Z = X × Y Z_t=(X_t,Y_t)\in\mathcal{Z}=\mathcal{X}\times\mathcal{Y} Z t = ( X t , Y t ) ∈ Z = X × Y and G t − 1 = σ ( ( Z r ) r < t ) \mathcal{G}_{t-1}=\sigma((Z_r)_{r<t}) G t − 1 = σ (( Z r ) r < t ) . For a fixed measurable score s s s , put s t = s ( Z t ) s_t=s(Z_t) s t = s ( Z t ) . Write Q ~ \widetilde{\mathcal{Q}} Q for all i.i.d. distributions on the observation sequence and Q \mathcal{Q} Q for the nonempty subclass under which s 1 s_1 s 1 is atomless. For an i.i.d. distribution P \mathbb{P} P , denote its one-observation marginal by μ P \mu_{\mathbb{P}} μ P , so P = μ P ⊗ N \mathbb{P}=\mu_{\mathbb{P}}^{\otimes\mathbb{N}} P = μ P ⊗ N . For fixed P \mathbb{P} P and s s s , abbreviate the score CDF F P , s F_{\mathbb{P},s} F P , s to F F F and retain q P , s q_{\mathbb{P},s} q P , s for the population quantile in (12) .
Write e C = ( e t C ) t ≥ 1 e^{\mathcal{C}}=(e_t^{\mathcal{C}})_{t\ge1} e C = ( e t C ) t ≥ 1 for the error sequence of C \mathcal{C} C and p t C = P ( e t C = 1 ∣ G t − 1 ) p_t^{\mathcal{C}}=\mathbb{P}(e_t^{\mathcal{C}}=1\mid\mathcal{G}_{t-1}) p t C = P ( e t C = 1 ∣ G t − 1 ) for its instantaneous training-conditional miscoverage probability. The error on a history h h h and fresh observation z z z is a product-measurable function e t ( h , z ) e_t(h,z) e t ( h , z ) . Use e 0 e^0 e 0 and e ∗ e^* e ∗ for the error sequences of the baseline and comparison oracle, respectively. When a single algorithm is fixed, we may omit its superscript. For binary paths u , v u,v u , v , write
E t ( u ) = ∑ r = 1 t ( u r − α ) , D T ( u , v ) = ∑ r = 1 T ∣ u r − v r ∣ , E 0 ( u ) = 0. E_t(u)=\sum_{r=1}^{t}(u_r-\alpha),\qquad D_T(u,v)=\sum_{r=1}^{T}|u_r-v_r|,\qquad E_0(u)=0. E t ( u ) = r = 1 ∑ t ( u r − α ) , D T ( u , v ) = r = 1 ∑ T ∣ u r − v r ∣ , E 0 ( u ) = 0.
Thus E t C = E t ( e C ) E_t^{\mathcal{C}}=E_t(e^{\mathcal{C}}) E t C = E t ( e C ) and ℓ T ( C , C ′ ) = D T ( e C , e C ′ ) \ell_T(\mathcal{C},\mathcal{C}')=D_T(e^{\mathcal{C}},e^{\mathcal{C}'}) ℓ T ( C , C ′ ) = D T ( e C , e C ′ ) . When comparing a constrained path u u u to a reference path v v v , abbreviate their centered sums to E t = E t ( u ) E_t=E_t(u) E t = E t ( u ) and S t = E t ( v ) S_t=E_t(v) S t = E t ( v ) , respectively.
The coverage constraint. The class A b , d , c − , c + \mathcal{A}_{b,d,c_-,c_+} A b , d , c − , c + consists of algorithms whose centered errors satisfy
− L t ≤ E t C ≤ U t for every t ≥ 1 and every data sequence. (27) -L_t\le E_t^{\mathcal{C}}\le U_t\qquad\text{for every }t\ge1\text{ and every data sequence.} \tag*{(27)} − L t ≤ E t C ≤ U t for every t ≥ 1 and every data sequence. (27)
Thus b b b controls the upper side and d d d the lower side. All algorithms and oracles in this appendix are deterministic, as in the main text.
Every binary path u u u satisfies − α t ≤ E t ( u ) ≤ ( 1 − α ) t -\alpha t\le E_t(u)\le(1-\alpha)t − α t ≤ E t ( u ) ≤ ( 1 − α ) t . The first horizon at which the constraint excludes a binary sequence is
T 0 = inf { t ∈ N ≥ 1 : U t < ( 1 − α ) t or L t < α t } , inf ∅ = ∞ . (28) T_0=\inf\{t\in\mathbb{N}_{\ge1}:U_t<(1-\alpha)t\text{ or }L_t<\alpha t\},\qquad\inf\varnothing=\infty. \tag*{(28)} T 0 = inf { t ∈ N ≥ 1 : U t < ( 1 − α ) t or L t < α t } , inf ∅ = ∞. (28)
We call the constraint nontrivial when T 0 < ∞ T_0<\infty T 0 < ∞ . Otherwise b = d = 0 b=d=0 b = d = 0 , c + ≥ 1 − α c_+\ge1-\alpha c + ≥ 1 − α , and c − ≥ α c_-\ge\alpha c − ≥ α , so A b , d , c − , c + = A \mathcal{A}_{b,d,c_-,c_+}=\mathcal{A} A b , d , c − , c + = A .
For nontrivial constraints, the cost of imposing the constraint on an exact oracle has three regimes:
g b , d ( T ) = { 1 , β ˉ < 1 / 2 , T , β ≤ 1 / 2 ≤ β ˉ , T β , β > 1 / 2. (29) g_{b,d}(T) =
\begin{cases}
1, & \bar{\beta} < 1/2, \\
\sqrt{T}, & \beta\le1/2 \le\bar{\beta}, \\
T^{\beta}, & \beta> 1/2.
\end{cases} \tag*{(29)} g b , d ( T ) = ⎩ ⎨ ⎧ 1 , T , T β , β ˉ < 1/2 , β ≤ 1/2 ≤ β ˉ , β > 1/2. (29)
Both boundaries grow faster than t \sqrt{t} t in the first regime. At least one boundary grows at most as fast as t \sqrt{t} t in the second, and both grow more slowly in the third. In the symmetric case, g β , β ( T ) g_{\beta,\beta}(T) g β , β ( T ) is 1 1 1 for β < 1 / 2 \beta< 1/2 β < 1/2 and T β T^{\beta} T β for β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 .
Asymmetric truncation. For a baseline C 0 \mathcal{C}^{0} C 0 , let C ^ = Γ a s y m ∘ C 0 \widehat{\mathcal{C}} = \Gamma_{\mathrm{asym}} \circ\mathcal{C}^{0} C = Γ asym ∘ C 0 denote the truncated algorithm for the fixed parameters ( b , d , c − , c + ) (b,d,c_{-},c_{+}) ( b , d , c − , c + ) , which is defined by
C ^ t ( x ) = { Y , E t − 1 C ^ + 1 − α > U t , ∅ , E t − 1 C ^ − α < − L t , C t 0 ( x ) , otherwise , E 0 C ^ = 0. (30) \widehat{\mathcal{C}}_{t}(x) =
\begin{cases}
\mathcal{Y}, & \mathbb{E}_{t-1}^{\widehat{\mathcal{C}}} + 1-\alpha> U_{t}, \\
\varnothing, & \mathbb{E}_{t-1}^{\widehat{\mathcal{C}}} - \alpha< -L_{t}, \\
\mathcal{C}^{0}_{t}(x), & \text{otherwise},
\end{cases}
\qquad
\mathbb{E}_{0}^{\widehat{\mathcal{C}}}=0. \tag*{(30)} C t ( x ) = ⎩ ⎨ ⎧ Y , ∅ , C t 0 ( x ) , E t − 1 C + 1 − α > U t , E t − 1 C − α < − L t , otherwise , E 0 C = 0. (30)
For a binary input e e e , write e ^ = Γ a s y m ( e ) \widehat{e}=\Gamma_{\mathrm{asym}}(e) e = Γ asym ( e ) for the output on errors. The first two conditions in (30) , evaluated at the centered sum of e ^ \widehat{e} e , specify rounds forced from above and below, respectively. In particular,
e Γ a s y m ∘ C 0 = Γ a s y m ( e C 0 ) , e ^ t = { 0 , forced from above , 1 , forced from below , e t , otherwise . (31) e^{\Gamma_{\mathrm{asym}}\circ\mathcal{C}^{0}}=\Gamma_{\mathrm{asym}}(e^{\mathcal{C}^{0}}),
\qquad
\widehat{e}_{t} =
\begin{cases}
0, & \text{forced from above}, \\
1, & \text{forced from below}, \\
e_{t}, & \text{otherwise}.
\end{cases} \tag*{(31)} e Γ asym ∘ C 0 = Γ asym ( e C 0 ) , e t = ⎩ ⎨ ⎧ 0 , 1 , e t , forced from above , forced from below , otherwise . (31)
The two conditions are disjoint since L t + U t ≥ 1 L_{t}+U_{t}\ge1 L t + U t ≥ 1 . The baseline uses every observation, including observations from forced rounds. Under b = d = β b=d=\beta b = d = β and c − = c + = κ c_{-}=c_{+}=\kappa c − = c + = κ , Γ a s y m \Gamma_{\mathrm{asym}} Γ asym specializes to Γ κ , β \Gamma_{\kappa,\beta} Γ κ , β in (18) .
Let N T + , N T − N_{T}^{+},N_{T}^{-} N T + , N T − count the rounds forced from above and below through T T T , and M T + , M T − M_{T}^{+},M_{T}^{-} M T + , M T − the rounds on which those respective branches change the input error. Write N T = N T + + N T − N_{T}=N_{T}^{+}+N_{T}^{-} N T = N T + + N T − and use subscript ∞ \infty ∞ for the corresponding limits. Appendix § 11 proves feasibility and stability.
Oracle risks. When P \mathbb{P} P is fixed, write C P ∗ \mathcal{C}_{\mathbb{P}}^{*} C P ∗ for an oracle in the exact-oracle family O α ( P ) \mathcal{O}_{\alpha}(\mathbb{P}) O α ( P ) of (11) . Define
r T ( C ; P ) = inf C P ∗ ∈ O α ( P ) E P ℓ T ( C , C P ∗ ) , r_{T}(\mathcal{C};\mathbb{P}) =
\inf_{\mathcal{C}_{\mathbb{P}}^{*}\in\mathcal{O}_{\alpha}(\mathbb{P})}
\mathbb{E}_{\mathbb{P}}\ell_{T}(\mathcal{C},\mathcal{C}_{\mathbb{P}}^{*}), r T ( C ; P ) = C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) ,
R T ( C ) = sup P ∈ Q r T ( C ; P ) , R T 0 = inf C ∈ A R T ( C ) . (32) R_{T}(\mathcal{C})=\sup_{\mathbb{P}\in\mathcal{Q}}r_{T}(\mathcal{C};\mathbb{P}),
\qquad
R_{T}^{0}=\inf_{\mathcal{C}\in\mathcal{A}}R_{T}(\mathcal{C}). \tag*{(32)} R T ( C ) = P ∈ Q sup r T ( C ; P ) , R T 0 = C ∈ A inf R T ( C ) . (32)
All constants in the constraint bounds below depend only on α , b , d , c − , c + \alpha,b,d,c_{-},c_{+} α , b , d , c − , c + .
Unconstrained minimax rate
Without a long-run empirical coverage constraint, the cost of learning from past observations is of order T \sqrt{T} T , even when the comparison ranges over all exact oracles.
Lemma A.1. For every T ≥ 1 T \ge1 T ≥ 1 ,
ν 2 32 T ≤ R T 0 ≤ 3 T . \frac{\nu^2}{32}\sqrt{T} \le R_T^0 \le3\sqrt{T}. 32 ν 2 T ≤ R T 0 ≤ 3 T .
Appendix § 12 proves the lemma and shows that split conformal prediction attains its upper bound.
Lower bounds
Theorem A.1 (Disagreement forced by an asymmetric constraint). Suppose that T 0 < ∞ T_0 < \infty T 0 < ∞ . For every i.i.d. law P P P admitting an exact oracle C P ∗ \mathcal{C}_{\mathbb{P}}^* C P ∗ , and every online algorithm C \mathcal{C} C satisfying (27) ,
E P ℓ T ( C , C P ∗ ) ≥ c g b , d ( T ) ( T ≥ T 1 ) , (33) \mathbb{E}_{P}\ell_T(\mathcal{C},\mathcal{C}_{\mathbb{P}}^*) \ge c\,g_{b,d}(T) \qquad(T \ge T_1), \tag*{(33)} E P ℓ T ( C , C P ∗ ) ≥ c g b , d ( T ) ( T ≥ T 1 ) , (33) where c > 0 c > 0 c > 0 and T 1 T_1 T 1 are uniform over the law, algorithm, and oracle. This statement allows C \mathcal{C} C to know P \mathbb{P} P . Consequently, every C ∈ A b , d , c − , c + \mathcal{C} \in\mathcal{A}_{b,d,c_-,c_+} C ∈ A b , d , c − , c + satisfies
R T ( C ) ≳ R T 0 + g b , d ( T ) . (34) R_T(\mathcal{C}) \gtrsim R_T^0 + g_{b,d}(T). \tag*{(34)} R T ( C ) ≳ R T 0 + g b , d ( T ) . (34)
Appendix § 10 proves the constraint bound and combines the two costs. Under the symmetric specialization, this gives Theorem 2.1 .
Truncation and the minimax rate
Theorem A.2 (Stability of truncation). For every baseline C 0 ∈ A \mathcal{C}^0 \in\mathcal{A} C 0 ∈ A , the algorithm Γ a s y m ∘ C 0 \Gamma_{\mathrm{asym}} \circ\mathcal{C}^0 Γ asym ∘ C 0 belongs to A b , d , c − , c + \mathcal{A}_{b,d,c_-,c_+} A b , d , c − , c + . For every i.i.d. law P P P and every exact oracle C P ∗ \mathcal{C}_{\mathbb{P}}^* C P ∗ under that law,
E P ℓ T ( Γ a s y m ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K g b , d ( T ) ( T ≥ 1 ) , (35) \mathbb{E}_{P}\ell_T(\Gamma_{\mathrm{asym}} \circ\mathcal{C}^0,\mathcal{C}_{\mathbb{P}}^*) \le2\mathbb{E}_{P}\ell_T(\mathcal{C}^0,\mathcal{C}_{\mathbb{P}}^*) + K g_{b,d}(T) \qquad(T \ge1), \tag*{(35)} E P ℓ T ( Γ asym ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K g b , d ( T ) ( T ≥ 1 ) , (35) where K < ∞ K < \infty K < ∞ is independent of the baseline, law, and oracle.
This result does not require a continuous score distribution or calibrated baseline errors. It uses only the exact oracle condition of the comparison algorithm. Appendix § 11 proves it, and the symmetric case gives (21) .
Theorem A.3 (Minimax disagreement under asymmetric constraints). For the fixed score s s s , nonempty class Q \mathcal{Q} Q , and full exact-oracle families of the main text,
inf C ∈ A b , d , c − , c + R T ( C ) ≍ T max { 1 / 2 , β } . (36) \inf_{\mathcal{C} \in\mathcal{A}_{b,d,c_-,c_+}} R_T(\mathcal{C}) \asymp T^{\max\{1/2,\beta\}}. \tag*{(36)} C ∈ A b , d , c − , c + inf R T ( C ) ≍ T m a x { 1/2 , β } . (36) The single algorithm Γ a s y m ∘ C C P \Gamma_{\mathrm{asym}} \circ\mathcal{C}^{\mathrm{CP}} Γ asym ∘ C CP attains the upper bound.
Appendix § 9 .§ 5 combines the learning and constraint bounds to prove this theorem. Taking b = d = β b = d = \beta b = d = β and c − = c + = κ c_- = c_+ = \kappa c − = c + = κ gives Theorem 2.2 .
Proof of Theorem A.3
Proof. We first compare the three possible constraint costs with the learning cost. We then establish matching lower and upper bounds. Step 1: identify the resulting rate. The definition of g b , d g_{b,d} g b , d gives
T + g b , d ( T ) ≍ T max { 1 / 2 , β } . (37) \sqrt{T}+g_{b,d}(T)\asymp T^{\max\{1/2,\beta\}}. \tag*{(37)} T + g b , d ( T ) ≍ T m a x { 1/2 , β } . (37)
Indeed, g b , d ( T ) g_{b,d}(T) g b , d ( T ) is bounded when β ˉ < 1 / 2 \bar{\beta}<1/2 β ˉ < 1/2 and is T \sqrt{T} T when β ≤ 1 / 2 ≤ β ˉ \beta\le1/2\le\bar{\beta} β ≤ 1/2 ≤ β ˉ . In both cases the sum has order T \sqrt{T} T . When β > 1 / 2 \beta>1/2 β > 1/2 , the term T β T^\beta T β is the larger term.
Step 2: bound every constrained algorithm from below. Suppose first that the constraint is nontrivial. By Theorem A.1 and Lemma A.1 , every C ∈ A b , d , c − , c + \mathcal{C}\in\mathcal{A}_{b,d,c_-,c_+} C ∈ A b , d , c − , c + satisfies
R T ( C ) ≳ T + g b , d ( T ) ≍ T max { 1 / 2 , β } . R_T(\mathcal{C})\gtrsim\sqrt{T}+g_{b,d}(T)\asymp T^{\max\{1/2,\beta\}}. R T ( C ) ≳ T + g b , d ( T ) ≍ T m a x { 1/2 , β } .
The constants and initial horizon are uniform over C \mathcal{C} C , so taking the infimum over A b , d , c − , c + \mathcal{A}_{b,d,c_-,c_+} A b , d , c − , c + preserves this bound. If the constraint is trivial, then A b , d , c − , c + = A \mathcal{A}_{b,d,c_-,c_+}=\mathcal{A} A b , d , c − , c + = A and β = 0 \beta=0 β = 0 . In that case Lemma A.1 gives the same conclusion directly.
Step 3: attain the rate with truncated conformal prediction. Take C 0 = C C P \mathcal{C}^{0}=\mathcal{C}^{\mathrm{CP}} C 0 = C CP in (30) . By Theorem A.2 , this algorithm belongs to A b , d , c − , c + \mathcal{A}_{b,d,c_-,c_+} A b , d , c − , c + on every data sequence. For each P ∈ Q \mathbb{P}\in\mathcal{Q} P ∈ Q , the population score oracle is exact, so
inf C P ∗ ∈ O α ( P ) E P ℓ T ( C ^ , C P ∗ ) ≤ E P ℓ T ( C ^ , C P , s ∗ ) \inf_{\mathcal{C}^{*}_{P}\in\mathcal{O}_{\alpha}(\mathbb{P})}\mathbb{E}_{\mathbb{P}}\ell_T(\widehat{\mathcal{C}},\mathcal{C}^{*}_{P})
\le\mathbb{E}_{\mathbb{P}}\ell_T(\widehat{\mathcal{C}},\mathcal{C}^{*}_{P,s}) C P ∗ ∈ O α ( P ) inf E P ℓ T ( C , C P ∗ ) ≤ E P ℓ T ( C , C P , s ∗ )
≤ 2 E P ℓ T ( C C P , C P , s ∗ ) + K g b , d ( T ) \le2\mathbb{E}_{\mathbb{P}}\ell_T(\mathcal{C}^{\mathrm{CP}},\mathcal{C}^{*}_{P,s})+K g_{b,d}(T) ≤ 2 E P ℓ T ( C CP , C P , s ∗ ) + K g b , d ( T )
≤ 6 T + K g b , d ( T ) . \le6\sqrt{T}+K g_{b,d}(T). ≤ 6 T + K g b , d ( T ) .
The last bound is uniform over P \mathbb{P} P , and (37) gives the desired upper rate. Neither the conformal baseline nor truncation depends on T T T , so the same algorithm works for all horizons.
Finally, setting b = d = β b=d=\beta b = d = β and c − = c + = κ c_-=c_+=\kappa c − = c + = κ turns Γ a s y m \Gamma_{\mathrm{asym}} Γ asym into the truncation rule (18) . The upper and lower bounds then give (20) and (19) .
Proof of the asymmetric lower bound
The proof is based on the following facts.
Lemma B.1. If a deterministic online oracle satisfies (11) , its errors are i.i.d. Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) .
Lemma B.2 (Comparing a constrained path with a reference path). Suppose that − L t ≤ E t ≤ U t -L_t\le E_t\le U_t − L t ≤ E t ≤ U t for every t ≤ T t\le T t ≤ T . For 0 ≤ r < r ′ ≤ T 0\le r<r'\le T 0 ≤ r < r ′ ≤ T ,
∑ t = r + 1 r ′ ∣ e t − e t ∗ ∣ ≥ ∣ S r ′ − S r ∣ − ( c − + c + ) T 1 − β . (38) \sum_{t=r+1}^{r'}\lvert e_t-e_t^{*}\rvert\ge\lvert S_{r'}-S_r\rvert-(c_-+c_+)T^{1-\beta}. \tag*{(38)} t = r + 1 ∑ r ′ ∣ e t − e t ∗ ∣ ≥ ∣ S r ′ − S r ∣ − ( c − + c + ) T 1 − β . (38)
At the terminal horizon,
D T ( e , e ∗ ) ≥ ( S T − U T ) + , D T ( e , e ∗ ) ≥ ( − S T − L T ) + . (39) D_T(e,e^{*})\ge(S_T-U_T)_{+},\qquad D_T(e,e^{*})\ge(-S_T-L_T)_{+}. \tag*{(39)} D T ( e , e ∗ ) ≥ ( S T − U T ) + , D T ( e , e ∗ ) ≥ ( − S T − L T ) + . (39)
Lemma B.3 (Fluctuations of the Bernoulli walk). Suppose the reference errors are i.i.d. Bern ( α ) (\alpha) ( α ) . There is a α r w > 0 a_{\alpha}^{\mathrm{rw}} > 0 a α rw > 0 such that E ∣ S n ∣ ≥ a α r w n \mathbb{E}|S_n| \ge a_{\alpha}^{\mathrm{rw}}\sqrt{n} E ∣ S n ∣ ≥ a α rw n for every n ≥ 1 n \ge1 n ≥ 1 . For every fixed a > 0 a > 0 a > 0 ,
lim n → ∞ P ( S n ≥ a n ) = lim n → ∞ P ( − S n ≥ a n ) = 1 − Φ ( a / σ ) > 0 , \lim_{n\to\infty}\mathbb{P}(S_n \ge a\sqrt{n}) = \lim_{n\to\infty}\mathbb{P}(-S_n \ge a\sqrt{n}) = 1-\Phi(a/\sigma)>0, n → ∞ lim P ( S n ≥ a n ) = n → ∞ lim P ( − S n ≥ a n ) = 1 − Φ ( a / σ ) > 0 , where Φ \Phi Φ is the standard normal distribution function.
The first two lemmas are elementary facts specific to our comparison. The last uses the classical central limit theorem and convergence of moments under uniform integrability; we recall the short application below rather than prove these standard results.
Proof of Theorem A.1
Proof. Fix P \mathbb{P} P , C \mathcal{C} C , and C P ∗ \mathcal{C}_{\mathbb{P}}^{*} C P ∗ as in the theorem. Apply Lemma B.2 to e = e C e=e^{\mathcal{C}} e = e C and e ∗ = e C P ∗ e^{*}=e_{\mathcal{C}_{\mathbb{P}}^{*}} e ∗ = e C P ∗ . By Lemma B.1, S t S_t S t has the law in Lemma B.3 , independently of the choices of law, algorithm, and oracle.
Step 1: two tight boundaries. Suppose β > 1 / 2 \beta>1/2 β > 1/2 and write C = c − + c + C=c_{-}+c_{+} C = c − + c + . On any block, the constrained path can move by at most C T 1 − β CT^{1-\beta} C T 1 − β . Choose blocks long enough that the oracle’s expected displacement is at least twice this amount:
A = ( 2 C a α r w ) 2 , n = ⌈ A T 2 − 2 β ⌉ , m = ⌊ T / n ⌋ . A=\left(\frac{2C}{a_{\alpha}^{\mathrm{rw}}}\right)^2,\qquad n=\left\lceil AT^{2-2\beta}\right\rceil,\qquad m=\lfloor T/n\rfloor. A = ( a α rw 2 C ) 2 , n = ⌈ A T 2 − 2 β ⌉ , m = ⌊ T / n ⌋ .
For each of the m m m complete blocks, Lemmas B.2 and B.3 give expected disagreement at least a α r w n / 2 a_{\alpha}^{\mathrm{rw}}\sqrt{n}/2 a α rw n /2 . Thus
E D T ( e , e ∗ ) ≥ a α r w 2 m n . \mathbb{E}D_T(e,e^{*})\ge\frac{a_{\alpha}^{\mathrm{rw}}}{2}m\sqrt{n}. E D T ( e , e ∗ ) ≥ 2 a α rw m n .
Since 2 − 2 β < 1 2-2\beta<1 2 − 2 β < 1 , we have n ≤ T / 2 n\le T/2 n ≤ T /2 for all sufficiently large T T T , including when β = 1 \beta=1 β = 1 . Then m ≥ T / ( 2 n ) m\ge T/(2n) m ≥ T / ( 2 n ) and n ≤ ( A + 1 ) T 2 − 2 β n\le(A+1)T^{2-2\beta} n ≤ ( A + 1 ) T 2 − 2 β , giving
E D T ( e , e ∗ ) ≥ a α r w T 4 n ≥ a α r w 4 A + 1 T β . (40) \mathbb{E}D_T(e,e^{*})\ge\frac{a_{\alpha}^{\mathrm{rw}}T}{4\sqrt{n}}\ge\frac{a_{\alpha}^{\mathrm{rw}}}{4\sqrt{A+1}}T^\beta. \tag*{(40)} E D T ( e , e ∗ ) ≥ 4 n a α rw T ≥ 4 A + 1 a α rw T β . (40)
Step 2: at least one tight boundary. Suppose β ≤ 1 / 2 ≤ β ˉ \beta\le1/2\le\bar{\beta} β ≤ 1/2 ≤ β ˉ . If b ≥ 1 / 2 b\ge1/2 b ≥ 1/2 , then U T ≤ c + T U_T\le c_{+}\sqrt{T} U T ≤ c + T . On { S T ≥ ( c + + 1 ) T } \{S_T\ge(c_{+}+1)\sqrt{T}\} { S T ≥ ( c + + 1 ) T } , (39) gives D T ( e , e ∗ ) ≥ T D_T(e,e^{*})\ge\sqrt{T} D T ( e , e ∗ ) ≥ T . Consequently,
E D T ( e , e ∗ ) ≥ T P { S T ≥ ( c + + 1 ) T } ≳ T \mathbb{E}D_T(e,e^{*})\ge\sqrt{T}\mathbb{P}\{S_T\ge(c_{+}+1)\sqrt{T}\}\gtrsim\sqrt{T} E D T ( e , e ∗ ) ≥ T P { S T ≥ ( c + + 1 ) T } ≳ T
by Lemma B.3 . If d ≥ 1 / 2 d\ge1/2 d ≥ 1/2 , apply the same argument to − S T -S_T − S T and c − c_{-} c − .
Step 3: two wide boundaries. Suppose β ˉ < 1 / 2 \bar{\beta}<1/2 β ˉ < 1/2 . Since T 0 < ∞ T_0<\infty T 0 < ∞ , at time T 0 T_0 T 0 the constraint excludes either the all-one or all-zero error path. The oracle follows these paths with probabilities α T 0 \alpha^{T_0} α T 0 and ( 1 − α ) T 0 (1-\alpha)^{T_0} ( 1 − α ) T 0 , respectively. On the excluded path, the constrained algorithm must disagree at least once. As D T ( e , e ∗ ) D_T(e,e^{*}) D T ( e , e ∗ ) is nondecreasing,
E D T ( e , e ∗ ) ≥ ν T 0 > 0 ( T ≥ T 0 ) . \mathbb{E}D_T(e,e^{*})\ge\nu^{T_0}>0\qquad(T\ge T_0). E D T ( e , e ∗ ) ≥ ν T 0 > 0 ( T ≥ T 0 ) .
Together, Steps 1–3 prove (33) , with constants and starting horizons depending only on the constraint parameters and α \alpha α .
Step 4: add the learning cost. Now let C ∈ A b , d , c − , c + \mathcal{C} \in\mathcal{A}_{b,d,c_{-},c_{+}} C ∈ A b , d , c − , c + be distribution-independent. The pointwise bound survives the infimum over exact oracles and the supremum over Q \mathcal{Q} Q , so R T ( C ) ≥ c g b , d ( T ) R_T(\mathcal{C}) \ge c g_{b,d}(T) R T ( C ) ≥ c g b , d ( T ) for large T T T . Also R T ( C ) ≥ R T 0 R_T(\mathcal{C}) \ge R_T^0 R T ( C ) ≥ R T 0 because C ∈ A \mathcal{C} \in\mathcal{A} C ∈ A . Taking the larger of these two bounds gives
R T ( C ) ≥ min { 1 , c } 2 ( R T 0 + g b , d ( T ) ) . R_T(\mathcal{C}) \ge\frac{\min\{1,c\}}{2}\left(R_T^0 + g_{b,d}(T)\right). R T ( C ) ≥ 2 min { 1 , c } ( R T 0 + g b , d ( T ) ) .
Finally, Lemma A.1 gives R T 0 ≍ T R_T^0 \asymp\sqrt{T} R T 0 ≍ T for the class and oracle family of the main text. This proves the theorem.
Proof of Lemma B.1
Proof. Because the oracle is deterministic and online, e 1 ∗ , … , e t − 1 ∗ e_1^*,\ldots,e_{t-1}^* e 1 ∗ , … , e t − 1 ∗ are measurable with respect to G t − 1 \mathcal{G}_{t-1} G t − 1 . The exact oracle condition gives P ( e t ∗ = 1 ∣ G t − 1 ) = α \mathbb{P}(e_t^* = 1 \mid\mathcal{G}_{t-1}) = \alpha P ( e t ∗ = 1 ∣ G t − 1 ) = α almost surely. For any a 1 , … , a t ∈ { 0 , 1 } a_1,\ldots,a_t \in\{0,1\} a 1 , … , a t ∈ { 0 , 1 } , conditioning on G t − 1 \mathcal{G}_{t-1} G t − 1 therefore gives
P ( e 1 ∗ = a 1 , … , e t ∗ = a t ) = α a t ( 1 − α ) 1 − a t P ( e 1 ∗ = a 1 , … , e t − 1 ∗ = a t − 1 ) . \mathbb{P}(e_1^* = a_1,\ldots,e_t^* = a_t) = \alpha^{a_t}(1-\alpha)^{1-a_t}\mathbb{P}(e_1^* = a_1,\ldots,e_{t-1}^* = a_{t-1}). P ( e 1 ∗ = a 1 , … , e t ∗ = a t ) = α a t ( 1 − α ) 1 − a t P ( e 1 ∗ = a 1 , … , e t − 1 ∗ = a t − 1 ) .
Iteration proves the product Bernoulli law. In fact, this argument only needs exact instantaneous training-conditional coverage, not independence of the original observations.
Proof of Lemma B.2
Proof. For 0 ≤ r < r ′ ≤ T 0 \le r < r' \le T 0 ≤ r < r ′ ≤ T , the triangle inequality gives
∑ t = r + 1 r ′ ∣ e t − e t ∗ ∣ ≥ ∣ ( S r ′ − S r ) − ( E r ′ − E r ) ∣ . \sum_{t=r+1}^{r'} \lvert e_t-e_t^*\rvert\ge\lvert(S_{r'}-S_r)-(E_{r'}-E_r)\rvert. t = r + 1 ∑ r ′ ∣ e t − e t ∗ ∣ ≥ ∣( S r ′ − S r ) − ( E r ′ − E r )∣ .
Both E r E_r E r and E r ′ E_{r'} E r ′ lie in [ − c − T 1 − β , c + T 1 − β ] [-c_{-}T^{1-\beta},c_{+}T^{1-\beta}] [ − c − T 1 − β , c + T 1 − β ] ; this includes E 0 = 0 E_0=0 E 0 = 0 . Their difference has absolute value at most ( c − + c + ) T 1 − β (c_{-}+c_{+})T^{1-\beta} ( c − + c + ) T 1 − β , proving (38) . At r = 0 r=0 r = 0 , the bounds E T ≤ U T E_T \le U_T E T ≤ U T and E T ≥ − L T E_T \ge-L_T E T ≥ − L T give D T ( e , e ∗ ) ≥ S T − U T D_T(e,e^*) \ge S_T-U_T D T ( e , e ∗ ) ≥ S T − U T and D T ( e , e ∗ ) ≥ − S T − L T D_T(e,e^*) \ge-S_T-L_T D T ( e , e ∗ ) ≥ − S T − L T . Since D T ( e , e ∗ ) ≥ 0 D_T(e,e^*) \ge0 D T ( e , e ∗ ) ≥ 0 , the positive-part bounds follow.
Justification of Lemma B.3
The classical i.i.d. central limit theorem gives S n / n ⇒ N ( 0 , σ 2 ) S_n/\sqrt{n} \Rightarrow N(0,\sigma^2) S n / n ⇒ N ( 0 , σ 2 ) . Also E ( S n / n ) 2 = σ 2 \mathbb{E}(S_n/\sqrt{n})^2=\sigma^2 E ( S n / n ) 2 = σ 2 , so ∣ S n ∣ / n \lvert S_n\rvert/\sqrt{n} ∣ S n ∣ / n is uniformly integrable. Convergence of first moments therefore gives
E ∣ S n ∣ n ⟶ σ 2 π > 0 ; \frac{\mathbb{E}\lvert S_n\rvert}{\sqrt{n}} \longrightarrow\sigma\sqrt{\frac{2}{\pi}}>0; n E ∣ S n ∣ ⟶ σ π 2 > 0 ;
see Van der Vaart [38 ] for these standard convergence results. Every finite n n n also has E ∣ S n ∣ > 0 \mathbb{E}\lvert S_n\rvert>0 E ∣ S n ∣ > 0 , so the infimum of these normalized expectations is positive. Finally, convergence of the two tail probabilities follows from the central limit theorem because the normal distribution has no atoms.
Proof of the truncation upper bound
This section proves Theorem A.2 , and we first present the following lemmas. In the notation of Appendix § 9 .§ 1 , take ( u , v ) = ( e ˉ , e ) (u,v)=(\bar e,e) ( u , v ) = ( e ˉ , e ) , the truncated output and its input.
Lemma C.1 (Feasibility and stability). For every binary input e e e , truncation satisfies
− L t ≤ E t ≤ U t for every t ≥ 1. -L_t \le E_t \le U_t \qquad\text{for every } t \ge1. − L t ≤ E t ≤ U t for every t ≥ 1.
For every two binary inputs e , e ′ e,e' e , e ′ and every T ≥ 1 T \ge1 T ≥ 1 ,
D T ( Γ a s y m ( e ) , Γ a s y m ( e ′ ) ) ≤ 2 D T ( e , e ′ ) . (41) D_T(\Gamma_{\mathrm{asym}}(e),\Gamma_{\mathrm{asym}}(e')) \le2D_T(e,e'). \tag*{(41)} D T ( Γ asym ( e ) , Γ asym ( e ′ )) ≤ 2 D T ( e , e ′ ) . (41)
Lemma C.2 (Expected cost on Bernoulli errors). Let the input errors e t e_t e t be i.i.d. Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) . There is a finite constant K K K such that
E D T ( Γ a s y m ( e ) , e ) ≤ E N T ≤ K g b , d ( T ) for every T ≥ 1. (42) \mathbb{E}D_T(\Gamma_{\mathrm{asym}}(e),e) \le\mathbb{E}N_T \le K g_{b,d}(T) \qquad\text{for every } T \ge1. \tag*{(42)} E D T ( Γ asym ( e ) , e ) ≤ E N T ≤ K g b , d ( T ) for every T ≥ 1. (42)
If β ˉ < 1 / 2 \bar{\beta}<1/2 β ˉ < 1/2 , then E N ∞ < ∞ \mathbb{E}N_\infty<\infty E N ∞ < ∞ .
Lemma C.1 shows that truncating two nearby error sequences keeps them nearby. Lemma C.2 bounds the additional disagreement needed to truncate an exact oracle, independently of its data law. We first combine these facts and then prove the lemmas.
Proof of Theorem A.2
Proof. Compare the baseline and oracle on the same observations.
Step 1: enforce the constraint. The first part of Lemma C.1 applies to every realization of e 0 e^0 e 0 . Hence Γ a s y m ∘ C 0 \Gamma_{\mathrm{asym}}\circ\mathcal{C}^0 Γ asym ∘ C 0 satisfies the asymmetric coverage constraint on every data sequence.
Step 2: compare the two truncated sequences. By the triangle inequality and (41),
ℓ T ( Γ a s y m ∘ C 0 , C P ∗ ) = D T ( Γ a s y m ( e 0 ) , e ∗ ) ≤ D T ( Γ a s y m ( e 0 ) , Γ a s y m ( e ∗ ) ) + D T ( Γ a s y m ( e ∗ ) , e ∗ ) ≤ 2 ℓ T ( C 0 , C P ∗ ) + D T ( Γ a s y m ( e ∗ ) , e ∗ ) . \begin{aligned}
\ell_T(\Gamma_{\mathrm{asym}}\circ\mathcal{C}^0,\mathcal{C}^*_{\mathrm{P}}) &= D_T(\Gamma_{\mathrm{asym}}(e^0),e^*) \\
&\le D_T(\Gamma_{\mathrm{asym}}(e^0),\Gamma_{\mathrm{asym}}(e^*)) + D_T(\Gamma_{\mathrm{asym}}(e^*),e^*) \\
&\le2\ell_T(\mathcal{C}^0,\mathcal{C}^*_{\mathrm{P}}) + D_T(\Gamma_{\mathrm{asym}}(e^*),e^*).
\end{aligned} ℓ T ( Γ asym ∘ C 0 , C P ∗ ) = D T ( Γ asym ( e 0 ) , e ∗ ) ≤ D T ( Γ asym ( e 0 ) , Γ asym ( e ∗ )) + D T ( Γ asym ( e ∗ ) , e ∗ ) ≤ 2 ℓ T ( C 0 , C P ∗ ) + D T ( Γ asym ( e ∗ ) , e ∗ ) .
This comparison is pathwise and requires no independence between the baseline and the oracle.
Step 3: bound the oracle’s truncation cost. By Lemma B.1, e ∗ e^* e ∗ is i.i.d. Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) . Taking expectations and applying Lemma C.2 gives
E P ℓ T ( Γ a s y m ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K g b , d ( T ) ( T ≥ 1 ) . \mathbb{E}_{\mathrm{P}}\ell_T(\Gamma_{\mathrm{asym}}\circ\mathcal{C}^0,\mathcal{C}^*_{\mathrm{P}}) \le2\mathbb{E}_{\mathrm{P}}\ell_T(\mathcal{C}^0,\mathcal{C}^*_{\mathrm{P}}) + K g_{b,d}(T) \qquad(T \ge1). E P ℓ T ( Γ asym ∘ C 0 , C P ∗ ) ≤ 2 E P ℓ T ( C 0 , C P ∗ ) + K g b , d ( T ) ( T ≥ 1 ) .
The constant is independent of the baseline, the oracle, and the law, as required. □
Proof of Lemma C.1
Proof. We prove the lemma in the following steps.
Step 1: write the allowed error counts. Let K t = ∑ r ≤ t e ^ r K_t = \sum_{r \le t} \hat{e}_r K t = ∑ r ≤ t e ^ r , with K 0 = 0 K_0 = 0 K 0 = 0 , and define
a t = ⌈ α t − L t ⌉ , z t = ⌊ α t + U t ⌋ ( t ≥ 1 ) , a 0 = z 0 = 0. a_t = \lceil\alpha t - L_t \rceil,\qquad z_t = \lfloor\alpha t + U_t \rfloor\qquad(t \ge1),\qquad a_0 = z_0 = 0. a t = ⌈ α t − L t ⌉ , z t = ⌊ α t + U t ⌋ ( t ≥ 1 ) , a 0 = z 0 = 0.
The coverage constraint is equivalent to a t ≤ K t ≤ z t a_t \le K_t \le z_t a t ≤ K t ≤ z t . The interval [ α t − L t , α t + U t ] [\alpha t - L_t, \alpha t + U_t] [ α t − L t , α t + U t ] has length L t + U t ≥ c − + c + ≥ 1 L_t + U_t \ge c_- + c_+ \ge1 L t + U t ≥ c − + c + ≥ 1 , so a t ≤ z t a_t \le z_t a t ≤ z t . Also, for every t ≥ 1 t \ge1 t ≥ 1 ,
z t ≥ z t − 1 , a t ≤ a t − 1 + 1. (43) z_t \ge z_{t-1},\qquad a_t \le a_{t-1} + 1. \tag*{(43)} z t ≥ z t − 1 , a t ≤ a t − 1 + 1. (43)
For t ≥ 2 t \ge2 t ≥ 2 , these inequalities follow because U t U_t U t is nondecreasing and α t − L t \alpha t - L_t α t − L t increases by at most α < 1 \alpha< 1 α < 1 in one round. For t = 1 t = 1 t = 1 , they follow from z 1 ≥ 0 z_1 \ge0 z 1 ≥ 0 and a 1 ≤ 1 a_1 \le1 a 1 ≤ 1 .
Step 2: identify truncation with clipping. Define clip t ( x ) = min { z t , max { a t , x } } \operatorname{clip}_t(x) = \min\{z_t, \max\{a_t, x\}\} clip t ( x ) = min { z t , max { a t , x }} . We prove by induction that
K t = clip t ( K t − 1 + e t ) , a t ≤ K t ≤ z t . (44) K_t = \operatorname{clip}_t(K_{t-1} + e_t),\qquad a_t \le K_t \le z_t. \tag*{(44)} K t = clip t ( K t − 1 + e t ) , a t ≤ K t ≤ z t . (44)
Assume a t − 1 ≤ K t − 1 ≤ z t − 1 a_{t-1} \le K_{t-1} \le z_{t-1} a t − 1 ≤ K t − 1 ≤ z t − 1 . The upper trigger in (30) is equivalent to K t − 1 + 1 > z t K_{t-1} + 1 > z_t K t − 1 + 1 > z t . By (43) , this can occur only when K t − 1 = z t K_{t-1} = z_t K t − 1 = z t and forcing error zero then gives the clipped value. The lower trigger is equivalent to K t − 1 < a t K_{t-1} < a_t K t − 1 < a t . Again, by (43) , this can occur only when K t − 1 + 1 = a t K_{t-1} + 1 = a_t K t − 1 + 1 = a t , which forces the error to be 1, giving the clipped value. Both triggers cannot hold simultaneously, since it would imply z t = K t − 1 < a t z_t = K_{t-1} < a_t z t = K t − 1 < a t . If neither holds, both K t − 1 K_{t-1} K t − 1 and K t − 1 + 1 K_{t-1} + 1 K t − 1 + 1 lie in [ a t , z t ] [a_t, z_t] [ a t , z t ] , and the input error is unchanged. This proves (44) and feasibility.
Step 3: change one input at a time. Suppose first that e e e and e ′ e' e ′ differ only at round r r r , with e r = 1 e_r = 1 e r = 1 and e r ′ = 0 e'_r = 0 e r ′ = 0 . Let K t , K t ′ K_t, K'_t K t , K t ′ be their clipped counts. The function clip t \operatorname{clip}_t clip t is nondecreasing and satisfies
0 ≤ clip t ( x ) − clip t ( y ) ≤ x − y ( x ≥ y ) . 0 \le\operatorname{clip}_t(x) - \operatorname{clip}_t(y) \le x-y \qquad(x \ge y). 0 ≤ clip t ( x ) − clip t ( y ) ≤ x − y ( x ≥ y ) .
Thus K t − K t ′ K_t - K'_t K t − K t ′ is zero before r r r , is either zero or one at r r r , and is nonnegative and nonincreasing afterward because the later inputs agree. The gap, which takes integer values, can change at most twice: from zero to one at r r r , and from one back to zero at a later round. The difference of the output errors equals the increment of this gap, so D T ( Γ a s y m ( e ) , Γ a s y m ( e ′ ) ) ≤ 2 D_T(\Gamma_{\mathrm{asym}}(e), \Gamma_{\mathrm{asym}}(e')) \le2 D T ( Γ asym ( e ) , Γ asym ( e ′ )) ≤ 2 . The case e r = 0 , e r ′ = 1 e_r = 0, e'_r = 1 e r = 0 , e r ′ = 1 follows by exchanging the two inputs. For arbitrary inputs, replace their differing coordinates in the first T T T rounds, one at a time, and apply the triangle inequality. The first T T T outputs depend only on those coordinates, giving (41) .
Proof of Lemma C.2
Counts and three bounds. For the i.i.d. Bern ( α ) \operatorname{Bern}(\alpha) Bern ( α ) input in Lemma C.2, the counts of Appendix A.1 give
D T ( Γ a s y m ( e ) , e ) = M T + + M T − ≤ N T , E t = S t − M t + + M t − . (45) D_T(\Gamma_{\mathrm{asym}}(e), e) = M_T^+ + M_T^- \le N_T,\qquad E_t = S_t - M_t^+ + M_t^-. \tag*{(45)} D T ( Γ asym ( e ) , e ) = M T + + M T − ≤ N T , E t = S t − M t + + M t − . (45)
The trigger at round t t t depends only on e 1 , … , e t − 1 e_1,\ldots,e_{t-1} e 1 , … , e t − 1 and is independent of e t e_t e t . It follows that
E N T + = α E N T + , E M T − = ( 1 − α ) E N T − . (46) \mathbb{E}N_T^{+}=\alpha\mathbb{E}N_T^{+},\qquad\mathbb{E}M_T^{-}=(1-\alpha)\mathbb{E}N_T^{-}. \tag*{(46)} E N T + = α E N T + , E M T − = ( 1 − α ) E N T − . (46)
We use three bounds, depending on whether a boundary grows faster than t \sqrt{t} t .
Lemma C.3. If d < 1 / 2 d<1/2 d < 1/2 , then E N ∞ − < ∞ \mathbb{E}N_\infty^{-}<\infty E N ∞ − < ∞ . If b < 1 / 2 b<1/2 b < 1/2 , then E N ∞ + < ∞ \mathbb{E}N_\infty^{+}<\infty E N ∞ + < ∞ .
Lemma C.4. If d < 1 / 2 ≤ b d<1/2\le b d < 1/2 ≤ b , then E N T + ≤ C T \mathbb{E}N_T^{+}\le C\sqrt{T} E N T + ≤ C T for every T ≥ 1 T\ge1 T ≥ 1 . If b < 1 / 2 ≤ d b<1/2\le d b < 1/2 ≤ d , then E N T − ≤ C T \mathbb{E}N_T^{-}\le C\sqrt{T} E N T − ≤ C T for every T ≥ 1 T\ge1 T ≥ 1 .
Lemma C.5. If β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 , then E N T ≤ C T β \mathbb{E}N_T\le CT^\beta E N T ≤ C T β for every T ≥ 1 T\ge1 T ≥ 1 .
Proof of Lemma C.2. The first inequality in (42) follows from (45) .
If β ‾ < 1 / 2 \overline{\beta}<1/2 β < 1/2 , Lemma C.3 bounds E N ∞ + \mathbb{E}N_\infty^{+} E N ∞ + and E N ∞ − \mathbb{E}N_\infty^{-} E N ∞ − , so E N T \mathbb{E}N_T E N T is bounded uniformly in T T T .
If β < 1 / 2 ≤ β ‾ \beta<1/2\le\overline{\beta} β < 1/2 ≤ β , Lemmas C.3 and C.4 give E N T ≤ C T \mathbb{E}N_T\le C\sqrt{T} E N T ≤ C T .
If β ‾ = 1 / 2 \underline{\beta}=1/2 β = 1/2 , Lemma C.5 gives the same bound.
Finally, if β > 1 / 2 \beta>1/2 β > 1/2 , Lemma C.5 gives E N T ≤ C T β \mathbb{E}N_T\le CT^\beta E N T ≤ C T β .
These are exactly the three rates in g b , d ( T ) g_{b,d}(T) g b , d ( T ) .
Proof of Lemma C.3
Proof. Assume d < 1 / 2 d<1/2 d < 1/2 and that round t t t is forced from below. Let r < t r<t r < t be the most recent upper forced round, or set r = 0 r=0 r = 0 if there is none. If r > 0 r>0 r > 0 , its upper trigger gives E r − 1 + 1 − α > U r ≥ 0 E_{r-1}+1-\alpha>U_r\ge0 E r − 1 + 1 − α > U r ≥ 0 , and hence E r = E r − 1 − α > − 1 E_r=E_{r-1}-\alpha>-1 E r = E r − 1 − α > − 1 . If r = 0 r=0 r = 0 , the same lower bound holds because E 0 = 0 E_0=0 E 0 = 0 . There are no upper changes between r + 1 r+1 r + 1 and t − 1 t-1 t − 1 , so (45) gives
E t − 1 ≥ E r + S t − 1 − S r > − 1 + S t − 1 − S r . E_{t-1}\ge E_r+S_{t-1}-S_r>-1+S_{t-1}-S_r. E t − 1 ≥ E r + S t − 1 − S r > − 1 + S t − 1 − S r .
The lower trigger gives E t − 1 < − L t + α E_{t-1}<-L_t+\alpha E t − 1 < − L t + α . Thus some 0 ≤ r < t 0\le r<t 0 ≤ r < t satisfies
S t − 1 − S r < − L t + α + 1. S_{t-1}-S_r<-L_t+\alpha+1. S t − 1 − S r < − L t + α + 1.
For all sufficiently large t t t , L t ≥ 2 ( α + 1 ) L_t\ge2(\alpha+1) L t ≥ 2 ( α + 1 ) , so the right-hand side is at most − L t / 2 -L_t/2 − L t /2 . The choice r = t − 1 r=t-1 r = t − 1 is then impossible. For each fixed r ≤ t − 2 r\le t-2 r ≤ t − 2 , the increment is the sum of t − 1 − r t-1-r t − 1 − r independent, centered variables, each taking values in an interval of length 1 1 1 . Then, Hoeffding’s inequality [23 Theorem 2, Eq. (2.6), p. 16] , applied to the negative increment, and a union bound give
P { t is forced from below } ≤ ∑ r = 0 t − 2 exp ( − L t 2 2 ( t − 1 − r ) ) ≤ t exp ( − c 2 2 t 1 − 2 d ) . \begin{aligned}
\mathbb{P}\{t\text{ is forced from below}\}\le\sum_{r=0}^{t-2}\exp\left(-\frac{L_t^2}{2(t-1-r)}\right) \\
&\le t\exp\left(-\frac{c^2}{2}t^{1-2d}\right).
\end{aligned} P { t is forced from below } ≤ r = 0 ∑ t − 2 exp ( − 2 ( t − 1 − r ) L t 2 ) ≤ t exp ( − 2 c 2 t 1 − 2 d ) .
Since 1 − 2 d > 0 1-2d>0 1 − 2 d > 0 , the last expression is summable in t t t . Summing the trigger probabilities, including the finitely many initial rounds, proves E N ∞ − < ∞ \mathbb{E}N_\infty^{-}<\infty E N ∞ − < ∞ .
For the other side, replace e t e_t e t by 1 − e t 1-e_t 1 − e t , α \alpha α by 1 − α 1-\alpha 1 − α , and exchange ( U t , L t ) (U_t,L_t) ( U t , L t ) . The two triggers are mutually exclusive by Lemma C.1. Induction in (30) therefore shows that the transformed output is 1 − e ^ t 1-\hat e_t 1 − e ^ t and its centered sum is − E t -E_t − E t . Its lower forced rounds are the original upper forced rounds. The result already proved gives E N ∞ + < ∞ \mathbb{E}N_\infty^+<\infty E N ∞ + < ∞ when b < 1 / 2 b<1/2 b < 1/2 . □
Proof of Lemma C.4
Proof. Assume d < 1 / 2 ≤ b d<1/2\le b d < 1/2 ≤ b . We bound the upper changes by the maximum of the free walk and the changes in the opposite direction. If M T + > 0 M_T^+>0 M T + > 0 , let t ≤ T t\le T t ≤ T be its last upper change. Then M T + = M t − 1 + + 1 M_T^+=M_{t-1}^++1 M T + = M t − 1 + + 1 , while the upper trigger gives E t − 1 > U t − ( 1 − α ) ≥ − 1 E_{t-1}>U_t-(1-\alpha)\ge-1 E t − 1 > U t − ( 1 − α ) ≥ − 1 . Using (45) , we obtain
M T + = S t − 1 + M t − 1 − − E t − 1 + 1 < S t − 1 + M T − + 2. M_T^+=S_{t-1}+M_{t-1}^- - E_{t-1}+1<S_{t-1}+M_T^-+2. M T + = S t − 1 + M t − 1 − − E t − 1 + 1 < S t − 1 + M T − + 2.
The case M T + = 0 M_T^+=0 M T + = 0 is immediate, so in all cases
M T + ≤ max 0 ≤ r ≤ T ∣ S r ∣ + M T − + 2. (47) M_T^+\le\max_{0\le r\le T}|S_r|+M_T^-+2. \tag*{(47)} M T + ≤ 0 ≤ r ≤ T max ∣ S r ∣ + M T − + 2. (47)
The free walk is a square-integrable martingale with E S T 2 = σ 2 T \mathbb{E}S_T^2=\sigma^2T E S T 2 = σ 2 T . Doob’s L 2 L^2 L 2 maximal inequality ([15 Theorem 4.4.4, p. 236] ) and Cauchy–Schwarz give
E max 0 ≤ r ≤ T ∣ S r ∣ ≤ ( E max 0 ≤ r ≤ T ∣ S r ∣ 2 ) 1 / 2 ≤ 2 σ T . \mathbb{E}\max_{0\le r\le T}|S_r|
\le\left(\mathbb{E}\max_{0\le r\le T}|S_r|^2\right)^{1/2}
\le2\sigma\sqrt{T}. E 0 ≤ r ≤ T max ∣ S r ∣ ≤ ( E 0 ≤ r ≤ T max ∣ S r ∣ 2 ) 1/2 ≤ 2 σ T .
Also, M T − ≤ N ∞ − M_T^-\le N_\infty^- M T − ≤ N ∞ − and Lemma C.3 gives E N ∞ − < ∞ \mathbb{E}N_\infty^-<\infty E N ∞ − < ∞ . Taking expectations in (47) and using (46) ,
E N T + ≤ 2 σ T + E N ∞ − + 2 α ≤ C T ( T ≥ 1 ) . \mathbb{E}N_T^+\le\frac{2\sigma\sqrt{T}+\mathbb{E}N_\infty^-+2}{\alpha}\le C\sqrt{T}\qquad(T\ge1). E N T + ≤ α 2 σ T + E N ∞ − + 2 ≤ C T ( T ≥ 1 ) .
Reversing the upper and lower boundaries, as in the proof of Lemma C.3 , gives the other case. □
Proof of Lemma C.5
Proof. If β = 1 \beta=1 β = 1 , then N T ≤ T N_T\le T N T ≤ T proves the claim. Assume 1 / 2 ≤ β < 1 1/2\le\beta<1 1/2 ≤ β < 1 .
Step 1: bound the width and the midpoint’s movement. Define
m t = U t − L t 2 , w t = U t + L t 2 , H t = E t − m t , ρ t = m t − m t − 1 . m_t=\frac{U_t-L_t}{2},\qquad w_t=\frac{U_t+L_t}{2},\qquad H_t=E_t-m_t,\qquad\rho_t=m_t-m_{t-1}. m t = 2 U t − L t , w t = 2 U t + L t , H t = E t − m t , ρ t = m t − m t − 1 .
Set m 0 = w 0 = H 0 = 0 m_0=w_0=H_0=0 m 0 = w 0 = H 0 = 0 . By feasibility, ∣ H t ∣ ≤ w t |H_t|\le w_t ∣ H t ∣ ≤ w t . There are constants 0 < c ≤ C < ∞ 0<c\le C<\infty 0 < c ≤ C < ∞ such that
c t 1 − β ≤ w t ≤ C t 1 − β , ∣ ρ t ∣ ≤ C t − β , w t − 1 ∣ ρ t ∣ ≤ C ( t ≥ 1 ) . (48) ct^{1-\beta}\le w_t\le Ct^{1-\beta},\qquad|\rho_t|\le Ct^{-\beta},\qquad w_{t-1}|\rho_t|\le C\qquad(t\ge1). \tag*{(48)} c t 1 − β ≤ w t ≤ C t 1 − β , ∣ ρ t ∣ ≤ C t − β , w t − 1 ∣ ρ t ∣ ≤ C ( t ≥ 1 ) . (48)
Indeed, one of b , d b,d b , d equals β \beta β , so the first bound holds with lower constant min { c − , c + } / 2 \min\{c_-,c_+\}/2 min { c − , c + } /2 and upper constant ( c − + c + ) / 2 (c_-+c_+)/2 ( c − + c + ) /2 . For t ≥ 2 t\ge2 t ≥ 2 and γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] , the mean value theorem gives
0 ≤ t γ − ( t − 1 ) γ ≤ 2 t γ − 1 . 0\le t^\gamma-(t-1)^\gamma\le2t^{\gamma-1}. 0 ≤ t γ − ( t − 1 ) γ ≤ 2 t γ − 1 .
Applying this to 1 − b 1-b 1 − b and 1 − d 1-d 1 − d proves the second bound, provided the constant is increased to cover t = 1 t=1 t = 1 . The first two bounds give w t − 1 ∣ ρ t ∣ ≤ C t 1 − 2 β ≤ C w_{t-1}|\rho_t|\le Ct^{1-2\beta}\le C w t − 1 ∣ ρ t ∣ ≤ C t 1 − 2 β ≤ C . Also, w t w_t w t is nondecreasing and tends to infinity, while ρ t \rho_t ρ t tends to zero. Choose t ⋆ t_\star t ⋆ so that
w t ≥ 2 , ∣ ρ t ∣ ≤ ν / 2 ( t ≥ t ⋆ ) . (49) w_t\ge2,\qquad|\rho_t|\le\nu/2\qquad(t\ge t_\star). \tag*{(49)} w t ≥ 2 , ∣ ρ t ∣ ≤ ν /2 ( t ≥ t ⋆ ) . (49)
Step 2: bound the increase on unforced rounds. Let I t 0 I_t^0 I t 0 indicate that neither trigger holds. On this event,
H t = H t − 1 + e t − α − ρ t . H_t = H_{t-1} + e_t - \alpha- \rho_t. H t = H t − 1 + e t − α − ρ t .
Both I t 0 I_t^0 I t 0 and H t − 1 H_{t-1} H t − 1 are determined by the previous input errors, whereas e t − α e_t-\alpha e t − α is independent of them, centered, and has variance σ 2 \sigma^2 σ 2 . Thus
E [ ( H t 2 − H t − 1 2 ) I t 0 ] = E [ ( − 2 H t − 1 ρ t + σ 2 + ρ t 2 ) I t 0 ] ≤ C 1 , (50) \mathbb{E}\left[(H_t^2-H_{t-1}^2)I_t^0\right] = \mathbb{E}\left[(-2H_{t-1}\rho_t+\sigma^2+\rho_t^2)I_t^0\right] \le C_1, \tag*{(50)} E [ ( H t 2 − H t − 1 2 ) I t 0 ] = E [ ( − 2 H t − 1 ρ t + σ 2 + ρ t 2 ) I t 0 ] ≤ C 1 , (50)
where the last bound follows from ∣ H t − 1 ∣ ≤ w t − 1 |H_{t-1}|\le w_{t-1} ∣ H t − 1 ∣ ≤ w t − 1 and (48) .
Step 3: bound the decrease on forced rounds. Fix t ≥ t ⋆ t\ge t_\star t ≥ t ⋆ and put h = E t − 1 − m t h=E_{t-1}-m_t h = E t − 1 − m t , so H t − 1 = h + ρ t H_{t-1}=h+\rho_t H t − 1 = h + ρ t . If the upper trigger holds, then h > w t − ( 1 − α ) h>w_t-(1-\alpha) h > w t − ( 1 − α ) and H t = h − α H_t=h-\alpha H t = h − α . Consequently,
H t 2 − H t − 1 2 = − ( α + ρ t ) ( 2 h − α + ρ t ) ≤ − α 2 w t . H_t^2-H_{t-1}^2=-(\alpha+\rho_t)(2h-\alpha+\rho_t)\le-\frac{\alpha}{2}w_t. H t 2 − H t − 1 2 = − ( α + ρ t ) ( 2 h − α + ρ t ) ≤ − 2 α w t .
Here (49) gives α + ρ t ≥ α / 2 \alpha+\rho_t\ge\alpha/2 α + ρ t ≥ α /2 and 2 h − α + ρ t ≥ 2 w t − 2 ≥ w t 2h-\alpha+\rho_t\ge2w_t-2\ge w_t 2 h − α + ρ t ≥ 2 w t − 2 ≥ w t . If the lower trigger holds, then h < − w t + α h<-w_t+\alpha h < − w t + α and H t = h + 1 − α H_t=h+1-\alpha H t = h + 1 − α . In this case,
H t 2 − H t − 1 2 = ( 1 − α − ρ t ) ( 2 h + 1 − α + ρ t ) ≤ − 1 − α 2 w t , H_t^2-H_{t-1}^2=(1-\alpha-\rho_t)(2h+1-\alpha+\rho_t)\le-\frac{1-\alpha}{2}w_t, H t 2 − H t − 1 2 = ( 1 − α − ρ t ) ( 2 h + 1 − α + ρ t ) ≤ − 2 1 − α w t ,
because the first factor is at least ( 1 − α ) / 2 (1-\alpha)/2 ( 1 − α ) /2 and the second is at most − 2 w t + 2 ≤ − w t -2w_t+2\le-w_t − 2 w t + 2 ≤ − w t . Writing I t = 1 − I t 0 I_t=1-I_t^0 I t = 1 − I t 0 for the indicator of a forced round, both cases give
( H t 2 − H t − 1 2 ) I t ≤ − ν 2 w t I t ( t ≥ t ⋆ ) . (51) (H_t^2-H_{t-1}^2)I_t\le-\frac{\nu}{2}w_tI_t\qquad(t\ge t_\star). \tag*{(51)} ( H t 2 − H t − 1 2 ) I t ≤ − 2 ν w t I t ( t ≥ t ⋆ ) . (51)
Step 4: count the forced rounds in a block. For an integer n ≥ t ⋆ n\ge t_\star n ≥ t ⋆ , sum (50) and the expectation of (51) over n < t ≤ 2 n n<t\le2n n < t ≤ 2 n . Since w t ≥ w n w_t\ge w_n w t ≥ w n on the block,
E H 2 n 2 − E H n 2 ≤ C 1 n − ν 2 w n E ( N 2 n − N n ) . \mathbb{E}H_{2n}^2-\mathbb{E}H_n^2\le C_1n-\frac{\nu}{2}w_n\mathbb{E}(N_{2n}-N_n). E H 2 n 2 − E H n 2 ≤ C 1 n − 2 ν w n E ( N 2 n − N n ) .
The left side is at least − w n 2 -w_n^2 − w n 2 . Rearranging and using (48) ,
E ( N 2 n − N n ) ≤ 2 ν ( C 1 n w n + w n ) ≤ C ( n β + n 1 − β ) ≤ C n β . \mathbb{E}(N_{2n}-N_n)\le\frac{2}{\nu}\left(\frac{C_1n}{w_n}+w_n\right)\le C\left(n^\beta+n^{1-\beta}\right)\le Cn^\beta. E ( N 2 n − N n ) ≤ ν 2 ( w n C 1 n + w n ) ≤ C ( n β + n 1 − β ) ≤ C n β .
The last inequality uses β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 .
Step 5: sum the blocks. Choose j 0 ≥ 0 j_0\ge0 j 0 ≥ 0 with 2 j 0 ≥ t ⋆ 2^{j_0}\ge t_\star 2 j 0 ≥ t ⋆ . For i > j 0 i>j_0 i > j 0 , Step 4 and N 2 j 0 ≤ 2 j 0 N_{2^{j_0}}\le2^{j_0} N 2 j 0 ≤ 2 j 0 give
E N 2 i ≤ 2 j 0 + C ∑ j = j 0 i − 1 2 j β ≤ C ′ 2 i β . \mathbb{E}N_{2^i}\le2^{j_0}+C\sum_{j=j_0}^{i-1}2^{j\beta}\le C'2^{i\beta}. E N 2 i ≤ 2 j 0 + C j = j 0 ∑ i − 1 2 j β ≤ C ′ 2 i β .
After increasing C ′ C' C ′ , this holds also for 0 ≤ i ≤ j 0 0\le i\le j_0 0 ≤ i ≤ j 0 . For any T ≥ 1 T\ge1 T ≥ 1 , choose i ≥ 0 i\ge0 i ≥ 0 with 2 i − 1 < T ≤ 2 i 2^{i-1}<T\le2^i 2 i − 1 < T ≤ 2 i . Monotonicity of N T N_T N T then gives E N T ≤ E N 2 i ≤ C ′ ( 2 T ) β \mathbb{E}N_T\le\mathbb{E}N_{2^i}\le C'(2T)^\beta E N T ≤ E N 2 i ≤ C ′ ( 2 T ) β , which proves the claim. □ \square □
Unconstrained minimax rate
We use the notation from Appendix § 9 .§ 1 . We first consider the following lemmas. For a fixed distribution, the first lemma turns disagreement with the closest exact oracle into a sum of instantaneous training-conditional errors.
Lemma D.1. Fix P ∈ Q \mathbb{P} \in\mathcal{Q} P ∈ Q and a deterministic measurable online algorithm C \mathcal{C} C . There is a deterministic measurable oracle C P r e p ∈ O α ( P ) \mathcal{C}_{\mathbb{P}}^{\mathrm{rep}} \in\mathcal{O}_{\alpha}(\mathbb{P}) C P rep ∈ O α ( P ) such that, for every T ≥ 1 T \ge1 T ≥ 1 ,
r T ( C ; P ) = E P ℓ T ( C , C P r e p ) = ∑ t = 1 T E P ∣ p t C − α ∣ . r_T(\mathcal{C};\mathbb{P}) = \mathbb{E}_{\mathbb{P}}\ell_T(\mathcal{C},\mathcal{C}_{\mathbb{P}}^{\mathrm{rep}}) = \sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}}|p_t^{\mathcal{C}}-\alpha|. r T ( C ; P ) = E P ℓ T ( C , C P rep ) = t = 1 ∑ T E P ∣ p t C − α ∣. The same oracle works for every horizon.
Let B t ∼ Binomial ( t , α ) B_t \sim\operatorname{Binomial}(t,\alpha) B t ∼ Binomial ( t , α ) . For t t t i.i.d. observations, B t B_t B t has the distribution of the number of miscoverages by the population score oracle. If the realized count is b b b , declaring miscoverage on the k k k largest scores disagrees with the population oracle on exactly ∣ b − k ∣ |b-k| ∣ b − k ∣ observations. The following lemma shows why the same count yields a lower bound even for algorithms that need not threshold scores.
Lemma D.2 (Comparison with a binomial count). For every C ∈ A \mathcal{C} \in\mathcal{A} C ∈ A and every T ≥ 1 T \ge1 T ≥ 1 ,
R T ( C ) ≥ ∑ t = 1 T 1 t min k ∈ { 0 , … , t } E ∣ B t − k ∣ . R_T(\mathcal{C}) \ge\sum_{t=1}^{T} \frac{1}{t}\min_{k \in\{0,\ldots,t\}}\mathbb{E}|B_t-k|. R T ( C ) ≥ t = 1 ∑ T t 1 k ∈ { 0 , … , t } min E ∣ B t − k ∣.
The last lemma supplies the upper bound using the unsmoothed conformal set in the main text.
Lemma D.3 (Conformal disagreement with the population oracle). For every P ∈ Q \mathbb{P} \in\mathcal{Q} P ∈ Q and every t ≥ 1 t \ge1 t ≥ 1 ,
E P ∣ P { Y t ∈ C t C P ( X t ) ∣ G t − 1 } − ( 1 − α ) ∣ ≤ 1 2 t + 1 + 1 t . \mathbb{E}_{\mathbb{P}}\left|\mathbb{P}\{Y_t \in\mathcal{C}^{\mathrm{CP}}_t(X_t)\mid\mathcal{G}_{t-1}\}-(1-\alpha)\right| \le\frac{1}{2\sqrt{t+1}}+\frac{1}{t}. E P P { Y t ∈ C t CP ( X t ) ∣ G t − 1 } − ( 1 − α ) ≤ 2 t + 1 1 + t 1 . The population score oracle attains the smallest expected disagreement with C C P \mathcal{C}^{\mathrm{CP}} C CP among all exact oracles. Consequently, for every T ≥ 1 T \ge1 T ≥ 1 ,
R T ( C C P ) ≤ 3 T . R_T(\mathcal{C}^{\mathrm{CP}}) \le3\sqrt{T}. R T ( C CP ) ≤ 3 T .
Proof of Lemma A.1
Proof. We first match the binomial lower bound by a prediction set with an integer cutoff at each round. The rate follows from the size of the binomial fluctuations.
Step 1. Match the lower bound at every horizon. Fix deterministic integers 0 ≤ k t ≤ t 0 \le k_t \le t 0 ≤ k t ≤ t and form the prediction set
C t ( k ) ( x ) = { y : 1 + ∑ r < t 1 { s r ≥ s ( x , y ) } > k t } . \mathcal{C}_t^{(k)}(x)=\left\{y:1+\sum_{r<t}\mathbf{1}\{s_r\ge s(x,y)\}>k_t\right\}. C t ( k ) ( x ) = { y : 1 + r < t ∑ 1 { s r ≥ s ( x , y )} > k t } .
Under any P ∈ Q \mathbb{P} \in\mathcal{Q} P ∈ Q , the t t t scores are almost surely distinct. Hold out each observation in turn and use the other t − 1 t-1 t − 1 scores in this formula. The algorithm declares miscoverage on the k t k_t k t largest scores. The population oracle declares miscoverage on the scores above q P , s q_{P,s} q P , s , whose number has distribution B t B_t B t . The two subsets are nested. By exchangeability, the disagreement probability at round t t t equals the expected fraction of these t t t decisions that disagree. Thus, for every P ∈ Q \mathbb{P} \in Q P ∈ Q ,
E P ℓ T ( C ( k ) , C P , s ∗ ) = ∑ t = 1 T E ∣ B t − k t ∣ t . \mathbb{E}_{\mathbb{P}}\ell_T(\mathcal{C}^{(k)},\mathcal{C}_{\mathbb{P},s}^{*}) = \sum_{t=1}^{T} \frac{\mathbb{E}|B_t-k_t|}{t}. E P ℓ T ( C ( k ) , C P , s ∗ ) = t = 1 ∑ T t E ∣ B t − k t ∣ .
Choose an integer median of B t B_t B t for k t k_t k t . It minimizes the summand because E ∣ B t − ( k + 1 ) ∣ − E ∣ B t − k ∣ = 2 Pr ( B t ≤ k ) − 1 \mathbb{E}|B_t-(k+1)|-\mathbb{E}|B_t-k| = 2\Pr(B_t \le k)-1 E ∣ B t − ( k + 1 ) ∣ − E ∣ B t − k ∣ = 2 Pr ( B t ≤ k ) − 1 . Comparing with the population oracle gives an upper bound uniform over Q Q Q . Together with Lemma D.2 , this gives the identity
R T 0 = ∑ t = 1 T 1 t min k ∈ { 0 , … , t } E ∣ B t − k ∣ . (52) R_T^0 = \sum_{t=1}^{T} \frac{1}{t}\min_{k\in\{0,\ldots,t\}}\mathbb{E}|B_t-k|. \tag*{(52)} R T 0 = t = 1 ∑ T t 1 k ∈ { 0 , … , t } min E ∣ B t − k ∣. (52)
Step 2. Bound the binomial fluctuations. Put X = B t − t α X=B_t-t\alpha X = B t − t α and let ξ ∼ Bernoulli ( α ) \xi\sim\operatorname{Bernoulli}(\alpha) ξ ∼ Bernoulli ( α ) . Independence and centering give
E X 2 = t σ 2 , E X 4 = t E ( ξ − α ) 4 + 3 t ( t − 1 ) σ 4 ≤ 2 t 2 σ 2 , \mathbb{E}X^2=t\sigma^2,\qquad\mathbb{E}X^4=t\mathbb{E}(\xi-\alpha)^4+3t(t-1)\sigma^4\le2t^2\sigma^2, E X 2 = t σ 2 , E X 4 = t E ( ξ − α ) 4 + 3 t ( t − 1 ) σ 4 ≤ 2 t 2 σ 2 ,
using ∣ ξ − α ∣ ≤ 1 |\xi-\alpha|\le1 ∣ ξ − α ∣ ≤ 1 and σ 2 ≤ 1 / 4 \sigma^2\le1/4 σ 2 ≤ 1/4 . For any k k k , ∣ t α − k ∣ ≤ E ∣ B t − k ∣ |t\alpha-k|\le\mathbb{E}|B_t-k| ∣ t α − k ∣ ≤ E ∣ B t − k ∣ by Jensen’s inequality. The triangle inequality and Hölder’s inequality therefore give
E ∣ B t − k ∣ ≥ 1 2 E ∣ X ∣ ≥ ( E X 2 ) 3 / 2 2 ( E X 4 ) 1 / 2 ≥ σ 2 2 2 t . \mathbb{E}|B_t-k|\ge\frac{1}{2}\mathbb{E}|X|\ge\frac{(\mathbb{E}X^2)^{3/2}}{2(\mathbb{E}X^4)^{1/2}}\ge\frac{\sigma^2}{2\sqrt{2}}\sqrt{t}. E ∣ B t − k ∣ ≥ 2 1 E ∣ X ∣ ≥ 2 ( E X 4 ) 1/2 ( E X 2 ) 3/2 ≥ 2 2 σ 2 t .
Since σ 2 ≥ ν 2 \sigma^2\ge\nu^2 σ 2 ≥ ν 2 and ∑ t = 1 T t − 1 / 2 ≥ T \sum_{t=1}^{T}t^{-1/2}\ge\sqrt{T} ∑ t = 1 T t − 1/2 ≥ T , (52) implies R T 0 ≥ ( ν 2 / 32 ) T R_T^0\ge(\nu^2/32)\sqrt{T} R T 0 ≥ ( ν 2 /32 ) T .
The usual split conformal set in (2) corresponds to k t = ⌊ α t ⌋ k_t=\lfloor\alpha t\rfloor k t = ⌊ α t ⌋ . For this choice, E ∣ B t − k t ∣ ≤ σ t + 1 \mathbb{E}|B_t-k_t|\le\sigma\sqrt{t}+1 E ∣ B t − k t ∣ ≤ σ t + 1 . Since σ ≤ 1 / 2 \sigma\le1/2 σ ≤ 1/2 and ∑ t = 1 T t − 1 / 2 ≤ 2 T \sum_{t=1}^{T}t^{-1/2}\le2\sqrt{T} ∑ t = 1 T t − 1/2 ≤ 2 T , Step 1 gives R T 0 ≤ R T ( C C P ) ≤ 3 T R_T^0\le R_T(\mathcal{C}^{\mathrm{CP}})\le3\sqrt{T} R T 0 ≤ R T ( C CP ) ≤ 3 T . □ \square □
Proof of Lemma D.1
Proof. We present the lemma in the following steps.
Step 1. Bound the disagreement of any exact oracle. For the error e t ∗ e_t^* e t ∗ of any exact oracle, conditional Jensen’s inequality gives
E P [ ∣ e t C − e t ∗ ∣ ∣ G t − 1 ] ≥ ∣ E P [ e t C − e t ∗ ∣ G t − 1 ] ∣ = ∣ p t C − α ∣ . \mathbb{E}_{\mathbb{P}}[|e_t^{C}-e_t^*|\mid\mathcal{G}_{t-1}]\ge\left|\mathbb{E}_{\mathbb{P}}[e_t^{C}-e_t^*\mid\mathcal{G}_{t-1}]\right|=|p_t^{C}-\alpha|. E P [ ∣ e t C − e t ∗ ∣ ∣ G t − 1 ] ≥ E P [ e t C − e t ∗ ∣ G t − 1 ] = ∣ p t C − α ∣.
It suffices to attain this bound at each round with the same oracle.
Step 2. Construct the oracle and compute its loss. Fix a round t t t and history h h h . For a fresh Z ∼ μ P Z\sim\mu_{\mathbb{P}} Z ∼ μ P , put
A h ( z ) = e t ( h , z ) + F ( s ( z ) ) , G h ( a ) = ∫ 1 { A h ( z ′ ) ≤ a } d μ P ( z ′ ) . A_h(z)=e_t(h,z)+F(s(z)),\qquad G_h(a)=\int\mathbf{1}\{A_h(z')\le a\}\,d\mu_{\mathbb{P}}(z'). A h ( z ) = e t ( h , z ) + F ( s ( z )) , G h ( a ) = ∫ 1 { A h ( z ′ ) ≤ a } d μ P ( z ′ ) .
Since F ( s ( Z ) ) F(s(Z)) F ( s ( Z )) is uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) , the algorithm covers exactly when A h ( Z ) ≤ 1 A_h(Z) \le1 A h ( Z ) ≤ 1 , almost surely. Also { A h ( Z ) = a } ⊆ { F ( s ( Z ) ) ∈ { a , a − 1 } } \{A_h(Z) = a\} \subseteq\{F(s(Z)) \in\{a, a-1\}\} { A h ( Z ) = a } ⊆ { F ( s ( Z )) ∈ { a , a − 1 }} , so A h ( Z ) A_h(Z) A h ( Z ) has no atoms and G h G_h G h is continuous.
Define
C P , t r e p ( x ; h ) = { y : G h ( A h ( x , y ) ) ≤ 1 − α } . C^{\mathrm{rep}}_{\mathrm{P},t}(x;h)=\{y:G_h(A_h(x,y))\le1-\alpha\}. C P , t rep ( x ; h ) = { y : G h ( A h ( x , y )) ≤ 1 − α } .
Given h h h , the probability integral transform makes G h ( A h ( Z ) ) G_h(A_h(Z)) G h ( A h ( Z )) uniformly distributed, so the oracle has instantaneous training-conditional coverage of 1 − α 1-\alpha 1 − α .
Both coverage events are lower intervals in A h ( Z ) A_h(Z) A h ( Z ) and hence are nested. If p ( h ) = ∫ e t ( h , z ) d μ P ( z ) p(h)=\int e_t(h,z)\,\mathrm{d}\mu_{\mathrm{P}}(z) p ( h ) = ∫ e t ( h , z ) d μ P ( z ) , their probabilities are G h ( 1 ) = 1 − p ( h ) G_h(1)=1-p(h) G h ( 1 ) = 1 − p ( h ) and 1 − α 1-\alpha 1 − α . Their conditional disagreement is therefore
∣ G h ( 1 ) − ( 1 − α ) ∣ = ∣ p ( h ) − α ∣ . \lvert G_h(1)-(1-\alpha)\rvert=\lvert p(h)-\alpha\rvert. ∣ G h ( 1 ) − ( 1 − α )∣ = ∣ p ( h ) − α ∣ .
At the observed history p ( h ) = p t C p(h)=p_t^C p ( h ) = p t C almost surely. Taking expectations and summing attains the lower bound from Step 1 for every T T T , since the construction is independent of the horizon. □ \square □
Proof of Lemma D.2
Proof. Fix C \mathcal{C} C and T T T . We first compute the calibration error of a decision that depends only on the relative order of the scores. We then choose one distribution under which such decisions approximate C \mathcal{C} C at every t ≤ T t\le T t ≤ T .
Step 1. Count disagreements for a rule based on ranks. Let V 1 , … , V t V_1,\ldots,V_t V 1 , … , V t be i.i.d. uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) . Write R i R_i R i for the rank of V i V_i V i among all t t t values, and let B t = ∑ i = 1 t 1 { V i ≤ α } B_t=\sum_{i=1}^{t}\mathbf{1}\{V_i\le\alpha\} B t = ∑ i = 1 t 1 { V i ≤ α } . For 0 ≤ k ≤ t 0\le k\le t 0 ≤ k ≤ t , the two indicators below select the first k k k and the first B t B_t B t ranks. Hence
∑ i = 1 t ∣ 1 { R i ≤ k } − 1 { V i ≤ α } ∣ = ∣ B t − k ∣ . \sum_{i=1}^{t}\left|\mathbf{1}\{R_i\le k\}-\mathbf{1}\{V_i\le\alpha\}\right|=\lvert B_t-k\rvert. i = 1 ∑ t ∣ 1 { R i ≤ k } − 1 { V i ≤ α } ∣ = ∣ B t − k ∣ .
Let V ( 1 ) , … , V ( t − 1 ) V_{(1)},\ldots,V_{(t-1)} V ( 1 ) , … , V ( t − 1 ) be the sorted past values, with V ( 0 ) = 0 V_{(0)}=0 V ( 0 ) = 0 and V ( t ) = 1 V_{(t)}=1 V ( t ) = 1 . Since R t ≤ k R_t\le k R t ≤ k exactly when V t ≤ V ( k ) V_t\le V_{(k)} V t ≤ V ( k ) almost surely, conditioning on the past and then using exchangeability gives
E ∣ V ( k ) − α ∣ = E ∣ 1 { R t ≤ k } − 1 { V t ≤ α } ∣ = 1 t E ∣ B t − k ∣ . \mathbb{E}\lvert V_{(k)}-\alpha\rvert=\mathbb{E}\left\lvert\mathbf{1}\{R_t\le k\}-\mathbf{1}\{V_t\le\alpha\}\right\rvert=\frac{1}{t}\mathbb{E}\lvert B_t-k\rvert. E ∣ V ( k ) − α ∣ = E ∣ 1 { R t ≤ k } − 1 { V t ≤ α } ∣ = t 1 E ∣ B t − k ∣ .
Fix the past order ρ \rho ρ . A rank-based rule declares miscoverage on some set J ( ρ ) J(\rho) J ( ρ ) . Given the past values, its miscoverage probability is
q t = ∑ j ∈ J ( ρ ) G j , G j = V ( j ) − V ( j − 1 ) . q_t=\sum_{j\in J(\rho)}G_j,\qquad G_j=V_{(j)}-V_{(j-1)}. q t = j ∈ J ( ρ ) ∑ G j , G j = V ( j ) − V ( j − 1 ) .
Given ρ \rho ρ , the sorted values have constant density ( t − 1 ) ! (t-1)! ( t − 1 )! , so the gaps are uniform on the simplex { g j ≥ 0 , ∑ j g j = 1 } \{g_j\ge0,\ \sum_j g_j=1\} { g j ≥ 0 , ∑ j g j = 1 } and are exchangeable. For t = 1 t=1 t = 1 the sole gap is G 1 = 1 G_1=1 G 1 = 1 . For k = ∣ J ( ρ ) ∣ k=\lvert J(\rho)\rvert k = ∣ J ( ρ )∣ , the sum has the same distribution as ∑ j = 1 k G j = V ( k ) \sum_{j=1}^{k}G_j=V_{(k)} ∑ j = 1 k G j = V ( k ) . Thus for each ρ \rho ρ ,
E [ ∣ q t − α ∣ ∣ ρ ] = 1 t E ∣ B t − k ∣ ≥ 1 t min 0 ≤ j ≤ t E ∣ B t − j ∣ . \mathbb{E}[\lvert q_t-\alpha\rvert\mid\rho]=\frac{1}{t}\mathbb{E}\lvert B_t-k\rvert\ge\frac{1}{t}\min_{0\le j\le t}\mathbb{E}\lvert B_t-j\rvert. E [∣ q t − α ∣ ∣ ρ ] = t 1 E ∣ B t − k ∣ ≥ t 1 0 ≤ j ≤ t min E ∣ B t − j ∣ .
Step 2. Approximate C \mathcal{C} C using only score ranks. Fix an integer m ≥ T m \ge T m ≥ T . We will give equal mass to m m m cells ordered by score. On each tuple of distinct cells, a function of the score ranks will approximate the miscoverage indicator e t = 1 { Y t ∉ C t ( X t ) } e_t = 1\{Y_t \notin\mathcal{C}_t(X_t)\} e t = 1 { Y t ∈ / C t ( X t )} with error probability below 1 / m 1/m 1/ m .
Choose the cells. Let N N N be large enough. Take μ 0 \mu_0 μ 0 with μ 0 ⊗ N ∈ Q \mu_0^{\otimes N} \in\mathcal{Q} μ 0 ⊗ N ∈ Q . Since the score is nonatomic, we can split Z \mathcal{Z} Z into N N N consecutive score bins I 1 , … , I N I_1,\ldots,I_N I 1 , … , I N , each of mass 1 / N 1/N 1/ N . For each t ≤ T t \le T t ≤ T , approximate { e t = 1 } \{e_t = 1\} { e t = 1 } in product measure by a finite union of rectangles with indicator f t f_t f t . Refine the bins by the sides of all these rectangles. Then f t f_t f t is constant on each product cell, and we can make the errors E t = { e t ≠ f t } E_t = \{e_t \ne f_t\} E t = { e t = f t } small enough that
∑ t = 1 T N t μ 0 ⊗ t ( E t ) < 1 / m . \sum_{t=1}^{T} N^t\mu_0^{\otimes t}(E_t) < 1/m. t = 1 ∑ T N t μ 0 ⊗ t ( E t ) < 1/ m .
Independently choose one partition cell D i D_i D i in each bin I i I_i I i , with Pr ( D i = D ) = N μ 0 ( D ) \Pr(D_i = D) = N\mu_0(D) Pr ( D i = D ) = N μ 0 ( D ) for each cell D ⊆ I i D \subseteq I_i D ⊆ I i . Set μ i = μ 0 ( ⋅ ∣ D i ) \mu_i = \mu_0(\mathord{\cdot}\mid D_i) μ i = μ 0 ( ⋅ ∣ D i ) . Averaging μ i \mu_i μ i over this choice gives μ 0 ( ⋅ ∣ I i ) \mu_0(\mathord{\cdot}\mid I_i) μ 0 ( ⋅ ∣ I i ) . For each ordered tuple i = ( i 1 , … , i t ) \mathbf{i} = (i_1,\ldots,i_t) i = ( i 1 , … , i t ) of distinct labels, write μ i = ⨂ r = 1 t μ i r \mu_{\mathbf{i}} = \bigotimes_{r=1}^{t}\mu_{i_r} μ i = ⨂ r = 1 t μ i r and I i = ∏ r = 1 t I i r I_{\mathbf{i}} = \prod_{r=1}^{t} I_{i_r} I i = ∏ r = 1 t I i r . Independence and disjointness of the bin products at each t t t give
E ∑ t = 1 T ∑ i μ i ( E t ) = ∑ t = 1 T N t ∑ i μ 0 ⊗ t ( E t ∩ I i ) ≤ ∑ t = 1 T N t μ 0 ⊗ t ( E t ) < 1 / m . \mathbb{E}\sum_{t=1}^{T}\sum_{\mathbf{i}}\mu_{\mathbf{i}}(E_t)
=
\sum_{t=1}^{T}N^t\sum_{\mathbf{i}}\mu_0^{\otimes t}(E_t\cap I_{\mathbf{i}})
\le
\sum_{t=1}^{T}N^t\mu_0^{\otimes t}(E_t)<1/m. E t = 1 ∑ T i ∑ μ i ( E t ) = t = 1 ∑ T N t i ∑ μ 0 ⊗ t ( E t ∩ I i ) ≤ t = 1 ∑ T N t μ 0 ⊗ t ( E t ) < 1/ m .
Fix a choice of cells for which the sum is below 1 / m 1/m 1/ m . Then μ i ( E t ) < 1 / m \mu_{\mathbf{i}}(E_t)<1/m μ i ( E t ) < 1/ m for every tuple in the sum.
Select cells on which ranks suffice. The color of a set of t t t labels records which orders give f t = 1 f_t=1 f t = 1 . For i 1 < ⋯ < i t i_1<\cdots<i_t i 1 < ⋯ < i t , define
c t ( i 1 , … , i t ) = { π ∈ S t : f t = 1 on D i π ( 1 ) × ⋯ × D i π ( t ) } , c_t(i_1,\ldots,i_t)
=
\{\pi\in S_t:f_t=1\text{ on }D_{i_{\pi(1)}}\times\cdots\times D_{i_{\pi(t)}}\}, c t ( i 1 , … , i t ) = { π ∈ S t : f t = 1 on D i π ( 1 ) × ⋯ × D i π ( t ) } ,
where S t S_t S t is the set of permutations of { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } . There are at most 2 t ! 2^{t!} 2 t ! colors. Applying the finite Ramsey theorem [33 Theorem B, p. 267] successively for t = 1 , … , T t=1,\ldots,T t = 1 , … , T gives a set H H H of m m m labels such that, for each t t t , every t t t -subset of H H H has the same color Π t \Pi_t Π t .
For distinct scores, let π ( r ) \pi(r) π ( r ) be the rank of s r s_r s r among s 1 , … , s t s_1,\ldots,s_t s 1 , … , s t and set e ~ t = 1 { π ∈ Π t } \widetilde e_t=1\{\pi\in\Pi_t\} e t = 1 { π ∈ Π t } . On distinct cells from H H H , the scores have the same relative order as their cell labels. Thus f t = e ~ t f_t=\widetilde e_t f t = e t on each such product cell, and
μ i { e t ≠ e ~ t } = μ i ( E t ) < 1 / m ( i 1 , … , i t distinct in H ) . \mu_{\mathbf{i}}\{e_t\ne\widetilde e_t\}=\mu_{\mathbf{i}}(E_t)<1/m
\qquad(i_1,\ldots,i_t\text{ distinct in }H). μ i { e t = e t } = μ i ( E t ) < 1/ m ( i 1 , … , i t distinct in H ) .
Step 3. Sum the bound under one distribution. Relabel the retained cells 1 , … , m 1,\ldots,m 1 , … , m and set μ = m − 1 ∑ i = 1 m μ i \mu=m^{-1}\sum_{i=1}^{m}\mu_i μ = m − 1 ∑ i = 1 m μ i . Since μ ≪ μ 0 \mu\ll\mu_0 μ ≪ μ 0 , the score remains nonatomic and P = μ ⊗ N ∈ Q \mathbb{P}=\mu^{\otimes N}\in\mathcal{Q} P = μ ⊗ N ∈ Q . Set p ~ t = E P [ e ~ t ∣ G t − 1 ] \widetilde p_t=\mathbb{E}_{\mathbb{P}}[\widetilde e_t\mid\mathcal{G}_{t-1}] p t = E P [ e t ∣ G t − 1 ] . The cell labels are i.i.d. uniform on { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } , so Step 2 and a union bound give
E P ∣ p t C − p ~ t ∣ ≤ P ( e t C ≠ e ~ t ) ≤ 1 m + P ( two of the first t labels coincide ) ≤ 1 + ( t 2 ) m . \mathbb{E}_{\mathbb{P}}|p_t^{\mathcal{C}}-\widetilde p_t|
\le
\mathbb{P}(e_t^{\mathcal{C}}\ne\widetilde e_t)
\le
\frac{1}{m}+\mathbb{P}(\text{two of the first }t\text{ labels coincide})
\le
\frac{1+\binom{t}{2}}{m}. E P ∣ p t C − p t ∣ ≤ P ( e t C = e t ) ≤ m 1 + P ( two of the first t labels coincide ) ≤ m 1 + ( 2 t ) .
The uniforms V r = 1 − F ( s r ) V_r=1-F(s_r) V r = 1 − F ( s r ) rank the scores in decreasing order, and V t V_t V t is independent of G t − 1 \mathcal{G}_{t-1} G t − 1 . Thus p ~ t \widetilde p_t p t is the gap sum in Step 1. By Lemma D.1 and the triangle inequality,
R T ( C ) ≥ r T ( C ; P ) = ∑ t = 1 T E P ∣ p t C − α ∣ ≥ ∑ t = 1 T 1 t min 0 ≤ k ≤ t E ∣ B t − k ∣ − 1 m ∑ t = 1 T ( 1 + ( t 2 ) ) . R_T(\mathcal{C})\ge r_T(\mathcal{C};\mathbb{P})
=
\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}}|p_t^{\mathcal{C}}-\alpha|
\ge
\sum_{t=1}^{T}\frac{1}{t}\min_{0\le k\le t}\mathbb{E}|B_t-k|
-
\frac{1}{m}\sum_{t=1}^{T}\left(1+\binom{t}{2}\right). R T ( C ) ≥ r T ( C ; P ) = t = 1 ∑ T E P ∣ p t C − α ∣ ≥ t = 1 ∑ T t 1 0 ≤ k ≤ t min E ∣ B t − k ∣ − m 1 t = 1 ∑ T ( 1 + ( 2 t ) ) .
Let m → ∞ m\to\infty m → ∞ with T T T fixed.
Proof of Lemma D.3
Proof. Fix P ∈ Q P \in\mathcal{Q} P ∈ Q . Let k t = ⌈ ( 1 − α ) t ⌉ k_t = \lceil(1-\alpha)t\rceil k t = ⌈( 1 − α ) t ⌉ . If k t ≤ t − 1 k_t \le t-1 k t ≤ t − 1 , the unsmoothed conformal set in (2) is, up to a fresh-score null event, the set whose cutoff is the k t k_t k t -th smallest of the t − 1 t-1 t − 1 past scores.
The transformed scores F ( s ( Z r ) ) F(s(Z_r)) F ( s ( Z r )) are independent uniform random variables. Consequently, the instantaneous training-conditional coverage probability Q t = 1 − p t C P Q_t = 1-p_t^{\mathrm{CP}} Q t = 1 − p t CP of the conformal set has distribution Beta ( k t , t − k t ) \operatorname{Beta}(k_t,t-k_t) Beta ( k t , t − k t ) when k t < t k_t<t k t < t , and equals one when k t = t k_t=t k t = t . The beta mean and variance, together with the case k t = t k_t=t k t = t , give
E Q t = k t t , Var ( Q t ) ≤ 1 4 ( t + 1 ) , ∣ k t t − ( 1 − α ) ∣ ≤ 1 t . \mathbb{E}Q_t = \frac{k_t}{t}, \qquad\operatorname{Var}(Q_t) \le\frac{1}{4(t+1)}, \qquad\left|\frac{k_t}{t}-(1-\alpha)\right| \le\frac{1}{t}. E Q t = t k t , Var ( Q t ) ≤ 4 ( t + 1 ) 1 , t k t − ( 1 − α ) ≤ t 1 .
The triangle inequality and Cauchy–Schwarz prove
E ∣ Q t − ( 1 − α ) ∣ ≤ 1 2 t + 1 + 1 t . \mathbb{E}\left|Q_t-(1-\alpha)\right| \le\frac{1}{2\sqrt{t+1}}+\frac{1}{t}. E ∣ Q t − ( 1 − α ) ∣ ≤ 2 t + 1 1 + t 1 .
The conformal and population prediction sets are thresholds of the same score, with both cutoffs determined before the fresh outcome. Their conditional disagreement probability is therefore exactly ∣ Q t − ( 1 − α ) ∣ |Q_t-(1-\alpha)| ∣ Q t − ( 1 − α ) ∣ . Conditional Jensen’s inequality gives this same quantity as a lower bound for every exact oracle, so the population oracle attains the infimum. Finally,
∑ t = 1 T ( 1 2 t + 1 + 1 t ) ≤ 3 2 ∑ t = 1 T t − 1 / 2 ≤ 3 T . \sum_{t=1}^{T}\left(\frac{1}{2\sqrt{t+1}}+\frac{1}{t}\right) \le\frac{3}{2}\sum_{t=1}^{T}t^{-1/2} \le3\sqrt{T}. t = 1 ∑ T ( 2 t + 1 1 + t 1 ) ≤ 2 3 t = 1 ∑ T t − 1/2 ≤ 3 T .
The bound is uniform over P ∈ Q P \in\mathcal{Q} P ∈ Q , which proves the lemma. □ \square □
Results with a relaxed oracle condition
An exact oracle condition may be impossible when the joint distribution has atoms. We therefore also consider relaxed oracles whose instantaneous training-conditional coverage is at least 1 − α 1-\alpha 1 − α :
P { Y t ∈ C P , t ∗ ( X t ) ∣ G t − 1 } ≥ 1 − α almost surely for every t ≥ 1. \mathbb{P}\{Y_t \in\mathcal{C}^{*}_{P,t}(X_t)\mid\mathcal{G}_{t-1}\}\ge1-\alpha\quad\text{almost surely for every } t\ge1. P { Y t ∈ C P , t ∗ ( X t ) ∣ G t − 1 } ≥ 1 − α almost surely for every t ≥ 1.
Let O α + ( P ) \mathcal{O}^{+}_{\alpha}(P) O α + ( P ) be a nonempty family of such oracles, fixed independently of the algorithm and horizon. The population quantile set (12) satisfies this condition even when the score distribution has atoms. For a specified nonempty family O α + ( P ) \mathcal{O}^{+}_{\alpha}(P) O α + ( P ) satisfying (oracle′), write
R T + ( C ) = sup P ∈ Q inf C P ∗ ∈ O α + ( P ) E P ℓ T ( C , C P ∗ ) , R T 0 , + = inf C ∈ A R T + ( C ) . R^{+}_{T}(\mathcal{C})=\sup_{P\in\mathcal{Q}}\inf_{\mathcal{C}^{*}_{P}\in\mathcal{O}^{+}_{\alpha}(P)}\mathbb{E}_{P}\ell_T(\mathcal{C},\mathcal{C}^{*}_{P}), \qquad R^{0,+}_{T}=\inf_{\mathcal{C}\in\mathcal{A}}R^{+}_{T}(\mathcal{C}). R T + ( C ) = P ∈ Q sup C P ∗ ∈ O α + ( P ) inf E P ℓ T ( C , C P ∗ ) , R T 0 , + = C ∈ A inf R T + ( C ) .
For this relaxed formulation, every C ∈ A b , d , c − , c + \mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}} C ∈ A b , d , c − , c + satisfies the lower-bound decomposition over the class Q \mathcal{Q} Q of all i.i.d. laws:
sup P ∈ Q inf C P ∗ ∈ O α + ( P ) E P ℓ T ( C , C P ∗ ) ≳ inf C 0 ∈ A sup P ∈ Q inf C P ∗ ∈ O α + ( P ) E P ℓ T ( C 0 , C P ∗ ) + { 0 , 0 ≤ β < 1 / 2 , T β , 1 / 2 ≤ β ≤ 1. (53) \begin{aligned}
&\sup_{P\in\mathcal{Q}}\inf_{\mathcal{C}^{*}_{P}\in\mathcal{O}^{+}_{\alpha}(P)}\mathbb{E}_{P}\ell_T(\mathcal{C},\mathcal{C}^{*}_{P}) \\
&\qquad\gtrsim\inf_{\mathcal{C}^{0}\in\mathcal{A}}\sup_{P\in\mathcal{Q}}\inf_{\mathcal{C}^{*}_{P}\in\mathcal{O}^{+}_{\alpha}(P)}\mathbb{E}_{P}\ell_T(\mathcal{C}^{0},\mathcal{C}^{*}_{P})+
\begin{cases}
0, & 0\le\beta<1/2,\\
T^{\beta}, & 1/2\le\beta\le1.
\end{cases} \tag*{(53)}
\end{aligned} P ∈ Q sup C P ∗ ∈ O α + ( P ) inf E P ℓ T ( C , C P ∗ ) ≳ C 0 ∈ A inf P ∈ Q sup C P ∗ ∈ O α + ( P ) inf E P ℓ T ( C 0 , C P ∗ ) + { 0 , T β , 0 ≤ β < 1/2 , 1/2 ≤ β ≤ 1. (53)
The unconstrained term need not have order T \sqrt{T} T . For example, if O α + ( P ) \mathcal{O}_{\alpha}^{+}(\mathbb{P}) O α + ( P ) contains all relaxed oracles, this term is zero: the algorithm that always predicts Y \mathcal{Y} Y agrees perfectly with the oracle that does the same. A relaxed oracle may therefore be a poor target for statistical accuracy, since matching it need not yield informative predictions or coverage close to 1 − α 1-\alpha 1 − α .
Formally, we have the following result.
Proposition E.1 (Lower bounds with relaxed oracles). Every C ∈ A b , d , c − , c + \mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}} C ∈ A b , d , c − , c + satisfies, for every T ≥ 1 T\ge1 T ≥ 1 ,
R T + ( C ) ≥ 1 2 ( R T 0 , + + ( α T − L T ) + ) . (54) R_{T}^{+}(\mathcal{C})\ge\frac{1}{2}\left(R_{T}^{0,+}+(\alpha T-L_{T})_{+}\right). \tag*{(54)} R T + ( C ) ≥ 2 1 ( R T 0 , + + ( α T − L T ) + ) . (54) If d > 0 d>0 d > 0 , or if d = 0 d=0 d = 0 and c − < α c_{-}<\alpha c − < α , the constrained minimax risk has order T T T . If the oracle family contains all relaxed oracles and d = 0 d=0 d = 0 , c − ≥ α c_{-}\ge\alpha c − ≥ α , the constrained minimax risk is zero.
Only the lower boundary forces a prediction set to miss a response that an always-covering oracle covers. This explains why g b , d g_{b,d} g b , d is not the appropriate universal lower bound for relaxed oracles.
To prove the lower bound above, we first consider the following lemma.
Lemma E.1 (Disagreement under a point mass). Fix any z 0 = ( x 0 , y 0 ) ∈ X × Y z_{0}=(x_{0},y_{0})\in\mathcal{X}\times\mathcal{Y} z 0 = ( x 0 , y 0 ) ∈ X × Y and let P p t \mathbb{P}_{\mathrm{pt}} P pt be the i.i.d. law concentrated on z 0 z_{0} z 0 . For every C ∈ A b , d , c − , c + \mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}} C ∈ A b , d , c − , c + , every deterministic relaxed oracle C P ∗ \mathcal{C}_{\mathbb{P}}^{*} C P ∗ under P p t \mathbb{P}_{\mathrm{pt}} P pt , and every T ≥ 1 T\ge1 T ≥ 1 ,
E P p t ℓ T ( C , C P ∗ ) = ∑ t = 1 T e t C ≥ ( α T − L T ) + . \mathbb{E}_{\mathbb{P}_{\mathrm{pt}}}\ell_{T}(\mathcal{C},\mathcal{C}_{\mathbb{P}}^{*})=\sum_{t=1}^{T}e_{t}^{\mathcal{C}}\ge(\alpha T-L_{T})_{+}. E P pt ℓ T ( C , C P ∗ ) = t = 1 ∑ T e t C ≥ ( α T − L T ) + .
Proof of Proposition E.1
Proof. We prove the proposition in the following steps.
Step 1. Combine the two lower bounds. Fix C ∈ A b , d , c − , c + \mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}} C ∈ A b , d , c − , c + and T ≥ 1 T\ge1 T ≥ 1 . Since C ∈ A \mathcal{C}\in\mathcal{A} C ∈ A , we have
R T + ( C ) ≥ R T 0 , + . R_{T}^{+}(\mathcal{C})\ge R_{T}^{0,+}. R T + ( C ) ≥ R T 0 , + .
Since P p t ∈ Q ~ \mathbb{P}_{\mathrm{pt}}\in\widetilde{\mathcal{Q}} P pt ∈ Q , Lemma E.1 gives
R T + ( C ) ≥ inf C P ∗ ∈ O α + ( P p t ) E P p t ℓ T ( C , C P ∗ ) ≥ ( α T − L T ) + . R_{T}^{+}(\mathcal{C})\ge\inf_{\mathcal{C}_{\mathbb{P}}^{*}\in\mathcal{O}_{\alpha}^{+}(\mathbb{P}_{\mathrm{pt}})}\mathbb{E}_{\mathbb{P}_{\mathrm{pt}}}\ell_{T}(\mathcal{C},\mathcal{C}_{\mathbb{P}}^{*})\ge(\alpha T-L_{T})_{+}. R T + ( C ) ≥ C P ∗ ∈ O α + ( P pt ) inf E P pt ℓ T ( C , C P ∗ ) ≥ ( α T − L T ) + .
Taking the larger of the bounds yields
R T + ( C ) ≥ max { R T 0 , + , ( α T − L T ) + } ≥ 1 2 ( R T 0 , + + ( α T − L T ) + ) , R_{T}^{+}(\mathcal{C})\ge\max\{R_{T}^{0,+},(\alpha T-L_{T})_{+}\}\ge\frac{1}{2}\left(R_{T}^{0,+}+(\alpha T-L_{T})_{+}\right), R T + ( C ) ≥ max { R T 0 , + , ( α T − L T ) + } ≥ 2 1 ( R T 0 , + + ( α T − L T ) + ) ,
which proves (54) for every horizon.
Step 2. Determine when the forced cost is linear. Since L T = c − T 1 − d L_{T}=c_{-}T^{1-d} L T = c − T 1 − d ,
( α T − L T ) + T = ( α − c − T − d ) + ⟶ { α , d > 0 , ( α − c − ) + , d = 0. \frac{(\alpha T-L_{T})_{+}}{T}=(\alpha-c_{-}T^{-d})_{+}\longrightarrow
\begin{cases}
\alpha, & d>0,\\
(\alpha-c_{-})_{+}, & d=0.
\end{cases} T ( α T − L T ) + = ( α − c − T − d ) + ⟶ { α , ( α − c − ) + , d > 0 , d = 0.
The limit is positive if d > 0 d>0 d > 0 or if d = 0 d=0 d = 0 and c − < α c_{-}<\alpha c − < α . Truncation supplies a feasible algorithm by Lemma C.1, and ℓ T ≤ T \ell_{T}\le T ℓ T ≤ T on every path. Hence in either case, for all sufficiently large T T T ,
c T ≤ inf C ∈ A b , d , c − , c + R T + ( C ) ≤ T cT\le\inf_{\mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}}}R_{T}^{+}(\mathcal{C})\le T c T ≤ C ∈ A b , d , c − , c + inf R T + ( C ) ≤ T
for some $c>0.
Step 3. Attain zero risk when the lower boundary permits full coverage. Suppose d = 0 d=0 d = 0 , c − ≥ α c_{-}\ge\alpha c − ≥ α , and the comparison family contains all relaxed oracles. The algorithm C t a l l ( x ) = Y \mathcal{C}^{\mathrm{all}}_{t}(x)=\mathcal{Y} C t all ( x ) = Y satisfies
− L t = − c − t ≤ E t C a l l = − α t ≤ U t ( t ≥ 1 ) , -L_{t}=-c_{-}t\le E^{\mathcal{C}^{\mathrm{all}}}_{t}=-\alpha t\le U_{t}\qquad(t\ge1), − L t = − c − t ≤ E t C all = − α t ≤ U t ( t ≥ 1 ) ,
so it belongs to A b , d , c − , c + \mathcal{A}_{b,d,c_{-},c_{+}} A b , d , c − , c + . Its instantaneous training-conditional coverage is one under every distribution, so it is also an admissible comparison oracle for each P ∈ Q ~ \mathbb{P}\in\widetilde{\mathcal{Q}} P ∈ Q . Comparing the algorithm with itself gives
0 ≤ inf C ∈ A b , d , c − , c + R T + ( C ) ≤ R T + ( C a l l ) ≤ sup P ∈ Q ~ E P ℓ T ( C a l l , C a l l ) = 0. 0\le\inf_{\mathcal{C}\in\mathcal{A}_{b,d,c_{-},c_{+}}}R^{+}_{T}(\mathcal{C})\le R^{+}_{T}(\mathcal{C}^{\mathrm{all}})\le\sup_{\mathbb{P}\in\widetilde{\mathcal{Q}}}\mathbb{E}_{\mathbb{P}}\ell_{T}(\mathcal{C}^{\mathrm{all}},\mathcal{C}^{\mathrm{all}})=0. 0 ≤ C ∈ A b , d , c − , c + inf R T + ( C ) ≤ R T + ( C all ) ≤ P ∈ Q sup E P ℓ T ( C all , C all ) = 0.
Proof of Lemma E.1
Proof. On the constant sequence Z t = z 0 Z_{t}=z_{0} Z t = z 0 , both the history h = ( z 0 , … , z 0 ) h=(z_{0},\ldots,z_{0}) h = ( z 0 , … , z 0 ) through round t − 1 t-1 t − 1 and the fresh response y 0 y_{0} y 0 are fixed. For a deterministic relaxed oracle, (oracle′ ' ′ ) becomes
1 − α ≤ P p t { Y t ∈ C t ∗ ( X t ) ∣ G t − 1 } = 1 { y 0 ∈ C t ∗ ( x 0 ; h ) } ∈ { 0 , 1 } . 1-\alpha\le\mathbb{P}_{\mathrm{pt}}\{Y_{t}\in\mathcal{C}^{*}_{t}(X_{t})\mid\mathcal{G}_{t-1}\}=\mathbb{1}\{y_{0}\in\mathcal{C}^{*}_{t}(x_{0};h)\}\in\{0,1\}. 1 − α ≤ P pt { Y t ∈ C t ∗ ( X t ) ∣ G t − 1 } = 1 { y 0 ∈ C t ∗ ( x 0 ; h )} ∈ { 0 , 1 } .
Since 1 − α > 0 1-\alpha>0 1 − α > 0 , the indicator is one at every round. The oracle’s error sequence is therefore zero, and on the unique data path
E P p t ℓ T ( C , C P ∗ ) = ∑ t = 1 T ∣ e t C − 0 ∣ = α T + E T C ≥ α T − L T . \mathbb{E}_{\mathbb{P}_{\mathrm{pt}}}\ell_{T}(\mathcal{C},\mathcal{C}^{*}_{\mathbb{P}})=\sum_{t=1}^{T}|e^{\mathcal{C}}_{t}-0|=\alpha T+E^{\mathcal{C}}_{T}\ge\alpha T-L_{T}. E P pt ℓ T ( C , C P ∗ ) = t = 1 ∑ T ∣ e t C − 0∣ = α T + E T C ≥ α T − L T .
The error count is also nonnegative, giving the positive part in the claim.
Take b = d = β b=d=\beta b = d = β and c − = c + = κ c_{-}=c_{+}=\kappa c − = c + = κ . If β ≥ 1 / 2 \beta\ge1/2 β ≥ 1/2 , then β > 0 \beta>0 β > 0 , so Step 2 gives R T + ( C ) ≳ T ≥ T β R^{+}_{T}(\mathcal{C})\gtrsim T\ge T^{\beta} R T + ( C ) ≳ T ≥ T β for every constrained algorithm. Together with R T + ( C ) ≥ R T + R^{+}_{T}(\mathcal{C})\ge R^{+}_{T} R T + ( C ) ≥ R T + , this proves the second case of (53) . If β < 1 / 2 \beta<1/2 β < 1/2 , that display adds zero to the unconstrained risk, so class inclusion alone proves its first case. In fact, the point-mass argument gives the stronger linear lower bound whenever β > 0 \beta>0 β > 0 . For asymmetric constraints, a tight upper bound alone does not yield this lower bound: Step 3 shows that zero risk is possible if the lower bound permits the always-covering algorithm.
Proofs for ACI
This section proves Proposition 3.1 and corollary 3.1. Here s t ∈ [ 0 , B ] s_{t}\in[0,B] s t ∈ [ 0 , B ] and e t = 1 { s t > q t } e_{t}=\mathbb{1}\{s_{t}>q_{t}\} e t = 1 { s t > q t } is the ACI error. The update (22) is q t + 1 = q t + η t ( e t − α ) q_{t+1}=q_{t}+\eta_{t}(e_{t}-\alpha) q t + 1 = q t + η t ( e t − α ) , where q 1 ∈ [ 0 , B ] q_{1}\in[0,B] q 1 ∈ [ 0 , B ] and the positive step sizes are deterministic. Write η ˉ t = max 1 ≤ r ≤ t η r \bar{\eta}_{t}=\max_{1\le r\le t}\eta_{r} η ˉ t = max 1 ≤ r ≤ t η r , with η ˉ 0 = 0 \bar{\eta}_{0}=0 η ˉ 0 = 0 . The following two bounds hold for every score sequence, without any distributional assumption. We cite their proofs from Angelopoulos et al. [2 ] .
Lemma F.1 (Angelopoulos et al., [2 ] , Lemma 1). For every sequence of scores in [ 0 , B ] [0,B] [ 0 , B ] and every t ≥ 1 t\ge1 t ≥ 1 ,
− α η ˉ t − 1 ≤ q t ≤ B + ( 1 − α ) η ˉ t − 1 . -\alpha\bar{\eta}_{t-1}\le q_{t}\le B+(1-\alpha)\bar{\eta}_{t-1}. − α η ˉ t − 1 ≤ q t ≤ B + ( 1 − α ) η ˉ t − 1 .
Lemma F.2 [2 Theorems 1 and 2] . For every sequence of scores in [ 0 , B ] [0,B] [ 0 , B ] and every T ≥ 1 T \ge1 T ≥ 1 ,
∣ E T A C I ∣ ≤ ( B + η ˉ T ) ( 1 η 1 + ∑ t = 2 T ∣ 1 η t − 1 η t − 1 ∣ ) . \left|\mathbb{E}^{\mathrm{ACI}}_T\right| \le(B+\bar{\eta}_T)\left(\frac{1}{\eta_1}+\sum_{t=2}^{T}\left|\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}\right|\right). E T ACI ≤ ( B + η ˉ T ) ( η 1 1 + t = 2 ∑ T η t 1 − η t − 1 1 ) . For nonincreasing step sizes, this becomes ∣ E T A C I ∣ ≤ ( B + η 1 ) / η T \left|\mathbb{E}^{\mathrm{ACI}}_T\right| \le(B+\eta_1)/\eta_T E T ACI ≤ ( B + η 1 ) / η T . In particular, η t = c t − ( 1 − β ) \eta_t=ct^{-(1-\beta)} η t = c t − ( 1 − β ) with c > 0 c>0 c > 0 and β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] gives the ( β , κ ) (\beta,\kappa) ( β , κ ) adversarial guarantee with κ = ( B + c ) / c \kappa=(B+c)/c κ = ( B + c ) / c .
The cited theorems bound the long-run empirical coverage rate, with the difference from 1 − α 1-\alpha 1 − α given by − E T A C I / T -\mathbb{E}^{\mathrm{ACI}}_T/T − E T ACI / T . For nonincreasing steps, 1 / η 1 + ∑ t = 2 T ∣ 1 / η t − 1 / η t − 1 ∣ = 1 / η T 1/\eta_1+\sum_{t=2}^{T}|1/\eta_t-1/\eta_{t-1}|=1/\eta_T 1/ η 1 + ∑ t = 2 T ∣1/ η t − 1/ η t − 1 ∣ = 1/ η T and η ˉ T = η 1 \bar{\eta}_T=\eta_1 η ˉ T = η 1 . This gives (23) for the stated power steps.
The score distribution and step sizes. For the rest of this section, fix an i.i.d. law P \mathbb{P} P under which the score has a density satisfying (24), and suppose
η t ⟶ 0 , ∣ η t + 1 − 1 − η t − 1 ∣ ⟶ 0. (55) \eta_t \longrightarrow0,\qquad\left|\eta_{t+1}^{-1}-\eta_t^{-1}\right|\longrightarrow0. \tag*{(55)} η t ⟶ 0 , η t + 1 − 1 − η t − 1 ⟶ 0. (55)
In particular, η ˉ : = sup t ≥ 1 η t < ∞ \bar{\eta}:=\sup_{t\ge1}\eta_t<\infty η ˉ := sup t ≥ 1 η t < ∞ . The score CDF F F F equals 0 below 0 and 1 above B B B . The density bounds give
λ − ( u − v ) ≤ F ( u ) − F ( v ) ≤ λ + ( u − v ) ( 0 ≤ v ≤ u ≤ B ) . (56) \lambda_-(u-v)\le F(u)-F(v)\le\lambda_+(u-v)\qquad(0\le v\le u\le B). \tag*{(56)} λ − ( u − v ) ≤ F ( u ) − F ( v ) ≤ λ + ( u − v ) ( 0 ≤ v ≤ u ≤ B ) . (56)
Thus F F F is continuous and strictly increasing on [ 0 , B ] [0,B] [ 0 , B ] , so q P , s ∈ ( 0 , B ) q_{\mathbb{P},s}\in(0,B) q P , s ∈ ( 0 , B ) and F ( q P , s ) = 1 − α F(q_{\mathbb{P},s})=1-\alpha F ( q P , s ) = 1 − α .
Cumulative quantile deviation and instantaneous training-conditional miscoverage. The threshold q t q_t q t is determined by the past observations, and the fresh score s t s_t s t is independent of that past. Hence, almost surely,
p t = p t A C I = 1 − F ( q t ) . (57) p_t=p_t^{\mathrm{ACI}}=1-F(q_t). \tag*{(57)} p t = p t ACI = 1 − F ( q t ) . (57)
Define
Δ t = q t − q P , s , χ ( u ) = F ( q P , s + u ) − F ( q P , s ) . (58) \Delta_t=q_t-q_{\mathbb{P},s},\qquad\chi(u)=F(q_{\mathbb{P},s}+u)-F(q_{\mathbb{P},s}). \tag*{(58)} Δ t = q t − q P , s , χ ( u ) = F ( q P , s + u ) − F ( q P , s ) . (58)
Then p t − α = − χ ( Δ t ) p_t-\alpha=-\chi(\Delta_t) p t − α = − χ ( Δ t ) , and the recursion becomes
Δ t + 1 = Δ t − η t χ ( Δ t ) + η t ξ t , ξ t = e t − p t . (59) \Delta_{t+1}=\Delta_t-\eta_t\chi(\Delta_t)+\eta_t\xi_t,\qquad\xi_t=e_t-p_t. \tag*{(59)} Δ t + 1 = Δ t − η t χ ( Δ t ) + η t ξ t , ξ t = e t − p t . (59)
Here − η t χ ( Δ t ) -\eta_t\chi(\Delta_t) − η t χ ( Δ t ) pulls the threshold toward the population quantile, while η t ξ t \eta_t\xi_t η t ξ t is noise satisfying
E P [ ξ t ∣ G t − 1 ] = 0 , E P [ ξ t 2 ∣ G t − 1 ] = p t ( 1 − p t ) , ∣ ξ t ∣ ≤ 1. (60) \mathbb{E}_{\mathbb{P}}[\xi_t\mid\mathcal{G}_{t-1}]=0,\qquad\mathbb{E}_{\mathbb{P}}[\xi_t^2\mid\mathcal{G}_{t-1}]=p_t(1-p_t),\qquad|\xi_t|\le1. \tag*{(60)} E P [ ξ t ∣ G t − 1 ] = 0 , E P [ ξ t 2 ∣ G t − 1 ] = p t ( 1 − p t ) , ∣ ξ t ∣ ≤ 1. (60)
We suppress the subscript P \mathbb{P} P on expectations below.
From disagreement to threshold deviations. The next lemma identifies the fixed-distribution risk in (32) and shows that the population prediction set attains it.
Lemma F.3 (Disagreement with the closest exact oracle). For every T ≥ 1 T \ge1 T ≥ 1 ,
r T ( C A C I ; P ) = E ∑ t = 1 T ∣ p t − α ∣ = E ∑ t = 1 T ∣ χ ( Δ t ) ∣ . (61) r_T(\mathcal{C}^{\mathrm{ACI}};\mathbb{P}) = \mathbb{E}\sum_{t=1}^{T}|p_t-\alpha| = \mathbb{E}\sum_{t=1}^{T}|\chi(\Delta_t)|. \tag*{(61)} r T ( C ACI ; P ) = E t = 1 ∑ T ∣ p t − α ∣ = E t = 1 ∑ T ∣ χ ( Δ t ) ∣. (61)
The population prediction set in (12) attains the infimum.
The density bounds make the change in instantaneous training-conditional miscoverage comparable to the threshold deviation, including when the threshold leaves [ 0 , B ] [0,B] [ 0 , B ] .
Lemma F.4 (Comparison with the threshold deviation). Let λ = min { λ − , ν / ( B + η ˉ ) } > 0 \lambda=\min\{\lambda_{-},\nu/(B+\bar{\eta})\}>0 λ = min { λ − , ν / ( B + η ˉ )} > 0 . Then ∣ Δ t ∣ ≤ B + η ˉ |\Delta_t|\le B+\bar{\eta} ∣ Δ t ∣ ≤ B + η ˉ for every t ≥ 1 t\ge1 t ≥ 1 . For every u u u with ∣ u ∣ ≤ B + η ˉ |u|\le B+\bar{\eta} ∣ u ∣ ≤ B + η ˉ , the value χ ( u ) \chi(u) χ ( u ) has the same sign as u u u and
λ ∣ u ∣ ≤ ∣ χ ( u ) ∣ ≤ λ + ∣ u ∣ . \lambda|u|\le|\chi(u)|\le\lambda_{+}|u|. λ ∣ u ∣ ≤ ∣ χ ( u ) ∣ ≤ λ + ∣ u ∣.
The last lemma gives the expected size of the deviation. Its proof balances the contraction of the second moment, of order η t E Δ t 2 \eta_t\mathbb{E}\Delta_t^2 η t E Δ t 2 , against noise of order η t 2 \eta_t^2 η t 2 . A fourth-moment bound ensures that the second moment does not come only from rare large deviations.
Lemma F.5 (Expected absolute deviation). Under (55) , there are constants 0 < c 0 ≤ C 0 < ∞ 0<c_0\le C_0<\infty 0 < c 0 ≤ C 0 < ∞ and a time t ⋆ ≥ 1 t_{\star}\ge1 t ⋆ ≥ 1 such that
c 0 η t ≤ E ∣ Δ t ∣ ≤ C 0 η t ( t ≥ t ⋆ ) . c_0\sqrt{\eta_t}\le\mathbb{E}|\Delta_t|\le C_0\sqrt{\eta_t}\qquad(t\ge t_{\star}). c 0 η t ≤ E ∣ Δ t ∣ ≤ C 0 η t ( t ≥ t ⋆ ) .
We first combine these lemmas to prove the proposition and derive the corollary. The supporting lemma proofs follow.
Proof of Proposition 3.1
Proof. The oracle identity and the density bounds reduce expected disagreement to the sum of expected absolute threshold deviations. We apply the deviation estimate and show that finitely many initial rounds are negligible. Write A T η = ∑ t = 1 T η t A_T^\eta=\sum_{t=1}^{T}\sqrt{\eta_t} A T η = ∑ t = 1 T η t , with A 0 η = 0 A_0^\eta=0 A 0 η = 0 .
Step 1: from the risk to the deviations. By Lemma F.3 and Lemma F.4 ,
λ − ∑ t = 1 T E ∣ Δ t ∣ ≤ r T ( C A C I ; P ) ≤ λ + ∑ t = 1 T E ∣ Δ t ∣ . (62) \lambda_{-}\sum_{t=1}^{T}\mathbb{E}|\Delta_t|\le r_T(\mathcal{C}^{\mathrm{ACI}};\mathbb{P})\le\lambda_{+}\sum_{t=1}^{T}\mathbb{E}|\Delta_t|. \tag*{(62)} λ − t = 1 ∑ T E ∣ Δ t ∣ ≤ r T ( C ACI ; P ) ≤ λ + t = 1 ∑ T E ∣ Δ t ∣. (62)
Step 2: the size of the deviations. By Lemma F.5 , c 0 η t ≤ E ∣ Δ t ∣ ≤ C 0 η t c_0\sqrt{\eta_t}\le\mathbb{E}|\Delta_t|\le C_0\sqrt{\eta_t} c 0 η t ≤ E ∣ Δ t ∣ ≤ C 0 η t for t ≥ t ⋆ t\ge t_{\star} t ≥ t ⋆ . For t < t ⋆ t<t_{\star} t < t ⋆ we use 0 ≤ E ∣ Δ t ∣ ≤ B + η ˉ 0\le\mathbb{E}|\Delta_t|\le B+\bar{\eta} 0 ≤ E ∣ Δ t ∣ ≤ B + η ˉ from Lemma F.4 . Inserting these bounds into (62) gives, for T ≥ t ⋆ T\ge t_{\star} T ≥ t ⋆ ,
λ − c 0 ( A T η − A t ⋆ − 1 η ) ≤ r T ( C A C I ; P ) ≤ λ + C 0 A T η + λ + ( B + η ˉ ) t ⋆ . \lambda_{-}c_0\left(A_T^\eta-A_{t_{\star}-1}^\eta\right)\le r_T(\mathcal{C}^{\mathrm{ACI}};\mathbb{P})\le\lambda_{+}C_0A_T^\eta+\lambda_{+}(B+\bar{\eta})t_{\star}. λ − c 0 ( A T η − A t ⋆ − 1 η ) ≤ r T ( C ACI ; P ) ≤ λ + C 0 A T η + λ + ( B + η ˉ ) t ⋆ .
Step 3: the first rounds are negligible. It remains to show that A T η → ∞ A_T^\eta\to\infty A T η → ∞ , so that the constants A t ⋆ − 1 η A_{t_{\star}-1}^\eta A t ⋆ − 1 η and λ + ( B + η ˉ ) t ⋆ \lambda_{+}(B+\bar{\eta})t_{\star} λ + ( B + η ˉ ) t ⋆ do not matter. Condition (55) says that the increments of 1 / η t 1/\eta_t 1/ η t tend to zero. The average of these increments then tends to zero as well, that is,
1 t η t = 1 t η 1 + 1 t ∑ r < t ( 1 η r + 1 − 1 η r ) ⟶ 0. \frac{1}{t\eta_t}=\frac{1}{t\eta_1}+\frac{1}{t}\sum_{r<t}\left(\frac{1}{\eta_{r+1}}-\frac{1}{\eta_r}\right)\longrightarrow0. t η t 1 = t η 1 1 + t 1 r < t ∑ ( η r + 1 1 − η r 1 ) ⟶ 0.
Hence t η t → ∞ t\eta_t \to\infty t η t → ∞ , so η t ≥ t − 1 / 2 \sqrt{\eta_t} \ge t^{-1/2} η t ≥ t − 1/2 for all large t t t , and A T η → ∞ A_T^\eta\to\infty A T η → ∞ . With Step 2, this gives
0 < lim inf T → ∞ r T ( C A C I ; P ) A T η ≤ lim sup T → ∞ r T ( C A C I ; P ) A T η < ∞ , (63) 0 < \liminf_{T\to\infty} \frac{r_T(\mathcal{C}^{\mathrm{ACI}};\mathbb{P})}{A_T^\eta} \le\limsup_{T\to\infty} \frac{r_T(\mathcal{C}^{\mathrm{ACI}};\mathbb{P})}{A_T^\eta} < \infty, \tag*{(63)} 0 < T → ∞ lim inf A T η r T ( C ACI ; P ) ≤ T → ∞ lim sup A T η r T ( C ACI ; P ) < ∞ , (63)
which is (25) . □
Proof of Corollary 3.1
Proof. We check the step-size assumptions of Proposition 3.1 and then evaluate the sum in its conclusion.
Step 1: check the step-size assumptions. Let c > 0 c > 0 c > 0 and β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) . The steps η t = c t − ( 1 − β ) \eta_t = ct^{-(1-\beta)} η t = c t − ( 1 − β ) tend to zero because β < 1 \beta< 1 β < 1 , and
0 ≤ 1 η t + 1 − 1 η t = ( t + 1 ) 1 − β − t 1 − β c ≤ ( 1 − β ) t − β c ⟶ 0 0 \le\frac{1}{\eta_{t+1}}-\frac{1}{\eta_t}=\frac{(t+1)^{1-\beta}-t^{1-\beta}}{c}\le\frac{(1-\beta)t^{-\beta}}{c}\longrightarrow0 0 ≤ η t + 1 1 − η t 1 = c ( t + 1 ) 1 − β − t 1 − β ≤ c ( 1 − β ) t − β ⟶ 0
because β > 0 \beta> 0 β > 0 . Thus Proposition 3.1 applies.
Step 2: evaluate the cumulative rate. For 0 ≤ γ < 1 0 \le\gamma< 1 0 ≤ γ < 1 , comparison with an integral gives
T 1 − γ ≤ ∑ t = 1 T t − γ ≤ ∫ 0 T u − γ d u = T 1 − γ 1 − γ . T^{1-\gamma}\le\sum_{t=1}^{T}t^{-\gamma}\le\int_{0}^{T}u^{-\gamma}\,du=\frac{T^{1-\gamma}}{1-\gamma}. T 1 − γ ≤ t = 1 ∑ T t − γ ≤ ∫ 0 T u − γ d u = 1 − γ T 1 − γ .
Taking γ = ( 1 − β ) / 2 \gamma=(1-\beta)/2 γ = ( 1 − β ) /2 yields
∑ t = 1 T η t = c ∑ t = 1 T t − ( 1 − β ) / 2 ≍ T ( 1 + β ) / 2 . \sum_{t=1}^{T}\sqrt{\eta_t}=\sqrt{c}\sum_{t=1}^{T}t^{-(1-\beta)/2}\asymp T^{(1+\beta)/2}. t = 1 ∑ T η t = c t = 1 ∑ T t − ( 1 − β ) /2 ≍ T ( 1 + β ) /2 .
Substitution into (25) proves (26) . □
By Lemma F.2 , these steps give the adversarial guarantee with κ = ( B + c ) / c \kappa=(B+c)/c κ = ( B + c ) / c . For any prescribed κ > 1 \kappa>1 κ > 1 , choose c = B / ( κ − 1 ) c=B/(\kappa-1) c = B / ( κ − 1 ) . Since ( 1 + β ) / 2 > max { 1 / 2 , β } (1+\beta)/2>\max\{1/2,\beta\} ( 1 + β ) /2 > max { 1/2 , β } for 0 < β < 1 0<\beta<1 0 < β < 1 , the corollary gives a larger disagreement rate than truncated split conformal prediction in Theorem 2.2 under the same guarantee.
Proofs of Lemmas F.3 and F.4
Proof of Lemma F.3. The second equality in (61) holds because p t − α = − χ ( Δ t ) p_t-\alpha=-\chi(\Delta_t) p t − α = − χ ( Δ t ) . For the first equality, we prove two inequalities.
Lower bound. Let C ′ ∈ O α ( P ) \mathcal{C}'\in\mathcal{O}_{\alpha}(\mathbb{P}) C ′ ∈ O α ( P ) be any deterministic exact oracle. Its oracle condition gives E [ e t C ′ ∣ G t − 1 ] = α \mathbb{E}[e_t^{\mathcal{C}'}\mid\mathcal{G}_{t-1}]=\alpha E [ e t C ′ ∣ G t − 1 ] = α almost surely, so conditional Jensen’s inequality gives
E P [ ∣ e t − e t C ′ ∣ ∣ G t − 1 ] ≥ ∣ E P [ e t − e t C ′ ∣ G t − 1 ] ∣ = ∣ p t − α ∣ . \mathbb{E}_{\mathbb{P}}\left[\left|e_t-e_t^{\mathcal{C}'}\right|\mid\mathcal{G}_{t-1}\right]\ge\left|\mathbb{E}_{\mathbb{P}}\left[e_t-e_t^{\mathcal{C}'}\mid\mathcal{G}_{t-1}\right]\right|=|p_t-\alpha|. E P [ e t − e t C ′ ∣ G t − 1 ] ≥ E P [ e t − e t C ′ ∣ G t − 1 ] = ∣ p t − α ∣.
Summing over t t t and taking expectations, E P [ ℓ T ( C A C I , C ′ ) ] ≥ E P ∑ t ≤ T ∣ p t − α ∣ \mathbb{E}_{\mathbb{P}}[\ell_T(\mathcal{C}^{\mathrm{ACI}},\mathcal{C}^\prime)] \ge\mathbb{E}_{\mathbb{P}}\sum_{t\le T}|p_t-\alpha| E P [ ℓ T ( C ACI , C ′ )] ≥ E P ∑ t ≤ T ∣ p t − α ∣ for every oracle in O α ( P ) \mathcal{O}_{\alpha}(\mathbb{P}) O α ( P ) .
Upper bound. The population prediction set in (12) is deterministic and measurable. Since the fresh score is independent of the past and F ( q P , s ) = 1 − α F(q_{\mathbb{P},s})=1-\alpha F ( q P , s ) = 1 − α , it belongs to O α ( P ) \mathcal{O}_{\alpha}(\mathbb{P}) O α ( P ) . The ACI set and the population set are thresholds of the same score, at the levels q t q_t q t and q P , s q_{\mathbb{P},s} q P , s . Their errors differ exactly when s t s_t s t lies between the two levels, which has conditional probability ∣ F ( q t ) − F ( q P , s ) ∣ = ∣ p t − α ∣ |F(q_t)-F(q_{\mathbb{P},s})|=|p_t-\alpha| ∣ F ( q t ) − F ( q P , s ) ∣ = ∣ p t − α ∣ given the past. So this oracle attains the lower bound. □
Proof of Lemma F.4. By Lemma F.1 and q P , s ∈ ( 0 , B ) q_{\mathbb{P},s}\in(0,B) q P , s ∈ ( 0 , B ) , we have − η ˉ α − B < Δ t < B + η ˉ ( 1 − α ) -\bar{\eta}\alpha-B<\Delta_t<B+\bar{\eta}(1-\alpha) − η ˉ α − B < Δ t < B + η ˉ ( 1 − α ) , so ∣ Δ t ∣ ≤ B + η ˉ |\Delta_t|\le B+\bar{\eta} ∣ Δ t ∣ ≤ B + η ˉ . The function χ \chi χ is nondecreasing with χ ( 0 ) = 0 \chi(0)=0 χ ( 0 ) = 0 , so χ ( u ) ≥ 0 \chi(u)\ge0 χ ( u ) ≥ 0 for u > 0 u>0 u > 0 and χ ( u ) ≤ 0 \chi(u)\le0 χ ( u ) ≤ 0 for u < 0 u<0 u < 0 . It remains to prove the two bounds on ∣ χ ( u ) ∣ |\chi(u)| ∣ χ ( u ) ∣ .
For the upper bound, the extended distribution function F F F has a density bounded by λ + \lambda_+ λ + on the whole real line, so ∣ χ ( u ) ∣ = ∣ F ( q P , s + u ) − F ( q P , s ) ∣ ≤ λ + ∣ u ∣ |\chi(u)|=|F(q_{\mathbb{P},s}+u)-F(q_{\mathbb{P},s})|\le\lambda_+|u| ∣ χ ( u ) ∣ = ∣ F ( q P , s + u ) − F ( q P , s ) ∣ ≤ λ + ∣ u ∣ for every u u u .
For the lower bound, let ∣ u ∣ ≤ B + η ˉ |u|\le B+\bar{\eta} ∣ u ∣ ≤ B + η ˉ and consider three cases. If q P , s + u ∈ [ 0 , B ] q_{\mathbb{P},s}+u\in[0,B] q P , s + u ∈ [ 0 , B ] , then (56) gives ∣ χ ( u ) ∣ ≥ λ − ∣ u ∣ ≥ λ ∣ u ∣ |\chi(u)|\ge\lambda_-|u|\ge\lambda|u| ∣ χ ( u ) ∣ ≥ λ − ∣ u ∣ ≥ λ ∣ u ∣ . If q P , s + u > B q_{\mathbb{P},s}+u>B q P , s + u > B , then χ ( u ) = 1 − ( 1 − α ) = α \chi(u)=1-(1-\alpha)=\alpha χ ( u ) = 1 − ( 1 − α ) = α , and λ ∣ u ∣ ≤ ν ≤ α \lambda|u|\le\nu\le\alpha λ ∣ u ∣ ≤ ν ≤ α because ∣ u ∣ ≤ B + η ˉ |u|\le B+\bar{\eta} ∣ u ∣ ≤ B + η ˉ . If q P , s + u < 0 q_{\mathbb{P},s}+u<0 q P , s + u < 0 , then χ ( u ) = − ( 1 − α ) \chi(u)=-(1-\alpha) χ ( u ) = − ( 1 − α ) , and λ ∣ u ∣ ≤ ν ≤ 1 − α \lambda|u|\le\nu\le1-\alpha λ ∣ u ∣ ≤ ν ≤ 1 − α . □
Proof of Lemma F.5
The proof has two ingredients. The first is a comparison lemma that turns a one-step inequality for a sequence into a bound on its size. The second applies this lemma to the moments of Δ t \Delta_t Δ t . The comparison is related to classical stochastic-approximation arguments ([13 , 16 ] ). We prove the form needed here for the general step sizes in (55) .
Lemma F.6 (A comparison lemma for recursions). Let ( η t ) (\eta_t) ( η t ) be positive step sizes satisfying (55) , let m ≥ 1 m\ge1 m ≥ 1 be an integer, and let A > 0 A>0 A > 0 and D ≥ 0 D\ge0 D ≥ 0 . Let ( z t ) (z_t) ( z t ) be a nonnegative sequence. Below, o ( η t ) o(\eta_t) o ( η t ) and o ( 1 ) o(1) o ( 1 ) stand for sequences of numbers whose ratio to η t \eta_t η t (resp. whose value) tends to zero as t → ∞ t\to\infty t → ∞ .
(a) If z t + 1 ≤ ( 1 − A η t + o ( η t ) ) z t + ( D + o ( 1 ) ) η t m + 1 z_{t+1}\le(1-A\eta_t+o(\eta_t))z_t+(D+o(1))\eta_t^{m+1} z t + 1 ≤ ( 1 − A η t + o ( η t )) z t + ( D + o ( 1 )) η t m + 1 for all large t t t , then lim sup t → ∞ z t / η t m ≤ D / A \limsup_{t\to\infty}z_t/\eta_t^m\le D/A lim sup t → ∞ z t / η t m ≤ D / A .
(b) If z t + 1 ≥ ( 1 − A η t + o ( η t ) ) z t + ( D + o ( 1 ) ) η t m + 1 z_{t+1}\ge(1-A\eta_t+o(\eta_t))z_t+(D+o(1))\eta_t^{m+1} z t + 1 ≥ ( 1 − A η t + o ( η t )) z t + ( D + o ( 1 )) η t m + 1 for all large t t t , then lim inf t → ∞ z t / η t m ≥ D / A \liminf_{t\to\infty}z_t/\eta_t^m\ge D/A lim inf t → ∞ z t / η t m ≥ D / A .
The level ( D / A ) η t m (D/A)\eta_t^m ( D / A ) η t m is where contraction and added noise balance. The two parts give the corresponding upper and lower comparisons.
Lemma F.7 (Moments of the deviation). Suppose that the step sizes satisfy (55) . There exist constants 0 < c Δ ≤ C Δ < ∞ 0<c_{\Delta}\le C_{\Delta}<\infty 0 < c Δ ≤ C Δ < ∞ and a time t ⋆ ≥ 1 t_{\star}\ge1 t ⋆ ≥ 1 such that, for every t ≥ t ⋆ t\ge t_{\star} t ≥ t ⋆ ,
c Δ η t ≤ E Δ t 2 ≤ C Δ η t , E Δ t 4 ≤ C Δ η t 2 . c_{\Delta}\eta_t\le\mathbb{E}\Delta_t^2\le C_{\Delta}\eta_t,\qquad\mathbb{E}\Delta_t^4\le C_{\Delta}\eta_t^2. c Δ η t ≤ E Δ t 2 ≤ C Δ η t , E Δ t 4 ≤ C Δ η t 2 .
Proof of Lemma F.5. We deduce the size of E ∣ Δ t ∣ \mathbb{E}|\Delta_t| E ∣ Δ t ∣ from the second and the fourth moment in Lemma F.7 . Let t ≥ t ⋆ t\ge t_{\star} t ≥ t ⋆ . For the upper bound, the Cauchy–Schwarz inequality gives
E ∣ Δ t ∣ ≤ ( E Δ t 2 ) 1 / 2 ≤ C Δ η t . \mathbb{E}|\Delta_t|\le(\mathbb{E}\Delta_t^2)^{1/2}\le\sqrt{C_{\Delta}}\sqrt{\eta_t}. E ∣ Δ t ∣ ≤ ( E Δ t 2 ) 1/2 ≤ C Δ η t .
For the lower bound, we need that Δ t \Delta_t Δ t is not concentrated on rare large values, and this is what the fourth moment controls. Hölder’s inequality gives E Δ t 2 ≤ ( E ∣ Δ t ∣ ) 2 / 3 ( E Δ t 4 ) 1 / 3 \mathbb{E}\Delta_t^2 \le(\mathbb{E}|\Delta_t|)^{2/3}(\mathbb{E}\Delta_t^4)^{1/3} E Δ t 2 ≤ ( E ∣ Δ t ∣ ) 2/3 ( E Δ t 4 ) 1/3 , and therefore
E ∣ Δ t ∣ ≥ ( E Δ t 2 ) 3 / 2 ( E Δ t 4 ) 1 / 2 ≥ ( c Δ η t ) 3 / 2 ( C Δ η t 2 ) 1 / 2 = c Δ 3 / 2 C Δ 1 / 2 η t . \mathbb{E}|\Delta_t| \ge\frac{(\mathbb{E}\Delta_t^2)^{3/2}}{(\mathbb{E}\Delta_t^4)^{1/2}} \ge\frac{(c_\Delta\eta_t)^{3/2}}{(C_\Delta\eta_t^2)^{1/2}} = \frac{c_\Delta^{3/2}}{C_\Delta^{1/2}}\sqrt{\eta_t}. E ∣ Δ t ∣ ≥ ( E Δ t 4 ) 1/2 ( E Δ t 2 ) 3/2 ≥ ( C Δ η t 2 ) 1/2 ( c Δ η t ) 3/2 = C Δ 1/2 c Δ 3/2 η t .
This proves the lemma with C 0 = C Δ 1 / 2 C_0=C_\Delta^{1/2} C 0 = C Δ 1/2 and c 0 = c Δ 3 / 2 / C Δ 1 / 2 c_0=c_\Delta^{3/2}/C_\Delta^{1/2} c 0 = c Δ 3/2 / C Δ 1/2 .
Proof of Lemma F.6
Proof. We first divide the sequence by η t m \eta_t^m η t m , and then compare the result with the level at which the two effects balance.
Step 1: normalization. Let Z ~ t = Z t / η t m \widetilde{Z}_t=Z_t/\eta_t^m Z t = Z t / η t m . By (55) ,
η t η t + 1 = 1 + η t ( 1 η t + 1 − 1 η t ) = 1 + o ( η t ) , \frac{\eta_t}{\eta_{t+1}}=1+\eta_t\left(\frac{1}{\eta_{t+1}}-\frac{1}{\eta_t}\right)=1+o(\eta_t), η t + 1 η t = 1 + η t ( η t + 1 1 − η t 1 ) = 1 + o ( η t ) ,
and, since the step sizes are bounded, also ( η t / η t + 1 ) m = 1 + o ( η t ) (\eta_t/\eta_{t+1})^m=1+o(\eta_t) ( η t / η t + 1 ) m = 1 + o ( η t ) . So the change of the normalization from η t m \eta_t^m η t m to η t + 1 m \eta_{t+1}^m η t + 1 m only contributes a factor of this form. Dividing the inequality in (a) by η t + 1 m \eta_{t+1}^m η t + 1 m and multiplying out, we get
Z ~ t + 1 ≤ ( 1 − A η t + o ( η t ) ) Z ~ t + ( D + o ( 1 ) ) η t for all large t . (64) \widetilde{Z}_{t+1}\leq(1-A\eta_t+o(\eta_t))\widetilde{Z}_t+(D+o(1))\eta_t \qquad\text{for all large }t. \tag*{(64)} Z t + 1 ≤ ( 1 − A η t + o ( η t )) Z t + ( D + o ( 1 )) η t for all large t . (64)
Only the deterministic coefficients are expanded here; no bound on Z ~ t \widetilde{Z}_t Z t is assumed. In the same way, the inequality in (b) gives Z ~ t + 1 ≥ ( 1 − A η t + o ( η t ) ) Z ~ t + ( D + o ( 1 ) ) η t \widetilde{Z}_{t+1}\geq(1-A\eta_t+o(\eta_t))\widetilde{Z}_t+(D+o(1))\eta_t Z t + 1 ≥ ( 1 − A η t + o ( η t )) Z t + ( D + o ( 1 )) η t for all large $t.
Step 2: the step sizes are not summable. The signed increments of 1 / η t 1/\eta_t 1/ η t tend to zero, so their Cesàro averages give
1 t η t = 1 t η 1 + 1 t ∑ r < t ( η r + 1 − 1 − η r − 1 ) ⟶ 0. \frac{1}{t\eta_t}=\frac{1}{t\eta_1}+\frac{1}{t}\sum_{r<t}(\eta_{r+1}^{-1}-\eta_r^{-1})\longrightarrow0. t η t 1 = t η 1 1 + t 1 r < t ∑ ( η r + 1 − 1 − η r − 1 ) ⟶ 0.
Thus t η t → ∞ t\eta_t\to\infty t η t → ∞ , and ∑ t η t = ∞ \sum_t\eta_t=\infty ∑ t η t = ∞ .
Step 3: part (a). Fix ε ∈ ( 0 , A ) \varepsilon\in(0,A) ε ∈ ( 0 , A ) . For all large t t t , the two o o o -terms in (64) are at most ε η t \varepsilon\eta_t ε η t and ε \varepsilon ε . Since Z ~ t ≥ 0 \widetilde{Z}_t\geq0 Z t ≥ 0 , this gives, for all large t t t ,
Z ~ t + 1 ≤ ( 1 − ( A − ε ) η t ) Z ~ t + ( D + ε ) η t . \widetilde{Z}_{t+1}\leq(1-(A-\varepsilon)\eta_t)\widetilde{Z}_t+(D+\varepsilon)\eta_t. Z t + 1 ≤ ( 1 − ( A − ε ) η t ) Z t + ( D + ε ) η t .
Let L + = ( D + ε ) / ( A − ε ) L^+=(D+\varepsilon)/(A-\varepsilon) L + = ( D + ε ) / ( A − ε ) be the level at which the two terms balance. Subtracting L + L^+ L + from both sides gives Z ~ t + 1 − L + ≤ ( 1 − ( A − ε ) η t ) ( Z ~ t − L + ) \widetilde{Z}_{t+1}-L^+\leq(1-(A-\varepsilon)\eta_t)(\widetilde{Z}_t-L^+) Z t + 1 − L + ≤ ( 1 − ( A − ε ) η t ) ( Z t − L + ) . The factor lies in ( 0 , 1 ) (0,1) ( 0 , 1 ) for large t t t , so the positive part satisfies
( Z ~ t + 1 − L + ) + ≤ ( 1 − ( A − ε ) η t ) ( Z ~ t − L + ) + . (\widetilde{Z}_{t+1}-L^+)^+\leq(1-(A-\varepsilon)\eta_t)(\widetilde{Z}_t-L^+)^+. ( Z t + 1 − L + ) + ≤ ( 1 − ( A − ε ) η t ) ( Z t − L + ) + .
Iterating from a large time t 1 t_1 t 1 ,
( Z ~ T − L + ) + ≤ ( Z ~ t 1 − L + ) + ∏ t = t 1 T − 1 ( 1 − ( A − ε ) η t ) ⟶ 0 as T → ∞ , (\widetilde{Z}_T-L^+)^+\leq(\widetilde{Z}_{t_1}-L^+)^+\prod_{t=t_1}^{T-1}(1-(A-\varepsilon)\eta_t)\longrightarrow0 \qquad\text{as }T\to\infty, ( Z T − L + ) + ≤ ( Z t 1 − L + ) + t = t 1 ∏ T − 1 ( 1 − ( A − ε ) η t ) ⟶ 0 as T → ∞ ,
because ∑ t η t = ∞ \sum_t\eta_t=\infty ∑ t η t = ∞ . Hence lim sup t Z ~ t ≤ L + \limsup_t\widetilde{Z}_t\leq L^+ lim sup t Z t ≤ L + , and letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 gives lim sup t Z ~ t ≤ D / A \limsup_t\widetilde{Z}_t\leq D/A lim sup t Z t ≤ D / A . Step 4: part (b). D = 0 D=0 D = 0 directly implies z ~ t ≥ 0 \tilde{z}_t \ge0 z ~ t ≥ 0 . Otherwise fix ε ∈ ( 0 , D ) \varepsilon\in(0,D) ε ∈ ( 0 , D ) and let L − = ( D − ε ) / ( A + ε ) L^-=(D-\varepsilon)/(A+\varepsilon) L − = ( D − ε ) / ( A + ε ) . For all large t t t , the two o o o -terms are at least − ε η t -\varepsilon\eta_t − ε η t and − ε -\varepsilon − ε , so the lower inequality gives z ~ t + 1 ≥ ( 1 − ( A + ε ) η t ) z ~ t + ( D − ε ) η t \tilde{z}_{t+1} \ge(1-(A+\varepsilon)\eta_t)\tilde{z}_t+(D-\varepsilon)\eta_t z ~ t + 1 ≥ ( 1 − ( A + ε ) η t ) z ~ t + ( D − ε ) η t . As in Step 3, this gives ( L − − z ~ t + 1 ) + ≤ ( 1 − ( A + ε ) η t ) ( L − − z ~ t ) + (L^- -\tilde{z}_{t+1})_+ \le(1-(A+\varepsilon)\eta_t)(L^- -\tilde{z}_t)_+ ( L − − z ~ t + 1 ) + ≤ ( 1 − ( A + ε ) η t ) ( L − − z ~ t ) + for all large t t t . Hence ( L − − z ~ T ) + → 0 (L^- -\tilde{z}_T)_+ \to0 ( L − − z ~ T ) + → 0 , so lim inf t z ~ t ≥ L − \liminf_t \tilde{z}_t \ge L^- lim inf t z ~ t ≥ L − , and letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 gives lim inf t z ~ t ≥ D / A \liminf_t \tilde{z}_t \ge D/A lim inf t z ~ t ≥ D / A . □ \square □
Proof of Lemma F.7
Proof. The idea is to raise the recursion (59) to the second and the fourth power and to take expectations. The noise has mean zero given the past, so the terms that are linear in the noise vanish. What remains is a one-step inequality for each moment, to which Lemma F.6 applies.
We write Δ t + 1 / 2 = Δ t − η t χ ( Δ t ) \Delta_{t+1/2}=\Delta_t-\eta_t\chi(\Delta_t) Δ t + 1/2 = Δ t − η t χ ( Δ t ) for the deviation, so that Δ t + 1 = Δ t + 1 / 2 + η t ξ t \Delta_{t+1}=\Delta_{t+1/2}+\eta_t\xi_t Δ t + 1 = Δ t + 1/2 + η t ξ t . The variable Δ t + 1 / 2 \Delta_{t+1/2} Δ t + 1/2 is determined by the past. The range bound and η ˉ < ∞ \bar{\eta}<\infty η ˉ < ∞ make Δ t \Delta_t Δ t , Δ t + 1 / 2 \Delta_{t+1/2} Δ t + 1/2 , and all the moments below bounded.
Step 1: contraction. By Lemma F.4 , λ − Δ t 2 ≤ Δ t χ ( Δ t ) ≤ λ + Δ t 2 \lambda_-\Delta_t^2 \le\Delta_t\chi(\Delta_t) \le\lambda_+\Delta_t^2 λ − Δ t 2 ≤ Δ t χ ( Δ t ) ≤ λ + Δ t 2 and χ ( Δ t ) 2 ≤ λ + 2 Δ t 2 \chi(\Delta_t)^2 \le\lambda_+^2\Delta_t^2 χ ( Δ t ) 2 ≤ λ + 2 Δ t 2 . Expanding Δ t + 1 / 2 2 = Δ t 2 − 2 η t Δ t χ ( Δ t ) + η t 2 χ ( Δ t ) 2 \Delta_{t+1/2}^2=\Delta_t^2-2\eta_t\Delta_t\chi(\Delta_t)+\eta_t^2\chi(\Delta_t)^2 Δ t + 1/2 2 = Δ t 2 − 2 η t Δ t χ ( Δ t ) + η t 2 χ ( Δ t ) 2 therefore gives
( 1 − 2 λ + η t ) Δ t 2 ≤ Δ t + 1 / 2 2 ≤ ( 1 − 2 λ − η t + λ + 2 η t 2 ) Δ t 2 . (65) (1-2\lambda_+\eta_t)\Delta_t^2 \le\Delta_{t+1/2}^2 \le(1-2\lambda_-\eta_t+\lambda_+^2\eta_t^2)\Delta_t^2. \tag*{(65)} ( 1 − 2 λ + η t ) Δ t 2 ≤ Δ t + 1/2 2 ≤ ( 1 − 2 λ − η t + λ + 2 η t 2 ) Δ t 2 . (65)
Step 2: the second moment, upper bound. Squaring Δ t + 1 = Δ t + 1 / 2 + η t ξ t \Delta_{t+1}=\Delta_{t+1/2}+\eta_t\xi_t Δ t + 1 = Δ t + 1/2 + η t ξ t and using (60) ,
E [ Δ t + 1 2 ∣ G t − 1 ] = Δ t + 1 / 2 2 + η t 2 p t ( 1 − p t ) . (66) \mathbb{E}\left[\Delta_{t+1}^2\mid\mathcal{G}_{t-1}\right]=\Delta_{t+1/2}^2+\eta_t^2p_t(1-p_t). \tag*{(66)} E [ Δ t + 1 2 ∣ G t − 1 ] = Δ t + 1/2 2 + η t 2 p t ( 1 − p t ) . (66)
Taking expectations and using the upper bound in (65) and p t ( 1 − p t ) ≤ 1 / 4 p_t(1-p_t)\le1/4 p t ( 1 − p t ) ≤ 1/4 ,
E Δ t + 1 2 ≤ ( 1 − 2 λ − η t + λ + 2 η t 2 ) E Δ t 2 + 1 4 η t 2 . \mathbb{E}\Delta_{t+1}^2\le(1-2\lambda_-\eta_t+\lambda_+^2\eta_t^2)\mathbb{E}\Delta_t^2+\frac{1}{4}\eta_t^2. E Δ t + 1 2 ≤ ( 1 − 2 λ − η t + λ + 2 η t 2 ) E Δ t 2 + 4 1 η t 2 .
Lemma F.6 (a) with z t = E Δ t 2 z_t=\mathbb{E}\Delta_t^2 z t = E Δ t 2 , m = 1 m=1 m = 1 , A = 2 λ − A=2\lambda_- A = 2 λ − , and D = 1 / 4 D=1/4 D = 1/4 gives lim sup t E Δ t 2 / η t ≤ 1 / ( 8 λ − ) . \limsup_t\mathbb{E}\Delta_t^2/\eta_t\le1/(8\lambda_-). lim sup t E Δ t 2 / η t ≤ 1/ ( 8 λ − ) . In particular E Δ t 2 → 0 \mathbb{E}\Delta_t^2\to0 E Δ t 2 → 0 .
Step 3: the second moment, lower bound. For p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] we have ∣ p ( 1 − p ) − α ( 1 − α ) ∣ = ∣ p − α ∣ ∣ 1 − p − α ∣ ≤ ∣ p − α ∣ |p(1-p)-\alpha(1-\alpha)|=|p-\alpha||1-p-\alpha|\le|p-\alpha| ∣ p ( 1 − p ) − α ( 1 − α ) ∣ = ∣ p − α ∣∣1 − p − α ∣ ≤ ∣ p − α ∣ , and ∣ p t − α ∣ = ∣ χ ( Δ t ) ∣ ≤ λ + ∣ Δ t ∣ |p_t-\alpha|=|\chi(\Delta_t)|\le\lambda_+|\Delta_t| ∣ p t − α ∣ = ∣ χ ( Δ t ) ∣ ≤ λ + ∣ Δ t ∣ . Hence
∣ E [ p t ( 1 − p t ) ] − σ 2 ∣ ≤ λ + E ∣ Δ t ∣ ≤ λ + ( E Δ t 2 ) 1 / 2 ⟶ 0 \left|\mathbb{E}[p_t(1-p_t)]-\sigma^2\right|\le\lambda_+\mathbb{E}|\Delta_t|\le\lambda_+(\mathbb{E}\Delta_t^2)^{1/2}\longrightarrow0 E [ p t ( 1 − p t )] − σ 2 ≤ λ + E ∣ Δ t ∣ ≤ λ + ( E Δ t 2 ) 1/2 ⟶ 0
by Step 2. Taking expectations in (66) and using the lower bound in (65) ,
E Δ t + 1 2 ≥ ( 1 − 2 λ + η t ) E Δ t 2 + ( σ 2 + o ( 1 ) ) η t 2 . \mathbb{E}\Delta_{t+1}^2\ge(1-2\lambda_+\eta_t)\mathbb{E}\Delta_t^2+(\sigma^2+o(1))\eta_t^2. E Δ t + 1 2 ≥ ( 1 − 2 λ + η t ) E Δ t 2 + ( σ 2 + o ( 1 )) η t 2 .
Lemma F.6 (b) with z t = E Δ t 2 z_t=\mathbb{E}\Delta_t^2 z t = E Δ t 2 , m = 1 m=1 m = 1 , A = 2 λ + A=2\lambda_+ A = 2 λ + , and D = σ 2 D=\sigma^2 D = σ 2 gives lim inf t E Δ t 2 / η t ≥ σ 2 / ( 2 λ + ) > 0 \liminf_t\mathbb{E}\Delta_t^2/\eta_t\ge\sigma^2/(2\lambda_+)>0 lim inf t E Δ t 2 / η t ≥ σ 2 / ( 2 λ + ) > 0 . Steps 2 and 3 prove the two bounds on E Δ t 2 \mathbb{E}\Delta_t^2 E Δ t 2 .
Step 4: the fourth moment. We expand ( Δ t + 1 / 2 + η t ξ t ) 4 (\Delta_{t+1/2}+\eta_t\xi_t)^4 ( Δ t + 1/2 + η t ξ t ) 4 and take the conditional expectation given the past. The term that is linear in ξ t \xi_t ξ t vanishes. For the other terms we use E [ ∣ ξ t ∣ j ∣ G t − 1 ] ≤ E [ ξ t 2 ∣ G t − 1 ] ≤ 1 / 4 \mathbb{E}[|\xi_t|^j\mid\mathcal{G}_{t-1}]\le\mathbb{E}[\xi_t^2\mid\mathcal{G}_{t-1}]\le1/4 E [ ∣ ξ t ∣ j ∣ G t − 1 ] ≤ E [ ξ t 2 ∣ G t − 1 ] ≤ 1/4 for j ≥ 2 j\ge2 j ≥ 2 , which holds because ∣ ξ t ∣ ≤ 1 |\xi_t|\le1 ∣ ξ t ∣ ≤ 1 . This gives
E [ Δ t + 1 4 ∣ G t − 1 ] ≤ Δ t + 1 / 2 4 + 3 2 η t 2 Δ t + 1 / 2 2 + η t 3 ∣ Δ t + 1 / 2 ∣ + 1 4 η t 4 . \mathbb{E}[\Delta_{t+1}^4\mid\mathcal{G}_{t-1}]\le\Delta_{t+1/2}^4+\frac{3}{2}\eta_t^2\Delta_{t+1/2}^2+\eta_t^3|\Delta_{t+1/2}|+\frac{1}{4}\eta_t^4. E [ Δ t + 1 4 ∣ G t − 1 ] ≤ Δ t + 1/2 4 + 2 3 η t 2 Δ t + 1/2 2 + η t 3 ∣ Δ t + 1/2 ∣ + 4 1 η t 4 .
Squaring the upper bound in (65) gives Δ t + 1 / 2 4 ≤ ( 1 − 4 λ η t + C η t 2 ) Δ t 4 \Delta_{t+1/2}^4\le(1-4\lambda\eta_t+C\eta_t^2)\Delta_t^4 Δ t + 1/2 4 ≤ ( 1 − 4 λ η t + C η t 2 ) Δ t 4 . Moreover, E Δ t + 1 / 2 2 ≤ C η t \mathbb{E}\Delta_{t+1/2}^2\le C\eta_t E Δ t + 1/2 2 ≤ C η t for all large t t t by Step 2, and ∣ Δ t + 1 / 2 ∣ |\Delta_{t+1/2}| ∣ Δ t + 1/2 ∣ is bounded. So the last three terms have expectation at most C η t 3 C\eta_t^3 C η t 3 , and for all large t t t ,
E Δ t + 1 4 ≤ ( 1 − 4 λ η t + C η t 2 ) E Δ t 4 + C η t 3 . \mathbb{E}\Delta_{t+1}^4\le(1-4\lambda\eta_t+C\eta_t^2)\mathbb{E}\Delta_t^4+C\eta_t^3. E Δ t + 1 4 ≤ ( 1 − 4 λ η t + C η t 2 ) E Δ t 4 + C η t 3 .
Lemma F.6(a) with z t = E Δ t 4 z_t=\mathbb{E}\Delta_t^4 z t = E Δ t 4 , m = 2 m=2 m = 2 , A = 4 λ A=4\lambda A = 4 λ , and D = C D=C D = C gives lim sup t E Δ t 4 / η t 2 < ∞ \limsup_t\mathbb{E}\Delta_t^4/\eta_t^2<\infty lim sup t E Δ t 4 / η t 2 < ∞ .
The three limits in Steps 2–4 give the lemma, with suitable constants c Δ c_\Delta c Δ and C Δ C_\Delta C Δ and a suitable time t ⋆ t_\star t ⋆ . □