Introduction
The length of a training run is often not fixed in advance. Early stopping and checkpoint selection depend on the observed trajectory (Aolaritei and Jordan, [2 ] ), large-scale training increasingly avoids committing to a duration (Hägele et al., [22 ] ), and schedule-free methods are designed so that no stopping time has to be specified (Defazio et al., [13 ] ). The model kept is the state of the run at the chosen time rather than an average of iterates. The stochastic gradients are often heavy-tailed ([59 , 72 ] ), and gradient clipping (Pascanu et al., [51 ] ) is a standard remedy, used routinely in training large language models (Touvron et al., [64 ] ). This paper asks what an unknown stopping time costs: how fast can the last iterate of clipped stochastic gradient descent (SGD; Robbins and Monro [54 ] ) converge with high probability when the time at which it is used is not fixed in advance?
Fixed-time guarantees do not answer this question. A bound that holds with probability 1 − δ 1-\delta 1 − δ at each fixed time may fail at a time chosen from the observed trajectory, just as A/B tests that are monitored continuously with methods assuming a fixed sample size have inflated Type I error (Howard et al., [24 ] ). A guarantee holds at every data-dependent stopping time exactly when it holds on one event, of probability at least 1 − δ 1-\delta 1 − δ , at all times simultaneously (§ 2 ). Under sub-Gaussian noise, passing to such time-uniform guarantees costs only logarithmic factors around the exponent 1 / 2 1/2 1/2 ((Li et al., 2026)).
Under heavy-tailed noise the price is polynomial, and we determine it: for noise with a bounded central p p p th moment, 1 < p ≤ 2 1 < p \le2 1 < p ≤ 2 , clipped SGD attains the last-iterate errors
O ( T − α p ) with a known horizon T , O ~ ( t − β p ) at all times t simultaneously , \begin{aligned}
O(T^{-\alpha_p}) &\quad\text{with a known horizon } T,\\
\widetilde{O}(t^{-\beta_p}) &\quad\text{at all times } t \text{ simultaneously},
\end{aligned} O ( T − α p ) O ( t − β p ) with a known horizon T , at all times t simultaneously ,
where α p = ( p − 1 ) / p \alpha_p = (p - 1)/p α p = ( p − 1 ) / p , β p = 2 ( p − 1 ) / ( 3 p − 1 ) \beta_p = 2(p - 1)/(3p - 1) β p = 2 ( p − 1 ) / ( 3 p − 1 ) , and O ~ \widetilde{O} O hides logarithmic factors; under finite variance, the exponents are 1 / 2 1/2 1/2 and 2 / 5 2/5 2/5 . The known-horizon rate is due to Liu [36 ] and Jiang et al. [27 ] ; the time-uniform rate is our main result. Both exponents are optimal, α p \alpha_p α p among all algorithms that query stochastic gradients and β p \beta_p β p among all rules that query their current iterate and step along the resulting stochastic gradient. For fixed δ ≤ 1 / 8 \delta\le1/8 δ ≤ 1/8 , every algorithm making T T T stochastic gradient queries has error Ω ( T − α p ) \Omega(T^{-\alpha_p}) Ω ( T − α p ) with probability at least 2 δ 2\delta 2 δ on some instance (Jiang et al. [27 ] , Proposition 1), and we prove that no such rule attains O ~ ( t − r ) \widetilde{O}(t^{-r}) O ( t − r ) at all times for any r > β p r > \beta_p r > β p , whatever its step sizes and clipping thresholds. The best previous time-uniform rate, O ~ ( t − 2 ( p − 1 ) / ( 3 p ) ) \widetilde{O}(t^{-2(p-1)/(3p)}) O ( t − 2 ( p − 1 ) / ( 3 p ) ) or O ~ ( t − 1 / 3 ) \widetilde{O}(t^{-1/3}) O ( t − 1/3 ) at p = 2 p = 2 p = 2 , is due to Chezhegov et al. [8 ] , who suggest that the gap to the optimal rate may be an artifact of the analysis; our results show that, for such rules, part of this gap is inherent. We also find that where gradients are queried matters more than how they are scaled: querying them at the running average of the iterates attains O ~ ( t − α p ) \widetilde{O}(t^{-\alpha_p}) O ( t − α p ) at all times.
With clipping, high-probability guarantees can depend only logarithmically on the confidence level ([42 , 21 , 10 , 56 , 47 ] ), as for robust mean estimators ([5 , 14 , 40 ] ), whereas unclipped SGD with predefined step sizes attains the optimal rate in expectation ([18 ] ) but can require polynomial dependence on 1 / δ 1/\delta 1/ δ ([56 , 18 ] ); most of these guarantees concern an averaged or auxiliary output and need not apply to the last iterate. Formally, we consider a convex L L L -smooth objective f : R d → R f : \mathbb{R}^d \to\mathbb{R} f : R d → R with a minimizer x ⋆ x^\star x ⋆ satisfying ∥ x 1 − x ⋆ ∥ ≤ R \lVert x_1 - x^\star\rVert\le R ∥ x 1 − x ⋆ ∥ ≤ R , and stochastic gradients g t g_t g t that are conditionally unbiased with
E [ ∥ g t − ∇ f ( x t ) ∥ p ∣ F t − 1 ] ≤ σ p , 1 < p ≤ 2. \mathbb{E}\left[\lVert g_t - \nabla f(x_t)\rVert^p \mid\mathcal{F}_{t-1}\right] \le\sigma^p,\qquad1 < p \le2. E [ ∥ g t − ∇ f ( x t ) ∥ p ∣ F t − 1 ] ≤ σ p , 1 < p ≤ 2.
Clipped SGD performs the updates
x t + 1 = x t − η t clip ( g t , λ t ) , clip ( g , λ ) = min { 1 , λ / ∥ g ∥ } g , (1) \begin{aligned}
x_{t+1} &= x_t - \eta_t \operatorname{clip}(g_t,\lambda_t),\\
\operatorname{clip}(g,\lambda) &= \min\{1,\lambda/\lVert g\rVert\}g, \tag*{(1)}
\end{aligned} x t + 1 clip ( g , λ ) = x t − η t clip ( g t , λ t ) , = min { 1 , λ / ∥ g ∥} g , (1)
where η t \eta_t η t is the step size and λ t \lambda_t λ t the clipping threshold. For an averaged output of clipped stochastic mirror descent, Nguyen et al. [47 ] Theorem 4.1`) proved that T T T oracle calls suffice to reach, with probability at least 1 − δ 1-\delta 1 − δ , the scale
σ R ( log ( 1 / δ ) T ) ( p − 1 ) / p (2) \sigma R\left(\frac{\log(1/\delta)}{T}\right)^{(p-1)/p} \tag*{(2)} σ R ( T log ( 1/ δ ) ) ( p − 1 ) / p (2)
plus a deterministic term of order L R 2 log ( 1 / δ ) / T LR^2\log(1/\delta)/T L R 2 log ( 1/ δ ) / T . For δ ≤ 1 / 8 \delta\le1/8 δ ≤ 1/8 and T ≥ log ( 1 / δ ) T \ge\log(1/\delta) T ≥ log ( 1/ δ ) , the lower bound of Jiang et al. [27 ] Proposition 1) shows that no algorithm using $T$ stochastic gradients improves the minimum of $LR^2$ and the scale {xref}(2)` by more than a constant factor.
For the last iterate, the horizon-free rate T − 2 ( p − 1 ) / ( 3 p ) T^{-2(p-1)/(3p)} T − 2 ( p − 1 ) / ( 3 p ) of Chezhegov et al. [8 ] Theorem 1 and {xrefext}Corollary 1) holds up to logarithms with a schedule that takes δ \delta δ as input, and their experiments led them to conjecture that an improved schedule could attain the optimal rate (Chezhegov et al. [8 ] Section 5)). With a known horizon the conjecture holds: linearly decaying step sizes attain {xref}(2)` at the last iterate, as shown by Liu [36 ] and Jiang et al. [27 ] (Theorem 1 below). Liu [36 ] leaves the case of an unknown horizon open. This is the case we study, and we find that there the conjecture fails for rules that query their current iterate and step along its stochastic gradient, both for time-uniform guarantees and for fixed-time guarantees with polylogarithmic confidence dependence (Theorems 4 and 6 ).
Main Results
Table 1 summarizes our results and compares them with previous and concurrent work; α p \alpha_p α p is the statistical exponent of (2) . We write error bounds as O ~ ( t − r ) \tilde{O}(t^{-r}) O ~ ( t − r ) , where O ~ \tilde{O} O ~ hides constants and factors polylogarithmic in t / δ t/\delta t / δ . An upper bound shows that the exponent r r r is attained; a lower bound with exponent r r r shows that for every r ′ > r r' > r r ′ > r , any claimed bound O ~ ( t − r ′ ) \tilde{O}(t^{-r'}) O ~ ( t − r ′ ) fails on some instance with probability more than δ \delta δ , rather than a pointwise bound Ω ( t − r ) \Omega(t^{-r}) Ω ( t − r ) .
Our main result is the optimal time-uniform rate (§ 4 ). We give a deterministic schedule that uses neither the horizon nor the confidence level and prove that clipped SGD with this schedule attains error O ~ ( t − β p ) \tilde{O}(t^{-\beta_p}) O ~ ( t − β p ) at all times simultaneously (Theorem 2). Because one trajectory serves every confidence level, the rate also holds almost surely. We then prove that β p \beta_p β p cannot be improved: no gradient-only rule (Definition 3 ) attains a time-uniform bound O ~ ( t − r ) \tilde{O}(t^{-r}) O ~ ( t − r ) with r > β p r > \beta_p r > β p , even if its step sizes and clipping thresholds respond adaptively and randomly to the history and the current gradient (Theorem 4 ). At p = 2 p = 2 p = 2 , Anonymous [1 ] prove, concurrently, that deterministic unclipped step sizes cannot attain almost sure rates O ~ ( t − r ) \tilde{O}(t^{-r}) O ~ ( t − r ) for any r > 1 / 3 r > 1/3 r > 1/3 , and in Remark 16 we show that their construction also excludes such time-uniform rates on our class. With our results, this shows that deterministic unclipped schedules are limited to the exponent 1 / 3 1/3 1/3 , whereas our clipped schedule attains 2 / 5 2/5 2/5 .
The lower bound raises the question whether a method outside this class can recover α p \alpha_p α p without a known horizon (§ 6 ). It can: if gradients are queried at the running average of the iterates, the error is O ~ ( t − α p ) \tilde{O}(t^{-\alpha_p}) O ~ ( t − α p ) uniformly over time (Theorem 9 , with a schedule that uses δ \delta δ ). The accelerated method of Nguyen et al. [47 ] also attains α p \alpha_p α p without a known horizon; their theorem is stated at each fixed time, and its proof gives the time-uniform form (Appendix § 21 ). The barrier therefore depends on where gradients are queried rather than on how they are scaled. Written as heavy-ball momentum (Polyak, [52 ] ), this update has 1 − β t 1-\beta_t 1 − β t of order 1 / t 1/t 1/ t , so its memory grows. We show that memory that does not grow is not enough. With zero initial velocity, polynomially bounded step sizes, and geometrically decaying memory, heavy-ball momentum attains no bound O ~ ( t − r ) \tilde{O}(t^{-r}) O ~ ( t − r ) with r > β p r > \beta_p r > β p , even in one dimension. Under polynomial forgetting 1 − β t ≥ ρ ( 1 + t ) − a 1-\beta_t \ge\rho(1+t)^{-a} 1 − β t ≥ ρ ( 1 + t ) − a , we prove the barriers ( 1 + a ) β p (1+a)\beta_p ( 1 + a ) β p in one dimension (Theorem 7) and max { β p , a } \max\{\beta_p,a\} max { β p , a } under constants shared across dimensions (Theorem 8 ).
The price also depends on what the guarantee must cover: at a single fixed time, we show that it moves into the confidence factor (§ 5 ). Our horizon-free schedule attains O ~ ( δ − ( p − 1 ) / p t − α p ) \tilde{O}(\delta^{-(p-1)/p}t^{-\alpha_p}) O ~ ( δ − ( p − 1 ) / p t − α p ) at each fixed time t t t , or O ~ ( δ − 1 t − α p ) \tilde{O}(\delta^{-1}t^{-\alpha_p}) O ~ ( δ − 1 t − α p ) without a confidence input (Theorem 5 ). For gradient-only rules and r ∈ ( β p , α p ] r \in(\beta_p,\alpha_p] r ∈ ( β p , α p ] , we prove that a fixed-time bound O ~ ( δ − c t − r ) \tilde{O}(\delta^{-c}t^{-r}) O ~ ( δ − c t − r ) that holds for every δ \delta δ with constants independent of δ \delta δ requires c ≥ r − β p c \ge r-\beta_p c ≥ r − β p , whereas c = ( 3 p − 1 ) ( r − β p ) / ( p − 1 ) c=(3p-1)(r-\beta_p)/(p-1) c = ( 3 p − 1 ) ( r − β p ) / ( p − 1 ) suffices (Theorems 5 and 6 ). With polylogarithmic dependence on 1 / δ 1/\delta 1/ δ , the exponent is again limited to β p \beta_p β p . Our lower bounds allow adaptive, randomized scalar responses to the history and the current gradient, while our upper bounds use deterministic schedules.
What the Results Mean
We draw three lessons from these results.
Table 1. Best last-iterate error of clipped SGD under finite variance, up to constants and logarithmic factors. Shaded: new in this paper; the arrow starts from the previous rate of Chezhegov et al. [8 ] , and the known-horizon rate is due to Liu [36 ] and Jiang et al. [27 ] . Down the first column, knowing less about when the run stops costs a polynomial factor; the second column shows that querying gradients at the running average removes this cost. The rates t − 2 / 5 t^{-2/5} t − 2/5 are optimal for every rule that queries its current iterate, with any step sizes and thresholds, and also limit heavy-ball momentum with a fixed coefficient and polynomially bounded step sizes (Theorems 7 and 8 ). For 1 < p ≤ 2 1 < p \le2 1 < p ≤ 2 , replace 1 / 2 1/2 1/2 by α p \alpha_p α p , 2 / 5 2/5 2/5 by β p \beta_p β p , and δ − 1 / 2 \delta^{-1/2} δ − 1/2 by δ − α p \delta^{-\alpha_p} δ − α p .
Under heavy-tailed noise, a guarantee for clipped SGD that covers early stopping or checkpoint selection has a polynomial price, and tuning cannot remove it. Our lower bound covers every rule that queries its current iterate and moves along the resulting stochastic gradient, with step sizes and thresholds that may adapt to all observed gradients. The reason is a counting argument (Proposition 17 ). On our hard instances the informative gradient observations are rare, and on each of them the iterate may move only a limited distance, since a longer move would violate the error bound on one of the instances that produce the same observations. Rare observations and limited moves cannot support any exponent above β p \beta_p β p .
What does help is to change where gradients are evaluated. If they are evaluated at the running average of the iterates and the average is kept as the model, the polynomial loss in the exponent disappears: the error is O ~ ( t − α p ) \widetilde{O}(t^{-\alpha_p}) O ( t − α p ) at all times (Theorem 9 ). This connects our analysis to schedule-free SGD (Defazio et al. [13 ] ), which evaluates gradients between this average and a base sequence; when it evaluates them at the average, its update with clipped gradients has the form (20) , with decreasing instead of constant step sizes. In overparameterized linear regression, Meterez et al. [41 ] show that horizon-free, polynomially decaying step sizes combined with weight averaging attain the minimax exponent of SGD in expectation under source and capacity conditions, and in language-model pretraining they find such schedules with averaging comparable to a tuned cosine schedule. Momentum helps in the same way only if its memory grows. With 1 − β t 1-\beta_t 1 − β t of order 1 / t 1/t 1/ t , the heavy-ball method is this averaging update, whereas geometrically decaying memory, as with a fixed coefficient, keeps the exponent β p \beta_p β p when the step sizes are polynomially bounded (Theorem 7).
For theory, our results show that under heavy-tailed noise, time-uniform analyses of gradient-only rules cannot match known-horizon rates up to logarithmic factors. At a single fixed time the gap moves into the confidence factor: O ~ ( t − α p ) \widetilde{O}(t^{-\alpha_p}) O ( t − α p ) is attainable there only with a factor polynomial in 1 / δ 1/\delta 1/ δ (Theorems 5 and 6 ). Two of our tools may be useful beyond this paper: a last-iterate potential whose weights stay bounded without a horizon, so that one concentration event covers all times (Lemma 11), and the counting argument above, which applies to every such rule. Appendix § 12 lists open problems, including adaptation to unknown problem parameters, lower bounds for more general updates, and the optimal confidence factor at a fixed time.
Techniques and Organization
Our upper bounds for clipped SGD rest on one potential (Lemma 11 ), which combines a recursive average of past objective gaps, weighted by tail sums of the remaining step sizes, with the distance from the last iterate to a matching average of the iterates; the weights follow the comparators of Zamani and Glineur [69 ] and Liu and Zhou [38 ] . For a known horizon, the weights end with full mass on the final iterate, so the potential bounds the last iterate directly; this is the case behind Theorem 1 (Jiang et al. [27 ] ). Without a known horizon we add a constant to the tail sums. The weights then stay bounded, smoothness converts the potential into a last-iterate bound, and the concentration events for all deterministic horizons can be intersected into one event. Each event comes from one stopped Freedman inequality for the whole trajectory (Lemma 15), without the induction and union bound over the steps that Nguyen et al. [47 ] identify as the source of log T \log T log T factors in earlier analyses. For fixed-time guarantees at exponents above β p \beta_p β p , we truncate the late clipping errors at levels set by the analysis horizon and charge the probability of truncation to the confidence factor. Our lower bounds couple translated objectives through rare gradient observations and bound the progress that can be made without violating the envelope of any objective in a fixed translated family. § 3 –§ 5 develop these arguments, § 6 treats momentum and averaging. Appendix § 10 discusses related work, Appendix § 11 illustrates the separation numerically at p = 2 p = 2 p = 2 , and the remaining appendices contain the proofs. Theorems 2, 4 , and 8 are also formalized in Lean 4, together with a proof of Theorem 1 (§ 7 ).
Problem Setting
∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ and ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ denote the Euclidean norm and inner product; logarithms are natural.
Assumption 1 (Objective). The function f : R d → R f : \mathbb{R}^{d} \to\mathbb{R} f : R d → R is differentiable and convex, and
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ for all x , y ∈ R d . \lVert\nabla f(x) - \nabla f(y)\rVert\le L\lVert x-y\rVert\quad\text{for all } x,y \in\mathbb{R}^{d}. ∥ ∇ f ( x ) − ∇ f ( y )∥ ≤ L ∥ x − y ∥ for all x , y ∈ R d . There is a minimizer x ⋆ x^{\star} x ⋆ , with f ⋆ = f ( x ⋆ ) f^{\star} = f(x^{\star}) f ⋆ = f ( x ⋆ ) , and a known bound ∥ x 1 − x ⋆ ∥ ≤ R \lVert x_{1} - x^{\star}\rVert\le R ∥ x 1 − x ⋆ ∥ ≤ R , where L , R > 0 L, R > 0 L , R > 0 .
Assumption 2 (Oracle). Let F t − 1 \mathcal{F}_{t-1} F t − 1 contain the initial state, any independent algorithmic randomness, and all observations up to time t − 1 t-1 t − 1 , and write E t − 1 [ ⋅ ] = E [ ⋅ ∣ F t − 1 ] \mathbb{E}_{t-1}[\cdot] = \mathbb{E}[\cdot\mid\mathcal{F}_{t-1}] E t − 1 [ ⋅ ] = E [ ⋅ ∣ F t − 1 ] . The query x t x_t x t is F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable, and the oracle returns one fresh observation g t g_t g t with, for some σ ≥ 0 \sigma\ge0 σ ≥ 0 ,
E t − 1 [ g t ] = ∇ f ( x t ) , \mathbb{E}_{t-1}[g_t] = \nabla f(x_t), E t − 1 [ g t ] = ∇ f ( x t ) , E t − 1 [ ∥ g t − ∇ f ( x t ) ∥ p ] ≤ σ p , 1 < p ≤ 2. \mathbb{E}_{t-1}\left[\lVert g_t - \nabla f(x_t)\rVert^{p}\right] \le\sigma^{p}, \qquad1 < p \le2. E t − 1 [ ∥ g t − ∇ f ( x t ) ∥ p ] ≤ σ p , 1 < p ≤ 2. Assumption 2 covers i.i.d. samples from a fixed oracle with bounds uniform in x x x , as well as conditionally unbiased martingale difference noise. Its bound on the central p p p th moment allows asymmetric noise and infinite variance for p < 2 p < 2 p < 2 , without a uniform bound on E t − 1 ∥ g t ∥ p \mathbb{E}_{t-1}\lVert g_t\rVert^{p} E t − 1 ∥ g t ∥ p . Sample losses need not be smooth or convex. The schedules use L , R , σ , p L, R, \sigma, p L , R , σ , p and, when specified, a confidence level δ \delta δ , as in prior analyses ([56 , 47 ] (Chezhg... et al. 2026)). The time-uniform schedule in § 4.1 does not use δ \delta δ .
Table 1.
We write
clip ( g , λ ) = { min { 1 , λ / ∥ g ∥ } g , g ≠ 0 , 0 , g = 0 , \operatorname{clip}(g,\lambda)=
\begin{cases}
\min\{1,\lambda/\lVert g\rVert\}g, & g\ne0,\\
0, & g=0,
\end{cases} clip ( g , λ ) = { min { 1 , λ / ∥ g ∥} g , 0 , g = 0 , g = 0 ,
for Euclidean clipping, that is, the projection of the gradient vector onto the ball of radius λ \lambda λ centered at zero; the iterates themselves are never projected. The output at time t t t is the last iterate x t + 1 x_{t+1} x t + 1 itself, without averaging, selection, or restarts.
Fixed-time and time-uniform guarantees. Let ε t ( δ ) \varepsilon_t(\delta) ε t ( δ ) be a deterministic envelope. A fixed-time guarantee asserts that for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and every deterministic t ≥ 1 t\ge1 t ≥ 1 ,
P { f ( x t + 1 ) − f ⋆ ≤ ε t ( δ ) } ≥ 1 − δ , \mathbb{P}\{f(x_{t+1})-f^\star\le\varepsilon_t(\delta)\}\ge1-\delta, P { f ( x t + 1 ) − f ⋆ ≤ ε t ( δ )} ≥ 1 − δ ,
so that the success event may depend on t t t . A time-uniform guarantee, analogous to a confidence sequence (Howard et al. [24 ] ), asserts the stronger statement
P { f ( x t + 1 ) − f ⋆ ≤ ε t ( δ ) for all t ≥ 1 } ≥ 1 − δ . \mathbb{P}\{f(x_{t+1})-f^\star\le\varepsilon_t(\delta)\text{ for all }t\ge1\}\ge1-\delta. P { f ( x t + 1 ) − f ⋆ ≤ ε t ( δ ) for all t ≥ 1 } ≥ 1 − δ .
A method for a known horizon T T T requires the guarantee only at t = T t=T t = T . A time-uniform guarantee also holds at every data-dependent time τ \tau τ , such as one chosen by early stopping or checkpoint selection, because its event implies f ( x τ + 1 ) − f ⋆ ≤ ε τ ( δ ) f(x_{\tau+1})-f^\star\le\varepsilon_\tau(\delta) f ( x τ + 1 ) − f ⋆ ≤ ε τ ( δ ) . Conversely, a guarantee that holds at every bounded stopping time is time-uniform: apply it at min { τ , N } \min\{\tau,N\} min { τ , N } , where τ \tau τ is the first time the bound fails, and let N → ∞ N\to\infty N → ∞ . A fixed-time guarantee covers only times chosen before the run. Converting fixed-time guarantees into a time-uniform event requires splitting the confidence budget; under heavy-tailed noise, this cost cannot always be absorbed into logarithmic factors (§ 5 ).
Known Horizon: An Optimal Last-Iterate Rate
We first recall the known-horizon rate of Jiang et al. [27 ] and Liu [36 ] : clipped SGD with a fixed threshold and linearly decaying step sizes attains the statistical scale (2) at its last iterate. We then extend the potential behind it to unknown horizons.
Algorithm 1 makes T T T oracle calls using O ( d ) O(d) O ( d ) memory and no knowledge of x ⋆ x^\star x ⋆ ; its clipping threshold is constant and its final step size is η / T \eta/T η / T . Linearly decaying step sizes are the worst-case optimal schedule in the analysis of Defazio et al. [12 ] .
Theorem 1 (Known horizon; Jiang et al. [27 ] , Theorem 1). *Let Assumptions 1 and 2 hold, and let T ≥ 1 T\ge1 T ≥ 1 and 0 < δ < 1 0<\delta<1 0 < δ < 1 . With probability at least 1 − δ 1-\delta 1 − δ , the output of Algorithm 1 satisfies, with
ℓ = log ( 8 / δ ) \ell= \log(8/\delta) ℓ = log ( 8/ δ ) ,
f ( x T + 1 ) − f ⋆ ≤ 1024 L R 2 ℓ T + 256 σ R ( ℓ T ) ( p − 1 ) / p . (3) f(x_{T+1}) - f^\star\le\frac{1024LR^2\ell}{T} + 256\sigma R\left(\frac{\ell}{T}\right)^{(p-1)/p}. \tag*{(3)} f ( x T + 1 ) − f ⋆ ≤ T 1024 L R 2 ℓ + 256 σ R ( T ℓ ) ( p − 1 ) / p . (3)
The bound has no log T \log T log T factor except through the confidence parameter and has constants independent of p p p and the dimension. At p = 2 p = 2 p = 2 the stochastic term is 256 σ R ℓ / T 256\sigma R\sqrt{\ell/T} 256 σ R ℓ / T ; at σ = 0 \sigma= 0 σ = 0 the threshold is 4 L R 4LR 4 L R . Liu [36 ] proves a bound of the same order with a state-dependent threshold (Appendix § 10 .§ 2 ). The proof of Jiang et al. [27 ] combines the tail-sum potential of Appendix § 13 .§ 2 with a stopping-time localization of the iterates. Our Lean formalization contains a machine-checked proof of Theorem 1 (§ 7 ).
When the stochastic term dominates, λ ≍ T 1 / p \lambda\asymp T^{1/p} λ ≍ T 1/ p balances the total clipping bias T σ p λ 1 − p T\sigma^p\lambda^{1-p} T σ p λ 1 − p against λ ℓ \lambda\ell λ ℓ , and each update moves by at most R / ( 128 ℓ ) R/(128\ell) R / ( 128 ℓ ) . The actual final state attains (2), which is optimal up to constants in this regime (Jiang et al., [27 ] ). The deterministic term is that of unaccelerated gradient descent; acceleration attains L R 2 / T 2 LR^2/T^2 L R 2 / T 2 without noise (Nesterov, [46 ] ; Lan, [31 ] ).
Unknown Horizon: Time-Uniform Guarantees
We now turn to an unknown horizon and ask what can be guaranteed at all times simultaneously. We first construct a schedule that attains O ~ ( t − β p ) \widetilde{O}(t^{-\beta_p}) O ( t − β p ) and then prove that no gradient-only rule attains a larger exponent.
A Horizon-Free Upper Bound
Define the exponents
β = β p = 2 ( p − 1 ) 3 p − 1 , a = p + 1 3 p − 1 = 1 − β , b = 2 3 p − 1 . (4) \beta= \beta_p = \frac{2(p-1)}{3p-1}, \qquad a = \frac{p+1}{3p-1} = 1-\beta, \qquad b = \frac{2}{3p-1}. \tag*{(4)} β = β p = 3 p − 1 2 ( p − 1 ) , a = 3 p − 1 p + 1 = 1 − β , b = 3 p − 1 2 . (4)
Let Q = max { L R , σ } Q = \max\{LR,\sigma\} Q = max { L R , σ } and ℓ t = log ( 100 t 2 ) \ell_t = \log(100t^2) ℓ t = log ( 100 t 2 ) . We run the recursion (1) for all t ≥ 1 t \ge1 t ≥ 1 with
η t = R Q c p t − a ℓ t 2 , λ t = 4 Q t b , (5) \eta_t = \frac{R}{Q}\frac{c_p t^{-a}}{\ell_t^2}, \qquad\lambda_t = 4Qt^b, \tag*{(5)} η t = Q R ℓ t 2 c p t − a , λ t = 4 Q t b , (5)
where c p > 0 c_p > 0 c p > 0 depends only on p p p . At p = 2 p = 2 p = 2 this is η t ∝ t − 3 / 5 \eta_t \propto t^{-3/5} η t ∝ t − 3/5 and λ t ∝ t 2 / 5 \lambda_t \propto t^{2/5} λ t ∝ t 2/5 . Neither a terminal horizon nor a confidence level enters the parameters or initialization. For analysis, write ι t ( δ ) = log ( 100 t 2 / δ ) \iota_t(\delta) = \log(100t^2/\delta) ι t ( δ ) = log ( 100 t 2 / δ ) .
Theorem 2 (Time-uniform upper bound). Let Assumptions 1 and 2 hold, and run (1) with the schedule (5). There is a finite positive constant c p c_p c p depending only on p p p , and we may take D p = 4 / c p D_p = 4/c_p D p = 4/ c p (see Appendix § 18 .§ 1 ), such that for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ , simultaneously for every integer T ≥ 1 T \ge1 T ≥ 1 ,
f ( x T + 1 ) − f ⋆ ≤ D p R Q T − β ι T ( δ ) 4 , (6) f(x_{T+1}) - f^\star\le D_pRQ T^{-\beta}\iota_T(\delta)^4, \tag*{(6)} f ( x T + 1 ) − f ⋆ ≤ D p R Q T − β ι T ( δ ) 4 , (6) ∥ x T + 1 − x ⋆ ∥ 2 ≤ R 2 [ log ( 100 / δ ) ] 2 . (7) \lVert x_{T+1} - x^\star\rVert^2 \le R^2[\log(100/\delta)]^2. \tag*{(7)} ∥ x T + 1 − x ⋆ ∥ 2 ≤ R 2 [ log ( 100/ δ ) ] 2 . (7) The trajectory is the same for every δ \delta δ ; only the event and its bounds depend on δ \delta δ . Hence the rate also holds almost surely: with δ = 1 / n \delta= 1/n δ = 1/ n , the theorem gives events of probability at least 1 − 1 / n 1 - 1/n 1 − 1/ n on which f ( x T + 1 ) − f ⋆ ≤ D p R Q T − β p ℓ T 4 ( 1 + log n / ℓ T ) 4 f(x_{T+1}) - f^\star\le D_pRQ T^{-\beta_p}\ell_T^4(1 + \log n/\ell_T)^4 f ( x T + 1 ) − f ⋆ ≤ D p R Q T − β p ℓ T 4 ( 1 + log n / ℓ T ) 4 for all T T T , so that, with probability one,
lim sup T → ∞ f ( x T + 1 ) − f ⋆ T − β p ℓ T 4 ≤ D p R Q . \limsup_{T\to\infty}\frac{f(x_{T+1}) - f^\star}{T^{-\beta_p}\ell_T^4} \le D_pRQ. T → ∞ lim sup T − β p ℓ T 4 f ( x T + 1 ) − f ⋆ ≤ D p R Q .
Our proof gives c 2 < 10 − 25 c_2 < 10^{-25} c 2 < 1 0 − 25 and D 2 > 10 25 D_2 > 10^{25} D 2 > 1 0 25 at p = 2 p = 2 p = 2 (Appendix § 18 .§ 1 ); the exponents of the schedule and of the rate do not depend on these constants, and the illustration in Appendix § 11 uses step-size constants of order one. The guarantee of Chezhegov et al. [8 ] is also time-uniform, since their proof controls nested events over all steps, but their schedule uses δ \delta δ ; our improvement of their exponent comes from the potential in Appendix § 13 .§ 2 . At p = 2 p = 2 p = 2 this also separates clipped SGD from unclipped SGD with deterministic step sizes, which attains no exponent above 1 / 3 1/3 1/3 almost surely (Anonymous [1 ] ); Appendix § 16 compares the two settings. In Theorem 4 we show that β p \beta_p β p is optimal.
A Matching Lower Bound for Horizon-Free Rules
To show that β p \beta_p β p cannot be improved, we consider all rules that query the current iterate and update along the resulting stochastic gradient. Every clipped update is a nonnegative scalar multiple of − g t -g_t − g t , and every such multiple for g t ≠ 0 g_t \ne0 g t = 0 can be implemented by clipping with a suitable step size. We call these rules gradient-only rules ; Definition 3 restricts their update direction and oracle access.
Definition 3 (Gradient-only rules). Let p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] , L = R = σ = 1 L = R = \sigma= 1 L = R = σ = 1 , and x 1 = 0 x_1 = 0 x 1 = 0 . A horizon-free gradient-only rule queries one fresh stochastic gradient g t g_t g t at the current iterate x t x_t x t and updates
x t + 1 = x t − c t g t , x_{t+1} = x_t - c_t g_t, x t + 1 = x t − c t g t , where the finite step factor c t ≥ 0 c_t \ge0 c t ≥ 0 is a measurable function of t t t , δ \delta δ , p p p , the bounds L , R , σ L, R, \sigma L , R , σ , the gradients g 1 , … , g t g_1,\ldots,g_t g 1 , … , g t , and independent randomness. Equivalently, c t g t = η t clip ( g t , λ t ) c_tg_t = \eta_t\operatorname{clip}(g_t,\lambda_t) c t g t = η t clip ( g t , λ t ) for some finite η t ≥ 0 \eta_t \ge0 η t ≥ 0 and λ t > 0 \lambda_t > 0 λ t > 0 chosen in the same way.
Momentum, extra queries, restarts, output selection, and averaging are excluded.
Theorem 4 (Time-uniform lower bound). Fix p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] and δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) . For every rule of Definition 3 , every C > 0 C > 0 C > 0 , m ≥ 0 m \ge0 m ≥ 0 , and
r > β p = 2 ( p − 1 ) 3 p − 1 , (8) r > \beta_p = \frac{2(p-1)}{3p-1}, \tag*{(8)} r > β p = 3 p − 1 2 ( p − 1 ) , (8) there is an instance satisfying Assumptions 1 and 2 with L = R = σ = 1 L = R = \sigma= 1 L = R = σ = 1 and x 1 = 0 x_1 = 0 x 1 = 0 such that
P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r [ log ( e t ) ] m } > δ . (9) \mathbb{P}\left\{\exists t \ge1 : f(x_{t+1}) - f^\star> Ct^{-r}[\log(et)]^m\right\} > \delta. \tag*{(9)} P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r [ log ( e t ) ] m } > δ . (9) The rule, C C C , and m m m may depend arbitrarily on δ \delta δ and p p p . The instance is one-dimensional, with i.i.d. additive noise and convex, globally 1-smooth sample losses that attain their minima.
Theorems 2 and 4 together answer our question for time-uniform guarantees: β p \beta_p β p is the optimal exponent for gradient-only rules, strictly below the exponent α p \alpha_p α p for a known horizon.
Idea of the proof. The sample losses F μ , y ( x ; Y ) = 1 2 ( x − y + μ ) + 2 − A Y x F_{\mu,y}(x;Y)=\frac{1}{2}(x-y+\mu)_+^2-AYx F μ , y ( x ; Y ) = 2 1 ( x − y + μ ) + 2 − A Y x , with Y ∼ Bernoulli ( μ / A ) Y \sim\operatorname{Bernoulli}(\mu/A) Y ∼ Bernoulli ( μ / A ) and A = ( 2 μ ) − 1 / ( p − 1 ) A=(2\mu)^{-1/(p-1)} A = ( 2 μ ) − 1/ ( p − 1 ) , have minimizer y ∈ [ μ , 1 ] y \in[\mu,1] y ∈ [ μ , 1 ] in expectation. Every target gives the same gradient − A Y -AY − A Y before crossing its boundary y − μ y-\mu y − μ . A shared transcript therefore couples all fixed targets. If a rule keeps the error below b t b_t b t for all t ≤ N t \le N t ≤ N , an overshoot longer than μ + 2 b t \mu+\sqrt{2b_t} μ + 2 b t violates one target’s envelope. Integrating, over the target location, the probabilities of failing at the first crossing charges safe progress only to the rare arrivals Y = 1 Y=1 Y = 1 , which have probability π = μ / A \pi=\mu/A π = μ / A . Proposition 17 turns this into a budget: if the envelopes b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N hold on every instance with probability at least 1 − ε 1-\varepsilon 1 − ε , then for every μ ∈ ( 4 b N , 1 / 2 ] \mu\in(4b_N,1/2] μ ∈ ( 4 b N , 1/2 ] ,
π ∑ t = 1 N ( μ + 2 b t ) ≥ 1 − 2 ε 2 . \pi\sum_{t=1}^{N}(\mu+\sqrt{2b_t}) \ge\frac{1-2\varepsilon}{2}. π t = 1 ∑ N ( μ + 2 b t ) ≥ 2 1 − 2 ε .
The budget holds for adaptive jump sizes, and the targets are fixed before the run rather than chosen after seeing the path. For a claimed exponent r > β p r > \beta_p r > β p , choose β p < u < min { r , 1 } \beta_p < u < \min\{r,1\} β p < u < min { r , 1 } and dominate the first N N N errors by b N , t = C log m ( e N ) t − u b_{N,t} = C\log^m(eN)t^{-u} b N , t = C log m ( e N ) t − u . With μ = 8 b N , N \mu= 8b_{N,N} μ = 8 b N , N , π ≍ μ p / ( p − 1 ) \pi\asymp\mu^{p/(p-1)} π ≍ μ p / ( p − 1 ) and the left side is, up to logarithms, N 1 − u ( p / ( p / ( p − 1 ) + 1 / 2 ) ) N^{1-u(p/(p/(p-1)+1/2))} N 1 − u ( p / ( p / ( p − 1 ) + 1/2 )) , which tends to zero because u > β p = 1 / ( p / ( p − 1 ) + 1 / 2 ) u > \beta_p = 1/(p/(p-1)+1/2) u > β p = 1/ ( p / ( p − 1 ) + 1/2 ) . Appendix § 17 carries out this calculation, which also gives Theorems 6 and 7.
Unknown Horizon: Fixed-Time Guarantees
We now show that, for gradient-only rules, the barrier β p \beta_p β p can be crossed at a single fixed time, but only at a polynomial cost in confidence: horizon-free clipped SGD attains the statistical exponent at each fixed time with polynomial confidence dependence, and every exponent between β p \beta_p β p and α p \alpha_p α p at a smaller confidence cost.
Theorem 5 (Fixed-time confidence–rate tradeoff). Let Assumptions 1 and 2 hold, and let Q Q Q , c p c_p c p , D p D_p D p , ℓ t \ell_t ℓ t , and ι T ( δ ) \iota_T(\delta) ι T ( δ ) be as in Theorem 2. Fix r ∈ ( β p , α p ] r \in(\beta_p,\alpha_p] r ∈ ( β p , α p ] and u ≥ 0 u \ge0 u ≥ 0 , and use the horizon-free schedule
η t = R Q c p δ u t − ( 1 − r ) ℓ t 2 , λ t = 4 Q max { 1 , δ u / ( p − 1 ) t r / ( p − 1 ) } . (10) \eta_t = \frac{R}{Q}\frac{c_p\delta^u t^{-(1-r)}}{\ell_t^2},
\qquad
\lambda_t = 4Q\max\left\{1,\delta^{u/(p-1)}t^{r/(p-1)}\right\}. \tag*{(10)} η t = Q R ℓ t 2 c p δ u t − ( 1 − r ) , λ t = 4 Q max { 1 , δ u / ( p − 1 ) t r / ( p − 1 ) } . (10) Put
c i n ( r ) = 3 p − 1 p − 1 ( r − β p ) , c_{\mathrm{in}}(r) = \frac{3p-1}{p-1}(r-\beta_p), c in ( r ) = p − 1 3 p − 1 ( r − β p ) , c f r e e ( r ) = ( 3 p − 1 ) r − 2 ( p − 1 ) ( 2 p − 1 ) r − ( p − 1 ) . c_{\mathrm{free}}(r) = \frac{(3p-1)r-2(p-1)}{(2p-1)r-(p-1)}. c free ( r ) = ( 2 p − 1 ) r − ( p − 1 ) ( 3 p − 1 ) r − 2 ( p − 1 ) . If u = c i n ( r ) u=c_{\mathrm{in}}(r) u = c in ( r ) , let c = c i n ( r ) c=c_{\mathrm{in}}(r) c = c in ( r ) ; if u = 0 u=0 u = 0 , let c = c f r e e ( r ) c=c_{\mathrm{free}}(r) c = c free ( r ) . Then for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and every deterministic T ≥ 1 T \ge1 T ≥ 1 , with probability at least 1 − δ 1-\delta 1 − δ ,
f ( x T + 1 ) − f ⋆ ≤ D p R Q T − r δ − c ι T ( δ ) 4 . (11) f(x_{T+1})-f^\star\le D_p RQ T^{-r}\delta^{-c}\iota_T(\delta)^4. \tag*{(11)} f ( x T + 1 ) − f ⋆ ≤ D p R Q T − r δ − c ι T ( δ ) 4 . (11) The schedule (10) clips the current stochastic gradient, so it is a rule of Definition 3 . With u = 0 u=0 u = 0 it uses neither the horizon nor the confidence level, and one trajectory satisfies (11) for every δ \delta δ ; the success event depends on δ \delta δ and T T T . At r = α p r=\alpha_p r = α p the confidence factor is δ − ( p − 1 ) / p \delta^{-(p-1)/p} δ − ( p − 1 ) / p with the confidence input and δ − 1 \delta^{-1} δ − 1 without it, that is, δ − 1 / 2 \delta^{-1/2} δ − 1/2 and δ − 1 \delta^{-1} δ − 1 at p = 2 p=2 p = 2 . Both exponents tend to zero as r ↓ β p r \downarrow\beta_p r ↓ β p , where the schedule of Theorem 2 attains β p \beta_p β p with polylogarithmic confidence dependence.
Conversely, for horizon-free gradient-only rules, every fixed-time exponent above β p \beta_p β p costs a polynomial confidence factor, because Proposition 17 also constrains fixed-time guarantees through a union bound over finite prefixes.
Theorem 6 (Fixed-time lower bound with polynomial confidence cost). Let ( r u l e δ ) δ ∈ ( 0 , 1 ) (\mathrm{rule}_\delta)_{\delta\in(0,1)} ( rule δ ) δ ∈ ( 0 , 1 ) be any family of rules of Definition 3 , and let C > 0 C>0 C > 0 , m ≥ 0 m\ge0 m ≥ 0 , c ∈ [ 0 , 1 − β p ) c\in[0,1-\beta_p) c ∈ [ 0 , 1 − β p ) , and r > β p + c r>\beta_p+c r > β p + c . There exist δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , a deterministic integer t ≥ 1 t\ge1 t ≥ 1 , and an instance in the class of Theorem 4 such that r u l e δ \mathrm{rule}_\delta rule δ satisfies
P { f ( x t + 1 ) − f ⋆ > C t − r δ − c [ log ( e t / δ ) ] m } > δ . (12) \mathbb{P}\left\{f(x_{t+1})-f^\star> Ct^{-r}\delta^{-c}[\log(et/\delta)]^m\right\}>\delta. \tag*{(12)} P { f ( x t + 1 ) − f ⋆ > C t − r δ − c [ log ( e t / δ ) ] m } > δ . (12) Here C C C , c c c , and m m m do not depend on δ \delta δ , t t t , or the instance, while each rule may depend arbitrarily on δ \delta δ , the history, independent randomness, and the current stochastic gradient.
With c = 0 c=0 c = 0 , fixed-time guarantees with uniformly polylogarithmic dependence on 1 / δ 1/\delta 1/ δ attain no exponent above β p \beta_p β p . Our proof applies Proposition 17 to the rule tuned for δ N = 1 / ( 4 N ) \delta_N=1/(4N) δ N = 1/ ( 4 N ) with the separate probability budget 1 / 4 1/4 1/4 : a union bound over the first N N N times turns the fixed-time envelope into a time-uniform one on this finite prefix, and δ N − c \delta_N^{-c} δ N − c contributes the factor ( 4 N ) c (4N)^c ( 4 N ) c (Appendix § 17 .§ 4 ).
For r ∈ ( β p , α p ] r\in(\beta_p,\alpha_p] r ∈ ( β p , α p ] , let c ⋆ ( r ) c^\star(r) c ⋆ ( r ) be the infimum of the exponents c c c for which some family of gradient-only rules attains a fixed-time envelope C t − r δ − c [ log ( e t / δ ) ] m Ct^{-r}\delta^{-c}[\log(et/\delta)]^m C t − r δ − c [ log ( e t / δ ) ] m on all instances. Since ι T ( δ ) ≤ 5 log ( e T / δ ) \iota_T(\delta)\leq5\log(eT/\delta) ι T ( δ ) ≤ 5 log ( e T / δ ) , Theorems 5 and 6 give
r − β p ≤ c ⋆ ( r ) ≤ 3 p − 1 p − 1 ( r − β p ) . (13) r-\beta_p\leq c^\star(r)\leq\frac{3p-1}{p-1}(r-\beta_p). \tag*{(13)} r − β p ≤ c ⋆ ( r ) ≤ p − 1 3 p − 1 ( r − β p ) . (13)
At r = α p r=\alpha_p r = α p the upper end is α p \alpha_p α p , and the lower end is the gap between the fixed-time and time-uniform exponents,
α p − β p = ( p − 1 ) 2 p ( 3 p − 1 ) > 0 , \alpha_p-\beta_p=\frac{(p-1)^2}{p(3p-1)}>0, α p − β p = p ( 3 p − 1 ) ( p − 1 ) 2 > 0 ,
which is 1 / 10 1/10 1/10 at p = 2 p=2 p = 2 . The two ends come from different arguments: the lower end from a union bound over the first N N N times, which does not use that, before the first crossing, the iterates of the hard instance move only at rare gradient spikes, and the upper end from truncating the late clipping errors, whose cost the p p p th moment controls. Which end is tight is open (Appendix § 12 ).
Memory and the Momentum Boundary
Momentum and averaging lie outside the class of Theorem 4 , so we ask whether memory can beat β p \beta_p β p . For clipped heavy-ball momentum with polynomially bounded step sizes, we find that it can only if it grows over time. To show this, we compare iterate averaging with two classes of clipped heavy-ball momentum. Each method queries one stochastic gradient at its current iterate and outputs the updated state. The lower bounds hold even for fixed i.i.d. additive noise and smooth convex sample losses, whereas the upper bound holds for the general oracle of Assumption 2.
Forgetting in One Dimension
Consider the stochastic heavy-ball recursion [52 ] in velocity form:
v t + 1 = β t v t + clip ( g t , λ t ) , x t + 1 = x t − η t v t + 1 , x 1 = v 1 = 0 , (14) \begin{aligned}
v_{t+1} &= \beta_t v_t+\operatorname{clip}(g_t,\lambda_t),\\
x_{t+1} &= x_t-\eta_t v_{t+1},\qquad x_1=v_1=0, \tag*{(14)}
\end{aligned} v t + 1 x t + 1 = β t v t + clip ( g t , λ t ) , = x t − η t v t + 1 , x 1 = v 1 = 0 , (14)
where η t \eta_t η t is the step size and β t ∈ [ 0 , 1 ) \beta_t\in[0,1) β t ∈ [ 0 , 1 ) is the momentum coefficient. A gradient observed at time j j j enters x t + 1 x_{t+1} x t + 1 with weight proportional to ∏ i = j + 1 t β i \prod_{i=j+1}^{t}\beta_i ∏ i = j + 1 t β i . A horizon-free rule may choose the scalar controls from the entire history, an independent seed, and the current raw gradient, subject on every trajectory to
0 ≤ β t < 1 , 1 − β t ≥ ρ ( 1 + t ) − a ( t ≥ t 0 ) , 0 ≤ η t ≤ H ( 1 + t ) h , 0 ≤ λ t < ∞ , (15) \begin{aligned}
0&\leq\beta_t<1,\qquad1-\beta_t\geq\rho(1+t)^{-a}\quad(t\geq t_0),\\
0&\leq\eta_t\leq H(1+t)^h,\qquad0\leq\lambda_t<\infty, \tag*{(15)}
\end{aligned} 0 0 ≤ β t < 1 , 1 − β t ≥ ρ ( 1 + t ) − a ( t ≥ t 0 ) , ≤ η t ≤ H ( 1 + t ) h , 0 ≤ λ t < ∞ , (15)
with constants a ∈ [ 0 , 1 ) a\in[0,1) a ∈ [ 0 , 1 ) , ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] , t 0 ∈ N t_0\in\mathbb{N} t 0 ∈ N , and H , h ≥ 0 H,h\geq0 H , h ≥ 0 that depend only on the rule and its confidence input, not on the instance, the samples, or the seed. Geometric forgetting, β t ≤ β ˉ < 1 \beta_t\leq\bar{\beta}<1 β t ≤ β ˉ < 1 , is the case a = 0 a=0 a = 0 with ρ = 1 − β ˉ \rho=1-\bar{\beta} ρ = 1 − β ˉ and t 0 = 1 t_0=1 t 0 = 1 .
Theorem 7 (One-dimensional momentum lower bound). Fix p ∈ ( 1 , 2 ] p\in(1,2] p ∈ ( 1 , 2 ] , a ∈ [ 0 , 1 ) a\in[0,1) a ∈ [ 0 , 1 ) , and a confidence 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , and let a horizon-free rule satisfy (14) and (15) . For every finite C > 0 C>0 C > 0 , m ≥ 0 m\geq0 m ≥ 0 , and r > ( 1 + a ) β p r>(1+a)\beta_p r > ( 1 + a ) β p , there is a fixed one-dimensional instance with L = R = σ = 1 L=R=\sigma=1 L = R = σ = 1 such that
P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r log m ( e t ) } > δ . (16) \mathbb{P}\{\exists t\geq1:f(x_{t+1})-f^\star>Ct^{-r}\log^m(et)\}>\delta. \tag*{(16)} P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r log m ( e t )} > δ . (16)
The instance satisfies Assumptions 1 and 2 with i.i.d. additive noise and convex, globally 1 1 1 -smooth sample losses that attain their minima, and it is fixed before the run.
Under geometric forgetting, the theorem excludes every exponent above β p \beta_p β p , as Theorem 4 does for gradient-only rules; in particular, it covers any fixed β ∈ [ 0 , 1 ) \beta\in[0,1) β ∈ [ 0 , 1 ) with arbitrary adaptive step sizes 0 ≤ η t ≤ ( 1 − β ) 2 0 \le\eta_t \le(1-\sqrt{\beta})^2 0 ≤ η t ≤ ( 1 − β ) 2 . For 0 ≤ a < ( p − 1 ) / ( 2 p ) 0 \le a < (p-1)/(2p) 0 ≤ a < ( p − 1 ) / ( 2 p ) , ( 1 + a ) β p < α p (1+a)\beta_p < \alpha_p ( 1 + a ) β p < α p , so polynomial forgetting at this rate does not attain the statistical exponent either. Our proof (Appendix § 19 ) bounds the progress that rare gradient spikes can make through the decaying momentum kernel.
Polynomial Forgetting with Constants Independent of Dimension
For polynomial forgetting, Theorem 7 excludes only exponents above ( 1 + a ) β p (1+a)\beta_p ( 1 + a ) β p : its budget lets each rare gradient spike move the iterate for O ~ ( N a ) \widetilde{O}(N^a) O ( N a ) steps on a horizon N N N , the time the momentum kernel needs to decay. If the dimension may grow and the constants are shared across dimensions, the barrier drops to max { β p , a } \max\{\beta_p,a\} max { β p , a } . Fix p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] and a ∈ [ 0 , 1 ) a \in[0,1) a ∈ [ 0 , 1 ) . The class A u n i f ( a ) \mathcal{A}_{\mathrm{unif}}(a) A unif ( a ) consists of rules defined in every finite dimension that run (14) from zero state and velocity, observe only stochastic gradients, and choose their controls as measurable functions of the dimension, time, confidence, the bounds L = R = σ = 1 L=R=\sigma=1 L = R = σ = 1 , the gradients up to the current one, and an independent seed. There must be deterministic constants ρ ∈ ( 0 , 1 ] \rho\in(0,1] ρ ∈ ( 0 , 1 ] , t 0 ∈ N t_0 \in\mathbb{N} t 0 ∈ N , and H , h ≥ 0 H,h \ge0 H , h ≥ 0 , which may depend on the rule, p p p , a a a , and δ \delta δ but not on the dimension, the instance, or the seed, such that in every dimension and on every history
0 ≤ β t < 1 , 0 ≤ λ t < ∞ , 0 ≤ η t ≤ H ( 1 + t ) h , 1 − β t ≥ ρ ( 1 + t ) − a ( t ≥ t 0 ) . (17) \begin{aligned}
0 &\le\beta_t < 1,\quad0 \le\lambda_t < \infty,\quad0 \le\eta_t \le H(1+t)^h,\\
1-\beta_t &\ge\rho(1+t)^{-a}\quad(t \ge t_0). \tag*{(17)}
\end{aligned} 0 1 − β t ≤ β t < 1 , 0 ≤ λ t < ∞ , 0 ≤ η t ≤ H ( 1 + t ) h , ≥ ρ ( 1 + t ) − a ( t ≥ t 0 ) . (17)
Theorem 8 (Dimension-uniform lower bound under polynomial forgetting). Let C > 0 C>0 C > 0 and k ≥ 0 k\ge0 k ≥ 0 be finite, let r > max { β p , a } r>\max\{\beta_p,a\} r > max { β p , a } , and fix a confidence δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) . For any rule in A u n i f ( a ) \mathcal{A}_{\mathrm{unif}}(a) A unif ( a ) , there is a finite-dimensional instance with L = R = σ = 1 L=R=\sigma=1 L = R = σ = 1 for which
P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r log k ( e t ) } > δ . (18) \mathbb{P}\{\exists t\ge1:f(x_{t+1})-f^\star>Ct^{-r}\log^k(et)\}>\delta. \tag*{(18)} P { ∃ t ≥ 1 : f ( x t + 1 ) − f ⋆ > C t − r log k ( e t )} > δ . (18)
Failure occurs on a deterministic finite prefix. The instance satisfies Assumptions 1 and 2 with i.i.d. additive noise and convex, globally 1 1 1 -smooth sample losses that attain their minima, and it is fixed before the samples and the seed are drawn; C C C and k k k are shared across dimensions.
The proof augments the objective with auxiliary quadratic coordinates, referred to as the nuisance block, subject to i.i.d. signed coordinate noise at each round. On a finite prefix with distinct coordinates, an orthogonal test vector bounds the useful displacement from each rare observation, accumulated over its whole forgetting window, by the allowed nuisance radius, even when controls depend on the current noisy vector; this removes the factor O ~ ( N a ) \widetilde{O}(N^a) O ( N a ) of the one-dimensional bound. Polynomial forgetting makes the remaining tail of each spike’s effect negligible (Appendix § 20 ).
Consequently the optimal dimension-uniform exponent in A u n i f ( a ) \mathcal{A}_{\mathrm{unif}}(a) A unif ( a ) is β p \beta_p β p for 0 ≤ a ≤ β p 0 \le a \le\beta_p 0 ≤ a ≤ β p : Theorem 2 attains it with β t = 0 \beta_t=0 β t = 0 and bounded steps, which meet (17) for every such a a a . For 0 < a < α p 0<a<\alpha_p 0 < a < α p , this barrier max { β p , a } \max\{\beta_p,a\} max { β p , a } lies strictly below min { ( 1 + a ) β p , α p } \min\{(1+a)\beta_p,\alpha_p\} min {( 1 + a ) β p , α p } . Shared constants match the upper bounds, whose constants do not depend on the dimension; the proof uses them by choosing the dimension after the horizon. Propositions 23 and 25 in the appendix extend Theorems 7 and 8 to fixed-time guarantees, as Theorem 6 does for Theorem 4 , when the step-size bound depends on δ \delta δ only through a polynomial factor.
Querying Gradients at the Running Average
Theorem 9 (Time-uniform averaging momentum). Let Assumptions 1 and 2 hold. For δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , define deterministic horizon-free parameters
c 0 = 1 128 , h δ = log 4 δ + 4 p p − 1 , ℓ ˉ t = h δ + log t , c_0 = \frac{1}{128},\qquad h_\delta= \log\frac{4}{\delta} + \frac{4p}{p-1},\qquad\bar{\ell}_t = h_\delta+ \log t, c 0 = 128 1 , h δ = log δ 4 + p − 1 4 p , ℓ ˉ t = h δ + log t , λ t = max { 4 L R , σ t 1 / p } , γ t = c 0 R λ t ℓ ˉ t 2 . (19) \lambda_t = \max\{4LR,\sigma t^{1/p}\},\qquad\gamma_t = \frac{c_0R}{\lambda_t\bar{\ell}_t^2}. \tag*{(19)} λ t = max { 4 L R , σ t 1/ p } , γ t = λ t ℓ ˉ t 2 c 0 R . (19) Starting from z 1 = x 1 z_1=x_1 z 1 = x 1 , make one oracle call at x t x_t x t and update
d t = clip ( g t , λ t ) , z t + 1 = z t − γ t d t , d_t = \operatorname{clip}(g_t,\lambda_t),\qquad z_{t+1}=z_t-\gamma_td_t, d t = clip ( g t , λ t ) , z t + 1 = z t − γ t d t , x t + 1 = t t + 1 x t + 1 t + 1 z t + 1 . (20) x_{t+1}=\frac{t}{t+1}x_t+\frac{1}{t+1}z_{t+1}. \tag*{(20)} x t + 1 = t + 1 t x t + t + 1 1 z t + 1 . (20) With probability at least 1 − δ 1-\delta 1 − δ , simultaneously for every integer T ≥ 1 T\ge1 T ≥ 1 , one has ∥ z T + 1 − x ⋆ ∥ < 2 R \lVert z_{T+1}-x^\star\rVert< \sqrt{2}R ∥ z T + 1 − x ⋆ ∥ < 2 R and
f ( x T + 1 ) − f ⋆ ≤ 128 R λ T ℓ ˉ T 2 + 2 L R 2 T + 1 (21) f(x_{T+1})-f^\star\le\frac{128R\lambda_T\bar{\ell}_T^2+2LR^2}{T+1} \tag*{(21)} f ( x T + 1 ) − f ⋆ ≤ T + 1 128 R λ T ℓ ˉ T 2 + 2 L R 2 (21) ≤ 514 ℓ ˉ T 2 ( L R 2 T + σ R T ( p − 1 ) / p ) . (22) \le514\bar{\ell}_T^2\left(\frac{LR^2}{T}+\frac{\sigma R}{T^{(p-1)/p}}\right). \tag*{(22)} ≤ 514 ℓ ˉ T 2 ( T L R 2 + T ( p − 1 ) / p σ R ) . (22) The point x T + 1 x_{T+1} x T + 1 is the actual updated state after exactly T T T calls.
The update (20) adapts the anytime online-to-batch conversion of Cutkosky [9 ] (building on classical online-to-batch conversion; Cesa-Bianchi et al. [7 ] ), whose primal averaging interpretation is due to Defazio [11 ] , to clipped stochastic gradients on an unbounded domain; the schedule (19) uses δ \delta δ but not the horizon. Proposition 26 expresses the same trajectory in the heavy-ball velocity form (14) , with bounded step sizes and α p / ( 2 t ) ≤ 1 − β t ≤ 1 / t \alpha_p/(2t)\le1-\beta_t\le1/t α p / ( 2 t ) ≤ 1 − β t ≤ 1/ t for t ≥ 2 t\ge2 t ≥ 2 . Proposition 27 realizes it with a constant momentum coefficient β t = b ∈ ( 0 , 1 ) \beta_t=b\in(0,1) β t = b ∈ ( 0 , 1 ) and exponentially growing step sizes, so Theorem 7 needs some restriction on the growth of the step sizes. The three-sequence accelerated clipped method of Nguyen et al. [47 ] also attains α p \alpha_p α p at its auxiliary output without a known horizon, and this bound transfers to its query state (Appendix L), whereas the trajectory of (20) has the two-sequence heavy-ball form (14) used by the momentum lower bounds.
Discussion
Implications. A known horizon T T T allows the step sizes and clipping threshold to be tuned to T T T , whereas a guarantee that covers adaptive checkpoint selection or early stopping must be time-uniform (§ 2 ). Our results quantify this separation for convex objective gap when the algorithm queries and outputs its current iterate: the attainable exponent drops from α p \alpha_p α p to β p \beta_p β p . For nonconvex stationarity, the bound on the average squared gradient norm over the trajectory in Nguyen et al. [47 ] retains the exponent for a known horizon up to logarithmic factors; obtaining a guarantee for a single selected iterate requires a separate selection argument, for example stationarity tests whose oracle calls are counted in the budget, combined with the doubling trick (Cesa-Bianchi and Lugosi, [6 ] ).
Formalization. We provide machine-checked proofs in Lean 4 with Mathlib of Theorems 2, 4 , and 8 and of the known-horizon bound of Theorem 1, including their proof dependencies. The code is provided as ancillary files of this arXiv entry and at https://github.com/Thefootofhappiness/clipped-sgd-last-iterate-lean . The formal proofs cover the recursive potential with two martingale tail bounds, integration of the probabilities of failing at the first crossing over a continuum of targets, and the momentum bound based on orthogonal projections.
References
AI Usage Statement
During the preparation of this manuscript, the authors used AI tools, including OpenAI’s GPT models and Anthropic’s Claude, for mathematical derivations and their verification, and to assist with writing. The authors take full responsibility for the content of this paper.
Related Work
Heavy-Tailed Noise and Gradient Clipping
Under the classical model with bounded pth moments ([44 , 67 ] ), truncated mirror descent ([42 ] ), smooth clipped methods ([21 , 56 , 47 ] ), and nonsmooth methods ([49 , 50 ] ) achieve high-probability statistical rates, typically for averaged or auxiliary outputs. Nekrasova et al. [43 ] relax the moment bound to a weak-L p L_p L p tail condition, with a noise scale that may grow with the gradient norm, and obtain high-probability rates for clipped SGD at its averaged iterate and for its accelerated variant at its last iterate, with clipping levels tuned to the horizon. Clipping is not always beneficial for averages: Suvorikova et al. [61 ] compare clipped and unclipped Polyak–Ruppert averaged SGD ([55 , 53 ] ) under finite pth moments with p ≥ 2 p \ge2 p ≥ 2 and show that, for p > 2 p > 2 p > 2 , clipping need not improve the leading term. Directional moments sharpen rates for structured instances ([70 , 37 ] ).
In decentralized smooth nonconvex optimization, Armacki et al. [3 ] analyze clipped DSGD under bounded central pth noise moments and establish stationarity bounds in high probability and in expectation, with linear speedup in the leading term. They bound averages over time of squared gradient norms across agents; we bound convex objective error at the last iterate and distinguish fixed-time from time-uniform behavior.
Last-Iterate Convergence
Schedules for a known horizon remove the logarithmic last-iterate factor of standard nonsmooth SGD ([58 , 23 , 26 , 69 ] ); for one-dimensional Lipschitz objectives with i.i.d. noise, constant step sizes tuned to the horizon already suffice, which fails without the i.i.d. assumption ([4 ] ). Smooth analyses based on moving comparators ((Liu and Zhou, 2024)) and online-to-batch regret reductions ([12 ] ) require stronger tail assumptions for high-probability guarantees. The bound in expectation under finite pth moments of Liu and Zhou (2026, Section 5) uses a p / ( p − 1 ) p/(p-1) p / ( p − 1 ) -uniformly convex mirror map, excluding Euclidean SGD at p < 2 p < 2 p < 2 . Parletta et al. [50 ] treat the last iterate of clipped SGD on Lipschitz objectives in expectation. For AdaGrad ([16 ] ) and AdaGrad-Norm ([60 , 68 ] ), with fixed parameters, Ou and Wang [48 ] show that the expected last-iterate error can decay arbitrarily slowly under an oracle whose noise depends on time and history. In our smooth setting, Chezhegov et al. [8 ] obtain the horizon-free exponent 2 ( p − 1 ) / ( 3 p ) 2(p-1)/(3p) 2 ( p − 1 ) / ( 3 p ) ; for clipped SGD with an unknown horizon, we establish β p \beta_p β p for time-uniform guarantees and α p \alpha_p α p for fixed-time guarantees with polynomial dependence on 1 / δ 1/\delta 1/ δ .
With a known horizon, recent work attains α p \alpha_p α p at the last iterate. Liu [36 ] treats Lipschitz and smooth convex objectives, strongly star-convex objectives, and composite and constrained problems under a fine-grained heavy-tailed noise model; Theorem 2 there covers smooth convex objectives with a state-dependent threshold and a refined noise dependence. Theorem 1 of Jiang et al. [27 ] is the bound we restate as Theorem 1. They also treat composite objectives with proximal updates and oracles under adversarial sample corruption, and establish two-point statistical lower bounds ([32 , 66 ] ). Both papers assume a known horizon; Liu [36 ] does so to avoid a potential logarithmic dependence on T T T . For gradient-only rules (Definition 3 ) with polylogarithmic dependence on 1 / δ 1/\delta 1/ δ , Theorems 2, 4 , and 6 show that when the horizon is unknown the optimal exponent drops from α p \alpha_p α p to β p \beta_p β p . Liu [36 ] lists matching lower bounds for smooth objectives as open; Jiang et al. [27 ] matches the stochastic term when the stochastic error dominates.
For the subgradient method, no single sequence of step sizes attains the optimal last-iterate rate at every iteration [69 ] . Deterministic anytime lower bounds use flat objectives and overshoots [29 , 65 , 30 ] . Our stochastic lower bound additionally handles adaptive responses to a shared i.i.d. transcript. Under conditional norm-sub-Gaussian noise, Li et al. (2026, Theorems 2.3, 3.4, and 4.1) characterize a logarithmic overhead around time exponent 1 / 2 1/2 1/2 . Finite second moments already permit the polynomial separation studied here.
Almost sure convergence. Under the ABC condition on conditional second moments [28 ] , Liu and Yuan [34 ] and Liu and Yuan (2024, Theorem 13) obtain almost sure last-iterate rates O ( t − 1 / 3 + ε ) O(t^{-1/3+\varepsilon}) O ( t − 1/3 + ε ) on smooth convex objectives for unclipped SGD, heavy-ball [52 ] , and Nesterov accelerated methods with deterministic step sizes of order t − 2 / 3 − ε t^{-2/3-\varepsilon} t − 2/3 − ε , 0 < ε < 1 / 3 0 < \varepsilon< 1/3 0 < ε < 1/3 . Sebbouh et al. [57 ] obtain o ( 1 / ∑ j < k η j ) o(1/\sum_{j<k}\eta_j) o ( 1/ ∑ j < k η j ) for weighted SGD averages and moving-average heavy-ball iterates under smooth convex sample losses, finite residual variance at the minimizer, and suitable step sizes and averaging weights. Concurrent and independent work by Anonymous [1 ] shows that, for every positive deterministic schedule of unclipped step sizes and every r > 1 / 3 r > 1/3 r > 1/3 , a one-dimensional smooth convex instance with a fixed i.i.d. finite-variance oracle satisfies lim sup t → ∞ ( t + 1 ) r ( f ( x t ) − f ⋆ ) = ∞ \limsup_{t\to\infty}(t+1)^r(f(x_t)-f^\star)=\infty lim sup t → ∞ ( t + 1 ) r ( f ( x t ) − f ⋆ ) = ∞ almost surely. Their Theorem 2.1 and Corollary 2.3 identify 1 / 3 1/3 1/3 as the supremal almost sure exponent under the ABC condition, and Proposition 2.4 establishes a matching rate up to logarithmic factors. Remark 16 adapts their lower bound to the time-uniform setting at a fixed confidence level δ \delta δ and compares it with clipping.
Online-to-batch conversions [7 , 9 ] , primal averaging [11 , 13 ] , and accelerated clipped methods [47 ] query coupled or averaged states. § 6 compares such memory with geometric forgetting. The upper proofs use the maximal concentration inequalities in Appendix § 15 ; for broader time-uniform martingale methods, see Howard et al. [24 ] .
Momentum lower bounds on quadratics also appear in Ganesh et al. [20 ] , for constant parameters and expected error. Drori and Shamir [15 ] use orthogonal noise for nonconvex stationarity, with coordinates indexed by time and step sizes and weights that may depend on the norms and inner products of all past iterates and stochastic gradients. Our momentum lower bound uses a fixed i.i.d. coordinate distribution and time-uniform convex objective error; its scalar controls may depend arbitrarily on signs, coordinates, and an independent seed, with constants shared across dimensions.
A Numerical Illustration
We illustrate the separation between α p \alpha_p α p and β p \beta_p β p numerically. Figure 1 compares the methods on the hard instances of Appendix § 17 .§ 1 at p = 2 p=2 p = 2 . For each horizon N N N we use the targets y ∈ { 1 / 4 , 1 / 2 , 3 / 4 , 1 } y \in\{1/4,1/2,3/4,1\} y ∈ { 1/4 , 1/2 , 3/4 , 1 } , the slopes μ = min { 0.2 , 1.3 N − α p } \mu=\min\{0.2,1.3N^{-\alpha_p}\} μ = min { 0.2 , 1.3 N − α p } and μ = min { 0.2 , 1.3 N − β p } \mu=\min\{0.2,1.3N^{-\beta_p}\} μ = min { 0.2 , 1.3 N − β p } , and the one-sided spike noise of (29); every method sees the same instances and the same spikes. Every method starts at x 1 = 0 x_1=0 x 1 = 0 , with z 1 = 0 z_1=0 z 1 = 0 for averaging and zero initial velocity for heavy-ball momentum, and N N N ranges over 500 ⋅ 2 k 500\cdot2^k 500 ⋅ 2 k for k = 0 , … , 6 k=0,\ldots,6 k = 0 , … , 6 . Clipped SGD uses the time-uniform schedule η t = t − ( p + 1 ) / ( 3 p − 1 ) \eta_t=t^{-(p+1)/(3p-1)} η t = t − ( p + 1 ) / ( 3 p − 1 ) , λ t = 2 t 2 / ( 3 p − 1 ) \lambda_t=2t^2/(3p-1) λ t = 2 t 2 / ( 3 p − 1 ) ; heavy-ball momentum uses β t = 0.8 \beta_t=0.8 β t = 0.8 , the same thresholds, and step sizes 0.2 t − ( p + 1 ) / ( 3 p − 1 ) 0.2t^{-(p+1)/(3p-1)} 0.2 t − ( p + 1 ) / ( 3 p − 1 ) ; averaging uses (20) with γ t = 0.5 t − 1 / p \gamma_t=0.5t^{-1/p} γ t = 0.5 t − 1/ p and λ t = 2 t 1 / p \lambda_t=2t^{1/p} λ t = 2 t 1/ p ; and Algorithm 1 uses λ = 2 N 1 / p \lambda= 2N^{1/p} λ = 2 N 1/ p and η t = 1.5 ( N − t + 1 ) / ( N λ ) \eta_t = 1.5(N - t + 1)/(N\lambda) η t = 1.5 ( N − t + 1 ) / ( N λ ) . These constants are of order one and do not change with N N N ; the theorems use smaller step sizes, different thresholds, and logarithmic factors. The script that produces the figure and its outputs are provided as ancillary files of this arXiv entry. For each method we take, over 1000 runs, the 0.9-quantile of the largest gap f ( x t + 1 ) − f ⋆ f(x_{t+1}) - f^\star f ( x t + 1 ) − f ⋆ over N / 2 ≤ t ≤ N N/2 \le t \le N N /2 ≤ t ≤ N , or of the terminal gap for Algorithm 1, and report its maximum over the eight instances.
Figure 1. Algorithm 1 for a known horizon, averaging (Theorem 9 ), time-uniform clipped SGD (Theorem 2), and heavy-ball momentum with β t = 0.8 \beta_t = 0.8 β t = 0.8 , with the exponents of the theorems and illustrative constants, on the hard instances of Appendix § 17 .§ 1 at p = 2 p = 2 p = 2 : worst case over eight instances of the 0.9-quantile, over 1000 runs, of the largest gap over N / 2 ≤ t ≤ N N/2 \le t \le N N /2 ≤ t ≤ N (terminal gap for Algorithm 1). Slopes are least-squares fits in log N \log N log N ; their 95% bootstrap intervals over the runs (200 resamples) have half-width below 0.02.
Algorithm 1 and averaging decay with fitted slopes − 0.50 -0.50 − 0.50 and − 0.55 -0.55 − 0.55 , close to − α 2 = − 1 / 2 -\alpha_2 = -1/2 − α 2 = − 1/2 , whereas clipped SGD and heavy-ball momentum decay with slopes − 0.35 -0.35 − 0.35 and − 0.30 -0.30 − 0.30 , and at N = 3.2 × 10 4 N = 3.2 \times10^4 N = 3.2 × 1 0 4 their worst gaps are 2.5 to 3 times those of the first two. Slopes fitted over this range of N N N also reflect constants and logarithmic factors. At p = 1.5 p = 1.5 p = 1.5 the experiment does not separate averaging from the other methods. There the exponents α p = 1 / 3 \alpha_p = 1/3 α p = 1/3 and β p = 2 / 7 \beta_p = 2/7 β p = 2/7 differ by less than 0.05. The fitted slopes are − 0.31 -0.31 − 0.31 for Algorithm 1 and for averaging and − 0.24 -0.24 − 0.24 and − 0.22 -0.22 − 0.22 for the other two methods, but at every N N N in this range the worst gap of averaging stays above those of clipped SGD and heavy-ball momentum; only the worst gap of Algorithm 1 falls below them, at N = 3.2 × 10 4 N = 3.2 \times10^4 N = 3.2 × 1 0 4 .
Open Problems
Our schedules use L L L , R R R , σ \sigma σ , p p p and, except for the time-uniform schedule and the schedule of Theorem 5 with u = 0 u = 0 u = 0 , a confidence input; adaptation to unknown problem parameters is a natural next step. The matching results concern polynomial exponents, so sharp logarithmic factors and constants, parameter interpolation, and the optimal confidence exponent c ⋆ ( r ) c^\star(r) c ⋆ ( r ) of fixed-time guarantees, bracketed in (13) , are left for future work. The two momentum lower bounds concern updates with zero initial velocity, queries and outputs at the current state, gradients as the only oracle information, and polynomially bounded nonnegative step sizes; the dimension-uniform theorem also uses control and rate constants shared across dimensions. Within this class, three questions remain: how the gap between the one-dimensional barrier ( 1 + a ) β p (1+a)\beta_p ( 1 + a ) β p and the dimension-uniform barrier max { β p , a } \max\{\beta_p,a\} max { β p , a } closes, which rates are attainable for a > β p a>\beta_p a > β p , also under a two-sided condition 1 − β t ≍ t − a 1-\beta_t\asymp t^{-a} 1 − β t ≍ t − a , and how the confidence factor of a fixed-time exponent above max { β p , a } \max\{\beta_p,a\} max { β p , a } grows under shared constants. Lower bounds for general update directions are also open. Concurrent analyses for a known horizon cover Lipschitz, strongly star-convex, composite, and constrained problems [36 , 27 ] ; horizon-free counterparts of these settings, and of non-Euclidean or ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -smooth objectives (El Bakkali El Kadi et al., 2026), are further directions.
Deterministic Last-Iterate Calculations
This appendix proves the one-step inequality and the recursive potential (Lemma 11 ).
One Inexact Gradient Step
Lemma 10 (Inexact smooth convex step). Let f f f be convex and L L L -smooth. Fix x , z , e ∈ R d x,z,e\in\mathbb{R}^d x , z , e ∈ R d , 0 < γ ≤ 1 / ( 2 L ) 0<\gamma\le1/(2L) 0 < γ ≤ 1/ ( 2 L ) , and y = x − γ ( ∇ f ( x ) + e ) y=x-\gamma(\nabla f(x)+e) y = x − γ ( ∇ f ( x ) + e ) . Then
γ [ f ( y ) − f ( z ) ] + 1 2 ∥ y − z ∥ 2 ≤ 1 2 ∥ x − z ∥ 2 + γ ⟨ e , z − x ⟩ + γ 2 ∥ e ∥ 2 . (23) \gamma[f(y)-f(z)]+\frac{1}{2}\lVert y-z\rVert^2\le\frac{1}{2}\lVert x-z\rVert^2+\gamma\langle e,z-x\rangle+\gamma^2\lVert e\rVert^2. \tag*{(23)} γ [ f ( y ) − f ( z )] + 2 1 ∥ y − z ∥ 2 ≤ 2 1 ∥ x − z ∥ 2 + γ ⟨ e , z − x ⟩ + γ 2 ∥ e ∥ 2 . (23)
Proof Smoothness, convexity and the three-point norm identity give
γ [ f ( y ) − f ( z ) ] + 1 2 ∥ y − z ∥ 2 ≤ 1 2 ∥ x − z ∥ 2 + γ ⟨ e , z − x ⟩ − 1 − γ L 2 ∥ x − y ∥ 2 + γ ⟨ e , x − y ⟩ . \gamma[f(y)-f(z)]+\frac{1}{2}\lVert y-z\rVert^2\le\frac{1}{2}\lVert x-z\rVert^2+\gamma\langle e,z-x\rangle-\frac{1-\gamma L}{2}\lVert x-y\rVert^2+\gamma\langle e,x-y\rangle. γ [ f ( y ) − f ( z )] + 2 1 ∥ y − z ∥ 2 ≤ 2 1 ∥ x − z ∥ 2 + γ ⟨ e , z − x ⟩ − 2 1 − γ L ∥ x − y ∥ 2 + γ ⟨ e , x − y ⟩ .
Use γ ⟨ e , x − y ⟩ ≤ γ 2 ∥ e ∥ 2 + ∥ x − y ∥ 2 / 4 \gamma\langle e,x-y\rangle\le\gamma^2\lVert e\rVert^2+\lVert x-y\rVert^2/4 γ ⟨ e , x − y ⟩ ≤ γ 2 ∥ e ∥ 2 + ∥ x − y ∥ 2 /4 and γ L ≤ 1 / 2 \gamma L\le1/2 γ L ≤ 1/2 . ■
A Recursively Averaged Potential
Potential functions are a standard tool for analyzing first-order methods [62 ] . Following the comparator weighted by inverse tail sums in [69 ] and (Liu and Zhou, 2024), we express the potential recursively. With boundary mass ζ = 0 \zeta=0 ζ = 0 below, it is the tail-sum potential that Jiang et al. [27 ] use to prove Theorem 1; the boundary mass ζ > 0 \zeta>0 ζ > 0 , which keeps the weights bounded without a horizon, is what our unknown-horizon results add. For any positive steps η t ≤ 1 / ( 2 L ) \eta_t\le1/(2L) η t ≤ 1/ ( 2 L ) and arbitrary realized errors, consider
x t + 1 = x t − η t ( ∇ f ( x t ) + e t ) . x_{t+1}=x_t-\eta_t(\nabla f(x_t)+e_t). x t + 1 = x t − η t ( ∇ f ( x t ) + e t ) .
For a deterministic analysis horizon T T T and boundary mass ζ ≥ 0 \zeta\ge0 ζ ≥ 0 , set
G t = f ( x t ) − f ⋆ , S t = ∑ r = t T η r , U t = ζ + S t , W = U 1 , θ t = η t / U t , G_t=f(x_t)-f^\star,\qquad S_t=\sum_{r=t}^{T}\eta_r,\qquad U_t=\zeta+S_t,\qquad W=U_1,\qquad\theta_t=\eta_t/U_t, G t = f ( x t ) − f ⋆ , S t = r = t ∑ T η r , U t = ζ + S t , W = U 1 , θ t = η t / U t ,
with S 0 = S 1 S_0=S_1 S 0 = S 1 , S T + 1 = 0 S_{T+1}=0 S T + 1 = 0 and U 0 = U 1 U_0=U_1 U 0 = U 1 . All denominators below involve only U 0 , … , U T > 0 U_0,\ldots,U_T>0 U 0 , … , U T > 0 , so ζ = 0 \zeta=0 ζ = 0 is allowed. Starting from z 0 = z 1 = x ⋆ z_0=z_1=x^\star z 0 = z 1 = x ⋆ and A 0 = 0 A_0=0 A 0 = 0 , define only for the analysis
z t + 1 = ( 1 − θ t ) z t + θ t x t + 1 , A t = ( 1 − θ t ) A t − 1 + θ t G t + 1 . z_{t+1}=(1-\theta_t)z_t+\theta_t x_{t+1},\qquad A_t=(1-\theta_t)A_{t-1}+\theta_tG_{t+1}. z t + 1 = ( 1 − θ t ) z t + θ t x t + 1 , A t = ( 1 − θ t ) A t − 1 + θ t G t + 1 .
Let
d t = z t − 1 − x t , H 0 = 1 2 ∥ d 1 ∥ 2 , H t = W 2 U t ∥ z t − x t + 1 ∥ 2 , d_t=z_{t-1}-x_t,\qquad H_0=\frac{1}{2}\lVert d_1\rVert^2,\qquad H_t=\frac{W}{2U_t}\lVert z_t-x_{t+1}\rVert^2, d t = z t − 1 − x t , H 0 = 2 1 ∥ d 1 ∥ 2 , H t = 2 U t W ∥ z t − x t + 1 ∥ 2 ,
q t = 2 W η t 2 U t , h t = W η t U t − 1 d t . q_t=\frac{2W\eta_t^2}{U_t},\qquad h_t=\frac{W\eta_t}{U_{t-1}}d_t. q t = U t 2 W η t 2 , h t = U t − 1 W η t d t .
In particular H T H_T H T uses z T − x T + 1 z_T-x_{T+1} z T − x T + 1 , not z T + 1 − x T + 1 z_{T+1}-x_{T+1} z T + 1 − x T + 1 .
Lemma 11 (Unified recursive potential). For every m ≤ T m \le T m ≤ T , A m , H m ≥ 0 A_m, H_m \ge0 A m , H m ≥ 0 and
W A m + H m ≤ R 2 2 + ∑ t ≤ m q t ∥ e t ∥ 2 + ∑ t ≤ m ⟨ e t , h t ⟩ . (24) W A_m + H_m \le\frac{R^2}{2} + \sum_{t \le m} q_t \lVert e_t\rVert^2 + \sum_{t \le m} \langle e_t,h_t\rangle. \tag*{(24)} W A m + H m ≤ 2 R 2 + t ≤ m ∑ q t ∥ e t ∥ 2 + t ≤ m ∑ ⟨ e t , h t ⟩ . (24) The full terminal potential also gives
G T + 1 ≤ ( 1 + L ζ 2 ζ + η T ) W A T + H T W G_{T+1} \le\left(1 + \frac{L\zeta^2}{\zeta+ \eta_T}\right)\frac{W A_T + H_T}{W} G T + 1 ≤ ( 1 + ζ + η T L ζ 2 ) W W A T + H T ≤ ( 1 + L ζ ) W A T + H T W . (25) \le(1 + L\zeta)\frac{W A_T + H_T}{W}. \tag*{(25)} ≤ ( 1 + L ζ ) W W A T + H T . (25) In particular, ζ = 0 \zeta= 0 ζ = 0 gives A T = G T + 1 A_T = G_{T+1} A T = G T + 1 , while ζ = 1 \zeta= 1 ζ = 1 keeps the inverse tail weights bounded.
Proof. Convexity and the synchronized recursions give f ( z t ) − f ⋆ ≤ A t − 1 f(z_t) - f^\star\le A_{t-1} f ( z t ) − f ⋆ ≤ A t − 1 by induction. Thus A t − A t − 1 ≤ θ t [ f ( x t + 1 ) − f ( z t ) ] A_t - A_{t-1} \le\theta_t[f(x_{t+1}) - f(z_t)] A t − A t − 1 ≤ θ t [ f ( x t + 1 ) − f ( z t )] . Also z t − x t = ( U t / U t − 1 ) d t z_t - x_t = (U_t/U_{t-1})d_t z t − x t = ( U t / U t − 1 ) d t , including t = 1 t = 1 t = 1 by convention. Multiply (23) of Lemma 10 , with z = z t z = z_t z = z t and γ = η t \gamma= \eta_t γ = η t , by W / U t W/U_t W / U t to obtain
W A t + H t ≤ W A t − 1 + U t U t − 1 H t − 1 + q t 2 ∥ e t ∥ 2 + ⟨ e t , h t ⟩ . W A_t + H_t \le W A_{t-1} + \frac{U_t}{U_{t-1}}H_{t-1} + \frac{q_t}{2}\lVert e_t\rVert^2 + \langle e_t,h_t\rangle. W A t + H t ≤ W A t − 1 + U t − 1 U t H t − 1 + 2 q t ∥ e t ∥ 2 + ⟨ e t , h t ⟩ .
Since U t ≤ U t − 1 U_t \le U_{t-1} U t ≤ U t − 1 , summation proves (24) , using q t / 2 ≤ q t q_t/2 \le q_t q t /2 ≤ q t . Nonnegativity follows from the definitions. The final synchronized update gives f ( z T + 1 ) − f ⋆ ≤ A T f(z_{T+1}) - f^\star\le A_T f ( z T + 1 ) − f ⋆ ≤ A T and
∥ z T + 1 − x T + 1 ∥ 2 = 2 ζ 2 H T W ( ζ + η T ) . \lVert z_{T+1} - x_{T+1}\rVert^2 = \frac{2\zeta^2 H_T}{W(\zeta+ \eta_T)}. ∥ z T + 1 − x T + 1 ∥ 2 = W ( ζ + η T ) 2 ζ 2 H T .
By L L L -smoothness evaluated at z − ∇ f ( z ) / L z - \nabla f(z)/L z − ∇ f ( z ) / L , we have ∥ ∇ f ( z ) ∥ 2 ≤ 2 L [ f ( z ) − f ⋆ ] \lVert\nabla f(z)\rVert^2 \le2L[f(z) - f^\star] ∥ ∇ f ( z ) ∥ 2 ≤ 2 L [ f ( z ) − f ⋆ ] . Thus, writing G ( x ) = f ( x ) − f ⋆ G(x) = f(x) - f^\star G ( x ) = f ( x ) − f ⋆ and ρ = L ζ 2 / ( ζ + η T ) \rho= L\zeta^2/(\zeta+ \eta_T) ρ = L ζ 2 / ( ζ + η T ) , smoothness and Cauchy–Schwarz give
G ( x T + 1 ) ≤ ( G ( z T + 1 ) + L / 2 ∥ x T + 1 − z T + 1 ∥ ) 2 ≤ ( 1 + ρ ) ( A T + H T / W ) . G(x_{T+1}) \le\left(\sqrt{G(z_{T+1})} + \sqrt{L/2}\lVert x_{T+1} - z_{T+1}\rVert\right)^2 \le(1+\rho)(A_T + H_T/W). G ( x T + 1 ) ≤ ( G ( z T + 1 ) + L /2 ∥ x T + 1 − z T + 1 ∥ ) 2 ≤ ( 1 + ρ ) ( A T + H T / W ) .
Since ρ ≤ L ζ \rho\le L\zeta ρ ≤ L ζ , this proves (25) . If ζ = 0 \zeta= 0 ζ = 0 , θ T = 1 \theta_T = 1 θ T = 1 also gives A T = G T + 1 A_T = G_{T+1} A T = G T + 1 directly. ■
The proofs of Theorems 2 and 5 take ζ = 1 \zeta= 1 ζ = 1 ; ζ = 0 \zeta= 0 ζ = 0 gives W = S 1 W = S_1 W = S 1 and U t = S t U_t = S_t U t = S t .
Conditional Clipping Estimates
Lemma 12 (Bias and second moment after clipping). Conditionally on a σ \sigma σ -field G \mathcal{G} G , suppose μ \mu μ is measurable, E [ g ∣ G ] = μ \mathbb{E}[g \mid\mathcal{G}] = \mu E [ g ∣ G ] = μ , and E [ ∥ g − μ ∥ p ∣ G ] ≤ σ p \mathbb{E}[\lVert g - \mu\rVert^p \mid\mathcal{G}] \le\sigma^p E [∥ g − μ ∥ p ∣ G ] ≤ σ p , for 1 < p ≤ 2 1 < p \le2 1 < p ≤ 2 . If ∥ μ ∥ ≤ λ / 2 \lVert\mu\rVert\le\lambda/2 ∥ μ ∥ ≤ λ /2 , set
c = clip ( g , λ ) , e = c − μ , b = E [ e ∣ G ] , u = e − b . c = \operatorname{clip}(g,\lambda), \qquad e = c - \mu, \qquad b = \mathbb{E}[e \mid\mathcal{G}], \qquad u = e - b. c = clip ( g , λ ) , e = c − μ , b = E [ e ∣ G ] , u = e − b . Then
∥ e ∥ ≤ min { ∥ g − μ ∥ , 3 λ / 2 } , ∥ u ∥ ≤ 2 λ , \lVert e\rVert\le\min\{\lVert g-\mu\rVert,3\lambda/2\}, \qquad\lVert u\rVert\le2\lambda, ∥ e ∥ ≤ min {∥ g − μ ∥ , 3 λ /2 } , ∥ u ∥ ≤ 2 λ , ∥ b ∥ ≤ 2 p − 1 σ p λ 1 − p ≤ 2 σ p λ 1 − p , \lVert b\rVert\le2^{p-1}\sigma^p\lambda^{1-p} \le2\sigma^p\lambda^{1-p}, ∥ b ∥ ≤ 2 p − 1 σ p λ 1 − p ≤ 2 σ p λ 1 − p , E [ ∥ e ∥ 2 ∣ G ] ≤ ( 3 λ / 2 ) 2 − p σ p ≤ 2 σ p λ 2 − p , E [ ∥ u ∥ 2 ∣ G ] ≤ E [ ∥ e ∥ 2 ∣ G ] . \mathbb{E}[\lVert e\rVert^2 \mid\mathcal{G}] \le(3\lambda/2)^{2-p}\sigma^p \le2\sigma^p\lambda^{2-p}, \qquad\mathbb{E}[\lVert u\rVert^2 \mid\mathcal{G}] \le\mathbb{E}[\lVert e\rVert^2 \mid\mathcal{G}]. E [∥ e ∥ 2 ∣ G ] ≤ ( 3 λ /2 ) 2 − p σ p ≤ 2 σ p λ 2 − p , E [∥ u ∥ 2 ∣ G ] ≤ E [∥ e ∥ 2 ∣ G ] .
Proof. These are the standard clipping bounds (cf. Sadiev et al., [56 ] ); the following Euclidean calculation records the sharper constants used here. Write P = clip ( ⋅ , λ ) P=\operatorname{clip}(\cdot,\lambda) P = clip ( ⋅ , λ ) and ξ = g − μ \xi=g-\mu ξ = g − μ . Since P μ = μ P\mu=\mu P μ = μ , nonexpansiveness and the clipping radius give
∥ e ∥ ≤ min { ∥ ξ ∥ , 3 λ / 2 } , ∥ u ∥ = ∥ P g − E [ P g ∣ G ] ∥ ≤ 2 λ . \lVert e\rVert\le\min\{\lVert\xi\rVert,3\lambda/2\},\qquad\lVert u\rVert=\lVert Pg-\mathbb{E}[Pg\mid\mathcal{G}]\rVert\le2\lambda. ∥ e ∥ ≤ min {∥ ξ ∥ , 3 λ /2 } , ∥ u ∥ = ∥ P g − E [ P g ∣ G ]∥ ≤ 2 λ .
Also ∥ P g − g ∥ ≤ ∥ ξ ∥ 1 { ∥ ξ ∥ > λ / 2 } \lVert Pg-g\rVert\le\lVert\xi\rVert\mathbf{1}_{\{\lVert\xi\rVert>\lambda/2\}} ∥ P g − g ∥ ≤ ∥ ξ ∥ 1 {∥ ξ ∥ > λ /2 } , so
∥ b ∥ = ∥ E [ P g − g ∣ G ] ∥ ≤ ( λ / 2 ) 1 − p E [ ∥ ξ ∥ p ∣ G ] . \lVert b\rVert=\lVert\mathbb{E}[Pg-g\mid\mathcal{G}]\rVert\le(\lambda/2)^{1-p}\mathbb{E}[\lVert\xi\rVert^{p}\mid\mathcal{G}]. ∥ b ∥ = ∥ E [ P g − g ∣ G ]∥ ≤ ( λ /2 ) 1 − p E [∥ ξ ∥ p ∣ G ] .
Finally,
E [ ∥ u ∥ 2 ∣ G ] ≤ E [ ∥ e ∥ 2 ∣ G ] ≤ ( 3 λ / 2 ) 2 − p E [ ∥ ξ ∥ p ∣ G ] , \mathbb{E}[\lVert u\rVert^{2}\mid\mathcal{G}]\le\mathbb{E}[\lVert e\rVert^{2}\mid\mathcal{G}]\le(3\lambda/2)^{2-p}\mathbb{E}[\lVert\xi\rVert^{p}\mid\mathcal{G}], E [∥ u ∥ 2 ∣ G ] ≤ E [∥ e ∥ 2 ∣ G ] ≤ ( 3 λ /2 ) 2 − p E [∥ ξ ∥ p ∣ G ] ,
where the first inequality is conditional variance reduction by centering.
The next decomposition imposes no bound on the true gradient. Related Lipschitz estimates for the clipping factor appear in Tian et al. [63 ] , under bounded noise. We prove the conditional p p p -moment bounds used here.
Lemma 13. (Conditional mean and variance after clipping). Conditionally on a σ \sigma σ -field G \mathcal{G} G , let μ \mu μ be measurable, E [ g ∣ G ] = μ \mathbb{E}[g\mid\mathcal{G}]=\mu E [ g ∣ G ] = μ , and E [ ∥ g − μ ∥ p ∣ G ] ≤ σ p \mathbb{E}[\lVert g-\mu\rVert^{p}\mid\mathcal{G}]\le\sigma^{p} E [∥ g − μ ∥ p ∣ G ] ≤ σ p . For deterministic or G \mathcal{G} G -measurable λ > 0 \lambda>0 λ > 0 , put
α ( v ) = { min { 1 , λ / ∥ v ∥ } , v ≠ 0 , 1 , v = 0 , C = clip ( g , λ ) , A = E [ α ( g ) ∣ G ] . \alpha(v)=
\begin{cases}
\min\{1,\lambda/\lVert v\rVert\}, & v\ne0,\\
1, & v=0,
\end{cases}
\qquad C=\operatorname{clip}(g,\lambda),\qquad A=\mathbb{E}[\alpha(g)\mid\mathcal{G}]. α ( v ) = { min { 1 , λ / ∥ v ∥} , 1 , v = 0 , v = 0 , C = clip ( g , λ ) , A = E [ α ( g ) ∣ G ] . Then 0 ≤ A ≤ 1 0\le A\le1 0 ≤ A ≤ 1 and
E [ C ∣ G ] = A μ + ε , ∥ ε ∥ ≤ σ p λ 1 − p . \mathbb{E}[C\mid\mathcal{G}]=A\mu+\varepsilon,\qquad\lVert\varepsilon\rVert\le\sigma^{p}\lambda^{1-p}. E [ C ∣ G ] = A μ + ε , ∥ ε ∥ ≤ σ p λ 1 − p . Moreover, u = C − E [ C ∣ G ] u=C-\mathbb{E}[C\mid\mathcal{G}] u = C − E [ C ∣ G ] satisfies
∥ u ∥ ≤ 2 λ , E [ ∥ u ∥ 2 ∣ G ] ≤ ( 2 λ ) 2 − p σ p . \lVert u\rVert\le2\lambda,\qquad\mathbb{E}[\lVert u\rVert^{2}\mid\mathcal{G}]\le(2\lambda)^{2-p}\sigma^{p}. ∥ u ∥ ≤ 2 λ , E [∥ u ∥ 2 ∣ G ] ≤ ( 2 λ ) 2 − p σ p . In particular, if σ ≤ 1 \sigma\le1 σ ≤ 1 and λ ≥ 4 \lambda\ge4 λ ≥ 4 , then d = C − A μ = ε + u d=C-A\mu=\varepsilon+u d = C − A μ = ε + u satisfies
∥ d ∥ ≤ 3 λ , E [ ∥ d ∥ 2 ∣ G ] ≤ 4 λ 2 − p . \lVert d\rVert\le3\lambda,\qquad\mathbb{E}[\lVert d\rVert^{2}\mid\mathcal{G}]\le4\lambda^{2-p}. ∥ d ∥ ≤ 3 λ , E [∥ d ∥ 2 ∣ G ] ≤ 4 λ 2 − p .
Proof. The scalar function r ↦ min { 1 , λ / r } r\mapsto\min\{1,\lambda/r\} r ↦ min { 1 , λ / r } , extended by 1 1 1 at zero, is 1 / λ 1/\lambda 1/ λ -Lipschitz on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) and takes values in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Writing ξ = g − μ \xi=g-\mu ξ = g − μ and using its conditional mean zero gives
ε = E [ α ( g ) ξ ∣ G ] = E [ ( α ( g ) − α ( μ ) ) ξ ∣ G ] , \varepsilon=\mathbb{E}[\alpha(g)\xi\mid\mathcal{G}]=\mathbb{E}[(\alpha(g)-\alpha(\mu))\xi\mid\mathcal{G}], ε = E [ α ( g ) ξ ∣ G ] = E [( α ( g ) − α ( μ )) ξ ∣ G ] ,
∥ ε ∥ ≤ E [ min { ∥ ξ ∥ / λ , 1 } ∥ ξ ∥ ∣ G ] ≤ λ 1 − p E [ ∥ ξ ∥ p ∣ G ] . \lVert\varepsilon\rVert\le\mathbb{E}[\min\{\lVert\xi\rVert/\lambda,1\}\lVert\xi\rVert\mid\mathcal{G}]\le\lambda^{1-p}\mathbb{E}[\lVert\xi\rVert^{p}\mid\mathcal{G}]. ∥ ε ∥ ≤ E [ min {∥ ξ ∥ / λ , 1 } ∥ ξ ∥ ∣ G ] ≤ λ 1 − p E [∥ ξ ∥ p ∣ G ] .
The final pointwise inequality follows separately for ∥ ξ ∥ ≤ λ \lVert\xi\rVert\le\lambda ∥ ξ ∥ ≤ λ and ∥ ξ ∥ > λ \lVert\xi\rVert>\lambda ∥ ξ ∥ > λ , using p ≤ 2 p\le2 p ≤ 2 and p > 1 p>1 p > 1 , respectively. For the projection P = clip ( ⋅ , λ ) P=\operatorname{clip}(\cdot,\lambda) P = clip ( ⋅ , λ ) , variance reduction and nonexpansiveness give
E [ ∥ u ∥ 2 ∣ G ] ≤ E [ ∥ P g − P μ ∥ 2 ∣ G ] ≤ E [ min { ∥ ξ ∥ , 2 λ } 2 ∣ G ] ≤ ( 2 λ ) 2 − p σ p . \mathbb{E}[\lVert u\rVert^{2}\mid\mathcal{G}]\le\mathbb{E}[\lVert Pg-P\mu\rVert^{2}\mid\mathcal{G}]\le\mathbb{E}[\min\{\lVert\xi\rVert,2\lambda\}^{2}\mid\mathcal{G}]\le(2\lambda)^{2-p}\sigma^{p}. E [∥ u ∥ 2 ∣ G ] ≤ E [∥ P g − P μ ∥ 2 ∣ G ] ≤ E [ min {∥ ξ ∥ , 2 λ } 2 ∣ G ] ≤ ( 2 λ ) 2 − p σ p .
Both C C C and its mean belong to the radius-λ \lambda λ ball, proving the range. Under the last assumptions, ∥ ε ∥ ≤ λ 1 − p ≤ λ \lVert\varepsilon\rVert\le\lambda^{1-p}\le\lambda ∥ ε ∥ ≤ λ 1 − p ≤ λ , so ∥ d ∥ ≤ 3 λ \lVert d\rVert\le3\lambda ∥ d ∥ ≤ 3 λ ; and
E [ ∥ d ∥ 2 ∣ G ] = E [ ∥ u ∥ 2 ∣ G ] + ∥ ε ∥ 2 ≤ 2 λ 2 − p + λ 2 − 2 p ≤ 4 λ 2 − p . \mathbb{E}[\lVert d\rVert^{2}\mid\mathcal{G}]=\mathbb{E}[\lVert u\rVert^{2}\mid\mathcal{G}]+\lVert\varepsilon\rVert^{2}\le2\lambda^{2-p}+\lambda^{2-2p}\le4\lambda^{2-p}. E [∥ d ∥ 2 ∣ G ] = E [∥ u ∥ 2 ∣ G ] + ∥ ε ∥ 2 ≤ 2 λ 2 − p + λ 2 − 2 p ≤ 4 λ 2 − p .
Elementary Maximal Concentration Bounds
We record a standard scalar concentration bound and one energy estimate used throughout the high-probability proofs. Both use only predictable local bounds.
Lemma 14 (Maximal inequality for bounded martingale increments). Let X t X_t X t be adapted to ( F t ) t = 0 T (\mathcal{F}_t)_{t=0}^{T} ( F t ) t = 0 T , with E t − 1 X t = 0 \mathbb{E}_{t-1}X_t=0 E t − 1 X t = 0 , ∣ X t ∣ ≤ b |X_t|\le b ∣ X t ∣ ≤ b almost surely, and
∑ t = 1 T E t − 1 X t 2 ≤ v almost surely . \sum_{t=1}^{T}\mathbb{E}_{t-1}X_t^2\le v \quad\text{almost surely}. t = 1 ∑ T E t − 1 X t 2 ≤ v almost surely . where b , v ≥ 0 b,v\ge0 b , v ≥ 0 are deterministic. For any ℓ > 0 \ell>0 ℓ > 0 ,
P { max 1 ≤ m ≤ T ∑ t = 1 m X t > 2 v ℓ + 2 b ℓ } ≤ e − ℓ . \mathbb{P}\left\{\max_{1\le m\le T}\sum_{t=1}^{m}X_t>2\sqrt{v\ell}+2b\ell\right\}\le e^{-\ell}. P { 1 ≤ m ≤ T max t = 1 ∑ m X t > 2 v ℓ + 2 b ℓ } ≤ e − ℓ .
Proof. The maximal form of Freedman’s inequality [19 Theorem 1.6] , after scaling the increments, gives
P { max m ≤ T ∑ t ≤ m X t > s } ≤ exp { − s 2 2 ( v + b s ) } . \mathbb{P}\left\{\max_{m\le T}\sum_{t\le m}X_t>s\right\}\le\exp\left\{-\frac{s^2}{2(v+bs)}\right\}. P { m ≤ T max t ≤ m ∑ X t > s } ≤ exp { − 2 ( v + b s ) s 2 } .
Set s = 2 v ℓ + 2 b ℓ s=2\sqrt{v\ell}+2b\ell s = 2 v ℓ + 2 b ℓ ; then s 2 ≥ 2 ℓ ( v + b s ) s^2\ge2\ell(v+bs) s 2 ≥ 2 ℓ ( v + b s ) . Zero budgets follow by continuity. ■
Lemma 15 (A common energy bound). Let e t e_t e t be integrable and adapted, P 0 , … , P N ≥ 0 P_0,\ldots,P_N\ge0 P 0 , … , P N ≥ 0 adapted, J t ∈ { 0 , 1 } J_t\in\{0,1\} J t ∈ { 0 , 1 } predictable and nonincreasing, and E \mathcal{E} E an event, for instance E = Ω \mathcal{E}=\Omega E = Ω . On E ∩ { J m = 1 } \mathcal{E}\cap\{J_m=1\} E ∩ { J m = 1 } , suppose
P m ≤ P 0 + ∑ t ≤ m { a t ∥ e t ∥ 2 + ⟨ e t , w t ⟩ } , P_m\le P_0+\sum_{t\le m}\{a_t\|e_t\|^2+\langle e_t,w_t\rangle\}, P m ≤ P 0 + t ≤ m ∑ { a t ∥ e t ∥ 2 + ⟨ e t , w t ⟩} , where w t w_t w t is predictable with ∥ w t ∥ ≤ s t P t − 1 \|w_t\|\le s_t\sqrt{P_{t-1}} ∥ w t ∥ ≤ s t P t − 1 on J t = 1 J_t=1 J t = 1 , and a t , s t ≥ 0 a_t,s_t\ge0 a t , s t ≥ 0 are deterministic. On J t = 1 J_t=1 J t = 1 , assume ∥ E t − 1 e t ∥ ≤ B t \|\mathbb{E}_{t-1}e_t\|\le B_t ∥ E t − 1 e t ∥ ≤ B t , E t − 1 ∥ e t ∥ 2 ≤ V t \mathbb{E}_{t-1}\|e_t\|^2\le V_t E t − 1 ∥ e t ∥ 2 ≤ V t , ∥ e t ∥ ≤ M t \|e_t\|\le M_t ∥ e t ∥ ≤ M t , and ∥ e t − E t − 1 e t ∥ ≤ U t \|e_t-\mathbb{E}_{t-1}e_t\|\le U_t ∥ e t − E t − 1 e t ∥ ≤ U t , with deterministic bounds. Put
A = ∑ t a t V t , K 0 = sup t a t M t 2 , B 0 = ∑ t s t B t , V 0 = ∑ t s t 2 V t , J 0 = sup t s t U t . A=\sum_t a_tV_t,\qquad K_0=\sup_t a_tM_t^2,\qquad B_0=\sum_t s_tB_t,\qquad V_0=\sum_t s_t^2V_t,\qquad J_0=\sup_t s_tU_t. A = t ∑ a t V t , K 0 = t sup a t M t 2 , B 0 = t ∑ s t B t , V 0 = t ∑ s t 2 V t , J 0 = t sup s t U t . For p 0 ≥ 0 p_0\ge0 p 0 ≥ 0 and q > 0 q>0 q > 0 , define
C = p 0 + A + 2 K 0 A q + 2 K 0 q , D = B 0 + 2 V 0 q + 2 J 0 q . C=p_0+A+2\sqrt{K_0Aq}+2K_0q,\qquad D=B_0+2\sqrt{V_0q}+2J_0q. C = p 0 + A + 2 K 0 A q + 2 K 0 q , D = B 0 + 2 V 0 q + 2 J 0 q . Except on probability e − q e^{-q} e − q , on E \mathcal{E} E , simultaneously for every m m m with J m = 1 J_m=1 J m = 1 and P 0 ≤ p 0 P_0\le p_0 P 0 ≤ p 0 ,
P m ≤ ( C + D ) 2 . P_m\le(\sqrt{C}+D)^2. P m ≤ ( C + D ) 2 . The initial state may be random; the conclusion extends to N = ∞ N=\infty N = ∞ if the budgets are finite.
Proof. Set H = ( C + D ) 2 H=(\sqrt{C}+D)^2 H = ( C + D ) 2 and I t = J t 1 { P 0 ≤ p 0 , max j < t P j ≤ H } I_t=J_t\mathbf{1}_{\{P_0\le p_0,\ \max_{j<t}P_j\le H\}} I t = J t 1 { P 0 ≤ p 0 , m a x j < t P j ≤ H } , a predictable indicator that does not involve E \mathcal{E} E . Center only stopped quantities: Y t = I t ∥ e t ∥ Y_t=I_t\|e_t\| Y t = I t ∥ e t ∥ , m t = E t − 1 Y t m_t=\mathbb{E}_{t-1}Y_t m t = E t − 1 Y t , and U t ′ = I t e t − E t − 1 ( I t e t ) U'_t=I_te_t-\mathbb{E}_{t-1}(I_te_t) U t ′ = I t e t − E t − 1 ( I t e t ) . The martingale increments X t = a t ( Y t − m t ) + ⟨ U t ′ , w t ⟩ X_t=a_t(Y_t-m_t)+\langle U'_t,w_t\rangle X t = a t ( Y t − m t ) + ⟨ U t ′ , w t ⟩ satisfy
∣ X t ∣ ≤ K 0 + H J 0 , ∑ t E t − 1 X t 2 ≤ K 0 A + H V 0 . |X_t|\le K_0+\sqrt{H}J_0,\qquad\sqrt{\sum_t\mathbb{E}_{t-1}X_t^2}\le\sqrt{K_0A}+\sqrt{HV_0}. ∣ X t ∣ ≤ K 0 + H J 0 , t ∑ E t − 1 X t 2 ≤ K 0 A + H V 0 .
Indeed, conditional variance reduction and the conditional L 2 L^2 L 2 triangle inequality give
E t − 1 X t 2 ≤ I t V t ( a t M t + s t H ) ; \sqrt{\mathbb{E}_{t-1}X_t^2} \le I_t\sqrt{V_t}(a_tM_t+s_t\sqrt{H}); E t − 1 X t 2 ≤ I t V t ( a t M t + s t H ) ;
then use the triangle inequality for the deterministic sequence of bounds. By Lemma 14, except on probability e − q e^{-q} e − q , every partial sum of the X t X_t X t is at most 2 K 0 A q + 2 K 0 q + H ( 2 V 0 q + 2 J 0 q ) 2\sqrt{K_0Aq}+2K_0q+\sqrt{H}(2\sqrt{V_0q}+2J_0q) 2 K 0 A q + 2 K 0 q + H ( 2 V 0 q + 2 J 0 q ) . On this event and on P 0 ≤ p 0 P_0\le p_0 P 0 ≤ p 0 , the mean and bias budgets give, for every m m m ,
P 0 + ∑ t ≤ m I t { a t ∥ e t ∥ 2 + ⟨ e t , w t ⟩ } ≤ C + H D ≤ H , P_0+\sum_{t\le m} I_t\{a_t\lVert e_t\rVert^2+\langle e_t,w_t\rangle\}\le C+\sqrt{H}D\le H, P 0 + t ≤ m ∑ I t { a t ∥ e t ∥ 2 + ⟨ e t , w t ⟩} ≤ C + H D ≤ H ,
since H − C − H D = C D H-C-\sqrt{H}D=\sqrt{C}D H − C − H D = C D . Suppose that, on this event and on E \mathcal{E} E , some m m m with J m = 1 J_m=1 J m = 1 and P 0 ≤ p 0 P_0\le p_0 P 0 ≤ p 0 has P m > H P_m>H P m > H , and take the first such m m m . Then I t = 1 I_t=1 I t = 1 for every t ≤ m t\le m t ≤ m , so the assumed recursion bounds P m P_m P m by the left side above, a contradiction. Taking the union over finite prefixes yields the claim for N = ∞ N=\infty N = ∞ . ■
Clipped versus Unclipped SGD
Remark 16 (Clipping and the cube-root barrier). In concurrent and independent work, Anonymous [1 ] prove that at p = 2 p=2 p = 2 , for every positive deterministic schedule of unclipped step sizes and every r > 1 / 3 r>1/3 r > 1/3 , some finite-variance instance makes ( t + 1 ) r ( f ( x t ) − f ⋆ ) (t+1)^r(f(x_t)-f^\star) ( t + 1 ) r ( f ( x t ) − f ⋆ ) unbounded almost surely. We first check that their theorem also bounds the time-uniform exponent of unclipped SGD on our class, and then compare it with clipping. Fix any positive deterministic schedule of unclipped step sizes, r ′ > 1 / 3 r'>1/3 r ′ > 1/3 , and finite C > 0 C>0 C > 0 , m ≥ 0 m\ge0 m ≥ 0 . Choose 1 / 3 < r < r ′ 1/3<r<r' 1/3 < r < r ′ . Their theorem supplies a fixed one-dimensional instance with L = 1 L=1 L = 1 , initial distance 1 / 2 1/2 1/2 , and an i.i.d. unbiased oracle with variance at most one, on which lim sup t → ∞ ( t + 1 ) r ( f ( x t ) − f ⋆ ) = ∞ \limsup_{t\to\infty}(t+1)^r(f(x_t)-f^\star)=\infty lim sup t → ∞ ( t + 1 ) r ( f ( x t ) − f ⋆ ) = ∞ almost surely. Their construction also satisfies our conditions on the sample losses: the shock branch has sample loss x 2 / 2 + ξ x x^2/2+\xi x x 2 /2 + ξ x , whose minimum is attained at − ξ -\xi − ξ , while the noiseless branch uses a convex smooth function with minimum at zero. Translating their initial point x 0 = 1 / 2 x_0=1/2 x 0 = 1/2 to our x 1 = 0 x_1=0 x 1 = 0 and shifting the time index preserves these properties, so both branches belong to our normalized p = 2 p=2 p = 2 class. On the event
f ( x t + 1 ) − f ⋆ ≤ C t − r ′ log m ( e t ) for all t ≥ 1 , f(x_{t+1})-f^\star\le Ct^{-r'}\log^m(et)\qquad\text{for all }t\ge1, f ( x t + 1 ) − f ⋆ ≤ C t − r ′ log m ( e t ) for all t ≥ 1 ,
the gap multiplied by t r t^r t r tends to zero, since t r − r ′ log m ( e t ) → 0 t^{r-r'}\log^m(et)\to0 t r − r ′ log m ( e t ) → 0 . The event therefore has probability zero. Thus, by their theorem, deterministic unclipped step sizes attain no time-uniform exponent above 1 / 3 1/3 1/3 on our class. In contrast, Theorem 2 attains β 2 = 2 / 5 \beta_2=2/5 β 2 = 2/5 with clipping, and Theorem 4 excludes every larger exponent for all gradient-only rules (Definition 3 ), including adaptive step sizes and clipping thresholds. Since clipping is a scalar response to the observed stochastic gradient, this resolves the time-uniform counterpart (at a fixed confidence level) of their question regarding adaptive step sizes: the exponent 2 / 5 2/5 2/5 is both attainable and optimal on our finite-variance class. Moreover, the almost sure consequence of Theorem 2 gives f ( x t + 1 ) − f ⋆ = O ( t − 2 / 5 log 4 t ) f(x_{t+1})-f^\star=O(t^{-2/5}\log^4 t) f ( x t + 1 ) − f ⋆ = O ( t − 2/5 log 4 t ) almost surely on every instance of our class, including theirs, so clipping also exceeds the almost sure exponent 1 / 3 1/3 1/3 of unclipped deterministic schedules.
Proofs for the Time-Uniform Lower Bound and Fixed-Time Guarantees
This appendix proves Proposition 17 and Theorems 4 and 6 ; Theorem 5 is proved in Appendix § 18 .§ 6 . For the lower bounds we fix p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] , L = R = σ = 1 L = R = \sigma= 1 L = R = σ = 1 , and x 1 = 0 x_1 = 0 x 1 = 0 . The rules are those of Definition 3 , and the same rule is used on every instance.
§ 4.2 outlines the argument. Its core is the following progress bound.
Proposition 17 (Progress bound under time-uniform guarantees). Fix ε ∈ ( 0 , 1 / 2 ) \varepsilon\in(0,1/2) ε ∈ ( 0 , 1/2 ) , N ≥ 1 N \ge1 N ≥ 1 , a rule of Definition 3 , and positive numbers b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N ; the rule may be tuned to a confidence level different from ε \varepsilon ε . Suppose that every instance in the class of Theorem 4 satisfies
P { f ( x t + 1 ) − f ⋆ ≤ b t for all 1 ≤ t ≤ N } ≥ 1 − ε . (26) \mathbb{P}\{f(x_{t+1}) - f^\star\le b_t\text{ for all }1 \le t \le N\} \ge1-\varepsilon. \tag*{(26)} P { f ( x t + 1 ) − f ⋆ ≤ b t for all 1 ≤ t ≤ N } ≥ 1 − ε . (26) Then for every μ ∈ ( 4 b N , 1 / 2 ] \mu\in(4b_N,1/2] μ ∈ ( 4 b N , 1/2 ] , with A = ( 2 μ ) − 1 / ( p − 1 ) A = (2\mu)^{-1/(p-1)} A = ( 2 μ ) − 1/ ( p − 1 ) and π = μ / A \pi= \mu/A π = μ / A ,
π ∑ t = 1 N ( μ + 2 b t ) ≥ 1 − 2 ε 2 . (27) \pi\sum_{t=1}^{N}(\mu+\sqrt{2b_t}) \ge\frac{1-2\varepsilon}{2}. \tag*{(27)} π t = 1 ∑ N ( μ + 2 b t ) ≥ 2 1 − 2 ε . (27)
Translated Targets with a Common I.I.D. Transcript
For 0 < μ ≤ 1 / 2 0 < \mu\le1/2 0 < μ ≤ 1/2 and y ∈ [ μ , 1 ] y \in[\mu,1] y ∈ [ μ , 1 ] , define
f μ , y ( x ) = 1 2 ( x − y + μ ) + 2 − μ x , f μ , y ⋆ = − μ y + μ 2 2 . f_{\mu,y}(x) = \frac{1}{2}(x-y+\mu)_{+}^{2}-\mu x,\qquad f_{\mu,y}^{\star}=-\mu y+\frac{\mu^{2}}{2}. f μ , y ( x ) = 2 1 ( x − y + μ ) + 2 − μx , f μ , y ⋆ = − μ y + 2 μ 2 .
Its derivative is − μ -\mu − μ on x ≤ y − μ x \le y-\mu x ≤ y − μ and x − y x-y x − y on x ≥ y − μ x \ge y-\mu x ≥ y − μ . These branches agree at the transition. Thus f μ , y f_{\mu,y} f μ , y is convex and globally 1-smooth, with unique minimizer y y y and initial distance at most one. Its gap is
f μ , y ( x ) − f μ , y ⋆ = { μ ( y − x ) − μ 2 / 2 , x ≤ y − μ , ( x − y ) 2 / 2 , x ≥ y − μ . (28) f_{\mu,y}(x)-f_{\mu,y}^{\star}=
\begin{cases}
\mu(y-x)-\mu^{2}/2, & x \le y-\mu,\\
(x-y)^{2}/2, & x \ge y-\mu.
\end{cases} \tag*{(28)} f μ , y ( x ) − f μ , y ⋆ = { μ ( y − x ) − μ 2 /2 , ( x − y ) 2 /2 , x ≤ y − μ , x ≥ y − μ . (28)
This objective is a reflected and translated one-sided Huber loss [25 ] , following the construction of Kornowski and Shamir [29 ] (Theorem 2 and Section 3.2); Tsai et al. [65 ] , Lemma 3.1 use a related overshoot at an arbitrary iteration. Those lower bounds concern exact gradients and prescribed step sizes. Against adaptive rules with i.i.d. noise, choosing the translation after observing a random trajectory would select the instance from the realized path, so we fix the translated family before the run and integrate, over the target location, the probabilities of failing at the first crossing. This accommodates adaptive step sizes and algorithmic randomness.
Set
A = ( 2 μ ) − 1 / ( p − 1 ) ≥ 1 , π = μ / A = 1 / ( 2 A p ) , Y t i.i.d. Bernoulli ( π ) . (29) A=(2\mu)^{-1/(p-1)}\ge1,\qquad\pi=\mu/A=1/(2A^{p}),\qquad Y_t\text{ i.i.d. Bernoulli}(\pi). \tag*{(29)} A = ( 2 μ ) − 1/ ( p − 1 ) ≥ 1 , π = μ / A = 1/ ( 2 A p ) , Y t i.i.d. Bernoulli ( π ) . (29)
Independently of the algorithm’s seed, each call draws a fresh Y t Y_t Y t . Use the sample loss
F μ , y ( x ; Y ) = 1 2 ( x − y + μ ) + 2 − A Y x = f μ , y ( x ) + ( μ − A Y ) x . (30) F_{\mu,y}(x;Y)=\frac{1}{2}(x-y+\mu)_{+}^{2}-AYx=f_{\mu,y}(x)+(\mu-AY)x. \tag*{(30)} F μ , y ( x ; Y ) = 2 1 ( x − y + μ ) + 2 − A Y x = f μ , y ( x ) + ( μ − A Y ) x . (30)
The additive noise ζ = μ − A Y \zeta=\mu-AY ζ = μ − A Y is centered, independent of the query and time, and has the same law for every y y y . Since μ ≤ A \mu\le A μ ≤ A ,
E ∣ ζ ∣ p = ( 1 − π ) μ p + π ( A − μ ) p ≤ μ p + μ A p − 1 ≤ 2 μ A p − 1 = 1. \mathbb{E}|\zeta|^{p}=(1-\pi)\mu^{p}+\pi(A-\mu)^{p}\le\mu^{p}+\mu A^{p-1}\le2\mu A^{p-1}=1. E ∣ ζ ∣ p = ( 1 − π ) μ p + π ( A − μ ) p ≤ μ p + μ A p − 1 ≤ 2 μ A p − 1 = 1.
Every sample loss is convex and globally 1-smooth, bounded below, and attains its minimum: for Y = 0 Y = 0 Y = 0 , every x ≤ y − μ x \le y - \mu x ≤ y − μ is a minimizer; for Y = 1 Y = 1 Y = 1 , the minimizer is y − μ + A y - \mu+ A y − μ + A . On the common left branch the raw gradient is exactly
g μ , y ( x ; Y ) = − A Y ( x ≤ y − μ ) . g_{\mu,y}(x;Y)=-AY \qquad(x\le y-\mu). g μ , y ( x ; Y ) = − A Y ( x ≤ y − μ ) .
The algorithm observes only these gradients and does not know y y y or f ∗ f^\ast f ∗ .
Proof of Proposition 17
We first isolate two lemmas used both here and for the momentum lower bound in Appendix § 19 : a crossing bound for monotone processes, and its application to the translated targets through a coupling at the first crossing.
Lemma 18 (Crossing bound for monotone processes). Let N ≥ 1 N \ge1 N ≥ 1 be an integer, let X 1 = 0 ≤ ⋯ ≤ X N + 1 X_1 = 0 \le\cdots\le X_{N+1} X 1 = 0 ≤ ⋯ ≤ X N + 1 be finite random variables, and put D t = X t + 1 − X t ≥ 0 D_t = X_{t+1} - X_t \ge0 D t = X t + 1 − X t ≥ 0 . For deterministic finite c > 0 c > 0 c > 0 , s 1 , … , s N ≥ 0 s_1,\ldots,s_N \ge0 s 1 , … , s N ≥ 0 , and 0 ≤ ε < 1 / 2 0 \le\varepsilon< 1/2 0 ≤ ε < 1/2 , suppose P ( X N + 1 > c ) ≥ 1 − ε \mathbb{P}(X_{N+1} > c) \ge1-\varepsilon P ( X N + 1 > c ) ≥ 1 − ε and, for each fixed z ∈ [ 0 , c ) z \in[0,c) z ∈ [ 0 , c ) ,
P { ∃ t ≤ N : X t ≤ z < X t + 1 , X t + 1 > z + s t } ≤ ε . \mathbb{P}\{\exists t \le N : X_t \le z < X_{t+1},\ X_{t+1} > z+s_t\} \le\varepsilon. P { ∃ t ≤ N : X t ≤ z < X t + 1 , X t + 1 > z + s t } ≤ ε . Then c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } c(1-2\varepsilon) \le\mathbb{E}\sum_{t=1}^{N}\min\{s_t,D_t\} c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } .
Proof Let B = [ 0 , c ) ∩ ⋃ t = 1 N [ X t , X t + 1 − s t ) B=[0,c)\cap\bigcup_{t=1}^{N}[X_t,X_{t+1}-s_t) B = [ 0 , c ) ∩ ⋃ t = 1 N [ X t , X t + 1 − s t ) be the badly crossed boundaries, with reversed intervals empty. Measurable endpoints make 1 { z ∈ B } \mathbf{1}_{\{z\in B\}} 1 { z ∈ B } jointly measurable. The fixed-z z z hypothesis and Tonelli’s theorem give E ∣ B ∣ = ∫ 0 c P ( z ∈ B ) d z ≤ c ε \mathbb{E}|B|=\int_0^c\mathbb{P}(z\in B)\,dz\le c\varepsilon E ∣ B ∣ = ∫ 0 c P ( z ∈ B ) d z ≤ c ε , where ∣ B ∣ |B| ∣ B ∣ denotes Lebesgue measure. At update t t t , the safely crossed boundaries have total length at most min { s t , D t } \min\{s_t,D_t\} min { s t , D t } . On { X N + 1 > c } \{X_{N+1}>c\} { X N + 1 > c } every boundary in [ 0 , c ) [0,c) [ 0 , c ) has been crossed, so
c 1 { X N + 1 > c } ≤ ∣ B ∣ + ∑ t = 1 N min { s t , D t } . c\mathbf{1}_{\{X_{N+1}>c\}}\le|B|+\sum_{t=1}^{N}\min\{s_t,D_t\}. c 1 { X N + 1 > c } ≤ ∣ B ∣ + t = 1 ∑ N min { s t , D t } .
Taking expectations proves the claim. ■
Lemma 19 (Fixed targets coupled at the first crossing). Fix 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 , an integer N ≥ 1 N\ge1 N ≥ 1 , positive numbers b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N , and μ ∈ ( 4 b N , 1 / 2 ] \mu\in(4b_N,1/2] μ ∈ ( 4 b N , 1/2 ] . Let A A A , π \pi π , and Y t Y_t Y t be as in (29) , and put c = 1 / 2 c=1/2 c = 1/2 and s t = μ + 2 b t s_t=\mu+\sqrt{2b_t} s t = μ + 2 b t . Consider a method that starts at x 1 = 0 x_1=0 x 1 = 0 , queries one stochastic gradient at its current iterate x t x_t x t , and computes x t + 1 ∈ R x_{t+1}\in\mathbb{R} x t + 1 ∈ R , together with any auxiliary state, from the gradients observed so far and an independent seed, by the same rule on every instance. Suppose every instance f μ , y f_{\mu,y} f μ , y , y ∈ [ μ , 1 ] y\in[\mu,1] y ∈ [ μ , 1 ] , with sample loss (30) satisfies (26) . Let the reference run X t X_t X t be the states produced from the observations − A Y t -AY_t − A Y t and the seed through the first update with X t + 1 > c X_{t+1}>c X t + 1 > c , held fixed thereafter without further oracle calls. If X t X_t X t is nondecreasing, then D t = X t + 1 − X t D_t=X_{t+1}-X_t D t = X t + 1 − X t satisfies c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } c(1-2\varepsilon)\le\mathbb{E}\sum_{t=1}^{N}\min\{s_t,D_t\} c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } .
Proof Since c ≤ 1 − μ c\le1-\mu c ≤ 1 − μ , every query before stopping lies where target y = 1 y=1 y = 1 returns − A Y t -AY_t − A Y t , so the reference agrees with the run on that target until it stops. On { X N + 1 ≤ c } \{X_{N+1}\le c\} { X N + 1 ≤ c } it has not stopped by time N N N , and (28) gives
f μ , 1 ( X N + 1 ) − f μ , 1 ∗ ≥ μ ( 1 − c ) − μ 2 / 2 ≥ μ / 4 > b N . f_{\mu,1}(X_{N+1})-f_{\mu,1}^{\ast}\ge\mu(1-c)-\mu^2/2\ge\mu/4>b_N. f μ , 1 ( X N + 1 ) − f μ , 1 ∗ ≥ μ ( 1 − c ) − μ 2 /2 ≥ μ /4 > b N .
Hence P ( X N + 1 > c ) ≥ 1 − ε \mathbb{P}(X_{N+1}>c)\ge1-\varepsilon P ( X N + 1 > c ) ≥ 1 − ε .
For any fixed z ∈ [ 0 , c ) z\in[0,c) z ∈ [ 0 , c ) , couple target y = z + μ y=z+\mu y = z + μ using the same Bernoulli sequence and the same seed. Its run agrees with the reference in all states, including auxiliary ones, through the first update strictly crossing z z z : all queries up to that update lie at or below z = y − μ z = y - \mu z = y − μ and have the same observations − A Y t -AY_t − A Y t . Each target is coupled separately, before the run. If that first crossing has X t + 1 > z + s t X_{t+1} > z + s_t X t + 1 > z + s t , the coupled target has gap ( X t + 1 − z − μ ) 2 / 2 > b t (X_{t+1} - z - \mu)^2/2 > b_t ( X t + 1 − z − μ ) 2 /2 > b t . Its prefix guarantee verifies the crossing hypothesis of Lemma 18 for each fixed z z z , and that lemma applies. ■
Proof of Proposition 17 . Let ε \varepsilon ε , N N N , the rule, and b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N be as in its statement, and fix μ ∈ ( 4 b N , 1 / 2 ] \mu\in(4b_N,1/2] μ ∈ ( 4 b N , 1/2 ] . The instances of Appendix H.1 belong to the class of Theorem 4 , and the rule meets the conditions of Lemma 19 . Let X t X_t X t be its reference run, with c = 1 / 2 c = 1/2 c = 1/2 and s t = μ + 2 b t s_t = \mu+ \sqrt{2b_t} s t = μ + 2 b t . All observations prior to stopping equal − A Y t -AY_t − A Y t , so
X 1 = 0 , X t + 1 = X t + Y t q t ≥ X t ≥ 0 , X_1 = 0,\qquad X_{t+1} = X_t + Y_tq_t \ge X_t \ge0, X 1 = 0 , X t + 1 = X t + Y t q t ≥ X t ≥ 0 ,
where q t = A c t ≥ 0 q_t = Ac_t \ge0 q t = A c t ≥ 0 before stopping and q t = 0 q_t = 0 q t = 0 afterwards. The responses are finite but need not be integrable or independent of Y t Y_t Y t . Since D t = Y t q t D_t = Y_tq_t D t = Y t q t , we have min { s t , D t } ≤ Y t s t \min\{s_t,D_t\} \le Y_ts_t min { s t , D t } ≤ Y t s t . Since c = 1 / 2 c = 1/2 c = 1/2 , Lemma 19 and E Y t = π \mathbb{E}Y_t = \pi E Y t = π give (27) :
c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } ≤ π ∑ t = 1 N s t . c(1 - 2\varepsilon) \le\mathbb{E}\sum_{t=1}^{N}\min\{s_t,D_t\} \le\pi\sum_{t=1}^{N}s_t. c ( 1 − 2 ε ) ≤ E t = 1 ∑ N min { s t , D t } ≤ π t = 1 ∑ N s t .
We first record the exponent calculation shared by Theorems 4 and 7; the proof of Theorem 6 repeats it with a confidence factor. Put q = p / ( p − 1 ) q = p/(p - 1) q = p / ( p − 1 ) and choose β p < u < min { r , 1 } \beta_p < u < \min\{r,1\} β p < u < min { r , 1 } . For any positive subpolynomial factors D N , K N = N o ( 1 ) D_N,K_N = N^{o(1)} D N , K N = N o ( 1 ) , let
b N , t = D N t − u , μ = 8 D N N − u , π = 2 1 / ( p − 1 ) μ q . (31) b_{N,t} = D_Nt^{-u},\qquad\mu= 8D_NN^{-u},\qquad\pi= 2^{1/(p-1)}\mu^q. \tag*{(31)} b N , t = D N t − u , μ = 8 D N N − u , π = 2 1/ ( p − 1 ) μ q . (31)
Then μ / 2 b N , N = 4 2 D N N − u / 2 → 0 \mu/\sqrt{2b_{N,N}} = 4\sqrt{2}\sqrt{D_N}N^{-u/2} \to0 μ / 2 b N , N = 4 2 D N N − u /2 → 0 . Since b N , t ≥ b N , N b_{N,t} \ge b_{N,N} b N , t ≥ b N , N , u < 1 u < 1 u < 1 , and β p = 1 / ( q + 1 / 2 ) \beta_p = 1/(q + 1/2) β p = 1/ ( q + 1/2 ) , summing t − u / 2 t^{-u/2} t − u /2 gives
K N π ∑ t = 1 N ( μ + 2 b N , t ) = O ( K N D N q + 1 / 2 N 1 − u ( q + 1 / 2 ) ) → 0. (32) K_N\pi\sum_{t=1}^{N}(\mu+\sqrt{2b_{N,t}}) = O\left(K_ND_N^{q+1/2}N^{1-u(q+1/2)}\right)\to0. \tag*{(32)} K N π t = 1 ∑ N ( μ + 2 b N , t ) = O ( K N D N q + 1/2 N 1 − u ( q + 1/2 ) ) → 0. (32)
Proof of Theorem 4 . Suppose its envelope holds on every instance. Choose u u u as above and D N = C log m ( e N ) D_N = C\log^m(eN) D N = C log m ( e N ) , so C t − r log m ( e t ) ≤ b N , t Ct^{-r}\log^m(et) \le b_{N,t} C t − r log m ( e t ) ≤ b N , t for t ≤ N t \le N t ≤ N . For all sufficiently large N N N , 4 b N , N < μ ≤ 1 / 2 4b_{N,N} < \mu\le1/2 4 b N , N < μ ≤ 1/2 . Proposition 17 with ε = δ \varepsilon= \delta ε = δ contradicts (32) with K N = 1 K_N = 1 K N = 1 . A failing finite prefix yields (9) . The resulting instance is fixed before its i.i.d. samples and the algorithm seed are drawn, and it may depend on N N N . ■
Proof of Theorem 6
Proof Suppose the displayed envelope holds on every instance at every time and confidence. Since c < 1 − β p c < 1 - \beta_p c < 1 − β p and r > β p + c r > \beta_p + c r > β p + c , we may choose β p + c < u < min { r , 1 } \beta_p + c < u < \min\{r,1\} β p + c < u < min { r , 1 } ; put v = u − c > β p v = u - c > \beta_p v = u − c > β p . For each deterministic N N N , set
δ N = 1 4 N c , D N = C 4 c log m ( 4 e N 2 ) , b N , t = D N N c t − u . \delta_N = \frac{1}{4N^c},\qquad D_N = C4^c\log^m(4eN^2),\qquad b_{N,t} = D_NN^ct^{-u}. δ N = 4 N c 1 , D N = C 4 c log m ( 4 e N 2 ) , b N , t = D N N c t − u .
Since δ N − c = ( 4 N ) c \delta_N^{-c} = (4N)^c δ N − c = ( 4 N ) c and log ( e t / δ N ) ≤ log ( 4 e N 2 ) \log(et/\delta_N) \le\log(4eN^2) log ( e t / δ N ) ≤ log ( 4 e N 2 ) , the claimed fixed-time envelope is at most b N , t b_{N,t} b N , t for t ≤ N t \le N t ≤ N . Use the δ N \delta_N δ N -tuned rule on the prefix. A union bound gives failure probability at most N δ N = 1 / 4 N\delta_N = 1/4 N δ N = 1/4 on every instance. Proposition 17 , with the separate budget ε 0 = 1 / 4 \varepsilon_0 = 1/4 ε 0 = 1/4 and μ = 8 b N , N = 8 D N N − v \mu= 8b_{N,N} = 8D_NN^{-v} μ = 8 b N , N = 8 D N N − v , which lies in ( 4 b N , N , 1 / 2 ] (4b_{N,N},1/2] ( 4 b N , N , 1/2 ] for large N N N , therefore requires π ∑ t ≤ N ( μ + 2 b N , t ) ≥ 1 / 4 \pi\sum_{t\le N}(\mu+\sqrt{2b_{N,t}})\ge1/4 π ∑ t ≤ N ( μ + 2 b N , t ) ≥ 1/4 .
With π = 2 1 / ( p − 1 ) μ q \pi=2^{1/(p-1)}\mu^q π = 2 1/ ( p − 1 ) μ q and ∑ t ≤ N t − u / 2 ≤ 2 N 1 − u / 2 \sum_{t\le N}t^{-u/2}\le2N^{1-u/2} ∑ t ≤ N t − u /2 ≤ 2 N 1 − u /2 ,
π ∑ t ≤ N ( μ + 2 b N , t ) ≤ 2 1 / ( p − 1 ) 8 q D N q ( 8 D N N − v / 2 + 2 2 D N ) N 1 − v ( q + 1 / 2 ) . \pi\sum_{t\le N}(\mu+\sqrt{2b_{N,t}})\le2^{1/(p-1)}8^qD_N^q(8D_NN^{-v/2}+2\sqrt{2D_N})N^{1-v(q+1/2)}. π t ≤ N ∑ ( μ + 2 b N , t ) ≤ 2 1/ ( p − 1 ) 8 q D N q ( 8 D N N − v /2 + 2 2 D N ) N 1 − v ( q + 1/2 ) .
The right side tends to zero, because D N = N o ( 1 ) D_N=N^{o(1)} D N = N o ( 1 ) and v ( q + 1 / 2 ) = v / β p > 1 v(q+1/2)=v/\beta_p>1 v ( q + 1/2 ) = v / β p > 1 ; this is a contradiction. By the union bound, a failure probability exceeding 1 / 4 1/4 1/4 on the prefix 1 ≤ t ≤ N 1\le t\le N 1 ≤ t ≤ N implies a fixed-time failure probability above δ N \delta_N δ N at some deterministic t ≤ N t\le N t ≤ N . ■
Proof of the Horizon-Free Time-Uniform Upper Bound
The proof first derives a time-uniform radius bound from a global decomposition of the conditional expectation of a clipped gradient. Once the clipping threshold exceeds the gradient norms allowed by this radius, the local clipping estimates apply on a deterministic suffix of the trajectory. For each analysis horizon, we use bounded inverse tail weights to control the full potential, which consists of the objective gap at a comparison point and its squared distance to the last iterate. Smoothness converts both terms into the endpoint gap by (25) . A summable allocation over horizons and a direct bound at early times give the same D p = 4 / c p D_p=4/c_p D p = 4/ c p for all times.
We first prove Theorem 2 under the normalized upper bounds L , R , σ ≤ 1 L,R,\sigma\le1 L , R , σ ≤ 1 . Thus ∥ x 1 − x ⋆ ∥ ≤ 1 \lVert x_1-x^\star\rVert\le1 ∥ x 1 − x ⋆ ∥ ≤ 1 , f f f is convex and at most 1-smooth, and the conditional central p p p th noise moment is at most one. Define β , a , b \beta,a,b β , a , b by (4) , and write
ℓ t = log ( 100 t 2 ) , η t = c t − a / ℓ t 2 , λ t = 4 t b . \ell_t=\log(100t^2),\qquad\eta_t=ct^{-a}/\ell_t^2,\qquad\lambda_t=4t^b. ℓ t = log ( 100 t 2 ) , η t = c t − a / ℓ t 2 , λ t = 4 t b .
Here c ∈ ( 0 , 1 ] c\in(0,1] c ∈ ( 0 , 1 ] is a deterministic constant depending only on p p p , chosen below. Set G t = f ( x t ) − f ⋆ G_t=f(x_t)-f^\star G t = f ( x t ) − f ⋆ , e t = clip ( g t , λ t ) − ∇ f ( x t ) e_t=\operatorname{clip}(g_t,\lambda_t)-\nabla f(x_t) e t = clip ( g t , λ t ) − ∇ f ( x t ) , b t = E t − 1 e t b_t=\mathbb{E}_{t-1}e_t b t = E t − 1 e t , and u t = e t − b t u_t=e_t-b_t u t = e t − b t . Whenever ∥ ∇ f ( x t ) ∥ ≤ λ t / 2 \lVert\nabla f(x_t)\rVert\le\lambda_t/2 ∥ ∇ f ( x t )∥ ≤ λ t /2 , Lemma 12 gives
∥ e t ∥ ≤ 3 2 λ t , ∥ u t ∥ ≤ 2 λ t , ∥ b t ∥ ≤ B t : = 2 λ t 1 − p , E t − 1 ∥ e t ∥ 2 , E t − 1 ∥ u t ∥ 2 ≤ V t : = 2 λ t 2 − p . (33) \lVert e_t\rVert\le\frac{3}{2}\lambda_t,\qquad\lVert u_t\rVert\le2\lambda_t,\qquad\lVert b_t\rVert\le B_t:=2\lambda_t^{1-p},\qquad\mathbb{E}_{t-1}\lVert e_t\rVert^2,\ \mathbb{E}_{t-1}\lVert u_t\rVert^2\le V_t:=2\lambda_t^{2-p}. \tag*{(33)} ∥ e t ∥ ≤ 2 3 λ t , ∥ u t ∥ ≤ 2 λ t , ∥ b t ∥ ≤ B t := 2 λ t 1 − p , E t − 1 ∥ e t ∥ 2 , E t − 1 ∥ u t ∥ 2 ≤ V t := 2 λ t 2 − p . (33)
The bounds B t , V t B_t,V_t B t , V t are deterministic. The concentration arguments below apply these conditional estimates on predictable events.
Explicit Constants and Deterministic Budgets
Put v = ( 2 − p ) b v=(2-p)b v = ( 2 − p ) b . The exponent identities needed throughout are
b ( p − 1 ) = β , a + β = 1 , 2 ( a − b ) = β , a − v = 3 2 β , 2 a − v = 1 + 1 2 β . (34) b(p-1)=\beta,\qquad a+\beta=1,\qquad2(a-b)=\beta,\qquad a-v=\frac{3}{2}\beta,\qquad2a-v=1+\frac{1}{2}\beta. \tag*{(34)} b ( p − 1 ) = β , a + β = 1 , 2 ( a − b ) = β , a − v = 2 3 β , 2 a − v = 1 + 2 1 β . (34)
Let q = 2 − β q=2^{-\beta} q = 2 − β and define the following finite constants:
J β = ∑ j = 0 ∞ q j ( j + 2 ) 2 = q ( 1 + q ) ( 1 − q ) 3 + 4 q ( 1 − q ) 2 + 4 1 − q , J_\beta=\sum_{j=0}^{\infty}q^j(j+2)^2=\frac{q(1+q)}{(1-q)^3}+\frac{4q}{(1-q)^2}+\frac{4}{1-q}, J β = j = 0 ∑ ∞ q j ( j + 2 ) 2 = ( 1 − q ) 3 q ( 1 + q ) + ( 1 − q ) 2 4 q + 1 − q 4 ,
H β = 64 ( 1 + β − 1 + J β ) , K = 2 20 H β 4 . (35) H_\beta=64(1+\beta^{-1}+J_\beta),\qquad K=2^{20}H_\beta^4. \tag*{(35)} H β = 64 ( 1 + β − 1 + J β ) , K = 2 20 H β 4 . (35)
c p = 1 1000 K , D p = 4 c p . c_p=\frac{1}{1000K},\qquad D_p=\frac{4}{c_p}. c p = 1000 K 1 , D p = c p 4 .
These constants depend only on p p p . The deterministic inequalities below hold for every 0 < c ≤ 1 0<c\le1 0 < c ≤ 1 ; we then take c = c p c=c_p c = c p .
For a deterministic proof horizon T T T , set S t = ∑ s = t T η s S_t=\sum_{s=t}^{T}\eta_s S t = ∑ s = t T η s , S 0 = S 1 S_0=S_1 S 0 = S 1 , S T + 1 = 0 S_{T+1}=0 S T + 1 = 0 , U = 1 + S 1 U=1+S_1 U = 1 + S 1 , and
Q t = U η t 2 1 + S t . (36) Q_t=\frac{U\eta_t^2}{1+S_t}. \tag*{(36)} Q t = 1 + S t U η t 2 . (36)
The following estimates treat early times, late times, and small cumulative step sums.
Lemma 20 (Deterministic anytime budgets). *For all T ≥ 1 T\ge1 T ≥ 1 and 0 < c ≤ 1 0<c\le1 0 < c ≤ 1 ,
c T β 2 ℓ T 2 ≤ S 1 ≤ H β T β ℓ T 2 , (37) \frac{cT^\beta}{2\ell_T^2}\le S_1\le H_\beta\frac{T^\beta}{\ell_T^2}, \tag*{(37)} 2 ℓ T 2 c T β ≤ S 1 ≤ H β ℓ T 2 T β , (37) ∑ t ≥ 1 η t B t ≤ K c / ℓ 1 , ∑ t ≥ 1 η t 2 V t ≤ K c 2 / ℓ 1 4 , sup t ≥ 1 η t λ t ≤ 4 c / ℓ 2 2 , (38) \sum_{t\ge1}\eta_tB_t\le Kc/\ell_1,\qquad
\sum_{t\ge1}\eta_t^2V_t\le Kc^2/\ell_1^4,\qquad
\sup_{t\ge1}\eta_t\lambda_t\le4c/\ell_2^2, \tag*{(38)} t ≥ 1 ∑ η t B t ≤ K c / ℓ 1 , t ≥ 1 ∑ η t 2 V t ≤ K c 2 / ℓ 1 4 , t ≥ 1 sup η t λ t ≤ 4 c / ℓ 2 2 , (38) ∑ t = 1 T Q t B t ≤ K c / ℓ 1 , ∑ t = 1 T Q t V t ≤ K c 2 / ℓ 1 3 , max t ≤ T Q t λ t 2 ≤ K c 2 / ℓ 1 4 . (39) \sum_{t=1}^{T}\sqrt{Q_t}B_t\le Kc/\ell_1,\qquad
\sum_{t=1}^{T}Q_tV_t\le Kc^2/\ell_1^3,\qquad
\max_{t\le T}Q_t\lambda_t^2\le Kc^2/\ell_1^4. \tag*{(39)} t = 1 ∑ T Q t B t ≤ K c / ℓ 1 , t = 1 ∑ T Q t V t ≤ K c 2 / ℓ 1 3 , t ≤ T max Q t λ t 2 ≤ K c 2 / ℓ 1 4 . (39)
Proof. From B t ≤ 2 t − β B_t\le2t^{-\beta} B t ≤ 2 t − β , V t ≤ 8 t v V_t\le8t^v V t ≤ 8 t v and (34) ,
η t B t ≤ 2 c t ℓ t 2 , η t 2 V t ≤ 8 c 2 t − 1 − β / 2 ℓ t 4 , η t 2 λ t 2 = 16 c 2 t − β ℓ t 4 . \eta_tB_t\le\frac{2c}{t\ell_t^2},\qquad
\eta_t^2V_t\le\frac{8c^2t^{-1-\beta/2}}{\ell_t^4},\qquad
\eta_t^2\lambda_t^2=\frac{16c^2t^{-\beta}}{\ell_t^4}. η t B t ≤ t ℓ t 2 2 c , η t 2 V t ≤ ℓ t 4 8 c 2 t − 1 − β /2 , η t 2 λ t 2 = ℓ t 4 16 c 2 t − β .
Integral comparison gives ∑ t ( t ℓ t 2 ) − 1 ≤ ℓ − 1 \sum_t(t\ell_t^2)^{-1}\le\ell^{-1} ∑ t ( t ℓ t 2 ) − 1 ≤ ℓ − 1 and ∑ t t − 1 − β / 2 ≤ 1 + 2 / β \sum_t t^{-1-\beta/2}\le1+2/\beta ∑ t t − 1 − β /2 ≤ 1 + 2/ β , proving (38) . The final ⌈ T / 2 ⌉ \lceil T/2\rceil ⌈ T /2 ⌉ indices give S 1 ≥ ( T / 2 ) η T S_1\ge(T/2)\eta_T S 1 ≥ ( T /2 ) η T . On each nonempty dyadic block T / 2 j + 1 < t ≤ T / 2 j T/2^{j+1}<t\le T/2^j T / 2 j + 1 < t ≤ T / 2 j ,
ℓ T / ℓ t ≤ 2 ( j + 2 ) , ∑ T / 2 j + 1 < t ≤ T / 2 j t − α ≤ 2 T β 2 − β j . \ell_T/\ell_t\le2(j+2),\qquad
\sum_{T/2^{j+1}<t\le T/2^j}t^{-\alpha}\le2T^\beta2^{-\beta j}. ℓ T / ℓ t ≤ 2 ( j + 2 ) , T / 2 j + 1 < t ≤ T / 2 j ∑ t − α ≤ 2 T β 2 − β j .
Summation gives S 1 ≤ 8 J β c T β / ℓ T 2 S_1\le8J_\beta cT^\beta/\ell_T^2 S 1 ≤ 8 J β c T β / ℓ T 2 and hence (37) .
Split the sums of (39) at ⌊ T / 2 ⌋ \lfloor T/2\rfloor ⌊ T /2 ⌋ . On the early half, U / ( 1 + S t ) ≤ 4 H β U/(1+S_t)\le4H_\beta U / ( 1 + S t ) ≤ 4 H β , so its bias, variance and range contributions are at most
4 H β c ℓ 1 , 32 H β ( 1 + 2 / β ) c 2 ℓ 1 4 , 64 H β c 2 ℓ 1 4 . 4\sqrt{H_\beta}\frac{c}{\ell_1},\qquad
32H_\beta(1+2/\beta)\frac{c^2}{\ell_1^4},\qquad
64H_\beta\frac{c^2}{\ell_1^4}. 4 H β ℓ 1 c , 32 H β ( 1 + 2/ β ) ℓ 1 4 c 2 , 64 H β ℓ 1 4 c 2 .
On the late half, t ≥ T / 2 t\ge T/2 t ≥ T /2 and ℓ T / ℓ t ≤ 2 \ell_T/\ell_t\le2 ℓ T / ℓ t ≤ 2 imply
η t V t ≤ 64 c T − 3 β / 2 ℓ T 2 , η t 2 λ t 2 ≤ 512 c 2 T − β ℓ T 4 , B t ≤ 4 T − β . \eta_tV_t\le\frac{64cT^{-3\beta/2}}{\ell_T^2},\qquad
\eta_t^2\lambda_t^2\le\frac{512c^2T^{-\beta}}{\ell_T^4},\qquad
B_t\le4T^{-\beta}. η t V t ≤ ℓ T 2 64 c T − 3 β /2 , η t 2 λ t 2 ≤ ℓ T 4 512 c 2 T − β , B t ≤ 4 T − β .
Since η t = S t − S t + 1 \eta_t=S_t-S_{t+1} η t = S t − S t + 1 , comparing the sums with the corresponding integrals yields
∑ t η t 1 + S t ≤ log U , ∑ t η t 1 + S t ≤ 2 ( U − 1 ) . (40) \sum_t\frac{\eta_t}{1+S_t}\le\log U,\qquad
\sum_t\frac{\eta_t}{\sqrt{1+S_t}}\le2(\sqrt{U}-1). \tag*{(40)} t ∑ 1 + S t η t ≤ log U , t ∑ 1 + S t η t ≤ 2 ( U − 1 ) . (40)
Consequently the late bias and range are bounded by
8 T − β U ( U − 1 ) ≤ 8 H β c ℓ T 2 , 512 U c 2 T − β / ℓ T 4 ≤ 1024 H β c 2 / ℓ T 4 . 8T^{-\beta}\sqrt{U}(\sqrt{U}-1)\le\frac{8H_\beta c}{\ell_T^2},\qquad
512Uc^2T^{-\beta}/\ell_T^4\le1024H_\beta c^2/\ell_T^4. 8 T − β U ( U − 1 ) ≤ ℓ T 2 8 H β c , 512 U c 2 T − β / ℓ T 4 ≤ 1024 H β c 2 / ℓ T 4 .
For the late variance, use U log U ≤ S 1 ( 1 + log U ) U\log U\le S_1(1+\log U) U log U ≤ S 1 ( 1 + log U ) , valid also when S 1 ≤ 1 S_1\le1 S 1 ≤ 1 , and log U ≤ H β ℓ T \log U\le H_\beta\ell_T log U ≤ H β ℓ T to obtain
∑ t > T / 2 Q t V t ≤ 64 c T − 3 β / 2 ℓ T 2 U log U ≤ 128 H β 2 c 2 T − β / 2 ℓ T 3 . \sum_{t>T/2}Q_tV_t\le\frac{64cT^{-3\beta/2}}{\ell_T^2}U\log U\le\frac{128H_\beta^2c^2T^{-\beta/2}}{\ell_T^3}. t > T /2 ∑ Q t V t ≤ ℓ T 2 64 c T − 3 β /2 U log U ≤ ℓ T 3 128 H β 2 c 2 T − β /2 .
Here U ≤ 1 + H β T β U\le1+H_\beta T^\beta U ≤ 1 + H β T β gives the logarithmic bound. Adding the early contributions proves (39) with K = 2 20 H β 4 K=2^{20}H_\beta^4 K = 2 20 H β 4 . ▪
A Radius Event for All Times
Use c = c p c=c_p c = c p and fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) ; the schedule does not depend on δ \delta δ . Write h = log ( 100 / δ ) h=\log(100/\delta) h = log ( 100/ δ ) and ι T = ι T ( δ ) = log ( 100 T 2 / δ ) \iota_T=\iota_T(\delta)=\log(100T^2/\delta) ι T = ι T ( δ ) = log ( 100 T 2 / δ ) ; thus ι T ≥ h > 2 \iota_T\ge h>2 ι T ≥ h > 2 . Apply Lemma 13 conditionally at every step, with μ t = ∇ f ( x t ) \mu_t=\nabla f(x_t) μ t = ∇ f ( x t ) , and write
clip ( g t , λ t ) = A t s μ t + d t , d t = ε t + u t , E t − 1 u t = 0. \operatorname{clip}(g_t,\lambda_t)=A_t^s\mu_t+d_t,\qquad d_t=\varepsilon_t+u_t,\qquad\mathbb{E}_{t-1}u_t=0. clip ( g t , λ t ) = A t s μ t + d t , d t = ε t + u t , E t − 1 u t = 0.
The following bounds hold globally: 0 ≤ A t s ≤ 1 0\le A_t^s\le1 0 ≤ A t s ≤ 1 , ∥ ε t ∥ ≤ B t \|\varepsilon_t\|\le B_t ∥ ε t ∥ ≤ B t , E t − 1 ∥ u t ∥ 2 ≤ V t \mathbb{E}_{t-1}\|u_t\|^2\le V_t E t − 1 ∥ u t ∥ 2 ≤ V t , ∥ u t ∥ ≤ 2 λ t \|u_t\|\le2\lambda_t ∥ u t ∥ ≤ 2 λ t , ∥ d t ∥ ≤ 3 λ t \|d_t\|\le3\lambda_t ∥ d t ∥ ≤ 3 λ t , and E t − 1 ∥ d t ∥ 2 ≤ 2 V t \mathbb{E}_{t-1}\|d_t\|^2\le2V_t E t − 1 ∥ d t ∥ 2 ≤ 2 V t .
Let r t = ∥ x t − x ⋆ ∥ r_t=\|x_t-x^\star\| r t = ∥ x t − x ⋆ ∥ and G t = f ( x t ) − f ⋆ G_t=f(x_t)-f^\star G t = f ( x t ) − f ⋆ . Since η t A t s ≤ 1 / 2 \eta_tA_t^s\le1/2 η t A t s ≤ 1/2 , expansion and ∥ μ t ∥ 2 ≤ 2 G t \|\mu_t\|^2\le2G_t ∥ μ t ∥ 2 ≤ 2 G t , ⟨ μ t , x t − x ⋆ ⟩ ≥ G t \langle\mu_t,x_t-x^\star\rangle\ge G_t ⟨ μ t , x t − x ⋆ ⟩ ≥ G t give
r t + 1 2 ≤ r t 2 − 2 η t ⟨ d t , x t − x ⋆ ⟩ + 2 η t 2 ∥ d t ∥ 2 . r_{t+1}^2\le r_t^2-2\eta_t\langle d_t,x_t-x^\star\rangle+2\eta_t^2\|d_t\|^2. r t + 1 2 ≤ r t 2 − 2 η t ⟨ d t , x t − x ⋆ ⟩ + 2 η t 2 ∥ d t ∥ 2 .
The remaining term with μ t \mu_t μ t is at most 2 η t A t s ( 2 η t A t s − 1 ) G t ≤ 0 2\eta_tA_t^s(2\eta_tA_t^s-1)G_t\le0 2 η t A t s ( 2 η t A t s − 1 ) G t ≤ 0 , as 0 ≤ η t A t s ≤ 1 / 2 0\le\eta_tA_t^s\le1/2 0 ≤ η t A t s ≤ 1/2 .
Apply Lemma 15 to this recursion with P t − 1 = r t 2 P_{t-1}=r_t^2 P t − 1 = r t 2 , p 0 = 1 p_0=1 p 0 = 1 , a t = 2 η t 2 a_t=2\eta_t^2 a t = 2 η t 2 , s t = 2 η t s_t=2\eta_t s t = 2 η t , and w t = − 2 η t ( x t − x ⋆ ) w_t=-2\eta_t(x_t-x^\star) w t = − 2 η t ( x t − x ⋆ ) , using confidence parameter h h h and J t ≡ 1 J_t\equiv1 J t ≡ 1 (no localization indicator). The error bounds above and (38) , using ℓ 1 > 1 \ell_1>1 ℓ 1 > 1 , give
C ≤ 1 + 650 K c 2 h , D ≤ 2 K c + 6 K c h + 32 c h . C\le1+650Kc^2h,\qquad D\le2Kc+6\sqrt{Kc}\sqrt{h}+32ch. C ≤ 1 + 650 K c 2 h , D ≤ 2 K c + 6 K c h + 32 c h .
Since K ≥ 1 K\ge1 K ≥ 1 , h > 2 h>2 h > 2 and K c = 1 / 1000 Kc=1/1000 K c = 1/1000 , C + D ≤ 1 + 66 K c h < h \sqrt{C}+D\le1+66Kch<h C + D ≤ 1 + 66 K c h < h . Hence there is an event R δ \mathcal{R}_\delta R δ , with P ( R δ ) ≥ 1 − e − h \mathbb{P}(\mathcal{R}_\delta)\ge1-e^{-h} P ( R δ ) ≥ 1 − e − h , on which
r t ≤ h , G t ≤ h 2 / 2 for every t ≥ 1. (41) r_t\le h,\qquad G_t\le h^2/2\qquad\text{for every }t\ge1. \tag*{(41)} r t ≤ h , G t ≤ h 2 /2 for every t ≥ 1. (41)
The gap bound uses smoothness at the minimizer.
A Potential on a Suffix of the Trajectory
Set k = ⌈ h 1 / b ⌉ k=\lceil h^{1/b}\rceil k = ⌈ h 1/ b ⌉ and split the analysis of the original recursion at time k k k . For t ≥ k t\ge k t ≥ k , λ t ≥ 4 h \lambda_t\ge4h λ t ≥ 4 h , so (33) holds whenever r t ≤ 2 h r_t\le2h r t ≤ 2 h , since ∥ ∇ f ( x t ) ∥ ≤ r t ≤ λ t / 2 \|\nabla f(x_t)\|\le r_t\le\lambda_t/2 ∥∇ f ( x t ) ∥ ≤ r t ≤ λ t /2 .
Fix a deterministic T ≥ 2 k T\ge2k T ≥ 2 k . Apply Lemma 11 , with ζ = 1 \zeta=1 ζ = 1 , to the updates k , … , T k,\ldots,T k , … , T . Keep S t = ∑ s = t T η s S_t=\sum_{s=t}^T\eta_s S t = ∑ s = t T η s , and set U t = 1 + S t U_t=1+S_t U t = 1 + S t , W = U k W=U_k W = U k , U k − 1 = U k U_{k-1}=U_k U k − 1 = U k , and write A m , H m A_m,H_m A m , H m for the quantities A m , H m A_m,H_m A m , H m of Lemma 11 for these updates. Start its analysis recursions at z k − 1 = z k = x ⋆ z_{k-1}=z_k=x^\star z k − 1 = z k = x ⋆ and A k − 1 = 0 A_{k-1}=0 A k − 1 = 0 , with H k − 1 = r k 2 / 2 H_{k-1}=r_k^2/2 H k − 1 = r k 2 /2 . Write
Q t ( k ) = W η t 2 U t , w t = W η t U t − 1 ( z t − 1 − x t ) , H t = W 2 U t ∥ z t − x t + 1 ∥ 2 . Q_t^{(k)}=\frac{W\eta_t^2}{U_t},\qquad w_t=\frac{W\eta_t}{U_{t-1}}(z_{t-1}-x_t),\qquad H_t=\frac{W}{2U_t}\|z_t-x_{t+1}\|^2. Q t ( k ) = U t W η t 2 , w t = U t − 1 W η t ( z t − 1 − x t ) , H t = 2 U t W ∥ z t − x t + 1 ∥ 2 .
The proof of Lemma 11 is pathwise, so here its initial distance term is r k 2 / 2 r_k^2/2 r k 2 /2 , also when x k x_k x k is random. Its inequality for the partial sums is
W A m + H m ≤ 1 2 r k 2 + 2 ∑ t = k m Q t ( k ) ∥ e t ∥ 2 + ∑ t = k m ⟨ e t , w t ⟩ . (42) WA_m+H_m\le\frac{1}{2}r_k^2+2\sum_{t=k}^{m}Q_t^{(k)}\|e_t\|^2+\sum_{t=k}^{m}\langle e_t,w_t\rangle. \tag*{(42)} W A m + H m ≤ 2 1 r k 2 + 2 t = k ∑ m Q t ( k ) ∥ e t ∥ 2 + t = k ∑ m ⟨ e t , w t ⟩ . (42)
The denominator of Q t ( k ) Q_t^{(k)} Q t ( k ) agrees with that of Q t Q_t Q t in (36) , and its numerator is smaller. Thus Q t ( k ) ≤ Q t Q_t^{(k)}\le Q_t Q t ( k ) ≤ Q t , so all three budgets (39) apply on the suffix.
Apply Lemma 15 with the predictable indicators J t = 1 { r s ≤ 2 h for k ≤ s ≤ t } J_t=\mathbf{1}_{\{r_s\le2h\text{ for }k\le s\le t\}} J t = 1 { r s ≤ 2 h for k ≤ s ≤ t } , with initial event r k ≤ h r_k\le h r k ≤ h and p 0 = h 2 / 2 p_0=h^2/2 p 0 = h 2 /2 . Set
P m = W A m + H m , a t = 2 Q t ( k ) , s t = 2 Q t ( k ) . P_m=WA_m+H_m,\qquad a_t=2Q_t^{(k)},\qquad s_t=\sqrt{2Q_t^{(k)}}. P m = W A m + H m , a t = 2 Q t ( k ) , s t = 2 Q t ( k ) .
Indeed ∥ w t ∥ 2 ≤ 2 Q ( k ) H t − 1 ≤ s t 2 P t − 1 \lVert w_t\rVert^2 \le2Q^{(k)}H_{t-1} \le s_t^2P_{t-1} ∥ w t ∥ 2 ≤ 2 Q ( k ) H t − 1 ≤ s t 2 P t − 1 , including t = k t=k t = k . With exponent q = ℓ T q=\ell_T q = ℓ T , the budgets (39) and ℓ 1 > 1 \ell_1>1 ℓ 1 > 1 give C ≤ h 2 / 2 + 17 K c 2 q C\le h^2/2+17Kc^2q C ≤ h 2 /2 + 17 K c 2 q and D ≤ 11 K c q D\le11Kcq D ≤ 11 K c q . Hence C + D ≤ ( 1 / 2 + 16 K c ) q < q \sqrt{C}+D\le(1/\sqrt{2}+16Kc)q<q C + D ≤ ( 1/ 2 + 16 K c ) q < q . Except on an unconditional event of probability e − ℓ T e^{-\ell_T} e − ℓ T , the lemma therefore gives
W A m + H m ≤ ℓ T 2 ( k ≤ m ≤ T ) W\mathcal{A}_m+\mathcal{H}_m\le\ell_T^2 \qquad(k\le m\le T) W A m + H m ≤ ℓ T 2 ( k ≤ m ≤ T )
on R δ \mathcal{R}_\delta R δ , where the initial event holds and every localization indicator equals one. Lemma 15 allows a random initial state, so the concentration bound holds unconditionally before the intersection with R δ \mathcal{R}_\delta R δ . Intersecting these concentration events over deterministic T ≥ 2 k T\ge2k T ≥ 2 k defines P δ \mathcal{P}_\delta P δ with total failure at most ∑ T ≥ 2 k e − ℓ T \sum_{T\ge2k}e^{-\ell_T} ∑ T ≥ 2 k e − ℓ T .
Direct Last-Iterate Control
On R δ ∩ P δ \mathcal{R}_\delta\cap\mathcal{P}_\delta R δ ∩ P δ , for every T ≥ 2 k T\ge2k T ≥ 2 k , the full endpoint estimate (25) gives
G T + 1 ≤ 2 ( W A T + H T ) W ≤ 2 ℓ T 2 W ≤ 4 c p T − β ℓ T 2 ≤ 4 c p T − β ℓ T 4 . \begin{aligned}
G_{T+1}\le\frac{2(W\mathcal{A}_T+\mathcal{H}_T)}{W}\le\frac{2\ell_T^2}{W} \\
&\le\frac{4}{c_p}T^{-\beta}\ell_T^2\le\frac{4}{c_p}T^{-\beta}\ell_T^4.
\end{aligned} G T + 1 ≤ W 2 ( W A T + H T ) ≤ W 2 ℓ T 2 ≤ c p 4 T − β ℓ T 2 ≤ c p 4 T − β ℓ T 4 .
Indeed, the suffix contains the last half of the updates, so W ≥ ∑ t = k T η t ≥ ( T / 2 ) η T = ( c p / 2 ) T β / ℓ T 2 W\ge\sum_{t=k}^{T}\eta_t\ge(T/2)\eta_T=(c_p/2)T^\beta/\ell_T^2 W ≥ ∑ t = k T η t ≥ ( T /2 ) η T = ( c p /2 ) T β / ℓ T 2 . For 1 ≤ T < 2 k 1\le T<2k 1 ≤ T < 2 k , use k ≤ 2 h 1 / β k\le2h^{1/\beta} k ≤ 2 h 1/ β , 0 < β ≤ 2 / 5 0<\beta\le2/5 0 < β ≤ 2/5 and β / b = p − 1 \beta/b=p-1 β / b = p − 1 . On R δ \mathcal{R}_\delta R δ ,
T β G T + 1 ≤ 1 2 h 2 ( 4 h 1 / β ) β ≤ h p + 1 ≤ h 3 ≤ ℓ T 4 . T^\beta G_{T+1}\le\frac{1}{2}h^2(4h^{1/\beta})^\beta\le h^{p+1}\le h^3\le\ell_T^4. T β G T + 1 ≤ 2 1 h 2 ( 4 h 1/ β ) β ≤ h p + 1 ≤ h 3 ≤ ℓ T 4 .
Since 4 / c p ≥ 1 4/c_p\ge1 4/ c p ≥ 1 , the same rate thus covers the early times as well. The total failure probability is at most
e − h + ∑ T ≥ 2 k e − ℓ T ≤ δ 100 ( 1 + ∑ T ≥ 1 T − 2 ) < δ . e^{-h}+\sum_{T\ge2k}e^{-\ell_T}\le\frac{\delta}{100}\left(1+\sum_{T\ge1}T^{-2}\right)<\delta. e − h + T ≥ 2 k ∑ e − ℓ T ≤ 100 δ ( 1 + T ≥ 1 ∑ T − 2 ) < δ .
Rescaling to the Original Parameters
For L , R > 0 L,R>0 L , R > 0 and σ ≥ 0 \sigma\ge0 σ ≥ 0 , put Q = max { L R , σ } Q=\max\{LR,\sigma\} Q = max { L R , σ } and use the normalized coordinate y = ( x − x 1 ) / R y=(x-x_1)/R y = ( x − x 1 ) / R with objective
F ( y ) = f ( x 1 + R y ) − f ⋆ R Q . F(y)=\frac{f(x_1+Ry)-f^\star}{RQ}. F ( y ) = R Q f ( x 1 + R y ) − f ⋆ .
Its minimizer is within distance one of zero, its smoothness is L R / Q ≤ 1 LR/Q\le1 L R / Q ≤ 1 , and the normalized oracle is g / Q g/Q g / Q , with conditional central p p p th moment at most ( σ / Q ) p ≤ 1 (\sigma/Q)^p\le1 ( σ / Q ) p ≤ 1 . Applying the normalized theorem with step c p t − α / ℓ t 2 c_pt^{-\alpha}/\ell_t^2 c p t − α / ℓ t 2 and threshold 4 t b 4t^b 4 t b gives, after multiplying coordinates by R R R , exactly (5) . Multiplying the objective bound by R Q RQ R Q yields (6) , and (41) becomes ∥ x t − x ⋆ ∥ 2 ≤ R 2 [ log ( 100 / δ ) ] 2 \lVert x_t-x^\star\rVert^2\le R^2[\log(100/\delta)]^2 ∥ x t − x ⋆ ∥ 2 ≤ R 2 [ log ( 100/ δ ) ] 2 . This scaling also covers σ = 0 \sigma=0 σ = 0 since Q = L R > 0 Q=LR>0 Q = L R > 0 .
Proof of Theorem 5
The proof reuses the radius event and the suffix potential of Theorem 2, with the fixed time as the analysis horizon. For r > β p r > \beta_p r > β p , the range of the late clipping errors, weighted by the potential, grows with the horizon, so Lemma 15 does not apply directly. We truncate these errors at deterministic levels that depend on T T T and δ \delta δ , apply the lemma on the event that no truncation occurs, and bound the probability of truncation through the p p p th moment. The factor δ u \delta^u δ u shortens the steps and lowers the thresholds, which postpones truncation and makes it less likely; the shorter steps cost the factor δ − u \delta^{-u} δ − u .
We keep the normalized setting and the constants (35) , fix r ∈ ( β p , α p ] r \in(\beta_p,\alpha_p] r ∈ ( β p , α p ] and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and write h = log ( 100 / δ ) h=\log(100/\delta) h = log ( 100/ δ ) and ι T = log ( 100 T 2 / δ ) \iota_T=\log(100T^2/\delta) ι T = log ( 100 T 2 / δ ) . Put
a r = 1 − r , b r = r p − 1 , d r = a r − b r = p p − 1 ( α p − r ) ≥ 0 , a_r=1-r,\qquad b_r=\frac{r}{p-1},\qquad d_r=a_r-b_r=\frac{p}{p-1}(\alpha_p-r)\ge0, a r = 1 − r , b r = p − 1 r , d r = a r − b r = p − 1 p ( α p − r ) ≥ 0 ,
κ = 3 p − 1 p − 1 , E = κ ( r − β p ) > 0. \kappa=\frac{3p-1}{p-1},\qquad E=\kappa(r-\beta_p)>0. κ = p − 1 3 p − 1 , E = κ ( r − β p ) > 0.
Since κ β p = 2 \kappa\beta_p=2 κ β p = 2 , also E = 2 b r + r − 2 a r E=2b_r+r-2a_r E = 2 b r + r − 2 a r , and
p p − 1 E + κ d r = p κ p − 1 ( α p − β p ) = 1. (43) \frac{p}{p-1}E+\kappa d_r=\frac{p\kappa}{p-1}(\alpha_p-\beta_p)=1. \tag*{(43)} p − 1 p E + κ d r = p − 1 p κ ( α p − β p ) = 1. (43)
For u , w ≥ 0 u,w\ge0 u , w ≥ 0 let
Ξ ( u , w ) = p u p − 1 + 2 w + d r E ( κ u + 2 w ) . \Xi(u,w)=\frac{pu}{p-1}+2w+\frac{d_r}{E}(\kappa u+2w). Ξ ( u , w ) = p − 1 p u + 2 w + E d r ( κ u + 2 w ) .
We prove the following claim: if Ξ ( u , w ) ≥ 1 \Xi(u,w)\ge1 Ξ ( u , w ) ≥ 1 , then the schedule (10) with this u u u satisfies, for every deterministic T ≥ 1 T\ge1 T ≥ 1 ,
P { f ( x T + 1 ) − f ⋆ ≤ D p T − r δ − ( u + 2 w ) ι T 4 } ≥ 1 − δ . (44) \mathbb{P}\left\{f(x_{T+1})-f^\star\le D_pT^{-r}\delta^{-(u+2w)}\iota_T^4\right\}\ge1-\delta. \tag*{(44)} P { f ( x T + 1 ) − f ⋆ ≤ D p T − r δ − ( u + 2 w ) ι T 4 } ≥ 1 − δ . (44)
The parameter w w w enters only the analysis. For u = E = c i n ( r ) u=E=c_{\mathrm{in}}(r) u = E = c in ( r ) and w = 0 w=0 w = 0 , (43) gives Ξ = 1 \Xi=1 Ξ = 1 . For u = 0 u=0 u = 0 and 2 w = E / ( E + d r ) 2w=E/(E+d_r) 2 w = E / ( E + d r ) , Ξ = 2 w ( 1 + d r / E ) = 1 \Xi=2w(1+d_r/E)=1 Ξ = 2 w ( 1 + d r / E ) = 1 , and
E E + d r = ( 3 p − 1 ) r − 2 ( p − 1 ) ( 2 p − 1 ) r − ( p − 1 ) = c f r e e ( r ) . \frac{E}{E+d_r}=\frac{(3p-1)r-2(p-1)}{(2p-1)r-(p-1)}=c_{\mathrm{free}}(r). E + d r E = ( 2 p − 1 ) r − ( p − 1 ) ( 3 p − 1 ) r − 2 ( p − 1 ) = c free ( r ) .
Thus the claim proves Theorem 5 in the normalized setting, and the rescaling of Appendix § 18 .§ 5 multiplies η t \eta_t η t by R / Q R/Q R / Q , λ t \lambda_t λ t by Q Q Q , and the bound by R Q RQ R Q .
Lemma 21 (Budgets for the fixed-time schedules). Let u ≥ 0 u\ge0 u ≥ 0 , 0 < c ≤ 1 0<c\le1 0 < c ≤ 1 , and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and let η t = c δ u t − a r / ℓ t 2 \eta_t=c\delta^u t^{-a_r}/\ell_t^2 η t = c δ u t − a r / ℓ t 2 and λ t = 4 max { 1 , δ u / ( p − 1 ) t b r } \lambda_t=4\max\{1,\delta^{u/(p-1)}t^{b_r}\} λ t = 4 max { 1 , δ u / ( p − 1 ) t b r } , with B t B_t B t and V t V_t V t as in (33) . Then (38) holds. Fix T ≥ 2 T\ge2 T ≥ 2 and an integer 1 ≤ k ≤ T / 2 1\le k\le T/2 1 ≤ k ≤ T /2 such that λ t = 4 δ u / ( p − 1 ) t b r \lambda_t=4\delta^{u/(p-1)}t^{b_r} λ t = 4 δ u / ( p − 1 ) t b r for all t ≥ k t\ge k t ≥ k , and put S t = ∑ s = t T η s S_t=\sum_{s=t}^T\eta_s S t = ∑ s = t T η s , W = 1 + S k W=1+S_k W = 1 + S k , and Q t = W η t 2 / ( 1 + S t ) Q_t=W\eta_t^2/(1+S_t) Q t = W η t 2 / ( 1 + S t ) . Then
c 2 δ u T r ℓ T 2 ≤ S k ≤ S 1 ≤ H β c δ u T r ℓ T 2 , (45) \frac{c}{2}\frac{\delta^u T^{r}}{\ell_T^2}\le S_k\le S_1\le H_{\beta}c\frac{\delta^u T^{r}}{\ell_T^2}, \tag*{(45)} 2 c ℓ T 2 δ u T r ≤ S k ≤ S 1 ≤ H β c ℓ T 2 δ u T r , (45)
∑ t = k T Q t B t ≤ K c 2 ℓ 1 2 , ∑ t = k T Q t V t ≤ K c 2 ℓ 1 3 , max k ≤ t ≤ T / 2 Q t λ t 2 ≤ K c 2 ℓ 1 4 , (46) \sum_{t=k}^{T}\sqrt{Q_t}B_t\le\frac{Kc}{2\ell_1^2},\qquad\sum_{t=k}^{T}Q_tV_t\le\frac{Kc^2}{\ell_1^3},\qquad\max_{k\le t\le T/2}Q_t\lambda_t^2\le\frac{Kc^2}{\ell_1^4}, \tag*{(46)} t = k ∑ T Q t B t ≤ 2 ℓ 1 2 K c , t = k ∑ T Q t V t ≤ ℓ 1 3 K c 2 , k ≤ t ≤ T /2 max Q t λ t 2 ≤ ℓ 1 4 K c 2 , (46)
∑ T / 2 < t ≤ T Q t V t ≤ 128 H β 2 c 2 ℓ T 3 δ p u / ( p − 1 ) T − d r . (47) \sum_{T/2<t\le T}Q_tV_t\le\frac{128H_\beta^2c^2}{\ell_T^3}\delta^{pu/(p-1)}T^{-d_r}. \tag*{(47)} T /2 < t ≤ T ∑ Q t V t ≤ ℓ T 3 128 H β 2 c 2 δ p u / ( p − 1 ) T − d r . (47)
Proof. In both branches of λ t \lambda_t λ t , B t ≤ 2 δ − u t − r B_t \le2\delta^{-u}t^{-r} B t ≤ 2 δ − u t − r and V t ≤ 8 max { 1 , δ ( 2 − p ) u / ( p − 1 ) t ( 2 − p ) b r } V_t \le8\max\{1,\delta^{(2-p)u/(p-1)}t^{(2-p)b_r}\} V t ≤ 8 max { 1 , δ ( 2 − p ) u / ( p − 1 ) t ( 2 − p ) b r } . Since a r + r = 1 a_r+r=1 a r + r = 1 , d r ≥ 0 d_r\ge0 d r ≥ 0 , 2 a r ≥ 1 2a_r\ge1 2 a r ≥ 1 , and 2 a r − ( 2 − p ) b r = 1 + d r 2a_r-(2-p)b_r=1+d_r 2 a r − ( 2 − p ) b r = 1 + d r ,
η t B t ≤ 2 c ℓ t 2 , η t 2 V t ≤ 8 c 2 ℓ t 4 , η t λ t ≤ 4 c ℓ t 2 . \eta_tB_t\le\frac{2c}{\ell_t^2},\qquad\eta_t^2V_t\le\frac{8c^2}{\ell_t^4},\qquad\eta_t\lambda_t\le\frac{4c}{\ell_t^2}. η t B t ≤ ℓ t 2 2 c , η t 2 V t ≤ ℓ t 4 8 c 2 , η t λ t ≤ ℓ t 2 4 c .
and integral comparison, as in Lemma 20 , gives (38) . The proof of (37) gives (45) : S k ≥ ( T / 2 ) η T S_k\ge(T/2)\eta_T S k ≥ ( T /2 ) η T , and every dyadic block has ∑ T − a r ≤ 2 T r 2 − r j ≤ 2 T r 2 − β p j \sum T^{-a_r}\le2T^{r}2^{-rj}\le2T^{r}2^{-\beta_pj} ∑ T − a r ≤ 2 T r 2 − r j ≤ 2 T r 2 − β p j . As there, W / ( 1 + S t ) ≤ 4 H β W/(1+S_t)\le4H_\beta W / ( 1 + S t ) ≤ 4 H β for t ≤ T / 2 t\le T/2 t ≤ T /2 , so the global budgets bound the early parts of the bias and variance sums in (46) by 4 H β c / ℓ 1 4\sqrt{H_\beta}c/\ell_1 4 H β c / ℓ 1 and 64 H β c 2 / ℓ 1 4 64H_\beta c^2/\ell_1^4 64 H β c 2 / ℓ 1 4 , and the early range by 64 H β c 2 / ℓ 1 4 64H_\beta c^2/\ell_1^4 64 H β c 2 / ℓ 1 4 . For T / 2 < t ≤ T T/2<t\le T T /2 < t ≤ T , the branch assumption, ℓ T / ℓ t ≤ 2 \ell_T/\ell_t\le2 ℓ T / ℓ t ≤ 2 , and − a r + ( 2 − p ) b r = − r − d r -a_r+(2-p)b_r=-r-d_r − a r + ( 2 − p ) b r = − r − d r give
B t ≤ 4 δ − u T − r , η t V t ≤ 64 c δ u / ( p − 1 ) T − r − d r ℓ T 2 . B_t\le4\delta^{-u}T^{-r},\qquad\eta_tV_t\le\frac{64c\delta^{u/(p-1)}T^{-r-d_r}}{\ell_T^2}. B t ≤ 4 δ − u T − r , η t V t ≤ ℓ T 2 64 c δ u / ( p − 1 ) T − r − d r .
By (40) , with W W W in place of U U U and the sums starting at k k k , the late bias sum is at most 8 δ − u T − r S k ≤ 8 H β c / ℓ T 2 8\delta^{-u}T^{-r}S_k\le8H_\beta c/\ell_T^2 8 δ − u T − r S k ≤ 8 H β c / ℓ T 2 . For the late variance, W log W ≤ S k ( 1 + log W ) W\log W\le S_k(1+\log W) W log W ≤ S k ( 1 + log W ) and 1 + log W ≤ H β ℓ T 1+\log W\le H_\beta\ell_T 1 + log W ≤ H β ℓ T give
∑ T / 2 < t ≤ T Q t V t ≤ 64 c δ u / ( p − 1 ) T − r − d r ℓ T 2 W log W ≤ 64 H β 2 c 2 ℓ T 3 δ p u / ( p − 1 ) T − d r . \sum_{T/2<t\le T}Q_tV_t\le\frac{64c\delta^{u/(p-1)}T^{-r-d_r}}{\ell_T^2}W\log W\le\frac{64H_\beta^2c^2}{\ell_T^3}\delta^{pu/(p-1)}T^{-d_r}. T /2 < t ≤ T ∑ Q t V t ≤ ℓ T 2 64 c δ u / ( p − 1 ) T − r − d r W log W ≤ ℓ T 3 64 H β 2 c 2 δ p u / ( p − 1 ) T − d r .
Adding both halves and using K = 2 20 H β 4 K=2^{20}H_\beta^4 K = 2 20 H β 4 proves (46) and (47) . ■
Radius and early times. Use c = c p c=c_p c = c p . Since λ t ≥ 4 \lambda_t\ge4 λ t ≥ 4 and η t ≤ c p \eta_t\le c_p η t ≤ c p , the argument of Appendix § 18 .§ 2 , with the global budgets of Lemma 21, gives an event R δ \mathcal{R}_\delta R δ with P ( R δ c ) ≤ δ / 100 \mathbb{P}(\mathcal{R}_\delta^c)\le\delta/100 P ( R δ c ) ≤ δ /100 on which ∥ x t − x ⋆ ∥ ≤ h \lVert x_t-x^\star\rVert\le h ∥ x t − x ⋆ ∥ ≤ h and G t ≤ h 2 / 2 G_t\le h^2/2 G t ≤ h 2 /2 for all t ≥ 1 t\ge1 t ≥ 1 . Let k = ⌈ δ − u / r h 1 / b r ⌉ k=\lceil\delta^{-u/r}h^{1/b_r}\rceil k = ⌈ δ − u / r h 1/ b r ⌉ . Since b r / r = 1 / ( p − 1 ) b_r/r=1/(p-1) b r / r = 1/ ( p − 1 ) , every t ≥ k t\ge k t ≥ k has δ u / ( p − 1 ) t b r ≥ h ≥ 1 \delta^{u/(p-1)}t^{b_r}\ge h\ge1 δ u / ( p − 1 ) t b r ≥ h ≥ 1 , hence λ t = 4 δ u / ( p − 1 ) t b r ≥ 4 h \lambda_t=4\delta^{u/(p-1)}t^{b_r}\ge4h λ t = 4 δ u / ( p − 1 ) t b r ≥ 4 h . If T < 2 k T<2k T < 2 k , then T < 4 δ − u / r h 1 / b r T<4\delta^{-u/r}h^{1/b_r} T < 4 δ − u / r h 1/ b r , and on R δ \mathcal{R}_\delta R δ , using r ≤ 1 / 2 r\le1/2 r ≤ 1/2 , r / b r = p − 1 r/b_r=p-1 r / b r = p − 1 , and p ≤ 2 p\le2 p ≤ 2 ,
δ u T r G T + 1 ≤ 1 2 4 r h p + 1 ≤ h 3 ≤ ℓ T 4 , \delta^{u}T^rG_{T+1}\le\frac{1}{2}4^rh^{p+1}\le h^3\le\ell_T^4, δ u T r G T + 1 ≤ 2 1 4 r h p + 1 ≤ h 3 ≤ ℓ T 4 ,
which proves (44) , since D p ≥ 1 D_p\ge1 D p ≥ 1 and δ − 2 w ≥ 1 \delta^{-2w}\ge1 δ − 2 w ≥ 1 .
Truncation. Fix a deterministic T ≥ 2 k T\ge2k T ≥ 2 k , and apply Lemma 11 with ζ = 1 \zeta=1 ζ = 1 to the updates k , … , T k,\ldots,T k , … , T as in Appendix § 18 .§ 3 . This gives P m = W A m + H m ≥ 0 P_m=W A_m+H_m\ge0 P m = W A m + H m ≥ 0 with W = 1 + S k W=1+S_k W = 1 + S k , the recursion (42) , and ∥ w t ∥ ≤ 2 Q t P t − 1 \lVert w_t\rVert\le\sqrt{2Q_t}\sqrt{P_{t-1}} ∥ w t ∥ ≤ 2 Q t P t − 1 , where Q t = Q t ( k ) Q_t=Q_t^{(k)} Q t = Q t ( k ) is the quantity of Lemma 21. Let J t J_t J t indicate that ∥ x s − x ⋆ ∥ ≤ 2 h \lVert x_s-x^\star\rVert\le2h ∥ x s − x ⋆ ∥ ≤ 2 h for k ≤ s ≤ t k\le s\le t k ≤ s ≤ t ; it is predictable and nonincreasing. On J t = 1 J_t=1 J t = 1 , ∥ ∇ f ( x t ) ∥ ≤ 2 h ≤ λ t / 2 \lVert\nabla f(x_t)\rVert\le2h\le\lambda_t/2 ∥ ∇ f ( x t )∥ ≤ 2 h ≤ λ t /2 , so Lemma 12 gives (33) and ∥ e t ∥ ≤ ∥ g t − ∇ f ( x t ) ∥ \lVert e_t\rVert\le\lVert g_t-\nabla f(x_t)\rVert ∥ e t ∥ ≤ ∥ g t − ∇ f ( x t )∥ . Set M 0 = K c p / ℓ 1 M_0=\sqrt{K}c_p/\ell_1 M 0 = K c p / ℓ 1 , and define deterministic levels and truncated errors by
m t = ∞ ( k ≤ t ≤ T / 2 ) , m t = M 0 δ − w Q t ( T / 2 < t ≤ T ) , e ^ t = e t 1 { ∥ e t ∥ ≤ m t } . m_t=\infty\quad(k\le t\le T/2),\qquad m_t=\frac{M_0\delta^{-w}}{\sqrt{Q_t}}\quad(T/2<t\le T),\qquad\widehat e_t=e_t\mathbf{1}_{\{\lVert e_t\rVert\le m_t\}}. m t = ∞ ( k ≤ t ≤ T /2 ) , m t = Q t M 0 δ − w ( T /2 < t ≤ T ) , e t = e t 1 {∥ e t ∥ ≤ m t } .
Let T = { t : m t < 3 λ t / 2 } \mathcal{T}=\{t:m_t<3\lambda_t/2\} T = { t : m t < 3 λ t /2 } and E T = { J t e t = J t e ^ t for k ≤ t ≤ T } \mathcal{E}_T=\{J_te_t=J_t\widehat e_t\text{ for }k\le t\le T\} E T = { J t e t = J t e t for k ≤ t ≤ T } . Only times in T \mathcal{T} T can violate E T \mathcal{E}_T E T , and the conditional Markov inequality with E t − 1 ∥ g t − ∇ f ( x t ) ∥ p ≤ 1 \mathbb{E}_{t-1}\lVert g_t-\nabla f(x_t)\rVert^p\le1 E t − 1 ∥ g t − ∇ f ( x t ) ∥ p ≤ 1 gives
P ( E T c ) ≤ Σ T : = ∑ t ∈ T m t − p . \mathbb{P}(\mathcal{E}_T^c)\le\Sigma_T:=\sum_{t\in\mathcal{T}}m_t^{-p}. P ( E T c ) ≤ Σ T := t ∈ T ∑ m t − p .
Suppose T ≠ ∅ \mathcal{T}\ne\varnothing T = ∅ . Since δ u T r ≥ δ u k r ≥ 1 \delta^uT^r\ge\delta^uk^r\ge1 δ u T r ≥ δ u k r ≥ 1 and H β c p ≤ 1 H_\beta c_p\le1 H β c p ≤ 1 , (45) gives W ≤ 2 δ u T r W\le2\delta^uT^r W ≤ 2 δ u T r . For T / 2 < t ≤ T T/2<t\le T T /2 < t ≤ T , also η t ≤ 8 c p δ u T − a r / ℓ T 2 \eta_t\le8c_p\delta^uT^{-a_r}/\ell_T^2 η t ≤ 8 c p δ u T − a r / ℓ T 2 and λ t ≤ 4 δ u / ( p − 1 ) T b r \lambda_t\le4\delta^{u/(p-1)}T^{b_r} λ t ≤ 4 δ u / ( p − 1 ) T b r , so
Q t λ t 2 ≤ W η t 2 λ t 2 ≤ 2048 c p 2 ℓ T 4 δ κ u T E . Q_t\lambda_t^2\le W\eta_t^2\lambda_t^2\le\frac{2048c_p^2}{\ell_T^4}\delta^{\kappa u}T^E. Q t λ t 2 ≤ W η t 2 λ t 2 ≤ ℓ T 4 2048 c p 2 δ κ u T E .
A time t ∈ T t \in\mathcal{T} t ∈ T has M 0 2 δ − 2 w < 9 4 Q t λ t 2 M_0^2\delta^{-2w}<\frac{9}{4}Q_t\lambda_t^2 M 0 2 δ − 2 w < 4 9 Q t λ t 2 , so K ≥ 4608 K\ge4608 K ≥ 4608 gives
T E > δ − ( κ u + 2 w ) . (48) T^{E}>\delta^{-(\kappa u+2w)}. \tag*{(48)} T E > δ − ( κ u + 2 w ) . (48)
For t ∈ T t\in\mathcal{T} t ∈ T , m t < 3 λ t / 2 m_t<3\lambda_t/2 m t < 3 λ t /2 and 0 ≤ 2 − p < 1 0\le2-p<1 0 ≤ 2 − p < 1 give m t 2 − p ≤ 3 4 V t m_t^{2-p}\le\frac{3}{4}V_t m t 2 − p ≤ 4 3 V t , hence m t − p = δ 2 w Q t m t 2 − p / M 0 2 ≤ 3 4 δ 2 w Q t V t / M 0 2 m_t^{-p}=\delta^{2w}Q_tm_t^{2-p}/M_0^2\le\frac{3}{4}\delta^{2w}Q_tV_t/M_0^2 m t − p = δ 2 w Q t m t 2 − p / M 0 2 ≤ 4 3 δ 2 w Q t V t / M 0 2 . By (47) , d r ≥ 0 d_r\ge0 d r ≥ 0 , and (48) ,
Σ T ≤ 96 H β 2 ℓ 1 K δ p u p − 1 + 2 w T − d r ≤ 96 H β 2 ℓ 1 K δ Ξ ( u , w ) ≤ δ 2 . \Sigma_{\mathcal{T}}\le\frac{96H_\beta^2\ell_1}{K}\delta^{\frac{pu}{p-1}+2w}T^{-d_r}\le\frac{96H_\beta^2\ell_1}{K}\delta^{\Xi(u,w)}\le\frac{\delta}{2}. Σ T ≤ K 96 H β 2 ℓ 1 δ p − 1 p u + 2 w T − d r ≤ K 96 H β 2 ℓ 1 δ Ξ ( u , w ) ≤ 2 δ .
If T = ∅ \mathcal{T}=\varnothing T = ∅ , then Σ T = 0 \Sigma_{\mathcal{T}}=0 Σ T = 0 .
Energy bound without truncation. On J t = 1 J_t=1 J t = 1 , the truncated errors satisfy
∥ E t − 1 e ^ t ∥ ≤ B t + 1 { t ∈ T } m t 1 − p , E t − 1 ∥ e ^ t ∥ 2 ≤ V t , \left\|E_{t-1}\hat e_t\right\|\le B_t+1_{\{t\in\mathcal{T}\}}m_t^{1-p},\qquad E_{t-1}\|\hat e_t\|^2\le V_t, ∥ E t − 1 e ^ t ∥ ≤ B t + 1 { t ∈ T } m t 1 − p , E t − 1 ∥ e ^ t ∥ 2 ≤ V t ,
∥ e ^ t ∥ ≤ min { 3 2 λ t , m t } , ∥ e ^ t − E t − 1 e ^ t ∥ ≤ 2 min { λ t , m t } . \|\hat e_t\|\le\min\left\{\frac{3}{2}\lambda_t,m_t\right\},\qquad\|\hat e_t-E_{t-1}\hat e_t\|\le2\min\{\lambda_t,m_t\}. ∥ e ^ t ∥ ≤ min { 2 3 λ t , m t } , ∥ e ^ t − E t − 1 e ^ t ∥ ≤ 2 min { λ t , m t } .
The first bound uses ∥ e t ∥ 1 { ∥ e t ∥ > m t } ≤ ∥ g t − ∇ f ( x t ) ∥ m t 1 − p \|e_t\|1_{\{\|e_t\|>m_t\}}\le\|g_t-\nabla f(x_t)\|m_t^{1-p} ∥ e t ∥ 1 { ∥ e t ∥ > m t } ≤ ∥ g t − ∇ f ( x t ) ∥ m t 1 − p . For the last, e ^ t + ∇ f ( x t ) \hat e_t+\nabla f(x_t) e ^ t + ∇ f ( x t ) equals clip ( g t , λ t ) \operatorname{clip}(g_t,\lambda_t) clip ( g t , λ t ) or ∇ f ( x t ) \nabla f(x_t) ∇ f ( x t ) , both in the ball of radius λ t \lambda_t λ t , and ∥ e ^ t ∥ ≤ m t \|\hat e_t\|\le m_t ∥ e ^ t ∥ ≤ m t . Put P ~ m = δ 2 w P m \widetilde P_m=\delta^{2w}P_m P m = δ 2 w P m . On E T ∩ { J m = 1 } \mathcal{E}_{\mathcal{T}}\cap\{J_m=1\} E T ∩ { J m = 1 } , the recursion (42) holds with e ^ t \hat e_t e ^ t in place of e t e_t e t , so
P ~ m ≤ P ~ k − 1 + ∑ t = k m ( 2 δ 2 w Q t ∥ e ^ t ∥ 2 + ⟨ e ^ t , δ 2 w w t ⟩ ) , ∥ δ 2 w w t ∥ ≤ δ w 2 Q t P ~ t − 1 . \widetilde P_m\le\widetilde P_{k-1}+\sum_{t=k}^{m}\left(2\delta^{2w}Q_t\|\hat e_t\|^2+\langle\hat e_t,\delta^{2w}w_t\rangle\right),\qquad\|\delta^{2w}w_t\|\le\delta^w\sqrt{2Q_t}\sqrt{\widetilde P_{t-1}}. P m ≤ P k − 1 + t = k ∑ m ( 2 δ 2 w Q t ∥ e ^ t ∥ 2 + ⟨ e ^ t , δ 2 w w t ⟩ ) , ∥ δ 2 w w t ∥ ≤ δ w 2 Q t P t − 1 .
Apply Lemma 15 with the event E T \mathcal{E}_{\mathcal{T}} E T , the errors e ^ t \hat e_t e ^ t , a t = 2 δ 2 w Q t a_t=2\delta^{2w}Q_t a t = 2 δ 2 w Q t , s t = δ w 2 Q t s_t=\delta^w\sqrt{2Q_t} s t = δ w 2 Q t , p 0 = h 2 / 2 p_0=h^2/2 p 0 = h 2 /2 , and exponent q = ι T q=\iota_{\mathcal{T}} q = ι T . Lemma 21, Σ T ≤ 1 / 2 \Sigma_{\mathcal{T}}\le1/2 Σ T ≤ 1/2 , and the identities δ w Q t m t 1 − p = M 0 m t − p \delta^w\sqrt{Q_t}m_t^{1-p}=M_0m_t^{-p} δ w Q t m t 1 − p = M 0 m t − p and δ 2 w Q t m t 2 = M 0 2 \delta^{2w}Q_tm_t^2=M_0^2 δ 2 w Q t m t 2 = M 0 2 for t > T / 2 t>T/2 t > T /2 give
A ≤ 2 K c p 2 ℓ 1 3 , K 0 ≤ 9 K c p 2 2 ℓ 1 4 , B 0 ≤ 2 K c p ℓ 1 , V 0 ≤ 2 K c p 2 ℓ 1 3 , J 0 ≤ 2 2 K c p ℓ 1 2 . A\le\frac{2Kc_p^2}{\ell_1^3},\qquad K_0\le\frac{9Kc_p^2}{2\ell_1^4},\qquad B_0\le\frac{\sqrt{2}Kc_p}{\ell_1},\qquad V_0\le\frac{2Kc_p^2}{\ell_1^3},\qquad J_0\le\frac{2\sqrt{2}Kc_p}{\ell_1^2}. A ≤ ℓ 1 3 2 K c p 2 , K 0 ≤ 2 ℓ 1 4 9 K c p 2 , B 0 ≤ ℓ 1 2 K c p , V 0 ≤ ℓ 1 3 2 K c p 2 , J 0 ≤ ℓ 1 2 2 2 K c p .
Hence C ≤ h 2 / 2 + 17 K c p 2 q C\le h^2/2+17Kc_p^2q C ≤ h 2 /2 + 17 K c p 2 q and D ≤ 11 K c p q D\le11Kc_pq D ≤ 11 K c p q , so C + D ≤ ( 1 / 2 + 16 K c p ) q < q \sqrt{C}+D\le(1/\sqrt{2}+16Kc_p)q<q C + D ≤ ( 1/ 2 + 16 K c p ) q < q , as in Appendix I.3.
On R δ \mathcal{R}_\delta R δ , P ~ k − 1 ≤ h 2 / 2 \widetilde P_{k-1}\le h^2/2 P k − 1 ≤ h 2 /2 and every J t = 1 J_t=1 J t = 1 . Thus, except on probability e − ι T ≤ δ / 100 e^{-\iota_{\mathcal{T}}}\le\delta/100 e − ι T ≤ δ /100 , every outcome in R δ ∩ E T \mathcal{R}_\delta\cap\mathcal{E}_{\mathcal{T}} R δ ∩ E T has P ~ T ≤ ι T 2 \widetilde P_T\le\iota_T^2 P T ≤ ι T 2 .
Conclusion. On R δ ∩ E T ∩ { P ~ T ≤ ι T 2 } \mathcal{R}_\delta\cap\mathcal{E}_{\mathcal{T}}\cap\{\widetilde P_T\le\iota_T^2\} R δ ∩ E T ∩ { P T ≤ ι T 2 } , the endpoint estimate (25) , W ≥ S k W\ge S_k W ≥ S k , and (45) give
G T + 1 ≤ 2 P T W ≤ 2 δ − 2 w ι T 2 ( c p / 2 ) δ u T / ℓ T 2 ≤ D p T − r δ − ( u + 2 w ) ι T 4 , G_{T+1}\le\frac{2P_T}{W}\le\frac{2\delta^{-2w}\iota_T^2}{(c_p/2)\delta^uT/\ell_T^2}\le D_pT^{-r}\delta^{-(u+2w)}\iota_T^4, G T + 1 ≤ W 2 P T ≤ ( c p /2 ) δ u T / ℓ T 2 2 δ − 2 w ι T 2 ≤ D p T − r δ − ( u + 2 w ) ι T 4 ,
since ℓ T ≤ ι T \ell_T\le\iota_T ℓ T ≤ ι T and D p = 4 / c p D_p=4/c_p D p = 4/ c p . The three exceptional events have total probability at most δ / 100 + δ / 2 + δ / 100 < δ \delta/100+\delta/2+\delta/100<\delta δ /100 + δ /2 + δ /100 < δ , which proves (44) .
Proof of the One-Dimensional Momentum Lower Bound
We prove Theorem 7 for rules that follow the heavy-ball recursion (14) under the bounds (15) , with clip ( g , 0 ) = 0 \operatorname{clip}(g,0)=0 clip ( g , 0 ) = 0 . Such rules observe only stochastic gradients and output their current iterate; their clipping thresholds, momentum coefficients (including β t = 0 \beta_t=0 β t = 0 ), and step sizes may all adapt. For an integer N ≥ 1 N\ge1 N ≥ 1 and k ≥ 0 k\ge0 k ≥ 0 , put
κ N , k = exp ( − ρ ( k − t 0 ) + ( 1 + N ) − α ) . \kappa_{N,k}=\exp\left(-\rho(k-t_0)+(1+N)^{-\alpha}\right). κ N , k = exp ( − ρ ( k − t 0 ) + ( 1 + N ) − α ) .
Proposition 22 (Necessary momentum progress budget). Fix such a rule and a failure budget 0 < ε < 1 / 2 0 < \varepsilon< 1/2 0 < ε < 1/2 . Let N ≥ 1 N \ge1 N ≥ 1 and let b 1 , … , b N b_1,\ldots,b_N b 1 , … , b N be positive. Suppose every instance in the class of Theorem 7 satisfies
P { f ( x t + 1 ) − f ⋆ ≤ b t for all 1 ≤ t ≤ N } ≥ 1 − ε . \mathbb{P}\{f(x_{t+1})-f^\star\le b_t\ \text{for all }1 \le t \le N\} \ge1-\varepsilon. P { f ( x t + 1 ) − f ⋆ ≤ b t for all 1 ≤ t ≤ N } ≥ 1 − ε . For every 4 b N < μ ≤ 1 / 2 4b_N < \mu\le1/2 4 b N < μ ≤ 1/2 , put A = ( 2 μ ) − 1 / ( p − 1 ) A=(2\mu)^{-1/(p-1)} A = ( 2 μ ) − 1/ ( p − 1 ) , π = μ / A \pi=\mu/A π = μ / A , s t = μ + 2 b t s_t=\mu+\sqrt{2b_t} s t = μ + 2 b t , and H N = H ( 1 + N ) h H_N=H(1+N)^h H N = H ( 1 + N ) h . Then
1 − 2 ε 2 ≤ π ∑ t = 1 N ∑ k = 0 t − 1 min { s t , H N A κ N , k } . (49) \frac{1-2\varepsilon}{2} \le\pi\sum_{t=1}^{N}\sum_{k=0}^{t-1}\min\{s_t,H_NA\kappa_{N,k}\}. \tag*{(49)} 2 1 − 2 ε ≤ π t = 1 ∑ N k = 0 ∑ t − 1 min { s t , H N A κ N , k } . (49)
Proof. Use the translated family of Appendix § 17 .§ 1 , fixed before the run:
F μ , y ( x ; Y ) = 1 2 ( x − y + μ ) + 2 − A Y x , y ∈ [ μ , 1 ] , Y ∼ Bernoulli ( π ) . F_{\mu,y}(x;Y)=\frac{1}{2}(x-y+\mu)_+^2-AYx,\qquad y\in[\mu,1],\qquad Y\sim\operatorname{Bernoulli}(\pi). F μ , y ( x ; Y ) = 2 1 ( x − y + μ ) + 2 − A Y x , y ∈ [ μ , 1 ] , Y ∼ Bernoulli ( π ) .
The population objective gap is given by (28) , and for x ≤ y − μ x\le y-\mu x ≤ y − μ the stochastic gradient is − A Y -AY − A Y . In particular, all sample and population properties stated in the theorem hold, with E ∣ μ − A Y ∣ p ≤ μ p + μ A p − 1 ≤ 1 \mathbb{E}|\mu-AY|^p\le\mu^p+\mu A^{p-1}\le1 E ∣ μ − A Y ∣ p ≤ μ p + μ A p − 1 ≤ 1 . Thus these instances satisfy the assumed prefix guarantee, and the rule meets the conditions of Lemma 19 , with the velocity as auxiliary state. Let X t X_t X t and V t V_t V t be the position and velocity of its reference run, with c = 1 / 2 c=1/2 c = 1/2 . Before stopping, let R t = − V t R_t=-V_t R t = − V t and write
R t + 1 = β t R t + Y t a t , a t = min { A , λ t } ∈ [ 0 , A ] , X t + 1 = X t + D t , D t = η t R t + 1 , R_{t+1}=\beta_tR_t+Y_ta_t,\qquad a_t=\min\{A,\lambda_t\}\in[0,A],\qquad X_{t+1}=X_t+D_t,\qquad D_t=\eta_tR_{t+1}, R t + 1 = β t R t + Y t a t , a t = min { A , λ t } ∈ [ 0 , A ] , X t + 1 = X t + D t , D t = η t R t + 1 ,
with X 1 = R 1 = 0 X_1=R_1=0 X 1 = R 1 = 0 . Set D t = 0 D_t=0 D t = 0 after stopping. Unrolling the recursion gives R t + 1 = ∑ j ≤ t ( ∏ i = j + 1 t β i ) Y j a j R_{t+1}=\sum_{j\le t}\left(\prod_{i=j+1}^{t}\beta_i\right)Y_ja_j R t + 1 = ∑ j ≤ t ( ∏ i = j + 1 t β i ) Y j a j . For t ≤ N t\le N t ≤ N , each index i ≥ t 0 i\ge t_0 i ≥ t 0 in the product satisfies β i ≤ 1 − ρ ( 1 + N ) − a ≤ exp ( − ρ ( 1 + N ) − a ) \beta_i\le1-\rho(1+N)^{-a}\le\exp(-\rho(1+N)^{-a}) β i ≤ 1 − ρ ( 1 + N ) − a ≤ exp ( − ρ ( 1 + N ) − a ) , and at least ( t − j − t 0 ) + (t-j-t_0)_+ ( t − j − t 0 ) + of its indices are at least t 0 t_0 t 0 , so ∏ i = j + 1 t β i ≤ κ N , t − j \prod_{i=j+1}^{t}\beta_i\le\kappa_{N,t-j} ∏ i = j + 1 t β i ≤ κ N , t − j . Hence
0 ≤ D t ≤ H N A ∑ j = 1 t κ N , t − j Y j ( t ≤ N ) . (50) 0\le D_t\le H_NA\sum_{j=1}^{t}\kappa_{N,t-j}Y_j\qquad(t\le N). \tag*{(50)} 0 ≤ D t ≤ H N A j = 1 ∑ t κ N , t − j Y j ( t ≤ N ) . (50)
This induction uses only the signs and pathwise bounds, so it holds for controls that depend on the current gradient and on internal randomness. In particular, the reference run is nondecreasing, and Lemma 19 and (50) give
c ( 1 − 2 ε ) ≤ E ∑ t = 1 N min { s t , D t } ≤ π ∑ t = 1 N ∑ k = 0 t − 1 min { s t , H N A κ N , k } . c(1-2\varepsilon)\le\mathbb{E}\sum_{t=1}^{N}\min\{s_t,D_t\}\le\pi\sum_{t=1}^{N}\sum_{k=0}^{t-1}\min\{s_t,H_NA\kappa_{N,k}\}. c ( 1 − 2 ε ) ≤ E t = 1 ∑ N min { s t , D t } ≤ π t = 1 ∑ N k = 0 ∑ t − 1 min { s t , H N A κ N , k } .
For the second inequality, use min { s , ∑ j w j } ≤ ∑ j min { s , w j } \min\{s,\sum_jw_j\}\le\sum_j\min\{s,w_j\} min { s , ∑ j w j } ≤ ∑ j min { s , w j } for w j ≥ 0 w_j\ge0 w j ≥ 0 and E Y j = π \mathbb{E}Y_j=\pi E Y j = π . ■ \blacksquare ■
Proof of Theorem 7. Suppose the asserted envelope holds on every instance. Since a < 1 a<1 a < 1 and β p ≤ 2 / 5 \beta_p\le2/5 β p ≤ 2/5 , we have ( 1 + a ) β p < 1 (1+a)\beta_p<1 ( 1 + a ) β p < 1 ; choose ( 1 + a ) β p < u < min { r , 1 } (1+a)\beta_p<u<\min\{r,1\} ( 1 + a ) β p < u < min { r , 1 } and put b t = b N , t b_t=b_{N,t} b t = b N , t from (31) , with D N = C log m ( e N ) D_N=C\log^m(eN) D N = C log m ( e N ) . This dominates the asserted envelope for t ≤ N t\le N t ≤ N . For sufficiently large N N N , 4 b N < μ ≤ 1 / 2 4b_N<\mu\le1/2 4 b N < μ ≤ 1/2 , and Proposition 22 applies with ε = δ \varepsilon=\delta ε = δ . If H = 0 H=0 H = 0 , the required progress is already impossible. Otherwise split the inner sum at
K N = t 0 + ⌈ ( 1 + N ) a ρ log + ( H N A μ ) ⌉ , log + ( v ) = max { 0 , log v } . K_N=t_0+\left\lceil\frac{(1+N)^a}{\rho}\log_+\left(\frac{H_NA}{\mu}\right)\right\rceil,\qquad\log_+(v)=\max\{0,\log v\}. K N = t 0 + ⌈ ρ ( 1 + N ) a log + ( μ H N A ) ⌉ , log + ( v ) = max { 0 , log v } .
For k ≥ K N k\ge K_N k ≥ K N , H N A κ N , k ≤ μ exp ( − ρ ( k − K N ) ( 1 + N ) − a ) H_NA\kappa_{N,k}\le\mu\exp(-\rho(k-K_N)(1+N)^{-a}) H N A κ N , k ≤ μ exp ( − ρ ( k − K N ) ( 1 + N ) − a ) , and ( 1 − e − x ) − 1 ≤ 1 + x − 1 (1-e^{-x})^{-1}\le1+x^{-1} ( 1 − e − x ) − 1 ≤ 1 + x − 1 for x > 0 x>0 x > 0 , so
∑ k = 0 t − 1 min { s t , H N A κ N , k } ≤ s t ( K N + 1 + ( 1 + N ) a ρ ) . (51) \sum_{k=0}^{t-1}\min\{s_t,H_NA\kappa_{N,k}\}\le s_t\left(K_N+1+\frac{(1+N)^a}{\rho}\right). \tag*{(51)} k = 0 ∑ t − 1 min { s t , H N A κ N , k } ≤ s t ( K N + 1 + ρ ( 1 + N ) a ) . (51)
The factor is O ( N a log ( e N ) ) O(N^{a}\log(eN)) O ( N a log ( e N )) , with constants depending on H H H , h h h , ρ \rho ρ , t 0 t_{0} t 0 , a a a , since log H N = log H + h log ( 1 + N ) \log H_{N}=\log H+h\log(1+N) log H N = log H + h log ( 1 + N ) and
A / μ = 2 − 1 / ( p − 1 ) μ − p / ( p − 1 ) . A/\mu=2^{-1/(p-1)}\mu^{-p/(p-1)}. A / μ = 2 − 1/ ( p − 1 ) μ − p / ( p − 1 ) .
By (32) with K N K_{N} K N replaced by this factor, the right side of (49) is
O ( D N q + 1 / 2 log ( e N ) N 1 + a − u / β p ) , O\left(D_{N}^{q+1/2}\log(eN)N^{1+a-u/\beta_{p}}\right), O ( D N q + 1/2 log ( e N ) N 1 + a − u / β p ) ,
which tends to zero because u > ( 1 + a ) β p u>(1+a)\beta_{p} u > ( 1 + a ) β p ; this contradicts ( 1 − 2 δ ) / 2 > 0 (1-2\delta)/2>0 ( 1 − 2 δ ) /2 > 0 . The contradiction at one finite N N N yields a fixed instance of this class on which (16) holds. ■
The same budget gives the fixed-time analogue, in the sense of Theorem 6 .
Proposition 23 (Fixed-time momentum lower bound). Fix p ∈ ( 1 , 2 ] p\in(1,2] p ∈ ( 1 , 2 ] and a ∈ [ 0 , 1 ) a\in[0,1) a ∈ [ 0 , 1 ) . Let ( rule δ ) δ ∈ ( 0 , 1 ) (\operatorname{rule}_{\delta})_{\delta\in(0,1)} ( rule δ ) δ ∈ ( 0 , 1 ) satisfy (14) and (15) with ρ \rho ρ , t 0 t_{0} t 0 , and h h h independent of δ \delta δ , and with H H H replaced by H δ − h 0 H\delta^{-h_{0}} H δ − h 0 for constants H , h 0 ≥ 0 H,h_{0}\ge0 H , h 0 ≥ 0 independent of δ \delta δ . For every finite C > 0 C>0 C > 0 , m ≥ 0 m\ge0 m ≥ 0 , c ∈ [ 0 , 1 − ( 1 + a ) β p ) c\in[0,1-(1+a)\beta_{p}) c ∈ [ 0 , 1 − ( 1 + a ) β p ) , and r > ( 1 + a ) β p + c r>(1+a)\beta_{p}+c r > ( 1 + a ) β p + c , there are δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , a deterministic integer t ≥ 1 t\ge1 t ≥ 1 , and a one-dimensional instance with L = R = σ = 1 L=R=\sigma=1 L = R = σ = 1 , fixed before the run and satisfying the conditions of Theorem 7, such that rule δ \operatorname{rule}_{\delta} rule δ satisfies P { f ( x t + 1 ) − f ⋆ > C t − r − c [ log ( e t / δ ) ] m } > δ \mathbb{P}\{f(x_{t+1})-f^{\star}>Ct^{-r-c}[\log(et/\delta)]^{m}\}>\delta P { f ( x t + 1 ) − f ⋆ > C t − r − c [ log ( e t / δ ) ] m } > δ .
An exponent above ( 1 + a ) β p (1+a)\beta_{p} ( 1 + a ) β p at a fixed time thus costs a polynomial confidence factor, and with uniformly polylogarithmic dependence on 1 / δ 1/\delta 1/ δ it is unattainable.
Proof of Proposition 23. Suppose the envelope holds for every δ \delta δ , every deterministic time, and every instance. Since c < 1 − ( 1 + a ) β p c<1-(1+a)\beta_{p} c < 1 − ( 1 + a ) β p and r > ( 1 + a ) β p + c r>(1+a)\beta_{p}+c r > ( 1 + a ) β p + c , choose ( 1 + a ) β p + c < u < min { r , 1 } (1+a)\beta_{p}+c<u<\min\{r,1\} ( 1 + a ) β p + c < u < min { r , 1 } and put v = u − c > ( 1 + a ) β p v=u-c>(1+a)\beta_{p} v = u − c > ( 1 + a ) β p . For each deterministic N N N , let δ N \delta_{N} δ N , D N D_{N} D N , and b N , t = D N N c t − u b_{N,t}=D_{N}N^{ct-u} b N , t = D N N c t − u be as in the proof of Theorem 6 ; the envelope of rule δ N \operatorname{rule}_{\delta_{N}} rule δ N is at most b N , t b_{N,t} b N , t for t ≤ N t\le N t ≤ N , and a union bound gives the prefix guarantee of Proposition 22 with failure budget 1 / 4 1/4 1/4 on every instance. On this prefix, η t ≤ H N : = H ( 4 N ) h 0 ( 1 + N ) h \eta_{t}\le H_{N}:=H(4N)^{h_{0}}(1+N)^{h} η t ≤ H N := H ( 4 N ) h 0 ( 1 + N ) h , and the proof of that proposition uses the step sizes only through this bound, so it applies with μ = 8 b N , N = 8 D N N − v \mu=8b_{N,N}=8D_{N}N^{-v} μ = 8 b N , N = 8 D N N − v , which lies in ( 4 b N , N , 1 / 2 ] (4b_{N,N},1/2] ( 4 b N , N , 1/2 ] for large N N N . Splitting the inner sums as in (51) , whose factor is again O ( N a log ( e N ) ) O(N^{a}\log(eN)) O ( N a log ( e N )) because log H N = O ( log ( e N ) ) \log H_{N}=O(\log(eN)) log H N = O ( log ( e N )) , and summing s t s_{t} s t as in the proof of Theorem 6 , the right side of (49) is
O ( D N q + 1 / 2 log ( e N ) N 1 + a − v / β p ) , O\left(D_{N}^{q+1/2}\log(eN)N^{1+a-v/\beta_{p}}\right), O ( D N q + 1/2 log ( e N ) N 1 + a − v / β p ) ,
which tends to zero because v > ( 1 + a ) β p v>(1+a)\beta_{p} v > ( 1 + a ) β p ; this contradicts 1 / 4 1/4 1/4 . At such an N N N , some instance fixed before the run fails the prefix guarantee with probability above 1 / 4 = N δ N 1/4=N\delta_{N} 1/4 = N δ N , and the union bound gives a deterministic t ≤ N t\le N t ≤ N whose fixed-time failure probability exceeds δ N \delta_{N} δ N . ■
A Dimension-Uniform Momentum Lower Bound
We prove Theorem 8 . Throughout, the control and rate constants are common over dimensions, as required by A u n i f ( a ) \mathcal{A}_{\mathrm{unif}}(a) A unif ( a ) .
A Pathwise Projection Identity
Fix the numerical scalar controls on a realized finite path; they may depend on the observations. Write clip ( g s , λ s ) = c s g s \operatorname{clip}(g_{s},\lambda_{s})=c_{s}g_{s} clip ( g s , λ s ) = c s g s , with c s ∈ [ 0 , 1 ] c_{s}\in[0,1] c s ∈ [ 0 , 1 ] and c s = 0 c_{s}=0 c s = 0 when g s = 0 g_{s}=0 g s = 0 . On the nuisance block, where g s g_{s} g s has component y s + ζ s y_{s}+\zeta_{s} y s + ζ s with nuisance noise ζ s \zeta_{s} ζ s , the components y s y_{s} y s of the state and v s v_{s} v s of the velocity satisfy v s + 1 = β s v s + c s ( y s + ζ s ) v_{s+1}=\beta_s v_s+c_s(y_s+\zeta_s) v s + 1 = β s v s + c s ( y s + ζ s ) and y s + 1 = y s − η s v s + 1 y_{s+1}=y_s-\eta_s v_{s+1} y s + 1 = y s − η s v s + 1 , with y 1 = v 1 = 0 y_1=v_1=0 y 1 = v 1 = 0 . An impulse of size A A A at time τ \tau τ has flat response
h t = A c τ ∑ s = τ t − 1 η s ∏ i = τ + 1 s β i ( t > τ ) , h t = 0 ( t ≤ τ ) . (52) h_t=Ac_\tau\sum_{s=\tau}^{t-1}\eta_s\prod_{i=\tau+1}^{s}\beta_i\quad(t>\tau),\qquad h_t=0\quad(t\le\tau). \tag*{(52)} h t = A c τ s = τ ∑ t − 1 η s i = τ + 1 ∏ s β i ( t > τ ) , h t = 0 ( t ≤ τ ) . (52)
Nonnegative controls make h t h_t h t nonnegative and nondecreasing.
Lemma 24 (Orthogonal pulse budget). *Suppose all ζ j \zeta_j ζ j , 1 ≤ j < t 1\le j<t 1 ≤ j < t , are nonzero and mutually orthogonal, with ζ j = R j ϵ j e J j \zeta_j=R_j\epsilon_j e_{J_j} ζ j = R j ϵ j e J j , R j ≥ B > 0 R_j\ge B>0 R j ≥ B > 0 , signs ϵ j ∈ { − 1 , 1 } \epsilon_j\in\{-1,1\} ϵ j ∈ { − 1 , 1 } , and distinct J j J_j J j . For τ < t \tau<t τ < t with R τ = A R_\tau=A R τ = A , let h t h_t h t be (52) . If ∥ y t ∥ ≤ R \lVert y_t\rVert\le R ∥ y t ∥ ≤ R and R t − τ − 1 ≤ B / 2 R\sqrt{t-\tau-1}\le B/2 R t − τ − 1 ≤ B /2 , then h t ≤ 2 R h_t\le2R h t ≤ 2 R .
Proof Define the test vector
w = ζ τ A + ∑ j = τ + 1 t − 1 h j R j 2 ζ j . w=\frac{\zeta_\tau}{A}+\sum_{j=\tau+1}^{t-1}\frac{h_j}{R_j^2}\zeta_j. w = A ζ τ + j = τ + 1 ∑ t − 1 R j 2 h j ζ j .
Orthogonality gives ⟨ ζ s , w ⟩ = h s + A 1 { s = τ } \langle\zeta_s,w\rangle=h_s+A1_{\{s=\tau\}} ⟨ ζ s , w ⟩ = h s + A 1 { s = τ } for s < t s<t s < t . Let k 1 = 0 k_1=0 k 1 = 0 and k s + 1 = β s k s + A c s 1 { s = τ } k_{s+1}=\beta_s k_s+Ac_s1_{\{s=\tau\}} k s + 1 = β s k s + A c s 1 { s = τ } ; then (52) gives h s + 1 = h s + η s k s + 1 h_{s+1}=h_s+\eta_s k_{s+1} h s + 1 = h s + η s k s + 1 . Induction in the nuisance recurrence yields ⟨ v s , w ⟩ = k s \langle v_s,w\rangle=k_s ⟨ v s , w ⟩ = k s and ⟨ y s , w ⟩ = − h s \langle y_s,w\rangle=-h_s ⟨ y s , w ⟩ = − h s for s ≤ t s\le t s ≤ t : the terms − h s + h s -h_s+h_s − h s + h s cancel at every update. Therefore
h t 2 ≤ ∥ y t ∥ 2 ∥ w ∥ 2 = ∥ y t ∥ 2 ( 1 + ∑ j = τ + 1 t − 1 h j 2 R j 2 ) ≤ R 2 + 1 4 h t 2 . h_t^2\le\lVert y_t\rVert^2\lVert w\rVert^2=\lVert y_t\rVert^2\left(1+\sum_{j=\tau+1}^{t-1}\frac{h_j^2}{R_j^2}\right)\le R^2+\frac{1}{4}h_t^2. h t 2 ≤ ∥ y t ∥ 2 ∥ w ∥ 2 = ∥ y t ∥ 2 ( 1 + j = τ + 1 ∑ t − 1 R j 2 h j 2 ) ≤ R 2 + 4 1 h t 2 .
Thus h t ≤ 2 R / 3 ≤ 2 R h_t\le2R/\sqrt{3}\le2R h t ≤ 2 R / 3 ≤ 2 R ; as the identity is pathwise, w w w may be chosen after the path.
A Fixed I.I.D. Witness and the Rate Contradiction
Proof of Theorem 8 . Choose max { β p , a } < u < min { r , 1 } \max\{\beta_p,a\}<u<\min\{r,1\} max { β p , a } < u < min { r , 1 } . A finite common D > 0 D>0 D > 0 makes b t = D t − u b_t=Dt^{-u} b t = D t − u dominate the proposed logarithmic envelope. Suppose this weaker envelope holds with probability at least 1 − δ 1-\delta 1 − δ on every finite-dimensional instance. For a large deterministic N N N , set
μ = 8 D N − u , κ = 1 / 128 , B = 1 / 16 , A = ( κ / μ ) 1 / ( p − 1 ) , π = μ / A . \mu=8DN^{-u},\qquad\kappa=1/128,\qquad B=1/16,\qquad A=(\kappa/\mu)^{1/(p-1)},\qquad\pi=\mu/A. μ = 8 D N − u , κ = 1/128 , B = 1/16 , A = ( κ / μ ) 1/ ( p − 1 ) , π = μ / A .
Choose an integer d N ≥ 2 N 2 / ( 1 − δ ) d_N\ge2N^2/(1-\delta) d N ≥ 2 N 2 / ( 1 − δ ) . Take N N N large enough that μ ≤ 1 / 2 \mu\le1/2 μ ≤ 1/2 , A ≥ 1 A\ge1 A ≥ 1 , and π ≤ 1 / 2 \pi\le1/2 π ≤ 1/2 . Independently each round, draw Y ∼ Bernoulli ( π ) Y\sim\operatorname{Bernoulli}(\pi) Y ∼ Bernoulli ( π ) , a uniform J ∈ { 1 , … , d N } J\in\{1,\ldots,d_N\} J ∈ { 1 , … , d N } , and a uniform sign ϵ \epsilon ϵ , independent within a sample as well. Let R 0 = B R_0=B R 0 = B , R 1 = A R_1=A R 1 = A , and define
F ( x , y ; Y , J , ϵ ) = 1 2 ( x − 1 + μ ) + 2 − A Y x + 1 2 ∥ y ∥ 2 + R Y ϵ y J . F(x,y;Y,J,\epsilon)=\frac{1}{2}(x-1+\mu)_+^2-AYx+\frac{1}{2}\lVert y\rVert^2+R_Y\epsilon y_J. F ( x , y ; Y , J , ϵ ) = 2 1 ( x − 1 + μ ) + 2 − A Y x + 2 1 ∥ y ∥ 2 + R Y ϵ y J .
Admissibility. Each sample is convex and globally 1 1 1 -smooth: the two orthogonal Hessian blocks are bounded by one. In the first coordinate x x x , the sample loss attains its minimum at any x ≤ 1 − μ x\le1-\mu x ≤ 1 − μ when Y = 0 Y=0 Y = 0 , and at x = 1 − μ + A x=1-\mu+A x = 1 − μ + A when Y = 1 Y=1 Y = 1 ; in the nuisance block y y y , its minimizer is − R Y ϵ e J -R_Y\epsilon e_J − R Y ϵ e J . Thus every sample minimum is finite and attained. The population is
f ( x , y ) = 1 2 ( x − 1 + μ ) + 2 − μ x + 1 2 ∥ y ∥ 2 , f(x,y)=\frac{1}{2}(x-1+\mu)_+^2-\mu x+\frac{1}{2}\lVert y\rVert^2, f ( x , y ) = 2 1 ( x − 1 + μ ) + 2 − μx + 2 1 ∥ y ∥ 2 ,
with minimizer ( 1 , 0 ) (1,0) ( 1 , 0 ) at initial distance one. The fixed additive noise ξ = ( μ − A Y , R Y ϵ e J ) \xi=(\mu-AY,R_Y\epsilon e_J) ξ = ( μ − A Y , R Y ϵ e J ) is centered. Since π A p = κ \pi A^p=\kappa π A p = κ and μ = π A \mu=\pi A μ = π A ,
E ∣ μ − A Y ∣ p ≤ 2 κ , E ∥ ξ ∥ p ≤ 2 p − 1 ( 2 κ + B p + κ ) ≤ 6 / 128 + 2 / 16 < 1. \mathbb{E}|\mu-AY|^p\le2\kappa,\qquad\mathbb{E}\lVert\xi\rVert^p\le2^{p-1}(2\kappa+B^p+\kappa)\le6/128+2/16<1. E ∣ μ − A Y ∣ p ≤ 2 κ , E ∥ ξ ∥ p ≤ 2 p − 1 ( 2 κ + B p + κ ) ≤ 6/128 + 2/16 < 1.
For every state the gap is at least ∥ y ∥ 2 / 2 \lVert y\rVert^2/2 ∥ y ∥ 2 /2 ; when x ≤ 1 / 2 x\le1/2 x ≤ 1/2 it is also at least μ ( 1 − x ) − μ 2 / 2 ≥ μ / 4 \mu(1-x)-\mu^2/2\ge\mu/4 μ ( 1 − x ) − μ 2 /2 ≥ μ /4 .
Coupling and useful events. Feed the rule reference gradients ( − A Y t , y t + R Y t ϵ t e J t ) (-AY_t,y_t+R_{Y_t}\epsilon_t e_{J_t}) ( − A Y t , y t + R Y t ϵ t e J t ) until the first update whose first coordinate X t + 1 X_{t+1} X t + 1 exceeds 1 / 2 1/2 1/2 , or until round N N N . Denote that last retained round by S ≤ N S \le N S ≤ N . The first velocity is nonpositive, so X t X_t X t is nondecreasing. Under the shared random draws and seed, the reference and actual trajectories coincide through step S S S : prior to step S S S , every queried first coordinate satisfies X t ≤ 1 / 2 ≤ 1 − μ X_t \le1/2 \le1-\mu X t ≤ 1/2 ≤ 1 − μ , so all stochastic gradients, histories, and controls coincide. Let G \mathcal{G} G be the actual instance’s success event for all t ≤ N t \le N t ≤ N . Then P ( G ) ≥ 1 − δ \mathbb{P}(\mathcal{G}) \ge1-\delta P ( G ) ≥ 1 − δ . On G \mathcal{G} G a crossing occurs by N N N , since otherwise the final gap is at least μ / 4 = 2 b N \mu/4 = 2b_N μ /4 = 2 b N ; also
∥ y t ∥ ≤ 2 b t − 1 ( 2 ≤ t ≤ S + 1 ) . (53) \lVert y_t\rVert\le\sqrt{2b_{t-1}} \qquad(2 \le t \le S+1). \tag*{(53)} ∥ y t ∥ ≤ 2 b t − 1 ( 2 ≤ t ≤ S + 1 ) . (53)
Let C \mathcal{C} C mean that J 1 , … , J N J_1,\ldots,J_N J 1 , … , J N are distinct. The union bound gives P ( C c ) ≤ N ( N − 1 ) / ( 2 d N ) ≤ ( 1 − δ ) / 4 \mathbb{P}(\mathcal{C}^{c}) \le N(N-1)/(2d_N) \le(1-\delta)/4 P ( C c ) ≤ N ( N − 1 ) / ( 2 d N ) ≤ ( 1 − δ ) /4 . For Q p = p / ( p − 1 ) Q_p=p/(p-1) Q p = p / ( p − 1 ) choose 0 < θ < min { 1 , u Q p } 0<\theta<\min\{1,uQ_p\} 0 < θ < min { 1 , u Q p } and set n 0 = ⌈ N θ ⌉ n_0=\lceil N^\theta\rceil n 0 = ⌈ N θ ⌉ . Let E \mathcal{E} E mean Y t = 0 Y_t=0 Y t = 0 for t < n 0 t<n_0 t < n 0 . Then P ( E c ) ≤ n 0 π = O ( N θ − u Q p ) → 0 \mathbb{P}(\mathcal{E}^{c})\le n_0\pi=O(N^{\theta-uQ_p})\to0 P ( E c ) ≤ n 0 π = O ( N θ − u Q p ) → 0 ; the nuisance noise still acts.
Each pulse has a short useful window. Set P = h + u / ( p − 1 ) + 5 P=h+u/(p-1)+5 P = h + u / ( p − 1 ) + 5 , Λ = 3 a P / ρ \Lambda=3^aP/\rho Λ = 3 a P / ρ , and w j = ⌈ Λ ( 1 + j ) a log N ⌉ w_j=\lceil\Lambda(1+j)^a\log N\rceil w j = ⌈ Λ ( 1 + j ) a log N ⌉ . Uniformly for n 0 ≤ j ≤ N n_0\le j\le N n 0 ≤ j ≤ N , large N N N gives j ≥ t 0 j\ge t_0 j ≥ t 0 , w j ≤ j w_j\le j w j ≤ j , and
2 b j w j B 2 = O ( N θ ( a − u ) log N + N − θ u ) ⟶ 0. (54) \frac{2b_jw_j}{B^2}=O\left(N^{\theta(a-u)}\log N+N^{-\theta u}\right)\longrightarrow0. \tag*{(54)} B 2 2 b j w j = O ( N θ ( a − u ) log N + N − θ u ) ⟶ 0. (54)
Fix the realized controls through S S S . For a rare arrival j ≤ S j\le S j ≤ S , let h t ( j ) h_t^{(j)} h t ( j ) be the impulse response (52) with τ = j \tau=j τ = j , and put t j = min { S + 1 , j + w j + 1 } t_j=\min\{S+1,j+w_j+1\} t j = min { S + 1 , j + w j + 1 } . On G ∩ C \mathcal{G}\cap\mathcal{C} G ∩ C , the nuisance observations ζ 1 , … , ζ t j − 1 \zeta_1,\ldots,\zeta_{t_j-1} ζ 1 , … , ζ t j − 1 are nonzero and orthogonal, each has norm at least B B B , and the vector at j j j has norm A A A . Equation (53) gives ∥ y t j ∥ ≤ 2 b j \lVert y_{t_j}\rVert\le\sqrt{2b_j} ∥ y t j ∥ ≤ 2 b j ; thus Lemma 24 and (54) give h t j ( j ) ≤ 2 2 b j h_{t_j}^{(j)}\le2\sqrt{2b_j} h t j ( j ) ≤ 2 2 b j for every j ≥ n 0 j\ge n_0 j ≥ n 0 .
If t j < S + 1 t_j<S+1 t j < S + 1 , the first w j w_j w j subsequent momentum coefficients satisfy
∏ i = j + 1 j + w j β i ≤ exp ( − ρ w j 3 a ( 1 + j ) a ) ≤ N − P . \prod_{i=j+1}^{j+w_j}\beta_i
\le\exp\left(-\frac{\rho w_j}{3^a(1+j)^a}\right)
\le N^{-P}. i = j + 1 ∏ j + w j β i ≤ exp ( − 3 a ( 1 + j ) a ρ w j ) ≤ N − P .
Every subsequent factor is at most one. Since c j ≤ 1 c_j\le1 c j ≤ 1 , the polynomial bound on the step sizes in (17) implies pathwise that
0 ≤ h S + 1 ( j ) − h t j ( j ) ≤ A H N ( 1 + N ) h N − P ≤ C 0 N − 4 , (55) 0\le h_{S+1}^{(j)}-h_{t_j}^{(j)}
\le AHN(1+N)^hN^{-P}
\le C_0N^{-4}, \tag*{(55)} 0 ≤ h S + 1 ( j ) − h t j ( j ) ≤ A H N ( 1 + N ) h N − P ≤ C 0 N − 4 , (55)
with C 0 C_0 C 0 depending only on common fixed parameters; indeed A = ( κ / ( 8 D ) ) 1 / ( p − 1 ) N u / ( p − 1 ) A=(\kappa/(8D))^{1/(p-1)}N^{u/(p-1)} A = ( κ / ( 8 D ) ) 1/ ( p − 1 ) N u / ( p − 1 ) . For t j = S + 1 t_j=S+1 t j = S + 1 the tail is zero.
Contradiction on total progress. The displacement along the first coordinate is X S + 1 = ∑ j ≤ S Y j h S + 1 ( j ) X_{S+1}=\sum_{j\le S}Y_jh_{S+1}^{(j)} X S + 1 = ∑ j ≤ S Y j h S + 1 ( j ) . On G ∩ C ∩ E \mathcal{G}\cap\mathcal{C}\cap\mathcal{E} G ∩ C ∩ E , it must exceed 1 / 2 1/2 1/2 , but the preceding bounds give
1 2 < X S + 1 ≤ 2 2 D ∑ j = n 0 N Y j j − u / 2 + C 0 N − 3 . \frac{1}{2}<X_{S+1}\le2\sqrt{2D}\sum_{j=n_0}^{N}Y_jj^{-u/2}+C_0N^{-3}. 2 1 < X S + 1 ≤ 2 2 D j = n 0 ∑ N Y j j − u /2 + C 0 N − 3 .
Multiply by that event’s indicator and take expectations. Dropping the indicator on the nonnegative right side and using E Y j = π \mathbb{E}Y_j=\pi E Y j = π yields
1 2 P ( G ∩ C ∩ E ) ≤ 2 2 D π ∑ j = 1 N j − u / 2 + C 0 N − 3 . (56) \frac{1}{2}\mathbb{P}(\mathcal{G}\cap\mathcal{C}\cap\mathcal{E})
\le2\sqrt{2D}\,\pi\sum_{j=1}^{N}j^{-u/2}+C_0N^{-3}. \tag*{(56)} 2 1 P ( G ∩ C ∩ E ) ≤ 2 2 D π j = 1 ∑ N j − u /2 + C 0 N − 3 . (56)
The left side has lim inf \liminf lim inf at least 3 ( 1 − δ ) / 8 3(1-\delta)/8 3 ( 1 − δ ) /8 . The right side is O ( N 1 − u ( Q p + 1 / 2 ) ) + O ( N − 3 ) → 0 O(N^{1-u(Q_p+1/2)})+O(N^{-3})\to0 O ( N 1 − u ( Q p + 1/2 ) ) + O ( N − 3 ) → 0 because u > β p = 1 / ( Q p + 1 / 2 ) u>\beta_p=1/(Q_p+1/2) u > β p = 1/ ( Q p + 1/2 ) and u < 1 u<1 u < 1 . This contradiction gives prefix failure strictly greater than δ \delta δ for one fixed law and finite dimension. ■
The same argument gives the fixed-time analogue.
Proposition 25 (Fixed-time dimension-uniform lower bound). Fix p ∈ ( 1 , 2 ] p \in(1,2] p ∈ ( 1 , 2 ] and a ∈ [ 0 , 1 ) a \in[0,1) a ∈ [ 0 , 1 ) , let C > 0 C > 0 C > 0 and k ≥ 0 k \ge0 k ≥ 0 be finite, and let r > max { β p , a } r > \max\{\beta_p,a\} r > max { β p , a } . Let ( r u l e δ ) δ ∈ ( 0 , 1 ) (\mathrm{rule}_{\delta})_{\delta\in(0,1)} ( rule δ ) δ ∈ ( 0 , 1 ) satisfy the conditions of A u n i f ( a ) \mathcal{A}_{\mathrm{unif}}(a) A unif ( a ) with ρ \rho ρ , t 0 t_0 t 0 , and h h h independent of δ \delta δ , and with H H H replaced by H δ − h 0 H\delta^{-h_0} H δ − h 0 for constants H , h 0 ≥ 0 H,h_0 \ge0 H , h 0 ≥ 0 independent of δ \delta δ . There are δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , a deterministic integer t ≥ 1 t \ge1 t ≥ 1 , and a finite-dimensional instance with L = R = σ = 1 L=R=\sigma=1 L = R = σ = 1 , fixed before the samples and the seed are drawn and satisfying the conditions of Theorem 8 , such that ruleδ _\delta δ satisfies P { f ( x t + 1 ) − f ⋆ > C t − r [ log ( e t / δ ) ] k } > δ \mathbb{P}\{f(x_{t+1})-f^\star> Ct^{-r}[\log(et/\delta)]^k\}>\delta P { f ( x t + 1 ) − f ⋆ > C t − r [ log ( e t / δ ) ] k } > δ . Here C C C and k k k are shared across dimensions and do not depend on δ \delta δ or t t t .
With polylogarithmic dependence on 1 / δ 1/\delta 1/ δ , no fixed-time exponent above max { β p , a } \max\{\beta_p,a\} max { β p , a } is therefore attainable either.
Proof of Proposition 25. Suppose the envelope holds for every δ \delta δ , every deterministic time, and every finite-dimensional instance. Choose max { β p , a } < u < min { r , 1 } \max\{\beta_p,a\}<u<\min\{r,1\} max { β p , a } < u < min { r , 1 } . For each deterministic N N N , put
δ N = 1 4 N , D N = C log k ( 4 e N 2 ) , b N , t = D N t − u . \delta_N=\frac{1}{4N}, \qquad D_N=C\log^k(4eN^2), \qquad b_{N,t}=D_Nt^{-u}. δ N = 4 N 1 , D N = C log k ( 4 e N 2 ) , b N , t = D N t − u .
Since t − r ≤ t − u t^{-r}\le t^{-u} t − r ≤ t − u and log ( e t / δ N ) ≤ log ( 4 e N 2 ) \log(et/\delta_N)\le\log(4eN^2) log ( e t / δ N ) ≤ log ( 4 e N 2 ) for 1 ≤ t ≤ N 1\le t\le N 1 ≤ t ≤ N , the envelope of ruleδ N _{\delta_N} δ N is at most b N , t b_{N,t} b N , t on this prefix, and a union bound shows that, on every instance, f ( x t + 1 ) − f ⋆ ≤ b N , t f(x_{t+1})-f^\star\le b_{N,t} f ( x t + 1 ) − f ⋆ ≤ b N , t for all t ≤ N t\le N t ≤ N with probability at least 3 / 4 3/4 3/4 ; there η t ≤ H ( 4 N ) h 0 ( 1 + N ) h \eta_t\le H(4N)^{h_0}(1+N)^h η t ≤ H ( 4 N ) h 0 ( 1 + N ) h .
Run the proof of Theorem 8 for ruleδ N _{\delta_N} δ N , with D D D replaced by D N D_N D N , 1 − δ 1-\delta 1 − δ by 3 / 4 3/4 3/4 , and P P P by h + h 0 + u / ( p − 1 ) + 5 h+h_0+u/(p-1)+5 h + h 0 + u / ( p − 1 ) + 5 . Its estimates depend on the rule only through the common constants ρ , t 0 , H , h , h 0 \rho,t_0,H,h,h_0 ρ , t 0 , H , h , h 0 , and C ≤ D N = N o ( 1 ) C\le D_N=N^{o(1)} C ≤ D N = N o ( 1 ) , so they hold for all large N N N , with constants independent of N N N and of the rule. Explicitly, μ = 8 D N N − u → 0 \mu=8D_NN^{-u}\to0 μ = 8 D N N − u → 0 , d N ≥ 8 N 2 / 3 d_N\ge8N^{2/3} d N ≥ 8 N 2/3 gives P ( C c ) ≤ 3 / 16 \mathbb{P}(\mathcal{C}^c)\le3/16 P ( C c ) ≤ 3/16 , and, uniformly for n 0 ≤ j ≤ N n_0\le j\le N n 0 ≤ j ≤ N ,
π = κ − 1 / ( p − 1 ) μ Q p = O ( D N Q p N − u Q p ) , P ( E c ) ≤ n 0 π = O ( D N Q p N θ − u Q p ) , \pi=\kappa^{-1/(p-1)}\mu Q_p=O(D_N^{Q_p}N^{-uQ_p}), \qquad\mathbb{P}(\mathcal{E}^c)\le n_0\pi=O(D_N^{Q_p}N^{\theta-uQ_p}), π = κ − 1/ ( p − 1 ) μ Q p = O ( D N Q p N − u Q p ) , P ( E c ) ≤ n 0 π = O ( D N Q p N θ − u Q p ) ,
2 b N , j w j B 2 = O ( D N [ N θ ( a − u ) log N + N − θ u ] ) , \frac{2b_{N,j}w_j}{B^2}=O\left(D_N\left[N^{\theta(a-u)}\log N+N^{-\theta u}\right]\right), B 2 2 b N , j w j = O ( D N [ N θ ( a − u ) log N + N − θ u ] ) ,
all of which tend to zero. In (55) , A ≤ ( κ / ( 8 C ) ) 1 / ( p − 1 ) N u / ( p − 1 ) A\le(\kappa/(8C))^{1/(p-1)}N^{u/(p-1)} A ≤ ( κ / ( 8 C ) ) 1/ ( p − 1 ) N u / ( p − 1 ) and η s ≤ H ( 4 N ) h 0 ( 1 + N ) h \eta_s\le H(4N)^{h_0}(1+N)^h η s ≤ H ( 4 N ) h 0 ( 1 + N ) h ; since 1 + h + h 0 + u / ( p − 1 ) − P = − 4 1+h+h_0+u/(p-1)-P=-4 1 + h + h 0 + u / ( p − 1 ) − P = − 4 , the tail is still O ( N − 4 ) O(N^{-4}) O ( N − 4 ) . The left side of (56) is at least ( 3 / 4 − 3 / 16 − o ( 1 ) ) / 2 (3/4-3/16-o(1))/2 ( 3/4 − 3/16 − o ( 1 )) /2 , with liminf at least 9 / 32 9/32 9/32 , whereas its right side is O ( D N Q p + 1 / 2 N 1 − u ( Q p + 1 / 2 ) ) + O ( N − 3 ) → 0 O(D_N^{Q_p+1/2}N^{1-u(Q_p+1/2)})+O(N^{-3})\to0 O ( D N Q p + 1/2 N 1 − u ( Q p + 1/2 ) ) + O ( N − 3 ) → 0 as u > β p = 1 / ( Q p + 1 / 2 ) u>\beta_p=1/(Q_p+1/2) u > β p = 1/ ( Q p + 1/2 ) . Hence, for some N N N , the instance of dimension d N d_N d N fails the prefix guarantee with probability above 1 / 4 = N δ N 1/4=N\delta_N 1/4 = N δ N , and the union bound gives a deterministic t ≤ N t\le N t ≤ N with fixed-time failure probability above δ N \delta_N δ N . ■
Time-Uniform Averaging Momentum
This appendix proves Theorem 9 and Propositions 26 and 27.
Proof of Theorem 9 . Write F t = f ( x t ) − f ⋆ F_t=f(x_t)-f^\star F t = f ( x t ) − f ⋆ , μ t = ∇ f ( x t ) \mu_t=\nabla f(x_t) μ t = ∇ f ( x t ) , and D t = ∥ z t − x ⋆ ∥ D_t=\lVert z_t-x^\star\rVert D t = ∥ z t − x ⋆ ∥ . The averaging update gives
x t = 1 t ∑ s = 1 t z s , z t = t x t − ( t − 1 ) x t − 1 . (57) x_t=\frac{1}{t}\sum_{s=1}^{t}z_s,\qquad z_t=tx_t-(t-1)x_{t-1}. \tag*{(57)} x t = t 1 s = 1 ∑ t z s , z t = t x t − ( t − 1 ) x t − 1 . (57)
At t = 1 t=1 t = 1 the second identity is independent of x 0 x_0 x 0 .
A smooth online-to-batch inequality. By the standard inequality for smooth convex functions [45 Theorem 2.1.5] and ∇ f ( x ⋆ ) = 0 \nabla f(x^\star)=0 ∇ f ( x ⋆ ) = 0 , we have
⟨ ∇ f ( x ) , x − x ⋆ ⟩ ≥ f ( x ) − f ⋆ + ∥ ∇ f ( x ) ∥ 2 2 L . \langle\nabla f(x),x-x^\star\rangle\ge f(x)-f^\star+\frac{\lVert\nabla f(x)\rVert^2}{2L}. ⟨ ∇ f ( x ) , x − x ⋆ ⟩ ≥ f ( x ) − f ⋆ + 2 L ∥ ∇ f ( x ) ∥ 2 .
Combining it with (57) and ⟨ μ t , x t − x t − 1 ⟩ ≥ F t − F t − 1 \langle\mu_t, x_t-x_{t-1}\rangle\ge F_t-F_{t-1} ⟨ μ t , x t − x t − 1 ⟩ ≥ F t − F t − 1 gives
⟨ μ t , z t − x ⋆ ⟩ ≥ t F t − ( t − 1 ) F t − 1 + ∥ μ t ∥ 2 2 L . (58) \langle\mu_t,z_t-x^\star\rangle\ge tF_t-(t-1)F_{t-1}+\frac{\|\mu_t\|^2}{2L}. \tag*{(58)} ⟨ μ t , z t − x ⋆ ⟩ ≥ t F t − ( t − 1 ) F t − 1 + 2 L ∥ μ t ∥ 2 . (58)
This is the smooth form of the anytime online-to-batch inequality [9 ] .
A pathwise energy recursion. Let e t = d t − μ t e_t=d_t-\mu_t e t = d t − μ t . Expanding the update and using (58) and ∥ μ t + e t ∥ 2 ≤ 2 ∥ μ t ∥ 2 + 2 ∥ e t ∥ 2 \|\mu_t+e_t\|^2\le2\|\mu_t\|^2+2\|e_t\|^2 ∥ μ t + e t ∥ 2 ≤ 2∥ μ t ∥ 2 + 2∥ e t ∥ 2 gives
D t + 1 2 ≤ D t 2 − 2 γ t { t F t − ( t − 1 ) F t − 1 } + Δ t , Δ t = 2 γ t 2 ∥ e t ∥ 2 − 2 γ t ⟨ e t , z t − x ⋆ ⟩ . D_{t+1}^2\le D_t^2-2\gamma_t\{tF_t-(t-1)F_{t-1}\}+\Delta_t,\qquad\Delta_t=2\gamma_t^2\|e_t\|^2-2\gamma_t\langle e_t,z_t-x^\star\rangle. D t + 1 2 ≤ D t 2 − 2 γ t { t F t − ( t − 1 ) F t − 1 } + Δ t , Δ t = 2 γ t 2 ∥ e t ∥ 2 − 2 γ t ⟨ e t , z t − x ⋆ ⟩ .
Here the omitted term involving ∥ μ t ∥ 2 \|\mu_t\|^2 ∥ μ t ∥ 2 is nonpositive since γ t ≤ c 0 / ( 4 L ℓ ˉ 2 ) ≤ 1 / ( 2 L ) \gamma_t\le c_0/(4L\bar{\ell}^2)\le1/(2L) γ t ≤ c 0 / ( 4 L ℓ ˉ 2 ) ≤ 1/ ( 2 L ) . Define W 1 = D 1 2 W_1=D_1^2 W 1 = D 1 2 and
W t + 1 = D t + 1 2 + 2 t γ t F t + 2 ∑ s = 1 t − 1 s ( γ s − γ s + 1 ) F s . W_{t+1}=D_{t+1}^2+2t\gamma_tF_t+2\sum_{s=1}^{t-1}s(\gamma_s-\gamma_{s+1})F_s. W t + 1 = D t + 1 2 + 2 t γ t F t + 2 s = 1 ∑ t − 1 s ( γ s − γ s + 1 ) F s .
Since γ t \gamma_t γ t is nonincreasing, W t ≥ D t 2 ≥ 0 W_t\ge D_t^2\ge0 W t ≥ D t 2 ≥ 0 . The exact difference W t + 1 − W t = D t + 1 2 − D t 2 + 2 γ t { t F t − ( t − 1 ) F t − 1 } W_{t+1}-W_t=D_{t+1}^2-D_t^2+2\gamma_t\{tF_t-(t-1)F_{t-1}\} W t + 1 − W t = D t + 1 2 − D t 2 + 2 γ t { t F t − ( t − 1 ) F t − 1 } therefore gives W t + 1 ≤ W t + Δ t W_{t+1}\le W_t+\Delta_t W t + 1 ≤ W t + Δ t , also at t = 1 t=1 t = 1 without an F 0 F_0 F 0 term.
Predictable localization and conditional clipping. Let τ = inf { t ≥ 1 : W t ≥ 2 R 2 } \tau=\inf\{t\ge1:W_t\ge2R^2\} τ = inf { t ≥ 1 : W t ≥ 2 R 2 } and I t = 1 { t < τ } I_t=\mathbf{1}_{\{t<\tau\}} I t = 1 { t < τ } . Each W s W_s W s is F s − 1 \mathcal{F}_{s-1} F s − 1 -measurable, so I t I_t I t is F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable, that is, predictable, and nonincreasing in t t t . Since ∥ d s ∥ ≤ λ s \|d_s\|\le\lambda_s ∥ d s ∥ ≤ λ s , the states z t z_t z t , x t x_t x t and the errors e t e_t e t are bounded at each fixed t t t , so e t e_t e t is integrable. On t < τ t<\tau t < τ , all s ≤ t s\le t s ≤ t satisfy D s < 2 R D_s<\sqrt{2}R D s < 2 R . Thus (57) gives ∥ x t − x ⋆ ∥ < 2 R \|x_t-x^\star\|<2R ∥ x t − x ⋆ ∥ < 2 R and ∥ μ t ∥ ≤ 2 L R ≤ λ t / 2 \|\mu_t\|\le2LR\le\lambda_t/2 ∥ μ t ∥ ≤ 2 L R ≤ λ t /2 . Lemma 12, applied conditionally on this predictable event, yields
∥ e t ∥ ≤ 3 2 λ t , ∥ E t − 1 e t ∥ ≤ B t : = 2 σ p λ t 1 − p , E t − 1 ∥ e t ∥ 2 ≤ V t : = 2 σ p λ t 2 − p . (59) \|e_t\|\le\frac{3}{2}\lambda_t,\qquad\|\mathbb{E}_{t-1}e_t\|\le B_t:=2\sigma^p\lambda_t^{1-p},\qquad\mathbb{E}_{t-1}\|e_t\|^2\le V_t:=2\sigma^p\lambda_t^{2-p}. \tag*{(59)} ∥ e t ∥ ≤ 2 3 λ t , ∥ E t − 1 e t ∥ ≤ B t := 2 σ p λ t 1 − p , E t − 1 ∥ e t ∥ 2 ≤ V t := 2 σ p λ t 2 − p . (59)
For q > 1 q>1 q > 1 , integral comparison gives
∑ t ≥ 1 1 t ( h δ + log t ) q ≤ 1 h δ q + 1 ( q − 1 ) h δ q − 1 . \sum_{t\ge1}\frac{1}{t(h_\delta+\log t)^q}\le\frac{1}{h_\delta^q}+\frac{1}{(q-1)h_\delta^{q-1}}. t ≥ 1 ∑ t ( h δ + log t ) q 1 ≤ h δ q 1 + ( q − 1 ) h δ q − 1 1 .
Since λ t p ≥ σ p t \lambda_t^p\ge\sigma^p t λ t p ≥ σ p t , the deterministic budgets are
∑ t γ t B t ≤ 4 c 0 R h δ , ∑ t γ t 2 V t ≤ 4 c 0 2 R 2 h δ 3 , γ t λ t = c 0 R ℓ ˉ t 2 . (60) \sum_t\gamma_tB_t\le\frac{4c_0R}{h_\delta},\qquad\sum_t\gamma_t^2V_t\le\frac{4c_0^2R^2}{h_\delta^3},\qquad\gamma_t\lambda_t=\frac{c_0R}{\bar{\ell}_t^2}. \tag*{(60)} t ∑ γ t B t ≤ h δ 4 c 0 R , t ∑ γ t 2 V t ≤ h δ 3 4 c 0 2 R 2 , γ t λ t = ℓ ˉ t 2 c 0 R . (60)
These include σ = 0 \sigma=0 σ = 0 , when B t = V t = 0 B_t=V_t=0 B t = V t = 0 .
One application of the common energy bound. Apply Lemma 15 with P m = W m + 1 P_m=W_{m+1} P m = W m + 1 for m ≥ 0 m\ge0 m ≥ 0 , the predictable indicators J t = I t J_t=I_t J t = I t , E = Ω \mathcal{E}=\Omega E = Ω , p 0 = R 2 p_0=R^2 p 0 = R 2 , q = h δ q=h_\delta q = h δ , and
a t = 2 γ t 2 , w t = − 2 γ t ( z t − x ⋆ ) , s t = 2 γ t , M t = 3 2 λ t , U t = 2 λ t . a_t=2\gamma_t^2,\qquad w_t=-2\gamma_t(z_t-x^\star),\qquad s_t=2\gamma_t,\qquad M_t=\frac{3}{2}\lambda_t,\qquad U_t=2\lambda_t. a t = 2 γ t 2 , w t = − 2 γ t ( z t − x ⋆ ) , s t = 2 γ t , M t = 2 3 λ t , U t = 2 λ t .
The pathwise recursion W t + 1 ≤ W t + Δ t W_{t+1}\le W_t+\Delta_t W t + 1 ≤ W t + Δ t is the required one, P 0 = D 1 2 ≤ R 2 P_0=D_1^2\le R^2 P 0 = D 1 2 ≤ R 2 , and ∥ w t ∥ ≤ s t P t − 1 \|w_t\|\le s_t\sqrt{P_{t-1}} ∥ w t ∥ ≤ s t P t − 1 because D t 2 ≤ W t D_t^2\le W_t D t 2 ≤ W t . On I t = 1 I_t=1 I t = 1 , (59) gives B t B_t B t , V t V_t V t , and M t M_t M t , and Lemma 12 also gives ∥ e t − E t − 1 e t ∥ ≤ U t \|e_t-\mathbb{E}_{t-1}e_t\|\le U_t ∥ e t − E t − 1 e t ∥ ≤ U t . By (60) and γ t λ t = c 0 R / ℓ ˉ t 2 ≤ c 0 R / h δ 2 \gamma_t\lambda_t=c_0R/\bar{\ell}_t^2\le c_0R/h_\delta^2 γ t λ t = c 0 R / ℓ ˉ t 2 ≤ c 0 R / h δ 2 , the budgets of the lemma satisfy
A ≤ 8 c 0 2 R 2 h δ 3 , K 0 ≤ 9 c 0 2 R 2 2 h δ 4 , B 0 ≤ 8 c 0 R h δ , V 0 ≤ 16 c 0 2 R 2 h δ 3 , J 0 ≤ 4 c 0 R h δ 2 . A\le\frac{8c_0^2R^2}{h_\delta^3},\qquad K_0\le\frac{9c_0^2R^2}{2h_\delta^4},\qquad B_0\le\frac{8c_0R}{h_\delta},\qquad V_0\le\frac{16c_0^2R^2}{h_\delta^3},\qquad J_0\le\frac{4c_0R}{h_\delta^2}. A ≤ h δ 3 8 c 0 2 R 2 , K 0 ≤ 2 h δ 4 9 c 0 2 R 2 , B 0 ≤ h δ 8 c 0 R , V 0 ≤ h δ 3 16 c 0 2 R 2 , J 0 ≤ h δ 2 4 c 0 R .
so C ≤ R 2 ( 1 + 29 c 0 2 / h δ 3 ) C\le R^2(1+29c_0^2/h_\delta^3) C ≤ R 2 ( 1 + 29 c 0 2 / h δ 3 ) and D ≤ 24 c 0 R / h δ D\le24c_0R/h_\delta D ≤ 24 c 0 R / h δ . Since c 0 = 1 / 128 c_0=1/128 c 0 = 1/128 and h δ ≥ 8 h_\delta\ge8 h δ ≥ 8 , ( C + D ) 2 ≤ R 2 ( 1 + 29 c 0 2 / h δ 3 + 24 c 0 / h δ ) 2 < 2 R 2 (\sqrt{C}+D)^2\le R^2(1+29c_0^2/h_\delta^3+24c_0/h_\delta)^2<2R^2 ( C + D ) 2 ≤ R 2 ( 1 + 29 c 0 2 / h δ 3 + 24 c 0 / h δ ) 2 < 2 R 2 . Except on probability e − h δ < δ e^{-h_\delta}<\delta e − h δ < δ , the lemma therefore gives W m + 1 < 2 R 2 W_{m+1} < 2R^2 W m + 1 < 2 R 2 whenever I m = 1 I_m = 1 I m = 1 . If τ < ∞ \tau< \infty τ < ∞ , then τ ≥ 2 \tau\ge2 τ ≥ 2 because W 1 ≤ R 2 W_1 \le R^2 W 1 ≤ R 2 , and m = τ − 1 m = \tau- 1 m = τ − 1 has I m = 1 I_m = 1 I m = 1 but W m + 1 = W τ ≥ 2 R 2 W_{m+1} = W_\tau\ge2R^2 W m + 1 = W τ ≥ 2 R 2 . Hence τ = ∞ \tau= \infty τ = ∞ on this event, and simultaneously for every T ≥ 1 T \ge1 T ≥ 1 ,
D T + 1 2 + 2 T γ T F T ≤ W T + 1 < 2 R 2 . D_{T+1}^2 + 2T\gamma_TF_T \le W_{T+1} < 2R^2. D T + 1 2 + 2 T γ T F T ≤ W T + 1 < 2 R 2 .
In particular, D T + 1 < 2 R D_{T+1} < \sqrt{2}R D T + 1 < 2 R and F T ≤ R 2 / ( T γ T ) = 128 R λ T ℓ ˉ T 2 / T F_T \le R^2/(T\gamma_T) = 128R\lambda_T\bar{\ell}_T^2/T F T ≤ R 2 / ( T γ T ) = 128 R λ T ℓ ˉ T 2 / T .
The last iterate. Convexity of the implemented update and smoothness at the minimizer give
f ( x T + 1 ) − f ⋆ ≤ T T + 1 F T + f ( z T + 1 ) − f ⋆ T + 1 ≤ 128 R λ T ℓ ˉ T 2 + 2 L R 2 T + 1 . \begin{aligned}
f(x_{T+1}) - f^\star\le\frac{T}{T+1}F_T + \frac{f(z_{T+1}) - f^\star}{T+1} \\
&\le\frac{128R\lambda_T\bar{\ell}_T^2 + 2LR^2}{T+1}.
\end{aligned} f ( x T + 1 ) − f ⋆ ≤ T + 1 T F T + T + 1 f ( z T + 1 ) − f ⋆ ≤ T + 1 128 R λ T ℓ ˉ T 2 + 2 L R 2 .
Finally, λ T ≤ 4 L R + σ T 1 / p \lambda_T \le4LR + \sigma T^{1/p} λ T ≤ 4 L R + σ T 1/ p , ℓ ˉ T ≥ 1 \bar{\ell}_T \ge1 ℓ ˉ T ≥ 1 , and ( T + 1 ) − 1 ≤ T − 1 (T+1)^{-1} \le T^{-1} ( T + 1 ) − 1 ≤ T − 1 prove (22) . ■
Proposition 26 (Exact momentum conventions). The states in (20) obey
x t + 1 = x t − η t d t + β ~ t ( x t − x t − 1 ) , η t = γ t t + 1 , β ~ t = t − 1 t + 1 . x_{t+1} = x_t - \eta_td_t + \widetilde{\beta}_t(x_t - x_{t-1}), \qquad\eta_t = \frac{\gamma_t}{t+1}, \qquad\widetilde{\beta}_t = \frac{t-1}{t+1}. x t + 1 = x t − η t d t + β t ( x t − x t − 1 ) , η t = t + 1 γ t , β t = t + 1 t − 1 . with x 0 = x 1 x_0 = x_1 x 0 = x 1 . In the velocity convention v t + 1 = β t v t + d t v_{t+1} = \beta_tv_t + d_t v t + 1 = β t v t + d t , x t + 1 = x t − η t v t + 1 x_{t+1} = x_t - \eta_tv_{t+1} x t + 1 = x t − η t v t + 1 , v 1 = 0 v_1 = 0 v 1 = 0 , the equivalent parameters are β 1 = 0 \beta_1 = 0 β 1 = 0 and
β t = t − 1 t γ t − 1 γ t , α p 2 t ≤ 1 − β t ≤ 1 t ( t ≥ 2 ) , α p = p − 1 p . \beta_t = \frac{t-1}{t}\frac{\gamma_{t-1}}{\gamma_t}, \qquad\frac{\alpha_p}{2t} \le1-\beta_t \le\frac{1}{t} \quad(t \ge2), \qquad\alpha_p = \frac{p-1}{p}. β t = t t − 1 γ t γ t − 1 , 2 t α p ≤ 1 − β t ≤ t 1 ( t ≥ 2 ) , α p = p p − 1 . The step sizes are uniformly bounded by c 0 / ( 8 L h δ 2 ) c_0/(8Lh_\delta^2) c 0 / ( 8 L h δ 2 ) .
Proof Use z t − x t = ( t − 1 ) ( x t − x t − 1 ) z_t-x_t=(t-1)(x_t-x_{t-1}) z t − x t = ( t − 1 ) ( x t − x t − 1 ) in the averaging update. Eliminating velocity then gives β t = β ~ t η t − 1 / η t \beta_t=\widetilde{\beta}_t\eta_{t-1}/\eta_t β t = β t η t − 1 / η t . For r ( s ) = max { 4 L R , σ s 1 / p } ( h δ + log s ) 2 r(s)=\max\{4LR,\sigma s^{1/p}\}(h_\delta+\log s)^2 r ( s ) = max { 4 L R , σ s 1/ p } ( h δ + log s ) 2 , γ t = c 0 R / r ( t ) \gamma_t=c_0R/r(t) γ t = c 0 R / r ( t ) , and almost everywhere
0 ≤ d log r ( s ) d log s ≤ 1 p + 2 h δ ≤ 1 − α p 2 . 0 \le\frac{d\log r(s)}{d\log s} \le\frac{1}{p}+\frac{2}{h_\delta} \le1-\frac{\alpha_p}{2}. 0 ≤ d log s d log r ( s ) ≤ p 1 + h δ 2 ≤ 1 − 2 α p . Integrating over [ t − 1 , t ] [t-1,t] [ t − 1 , t ] proves
t − 1 t ≤ β t ≤ ( t − 1 t ) α p / 2 < 1. \frac{t-1}{t} \le\beta_t \le\left(\frac{t-1}{t}\right)^{\alpha_p/2} < 1. t t − 1 ≤ β t ≤ ( t t − 1 ) α p /2 < 1. Concavity of u ↦ u α p / 2 u \mapsto u^{\alpha_p/2} u ↦ u α p /2 yields the asserted lower bound on 1 − β t 1-\beta_t 1 − β t ; the upper bound is immediate. The bound on the step sizes follows from λ t ≥ 4 L R \lambda_t \ge4LR λ t ≥ 4 L R and t + 1 ≥ 2 t+1 \ge2 t + 1 ≥ 2 . ■
Proposition 27 (Fixed momentum coefficient with unbounded step sizes). For every fixed b ∈ ( 0 , 1 ) b \in(0,1) b ∈ ( 0 , 1 ) , the trajectory in Theorem 9 admits the exact representation
w t + 1 = b w t + clip ( g t , Λ t ) , x t + 1 = x t − H t w t + 1 , w 1 = 0 , w_{t+1} = bw_t + \operatorname{clip}(g_t,\Lambda_t), \qquad x_{t+1} = x_t - H_tw_{t+1}, \qquad w_1 = 0, w t + 1 = b w t + clip ( g t , Λ t ) , x t + 1 = x t − H t w t + 1 , w 1 = 0 , with deterministic finite step sizes H t → ∞ H_t \to\infty H t → ∞ and clipping thresholds Λ t \Lambda_t Λ t that may depend on the current stochastic gradient. In particular, a constant momentum coefficient b ∈ ( 0 , 1 ) b \in(0,1) b ∈ ( 0 , 1 ) does not by itself force the β p \beta_p β p barrier if exponentially growing step sizes H t H_t H t and clipping thresholds depending on the current gradient are permitted. Because H t H_t H t grows exponentially, it violates the polynomial bound on the step sizes in Theorem 7, so some restriction on the growth of the step sizes is needed there.
Proof Set
H 1 = γ 1 2 ( 1 − b ) 2 , H t = H 1 2 b − ( t − 1 ) t ( t + 1 ) , s t = t γ t b t − 1 2 H 1 , Λ t = s t min { ∥ g t ∥ , λ t } . H_1=\frac{\gamma_1}{2(1-b)^2},\qquad H_t=H_1\frac{2b^{-(t-1)}}{t(t+1)},\qquad s_t=\frac{t\gamma_t b^{t-1}}{2H_1},\qquad\Lambda_t=s_t\min\{\lVert g_t\rVert,\lambda_t\}. H 1 = 2 ( 1 − b ) 2 γ 1 , H t = H 1 t ( t + 1 ) 2 b − ( t − 1 ) , s t = 2 H 1 t γ t b t − 1 , Λ t = s t min {∥ g t ∥ , λ t } .
Since γ t ≤ γ 1 \gamma_t\le\gamma_1 γ t ≤ γ 1 and ∑ t ≥ 1 t b t − 1 = ( 1 − b ) − 2 \sum_{t\ge1}tb^{t-1}=(1-b)^{-2} ∑ t ≥ 1 t b t − 1 = ( 1 − b ) − 2 , 0 < s t ≤ 1 0<s_t\le1 0 < s t ≤ 1 . Therefore clip ( g t , Λ t ) = s t d t \operatorname{clip}(g_t,\Lambda_t)=s_td_t clip ( g t , Λ t ) = s t d t . At t = 1 t=1 t = 1 the displacement is − γ 1 d 1 / 2 -\gamma_1d_1/2 − γ 1 d 1 /2 . For t ≥ 2 t\ge2 t ≥ 2 , eliminating w t w_t w t gives
x t + 1 − x t = b H t H t − 1 ( x t − x t − 1 ) − H t s t d t = t − 1 t + 1 ( x t − x t − 1 ) − γ t t + 1 d t . x_{t+1}-x_t=b\frac{H_t}{H_{t-1}}(x_t-x_{t-1})-H_ts_td_t=\frac{t-1}{t+1}(x_t-x_{t-1})-\frac{\gamma_t}{t+1}d_t. x t + 1 − x t = b H t − 1 H t ( x t − x t − 1 ) − H t s t d t = t + 1 t − 1 ( x t − x t − 1 ) − t + 1 γ t d t .
This is exactly Proposition 26 , path by path. Also H t → ∞ H_t\to\infty H t → ∞ exponentially. When g t = 0 g_t=0 g t = 0 , take clipping at zero to be zero; if strictly positive thresholds are required, assign any positive threshold on that event without changing the update. ■
Comparison with existing averaging methods. Nguyen et al. [47 ] obtain the statistical exponent with horizon-free averaged methods. For their Algorithm 3, the proof of their Theorem D.1, via Lemma D.4 and Proposition D.5, gives ∥ z t − x ⋆ ∥ ≤ 2 R \lVert z_t-x^\star\rVert\le2R ∥ z t − x ⋆ ∥ ≤ 2 R on nested events over each finite prefix. Combining their query relation x t = ( 1 − a t ) y t + a t z t x_t=(1-a_t)y_t+a_tz_t x t = ( 1 − a t ) y t + a t z t (a t = 2 / ( t + 1 ) a_t=2/(t+1) a t = 2/ ( t + 1 ) ) with convexity and L L L -smoothness at x ⋆ x^\star x ⋆ gives
f ( x T + 1 ) − f ⋆ ≤ f ( y T + 1 ) − f ⋆ + 4 L R 2 T + 2 . f(x_{T+1})-f^\star\le f(y_{T+1})-f^\star+\frac{4LR^2}{T+2}. f ( x T + 1 ) − f ⋆ ≤ f ( y T + 1 ) − f ⋆ + T + 2 4 L R 2 .
Intersecting these nested events yields a time-uniform guarantee at the query state x T + 1 x_{T+1} x T + 1 as well, although their three-sequence accelerated scheme differs from the two-sequence recursion (20) . The high-probability regret bounds of Zhang and Cutkosky [71 ] assume bounded expected gradients and a horizon-dependent learner.