重尾噪声下裁剪 SGD 的最后迭代点因迭代期限未知而付出的代价

# The Cost of an Unknown Horizon for the Last Iterateof Clipped SGD under Heavy-Tailed Noise
Source: [https://arxiv.org/html/2610.33381](https://arxiv.org/html/2610.33381)
Yuxing PengZhiqing TangAffiliation:Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, ChinaAffiliation:Corresponding author:zhiqingtang@bnu\.edu\.cnWeijia JiaAffiliation:Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, ChinaAffiliation:Guangdong Key Lab of AI and Multi\-Modal Data Processing, Beijing Normal\-Hong Kong Baptist University, Zhuhai 519087, China

###### Abstract

Training is often stopped at a data\-dependent time, so guarantees for the last iterate must hold at all times simultaneously\. We determine the optimal time\-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy\-tailed noise with a bounded centralppth moment,1<p≤21<p\\leq 2\. A schedule without horizon or confidence inputs attainsO~​\(t−βp\)\\tilde\{O\}\(t^\{\-\\beta\_\{p\}\}\)at all times, withβp=2​\(p−1\)/\(3​p−1\)\\beta\_\{p\}=2\(p\-1\)/\(3p\-1\), also almost surely, and no rule that steps along the stochastic gradient at its current iterate attainsO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\)for anyr\>βpr\>\\beta\_\{p\}, even with adaptive step sizes and thresholds\. This rate lies between the optimal rateO⁡\(T−αp\)O\(T^\{\-\\alpha\_\{p\}\}\)for a known horizonTT,αp=\(p−1\)/p\\alpha\_\{p\}=\(p\-1\)/p, and the previous time\-uniform rateO~\(t−2\(p−1\)/\(3p\)\)\\tilde\{O\}\(t^\{\-2\(p\-1\)/\(3p\)\}\)\(Chezhegov et al\., ICLR 2026\); under finite variance, the exponents are1/21/2,2/52/5, and1/31/3\. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon \(Liu; Jiang et al\.\) but fails without one\. Querying gradients at the running average attainsO~​\(t−αp\)\\tilde\{O\}\(t^\{\-\\alpha\_\{p\}\}\)at all times, whereas heavy\-ball momentum with geometric forgetting and polynomially bounded steps cannot improve onβp\\beta\_\{p\}\.

## 1Introduction

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, 2026](https://arxiv.org/html/2610.33381#bib.bib2)\), large\-scale training increasingly avoids committing to a duration\([Hägele et al\., 2024](https://arxiv.org/html/2610.33381#bib.bib21)\), and schedule\-free methods are designed so that no stopping time has to be specified\([Defazio et al\., 2024b](https://arxiv.org/html/2610.33381#bib.bib13)\)\. 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\([Şimşekli et al\., 2019](https://arxiv.org/html/2610.33381#bib.bib56);[Zhang et al\., 2020](https://arxiv.org/html/2610.33381#bib.bib69)\), and gradient clipping\([Pascanu et al\., 2013](https://arxiv.org/html/2610.33381#bib.bib48)\)is a standard remedy, used routinely in training large language models\([Touvron et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib61)\)\. This paper asks what an unknown stopping time costs: how fast can the last iterate of clipped stochastic gradient descent \(SGD;[Robbins and Monro 1951](https://arxiv.org/html/2610.33381#bib.bib51)\) 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 probability1−δ1\-\\deltaat 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\., 2021](https://arxiv.org/html/2610.33381#bib.bib23)\)\. A guarantee holds at every data\-dependent stopping time exactly when it holds on one event, of probability at least1−δ1\-\\delta, at all times simultaneously \(Section[2](https://arxiv.org/html/2610.33381#S2)\)\. Under sub\-Gaussian noise, passing to such*time\-uniform*guarantees costs only logarithmic factors around the exponent1/21/2\([Li et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib32)\)\.

Under heavy\-tailed noise the price is polynomial, and we determine it: for noise with a bounded centralppth moment,1<p≤21<p\\leq 2, clipped SGD attains the last\-iterate errors

O⁡\(T−αp\)​with a known horizon​T,\\displaystyle O\\bigl\(T^\{\-\\alpha\_\{p\}\}\\bigr\)\\ \\text\{ with a known horizon \}T,O~​\(t−βp\)​at all times​t​simultaneously,\\displaystyle\\tilde\{O\}\\bigl\(t^\{\-\\beta\_\{p\}\}\\bigr\)\\ \\text\{ at all times \}t\\text\{ simultaneously\},whereαp=\(p−1\)/p\\alpha\_\{p\}=\(p\-1\)/p,βp=2​\(p−1\)/\(3​p−1\)\\beta\_\{p\}=2\(p\-1\)/\(3p\-1\), andO~\\tilde\{O\}hides logarithmic factors; under finite variance, the exponents are1/21/2and2/52/5\. The known\-horizon rate is due to[Liu \(2026a\)](https://arxiv.org/html/2610.33381#bib.bib35)and[Jiang et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib26); the time\-uniform rate is our main result\. Both exponents are optimal,αp\\alpha\_\{p\}among all algorithms that query stochastic gradients andβp\\beta\_\{p\}among all rules that query their current iterate and step along the resulting stochastic gradient\. For fixedδ≤1/8\\delta\\leq 1/8, every algorithm makingTTstochastic gradient queries has errorΩ⁡\(T−αp\)\\Omega\(T^\{\-\\alpha\_\{p\}\}\)with probability at least2​δ2\\deltaon some instance\([Jiang et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib26), Proposition 1\), and we prove that no such rule attainsO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\)at all times for anyr\>βpr\>\\beta\_\{p\}, whatever its step sizes and clipping thresholds\. The best previous time\-uniform rate,O~\(t−2\(p−1\)/\(3p\)\)\\tilde\{O\}\(t^\{\-2\(p\-1\)/\(3p\)\}\)orO~\(t−1/3\)\\tilde\{O\}\(t^\{\-1/3\}\)atp=2p=2, is due to[Chezhegov et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib8), 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 attainsO~​\(t−αp\)\\tilde\{O\}\(t^\{\-\\alpha\_\{p\}\}\)at all times\.

With clipping, high\-probability guarantees can depend only logarithmically on the confidence level\([Nazin et al\., 2019](https://arxiv.org/html/2610.33381#bib.bib40);[Gorbunov et al\., 2020](https://arxiv.org/html/2610.33381#bib.bib20);[Cutkosky and Mehta, 2021](https://arxiv.org/html/2610.33381#bib.bib10);[Sadiev et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib53);[Nguyen et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib44)\), as for robust mean estimators\([Catoni, 2012](https://arxiv.org/html/2610.33381#bib.bib5);[Devroye et al\., 2016](https://arxiv.org/html/2610.33381#bib.bib14);[Lugosi and Mendelson, 2019](https://arxiv.org/html/2610.33381#bib.bib39)\), whereas unclipped SGD can require polynomial dependence\([Sadiev et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib53)\); most of these guarantees concern an averaged or auxiliary output and need not apply to the last iterate\. Formally, we consider a convexLL\-smooth objectivef:ℝd→ℝf:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}with a minimizerx⋆x^\{\\star\}satisfying∥x1−x⋆∥≤R\\lVert x\_\{1\}\-x^\{\\star\}\\rVert\\leq R, and stochastic gradientsgtg\_\{t\}that are conditionally unbiased with

𝔼⁡\[∥gt−∇f​\(xt\)∥p\|ℱt−1\]≤σp,1<p≤2\.\\mathbb\{E\}\\bigl\[\\lVert g\_\{t\}\-\\nabla f\(x\_\{t\}\)\\rVert^\{p\}\\bigm\|\\mathcal\{F\}\_\{t\-1\}\\bigr\]\\leq\\sigma^\{p\},\\qquad 1<p\\leq 2\.Clipped SGD performs the updates

xt\+1=xt−ηt​clip⁡\(gt,λt\),clip⁡\(g,λ\)=min⁡\{1,λ/∥g∥\}​g,\\begin\{gathered\}x\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\),\\\\ \\operatorname\{clip\}\(g,\\lambda\)=\\min\\\{1,\\lambda/\\lVert g\\rVert\\\}\\,g,\\end\{gathered\}\(1\)whereηt\\eta\_\{t\}is the step size andλt\\lambda\_\{t\}the clipping threshold\. For an averaged output of clipped stochastic mirror descent,[Nguyen et al\. \(2023, Theorem 4\.1\)](https://arxiv.org/html/2610.33381#bib.bib44)proved thatTToracle calls suffice to reach, with probability at least1−δ1\-\\delta, the scale

σ​R​\(log⁡\(1/δ\)T\)\(p−1\)/p\\sigma R\\Bigl\(\\frac\{\\log\(1/\\delta\)\}\{T\}\\Bigr\)^\{\(p\-1\)/p\}\(2\)plus a deterministic term of orderL​R2​log⁡\(1/δ\)/TLR^\{2\}\\log\(1/\\delta\)/T\. Forδ≤1/8\\delta\\leq 1/8andT≥log⁡\(1/δ\)T\\geq\\log\(1/\\delta\), the lower bound of[Jiang et al\. \(2026, Proposition 1\)](https://arxiv.org/html/2610.33381#bib.bib26)shows that no algorithm usingTTstochastic gradients improves the minimum ofL​R2LR^\{2\}and the scale \([2](https://arxiv.org/html/2610.33381#S1.E2)\) by more than a constant factor\.

For the last iterate, the horizon\-free rateT−2\(p−1\)/\(3p\)T^\{\-2\(p\-1\)/\(3p\)\}of[Chezhegov et al\. \(2026, Theorem 1 and Corollary 1\)](https://arxiv.org/html/2610.33381#bib.bib8)holds up to logarithms with a schedule that takesδ\\deltaas input, and their experiments led them to conjecture that an improved schedule could attain the optimal rate\([Chezhegov et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib8), Section 5\)\. With a known horizon the conjecture holds: linearly decaying step sizes attain \([2](https://arxiv.org/html/2610.33381#S1.E2)\) at the last iterate, as shown by[Liu \(2026a, Theorem 2\)](https://arxiv.org/html/2610.33381#bib.bib35)and[Jiang et al\. \(2026, Theorem 1\)](https://arxiv.org/html/2610.33381#bib.bib26)\(Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1)below\)\.[Liu \(2026a, Section 5\)](https://arxiv.org/html/2610.33381#bib.bib35)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](https://arxiv.org/html/2610.33381#Thmtheorem4)and[6](https://arxiv.org/html/2610.33381#Thmtheorem6)\)\.

### 1\.1Main Results

Table[1](https://arxiv.org/html/2610.33381#S1.T1)summarizes our results and compares them with previous and concurrent work;αp\\alpha\_\{p\}is the statistical exponent of \([2](https://arxiv.org/html/2610.33381#S1.E2)\)\. We write error bounds asO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\), whereO~\\tilde\{O\}hides constants and factors polylogarithmic int/δt/\\delta\. An upper bound shows that the exponentrris attained; a lower bound with exponentrrshows that for everyr′\>rr^\{\\prime\}\>r, any claimed boundO~​\(t−r′\)\\tilde\{O\}\(t^\{\-r^\{\\prime\}\}\)fails on some instance with probability more thanδ\\delta, rather than a pointwise boundΩ⁡\(t−r\)\\Omega\(t^\{\-r\}\)\.

Our main result is the optimal time\-uniform rate \(Section[4](https://arxiv.org/html/2610.33381#S4)\)\. We give a deterministic schedule that uses neither the horizon nor the confidence level and prove that clipped SGD with this schedule attains errorO~​\(t−βp\)\\tilde\{O\}\(t^\{\-\\beta\_\{p\}\}\)at all times simultaneously \(Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)\)\. Because one trajectory serves every confidence level, the rate also holds almost surely\. This improves the rateO~\(t−2\(p−1\)/\(3p\)\)\\tilde\{O\}\(t^\{\-2\(p\-1\)/\(3p\)\}\)of[Chezhegov et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib8), whose schedule needsδ\\delta\. We then prove thatβp\\beta\_\{p\}cannot be improved: no gradient\-only rule \(Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3)\) attains a time\-uniform boundO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\)withr\>βpr\>\\beta\_\{p\}, even if its step sizes and clipping thresholds respond adaptively and randomly to the history and the current gradient \(Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)\)\. Atp=2p=2,[Anonymous \(2026\)](https://arxiv.org/html/2610.33381#bib.bib1)prove, concurrently, that deterministic unclipped step sizes cannot attain almost sure ratesO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\)for anyr\>1/3r\>1/3, and in Remark[16](https://arxiv.org/html/2610.33381#Thmtheorem16)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 exponent1/31/3, whereas our clipped schedule attains2/52/5\.

The lower bound raises the question whether a method outside this class can recoverαp\\alpha\_\{p\}without a known horizon \(Section[6](https://arxiv.org/html/2610.33381#S6)\)\. It can: if gradients are queried at the running average of the iterates, the error isO~​\(t−αp\)\\tilde\{O\}\(t^\{\-\\alpha\_\{p\}\}\)uniformly over time \(Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9), with a schedule that usesδ\\delta\)\. The accelerated method of[Nguyen et al\. \(2023\)](https://arxiv.org/html/2610.33381#bib.bib44)also attainsαp\\alpha\_\{p\}without a known horizon; their theorem is stated at each fixed time, and its proof gives the time\-uniform form \(Appendix[L](https://arxiv.org/html/2610.33381#A12)\)\. The barrier therefore depends on where gradients are queried rather than on how they are scaled\. Written as heavy\-ball momentum\([Polyak, 1964](https://arxiv.org/html/2610.33381#bib.bib49)\), this update has1−βt1\-\\beta\_\{t\}of order1/t1/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 boundO~​\(t−r\)\\tilde\{O\}\(t^\{\-r\}\)withr\>βpr\>\\beta\_\{p\}, even in one dimension\. Under polynomial forgetting1−βt≥ρ​\(1\+t\)−a1\-\\beta\_\{t\}\\geq\\rho\(1\+t\)^\{\-a\}, we prove the barriers\(1\+a\)​βp\(1\+a\)\\beta\_\{p\}in one dimension \(Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\) andmax⁡\{βp,a\}\\max\\\{\\beta\_\{p\},a\\\}under constants shared across dimensions \(Theorem[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\)\. Both also hold for fixed\-time guarantees with polylogarithmic confidence dependence when the rule’s constants depend onδ\\deltaonly through a polynomial factor in the step\-size bound\.

The price also depends on what the guarantee must cover: at a single fixed time, we show that it moves into the confidence factor \(Section[5](https://arxiv.org/html/2610.33381#S5)\)\. Our horizon\-free schedule attainsO~\(δ−\(p−1\)/pt−αp\)\\tilde\{O\}\(\\delta^\{\-\(p\-1\)/p\}t^\{\-\\alpha\_\{p\}\}\)at each fixed timett, orO~​\(δ−1​t−αp\)\\tilde\{O\}\(\\delta^\{\-1\}t^\{\-\\alpha\_\{p\}\}\)without a confidence input \(Theorem[5](https://arxiv.org/html/2610.33381#Thmtheorem5)\)\. For gradient\-only rules andr∈\(βp,αp\]r\\in\(\\beta\_\{p\},\\alpha\_\{p\}\], we prove that a fixed\-time boundO~​\(δ−c​t−r\)\\tilde\{O\}\(\\delta^\{\-c\}t^\{\-r\}\)that holds for everyδ\\deltawith constants independent ofδ\\deltarequiresc≥r−βpc\\geq r\-\\beta\_\{p\}, whereasc=\(3​p−1\)​\(r−βp\)/\(p−1\)c=\(3p\-1\)\(r\-\\beta\_\{p\}\)/\(p\-1\)suffices \(Theorems[5](https://arxiv.org/html/2610.33381#Thmtheorem5)and[6](https://arxiv.org/html/2610.33381#Thmtheorem6)\)\. With polylogarithmic dependence on1/δ1/\\delta, the exponent is again limited toβp\\beta\_\{p\}\.

With a known horizon,[Liu \(2026a\)](https://arxiv.org/html/2610.33381#bib.bib35)and[Jiang et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib26)show that a fixed threshold and linearly decaying step sizes attainO⁡\(T−αp\)O\(T^\{\-\\alpha\_\{p\}\}\)at the last iterate, which matches the lower boundΩ⁡\(T−αp\)\\Omega\(T^\{\-\\alpha\_\{p\}\}\)of[Jiang et al\. \(2026, Proposition 1\)](https://arxiv.org/html/2610.33381#bib.bib26); we restate their bound as Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1)\. Our lower bounds allow adaptive, randomized scalar responses to the history and the current gradient, while our upper bounds use deterministic schedules\.

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\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib8), and the known\-horizon rate is due to[Liu \(2026a\)](https://arxiv.org/html/2610.33381#bib.bib35)and[Jiang et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib26)\. 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 ratest−2/5t^\{\-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](https://arxiv.org/html/2610.33381#Thmtheorem7)and[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\)\. For1<p≤21<p\\leq 2, replace1/21/2byαp=\(p−1\)/p\\alpha\_\{p\}=\(p\-1\)/p,2/52/5byβp=2​\(p−1\)/\(3​p−1\)\\beta\_\{p\}=2\(p\-1\)/\(3p\-1\), andδ−1/2\\delta^\{\-1/2\}byδ−\(p−1\)/p\\delta^\{\-\(p\-1\)/p\}\.
### 1\.2What the Results Mean

We draw three lessons from these results\.

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\. When the model may be used at any time, the best error bound for clipped SGD under finite variance isO~\(t−2/5\)\\tilde\{O\}\(t^\{\-2/5\}\)rather thanO\(T−1/2\)O\(T^\{\-1/2\}\), whereas under sub\-Gaussian noise the same requirement costs only logarithmic factors\([Li et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib32)\)\. 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](https://arxiv.org/html/2610.33381#Thmtheorem17)\)\. 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\}\.

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 isO~​\(t−αp\)\\tilde\{O\}\(t^\{\-\\alpha\_\{p\}\}\)at all times \(Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9)\)\. This connects our analysis to schedule\-free SGD\([Defazio et al\., 2024b](https://arxiv.org/html/2610.33381#bib.bib13)\), 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](https://arxiv.org/html/2610.33381#S6.E20)\), with decreasing instead of constant step sizes\. Momentum helps in the same way only if its memory grows\. With1−βt1\-\\beta\_\{t\}of order1/t1/t, the heavy\-ball method is this averaging update, whereas geometrically decaying memory, as with a fixed coefficient, keeps the exponentβp\\beta\_\{p\}when the step sizes are polynomially bounded \(Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\)\.

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\)\\tilde\{O\}\(t^\{\-\\alpha\_\{p\}\}\)is attainable there only with a factor polynomial in1/δ1/\\delta\(Theorems[5](https://arxiv.org/html/2610.33381#Thmtheorem5)and[6](https://arxiv.org/html/2610.33381#Thmtheorem6)\)\. 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](https://arxiv.org/html/2610.33381#Thmtheorem11)\), and the counting argument above, which applies to every such rule\. Appendix[C](https://arxiv.org/html/2610.33381#A3)lists open problems, including adaptation to unknown problem parameters, lower bounds for more general updates, and the optimal confidence factor at a fixed time\.

### 1\.3Techniques and Organization

Our upper bounds for clipped SGD rest on one potential \(Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11)\), 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 \(2025\)](https://arxiv.org/html/2610.33381#bib.bib66)and[Liu and Zhou \(2024\)](https://arxiv.org/html/2610.33381#bib.bib37)\. 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](https://arxiv.org/html/2610.33381#Thmtheorem1)\([Jiang et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib26)\)\. 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](https://arxiv.org/html/2610.33381#Thmtheorem15)\), without the induction and union bound over the steps that[Nguyen et al\. \(2023\)](https://arxiv.org/html/2610.33381#bib.bib44)identify as the source oflog⁡T\\log Tfactors in earlier analyses\. For fixed\-time guarantees at exponents aboveβp\\beta\_\{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\. Sections[3](https://arxiv.org/html/2610.33381#S3)–[5](https://arxiv.org/html/2610.33381#S5)develop these arguments, Section[6](https://arxiv.org/html/2610.33381#S6)treats momentum and averaging\. Appendix[A](https://arxiv.org/html/2610.33381#A1)discusses related work, Appendix[B](https://arxiv.org/html/2610.33381#A2)illustrates the separation numerically, and the remaining appendices contain the proofs\. Theorems[4](https://arxiv.org/html/2610.33381#Thmtheorem4)and[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\(i\) are also formalized in Lean 4, together with a proof of Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1)\(Section[7](https://arxiv.org/html/2610.33381#S7)\)\.

## 2Problem Setting

∥⋅∥\\lVert\\cdot\\rVertand⟨⋅,⋅⟩\\langle\\cdot,\\cdot\\rangledenote the Euclidean norm and inner product; logarithms are natural\.

###### Assumption 1\(Objective\)\.

The functionf:ℝd→ℝf:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}is differentiable and convex, and

∥∇f​\(x\)−∇f​\(y\)∥≤L⁡∥x−y∥for all​x,y∈ℝd\.\\lVert\\nabla f\(x\)\-\\nabla f\(y\)\\rVert\\leq L\\lVert x\-y\\rVert\\quad\\text\{for all \}x,y\\in\\mathbb\{R\}^\{d\}\.There is a minimizerx⋆x^\{\\star\}, withf⋆=f⁡\(x⋆\)f^\{\\star\}=f\(x^\{\\star\}\), and a known bound∥x1−x⋆∥≤R\\lVert x\_\{1\}\-x^\{\\star\}\\rVert\\leq R, whereL,R\>0L,R\>0\.

###### Assumption 2\(Oracle\)\.

Letℱt−1\\mathcal\{F\}\_\{t\-1\}contain the initial state, any independent algorithmic randomness, and all observations up to timet−1t\-1, and write𝔼t−1\[⋅\]=𝔼\[⋅∣ℱt−1\]\\mathbb\{E\}\_\{t\-1\}\[\\cdot\]=\\mathbb\{E\}\[\\cdot\\mid\\mathcal\{F\}\_\{t\-1\}\]\. The queryxtx\_\{t\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable, and the oracle returns one fresh observationgtg\_\{t\}with, for someσ≥0\\sigma\\geq 0,

𝔼t−1​\[gt\]\\displaystyle\\mathbb\{E\}\_\{t\-1\}\[g\_\{t\}\]=∇f​\(xt\),\\displaystyle=\\nabla f\(x\_\{t\}\),𝔼t−1​\[∥gt−∇f​\(xt\)∥p\]\\displaystyle\\mathbb\{E\}\_\{t\-1\}\\bigl\[\\lVert g\_\{t\}\-\\nabla f\(x\_\{t\}\)\\rVert^\{p\}\\bigr\]≤σp,1<p≤2\.\\displaystyle\\leq\\sigma^\{p\},\\qquad 1<p\\leq 2\.

Assumption[2](https://arxiv.org/html/2610.33381#Thmassumption2)covers i\.i\.d\. samples from a fixed oracle with bounds uniform inxx, as well as conditionally unbiased martingale difference noise\. Its bound on the centralppth moment allows asymmetric noise and infinite variance forp<2p<2, without a uniform bound on𝔼t−1​∥gt∥p\\mathbb\{E\}\_\{t\-1\}\\lVert g\_\{t\}\\rVert^\{p\}\. Sample losses need not be smooth or convex\. The schedules useL,R,σ,pL,R,\\sigma,pand, when specified, a confidence levelδ\\delta, as in prior analyses\([Sadiev et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib53);[Nguyen et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib44);[Chezhegov et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib8)\)\. The time\-uniform schedule in Section[4\.1](https://arxiv.org/html/2610.33381#S4.SS1)does not useδ\\delta\.

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\\neq 0,\\\\ 0,&g=0,\\end\{cases\}for Euclidean clipping, that is, the projection of the gradient vector onto the ball of radiusλ\\lambdacentered at zero; the iterates themselves are never projected\. The output at timettis the last iteratext\+1x\_\{t\+1\}itself, without averaging, selection, or restarts\.

*Fixed\-time and time\-uniform guarantees\.*Letεt​\(δ\)\\varepsilon\_\{t\}\(\\delta\)be a deterministic envelope\. A*fixed\-time*guarantee asserts that for everyδ∈\(0,1\)\\delta\\in\(0,1\)and every deterministict≥1t\\geq 1,

ℙ\{f\(xt\+1\)−f⋆≤εt\(δ\)\}≥1−δ,\\mathbb\{P\}\\bigl\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\\leq\\varepsilon\_\{t\}\(\\delta\)\\bigr\\\}\\geq 1\-\\delta,so that the success event may depend ontt\. A*time\-uniform*guarantee, analogous to a confidence sequence\([Howard et al\., 2021](https://arxiv.org/html/2610.33381#bib.bib23)\), asserts the stronger statement

ℙ\{f\(xt\+1\)−f⋆≤εt\(δ\)for allt≥1\}≥1−δ\.\\mathbb\{P\}\\bigl\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\\leq\\varepsilon\_\{t\}\(\\delta\)\\ \\text\{for all\}\\ t\\geq 1\\bigr\\\}\\geq 1\-\\delta\.A method for a known horizonTTrequires the guarantee only att=Tt=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 impliesf⁡\(xτ\+1\)−f⋆≤ετ​\(δ\)f\(x\_\{\\tau\+1\}\)\-f^\{\\star\}\\leq\\varepsilon\_\{\\tau\}\(\\delta\)\. Conversely, a guarantee that holds at every bounded stopping time is time\-uniform: apply it atmin⁡\{τ,N\}\\min\\\{\\tau,N\\\}, whereτ\\tauis the first time the bound fails, and letN→∞N\\to\\infty\. 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 \(Section[5](https://arxiv.org/html/2610.33381#S5)\)\.

## 3Known Horizon: An Optimal Last\-Iterate Rate

We first recall the known\-horizon rate of[Jiang et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib26)and[Liu \(2026a\)](https://arxiv.org/html/2610.33381#bib.bib35): clipped SGD with a fixed threshold and linearly decaying step sizes attains the statistical scale \([2](https://arxiv.org/html/2610.33381#S1.E2)\) at its last iterate\. We then extend the potential behind it to unknown horizons\.

Algorithm 1Clipped SGD for a known horizon1:Input:

x1x\_\{1\},

LL,

RR,

σ\\sigma,

pp,

TT,

δ\\delta
2:

ℓ←log⁡\(8/δ\)\\ell\\leftarrow\\log\(8/\\delta\)
3:

λ←max⁡\{4​L​R,σ​\(T/ℓ\)1/p\}\\lambda\\leftarrow\\max\\\{4LR,\\sigma\(T/\\ell\)^\{1/p\}\\\}
4:

η←R/\(128​λ​ℓ\)\\eta\\leftarrow R/\(128\\lambda\\ell\)
5:for

t=1,…,Tt=1,\\ldots,Tdo

6:Draw one fresh stochastic gradient

gtg\_\{t\}at

xtx\_\{t\}
7:

ηt←η⁡\(T−t\+1\)/T\\eta\_\{t\}\\leftarrow\\eta\(T\-t\+1\)/T
8:

xt\+1←xt−ηt​clip⁡\(gt,λ\)x\_\{t\+1\}\\leftarrow x\_\{t\}\-\\eta\_\{t\}\\operatorname\{clip\}\(g\_\{t\},\\lambda\)
9:endfor

10:Return

xT\+1x\_\{T\+1\}

Algorithm[1](https://arxiv.org/html/2610.33381#alg1)makesTToracle calls usingO⁡\(d\)O\(d\)memory and no knowledge ofx⋆x^\{\\star\}; its clipping threshold is constant and its final step size isη/T\\eta/T\. Linearly decaying step sizes are the worst\-case optimal schedule in the analysis of[Defazio et al\. \(2024a\)](https://arxiv.org/html/2610.33381#bib.bib12)\.

###### Theorem 1\(Known horizon;[Jiang et al\. 2026](https://arxiv.org/html/2610.33381#bib.bib26), Theorem 1\)\.

Let Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)hold, and letT≥1T\\geq 1and0<δ<10<\\delta<1\. With probability at least1−δ1\-\\delta, the output of Algorithm[1](https://arxiv.org/html/2610.33381#alg1)satisfies, withℓ=log⁡\(8/δ\)\\ell=\\log\(8/\\delta\),

f⁡\(xT\+1\)−f⋆≤1024​L​R2​ℓT\+256​σ​R​\(ℓT\)\(p−1\)/p\.f\(x\_\{T\+1\}\)\-f^\{\\star\}\\leq\\frac\{1024LR^\{2\}\\ell\}\{T\}\+256\\sigma R\\left\(\\frac\{\\ell\}\{T\}\\right\)^\{\(p\-1\)/p\}\.\(3\)

The bound has nolog⁡T\\log Tfactor except through the confidence parameter and has constants independent ofppand the dimension\. Atp=2p=2the stochastic term is256​σ​R​ℓ/T256\\sigma R\\sqrt\{\\ell/T\}; atσ=0\\sigma=0the threshold is4​L​R4LR\.[Liu \(2026a, Theorem 2\)](https://arxiv.org/html/2610.33381#bib.bib35)proves a bound of the same order with a state\-dependent threshold \(Section[A\.2](https://arxiv.org/html/2610.33381#A1.SS2)\)\. The proof of[Jiang et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib26)combines the tail\-sum potential of Section[D\.2](https://arxiv.org/html/2610.33381#A4.SS2)with a stopping\-time localization of the iterates\. Our Lean formalization contains a machine\-checked proof of Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1)\(Section[7](https://arxiv.org/html/2610.33381#S7)\)\.

When the stochastic term dominates,λ≍T1/p\\lambda\\asymp T^\{1/p\}balances the total clipping biasT​σp​λ1−pT\\sigma^\{p\}\\lambda^\{1\-p\}againstλ​ℓ\\lambda\\ell, and each update moves by at mostR/\(128​ℓ\)R/\(128\\ell\)\. The actual final state attains \([2](https://arxiv.org/html/2610.33381#S1.E2)\), which is optimal up to constants in this regime\([Jiang et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib26), Proposition 1\)\. The deterministic term is that of unaccelerated gradient descent; acceleration attainsL​R2/T2LR^\{2\}/T^\{2\}without noise\([Nesterov, 1983](https://arxiv.org/html/2610.33381#bib.bib43);[Lan, 2012](https://arxiv.org/html/2610.33381#bib.bib30)\)\.

## 4Unknown 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 attainsO~​\(t−βp\)\\tilde\{O\}\(t^\{\-\\beta\_\{p\}\}\)and then prove that no gradient\-only rule attains a larger exponent\.

### 4\.1A Horizon\-Free Upper Bound

Define the exponents

β=βp=2​\(p−1\)3​p−1,a=p\+13​p−1=1−β,b=23​p−1\.\\begin\{gathered\}\\beta=\\beta\_\{p\}=\\frac\{2\(p\-1\)\}\{3p\-1\},\\\\ a=\\frac\{p\+1\}\{3p\-1\}=1\-\\beta,\\qquad b=\\frac\{2\}\{3p\-1\}\.\\end\{gathered\}\(4\)LetQ=max⁡\{L​R,σ\}Q=\\max\\\{LR,\\sigma\\\}andℓt=log⁡\(100​t2\)\\ell\_\{t\}=\\log\(100t^\{2\}\)\. We run the recursion \([1](https://arxiv.org/html/2610.33381#S1.E1)\) for allt≥1t\\geq 1with

ηt=RQ​cp​t−aℓt2,λt=4​Q​tb,\\eta\_\{t\}=\\frac\{R\}\{Q\}\\,\\frac\{c\_\{p\}\\,t^\{\-a\}\}\{\\ell\_\{t\}^\{2\}\},\\qquad\\lambda\_\{t\}=4Qt^\{b\},\(5\)wherecp\>0c\_\{p\}\>0depends only onpp\. Atp=2p=2this isηt∝t−3/5\\eta\_\{t\}\\propto t^\{\-3/5\}andλt∝t2/5\\lambda\_\{t\}\\propto t^\{2/5\}\. Neither a terminal horizon nor a confidence level enters the parameters or initialization\. For analysis, writeιt​\(δ\)=log⁡\(100​t2/δ\)\\iota\_\{t\}\(\\delta\)=\\log\(100t^\{2\}/\\delta\)\.

###### Theorem 2\(Time\-uniform upper bound\)\.

Let Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)hold, and run \([1](https://arxiv.org/html/2610.33381#S1.E1)\) with the schedule \([5](https://arxiv.org/html/2610.33381#S4.E5)\)\. There is a finite positive constantcpc\_\{p\}depending only onpp, and we may takeDp=4/cpD\_\{p\}=4/c\_\{p\}\(see Appendix[I\.1](https://arxiv.org/html/2610.33381#A9.SS1)\), such that for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, simultaneously for every integerT≥1T\\geq 1,

f⁡\(xT\+1\)−f⋆\\displaystyle f\(x\_\{T\+1\}\)\-f^\{\\star\}≤Dp​R​Q​T−β​ιT​\(δ\)4,\\displaystyle\\leq D\_\{p\}\\,RQ\\,T^\{\-\\beta\}\\iota\_\{T\}\(\\delta\)^\{4\},\(6\)∥xT\+1−x⋆∥2\\displaystyle\\lVert x\_\{T\+1\}\-x^\{\\star\}\\rVert^\{2\}≤R2​\[log⁡\(100/δ\)\]2\.\\displaystyle\\leq R^\{2\}\[\\log\(100/\\delta\)\]^\{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, the theorem gives events of probability at least1−1/n1\-1/non whichf⁡\(xT\+1\)−f⋆≤Dp​R​Q​T−βp​ℓT4​\(1\+log⁡n/ℓT\)4f\(x\_\{T\+1\}\)\-f^\{\\star\}\\leq D\_\{p\}RQ\\,T^\{\-\\beta\_\{p\}\}\\ell\_\{T\}^\{4\}\(1\+\\log n/\\ell\_\{T\}\)^\{4\}for allTT, so that, with probability one,

lim supT→∞f⁡\(xT\+1\)−f⋆T−βp​ℓT4≤Dp​R​Q\.\\limsup\_\{T\\to\\infty\}\\frac\{f\(x\_\{T\+1\}\)\-f^\{\\star\}\}\{T^\{\-\\beta\_\{p\}\}\\ell\_\{T\}^\{4\}\}\\leq D\_\{p\}RQ\.Our exponentβp\\beta\_\{p\}improves the exponent2​\(p−1\)/\(3​p\)2\(p\-1\)/\(3p\)of[Chezhegov et al\. \(2026\)](https://arxiv.org/html/2610.33381#bib.bib8), from1/31/3to2/52/5atp=2p=2\. Their schedule usesδ\\delta, and their proof controls nested events over all steps, so their guarantee is also time\-uniform; our improvement comes from the potential in Appendix[D\.2](https://arxiv.org/html/2610.33381#A4.SS2)\. Atp=2p=2this also separates clipped SGD from unclipped SGD with deterministic step sizes, which attains no exponent above1/31/3almost surely\([Anonymous, 2026](https://arxiv.org/html/2610.33381#bib.bib1)\); Appendix[G](https://arxiv.org/html/2610.33381#A7)compares the two settings\. In Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)we show thatβp\\beta\_\{p\}is optimal\.

### 4\.2A Matching Lower Bound for Horizon\-Free Rules

To show thatβp\\beta\_\{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−gt\-g\_\{t\}, and every such multiple forgt≠0g\_\{t\}\\neq 0can be implemented by clipping with a suitable step size\. We call these rules*gradient\-only rules*; Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3)restricts their update direction and oracle access\.

###### Definition 3\(Gradient\-only rules\)\.

Letp∈\(1,2\]p\\in\(1,2\],L=R=σ=1L=R=\\sigma=1, andx1=0x\_\{1\}=0\. A horizon\-free*gradient\-only rule*queries one fresh stochastic gradientgtg\_\{t\}at the current iteratextx\_\{t\}and updates

xt\+1=xt−ct​gt,x\_\{t\+1\}=x\_\{t\}\-c\_\{t\}\\,g\_\{t\},where the finite step factorct≥0c\_\{t\}\\geq 0is a measurable function oftt,δ\\delta,pp, the boundsL,R,σL,R,\\sigma, the gradientsg1,…,gtg\_\{1\},\\ldots,g\_\{t\}, and independent randomness\. Equivalently,ct​gt=ηt​clip⁡\(gt,λt\)c\_\{t\}g\_\{t\}=\\eta\_\{t\}\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\)for some finiteηt≥0\\eta\_\{t\}\\geq 0andλt\>0\\lambda\_\{t\}\>0chosen in the same way\.

Momentum, extra queries, restarts, output selection, and averaging are excluded\.

###### Theorem 4\(Time\-uniform lower bound\)\.

Fixp∈\(1,2\]p\\in\(1,2\]andδ∈\(0,1/2\)\\delta\\in\(0,1/2\)\. For every rule of Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3), everyC\>0C\>0,m≥0m\\geq 0, and

r\>βp=2​\(p−1\)3​p−1,r\>\\beta\_\{p\}=\\frac\{2\(p\-1\)\}\{3p\-1\},\(8\)there is an instance satisfying Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)withL=R=σ=1L=R=\\sigma=1andx1=0x\_\{1\}=0such that

ℙ⁡\{∃t≥1:f⁡\(xt\+1\)−f⋆\>C​t−r​\[log⁡\(e​t\)\]m\}\>δ\.\\mathbb\{P\}\\Bigl\\\{\\exists t\\geq 1:\\ f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\[\\log\(et\)\]^\{m\}\\Bigr\\\}\>\\delta\.\(9\)The rule,CC, andmmmay depend arbitrarily onδ\\deltaandpp\. The instance is one\-dimensional, with i\.i\.d\. additive noise and convex, globally11\-smooth sample losses that attain their minima\.

Theorems[2](https://arxiv.org/html/2610.33381#Thmtheorem2)and[4](https://arxiv.org/html/2610.33381#Thmtheorem4)together answer our question for time\-uniform guarantees:βp\\beta\_\{p\}is the optimal exponent for gradient\-only rules, strictly below the exponentαp\\alpha\_\{p\}for a known horizon\.

## 5Unknown Horizon: Fixed\-Time Guarantees

We now show that, for gradient\-only rules, the barrierβp\\beta\_\{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\}andαp\\alpha\_\{p\}at a smaller confidence cost\.

###### Theorem 5\(Fixed\-time confidence–rate tradeoff\)\.

Let Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)hold, and letQQ,cpc\_\{p\},DpD\_\{p\},ℓt\\ell\_\{t\}, andιT​\(δ\)\\iota\_\{T\}\(\\delta\)be as in Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)\. Fixr∈\(βp,αp\]r\\in\(\\beta\_\{p\},\\alpha\_\{p\}\]andu≥0u\\geq 0, and use the horizon\-free schedule

ηt=RQ​cp​δu​t−\(1−r\)ℓt2,λt=4​Q​max⁡\{1,δu/\(p−1\)​tr/\(p−1\)\}\.\\begin\{gathered\}\\eta\_\{t\}=\\frac\{R\}\{Q\}\\,\\frac\{c\_\{p\}\\,\\delta^\{u\}\\,t^\{\-\(1\-r\)\}\}\{\\ell\_\{t\}^\{2\}\},\\\\ \\lambda\_\{t\}=4Q\\max\\bigl\\\{1,\\delta^\{u/\(p\-1\)\}t^\{r/\(p\-1\)\}\\bigr\\\}\.\\end\{gathered\}\(10\)Put

cin​\(r\)=3​p−1p−1​\(r−βp\),\\displaystyle c\_\{\\rm in\}\(r\)=\\frac\{3p\-1\}\{p\-1\}\(r\-\\beta\_\{p\}\),cfree​\(r\)=\(3​p−1\)​r−2​\(p−1\)\(2​p−1\)​r−\(p−1\)\.\\displaystyle c\_\{\\rm free\}\(r\)=\\frac\{\(3p\-1\)r\-2\(p\-1\)\}\{\(2p\-1\)r\-\(p\-1\)\}\.Ifu=cin​\(r\)u=c\_\{\\rm in\}\(r\), letc=cin​\(r\)c=c\_\{\\rm in\}\(r\); ifu=0u=0, letc=cfree​\(r\)c=c\_\{\\rm free\}\(r\)\. Then for everyδ∈\(0,1\)\\delta\\in\(0,1\)and every deterministicT≥1T\\geq 1, with probability at least1−δ1\-\\delta,

f⁡\(xT\+1\)−f⋆≤Dp​R​Q​T−r​δ−c​ιT​\(δ\)4\.f\(x\_\{T\+1\}\)\-f^\{\\star\}\\leq D\_\{p\}\\,RQ\\,T^\{\-r\}\\delta^\{\-c\}\\,\\iota\_\{T\}\(\\delta\)^\{4\}\.\(11\)

The schedule \([10](https://arxiv.org/html/2610.33381#S5.E10)\) clips the current stochastic gradient, so it is a rule of Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3)\. Withu=0u=0it uses neither the horizon nor the confidence level, and one trajectory satisfies \([11](https://arxiv.org/html/2610.33381#S5.E11)\) for everyδ\\delta; the success event depends onδ\\deltaandTT\. Atr=αpr=\\alpha\_\{p\}the confidence factor isδ−\(p−1\)/p\\delta^\{\-\(p\-1\)/p\}with the confidence input andδ−1\\delta^\{\-1\}without it, that is,δ−1/2\\delta^\{\-1/2\}andδ−1\\delta^\{\-1\}atp=2p=2\. Both exponents tend to zero asr↓βpr\\downarrow\\beta\_\{p\}, where the schedule of Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)attainsβp\\beta\_\{p\}with polylogarithmic confidence dependence\.

Conversely, for horizon\-free gradient\-only rules, every fixed\-time exponent aboveβp\\beta\_\{p\}costs a polynomial confidence factor, because Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)also constrains fixed\-time guarantees through a union bound over finite prefixes\.

###### Theorem 6\(Fixed\-time lower bound with polynomial confidence cost\)\.

Let\(ruleδ\)δ∈\(0,1\)\(\\mathrm\{rule\}\_\{\\delta\}\)\_\{\\delta\\in\(0,1\)\}be any family of rules of Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3), and letC\>0C\>0,m≥0m\\geq 0,c∈\[0,1−βp\)c\\in\[0,1\-\\beta\_\{p\}\), andr\>βp\+cr\>\\beta\_\{p\}\+c\. There existδ∈\(0,1\)\\delta\\in\(0,1\), a deterministic integert≥1t\\geq 1, and an instance in the class of Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)such thatruleδ\\mathrm\{rule\}\_\{\\delta\}satisfies

ℙ\{f\(xt\+1\)−f⋆\>Ct−rδ−c\[log\(et/δ\)\]m\}\>δ\.\\mathbb\{P\}\\Bigl\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\\delta^\{\-c\}\[\\log\(et/\\delta\)\]^\{m\}\\Bigr\\\}\>\\delta\.\(12\)HereCC,cc, andmmdo not depend onδ\\delta,tt, or the instance, while each rule may depend arbitrarily onδ\\delta, the history, independent randomness, and the current stochastic gradient\.

Withc=0c=0, fixed\-time guarantees with uniformly polylogarithmic dependence on1/δ1/\\deltaattain no exponent aboveβp\\beta\_\{p\}\. Our proof applies Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)to the rule tuned forδN=1/\(4​N\)\\delta\_\{N\}=1/\(4N\)with the separate probability budget1/41/4: a union bound over the firstNNtimes turns the fixed\-time envelope into a time\-uniform one on this finite prefix, andδN−c\\delta\_\{N\}^\{\-c\}contributes the factor\(4​N\)c\(4N\)^\{c\}\(Appendix[H\.5](https://arxiv.org/html/2610.33381#A8.SS5)\)\.

Forr∈\(βp,αp\]r\\in\(\\beta\_\{p\},\\alpha\_\{p\}\], letc⋆​\(r\)c^\{\\star\}\(r\)be the infimum of the exponentsccfor which some family of gradient\-only rules attains a fixed\-time envelopeC​t−r​δ−c​\[log⁡\(e​t/δ\)\]mCt^\{\-r\}\\delta^\{\-c\}\[\\log\(et/\\delta\)\]^\{m\}on all instances\. SinceιT​\(δ\)≤5​log⁡\(e​T/δ\)\\iota\_\{T\}\(\\delta\)\\leq 5\\log\(eT/\\delta\), Theorems[5](https://arxiv.org/html/2610.33381#Thmtheorem5)and[6](https://arxiv.org/html/2610.33381#Thmtheorem6)give

r−βp≤c⋆​\(r\)≤3​p−1p−1​\(r−βp\)\.r\-\\beta\_\{p\}\\leq c^\{\\star\}\(r\)\\leq\\frac\{3p\-1\}\{p\-1\}\(r\-\\beta\_\{p\}\)\.\(13\)Atr=αpr=\\alpha\_\{p\}the upper end isαp\\alpha\_\{p\}, and the lower end is the gap between the fixed\-time and time\-uniform exponents,

αp−βp=\(p−1\)2p⁡\(3​p−1\)\>0,\\alpha\_\{p\}\-\\beta\_\{p\}=\\frac\{\(p\-1\)^\{2\}\}\{p\(3p\-1\)\}\>0,which is1/101/10atp=2p=2\. The two ends come from different arguments: the lower end from a union bound over the firstNNtimes, 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 theppth moment controls\. Which end is tight is open \(Appendix[C](https://arxiv.org/html/2610.33381#A3)\)\.

## 6Memory and the Momentum Boundary

Momentum and averaging lie outside the class of Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4), so we ask whether memory can beatβp\\beta\_\{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](https://arxiv.org/html/2610.33381#Thmassumption2)\.

### 6\.1Forgetting in One Dimension

Consider the stochastic heavy\-ball recursion\([Polyak, 1964](https://arxiv.org/html/2610.33381#bib.bib49)\)in velocity form:

vt\+1=βt​vt\+clip⁡\(gt,λt\),xt\+1=xt−ηtvt\+1,x1=v1=0,\\begin\{gathered\}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,\\end\{gathered\}\(14\)whereηt\\eta\_\{t\}is the step size andβt∈\[0,1\)\\beta\_\{t\}\\in\[0,1\)is the momentum coefficient\. A gradient observed at timejjentersxt\+1x\_\{t\+1\}with weight proportional to∏i=j\+1tβi\\prod\_\{i=j\+1\}^\{t\}\\beta\_\{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≥t0\),0≤ηt≤H\(1\+t\)h,0≤λt<∞,\\begin\{gathered\}0\\leq\\beta\_\{t\}<1,\\quad 1\-\\beta\_\{t\}\\geq\\rho\(1\+t\)^\{\-a\}\\ \(t\\geq t\_\{0\}\),\\\\ 0\\leq\\eta\_\{t\}\\leq H\(1\+t\)^\{h\},\\quad 0\\leq\\lambda\_\{t\}<\\infty,\\end\{gathered\}\(15\)with constantsa∈\[0,1\)a\\in\[0,1\),ρ∈\(0,1\]\\rho\\in\(0,1\],t0∈ℕt\_\{0\}\\in\\mathbb\{N\}, andH,h≥0H,h\\geq 0that 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, is the casea=0a=0withρ=1−β¯\\rho=1\-\\bar\{\\beta\}andt0=1t\_\{0\}=1\.

###### Theorem 7\(One\-dimensional momentum lower bound\)\.

Fixp∈\(1,2\]p\\in\(1,2\],a∈\[0,1\)a\\in\[0,1\)\.

1. \(i\)Fix a confidence0<δ<1/20<\\delta<1/2, and let a horizon\-free rule satisfy \([14](https://arxiv.org/html/2610.33381#S6.E14)\) and \([15](https://arxiv.org/html/2610.33381#S6.E15)\)\. For every finiteC\>0C\>0,m≥0m\\geq 0, andr\>\(1\+a\)​βpr\>\(1\+a\)\\beta\_\{p\}, there is a fixed one\-dimensional instance withL=R=σ=1L=R=\\sigma=1such that ℙ⁡\{∃t≥1:f⁡\(xt\+1\)−f⋆\>C​t−r​logm⁡\(e​t\)\}\>δ\.\\mathbb\{P\}\\\!\\left\\\{\\exists t\\geq 1:f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\\log^\{m\}\(et\)\\right\\\}\>\\delta\.\(16\)
2. \(ii\)Let\(ruleδ\)δ∈\(0,1\)\(\\mathrm\{rule\}\_\{\\delta\}\)\_\{\\delta\\in\(0,1\)\}satisfy \([14](https://arxiv.org/html/2610.33381#S6.E14)\) and \([15](https://arxiv.org/html/2610.33381#S6.E15)\) withρ\\rho,t0t\_\{0\}, andhhindependent ofδ\\delta, and withHHreplaced byH​δ−h0H\\delta^\{\-h\_\{0\}\}for constantsH,h0≥0H,h\_\{0\}\\geq 0independent ofδ\\delta\. For every finiteC\>0C\>0,m≥0m\\geq 0,c∈\[0,1−\(1\+a\)βp\)c\\in\[0,1\-\(1\+a\)\\beta\_\{p\}\), andr\>\(1\+a\)​βp\+cr\>\(1\+a\)\\beta\_\{p\}\+c, there areδ∈\(0,1\)\\delta\\in\(0,1\), a deterministic integert≥1t\\geq 1, and a one\-dimensional instance withL=R=σ=1L=R=\\sigma=1such thatruleδ\\mathrm\{rule\}\_\{\\delta\}satisfiesℙ\{f\(xt\+1\)−f⋆\>Ct−rδ−c\[log\(et/δ\)\]m\}\>δ\\mathbb\{P\}\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\\delta^\{\-c\}\[\\log\(et/\\delta\)\]^\{m\}\\\}\>\\delta\.

In both parts the instance satisfies Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)with i\.i\.d\. additive noise and convex, globally11\-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\}, as Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)does for gradient\-only rules; in particular, it covers any fixedβ∈\[0,1\)\\beta\\in\[0,1\)with arbitrary adaptive step sizes0≤ηt≤\(1−β\)20\\leq\\eta\_\{t\}\\leq\(1\-\\sqrt\{\\beta\}\)^\{2\}\. For0≤a<\(p−1\)/\(2​p\)0\\leq a<\(p\-1\)/\(2p\),\(1\+a\)​βp<αp\(1\+a\)\\beta\_\{p\}<\\alpha\_\{p\}, so polynomial forgetting at this rate does not attain the statistical exponent either\. Part \(ii\) is the analogue of Theorem[6](https://arxiv.org/html/2610.33381#Thmtheorem6): an exponent above\(1\+a\)​βp\(1\+a\)\\beta\_\{p\}at a fixed time costs a polynomial confidence factor, and with uniformly polylogarithmic dependence on1/δ1/\\deltait is unattainable\. Our proof \(Appendix[J](https://arxiv.org/html/2610.33381#A10)\) bounds the progress that rare gradient spikes can make through the decaying momentum kernel\.

### 6\.2Polynomial Forgetting with Constants Independent of Dimension

For polynomial forgetting, Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)excludes only exponents above\(1\+a\)​βp\(1\+a\)\\beta\_\{p\}: its budget lets each rare gradient spike move the iterate forO~​\(Na\)\\tilde\{O\}\(N^\{a\}\)steps on a horizonNN, the time the momentum kernel needs to decay\. If the dimension may grow and the constants are shared across dimensions, the barrier drops tomax⁡\{βp,a\}\\max\\\{\\beta\_\{p\},a\\\}\. Fixp∈\(1,2\]p\\in\(1,2\]anda∈\[0,1\)a\\in\[0,1\)\. The class𝒜unif​\(a\)\\mathcal\{A\}\_\{\\mathrm\{unif\}\}\(a\)consists of rules defined in every finite dimension that run \([14](https://arxiv.org/html/2610.33381#S6.E14)\) from zero state and velocity, observe only stochastic gradients, and choose their controls as measurable functions of the dimension, time, confidence, the boundsL=R=σ=1L=R=\\sigma=1, the gradients up to the current one, and an independent seed\. There must be deterministic constantsρ∈\(0,1\]\\rho\\in\(0,1\],t0∈ℕt\_\{0\}\\in\\mathbb\{N\}, andH,h≥0H,h\\geq 0, which may depend on the rule,pp,aa, andδ\\deltabut 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≥t0\)\.\\begin\{gathered\}0\\leq\\beta\_\{t\}<1,\\quad 0\\leq\\lambda\_\{t\}<\\infty,\\quad 0\\leq\\eta\_\{t\}\\leq H\(1\+t\)^\{h\},\\\\ 1\-\\beta\_\{t\}\\geq\\rho\(1\+t\)^\{\-a\}\\quad\(t\\geq t\_\{0\}\)\.\\end\{gathered\}\(17\)
###### Theorem 8\(Dimension\-uniform lower bound under polynomial forgetting\)\.

LetC\>0C\>0andk≥0k\\geq 0be finite, and letr\>max⁡\{βp,a\}r\>\\max\\\{\\beta\_\{p\},a\\\}\.

1. \(i\)Fix a confidenceδ∈\(0,1/2\)\\delta\\in\(0,1/2\)\. For any rule in𝒜unif​\(a\)\\mathcal\{A\}\_\{\\mathrm\{unif\}\}\(a\), there is a finite\-dimensional instance withL=R=σ=1L=R=\\sigma=1for which ℙ⁡\{∃t≥1:f⁡\(xt\+1\)−f⋆\>C​t−r​logk⁡\(e​t\)\}\>δ\.\\mathbb\{P\}\\\{\\exists t\\geq 1:\\ f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\\log^\{k\}\(et\)\\\}\>\\delta\.\(18\)Failure occurs on a deterministic finite prefix\.
2. \(ii\)Let\(ruleδ\)δ∈\(0,1\)\(\\mathrm\{rule\}\_\{\\delta\}\)\_\{\\delta\\in\(0,1\)\}satisfy the conditions of𝒜unif​\(a\)\\mathcal\{A\}\_\{\\mathrm\{unif\}\}\(a\)withρ\\rho,t0t\_\{0\}, andhhindependent ofδ\\delta, and withHHreplaced byH​δ−h0H\\delta^\{\-h\_\{0\}\}for constantsH,h0≥0H,h\_\{0\}\\geq 0independent ofδ\\delta\. There areδ∈\(0,1\)\\delta\\in\(0,1\), a deterministic integert≥1t\\geq 1, and a finite\-dimensional instance withL=R=σ=1L=R=\\sigma=1such thatruleδ\\mathrm\{rule\}\_\{\\delta\}satisfiesℙ\{f\(xt\+1\)−f⋆\>Ct−r\[log\(et/δ\)\]k\}\>δ\\mathbb\{P\}\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\>Ct^\{\-r\}\[\\log\(et/\\delta\)\]^\{k\}\\\}\>\\delta\.

In both parts the instance satisfies Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)with i\.i\.d\. additive noise and convex, globally11\-smooth sample losses that attain their minima, and it is fixed before the samples and the seed are drawn;CCandkkare shared across dimensions and, in part \(ii\), do not depend onδ\\deltaortt\.

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 factorO~​\(Na\)\\tilde\{O\}\(N^\{a\}\)of the one\-dimensional bound\. Polynomial forgetting makes the remaining pulse tail negligible \(Appendix[K](https://arxiv.org/html/2610.33381#A11)\)\. Part \(ii\) follows as Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\(ii\) does: with polylogarithmic dependence on1/δ1/\\delta, no fixed\-time exponent abovemax⁡\{βp,a\}\\max\\\{\\beta\_\{p\},a\\\}is attainable either\.

Consequently the optimal dimension\-uniform exponent in𝒜unif​\(a\)\\mathcal\{A\}\_\{\\mathrm\{unif\}\}\(a\)isβp\\beta\_\{p\}for0≤a≤βp0\\leq a\\leq\\beta\_\{p\}: Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)attains it withβt=0\\beta\_\{t\}=0and bounded steps, which meet the one\-sided condition for every suchaa\. For0<a<αp0<a<\\alpha\_\{p\}, this barriermax⁡\{βp,a\}\\max\\\{\\beta\_\{p\},a\\\}lies strictly belowmin⁡\{\(1\+a\)​βp,αp\}\\min\\\{\(1\+a\)\\beta\_\{p\},\\alpha\_\{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\.

### 6\.3Querying Gradients at the Running Average

###### Theorem 9\(Time\-uniform averaging momentum\)\.

Let Assumptions[1](https://arxiv.org/html/2610.33381#Thmassumption1)and[2](https://arxiv.org/html/2610.33381#Thmassumption2)hold\. Forδ∈\(0,1\)\\delta\\in\(0,1\), define deterministic horizon\-free parameters

a=1128,h=log4δ\+4​pp−1,ℓt=h\+logt,λt=max\{4LR,σt1/p\},γt=a​Rλt​ℓt2\.\\begin\{gathered\}a=\\frac\{1\}\{128\},\\quad h=\\log\\frac\{4\}\{\\delta\}\+\\frac\{4p\}\{p\-1\},\\quad\\ell\_\{t\}=h\+\\log t,\\\\ \\lambda\_\{t\}=\\max\\\{4LR,\\sigma t^\{1/p\}\\\},\\quad\\gamma\_\{t\}=\\frac\{aR\}\{\\lambda\_\{t\}\\ell\_\{t\}^\{2\}\}\.\\end\{gathered\}\(19\)Starting fromz1=x1z\_\{1\}=x\_\{1\}, make one oracle call atxtx\_\{t\}and update

dt=clip\(gt,λt\),zt\+1=zt−γtdt,xt\+1=tt\+1​xt\+1t\+1​zt\+1\.\\begin\{gathered\}d\_\{t\}=\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\),\\qquad z\_\{t\+1\}=z\_\{t\}\-\\gamma\_\{t\}d\_\{t\},\\\\ x\_\{t\+1\}=\\frac\{t\}\{t\+1\}x\_\{t\}\+\\frac\{1\}\{t\+1\}z\_\{t\+1\}\.\\end\{gathered\}\(20\)With probability at least1−δ1\-\\delta, simultaneously for every integerT≥1T\\geq 1, one has‖zT\+1−x⋆‖<2​R\\\|z\_\{T\+1\}\-x^\{\\star\}\\\|<\\sqrt\{2\}Rand

f⁡\(xT\+1\)−f⋆\\displaystyle f\(x\_\{T\+1\}\)\-f^\{\\star\}≤128​R​λT​ℓT2\+2​L​R2T\+1\\displaystyle\\leq\\frac\{128R\\lambda\_\{T\}\\ell\_\{T\}^\{2\}\+2LR^\{2\}\}\{T\+1\}\(21\)≤514​ℓT2​\(L​R2T\+σ​RT\(p−1\)/p\)\.\\displaystyle\\leq 514\\ell\_\{T\}^\{2\}\\left\(\\frac\{LR^\{2\}\}\{T\}\+\\frac\{\\sigma R\}\{T^\{\(p\-1\)/p\}\}\\right\)\.\(22\)The pointxT\+1x\_\{T\+1\}is the actual updated state after exactlyTTcalls\.

The update \([20](https://arxiv.org/html/2610.33381#S6.E20)\) adapts the anytime online\-to\-batch conversion of[Cutkosky \(2019, Algorithm 1 and Theorem 1\)](https://arxiv.org/html/2610.33381#bib.bib9)\(building on classical online\-to\-batch conversion;[Cesa\-Bianchi et al\. 2004](https://arxiv.org/html/2610.33381#bib.bib7)\), whose primal averaging interpretation is due to[Defazio \(2021, Theorem 1\)](https://arxiv.org/html/2610.33381#bib.bib11), to clipped stochastic gradients on an unbounded domain; the schedule \([19](https://arxiv.org/html/2610.33381#S6.E19)\) usesδ\\deltabut not the horizon\. Proposition[24](https://arxiv.org/html/2610.33381#Thmtheorem24)expresses the same trajectory in the heavy\-ball velocity form \([14](https://arxiv.org/html/2610.33381#S6.E14)\), with bounded step sizes andαp/\(2​t\)≤1−βt≤1/t\\alpha\_\{p\}/\(2t\)\\leq 1\-\\beta\_\{t\}\\leq 1/tfort≥2t\\geq 2\. Proposition[25](https://arxiv.org/html/2610.33381#Thmtheorem25)realizes it with a constant momentum coefficientβt=b∈\(0,1\)\\beta\_\{t\}=b\\in\(0,1\)and exponentially growing step sizes, so Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)needs some restriction on the growth of the step sizes\. The three\-sequence accelerated clipped method of[Nguyen et al\. \(2023, Algorithm 3 and Theorem D\.1\(2\)\)](https://arxiv.org/html/2610.33381#bib.bib44)also attainsαp\\alpha\_\{p\}at its auxiliary output without a known horizon, and this bound transfers to its query state \(Appendix[L](https://arxiv.org/html/2610.33381#A12)\), whereas the trajectory of \([20](https://arxiv.org/html/2610.33381#S6.E20)\) has the two\-sequence heavy\-ball form \([14](https://arxiv.org/html/2610.33381#S6.E14)\) used by the momentum lower bounds\.

## 7Discussion

*Implications\.*A known horizonTTallows the step sizes and clipping threshold to be tuned toTT, whereas a guarantee that covers adaptive checkpoint selection or early stopping must be time\-uniform \(Section[2](https://arxiv.org/html/2610.33381#S2)\)\. 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\}toβp\\beta\_\{p\}\. For nonconvex stationarity, the bound on the average squared gradient norm over the trajectory in[Nguyen et al\. \(2023, Theorem B\.2\)](https://arxiv.org/html/2610.33381#bib.bib44)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, 2006](https://arxiv.org/html/2610.33381#bib.bib6)\)\.

*Formalization\.*We provide machine\-checked proofs in Lean 4 with Mathlib of Theorems[4](https://arxiv.org/html/2610.33381#Thmtheorem4)and[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\(i\) and of the known\-horizon bound of Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1), 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](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

- Anonymous \[2026\]Anonymous\.The cube\-root barrier for almost\-sure last\-iterate convergence of SGD\.Submission to the International Conference on Learning Representations 2027,[https://openreview\.net/forum?id=PsmfXqmgZI](https://openreview.net/forum?id=PsmfXqmgZI), 2026\.
- Aolaritei and Jordan \[2026\]L\. Aolaritei and M\. I\. Jordan\.Stopping rules for stochastic gradient descent via anytime\-valid confidence sequences\.arXiv:2512\.13123v5, 2026\.
- Armacki et al\. \[2026\]A\. Armacki, H\. Cai, and A\. H\. Sayed\.Decentralized SGD under heavy\-tailed noise: Optimal convergence rates and the role of gradient clipping\.arXiv:2610\.10527v1, 2026\.URL[https://arxiv\.org/abs/2610\.10527v1](https://arxiv.org/abs/2610.10527v1)\.
- Beretta et al\. \[2026\]G\. Beretta, T\. Cesari, R\. Colomboni, and A\. Paudice\.New bounds for the last iterate of the stochastic subGradient method\.arXiv:2606\.24879v1, 2026\.
- Catoni \[2012\]O\. Catoni\.Challenging the empirical mean and empirical variance: A deviation study\.*Annales de l’Institut Henri Poincaré, Probabilités et Statistiques*, 48\(4\):1148–1185, 2012\.
- Cesa\-Bianchi and Lugosi \[2006\]N\. Cesa\-Bianchi and G\. Lugosi\.*Prediction, Learning, and Games*\.Cambridge University Press, Cambridge, 2006\.
- Cesa\-Bianchi et al\. \[2004\]N\. Cesa\-Bianchi, A\. Conconi, and C\. Gentile\.On the generalization ability of on\-line learning algorithms\.*IEEE Transactions on Information Theory*, 50\(9\):2050–2057, 2004\.
- Chezhegov et al\. \[2026\]S\. Chezhegov, D\. A\. Parletta, A\. Paudice, and E\. Gorbunov\.High\-probability bounds for the last iterate of clipped SGD\.In*International Conference on Learning Representations*, 2026\.
- Cutkosky \[2019\]A\. Cutkosky\.Anytime online\-to\-batch, optimism and acceleration\.In*Proceedings of the 36th International Conference on Machine Learning*, volume 97 of*Proceedings of Machine Learning Research*, pages 1446–1454, 2019\.
- Cutkosky and Mehta \[2021\]A\. Cutkosky and H\. Mehta\.High\-probability bounds for non\-convex stochastic optimization with heavy tails\.In*Advances in Neural Information Processing Systems*, volume 34, pages 4883–4895, 2021\.
- Defazio \[2021\]A\. Defazio\.Momentum via primal averaging: Theoretical insights and learning rate schedules for non\-convex optimization\.arXiv:2010\.00406v4, 2021\.URL[https://arxiv\.org/abs/2010\.00406v4](https://arxiv.org/abs/2010.00406v4)\.
- Defazio et al\. \[2024a\]A\. Defazio, A\. Cutkosky, H\. Mehta, and K\. Mishchenko\.Optimal linear decay learning rate schedules and further refinements\.arXiv:2310\.07831v2, 2024a\.
- Defazio et al\. \[2024b\]A\. Defazio, X\. Yang, H\. Mehta, K\. Mishchenko, A\. Khaled, and A\. Cutkosky\.The road less scheduled\.In*Advances in Neural Information Processing Systems*, volume 37, pages 9974–10007, 2024b\.
- Devroye et al\. \[2016\]L\. Devroye, M\. Lerasle, G\. Lugosi, and R\. I\. Oliveira\.Sub\-Gaussian mean estimators\.*The Annals of Statistics*, 44\(6\):2695–2725, 2016\.
- Drori and Shamir \[2020\]Y\. Drori and O\. Shamir\.The complexity of finding stationary points with stochastic gradient descent\.In*Proceedings of the 37th International Conference on Machine Learning*, volume 119 of*Proceedings of Machine Learning Research*, pages 2658–2667, 2020\.URL[https://proceedings\.mlr\.press/v119/drori20a\.html](https://proceedings.mlr.press/v119/drori20a.html)\.
- Duchi et al\. \[2011\]J\. Duchi, E\. Hazan, and Y\. Singer\.Adaptive subgradient methods for online learning and stochastic optimization\.*Journal of Machine Learning Research*, 12\(61\):2121–2159, 2011\.
- El Bakkali El Kadi et al\. \[2026\]T\. El Bakkali El Kadi, S\. Chezhegov, A\. Beznosikov, S\. Horváth, and E\. Gorbunov\.High\-probability convergence of clipped SGD under heavy\-tailed noise and\(L0,L1\)\(L\_\{0\},L\_\{1\}\)\-smoothness\.arXiv:2505\.20817v3, 2026\.
- Freedman \[1975\]D\. A\. Freedman\.On tail probabilities for martingales\.*The Annals of Probability*, 3\(1\):100–118, 1975\.
- Ganesh et al\. \[2023\]S\. Ganesh, R\. Deb, G\. Thoppe, and A\. Budhiraja\.Does momentum help in stochastic optimization? A sample complexity analysis\.In*Proceedings of the Thirty\-Ninth Conference on Uncertainty in Artificial Intelligence*, volume 216 of*Proceedings of Machine Learning Research*, pages 602–612, 2023\.URL[https://proceedings\.mlr\.press/v216/ganesh23a\.html](https://proceedings.mlr.press/v216/ganesh23a.html)\.
- Gorbunov et al\. \[2020\]E\. Gorbunov, M\. Danilova, and A\. Gasnikov\.Stochastic optimization with heavy\-tailed noise via accelerated gradient clipping\.In*Advances in Neural Information Processing Systems*, volume 33, pages 15042–15053, 2020\.
- Hägele et al\. \[2024\]A\. Hägele, E\. Bakouch, A\. Kosson, L\. Ben Allal, L\. Von Werra, and M\. Jaggi\.Scaling laws and compute\-optimal training beyond fixed training durations\.In*Advances in Neural Information Processing Systems*, volume 37, pages 76232–76264, 2024\.
- Harvey et al\. \[2019\]N\. J\. A\. Harvey, C\. Liaw, Y\. Plan, and S\. Randhawa\.Tight analyses for non\-smooth stochastic gradient descent\.In*Proceedings of the Thirty\-Second Conference on Learning Theory*, volume 99 of*Proceedings of Machine Learning Research*, pages 1579–1613, 2019\.
- Howard et al\. \[2021\]S\. R\. Howard, A\. Ramdas, J\. McAuliffe, and J\. Sekhon\.Time\-uniform, nonparametric, nonasymptotic confidence sequences\.*The Annals of Statistics*, 49\(2\):1055–1080, 2021\.
- Huber \[1964\]P\. J\. Huber\.Robust estimation of a location parameter\.*The Annals of Mathematical Statistics*, 35\(1\):73–101, 1964\.
- Jain et al\. \[2021\]P\. Jain, D\. M\. Nagaraj, and P\. Netrapalli\.Making the last iterate of SGD information theoretically optimal\.*SIAM Journal on Optimization*, 31\(2\):1108–1130, 2021\.
- Jiang et al\. \[2026\]W\. Jiang, H\. Bai, and Z\. Li\.Last\-iterate convergence of clipped SGD with linear decay\.arXiv:2610\.18555v1, 2026\.URL[https://arxiv\.org/abs/2610\.18555v1](https://arxiv.org/abs/2610.18555v1)\.
- Khaled and Richtárik \[2023\]A\. Khaled and P\. Richtárik\.Better theory for SGD in the nonconvex world\.*Transactions on Machine Learning Research*, 2023\.URL[https://openreview\.net/forum?id=AU4qHN2VkS](https://openreview.net/forum?id=AU4qHN2VkS)\.
- Kornowski and Shamir \[2024\]G\. Kornowski and O\. Shamir\.Open problem: Anytime convergence rate of gradient descent\.In*Proceedings of the Thirty Seventh Conference on Learning Theory*, volume 247 of*Proceedings of Machine Learning Research*, pages 5335–5339, 2024\.
- Kornowski and Shamir \[2026\]G\. Kornowski and O\. Shamir\.Gradient descent’s last iterate is often \(slightly\) suboptimal\.arXiv:2604\.13870v2, 2026\.
- Lan \[2012\]G\. Lan\.An optimal method for stochastic composite optimization\.*Mathematical Programming*, 133\(1–2\):365–397, 2012\.
- Le Cam \[1973\]L\. Le Cam\.Convergence of estimates under dimensionality restrictions\.*The Annals of Statistics*, 1\(1\):38–53, 1973\.
- Li et al\. \[2026\]R\. Li, K\. Chen, and T\. Wang\.The exact time\-uniform rate frontier for stochastic gradient descent on smooth convex objectives\.arXiv:2609\.08537v1, 2026\.
- Liu and Yuan \[2022\]J\. Liu and Y\. Yuan\.On almost sure convergence rates of stochastic gradient methods\.In*Proceedings of Thirty Fifth Conference on Learning Theory*, volume 178 of*Proceedings of Machine Learning Research*, pages 2963–2983, 2022\.URL[https://proceedings\.mlr\.press/v178/liu22d\.html](https://proceedings.mlr.press/v178/liu22d.html)\.
- Liu and Yuan \[2024\]J\. Liu and Y\. Yuan\.Almost sure convergence rates analysis and saddle avoidance of stochastic gradient methods\.*Journal of Machine Learning Research*, 25\(271\):1–40, 2024\.URL[https://jmlr\.org/papers/v25/23\-1436\.html](https://jmlr.org/papers/v25/23-1436.html)\.
- Liu \[2026a\]Z\. Liu\.On the last\-iterate convergence of clipped gradient methods\.In*Advances in Neural Information Processing Systems*, 2026a\.URL[https://arxiv\.org/abs/2610\.21026v1](https://arxiv.org/abs/2610.21026v1)\.To appear\.
- Liu \[2026b\]Z\. Liu\.Clipped gradient methods for nonsmooth convex optimization under heavy\-tailed noise: A refined analysis\.In*International Conference on Learning Representations*, 2026b\.Extended version: arXiv:2512\.23178v3\.
- Liu and Zhou \[2024\]Z\. Liu and Z\. Zhou\.Revisiting the last\-iterate convergence of stochastic gradient methods\.In*International Conference on Learning Representations*, 2024\.
- Liu and Zhou \[2026\]Z\. Liu and Z\. Zhou\.Revisiting the last\-iterate convergence of stochastic gradient methods\.Extended version, arXiv:2312\.08531v4, 2026\.
- Lugosi and Mendelson \[2019\]G\. Lugosi and S\. Mendelson\.Mean estimation and regression under heavy\-tailed distributions: A survey\.*Foundations of Computational Mathematics*, 19\(5\):1145–1190, 2019\.
- Nazin et al\. \[2019\]A\. V\. Nazin, A\. S\. Nemirovsky, A\. B\. Tsybakov, and A\. B\. Juditsky\.Algorithms of robust stochastic optimization based on mirror descent method\.*Automation and Remote Control*, 80\(9\):1607–1627, 2019\.
- Nemirovsky and Yudin \[1983\]A\. S\. Nemirovsky and D\. B\. Yudin\.*Problem Complexity and Method Efficiency in Optimization*\.Wiley, New York, 1983\.
- Nesterov \[2004\]Y\. Nesterov\.*Introductory Lectures on Convex Optimization: A Basic Course*, volume 87 of*Applied Optimization*\.Kluwer Academic Publishers, Boston, MA, 2004\.
- Nesterov \[1983\]Y\. E\. Nesterov\.A method of solving a convex programming problem with convergence rateO⁡\(1/k2\)O\(1/k^\{2\}\)\.*Doklady Akademii Nauk SSSR*, 269\(3\):543–547, 1983\.
- Nguyen et al\. \[2023\]T\. D\. Nguyen, T\. H\. Nguyen, A\. Ene, and H\. L\. Nguyen\.Improved convergence in high probability of clipped gradient methods with heavy tailed noise\.In*Advances in Neural Information Processing Systems*, volume 36, pages 24191–24222, 2023\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2023/hash/4c454d34f3a4c8d6b4ca85a918e5d7ba\-Abstract\-Conference\.html](https://proceedings.neurips.cc/paper_files/paper/2023/hash/4c454d34f3a4c8d6b4ca85a918e5d7ba-Abstract-Conference.html)\.
- Ou and Wang \[2026\]W\. Ou and X\. Wang\.Revisiting AdaGrad in stochastic convex optimization: Last iterates, high probability, and lower bounds\.arXiv:2609\.32729v1, 2026\.
- Parletta et al\. \[2024\]D\. A\. Parletta, A\. Paudice, M\. Pontil, and S\. Salzo\.High probability bounds for stochastic subgradient schemes with heavy tailed noise\.*SIAM Journal on Mathematics of Data Science*, 6\(4\):953–977, 2024\.
- Parletta et al\. \[2025\]D\. A\. Parletta, A\. Paudice, and S\. Salzo\.An improved analysis of the clipped stochastic subGradient method under heavy\-tailed noise\.arXiv:2410\.00573v2, 2025\.
- Pascanu et al\. \[2013\]R\. Pascanu, T\. Mikolov, and Y\. Bengio\.On the difficulty of training recurrent neural networks\.In*Proceedings of the 30th International Conference on Machine Learning*, volume 28 of*Proceedings of Machine Learning Research*, pages 1310–1318, 2013\.
- Polyak \[1964\]B\. T\. Polyak\.Some methods of speeding up the convergence of iteration methods\.*USSR Computational Mathematics and Mathematical Physics*, 4\(5\):1–17, 1964\.
- Polyak and Juditsky \[1992\]B\. T\. Polyak and A\. B\. Juditsky\.Acceleration of stochastic approximation by averaging\.*SIAM Journal on Control and Optimization*, 30\(4\):838–855, 1992\.
- Robbins and Monro \[1951\]H\. Robbins and S\. Monro\.A stochastic approximation method\.*The Annals of Mathematical Statistics*, 22\(3\):400–407, 1951\.
- Ruppert \[1988\]D\. Ruppert\.Efficient estimations from a slowly convergent Robbins–Monro process\.Technical Report 781, School of Operations Research and Industrial Engineering, Cornell University, 1988\.
- Sadiev et al\. \[2023\]A\. Sadiev, M\. Danilova, E\. Gorbunov, S\. Horváth, G\. Gidel, P\. Dvurechensky, A\. Gasnikov, and P\. Richtárik\.High\-probability bounds for stochastic optimization and variational inequalities: The case of unbounded variance\.In*Proceedings of the 40th International Conference on Machine Learning*, volume 202 of*Proceedings of Machine Learning Research*, pages 29563–29648, 2023\.
- Sebbouh et al\. \[2021\]O\. Sebbouh, R\. M\. Gower, and A\. Defazio\.Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball\.In*Proceedings of the 34th Conference on Learning Theory*, volume 134 of*Proceedings of Machine Learning Research*, pages 3935–3971, 2021\.URL[https://proceedings\.mlr\.press/v134/sebbouh21a\.html](https://proceedings.mlr.press/v134/sebbouh21a.html)\.
- Shamir and Zhang \[2013\]O\. Shamir and T\. Zhang\.Stochastic gradient descent for non\-smooth optimization: Convergence results and optimal averaging schemes\.In*Proceedings of the 30th International Conference on Machine Learning*, volume 28 of*Proceedings of Machine Learning Research*, pages 71–79, 2013\.
- Şimşekli et al\. \[2019\]U\. Şimşekli, L\. Sagun, and M\. Gürbüzbalaban\.A tail\-index analysis of stochastic gradient noise in deep neural networks\.In*Proceedings of the 36th International Conference on Machine Learning*, volume 97 of*Proceedings of Machine Learning Research*, pages 5827–5837, 2019\.
- Streeter and McMahan \[2010\]M\. Streeter and H\. B\. McMahan\.Less regret via online conditioning\.arXiv:1002\.4862v1, 2010\.URL[https://arxiv\.org/abs/1002\.4862v1](https://arxiv.org/abs/1002.4862v1)\.
- Suvorikova et al\. \[2026\]A\. Suvorikova, E\. Gladin, D\. Dvinskikh, A\. Agafonov, M\. Alkousa, Y\. Dorn, V\. Matyukhin, and A\. Gasnikov\.Clipped or unclipped? Finite\-sample trade\-offs for averaged SGD under heavy\-tailed noise\.arXiv:2609\.32962v1, 2026\.
- Taylor and Bach \[2019\]A\. Taylor and F\. Bach\.Stochastic first\-order methods: Non\-asymptotic and computer\-aided analyses via potential functions\.In*Proceedings of the Thirty\-Second Conference on Learning Theory*, volume 99 of*Proceedings of Machine Learning Research*, 2019\.
- Tian et al\. \[2026\]X\. Tian, J\. Fan, R\. H\. L\. Sim, and B\. K\. H\. Low\.INO\-SGD: Addressing utility imbalance under individualized differential privacy\.In*International Conference on Learning Representations*, 2026\.URL[https://arxiv\.org/abs/2605\.07930v1](https://arxiv.org/abs/2605.07930v1)\.
- Touvron et al\. \[2023\]H\. Touvron, T\. Lavril, G\. Izacard, X\. Martinet, M\.\-A\. Lachaux, T\. Lacroix, B\. Rozière, N\. Goyal, E\. Hambro, F\. Azhar, A\. Rodriguez, A\. Joulin, E\. Grave, and G\. Lample\.LLaMA: Open and efficient foundation language models\.arXiv:2302\.13971v1, 2023\.URL[https://arxiv\.org/abs/2302\.13971v1](https://arxiv.org/abs/2302.13971v1)\.
- Tsai et al\. \[2026\]C\.\-E\. Tsai, I\. Fatkhullin, L\. Zhang, and N\. He\.Lower bounds for anytime acceleration of gradient descent\.arXiv:2607\.02053v1, 2026\.
- Tsybakov \[2009\]A\. B\. Tsybakov\.*Introduction to Nonparametric Estimation*\.Springer Series in Statistics\. Springer, New York, 2009\.
- Vural et al\. \[2022\]N\. M\. Vural, L\. Yu, K\. Balasubramanian, S\. Volgushev, and M\. A\. Erdogdu\.Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance\.In*Proceedings of Thirty Fifth Conference on Learning Theory*, volume 178 of*Proceedings of Machine Learning Research*, pages 65–102, 2022\.
- Ward et al\. \[2020\]R\. Ward, X\. Wu, and L\. Bottou\.AdaGrad stepsizes: Sharp convergence over nonconvex landscapes\.*Journal of Machine Learning Research*, 21\(219\):1–30, 2020\.
- Zamani and Glineur \[2025\]M\. Zamani and F\. Glineur\.Exact convergence rate of the last iterate in subgradient methods\.*SIAM Journal on Optimization*, 35\(3\):2182–2201, 2025\.
- Zhang et al\. \[2026\]H\. Zhang, W\. Wu, C\. Zhang, Y\. Li, C\. Zheng, C\. Fang, H\. Li, and Z\. Lin\.Sharp high\-probability statistical rates for heavy\-tailed nonsmooth convex optimization\.arXiv:2610\.00260v1, 2026\.
- Zhang and Cutkosky \[2022\]J\. Zhang and A\. Cutkosky\.Parameter\-free regret in high probability with heavy tails\.In*Advances in Neural Information Processing Systems*, volume 35, pages 8000–8012, 2022\.
- Zhang et al\. \[2020\]J\. Zhang, S\. P\. Karimireddy, A\. Veit, S\. Kim, S\. J\. Reddi, S\. Kumar, and S\. Sra\.Why are adaptive methods good for attention models?In*Advances in Neural Information Processing Systems*, volume 33, pages 15383–15393, 2020\.

## 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\.

## Appendix ARelated Work

### A\.1Heavy\-Tailed Noise and Gradient Clipping

Under the classical model with boundedppth moments\[[Nemirovsky and Yudin, 1983](https://arxiv.org/html/2610.33381#bib.bib41),[Vural et al\., 2022](https://arxiv.org/html/2610.33381#bib.bib64)\], truncated mirror descent\[[Nazin et al\., 2019](https://arxiv.org/html/2610.33381#bib.bib40)\], smooth clipped methods\[[Gorbunov et al\., 2020](https://arxiv.org/html/2610.33381#bib.bib20),[Sadiev et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib53),[Nguyen et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib44)\], and nonsmooth methods\[[Parletta et al\., 2024](https://arxiv.org/html/2610.33381#bib.bib46),[Parletta et al\., 2025](https://arxiv.org/html/2610.33381#bib.bib47)\]achieve high\-probability statistical rates, typically for averaged or auxiliary outputs\. Clipping is not always beneficial for averages:[Suvorikova et al\. \[2026\]](https://arxiv.org/html/2610.33381#bib.bib58)compare clipped and unclipped Polyak–Ruppert averaged SGD\[[Ruppert, 1988](https://arxiv.org/html/2610.33381#bib.bib52),[Polyak and Juditsky, 1992](https://arxiv.org/html/2610.33381#bib.bib50)\]under finiteppth moments withp≥2p\\geq 2and show that, forp\>2p\>2, clipping need not improve the leading term\. Directional moments sharpen rates for structured instances\[[Zhang et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib67),[Liu, 2026b](https://arxiv.org/html/2610.33381#bib.bib36)\]\.

In decentralized smooth nonconvex optimization,[Armacki et al\. \[2026\]](https://arxiv.org/html/2610.33381#bib.bib3)analyze clipped DSGD under bounded centralppth 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\.

### A\.2Last\-Iterate Convergence

Schedules for a known horizon remove the logarithmic last\-iterate factor of standard nonsmooth SGD\[[Shamir and Zhang, 2013](https://arxiv.org/html/2610.33381#bib.bib55),[Harvey et al\., 2019](https://arxiv.org/html/2610.33381#bib.bib22),[Jain et al\., 2021](https://arxiv.org/html/2610.33381#bib.bib25),[Zamani and Glineur, 2025](https://arxiv.org/html/2610.33381#bib.bib66)\]; 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\[[Beretta et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib4)\]\. Smooth analyses based on moving comparators\[[Liu and Zhou, 2024](https://arxiv.org/html/2610.33381#bib.bib37)\]and online\-to\-batch regret reductions\[[Defazio et al\., 2024a](https://arxiv.org/html/2610.33381#bib.bib12)\]require stronger tail assumptions for high\-probability guarantees\. The bound in expectation under finiteppth moments of[Liu and Zhou \[2026, Section 5\]](https://arxiv.org/html/2610.33381#bib.bib38)uses ap/\(p−1\)p/\(p\-1\)\-uniformly convex mirror map, excluding Euclidean SGD atp<2p<2\.[Parletta et al\. \[2025\]](https://arxiv.org/html/2610.33381#bib.bib47)treat the last iterate of clipped SGD on Lipschitz objectives in expectation\. For AdaGrad\[[Duchi et al\., 2011](https://arxiv.org/html/2610.33381#bib.bib16)\]and AdaGrad\-Norm\[[Streeter and McMahan, 2010](https://arxiv.org/html/2610.33381#bib.bib57),[Ward et al\., 2020](https://arxiv.org/html/2610.33381#bib.bib65)\]with fixed parameters,[Ou and Wang \[2026, Theorem 3\.1\]](https://arxiv.org/html/2610.33381#bib.bib45)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\. \[2026, Theorem 1 and Corollary 1\]](https://arxiv.org/html/2610.33381#bib.bib8)obtain the horizon\-free exponent2​\(p−1\)/\(3​p\)2\(p\-1\)/\(3p\); for clipped SGD with an unknown horizon, we establishβp\\beta\_\{p\}for time\-uniform guarantees andαp\\alpha\_\{p\}for fixed\-time guarantees with polynomial dependence on1/δ1/\\delta\.

With a known horizon, recent work attainsαp\\alpha\_\{p\}at the last iterate\.[Liu \[2026a\]](https://arxiv.org/html/2610.33381#bib.bib35)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\. \[2026\]](https://arxiv.org/html/2610.33381#bib.bib26)is the bound we restate as Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1)\. They also treat composite objectives with proximal updates and oracles under adversarial sample corruption, and establish two\-point statistical lower bounds\[[Le Cam, 1973](https://arxiv.org/html/2610.33381#bib.bib31),[Tsybakov, 2009](https://arxiv.org/html/2610.33381#bib.bib63)\]\. Both papers assume a known horizon;[Liu \[2026a, Remark 4\]](https://arxiv.org/html/2610.33381#bib.bib35)does so to avoid a potential logarithmic dependence onTT\. For gradient\-only rules \(Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3)\) with polylogarithmic dependence on1/δ1/\\delta, Theorems[2](https://arxiv.org/html/2610.33381#Thmtheorem2),[4](https://arxiv.org/html/2610.33381#Thmtheorem4), and[6](https://arxiv.org/html/2610.33381#Thmtheorem6)show that when the horizon is unknown the optimal exponent drops fromαp\\alpha\_\{p\}toβp\\beta\_\{p\}\.[Liu \[2026a, Section 5\]](https://arxiv.org/html/2610.33381#bib.bib35)lists matching lower bounds for smooth objectives as open;[Jiang et al\. \[2026, Proposition 1\]](https://arxiv.org/html/2610.33381#bib.bib26)matches the stochastic term when the stochastic error dominates\.

### A\.3Unknown Horizons and Time\-Uniform Guarantees

For the subgradient method, no single sequence of step sizes attains the optimal last\-iterate rate at every iteration\[[Zamani and Glineur, 2025](https://arxiv.org/html/2610.33381#bib.bib66)\]\. Deterministic anytime lower bounds use flat objectives and overshoots\[[Kornowski and Shamir, 2024](https://arxiv.org/html/2610.33381#bib.bib28),[Tsai et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib62),[Kornowski and Shamir, 2026](https://arxiv.org/html/2610.33381#bib.bib29)\]\. 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\]](https://arxiv.org/html/2610.33381#bib.bib32)characterize a logarithmic overhead around time exponent1/21/2\. Finite second moments already permit the polynomial separation studied here\.

*Almost sure convergence\.*Under the ABC condition on conditional second moments\[[Khaled and Richtárik, 2023](https://arxiv.org/html/2610.33381#bib.bib27)\],[Liu and Yuan \[2022, Theorem 5\]](https://arxiv.org/html/2610.33381#bib.bib33)and[Liu and Yuan \[2024, Theorem 13\]](https://arxiv.org/html/2610.33381#bib.bib34)obtain almost sure last\-iterate ratesO\(t−1/3\+ε\)O\(t^\{\-1/3\+\\varepsilon\}\)on smooth convex objectives for unclipped SGD, heavy\-ball\[[Polyak, 1964](https://arxiv.org/html/2610.33381#bib.bib49)\], and Nesterov accelerated methods with deterministic step sizes of ordert−2/3−εt^\{\-2/3\-\\varepsilon\},0<ε<1/30<\\varepsilon<1/3\.[Sebbouh et al\. \[2021, Theorems 8 and 13\]](https://arxiv.org/html/2610.33381#bib.bib54)obtaino⁡\(1/∑j<kηj\)o\(1/\\sum\_\{j<k\}\\eta\_\{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 \[2026, Theorem 2\.2\]](https://arxiv.org/html/2610.33381#bib.bib1)shows that, for every positive deterministic schedule of unclipped step sizes and everyr\>1/3r\>1/3, a one\-dimensional smooth convex instance with a fixed i\.i\.d\. finite\-variance oracle satisfieslim supt→∞\(t\+1\)r​\(f⁡\(xt\)−f⋆\)=∞\\limsup\_\{t\\to\\infty\}\(t\+1\)^\{r\}\(f\(x\_\{t\}\)\-f^\{\\star\}\)=\\inftyalmost surely\. Their Theorem 2\.1 and Corollary 2\.3 identify1/31/3as the supremal almost sure exponent under the ABC condition, and Proposition 2\.4 establishes a matching rate up to logarithmic factors\. Remark[16](https://arxiv.org/html/2610.33381#Thmtheorem16)adapts their lower bound to the time\-uniform setting at a fixed confidence levelδ\\deltaand compares it with clipping\.

Online\-to\-batch conversions\[[Cesa\-Bianchi et al\., 2004](https://arxiv.org/html/2610.33381#bib.bib7),[Cutkosky, 2019](https://arxiv.org/html/2610.33381#bib.bib9)\], primal averaging\[[Defazio, 2021](https://arxiv.org/html/2610.33381#bib.bib11),[Defazio et al\., 2024b](https://arxiv.org/html/2610.33381#bib.bib13)\], and accelerated clipped methods\[[Nguyen et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib44)\]query coupled or averaged states\. Section[6](https://arxiv.org/html/2610.33381#S6)compares such memory with geometric forgetting\. The upper proofs use the maximal concentration inequalities in Appendix[F](https://arxiv.org/html/2610.33381#A6); for broader time\-uniform martingale methods, see[Howard et al\. \[2021\]](https://arxiv.org/html/2610.33381#bib.bib23)\.

Momentum lower bounds on quadratics also appear in[Ganesh et al\. \[2023\]](https://arxiv.org/html/2610.33381#bib.bib19), for constant parameters and expected error\.[Drori and Shamir \[2020, Theorem 2\]](https://arxiv.org/html/2610.33381#bib.bib15)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\.

## Appendix BA Numerical Illustration

We illustrate the separation betweenαp\\alpha\_\{p\}andβp\\beta\_\{p\}numerically\. Figure[1](https://arxiv.org/html/2610.33381#A2.F1)compares the methods on the hard instances of Appendix[H\.2](https://arxiv.org/html/2610.33381#A8.SS2)atp=2p=2\. For each horizonNNwe use the targetsy∈\{1/4,1/2,3/4,1\}y\\in\\\{1/4,1/2,3/4,1\\\}, the slopesμ=min⁡\{0\.2,1\.3​N−αp\}\\mu=\\min\\\{0\.2,1\.3N^\{\-\\alpha\_\{p\}\}\\\}andμ=min⁡\{0\.2,1\.3​N−βp\}\\mu=\\min\\\{0\.2,1\.3N^\{\-\\beta\_\{p\}\}\\\}, and the one\-sided spike noise of \([29](https://arxiv.org/html/2610.33381#A8.E29)\); every method sees the same instances and the same spikes\. Every method starts atx1=0x\_\{1\}=0, withz1=0z\_\{1\}=0for averaging and zero initial velocity for heavy\-ball momentum, andNNranges over500⋅2k500\\cdot 2^\{k\}fork=0,…,6k=0,\\dots,6\. Clipped SGD uses the time\-uniform scheduleηt=t−\(p\+1\)/\(3p−1\)\\eta\_\{t\}=t^\{\-\(p\+1\)/\(3p\-1\)\},λt=2​t2/\(3​p−1\)\\lambda\_\{t\}=2t^\{2/\(3p\-1\)\}; heavy\-ball momentum usesβt=0\.8\\beta\_\{t\}=0\.8, the same thresholds, and step sizes0\.2t−\(p\+1\)/\(3p−1\)0\.2\\,t^\{\-\(p\+1\)/\(3p\-1\)\}; averaging uses \([20](https://arxiv.org/html/2610.33381#S6.E20)\) withγt=0\.5t−1/p\\gamma\_\{t\}=0\.5\\,t^\{\-1/p\}andλt=2​t1/p\\lambda\_\{t\}=2t^\{1/p\}; and Algorithm[1](https://arxiv.org/html/2610.33381#alg1)usesλ=2​N1/p\\lambda=2N^\{1/p\}andηt=1\.5​\(N−t\+1\)/\(N​λ\)\\eta\_\{t\}=1\.5\(N\-t\+1\)/\(N\\lambda\)\. These constants are of order one and do not change withNN; 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, over10001000runs, the0\.90\.9\-quantile of the largest gapf⁡\(xt\+1\)−f⋆f\(x\_\{t\+1\}\)\-f^\{\\star\}overN/2≤t≤NN/2\\leq t\\leq N, or of the terminal gap for Algorithm[1](https://arxiv.org/html/2610.33381#alg1), and report its maximum over the eight instances\.

10310^\{3\}10410^\{4\}10−210^\{\-2\}10−110^\{\-1\}horizonNNworst0\.90\.9\-quantile of the gapknown horizon, slope−0\.50\-0\.50averaging, slope−0\.55\-0\.55clipped SGD, slope−0\.35\-0\.35heavy ball, slope−0\.30\-0\.30Figure 1:Algorithm[1](https://arxiv.org/html/2610.33381#alg1)for a known horizon, averaging \(Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9)\), time\-uniform clipped SGD \(Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)\), and heavy\-ball momentum withβt=0\.8\\beta\_\{t\}=0\.8, with the exponents of the theorems and illustrative constants \(Section[B](https://arxiv.org/html/2610.33381#A2)\), on the hard instances of Appendix[H\.2](https://arxiv.org/html/2610.33381#A8.SS2)atp=2p=2: worst case over eight instances of the0\.90\.9\-quantile, over10001000runs, of the largest gap overN/2≤t≤NN/2\\leq t\\leq N\(terminal gap for Algorithm[1](https://arxiv.org/html/2610.33381#alg1)\)\. Slopes are least\-squares fits inlog⁡N\\log N; their95%95\\%bootstrap intervals over the runs \(200 resamples\) have half\-width below0\.020\.02\.Algorithm[1](https://arxiv.org/html/2610.33381#alg1)and averaging decay with fitted slopes−0\.50\-0\.50and−0\.55\-0\.55, close to−α2=−1/2\-\\alpha\_\{2\}=\-1/2, whereas clipped SGD and heavy\-ball momentum decay with slopes−0\.35\-0\.35and−0\.30\-0\.30, and atN=3\.2×104N=3\.2\\times 10^\{4\}their worst gaps are2\.52\.5to33times those of the first two\. Slopes fitted over this range ofNNalso reflect constants and logarithmic factors\. Atp=1\.5p=1\.5, where the exponents1/31/3and2/72/7differ by less than0\.050\.05, the same experiment gives slopes−0\.31\-0\.31for Algorithm[1](https://arxiv.org/html/2610.33381#alg1)and for averaging and−0\.24\-0\.24and−0\.22\-0\.22for the other two methods; the worst gap of Algorithm[1](https://arxiv.org/html/2610.33381#alg1)falls below those of the other two methods atN=3\.2×104N=3\.2\\times 10^\{4\}, while that of averaging remains above them\.

## Appendix COpen Problems

Our schedules useL,R,σ,pL,R,\\sigma,pand, except for the time\-uniform schedule and the schedule of Theorem[5](https://arxiv.org/html/2610.33381#Thmtheorem5)withu=0u=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 exponentc⋆​\(r\)c^\{\\star\}\(r\)of fixed\-time guarantees, bracketed in \([13](https://arxiv.org/html/2610.33381#S5.E13)\), 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\}and the dimension\-uniform barriermax⁡\{βp,a\}\\max\\\{\\beta\_\{p\},a\\\}closes, which rates are attainable fora\>βpa\>\\beta\_\{p\}, also under a two\-sided condition1−βt≍t−a1\-\\beta\_\{t\}\\asymp t^\{\-a\}, and how the confidence factor of a fixed\-time exponent abovemax⁡\{βp,a\}\\max\\\{\\beta\_\{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\[[Liu, 2026a](https://arxiv.org/html/2610.33381#bib.bib35),[Jiang et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib26)\]; horizon\-free counterparts of these settings, and of non\-Euclidean or\(L0,L1\)\(L\_\{0\},L\_\{1\}\)\-smooth objectives\[[El Bakkali El Kadi et al\., 2026](https://arxiv.org/html/2610.33381#bib.bib17)\], are further directions\.

## Appendix DDeterministic Last\-Iterate Calculations

This appendix proves the one\-step inequality and the recursive potential \(Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11)\)\.

### D\.1One Inexact Gradient Step

###### Lemma 10\(Inexact smooth convex step\)\.

Letffbe convex andLL\-smooth\. Fixx,z,e∈ℝdx,z,e\\in\\mathbb\{R\}^\{d\},0<γ≤1/\(2​L\)0<\\gamma\\leq 1/\(2L\), andy=x−γ⁡\(∇f​\(x\)\+e\)y=x\-\\gamma\(\\nabla f\(x\)\+e\)\. Then

γ⁡\[f⁡\(y\)−f⁡\(z\)\]\+12​∥y−z∥2≤12​∥x−z∥2\+γ⁡⟨e,z−x⟩\+γ2​∥e∥2\.\\gamma\[f\(y\)\-f\(z\)\]\+\\frac\{1\}\{2\}\\lVert y\-z\\rVert^\{2\}\\leq\\frac\{1\}\{2\}\\lVert x\-z\\rVert^\{2\}\+\\gamma\\langle e,z\-x\\rangle\+\\gamma^\{2\}\\lVert e\\rVert^\{2\}\.\(23\)

ProofSmoothness, convexity and the three\-point norm identity give

γ⁡\[f⁡\(y\)−f⁡\(z\)\]\+12​‖y−z‖2≤12​‖x−z‖2\+γ⁡⟨e,z−x⟩−1−γ​L2​‖x−y‖2\+γ⁡⟨e,x−y⟩\.\\gamma\[f\(y\)\-f\(z\)\]\+\\tfrac\{1\}\{2\}\\\|y\-z\\\|^\{2\}\\leq\\tfrac\{1\}\{2\}\\\|x\-z\\\|^\{2\}\+\\gamma\\langle e,z\-x\\rangle\-\\tfrac\{1\-\\gamma L\}\{2\}\\\|x\-y\\\|^\{2\}\+\\gamma\\langle e,x\-y\\rangle\.Useγ⁡⟨e,x−y⟩≤γ2​‖e‖2\+‖x−y‖2/4\\gamma\\langle e,x\-y\\rangle\\leq\\gamma^\{2\}\\\|e\\\|^\{2\}\+\\\|x\-y\\\|^\{2\}/4andγ​L≤1/2\\gamma L\\leq 1/2\.■\\blacksquare

### D\.2A Recursively Averaged Potential

Potential functions are a standard tool for analyzing first\-order methods\[[Taylor and Bach, 2019](https://arxiv.org/html/2610.33381#bib.bib59)\]\. Following the comparator weighted by inverse tail sums in[Zamani and Glineur \[2025\]](https://arxiv.org/html/2610.33381#bib.bib66)and[Liu and Zhou \[2024\]](https://arxiv.org/html/2610.33381#bib.bib37), we express the potential recursively\. With boundary massζ=0\\zeta=0below, it is the tail\-sum potential that[Jiang et al\. \[2026, Lemma 4\]](https://arxiv.org/html/2610.33381#bib.bib26)use to prove Theorem[1](https://arxiv.org/html/2610.33381#Thmtheorem1); the boundary massζ\>0\\zeta\>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\}\\leq 1/\(2L\)and arbitrary realized errors, consider

xt\+1=xt−ηt​\(∇f​\(xt\)\+et\)\.x\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}\(\\nabla f\(x\_\{t\}\)\+e\_\{t\}\)\.For a deterministic analysis horizonTTand boundary massζ≥0\\zeta\\geq 0, set

Gt=f⁡\(xt\)−f⋆,St=∑r=tTηr,Ut=ζ\+St,W=U1,θt=ηt/Ut,G\_\{t\}=f\(x\_\{t\}\)\-f^\{\\star\},\\quad S\_\{t\}=\\sum\_\{r=t\}^\{T\}\\eta\_\{r\},\\quad U\_\{t\}=\\zeta\+S\_\{t\},\\quad W=U\_\{1\},\\quad\\theta\_\{t\}=\\eta\_\{t\}/U\_\{t\},withS0=S1S\_\{0\}=S\_\{1\},ST\+1=0S\_\{T\+1\}=0andU0=U1U\_\{0\}=U\_\{1\}\. All denominators below involve onlyU0,…,UT\>0U\_\{0\},\\ldots,U\_\{T\}\>0, soζ=0\\zeta=0is allowed\. Starting fromz0=z1=x⋆z\_\{0\}=z\_\{1\}=x^\{\\star\}andA0=0A\_\{0\}=0, define only for the analysis

zt\+1=\(1−θt\)​zt\+θt​xt\+1,At=\(1−θt\)​At−1\+θt​Gt\+1\.z\_\{t\+1\}=\(1\-\\theta\_\{t\}\)z\_\{t\}\+\\theta\_\{t\}x\_\{t\+1\},\\qquad A\_\{t\}=\(1\-\\theta\_\{t\}\)A\_\{t\-1\}\+\\theta\_\{t\}G\_\{t\+1\}\.Let

dt=zt−1−xt,H0=12∥d1∥2,Ht=W2​Ut∥zt−xt\+1∥2,qt=2​W​ηt2Ut,ht=W​ηtUt−1dt\.\\begin\{split\}d\_\{t\}&=z\_\{t\-1\}\-x\_\{t\},\\qquad H\_\{0\}=\\tfrac\{1\}\{2\}\\\|d\_\{1\}\\\|^\{2\},\\qquad H\_\{t\}=\\frac\{W\}\{2U\_\{t\}\}\\\|z\_\{t\}\-x\_\{t\+1\}\\\|^\{2\},\\\\ q\_\{t\}&=\\frac\{2W\\eta\_\{t\}^\{2\}\}\{U\_\{t\}\},\\qquad h\_\{t\}=\\frac\{W\\eta\_\{t\}\}\{U\_\{t\-1\}\}d\_\{t\}\.\\end\{split\}In particularHTH\_\{T\}useszT−xT\+1z\_\{T\}\-x\_\{T\+1\}, notzT\+1−xT\+1z\_\{T\+1\}\-x\_\{T\+1\}\.

###### Lemma 11\(Unified recursive potential\)\.

For everym≤Tm\\leq T,Am,Hm≥0A\_\{m\},H\_\{m\}\\geq 0and

W​Am\+Hm≤R22\+∑t≤mqt​‖et‖2\+∑t≤m⟨et,ht⟩\.WA\_\{m\}\+H\_\{m\}\\leq\\frac\{R^\{2\}\}\{2\}\+\\sum\_\{t\\leq m\}q\_\{t\}\\\|e\_\{t\}\\\|^\{2\}\+\\sum\_\{t\\leq m\}\\langle e\_\{t\},h\_\{t\}\\rangle\.\(24\)The full terminal potential also gives

GT\+1≤\(1\+L​ζ2ζ\+ηT\)​W​AT\+HTW≤\(1\+L​ζ\)​W​AT\+HTW\.\\begin\{split\}G\_\{T\+1\}&\\leq\\left\(1\+\\frac\{L\\zeta^\{2\}\}\{\\zeta\+\\eta\_\{T\}\}\\right\)\\frac\{WA\_\{T\}\+H\_\{T\}\}\{W\}\\\\ &\\leq\(1\+L\\zeta\)\\frac\{WA\_\{T\}\+H\_\{T\}\}\{W\}\.\\end\{split\}\(25\)In particular,ζ=0\\zeta=0givesAT=GT\+1A\_\{T\}=G\_\{T\+1\}, whileζ=1\\zeta=1keeps the inverse tail weights bounded\.

ProofConvexity and the synchronized recursions givef⁡\(zt\)−f⋆≤At−1f\(z\_\{t\}\)\-f^\{\\star\}\\leq A\_\{t\-1\}by induction\. ThusAt−At−1≤θt​\[f⁡\(xt\+1\)−f⁡\(zt\)\]A\_\{t\}\-A\_\{t\-1\}\\leq\\theta\_\{t\}\[f\(x\_\{t\+1\}\)\-f\(z\_\{t\}\)\]\. Alsozt−xt=\(Ut/Ut−1\)​dtz\_\{t\}\-x\_\{t\}=\(U\_\{t\}/U\_\{t\-1\}\)d\_\{t\}, includingt=1t=1by convention\. Multiply \([23](https://arxiv.org/html/2610.33381#A4.E23)\) of Lemma[10](https://arxiv.org/html/2610.33381#Thmtheorem10)\(Appendix[D](https://arxiv.org/html/2610.33381#A4)\), withz=ztz=z\_\{t\}andγ=ηt\\gamma=\\eta\_\{t\}, byW/UtW/U\_\{t\}to obtain

W​At\+Ht≤W​At−1\+UtUt−1​Ht−1\+qt2​‖et‖2\+⟨et,ht⟩\.WA\_\{t\}\+H\_\{t\}\\leq WA\_\{t\-1\}\+\\frac\{U\_\{t\}\}\{U\_\{t\-1\}\}H\_\{t\-1\}\+\\frac\{q\_\{t\}\}\{2\}\\\|e\_\{t\}\\\|^\{2\}\+\\langle e\_\{t\},h\_\{t\}\\rangle\.SinceUt≤Ut−1U\_\{t\}\\leq U\_\{t\-1\}, summation proves \([24](https://arxiv.org/html/2610.33381#A4.E24)\), usingqt/2≤qtq\_\{t\}/2\\leq q\_\{t\}\. Nonnegativity follows from the definitions\. The final synchronized update givesf⁡\(zT\+1\)−f⋆≤ATf\(z\_\{T\+1\}\)\-f^\{\\star\}\\leq A\_\{T\}and

‖zT\+1−xT\+1‖2=2​ζ2​HTW⁡\(ζ\+ηT\)\.\\\|z\_\{T\+1\}\-x\_\{T\+1\}\\\|^\{2\}=\\frac\{2\\zeta^\{2\}H\_\{T\}\}\{W\(\\zeta\+\\eta\_\{T\}\)\}\.ByLL\-smoothness evaluated atz−∇f​\(z\)/Lz\-\\nabla f\(z\)/L, we have‖∇f​\(z\)‖2≤2​L​\[f⁡\(z\)−f⋆\]\\\|\\nabla f\(z\)\\\|^\{2\}\\leq 2L\[f\(z\)\-f^\{\\star\}\]\. Thus, writingG⁡\(x\)=f⁡\(x\)−f⋆G\(x\)=f\(x\)\-f^\{\\star\}andρ=L​ζ2/\(ζ\+ηT\)\\rho=L\\zeta^\{2\}/\(\\zeta\+\\eta\_\{T\}\), smoothness and Cauchy–Schwarz give

G⁡\(xT\+1\)≤\(G⁡\(zT\+1\)\+L/2​‖xT\+1−zT\+1‖\)2≤\(1\+ρ\)​\(AT\+HT/W\)\.G\(x\_\{T\+1\}\)\\leq\\left\(\\sqrt\{G\(z\_\{T\+1\}\)\}\+\\sqrt\{L/2\}\\,\\\|x\_\{T\+1\}\-z\_\{T\+1\}\\\|\\right\)^\{2\}\\leq\(1\+\\rho\)\(A\_\{T\}\+H\_\{T\}/W\)\.Sinceρ≤L​ζ\\rho\\leq L\\zeta, this proves \([25](https://arxiv.org/html/2610.33381#A4.E25)\)\. Ifζ=0\\zeta=0,θT=1\\theta\_\{T\}=1also givesAT=GT\+1A\_\{T\}=G\_\{T\+1\}directly\.■\\blacksquare

The proofs of Theorems[2](https://arxiv.org/html/2610.33381#Thmtheorem2)and[5](https://arxiv.org/html/2610.33381#Thmtheorem5)takeζ=1\\zeta=1;ζ=0\\zeta=0givesW=S1W=S\_\{1\}andUt=StU\_\{t\}=S\_\{t\}\.

## Appendix EConditional Clipping Estimates

###### Lemma 12\(Bias and second moment after clipping\)\.

Conditionally on aσ\\sigma\-field𝒢\\mathcal\{G\}, supposeμ\\muis measurable,𝔼⁡\[g∣𝒢\]=μ\\mathbb\{E\}\[g\\mid\\mathcal\{G\}\]=\\mu, and𝔼⁡\[∥g−μ∥p∣𝒢\]≤σp\\mathbb\{E\}\[\\lVert g\-\\mu\\rVert^\{p\}\\mid\\mathcal\{G\}\]\\leq\\sigma^\{p\}, for1<p≤21<p\\leq 2\. If∥μ∥≤λ/2\\lVert\\mu\\rVert\\leq\\lambda/2, set

c=clip⁡\(g,λ\),e=c−μ,b=𝔼⁡\[e∣𝒢\],u=e−b\.c=\\operatorname\{clip\}\(g,\\lambda\),\\quad e=c\-\\mu,\\quad b=\\mathbb\{E\}\[e\\mid\\mathcal\{G\}\],\\quad u=e\-b\.Then

∥e∥\\displaystyle\\lVert e\\rVert≤min⁡\{∥g−μ∥,3​λ/2\},\\displaystyle\\leq\\min\\\{\\lVert g\-\\mu\\rVert,3\\lambda/2\\\},∥u∥\\displaystyle\\lVert u\\rVert≤2​λ,\\displaystyle\\leq 2\\lambda,∥b∥\\displaystyle\\lVert b\\rVert≤2p−1​σp​λ1−p≤2​σp​λ1−p,\\displaystyle\\leq 2^\{p\-1\}\\sigma^\{p\}\\lambda^\{1\-p\}\\leq 2\\sigma^\{p\}\\lambda^\{1\-p\},𝔼⁡\[∥e∥2∣𝒢\]\\displaystyle\\mathbb\{E\}\[\\lVert e\\rVert^\{2\}\\mid\\mathcal\{G\}\]≤\(3​λ/2\)2−p​σp≤2​σp​λ2−p,\\displaystyle\\leq\(3\\lambda/2\)^\{2\-p\}\\sigma^\{p\}\\leq 2\\sigma^\{p\}\\lambda^\{2\-p\},𝔼⁡\[∥u∥2∣𝒢\]\\displaystyle\\mathbb\{E\}\[\\lVert u\\rVert^\{2\}\\mid\\mathcal\{G\}\]≤𝔼⁡\[∥e∥2∣𝒢\]\.\\displaystyle\\leq\\mathbb\{E\}\[\\lVert e\\rVert^\{2\}\\mid\\mathcal\{G\}\]\.

ProofThese are the standard clipping bounds \(cf\.[Sadiev et al\., 2023](https://arxiv.org/html/2610.33381#bib.bib53), Lemma 5\.1\); the following Euclidean calculation records the sharper constants used here\. WriteP=clip⁡\(⋅,λ\)P=\\operatorname\{clip\}\(\\cdot,\\lambda\)andξ=g−μ\\xi=g\-\\mu\. SinceP​μ=μP\\mu=\\mu, nonexpansiveness and the clipping radius give

‖e‖≤min⁡\{‖ξ‖,3​λ/2\},‖u‖=‖P​g−𝔼⁡\[P​g∣𝒢\]‖≤2​λ\.\\\|e\\\|\\leq\\min\\\{\\\|\\xi\\\|,3\\lambda/2\\\},\\qquad\\\|u\\\|=\\\|Pg\-\\mathbb\{E\}\[Pg\\mid\\mathcal\{G\}\]\\\|\\leq 2\\lambda\.Also∥Pg−g∥≤∥ξ∥𝟏\{∥ξ∥\>λ/2\}\\\|Pg\-g\\\|\\leq\\\|\\xi\\\|\\mathbf\{1\}\_\{\\\{\\\|\\xi\\\|\>\\lambda/2\\\}\}, so

‖b‖=\|𝔼⁡\[P​g−g∣𝒢\]\|≤\(λ/2\)1−p​𝔼​\[‖ξ‖p∣𝒢\]\.\\\|b\\\|=\\\|\\mathbb\{E\}\[Pg\-g\\mid\\mathcal\{G\}\]\\\|\\leq\(\\lambda/2\)^\{1\-p\}\\mathbb\{E\}\[\\\|\\xi\\\|^\{p\}\\mid\\mathcal\{G\}\]\.Finally,

𝔼⁡\[‖u‖2∣𝒢\]≤𝔼⁡\[‖e‖2∣𝒢\]≤\(3​λ/2\)2−p​𝔼​\[‖ξ‖p∣𝒢\],\\mathbb\{E\}\[\\\|u\\\|^\{2\}\\mid\\mathcal\{G\}\]\\leq\\mathbb\{E\}\[\\\|e\\\|^\{2\}\\mid\\mathcal\{G\}\]\\leq\(3\\lambda/2\)^\{2\-p\}\\mathbb\{E\}\[\\\|\\xi\\\|^\{p\}\\mid\\mathcal\{G\}\],where the first inequality is conditional variance reduction by centering\.■\\blacksquare

The next decomposition imposes no bound on the true gradient\. Related Lipschitz estimates for the clipping factor appear in[Tian et al\. \[2026, Appendix C\.1\.2, Eqs\. \(13\)–\(14\)\]](https://arxiv.org/html/2610.33381#bib.bib60), under bounded noise\. We prove the conditionalpp\-moment bounds used here\.

###### Lemma 13\(Conditional mean and variance after clipping\)\.

Conditionally on aσ\\sigma\-field𝒢\\mathcal\{G\}, letμ\\mube measurable,𝔼⁡\[g∣𝒢\]=μ\\mathbb\{E\}\[g\\mid\\mathcal\{G\}\]=\\mu, and𝔼⁡\[∥g−μ∥p∣𝒢\]≤σp\\mathbb\{E\}\[\\lVert g\-\\mu\\rVert^\{p\}\\mid\\mathcal\{G\}\]\\leq\\sigma^\{p\}\. For deterministic or𝒢\\mathcal\{G\}\-measurableλ\>0\\lambda\>0, put

α⁡\(v\)=\{min⁡\{1,λ/∥v∥\},v≠0,1,v=0,C=clip⁡\(g,λ\),A=𝔼⁡\[α⁡\(g\)∣𝒢\]\.\\alpha\(v\)=\\begin\{cases\}\\min\\\{1,\\lambda/\\lVert v\\rVert\\\},&v\\neq 0,\\\\ 1,&v=0,\\end\{cases\}\\quad C=\\operatorname\{clip\}\(g,\\lambda\),\\quad A=\\mathbb\{E\}\[\\alpha\(g\)\\mid\\mathcal\{G\}\]\.Then0≤A≤10\\leq A\\leq 1and

𝔼⁡\[C∣𝒢\]=A​μ\+ε,∥ε∥≤σp​λ1−p\.\\mathbb\{E\}\[C\\mid\\mathcal\{G\}\]=A\\mu\+\\varepsilon,\\qquad\\lVert\\varepsilon\\rVert\\leq\\sigma^\{p\}\\lambda^\{1\-p\}\.Moreover,u=C−𝔼⁡\[C∣𝒢\]u=C\-\\mathbb\{E\}\[C\\mid\\mathcal\{G\}\]satisfies

∥u∥≤2​λ,𝔼⁡\[∥u∥2∣𝒢\]≤\(2​λ\)2−p​σp\.\\lVert u\\rVert\\leq 2\\lambda,\\qquad\\mathbb\{E\}\[\\lVert u\\rVert^\{2\}\\mid\\mathcal\{G\}\]\\leq\(2\\lambda\)^\{2\-p\}\\sigma^\{p\}\.In particular, ifσ≤1\\sigma\\leq 1andλ≥4\\lambda\\geq 4, thend=C−A​μ=ε\+ud=C\-A\\mu=\\varepsilon\+usatisfies

∥d∥≤3​λ,𝔼⁡\[∥d∥2∣𝒢\]≤4​λ2−p\.\\lVert d\\rVert\\leq 3\\lambda,\\qquad\\mathbb\{E\}\[\\lVert d\\rVert^\{2\}\\mid\\mathcal\{G\}\]\\leq 4\\lambda^\{2\-p\}\.

ProofThe scalar functionr↦min⁡\{1,λ/r\}r\\mapsto\\min\\\{1,\\lambda/r\\\}, extended by11at zero, is1/λ1/\\lambda\-Lipschitz on\[0,∞\)\[0,\\infty\)and takes values in\[0,1\]\[0,1\]\. Writingξ=g−μ\\xi=g\-\\muand using its conditional mean zero gives

ε\\displaystyle\\varepsilon=𝔼⁡\[α⁡\(g\)​ξ∣𝒢\]=𝔼⁡\[\(α⁡\(g\)−α⁡\(μ\)\)​ξ∣𝒢\],\\displaystyle=\\mathbb\{E\}\[\\alpha\(g\)\\xi\\mid\\mathcal\{G\}\]=\\mathbb\{E\}\[\(\\alpha\(g\)\-\\alpha\(\\mu\)\)\\xi\\mid\\mathcal\{G\}\],∥ε∥\\displaystyle\\lVert\\varepsilon\\rVert≤𝔼⁡\[min⁡\{∥ξ∥/λ,1\}​∥ξ∥∣𝒢\]≤λ1−p​𝔼​\[∥ξ∥p∣𝒢\]\.\\displaystyle\\leq\\mathbb\{E\}\\\!\\left\[\\min\\\{\\lVert\\xi\\rVert/\\lambda,1\\\}\\lVert\\xi\\rVert\\mid\\mathcal\{G\}\\right\]\\leq\\lambda^\{1\-p\}\\mathbb\{E\}\[\\lVert\\xi\\rVert^\{p\}\\mid\\mathcal\{G\}\]\.The final pointwise inequality follows separately for∥ξ∥≤λ\\lVert\\xi\\rVert\\leq\\lambdaand∥ξ∥\>λ\\lVert\\xi\\rVert\>\\lambda, usingp≤2p\\leq 2andp\>1p\>1, respectively\. For the projectionP=clip⁡\(⋅,λ\)P=\\operatorname\{clip\}\(\\cdot,\\lambda\), variance reduction and nonexpansiveness give

𝔼⁡\[∥u∥2∣𝒢\]≤𝔼⁡\[∥P​g−P​μ∥2∣𝒢\]≤𝔼⁡\[min⁡\{∥ξ∥,2​λ\}2∣𝒢\]≤\(2​λ\)2−p​σp\.\\mathbb\{E\}\[\\lVert u\\rVert^\{2\}\\mid\\mathcal\{G\}\]\\leq\\mathbb\{E\}\[\\lVert Pg\-P\\mu\\rVert^\{2\}\\mid\\mathcal\{G\}\]\\leq\\mathbb\{E\}\[\\min\\\{\\lVert\\xi\\rVert,2\\lambda\\\}^\{2\}\\mid\\mathcal\{G\}\]\\leq\(2\\lambda\)^\{2\-p\}\\sigma^\{p\}\.BothCCand its mean belong to the radius\-λ\\lambdaball, proving the range\. Under the last assumptions,∥ε∥≤λ1−p≤λ\\lVert\\varepsilon\\rVert\\leq\\lambda^\{1\-p\}\\leq\\lambda, so∥d∥≤3​λ\\lVert d\\rVert\\leq 3\\lambda; and

𝔼⁡\[∥d∥2∣𝒢\]=𝔼⁡\[∥u∥2∣𝒢\]\+∥ε∥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\}\\leq 2\\lambda^\{2\-p\}\+\\lambda^\{2\-2p\}\\leq 4\\lambda^\{2\-p\}\.■\\blacksquare

## Appendix FElementary 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\)\.

LetXtX\_\{t\}be adapted to\(ℱt\)t=0T\(\\mathcal\{F\}\_\{t\}\)\_\{t=0\}^\{T\}, with𝔼t−1​Xt=0\\mathbb\{E\}\_\{t\-1\}X\_\{t\}=0,\|Xt\|≤b\|X\_\{t\}\|\\leq balmost surely, and

∑t=1T𝔼t−1​Xt2≤valmost surely,\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{t\-1\}X\_\{t\}^\{2\}\\leq v\\quad\\text\{almost surely\},whereb,v≥0b,v\\geq 0are deterministic\. For anyℓ\>0\\ell\>0,

ℙ\{max1≤m≤T∑t=1mXt\>2v​ℓ\+2bℓ\}≤e−ℓ\.\\mathbb\{P\}\\left\\\{\\max\_\{1\\leq m\\leq T\}\\sum\_\{t=1\}^\{m\}X\_\{t\}\>2\\sqrt\{v\\ell\}\+2b\\ell\\right\\\}\\leq e^\{\-\\ell\}\.

ProofThe maximal form of Freedman’s inequality\[[Freedman, 1975](https://arxiv.org/html/2610.33381#bib.bib18), Theorem 1\.6\], after scaling the increments, gives

ℙ\{maxm≤T∑t≤mXt\>s\}≤exp\{−s22​\(v\+b​s\)\}\.\\mathbb\{P\}\\left\\\{\\max\_\{m\\leq T\}\\sum\_\{t\\leq m\}X\_\{t\}\>s\\right\\\}\\leq\\exp\\\!\\left\\\{\-\\frac\{s^\{2\}\}\{2\(v\+bs\)\}\\right\\\}\.Sets=2​v​ℓ\+2​b​ℓs=2\\sqrt\{v\\ell\}\+2b\\ell; thens2≥2​ℓ​\(v\+b​s\)s^\{2\}\\geq 2\\ell\(v\+bs\)\. Zero budgets follow by continuity\.■\\blacksquare

###### Lemma 15\(A common energy bound\)\.

Letete\_\{t\}be integrable and adapted,P0,…,PN≥0P\_\{0\},\\ldots,P\_\{N\}\\geq 0adapted,Jt∈\{0,1\}J\_\{t\}\\in\\\{0,1\\\}predictable and nonincreasing, andℰ\\mathcal\{E\}an event, for instanceℰ=Ω\\mathcal\{E\}=\\Omega\. Onℰ∩\{Jm=1\}\\mathcal\{E\}\\cap\\\{J\_\{m\}=1\\\}, suppose

Pm≤P0\+∑t≤m\{at​‖et‖2\+⟨et,wt⟩\},P\_\{m\}\\leq P\_\{0\}\+\\sum\_\{t\\leq m\}\\\{a\_\{t\}\\\|e\_\{t\}\\\|^\{2\}\+\\langle e\_\{t\},w\_\{t\}\\rangle\\\},wherewtw\_\{t\}is predictable with‖wt‖≤st​Pt−1\\\|w\_\{t\}\\\|\\leq s\_\{t\}\\sqrt\{P\_\{t\-1\}\}onJt=1J\_\{t\}=1, andat,st≥0a\_\{t\},s\_\{t\}\\geq 0are deterministic\. OnJt=1J\_\{t\}=1, assume‖𝔼t−1​et‖≤Bt\\\|\\mathbb\{E\}\_\{t\-1\}e\_\{t\}\\\|\\leq B\_\{t\},𝔼t−1​‖et‖2≤Vt\\mathbb\{E\}\_\{t\-1\}\\\|e\_\{t\}\\\|^\{2\}\\leq V\_\{t\},‖et‖≤Mt\\\|e\_\{t\}\\\|\\leq M\_\{t\}, and‖et−𝔼t−1​et‖≤Ut\\\|e\_\{t\}\-\\mathbb\{E\}\_\{t\-1\}e\_\{t\}\\\|\\leq U\_\{t\}, with deterministic bounds\. Put

A=∑tat​Vt,K0=suptat​Mt2,B0=∑tst​Bt,V0=∑tst2​Vt,J0=suptst​Ut\.A=\\sum\_\{t\}a\_\{t\}V\_\{t\},\\quad K\_\{0\}=\\sup\_\{t\}a\_\{t\}M\_\{t\}^\{2\},\\quad B\_\{0\}=\\sum\_\{t\}s\_\{t\}B\_\{t\},\\quad V\_\{0\}=\\sum\_\{t\}s\_\{t\}^\{2\}V\_\{t\},\\quad J\_\{0\}=\\sup\_\{t\}s\_\{t\}U\_\{t\}\.Forp0≥0p\_\{0\}\\geq 0andq\>0q\>0, define

C=p0\+A\+2​K0​A​q\+2​K0​q,D=B0\+2​V0​q\+2​J0​q\.C=p\_\{0\}\+A\+2\\sqrt\{K\_\{0\}Aq\}\+2K\_\{0\}q,\\qquad D=B\_\{0\}\+2\\sqrt\{V\_\{0\}q\}\+2J\_\{0\}q\.Except on probabilitye−qe^\{\-q\}, onℰ\\mathcal\{E\}, simultaneously for everymmwithJm=1J\_\{m\}=1andP0≤p0P\_\{0\}\\leq p\_\{0\},

Pm≤\(C\+D\)2\.P\_\{m\}\\leq\(\\sqrt\{C\}\+D\)^\{2\}\.The initial state may be random; the conclusion extends toN=∞N=\\inftyif the budgets are finite\.

ProofSetH=\(C\+D\)2H=\(\\sqrt\{C\}\+D\)^\{2\}andIt=Jt​𝟏\{P0≤p0,maxj<t⁡Pj≤H\}I\_\{t\}=J\_\{t\}\\mathbf\{1\}\_\{\\\{P\_\{0\}\\leq p\_\{0\},\\ \\max\_\{j<t\}P\_\{j\}\\leq H\\\}\}, a predictable indicator that does not involveℰ\\mathcal\{E\}\. Center only stopped quantities:Yt=It​‖et‖2Y\_\{t\}=I\_\{t\}\\\|e\_\{t\}\\\|^\{2\},mt=𝔼t−1​Ytm\_\{t\}=\\mathbb\{E\}\_\{t\-1\}Y\_\{t\}, andUt′=It​et−𝔼t−1​\(It​et\)U^\{\\prime\}\_\{t\}=I\_\{t\}e\_\{t\}\-\\mathbb\{E\}\_\{t\-1\}\(I\_\{t\}e\_\{t\}\)\. The martingale incrementsXt=at​\(Yt−mt\)\+⟨Ut′,wt⟩X\_\{t\}=a\_\{t\}\(Y\_\{t\}\-m\_\{t\}\)\+\\langle U^\{\\prime\}\_\{t\},w\_\{t\}\\ranglesatisfy

\|Xt\|≤K0\+H​J0,∑t𝔼t−1​Xt2≤K0​A\+H​V0\.\|X\_\{t\}\|\\leq K\_\{0\}\+\\sqrt\{H\}J\_\{0\},\\qquad\\sqrt\{\\sum\_\{t\}\\mathbb\{E\}\_\{t\-1\}X\_\{t\}^\{2\}\}\\leq\\sqrt\{K\_\{0\}A\}\+\\sqrt\{HV\_\{0\}\}\.Indeed, conditional variance reduction and the conditionalL2L^\{2\}triangle inequality give𝔼t−1​Xt2≤It​Vt​\(at​Mt\+st​H\)\\sqrt\{\\mathbb\{E\}\_\{t\-1\}X\_\{t\}^\{2\}\}\\leq I\_\{t\}\\sqrt\{V\_\{t\}\}\(a\_\{t\}M\_\{t\}\+s\_\{t\}\\sqrt\{H\}\); then use the triangle inequality for the deterministic sequence of bounds\. By Lemma[14](https://arxiv.org/html/2610.33381#Thmtheorem14), except on probabilitye−qe^\{\-q\}, every partial sum of theXtX\_\{t\}is at most2​K0​A​q\+2​K0​q\+H​\(2​V0​q\+2​J0​q\)2\\sqrt\{K\_\{0\}Aq\}\+2K\_\{0\}q\+\\sqrt\{H\}\(2\\sqrt\{V\_\{0\}q\}\+2J\_\{0\}q\)\. On this event and onP0≤p0P\_\{0\}\\leq p\_\{0\}, the mean and bias budgets give, for everymm,

P0\+∑t≤mIt​\{at​‖et‖2\+⟨et,wt⟩\}≤C\+H​D≤H,P\_\{0\}\+\\sum\_\{t\\leq m\}I\_\{t\}\\\{a\_\{t\}\\\|e\_\{t\}\\\|^\{2\}\+\\langle e\_\{t\},w\_\{t\}\\rangle\\\}\\leq C\+\\sqrt\{H\}D\\leq H,sinceH−C−H​D=C​DH\-C\-\\sqrt\{H\}D=\\sqrt\{C\}D\. Suppose that, on this event and onℰ\\mathcal\{E\}, somemmwithJm=1J\_\{m\}=1andP0≤p0P\_\{0\}\\leq p\_\{0\}hasPm\>HP\_\{m\}\>H, and take the first suchmm\. ThenIt=1I\_\{t\}=1for everyt≤mt\\leq m, so the assumed recursion boundsPmP\_\{m\}by the left side above, a contradiction\. Taking the union over finite prefixes yields the claim forN=∞N=\\infty\.■\\blacksquare

## Appendix GClipped versus Unclipped SGD

## Appendix HProofs for the Time\-Uniform Lower Bound and Fixed\-Time Guarantees

This appendix proves Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)and Theorems[4](https://arxiv.org/html/2610.33381#Thmtheorem4)and[6](https://arxiv.org/html/2610.33381#Thmtheorem6); Theorem[5](https://arxiv.org/html/2610.33381#Thmtheorem5)is proved in Appendix[I\.6](https://arxiv.org/html/2610.33381#A9.SS6)\. For the lower bounds we fixp∈\(1,2\]p\\in\(1,2\],L=R=σ=1L=R=\\sigma=1, andx1=0x\_\{1\}=0\. The rules are those of Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3), and the same rule is used on every instance\.

### H\.1Proof Ideas

*The upper bound\.*We first derive 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 actual endpoint gap by \([25](https://arxiv.org/html/2610.33381#A4.E25)\)\. A summable allocation over horizons and a direct bound at early times give the sameDp=4/cpD\_\{p\}=4/c\_\{p\}for all times \(Appendix[I](https://arxiv.org/html/2610.33381#A9)\)\.

*The lower bound\.*The sample lossesFμ,y​\(x,Y\)=12​\(x−y\+μ\)\+2−A​Y​xF\_\{\\mu,y\}\(x;Y\)=\\tfrac\{1\}\{2\}\(x\-y\+\\mu\)\_\{\+\}^\{2\}\-AYx, withY∼Bernoulli⁡\(μ/A\)Y\\sim\\operatorname\{Bernoulli\}\(\\mu/A\)andA=\(2μ\)−1/\(p−1\)A=\(2\\mu\)^\{\-1/\(p\-1\)\}, have minimizery∈\[μ,1\]y\\in\[\\mu,1\]in expectation\. Every target gives the same gradient−A​Y\-AYbefore crossing its boundaryy−μy\-\\mu\. A shared transcript therefore couples all fixed targets\. An overshoot longer thanμ\+2​bt\\mu\+\\sqrt\{2b\_\{t\}\}violates one target’s envelope\. Integrating, over the target location, the probabilities of failing at the first crossing charges safe progress only to rare arrivals, which yields the following bound\.

###### Proposition 17\(Progress bound under time\-uniform guarantees\)\.

Fixε∈\(0,1/2\)\\varepsilon\\in\(0,1/2\),N≥1N\\geq 1, a rule of Definition[3](https://arxiv.org/html/2610.33381#Thmtheorem3), and positive numbersb1,…,bNb\_\{1\},\\ldots,b\_\{N\}; the rule may be tuned to a confidence level different fromε\\varepsilon\. Suppose that every instance in the class of Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)satisfies

ℙ\{f\(xt\+1\)−f⋆≤btfor all1≤t≤N\}≥1−ε\.\\mathbb\{P\}\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\\leq b\_\{t\}\\text\{ for all \}1\\leq t\\leq N\\\}\\geq 1\-\\varepsilon\.\(26\)Then for everyμ∈\(4​bN,1/2\]\\mu\\in\(4b\_\{N\},1/2\], withA=\(2μ\)−1/\(p−1\)A=\(2\\mu\)^\{\-1/\(p\-1\)\}andπ=μ/A\\pi=\\mu/A,

π​∑t=1N\(μ\+2​bt\)≥1−2​ε2\.\\pi\\sum\_\{t=1\}^\{N\}\\bigl\(\\mu\+\\sqrt\{2b\_\{t\}\}\\bigr\)\\geq\\frac\{1\-2\\varepsilon\}\{2\}\.\(27\)

Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)bounds the total progress without restricting adaptive jump sizes or choosing the target after seeing the path\. For any claimed exponentr\>βpr\>\\beta\_\{p\}, chooseβp<u<min⁡\{r,1\}\\beta\_\{p\}<u<\\min\\\{r,1\\\}and dominate its firstNNerrors bybN,t=C​logm⁡\(e​N\)​t−ub\_\{N,t\}=C\\log^\{m\}\(eN\)t^\{\-u\}\. Withμ=8​bN,N\\mu=8b\_\{N,N\},π≍μp/\(p−1\)\\pi\\asymp\\mu^\{p/\(p\-1\)\}and the budget is, up to logarithms,N1−u⁡\(p/\(p−1\)\+1/2\)→0N^\{1\-u\(p/\(p\-1\)\+1/2\)\}\\to 0\. Appendix[H](https://arxiv.org/html/2610.33381#A8)records this calculation once for Theorems[4](https://arxiv.org/html/2610.33381#Thmtheorem4),[6](https://arxiv.org/html/2610.33381#Thmtheorem6), and[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\.

### H\.2Translated Targets with a Common I\.I\.D\. Transcript

For0<μ≤1/20<\\mu\\leq 1/2andy∈\[μ,1\]y\\in\[\\mu,1\], define

fμ,y​\(x\)=12​\(x−y\+μ\)\+2−μ​x,fμ,y⋆=−μ​y\+μ2/2\.f\_\{\\mu,y\}\(x\)=\\tfrac\{1\}\{2\}\(x\-y\+\\mu\)\_\{\+\}^\{2\}\-\\mu x,\\qquad f\_\{\\mu,y\}^\{\\star\}=\-\\mu y\+\\mu^\{2\}/2\.Its derivative is−μ\-\\muonx≤y−μx\\leq y\-\\muandx−yx\-yonx≥y−μx\\geq y\-\\mu\. These branches agree at the transition\. Thusfμ,yf\_\{\\mu,y\}is convex and globally11\-smooth, with unique minimizeryyand 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−μ\.f\_\{\\mu,y\}\(x\)\-f\_\{\\mu,y\}^\{\\star\}=\\begin\{cases\}\\mu\(y\-x\)\-\\mu^\{2\}/2,&x\\leq y\-\\mu,\\\\ \(x\-y\)^\{2\}/2,&x\\geq y\-\\mu\.\\end\{cases\}\(28\)This objective is a reflected and translated one\-sided Huber loss\[[Huber, 1964](https://arxiv.org/html/2610.33381#bib.bib24)\], following the construction of[Kornowski and Shamir \[2024, Theorem 2 and Section 3\.2\]](https://arxiv.org/html/2610.33381#bib.bib28);[Tsai et al\. \[2026, Lemma 3\.1\]](https://arxiv.org/html/2610.33381#bib.bib62)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/\(2Ap\),Yti\.i\.d\.Bernoulli\(π\)\.A=\(2\\mu\)^\{\-1/\(p\-1\)\}\\geq 1,\\qquad\\pi=\\mu/A=1/\(2A^\{p\}\),\\qquad Y\_\{t\}\\ \\text\{i\.i\.d\.\}\\ \\operatorname\{Bernoulli\}\(\\pi\)\.\(29\)Independently of the algorithm’s seed, each call draws a freshYtY\_\{t\}\. Use the sample loss

Fμ,y​\(x,Y\)=12​\(x−y\+μ\)\+2−A​Y​x=fμ,y​\(x\)\+\(μ−A​Y\)​x\.F\_\{\\mu,y\}\(x;Y\)=\\tfrac\{1\}\{2\}\(x\-y\+\\mu\)\_\{\+\}^\{2\}\-AYx=f\_\{\\mu,y\}\(x\)\+\(\\mu\-AY\)x\.\(30\)The additive noiseζ=μ−A​Y\\zeta=\\mu\-AYis centered, independent of the query and time, and has the same law for everyyy\. Sinceμ≤A\\mu\\leq A,

𝔼​\|ζ\|p=\(1−π\)​μp\+π​\(A−μ\)p≤μp\+μ​Ap−1≤2​μ​Ap−1=1\.\\mathbb\{E\}\|\\zeta\|^\{p\}=\(1\-\\pi\)\\mu^\{p\}\+\\pi\(A\-\\mu\)^\{p\}\\leq\\mu^\{p\}\+\\mu A^\{p\-1\}\\leq 2\\mu A^\{p\-1\}=1\.Every sample loss is convex and globally11\-smooth, bounded below, and attains its minimum: forY=0Y=0, everyx≤y−μx\\leq y\-\\muis a minimizer; forY=1Y=1, the minimizer isy−μ\+Ay\-\\mu\+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\\leq y\-\\mu\)\.The algorithm observes only these gradients and does not knowyyorf⋆f^\{\\star\}\.

### H\.3Proof of Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)

We first isolate two lemmas used both here and for the momentum lower bound in Appendix[J](https://arxiv.org/html/2610.33381#A10): 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\)\.

LetN≥1N\\geq 1be an integer, letX1=0≤⋯≤XN\+1X\_\{1\}=0\\leq\\cdots\\leq X\_\{N\+1\}be finite random variables, and putDt=Xt\+1−Xt≥0D\_\{t\}=X\_\{t\+1\}\-X\_\{t\}\\geq 0\. For deterministic finitec\>0c\>0,s1,…,sN≥0s\_\{1\},\\ldots,s\_\{N\}\\geq 0, and0≤ε<1/20\\leq\\varepsilon<1/2, supposeℙ⁡\(XN\+1\>c\)≥1−ε\\mathbb\{P\}\(X\_\{N\+1\}\>c\)\\geq 1\-\\varepsilonand, for each fixedz∈\[0,c\)z\\in\[0,c\),

ℙ\{∃t≤N:Xt≤z<Xt\+1,Xt\+1\>z\+st\}≤ε\.\\mathbb\{P\}\\\{\\exists t\\leq N:\\ X\_\{t\}\\leq z<X\_\{t\+1\},\\quad X\_\{t\+1\}\>z\+s\_\{t\}\\\}\\leq\\varepsilon\.Thenc⁡\(1−2​ε\)≤𝔼​∑t=1Nmin⁡\{st,Dt\}c\(1\-2\\varepsilon\)\\leq\\mathbb\{E\}\\sum\_\{t=1\}^\{N\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\.

ProofLetB=\[0,c\)∩⋃t=1N\[Xt,Xt\+1−st\)B=\[0,c\)\\cap\\bigcup\_\{t=1\}^\{N\}\[X\_\{t\},X\_\{t\+1\}\-s\_\{t\}\)be the badly crossed boundaries, with reversed intervals empty\. Measurable endpoints make𝟏\{z∈B\}\\mathbf\{1\}\_\{\\\{z\\in B\\\}\}jointly measurable\. The fixed\-zzhypothesis and Tonelli’s theorem give𝔼​\|B\|=∫0cℙ⁡\(z∈B\)​𝑑z≤c​ε\\mathbb\{E\}\|B\|=\\int\_\{0\}^\{c\}\\mathbb\{P\}\(z\\in B\)\\,dz\\leq c\\varepsilon, where\|B\|\|B\|denotes Lebesgue measure\. At updatett, the safely crossed boundaries have total length at mostmin⁡\{st,Dt\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\. On\{XN\+1\>c\}\\\{X\_\{N\+1\}\>c\\\}every boundary in\[0,c\)\[0,c\)has been crossed, so

c𝟏\{XN\+1\>c\}≤\|B\|\+∑t=1Nmin\{st,Dt\}\.c\\mathbf\{1\}\_\{\\\{X\_\{N\+1\}\>c\\\}\}\\leq\|B\|\+\\sum\_\{t=1\}^\{N\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\.Taking expectations proves the claim\.■\\blacksquare

###### Lemma 19\(Fixed targets coupled at the first crossing\)\.

Fix0<ε<1/20<\\varepsilon<1/2, an integerN≥1N\\geq 1, positive numbersb1,…,bNb\_\{1\},\\ldots,b\_\{N\}, andμ∈\(4​bN,1/2\]\\mu\\in\(4b\_\{N\},1/2\]\. LetAA,π\\pi, andYtY\_\{t\}be as in \([29](https://arxiv.org/html/2610.33381#A8.E29)\), and putc=1/2c=1/2andst=μ\+2​bts\_\{t\}=\\mu\+\\sqrt\{2b\_\{t\}\}\. Consider a method that starts atx1=0x\_\{1\}=0, queries one stochastic gradient at its current iteratextx\_\{t\}, and computesxt\+1∈ℝx\_\{t\+1\}\\in\\mathbb\{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 instancefμ,yf\_\{\\mu,y\},y∈\[μ,1\]y\\in\[\\mu,1\], with sample loss \([30](https://arxiv.org/html/2610.33381#A8.E30)\) satisfies \([26](https://arxiv.org/html/2610.33381#A8.E26)\)\. Let the reference runXtX\_\{t\}be the states produced from the observations−A​Yt\-AY\_\{t\}and the seed through the first update withXt\+1\>cX\_\{t\+1\}\>c, held fixed thereafter without further oracle calls\. IfXtX\_\{t\}is nondecreasing, thenDt=Xt\+1−XtD\_\{t\}=X\_\{t\+1\}\-X\_\{t\}satisfiesc⁡\(1−2​ε\)≤𝔼​∑t=1Nmin⁡\{st,Dt\}c\(1\-2\\varepsilon\)\\leq\\mathbb\{E\}\\sum\_\{t=1\}^\{N\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\.

ProofSincec≤1−μc\\leq 1\-\\mu, every query before stopping lies where targety=1y=1returns−A​Yt\-AY\_\{t\}, so the reference agrees with the run on that target until it stops\. On\{XN\+1≤c\}\\\{X\_\{N\+1\}\\leq c\\\}it has not stopped by timeNN, and \([28](https://arxiv.org/html/2610.33381#A8.E28)\) gives

fμ,1​\(XN\+1\)−fμ,1⋆≥μ⁡\(1−c\)−μ2/2≥μ/4\>bN\.f\_\{\\mu,1\}\(X\_\{N\+1\}\)\-f\_\{\\mu,1\}^\{\\star\}\\geq\\mu\(1\-c\)\-\\mu^\{2\}/2\\geq\\mu/4\>b\_\{N\}\.Henceℙ⁡\(XN\+1\>c\)≥1−ε\\mathbb\{P\}\(X\_\{N\+1\}\>c\)\\geq 1\-\\varepsilon\.

For any fixedz∈\[0,c\)z\\in\[0,c\), couple targety=z\+μy=z\+\\muusing 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 crossingzz: all queries up to that update lie at or belowz=y−μz=y\-\\muand have the same observations−A​Yt\-AY\_\{t\}\. Each target is coupled separately, before the run\. If that first crossing hasXt\+1\>z\+stX\_\{t\+1\}\>z\+s\_\{t\}, the coupled target has gap\(Xt\+1−z−μ\)2/2\>bt\(X\_\{t\+1\}\-z\-\\mu\)^\{2\}/2\>b\_\{t\}\. Its prefix guarantee verifies the crossing hypothesis of Lemma[18](https://arxiv.org/html/2610.33381#Thmtheorem18)for each fixedzz, and that lemma applies\.■\\blacksquare

Proofof Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)\.Letε\\varepsilon,NN, the rule, andb1,…,bNb\_\{1\},\\ldots,b\_\{N\}be as in its statement, and fixμ∈\(4​bN,1/2\]\\mu\\in\(4b\_\{N\},1/2\]\. The instances of Appendix[H\.2](https://arxiv.org/html/2610.33381#A8.SS2)belong to the class of Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4), and the rule meets the conditions of Lemma[19](https://arxiv.org/html/2610.33381#Thmtheorem19)\. LetXtX\_\{t\}be its reference run, withc=1/2c=1/2andst=μ\+2​bts\_\{t\}=\\mu\+\\sqrt\{2b\_\{t\}\}\. All observations prior to stopping equal−A​Yt\-AY\_\{t\}, so

X1=0,Xt\+1=Xt\+Yt​qt≥Xt≥0,X\_\{1\}=0,\\qquad X\_\{t\+1\}=X\_\{t\}\+Y\_\{t\}q\_\{t\}\\geq X\_\{t\}\\geq 0,whereqt=A​ct≥0q\_\{t\}=Ac\_\{t\}\\geq 0before stopping andqt=0q\_\{t\}=0afterwards\. The responses are finite but need not be integrable or independent ofYtY\_\{t\}\. SinceDt=Yt​qtD\_\{t\}=Y\_\{t\}q\_\{t\}, we havemin⁡\{st,Dt\}≤Yt​st\\min\\\{s\_\{t\},D\_\{t\}\\\}\\leq Y\_\{t\}s\_\{t\}\. Sincec=1/2c=1/2, Lemma[19](https://arxiv.org/html/2610.33381#Thmtheorem19)and𝔼​Yt=π\\mathbb\{E\}Y\_\{t\}=\\pigive \([27](https://arxiv.org/html/2610.33381#A8.E27)\):

c⁡\(1−2​ε\)≤𝔼​∑t=1Nmin⁡\{st,Dt\}≤π​∑t=1Nst\.c\(1\-2\\varepsilon\)\\leq\\mathbb\{E\}\\sum\_\{t=1\}^\{N\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\\leq\\pi\\sum\_\{t=1\}^\{N\}s\_\{t\}\.■\\blacksquare

### H\.4Proof of the Time\-Uniform Lower Bound

We first record the exponent calculation shared by Theorems[4](https://arxiv.org/html/2610.33381#Thmtheorem4)and[7](https://arxiv.org/html/2610.33381#Thmtheorem7); the proof of Theorem[6](https://arxiv.org/html/2610.33381#Thmtheorem6)repeats it with a confidence factor\. Putq=p/\(p−1\)q=p/\(p\-1\)and chooseβp<u<min⁡\{r,1\}\\beta\_\{p\}<u<\\min\\\{r,1\\\}\. For any positive subpolynomial factorsDN,KN=No⁡\(1\)D\_\{N\},K\_\{N\}=N^\{o\(1\)\}, let

bN,t=DN​t−u,μ=8​DN​N−u,π=21/\(p−1\)​μq\.b\_\{N,t\}=D\_\{N\}t^\{\-u\},\\qquad\\mu=8D\_\{N\}N^\{\-u\},\\qquad\\pi=2^\{1/\(p\-1\)\}\\mu^\{q\}\.\(31\)Thenμ/2​bN,N=42DNN−u/2→0\\mu/\\sqrt\{2b\_\{N,N\}\}=4\\sqrt\{2\}\\sqrt\{D\_\{N\}\}N^\{\-u/2\}\\to 0\. SincebN,t≥bN,Nb\_\{N,t\}\\geq b\_\{N,N\},u<1u<1, andβp=1/\(q\+1/2\)\\beta\_\{p\}=1/\(q\+1/2\), summingt−u/2t^\{\-u/2\}gives

KN​π​∑t=1N\(μ\+2​bN,t\)=O⁡\(KN​DNq\+1/2​N1−u⁡\(q\+1/2\)\)⟶0\.K\_\{N\}\\pi\\sum\_\{t=1\}^\{N\}\(\\mu\+\\sqrt\{2b\_\{N,t\}\}\)=O\\\!\\left\(K\_\{N\}D\_\{N\}^\{q\+1/2\}N^\{1\-u\(q\+1/2\)\}\\right\)\\longrightarrow 0\.\(32\)
Proofof Theorem[4](https://arxiv.org/html/2610.33381#Thmtheorem4)\.Suppose its envelope holds on every instance\. Chooseuuas above andDN=C​logm⁡\(e​N\)D\_\{N\}=C\\log^\{m\}\(eN\), soC​t−r​logm⁡\(e​t\)≤bN,tCt^\{\-r\}\\log^\{m\}\(et\)\\leq b\_\{N,t\}fort≤Nt\\leq N\. For all sufficiently largeNN,4​bN,N<μ≤1/24b\_\{N,N\}<\\mu\\leq 1/2\. Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17)withε=δ\\varepsilon=\\deltacontradicts \([32](https://arxiv.org/html/2610.33381#A8.E32)\) withKN=1K\_\{N\}=1\. A failing finite prefix yields \([9](https://arxiv.org/html/2610.33381#S4.E9)\)\. The resulting instance is fixed before its i\.i\.d\. samples and the algorithm seed are drawn, and it may depend onNN\.■\\blacksquare

### H\.5Proof of Theorem[6](https://arxiv.org/html/2610.33381#Thmtheorem6)

ProofSuppose the displayed envelope holds on every instance at every time and confidence\. Sincec<1−βpc<1\-\\beta\_\{p\}andr\>βp\+cr\>\\beta\_\{p\}\+c, we may chooseβp\+c<u<min⁡\{r,1\}\\beta\_\{p\}\+c<u<\\min\\\{r,1\\\}; putv=u−c\>βpv=u\-c\>\\beta\_\{p\}\. For each deterministicNN, set

δN=14​N,DN=C​4c​logm⁡\(4​e​N2\),bN,t=DN​Nc​t−u\.\\delta\_\{N\}=\\frac\{1\}\{4N\},\\qquad D\_\{N\}=C4^\{c\}\\log^\{m\}\(4eN^\{2\}\),\\qquad b\_\{N,t\}=D\_\{N\}N^\{c\}t^\{\-u\}\.SinceδN−c=\(4​N\)c\\delta\_\{N\}^\{\-c\}=\(4N\)^\{c\}andlog⁡\(e​t/δN\)≤log⁡\(4​e​N2\)\\log\(et/\\delta\_\{N\}\)\\leq\\log\(4eN^\{2\}\), the claimed fixed\-time envelope is at mostbN,tb\_\{N,t\}fort≤Nt\\leq N\. Use theδN\\delta\_\{N\}\-tuned rule on the prefix\. A union bound gives failure probability at mostN​δN=1/4N\\delta\_\{N\}=1/4on every instance\. Proposition[17](https://arxiv.org/html/2610.33381#Thmtheorem17), with the separate budgetε0=1/4\\varepsilon\_\{0\}=1/4andμ=8​bN,N=8​DN​N−v\\mu=8b\_\{N,N\}=8D\_\{N\}N^\{\-v\}, which lies in\(4​bN,N,1/2\]\(4b\_\{N,N\},1/2\]for largeNN, therefore requiresπ​∑t≤N\(μ\+2​bN,t\)≥1/4\\pi\\sum\_\{t\\leq N\}\(\\mu\+\\sqrt\{2b\_\{N,t\}\}\)\\geq 1/4\. Withπ=21/\(p−1\)​μq\\pi=2^\{1/\(p\-1\)\}\\mu^\{q\}and∑t≤Nt−u/2≤2N1−u/2\\sum\_\{t\\leq N\}t^\{\-u/2\}\\leq 2N^\{1\-u/2\},

π∑t≤N\(μ\+2​bN,t\)≤21/\(p−1\)8qDNq\(8DNN−v/2\+22​DN\)N1−v⁡\(q\+1/2\)\.\\pi\\sum\_\{t\\leq N\}\(\\mu\+\\sqrt\{2b\_\{N,t\}\}\)\\leq 2^\{1/\(p\-1\)\}8^\{q\}D\_\{N\}^\{q\}\\bigl\(8D\_\{N\}N^\{\-v/2\}\+2\\sqrt\{2D\_\{N\}\}\\bigr\)N^\{1\-v\(q\+1/2\)\}\.The right side tends to zero, becauseDN=No⁡\(1\)D\_\{N\}=N^\{o\(1\)\}andv⁡\(q\+1/2\)=v/βp\>1v\(q\+1/2\)=v/\\beta\_\{p\}\>1; this is a contradiction\. By the union bound, a failure probability exceeding1/41/4on the prefix1≤t≤N1\\leq t\\leq Nimplies a fixed\-time failure probability aboveδN\\delta\_\{N\}at some deterministict≤Nt\\leq N\.■\\blacksquare

## Appendix IProof of the Horizon\-Free Time\-Uniform Upper Bound

We first prove Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2)under the normalized upper boundsL,R,σ≤1L,R,\\sigma\\leq 1\. Thus∥x1−x⋆∥≤1\\lVert x\_\{1\}\-x^\{\\star\}\\rVert\\leq 1,ffis convex and at most11\-smooth, and the conditional centralppth noise moment is at most one\. Defineβ,a,b\\beta,a,bby \([4](https://arxiv.org/html/2610.33381#S4.E4)\), and write

ℓt=log⁡\(100​t2\),ηt=c​t−a/ℓt2,λt=4​tb\.\\ell\_\{t\}=\\log\(100t^\{2\}\),\\qquad\\eta\_\{t\}=ct^\{\-a\}/\\ell\_\{t\}^\{2\},\\qquad\\lambda\_\{t\}=4t^\{b\}\.Herec∈\(0,1\]c\\in\(0,1\]is a deterministic constant depending only onpp, chosen below\. SetGt=f⁡\(xt\)−f⋆G\_\{t\}=f\(x\_\{t\}\)\-f^\{\\star\},et=clip⁡\(gt,λt\)−∇f​\(xt\)e\_\{t\}=\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\)\-\\nabla f\(x\_\{t\}\),bt=𝔼t−1​etb\_\{t\}=\\mathbb\{E\}\_\{t\-1\}e\_\{t\}, andut=et−btu\_\{t\}=e\_\{t\}\-b\_\{t\}\. Whenever∥∇f​\(xt\)∥≤λt/2\\lVert\\nabla f\(x\_\{t\}\)\\rVert\\leq\\lambda\_\{t\}/2, Lemma[12](https://arxiv.org/html/2610.33381#Thmtheorem12)gives

∥et∥≤32λt,∥ut∥≤2λt,∥bt∥≤Bt:=2λt1−p,𝔼t−1∥et∥2,𝔼t−1∥ut∥2≤Vt:=2λt2−p\.\\lVert e\_\{t\}\\rVert\\leq\\tfrac\{3\}\{2\}\\lambda\_\{t\},\\quad\\lVert u\_\{t\}\\rVert\\leq 2\\lambda\_\{t\},\\quad\\lVert b\_\{t\}\\rVert\\leq B\_\{t\}:=2\\lambda\_\{t\}^\{1\-p\},\\quad\\mathbb\{E\}\_\{t\-1\}\\lVert e\_\{t\}\\rVert^\{2\},\\ \\mathbb\{E\}\_\{t\-1\}\\lVert u\_\{t\}\\rVert^\{2\}\\leq V\_\{t\}:=2\\lambda\_\{t\}^\{2\-p\}\.\(33\)The boundsBt,VtB\_\{t\},V\_\{t\}are deterministic\. The concentration arguments below apply these conditional estimates on predictable events\.

### I\.1Explicit Constants and Deterministic Budgets

Putv=\(2−p\)​bv=\(2\-p\)b\. The exponent identities needed throughout are

b⁡\(p−1\)=β,a\+β=1,2​\(a−b\)=β,a−v=32​β,2​a−v=1\+12​β\.b\(p\-1\)=\\beta,\\qquad a\+\\beta=1,\\qquad 2\(a\-b\)=\\beta,\\qquad a\-v=\\tfrac\{3\}\{2\}\\beta,\\qquad 2a\-v=1\+\\tfrac\{1\}\{2\}\\beta\.\(34\)Letq=2−βq=2^\{\-\\beta\}and define the following finite constants:

Jβ\\displaystyle J\_\{\\beta\}=∑j=0∞qj​\(j\+2\)2=q⁡\(1\+q\)\(1−q\)3\+4​q\(1−q\)2\+41−q,\\displaystyle=\\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\},Hβ\\displaystyle H\_\{\\beta\}=64​\(1\+β−1\+Jβ\),K=220​Hβ4,\\displaystyle=64\(1\+\\beta^\{\-1\}\+J\_\{\\beta\}\),\\qquad K=2^\{20\}H\_\{\\beta\}^\{4\},\(35\)cp\\displaystyle c\_\{p\}=11000​K,Dp=4cp\.\\displaystyle=\\frac\{1\}\{1000K\},\\qquad D\_\{p\}=\\frac\{4\}\{c\_\{p\}\}\.These constants depend only onpp\. The deterministic inequalities below hold for every0<c≤10<c\\leq 1; we then takec=cpc=c\_\{p\}\.

For a deterministic proof horizonTT, setSt=∑s=tTηsS\_\{t\}=\\sum\_\{s=t\}^\{T\}\\eta\_\{s\},S0=S1S\_\{0\}=S\_\{1\},ST\+1=0S\_\{T\+1\}=0,U=1\+S1U=1\+S\_\{1\}, and

𝖰t=U​ηt21\+St\.\\mathsf\{Q\}\_\{t\}=\\frac\{U\\eta\_\{t\}^\{2\}\}\{1\+S\_\{t\}\}\.\(36\)The following estimates treat early times, late times, and small cumulative step sums\.

###### Lemma 20\(Deterministic anytime budgets\)\.

For allT≥1T\\geq 1and0<c≤10<c\\leq 1,

c2​TβℓT2≤S1\\displaystyle\\frac\{c\}\{2\}\\frac\{T^\{\\beta\}\}\{\\ell\_\{T\}^\{2\}\}\\leq S\_\{1\}≤Hβ​c​TβℓT2,\\displaystyle\\leq H\_\{\\beta\}c\\frac\{T^\{\\beta\}\}\{\\ell\_\{T\}^\{2\}\},\(37\)∑t≥1ηt​Bt\\displaystyle\\sum\_\{t\\geq 1\}\\eta\_\{t\}B\_\{t\}≤K​c/ℓ1,∑t≥1ηt2​Vt≤K​c2/ℓ14,supt≥1ηt​λt≤4​c/ℓ12,\\displaystyle\\leq Kc/\\ell\_\{1\},\\qquad\\sum\_\{t\\geq 1\}\\eta\_\{t\}^\{2\}V\_\{t\}\\leq Kc^\{2\}/\\ell\_\{1\}^\{4\},\\qquad\\sup\_\{t\\geq 1\}\\eta\_\{t\}\\lambda\_\{t\}\\leq 4c/\\ell\_\{1\}^\{2\},\(38\)∑t=1T𝖰t​Bt\\displaystyle\\sum\_\{t=1\}^\{T\}\\sqrt\{\\mathsf\{Q\}\_\{t\}\}B\_\{t\}≤K​c/ℓ1,∑t=1T𝖰t​Vt≤K​c2/ℓ13,maxt≤T⁡𝖰t​λt2≤K​c2/ℓ14\.\\displaystyle\\leq Kc/\\ell\_\{1\},\\qquad\\sum\_\{t=1\}^\{T\}\\mathsf\{Q\}\_\{t\}V\_\{t\}\\leq Kc^\{2\}/\\ell\_\{1\}^\{3\},\\qquad\\max\_\{t\\leq T\}\\mathsf\{Q\}\_\{t\}\\lambda\_\{t\}^\{2\}\\leq Kc^\{2\}/\\ell\_\{1\}^\{4\}\.\(39\)

ProofFromBt≤2​t−βB\_\{t\}\\leq 2t^\{\-\\beta\},Vt≤8​tvV\_\{t\}\\leq 8t^\{v\}and \([34](https://arxiv.org/html/2610.33381#A9.E34)\),

ηt​Bt≤2​ct​ℓt2,ηt2​Vt≤8​c2​t−1−β/2ℓt4,ηt2​λt2=16​c2​t−βℓt4\.\\eta\_\{t\}B\_\{t\}\\leq\\frac\{2c\}\{t\\ell\_\{t\}^\{2\}\},\\qquad\\eta\_\{t\}^\{2\}V\_\{t\}\\leq\\frac\{8c^\{2\}t^\{\-1\-\\beta/2\}\}\{\\ell\_\{t\}^\{4\}\},\\qquad\\eta\_\{t\}^\{2\}\\lambda\_\{t\}^\{2\}=\\frac\{16c^\{2\}t^\{\-\\beta\}\}\{\\ell\_\{t\}^\{4\}\}\.Integral comparison gives∑t\(t​ℓt2\)−1≤ℓ1−1\\sum\_\{t\}\(t\\ell\_\{t\}^\{2\}\)^\{\-1\}\\leq\\ell\_\{1\}^\{\-1\}and∑tt−1−β/2≤1\+2/β\\sum\_\{t\}t^\{\-1\-\\beta/2\}\\leq 1\+2/\\beta, proving \([38](https://arxiv.org/html/2610.33381#A9.E38)\)\. The final⌈T/2⌉\\lceil T/2\\rceilindices giveS1≥\(T/2\)​ηTS\_\{1\}\\geq\(T/2\)\\eta\_\{T\}\. On each nonempty dyadic blockT/2j\+1<t≤T/2jT/2^\{j\+1\}<t\\leq T/2^\{j\},

ℓT/ℓt≤2​\(j\+2\),∑T/2j\+1<t≤T/2jt−a≤2​Tβ​2−β​j\.\\ell\_\{T\}/\\ell\_\{t\}\\leq 2\(j\+2\),\\qquad\\sum\_\{T/2^\{j\+1\}<t\\leq T/2^\{j\}\}t^\{\-a\}\\leq 2T^\{\\beta\}2^\{\-\\beta j\}\.Summation givesS1≤8​Jβ​c​Tβ/ℓT2S\_\{1\}\\leq 8J\_\{\\beta\}cT^\{\\beta\}/\\ell\_\{T\}^\{2\}and hence \([37](https://arxiv.org/html/2610.33381#A9.E37)\)\.

Split the capped sums at⌊T/2⌋\\lfloor T/2\\rfloor\. On the early half,U/\(1\+St\)≤4​HβU/\(1\+S\_\{t\}\)\\leq 4H\_\{\\beta\}, so its bias, variance and range contributions are at most

4​Hβ​cℓ1,32​Hβ​\(1\+2/β\)​c2ℓ14,64​Hβ​c2ℓ14\.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\}\}\.On the late half,t≥T/2t\\geq T/2andℓT/ℓt≤2\\ell\_\{T\}/\\ell\_\{t\}\\leq 2imply

ηtVt≤64cT−3β/2/ℓT2,ηt2λt2≤512c2T−β/ℓT4,Bt≤4T−β\.\\eta\_\{t\}V\_\{t\}\\leq 64cT^\{\-3\\beta/2\}/\\ell\_\{T\}^\{2\},\\qquad\\eta\_\{t\}^\{2\}\\lambda\_\{t\}^\{2\}\\leq 512c^\{2\}T^\{\-\\beta\}/\\ell\_\{T\}^\{4\},\\qquad B\_\{t\}\\leq 4T^\{\-\\beta\}\.Sinceηt=St−St\+1\\eta\_\{t\}=S\_\{t\}\-S\_\{t\+1\}, comparing the sums with the corresponding integrals yields

∑tηt1\+St≤log⁡U,∑tηt1\+St≤2​\(U−1\)\.\\sum\_\{t\}\\frac\{\\eta\_\{t\}\}\{1\+S\_\{t\}\}\\leq\\log U,\\qquad\\sum\_\{t\}\\frac\{\\eta\_\{t\}\}\{\\sqrt\{1\+S\_\{t\}\}\}\\leq 2\(\\sqrt\{U\}\-1\)\.\(40\)Consequently the late bias and range are bounded by

8​T−β​U​\(U−1\)≤8​Hβ​c/ℓT2,512​U​c2​T−β/ℓT4≤1024​Hβ​c2/ℓ14\.8T^\{\-\\beta\}\\sqrt\{U\}\(\\sqrt\{U\}\-1\)\\leq 8H\_\{\\beta\}c/\\ell\_\{T\}^\{2\},\\qquad 512Uc^\{2\}T^\{\-\\beta\}/\\ell\_\{T\}^\{4\}\\leq 1024H\_\{\\beta\}c^\{2\}/\\ell\_\{1\}^\{4\}\.For the late variance, useU​log⁡U≤S1​\(1\+log⁡U\)U\\log U\\leq S\_\{1\}\(1\+\\log U\), valid also whenS1≤1S\_\{1\}\\leq 1, andlog⁡U≤Hβ​ℓT\\log U\\leq H\_\{\\beta\}\\ell\_\{T\}to obtain

∑t\>T/2𝖰t​Vt≤64cT−3β/2ℓT2​U​log⁡U≤128Hβ2c2T−β/2ℓT3\.\\sum\_\{t\>T/2\}\\mathsf\{Q\}\_\{t\}V\_\{t\}\\leq\\frac\{64cT^\{\-3\\beta/2\}\}\{\\ell\_\{T\}^\{2\}\}U\\log U\\leq\\frac\{128H\_\{\\beta\}^\{2\}c^\{2\}T^\{\-\\beta/2\}\}\{\\ell\_\{T\}^\{3\}\}\.HereU≤1\+Hβ​TβU\\leq 1\+H\_\{\\beta\}T^\{\\beta\}gives the logarithmic bound\. Adding the early contributions proves \([39](https://arxiv.org/html/2610.33381#A9.E39)\) withK=220​Hβ4K=2^\{20\}H\_\{\\beta\}^\{4\}\.■\\blacksquare

### I\.2A Radius Event for All Times

Usec=cpc=c\_\{p\}and fixδ∈\(0,1\)\\delta\\in\(0,1\); the schedule does not depend onδ\\delta\. Writeh=log⁡\(100/δ\)h=\\log\(100/\\delta\)andιT=ιT​\(δ\)=log⁡\(100​T2/δ\)\\iota\_\{T\}=\\iota\_\{T\}\(\\delta\)=\\log\(100T^\{2\}/\\delta\); thusιT≥h\>2\\iota\_\{T\}\\geq h\>2\. Apply Lemma[13](https://arxiv.org/html/2610.33381#Thmtheorem13)conditionally at every step, withμt=∇f​\(xt\)\\mu\_\{t\}=\\nabla f\(x\_\{t\}\), and write

clip⁡\(gt,λt\)=Ats​μt\+dt,dt=εt\+ut,𝔼t−1​ut=0\.\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\)=A\_\{t\}^\{\\rm s\}\\mu\_\{t\}\+d\_\{t\},\\quad d\_\{t\}=\\varepsilon\_\{t\}\+u\_\{t\},\\quad\\mathbb\{E\}\_\{t\-1\}u\_\{t\}=0\.The following bounds hold globally:0≤Ats≤10\\leq A\_\{t\}^\{\\rm s\}\\leq 1,∥εt∥≤Bt\\lVert\\varepsilon\_\{t\}\\rVert\\leq B\_\{t\},𝔼t−1​∥ut∥2≤Vt\\mathbb\{E\}\_\{t\-1\}\\lVert u\_\{t\}\\rVert^\{2\}\\leq V\_\{t\},∥ut∥≤2​λt\\lVert u\_\{t\}\\rVert\\leq 2\\lambda\_\{t\},∥dt∥≤3​λt\\lVert d\_\{t\}\\rVert\\leq 3\\lambda\_\{t\}, and𝔼t−1​∥dt∥2≤2​Vt\\mathbb\{E\}\_\{t\-1\}\\lVert d\_\{t\}\\rVert^\{2\}\\leq 2V\_\{t\}\.

Letrt=∥xt−x⋆∥r\_\{t\}=\\lVert x\_\{t\}\-x^\{\\star\}\\rVertandGt=f⁡\(xt\)−f⋆G\_\{t\}=f\(x\_\{t\}\)\-f^\{\\star\}\. Sinceηt​Ats≤1/2\\eta\_\{t\}A\_\{t\}^\{\\rm s\}\\leq 1/2, expansion and∥μt∥2≤2​Gt\\lVert\\mu\_\{t\}\\rVert^\{2\}\\leq 2G\_\{t\},⟨μt,xt−x⋆⟩≥Gt\\langle\\mu\_\{t\},x\_\{t\}\-x^\{\\star\}\\rangle\\geq G\_\{t\}give

rt\+12≤rt2−2​ηt​⟨dt,xt−x⋆⟩\+2​ηt2​∥dt∥2\.r\_\{t\+1\}^\{2\}\\leq r\_\{t\}^\{2\}\-2\\eta\_\{t\}\\langle d\_\{t\},x\_\{t\}\-x^\{\\star\}\\rangle\+2\\eta\_\{t\}^\{2\}\\lVert d\_\{t\}\\rVert^\{2\}\.The remaining term withμt\\mu\_\{t\}is at most2​ηt​Ats​\(2​ηt​Ats−1\)​Gt≤02\\eta\_\{t\}A\_\{t\}^\{\\rm s\}\(2\\eta\_\{t\}A\_\{t\}^\{\\rm s\}\-1\)G\_\{t\}\\leq 0, as0≤ηt​Ats≤1/20\\leq\\eta\_\{t\}A\_\{t\}^\{\\rm s\}\\leq 1/2\.

Apply Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)to this recursion withPt−1=rt2P\_\{t\-1\}=r\_\{t\}^\{2\},p0=1p\_\{0\}=1,at=2​ηt2a\_\{t\}=2\\eta\_\{t\}^\{2\},st=2​ηts\_\{t\}=2\\eta\_\{t\}, andwt=−2​ηt​\(xt−x⋆\)w\_\{t\}=\-2\\eta\_\{t\}\(x\_\{t\}\-x^\{\\star\}\), using confidence parameterhhandJt≡1J\_\{t\}\\equiv 1\(no localization indicator\)\. The error bounds above and \([38](https://arxiv.org/html/2610.33381#A9.E38)\), usingℓ1\>1\\ell\_\{1\}\>1, give

C≤1\+650​K​c2​h,D≤2​K​c\+6​K​c​h\+32​c​h\.C\\leq 1\+650Kc^\{2\}h,\\qquad D\\leq 2Kc\+6\\sqrt\{K\}c\\sqrt\{h\}\+32ch\.SinceK≥1K\\geq 1,h\>2h\>2andK​c=1/1000Kc=1/1000,C\+D≤1\+66​K​c​h<h\\sqrt\{C\}\+D\\leq 1\+66Kch<h\. Hence there is an eventℛδ\\mathcal\{R\}\_\{\\delta\}, withℙ⁡\(ℛδ\)≥1−e−h\\mathbb\{P\}\(\\mathcal\{R\}\_\{\\delta\}\)\\geq 1\-e^\{\-h\}, on which

rt≤h,Gt≤h2/2for every​t≥1\.r\_\{t\}\\leq h,\\qquad G\_\{t\}\\leq h^\{2\}/2\\qquad\\hbox\{for every \}t\\geq 1\.\(41\)The gap bound uses smoothness at the minimizer\.

### I\.3A Potential on a Suffix of the Trajectory

Setk=⌈h1/b⌉k=\\lceil h^\{1/b\}\\rceiland split the analysis of the original recursion at timekk\. Fort≥kt\\geq k,λt≥4​h\\lambda\_\{t\}\\geq 4h, so \([33](https://arxiv.org/html/2610.33381#A9.E33)\) holds wheneverrt≤2​hr\_\{t\}\\leq 2h, since∥∇f​\(xt\)∥≤rt≤λt/2\\lVert\\nabla f\(x\_\{t\}\)\\rVert\\leq r\_\{t\}\\leq\\lambda\_\{t\}/2\.

Fix a deterministicT≥2​kT\\geq 2k\. Apply Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11), withζ=1\\zeta=1, to the updatesk,…,Tk,\\ldots,T\. KeepSt=∑s=tTηsS\_\{t\}=\\sum\_\{s=t\}^\{T\}\\eta\_\{s\}, and setUt=1\+StU\_\{t\}=1\+S\_\{t\},W=UkW=U\_\{k\},Uk−1=UkU\_\{k\-1\}=U\_\{k\}, and write𝒜m,ℋm\\mathcal\{A\}\_\{m\},\\mathcal\{H\}\_\{m\}for the quantitiesAm,HmA\_\{m\},H\_\{m\}of Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11)for these updates\. Start its analysis recursions atzk−1=zk=x⋆z\_\{k\-1\}=z\_\{k\}=x^\{\\star\}and𝒜k−1=0\\mathcal\{A\}\_\{k\-1\}=0, withℋk−1=rk2/2\\mathcal\{H\}\_\{k\-1\}=r\_\{k\}^\{2\}/2\. Write

𝖰t\(k\)=W​ηt2Ut,wt=W​ηtUt−1​\(zt−1−xt\),ℋt=W2​Ut​∥zt−xt\+1∥2\.\\mathsf\{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\\mathcal\{H\}\_\{t\}=\\frac\{W\}\{2U\_\{t\}\}\\lVert z\_\{t\}\-x\_\{t\+1\}\\rVert^\{2\}\.The proof of Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11)is pathwise, so here its initial distance term isrk2/2r\_\{k\}^\{2\}/2, also whenxkx\_\{k\}is random\. Its inequality for the partial sums is

W​𝒜m\+ℋm≤12​rk2\+2​∑t=km𝖰t\(k\)​∥et∥2\+∑t=km⟨et,wt⟩\.W\\mathcal\{A\}\_\{m\}\+\\mathcal\{H\}\_\{m\}\\leq\\tfrac\{1\}\{2\}r\_\{k\}^\{2\}\+2\\sum\_\{t=k\}^\{m\}\\mathsf\{Q\}\_\{t\}^\{\(k\)\}\\lVert e\_\{t\}\\rVert^\{2\}\+\\sum\_\{t=k\}^\{m\}\\langle e\_\{t\},w\_\{t\}\\rangle\.\(42\)The denominator of𝖰t\(k\)\\mathsf\{Q\}\_\{t\}^\{\(k\)\}agrees with that of𝖰t\\mathsf\{Q\}\_\{t\}in \([36](https://arxiv.org/html/2610.33381#A9.E36)\), and its numerator is smaller\. Thus𝖰t\(k\)≤𝖰t\\mathsf\{Q\}\_\{t\}^\{\(k\)\}\\leq\\mathsf\{Q\}\_\{t\}, so all three budgets \([39](https://arxiv.org/html/2610.33381#A9.E39)\) apply on the suffix\.

Apply Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)with the predictable indicatorsJt=𝟏\{rs≤2hfork≤s≤t\}J\_\{t\}=\\mathbf\{1\}\_\{\\\{r\_\{s\}\\leq 2h\\text\{ for \}k\\leq s\\leq t\\\}\}, with initial eventrk≤hr\_\{k\}\\leq handp0=h2/2p\_\{0\}=h^\{2\}/2\. Set

Pm=W​𝒜m\+ℋm,at=2​𝖰t\(k\),st=2​𝖰t\(k\)\.P\_\{m\}=W\\mathcal\{A\}\_\{m\}\+\\mathcal\{H\}\_\{m\},\\qquad a\_\{t\}=2\\mathsf\{Q\}\_\{t\}^\{\(k\)\},\\qquad s\_\{t\}=\\sqrt\{2\\mathsf\{Q\}\_\{t\}^\{\(k\)\}\}\.Indeed‖wt‖2≤2​𝖰t\(k\)​ℋt−1≤st2​Pt−1\\\|w\_\{t\}\\\|^\{2\}\\leq 2\\mathsf\{Q\}\_\{t\}^\{\(k\)\}\\mathcal\{H\}\_\{t\-1\}\\leq s\_\{t\}^\{2\}P\_\{t\-1\}, includingt=kt=k\. With exponentq=ιTq=\\iota\_\{T\}, the capped budgets andℓ1\>1\\ell\_\{1\}\>1giveC≤h2/2\+17​K​c2​qC\\leq h^\{2\}/2\+17Kc^\{2\}qandD≤11​K​c​qD\\leq 11Kcq\. HenceC\+D≤\(1/2\+16​K​c\)​q<q\\sqrt\{C\}\+D\\leq\(1/\\sqrt\{2\}\+16Kc\)q<q\. Except on an unconditional event of probabilitye−ιTe^\{\-\\iota\_\{T\}\}, the lemma therefore gives

W​𝒜m\+ℋm≤ιT2\(k≤m≤T\)W\\mathcal\{A\}\_\{m\}\+\\mathcal\{H\}\_\{m\}\\leq\\iota\_\{T\}^\{2\}\\qquad\(k\\leq m\\leq T\)onℛδ\\mathcal\{R\}\_\{\\delta\}, where the initial event holds and every localization indicator equals one\. Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)allows a random initial state, so the concentration bound holds unconditionally before the intersection withℛδ\\mathcal\{R\}\_\{\\delta\}\. Intersecting these concentration events over deterministicT≥2​kT\\geq 2kdefines𝒫δ\\mathcal\{P\}\_\{\\delta\}with total failure at most∑T≥2​ke−ιT\\sum\_\{T\\geq 2k\}e^\{\-\\iota\_\{T\}\}\.

### I\.4Direct Last\-Iterate Control

Onℛδ∩𝒫δ\\mathcal\{R\}\_\{\\delta\}\\cap\\mathcal\{P\}\_\{\\delta\}, for everyT≥2​kT\\geq 2k, the full endpoint estimate \([25](https://arxiv.org/html/2610.33381#A4.E25)\) gives

GT\+1≤2​\(W​𝒜T\+ℋT\)W≤2​ιT2W≤4cp​T−β​ℓT2​ιT2≤4cp​T−β​ιT4\.\\begin\{split\}G\_\{T\+1\}&\\leq\\frac\{2\(W\\mathcal\{A\}\_\{T\}\+\\mathcal\{H\}\_\{T\}\)\}\{W\}\\leq\\frac\{2\\iota\_\{T\}^\{2\}\}\{W\}\\\\ &\\leq\\frac\{4\}\{c\_\{p\}\}T^\{\-\\beta\}\\ell\_\{T\}^\{2\}\\iota\_\{T\}^\{2\}\\leq\\frac\{4\}\{c\_\{p\}\}T^\{\-\\beta\}\\iota\_\{T\}^\{4\}\.\\end\{split\}Indeed, the suffix contains the last half of the updates, soW≥∑t=kTηt≥\(T/2\)​ηT=\(cp/2\)​Tβ/ℓT2W\\geq\\sum\_\{t=k\}^\{T\}\\eta\_\{t\}\\geq\(T/2\)\\eta\_\{T\}=\(c\_\{p\}/2\)T^\{\\beta\}/\\ell\_\{T\}^\{2\}\. For1≤T<2​k1\\leq T<2k, usek≤2​h1/bk\\leq 2h^\{1/b\},0<β≤2/50<\\beta\\leq 2/5andβ/b=p−1\\beta/b=p\-1\. Onℛδ\\mathcal\{R\}\_\{\\delta\},

Tβ​GT\+1≤12​h2​\(4​h1/b\)β≤hp\+1≤h3≤ιT4\.T^\{\\beta\}G\_\{T\+1\}\\leq\\tfrac\{1\}\{2\}h^\{2\}\(4h^\{1/b\}\)^\{\\beta\}\\leq h^\{p\+1\}\\leq h^\{3\}\\leq\\iota\_\{T\}^\{4\}\.Since4/cp≥14/c\_\{p\}\\geq 1, the same rate thus covers the early times as well\. The total failure probability is at most

e−h\+∑T≥2​ke−ιT≤δ100​\(1\+∑T≥1T−2\)<δ\.e^\{\-h\}\+\\sum\_\{T\\geq 2k\}e^\{\-\\iota\_\{T\}\}\\leq\\frac\{\\delta\}\{100\}\\left\(1\+\\sum\_\{T\\geq 1\}T^\{\-2\}\\right\)<\\delta\.

### I\.5Rescaling to the Original Parameters

ForL,R\>0L,R\>0andσ≥0\\sigma\\geq 0, putQ=max⁡\{L​R,σ\}Q=\\max\\\{LR,\\sigma\\\}and use the normalized coordinatey=\(x−x1\)/Ry=\(x\-x\_\{1\}\)/Rwith objective

F⁡\(y\)=f⁡\(x1\+R​y\)−f⋆R​Q\.F\(y\)=\\frac\{f\(x\_\{1\}\+Ry\)\-f^\{\\star\}\}\{RQ\}\.Its minimizer is within distance one of zero, its smoothness isL​R/Q≤1LR/Q\\leq 1, and the normalized oracle isg/Qg/Q, with conditional centralppth moment at most\(σ/Q\)p≤1\(\\sigma/Q\)^\{p\}\\leq 1\. Applying the normalized theorem with stepcp​t−a/ℓt2c\_\{p\}t^\{\-a\}/\\ell\_\{t\}^\{2\}and threshold4​tb4t^\{b\}gives, after multiplying coordinates byRR, exactly \([5](https://arxiv.org/html/2610.33381#S4.E5)\)\. Multiplying the objective bound byR​QRQyields \([6](https://arxiv.org/html/2610.33381#S4.E6)\), and \([41](https://arxiv.org/html/2610.33381#A9.E41)\) becomes∥xt−x⋆∥2≤R2​\[log⁡\(100/δ\)\]2\\lVert x\_\{t\}\-x^\{\\star\}\\rVert^\{2\}\\leq R^\{2\}\[\\log\(100/\\delta\)\]^\{2\}\. This scaling also coversσ=0\\sigma=0sinceQ=L​R\>0Q=LR\>0\.

### I\.6Proof of Theorem[5](https://arxiv.org/html/2610.33381#Thmtheorem5)

The proof reuses the radius event and the suffix potential of Theorem[2](https://arxiv.org/html/2610.33381#Thmtheorem2), with the fixed time as the analysis horizon\. Forr\>βpr\>\\beta\_\{p\}, the range of the late clipping errors, weighted by the potential, grows with the horizon, so Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)does not apply directly\. We truncate these errors at deterministic levels that depend onTTandδ\\delta, apply the lemma on the event that no truncation occurs, and bound the probability of truncation through theppth moment\. The factorδu\\delta^\{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\}\.

We keep the normalized setting and the constants \([35](https://arxiv.org/html/2610.33381#A9.E35)\), fixr∈\(βp,αp\]r\\in\(\\beta\_\{p\},\\alpha\_\{p\}\]andδ∈\(0,1\)\\delta\\in\(0,1\), and writeh=log⁡\(100/δ\)h=\\log\(100/\\delta\)andιT=log⁡\(100​T2/δ\)\\iota\_\{T\}=\\log\(100T^\{2\}/\\delta\)\. Put

ar=1−r,br=rp−1,dr=ar−br=pp−1​\(αp−r\)≥0,\\displaystyle 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\)\\geq 0,κ=3​p−1p−1,E=κ⁡\(r−βp\)\>0\.\\displaystyle\\kappa=\\frac\{3p\-1\}\{p\-1\},\\qquad E=\\kappa\(r\-\\beta\_\{p\}\)\>0\.Sinceκ​βp=2\\kappa\\beta\_\{p\}=2, alsoE=2​br\+r−2​arE=2b\_\{r\}\+r\-2a\_\{r\}, and

pp−1​E\+κ​dr=p​κp−1​\(αp−βp\)=1\.\\frac\{p\}\{p\-1\}E\+\\kappa d\_\{r\}=\\frac\{p\\kappa\}\{p\-1\}\(\\alpha\_\{p\}\-\\beta\_\{p\}\)=1\.\(43\)Foru,w≥0u,w\\geq 0let

Ξ⁡\(u,w\)=p​up−1\+2​w\+drE​\(κ​u\+2​w\)\.\\Xi\(u,w\)=\\frac\{pu\}\{p\-1\}\+2w\+\\frac\{d\_\{r\}\}\{E\}\(\\kappa u\+2w\)\.We prove the following claim: ifΞ⁡\(u,w\)≥1\\Xi\(u,w\)\\geq 1, then the schedule \([10](https://arxiv.org/html/2610.33381#S5.E10)\) with thisuusatisfies, for every deterministicT≥1T\\geq 1,

ℙ\{f\(xT\+1\)−f⋆≤DpT−rδ−\(u\+2​w\)ιT4\}≥1−δ\.\\mathbb\{P\}\\bigl\\\{f\(x\_\{T\+1\}\)\-f^\{\\star\}\\leq D\_\{p\}T^\{\-r\}\\delta^\{\-\(u\+2w\)\}\\iota\_\{T\}^\{4\}\\bigr\\\}\\geq 1\-\\delta\.\(44\)The parameterwwenters only the analysis\. Foru=E=cin​\(r\)u=E=c\_\{\\rm in\}\(r\)andw=0w=0, \([43](https://arxiv.org/html/2610.33381#A9.E43)\) givesΞ=1\\Xi=1\. Foru=0u=0and2​w=E/\(E\+dr\)2w=E/\(E\+d\_\{r\}\),Ξ=2​w​\(1\+dr/E\)=1\\Xi=2w\(1\+d\_\{r\}/E\)=1, and

EE\+dr=\(3​p−1\)​r−2​\(p−1\)\(2​p−1\)​r−\(p−1\)=cfree​\(r\)\.\\frac\{E\}\{E\+d\_\{r\}\}=\\frac\{\(3p\-1\)r\-2\(p\-1\)\}\{\(2p\-1\)r\-\(p\-1\)\}=c\_\{\\rm free\}\(r\)\.Thus the claim proves Theorem[5](https://arxiv.org/html/2610.33381#Thmtheorem5)in the normalized setting, and the rescaling of Appendix[I\.5](https://arxiv.org/html/2610.33381#A9.SS5)multipliesηt\\eta\_\{t\}byR/QR/Q,λt\\lambda\_\{t\}byQQ, and the bound byR​QRQ\.

###### Lemma 21\(Budgets for the fixed\-time schedules\)\.

Letu≥0u\\geq 0,0<c≤10<c\\leq 1, andδ∈\(0,1\)\\delta\\in\(0,1\), and letηt=c​δu​t−ar/ℓt2\\eta\_\{t\}=c\\,\\delta^\{u\}t^\{\-a\_\{r\}\}/\\ell\_\{t\}^\{2\}andλt=4​max⁡\{1,δu/\(p−1\)​tbr\}\\lambda\_\{t\}=4\\max\\\{1,\\delta^\{u/\(p\-1\)\}t^\{b\_\{r\}\}\\\}, withBtB\_\{t\}andVtV\_\{t\}as in \([33](https://arxiv.org/html/2610.33381#A9.E33)\)\. Then \([38](https://arxiv.org/html/2610.33381#A9.E38)\) holds\. FixT≥2T\\geq 2and an integer1≤k≤T/21\\leq k\\leq T/2such thatλt=4​δu/\(p−1\)​tbr\\lambda\_\{t\}=4\\delta^\{u/\(p\-1\)\}t^\{b\_\{r\}\}for allt≥kt\\geq k, and putSt=∑s=tTηsS\_\{t\}=\\sum\_\{s=t\}^\{T\}\\eta\_\{s\},W=1\+SkW=1\+S\_\{k\}, and𝖰t=W​ηt2/\(1\+St\)\\mathsf\{Q\}\_\{t\}=W\\eta\_\{t\}^\{2\}/\(1\+S\_\{t\}\)\. Then

c2​δu​TrℓT2≤Sk≤S1≤Hβ​c​δu​TrℓT2,\\displaystyle\\frac\{c\}\{2\}\\,\\frac\{\\delta^\{u\}T^\{r\}\}\{\\ell\_\{T\}^\{2\}\}\\leq S\_\{k\}\\leq S\_\{1\}\\leq H\_\{\\beta\}c\\,\\frac\{\\delta^\{u\}T^\{r\}\}\{\\ell\_\{T\}^\{2\}\},\(45\)∑t=kT𝖰t​Bt≤K​c2​ℓ1,∑t=kT𝖰t​Vt≤K​c2ℓ13,maxk≤t≤T/2⁡𝖰t​λt2≤K​c2ℓ14,\\displaystyle\\sum\_\{t=k\}^\{T\}\\sqrt\{\\mathsf\{Q\}\_\{t\}\}B\_\{t\}\\leq\\frac\{Kc\}\{2\\ell\_\{1\}\},\\qquad\\sum\_\{t=k\}^\{T\}\\mathsf\{Q\}\_\{t\}V\_\{t\}\\leq\\frac\{Kc^\{2\}\}\{\\ell\_\{1\}^\{3\}\},\\qquad\\max\_\{k\\leq t\\leq T/2\}\\mathsf\{Q\}\_\{t\}\\lambda\_\{t\}^\{2\}\\leq\\frac\{Kc^\{2\}\}\{\\ell\_\{1\}^\{4\}\},\(46\)∑T/2<t≤T𝖰t​Vt≤128​Hβ2​c2ℓT3​δp​u/\(p−1\)​T−dr\.\\displaystyle\\sum\_\{T/2<t\\leq T\}\\mathsf\{Q\}\_\{t\}V\_\{t\}\\leq\\frac\{128H\_\{\\beta\}^\{2\}c^\{2\}\}\{\\ell\_\{T\}^\{3\}\}\\,\\delta^\{pu/\(p\-1\)\}T^\{\-d\_\{r\}\}\.\(47\)

ProofIn both branches ofλt\\lambda\_\{t\},Bt≤2​δ−u​t−rB\_\{t\}\\leq 2\\delta^\{\-u\}t^\{\-r\}andVt≤8​max⁡\{1,δ\(2−p\)​u/\(p−1\)​t\(2−p\)​br\}V\_\{t\}\\leq 8\\max\\\{1,\\delta^\{\(2\-p\)u/\(p\-1\)\}t^\{\(2\-p\)b\_\{r\}\}\\\}\. Sincear\+r=1a\_\{r\}\+r=1,dr≥0d\_\{r\}\\geq 0,2​ar≥12a\_\{r\}\\geq 1, and2​ar−\(2−p\)​br=1\+dr2a\_\{r\}\-\(2\-p\)b\_\{r\}=1\+d\_\{r\},

ηt​Bt≤2​ct​ℓt2,ηt2​Vt≤8​c2t​ℓt4,ηt​λt≤4​cℓ12,\\eta\_\{t\}B\_\{t\}\\leq\\frac\{2c\}\{t\\ell\_\{t\}^\{2\}\},\\qquad\\eta\_\{t\}^\{2\}V\_\{t\}\\leq\\frac\{8c^\{2\}\}\{t\\ell\_\{t\}^\{4\}\},\\qquad\\eta\_\{t\}\\lambda\_\{t\}\\leq\\frac\{4c\}\{\\ell\_\{1\}^\{2\}\},and integral comparison, as in Lemma[20](https://arxiv.org/html/2610.33381#Thmtheorem20), gives \([38](https://arxiv.org/html/2610.33381#A9.E38)\)\. The proof of \([37](https://arxiv.org/html/2610.33381#A9.E37)\) gives \([45](https://arxiv.org/html/2610.33381#A9.E45)\):Sk≥\(T/2\)​ηTS\_\{k\}\\geq\(T/2\)\\eta\_\{T\}, and every dyadic block has∑t−ar≤2​Tr​2−r​j≤2​Tr​2−βp​j\\sum t^\{\-a\_\{r\}\}\\leq 2T^\{r\}2^\{\-rj\}\\leq 2T^\{r\}2^\{\-\\beta\_\{p\}j\}\. As there,W/\(1\+St\)≤4​HβW/\(1\+S\_\{t\}\)\\leq 4H\_\{\\beta\}fort≤T/2t\\leq T/2, so the global budgets bound the early parts of the bias and variance sums in \([46](https://arxiv.org/html/2610.33381#A9.E46)\) by4​Hβ​c/ℓ14\\sqrt\{H\_\{\\beta\}\}c/\\ell\_\{1\}and64​Hβ​c2/ℓ1464H\_\{\\beta\}c^\{2\}/\\ell\_\{1\}^\{4\}, and the early range by64​Hβ​c2/ℓ1464H\_\{\\beta\}c^\{2\}/\\ell\_\{1\}^\{4\}\. ForT/2<t≤TT/2<t\\leq T, the branch assumption,ℓT/ℓt≤2\\ell\_\{T\}/\\ell\_\{t\}\\leq 2, and−ar\+\(2−p\)​br=−r−dr\-a\_\{r\}\+\(2\-p\)b\_\{r\}=\-r\-d\_\{r\}give

Bt≤4​δ−u​T−r,ηt​Vt≤64​c​δu/\(p−1\)​T−r−drℓT2\.B\_\{t\}\\leq 4\\delta^\{\-u\}T^\{\-r\},\\qquad\\eta\_\{t\}V\_\{t\}\\leq\\frac\{64c\\,\\delta^\{u/\(p\-1\)\}T^\{\-r\-d\_\{r\}\}\}\{\\ell\_\{T\}^\{2\}\}\.By \([40](https://arxiv.org/html/2610.33381#A9.E40)\), withWWin place ofUUand the sums starting atkk, the late bias sum is at most8​δ−u​T−r​Sk≤8​Hβ​c/ℓT28\\delta^\{\-u\}T^\{\-r\}S\_\{k\}\\leq 8H\_\{\\beta\}c/\\ell\_\{T\}^\{2\}\. For the late variance,W​log⁡W≤Sk​\(1\+log⁡W\)W\\log W\\leq S\_\{k\}\(1\+\\log W\)and1\+log⁡W≤Hβ​ℓT1\+\\log W\\leq H\_\{\\beta\}\\ell\_\{T\}give

∑T/2<t≤T𝖰t​Vt≤64​c​δu/\(p−1\)​T−r−drℓT2​W​log⁡W≤64​Hβ2​c2ℓT3​δp​u/\(p−1\)​T−dr\.\\sum\_\{T/2<t\\leq T\}\\mathsf\{Q\}\_\{t\}V\_\{t\}\\leq\\frac\{64c\\,\\delta^\{u/\(p\-1\)\}T^\{\-r\-d\_\{r\}\}\}\{\\ell\_\{T\}^\{2\}\}\\,W\\log W\\leq\\frac\{64H\_\{\\beta\}^\{2\}c^\{2\}\}\{\\ell\_\{T\}^\{3\}\}\\,\\delta^\{pu/\(p\-1\)\}T^\{\-d\_\{r\}\}\.Adding both halves and usingK=220​Hβ4K=2^\{20\}H\_\{\\beta\}^\{4\}proves \([46](https://arxiv.org/html/2610.33381#A9.E46)\) and \([47](https://arxiv.org/html/2610.33381#A9.E47)\)\.■\\blacksquare

*Radius and early times\.*Usec=cpc=c\_\{p\}\. Sinceλt≥4\\lambda\_\{t\}\\geq 4andηt≤cp\\eta\_\{t\}\\leq c\_\{p\}, the argument of Appendix[I\.2](https://arxiv.org/html/2610.33381#A9.SS2), with the global budgets of Lemma[21](https://arxiv.org/html/2610.33381#Thmtheorem21), gives an eventℛδ\\mathcal\{R\}\_\{\\delta\}withℙ⁡\(ℛδc\)≤δ/100\\mathbb\{P\}\(\\mathcal\{R\}\_\{\\delta\}^\{c\}\)\\leq\\delta/100on which∥xt−x⋆∥≤h\\lVert x\_\{t\}\-x^\{\\star\}\\rVert\\leq handGt≤h2/2G\_\{t\}\\leq h^\{2\}/2for allt≥1t\\geq 1\. Letk=⌈δ−u/rh1/br⌉k=\\lceil\\delta^\{\-u/r\}h^\{1/b\_\{r\}\}\\rceil\. Sincebr/r=1/\(p−1\)b\_\{r\}/r=1/\(p\-1\), everyt≥kt\\geq khasδu/\(p−1\)​tbr≥h≥1\\delta^\{u/\(p\-1\)\}t^\{b\_\{r\}\}\\geq h\\geq 1, henceλt=4​δu/\(p−1\)​tbr≥4​h\\lambda\_\{t\}=4\\delta^\{u/\(p\-1\)\}t^\{b\_\{r\}\}\\geq 4h\. IfT<2​kT<2k, thenT<4δ−u/rh1/brT<4\\delta^\{\-u/r\}h^\{1/b\_\{r\}\}, and onℛδ\\mathcal\{R\}\_\{\\delta\}, usingr≤1/2r\\leq 1/2,r/br=p−1r/b\_\{r\}=p\-1, andp≤2p\\leq 2,

δu​Tr​GT\+1≤12​4r​hp\+1≤h3≤ιT4,\\delta^\{u\}T^\{r\}G\_\{T\+1\}\\leq\\tfrac\{1\}\{2\}\\,4^\{r\}h^\{p\+1\}\\leq h^\{3\}\\leq\\iota\_\{T\}^\{4\},which proves \([44](https://arxiv.org/html/2610.33381#A9.E44)\), sinceDp≥1D\_\{p\}\\geq 1andδ−2​w≥1\\delta^\{\-2w\}\\geq 1\.

*Truncation\.*Fix a deterministicT≥2​kT\\geq 2k, and apply Lemma[11](https://arxiv.org/html/2610.33381#Thmtheorem11)withζ=1\\zeta=1to the updatesk,…,Tk,\\ldots,Tas in Appendix[I\.3](https://arxiv.org/html/2610.33381#A9.SS3)\. This givesPm=W​𝒜m\+ℋm≥0P\_\{m\}=W\\mathcal\{A\}\_\{m\}\+\\mathcal\{H\}\_\{m\}\\geq 0withW=1\+SkW=1\+S\_\{k\}, the recursion \([42](https://arxiv.org/html/2610.33381#A9.E42)\), and∥wt∥≤2​𝖰t​Pt−1\\lVert w\_\{t\}\\rVert\\leq\\sqrt\{2\\mathsf\{Q\}\_\{t\}\}\\sqrt\{P\_\{t\-1\}\}, where𝖰t=𝖰t\(k\)\\mathsf\{Q\}\_\{t\}=\\mathsf\{Q\}\_\{t\}^\{\(k\)\}is the quantity of Lemma[21](https://arxiv.org/html/2610.33381#Thmtheorem21)\. LetJtJ\_\{t\}indicate that∥xs−x⋆∥≤2​h\\lVert x\_\{s\}\-x^\{\\star\}\\rVert\\leq 2hfork≤s≤tk\\leq s\\leq t; it is predictable and nonincreasing\. OnJt=1J\_\{t\}=1,∥∇f​\(xt\)∥≤2​h≤λt/2\\lVert\\nabla f\(x\_\{t\}\)\\rVert\\leq 2h\\leq\\lambda\_\{t\}/2, so Lemma[12](https://arxiv.org/html/2610.33381#Thmtheorem12)gives \([33](https://arxiv.org/html/2610.33381#A9.E33)\) and∥et∥≤∥gt−∇f​\(xt\)∥\\lVert e\_\{t\}\\rVert\\leq\\lVert g\_\{t\}\-\\nabla f\(x\_\{t\}\)\\rVert\. SetM0=K​cp/ℓ12M\_\{0\}=\\sqrt\{K\}c\_\{p\}/\\ell\_\{1\}^\{2\}, and define deterministic levels and truncated errors by

mt=∞\(k≤t≤T/2\),mt=M0​δ−w𝖰t\(T/2<t≤T\),e^t=et𝟏\{∥et∥≤mt\}\.m\_\{t\}=\\infty\\quad\(k\\leq t\\leq T/2\),\\qquad m\_\{t\}=\\frac\{M\_\{0\}\\delta^\{\-w\}\}\{\\sqrt\{\\mathsf\{Q\}\_\{t\}\}\}\\quad\(T/2<t\\leq T\),\\qquad\\hat\{e\}\_\{t\}=e\_\{t\}\\mathbf\{1\}\_\{\\\{\\lVert e\_\{t\}\\rVert\\leq m\_\{t\}\\\}\}\.Let𝒯=\{t:mt<3​λt/2\}\\mathcal\{T\}=\\\{t:m\_\{t\}<3\\lambda\_\{t\}/2\\\}andℰT=\{Jtet=Jte^tfork≤t≤T\}\\mathcal\{E\}\_\{T\}=\\\{J\_\{t\}e\_\{t\}=J\_\{t\}\\hat\{e\}\_\{t\}\\text\{ for \}k\\leq t\\leq T\\\}\. Only times in𝒯\\mathcal\{T\}can violateℰT\\mathcal\{E\}\_\{T\}, and the conditional Markov inequality with𝔼t−1​∥gt−∇f​\(xt\)∥p≤1\\mathbb\{E\}\_\{t\-1\}\\lVert g\_\{t\}\-\\nabla f\(x\_\{t\}\)\\rVert^\{p\}\\leq 1gives

ℙ⁡\(ℰTc\)≤ΣT:=∑t∈𝒯mt−p\.\\mathbb\{P\}\(\\mathcal\{E\}\_\{T\}^\{c\}\)\\leq\\Sigma\_\{T\}:=\\sum\_\{t\\in\\mathcal\{T\}\}m\_\{t\}^\{\-p\}\.Suppose𝒯≠∅\\mathcal\{T\}\\neq\\varnothing\. Sinceδu​Tr≥δu​kr≥1\\delta^\{u\}T^\{r\}\\geq\\delta^\{u\}k^\{r\}\\geq 1andHβ​cp≤1H\_\{\\beta\}c\_\{p\}\\leq 1, \([45](https://arxiv.org/html/2610.33381#A9.E45)\) givesW≤2​δu​TrW\\leq 2\\delta^\{u\}T^\{r\}\. ForT/2<t≤TT/2<t\\leq T, alsoηt≤8​cp​δu​T−ar/ℓT2\\eta\_\{t\}\\leq 8c\_\{p\}\\delta^\{u\}T^\{\-a\_\{r\}\}/\\ell\_\{T\}^\{2\}andλt≤4​δu/\(p−1\)​Tbr\\lambda\_\{t\}\\leq 4\\delta^\{u/\(p\-1\)\}T^\{b\_\{r\}\}, so

𝖰t​λt2≤W​ηt2​λt2≤2048​cp2ℓT4​δκ​u​TE\.\\mathsf\{Q\}\_\{t\}\\lambda\_\{t\}^\{2\}\\leq W\\eta\_\{t\}^\{2\}\\lambda\_\{t\}^\{2\}\\leq\\frac\{2048c\_\{p\}^\{2\}\}\{\\ell\_\{T\}^\{4\}\}\\,\\delta^\{\\kappa u\}T^\{E\}\.A timet∈𝒯t\\in\\mathcal\{T\}hasM02​δ−2​w<94​𝖰t​λt2M\_\{0\}^\{2\}\\delta^\{\-2w\}<\\frac\{9\}\{4\}\\mathsf\{Q\}\_\{t\}\\lambda\_\{t\}^\{2\}, soK≥4608K\\geq 4608gives

TE\>δ−\(κ​u\+2​w\)\.T^\{E\}\>\\delta^\{\-\(\\kappa u\+2w\)\}\.\(48\)Fort∈𝒯t\\in\\mathcal\{T\},mt<3​λt/2m\_\{t\}<3\\lambda\_\{t\}/2and0≤2−p<10\\leq 2\-p<1givemt2−p≤34​Vtm\_\{t\}^\{2\-p\}\\leq\\frac\{3\}\{4\}V\_\{t\}, hencemt−p=δ2​w​𝖰t​mt2−p/M02≤34​δ2​w​𝖰t​Vt/M02m\_\{t\}^\{\-p\}=\\delta^\{2w\}\\mathsf\{Q\}\_\{t\}m\_\{t\}^\{2\-p\}/M\_\{0\}^\{2\}\\leq\\frac\{3\}\{4\}\\delta^\{2w\}\\mathsf\{Q\}\_\{t\}V\_\{t\}/M\_\{0\}^\{2\}\. By \([47](https://arxiv.org/html/2610.33381#A9.E47)\),dr≥0d\_\{r\}\\geq 0, and \([48](https://arxiv.org/html/2610.33381#A9.E48)\),

ΣT≤96​Hβ2​ℓ1K​δp​up−1\+2​w​T−dr≤96​Hβ2​ℓ1K​δΞ⁡\(u,w\)≤δ2\.\\Sigma\_\{T\}\\leq\\frac\{96H\_\{\\beta\}^\{2\}\\ell\_\{1\}\}\{K\}\\,\\delta^\{\\frac\{pu\}\{p\-1\}\+2w\}T^\{\-d\_\{r\}\}\\leq\\frac\{96H\_\{\\beta\}^\{2\}\\ell\_\{1\}\}\{K\}\\,\\delta^\{\\Xi\(u,w\)\}\\leq\\frac\{\\delta\}\{2\}\.If𝒯=∅\\mathcal\{T\}=\\varnothing, thenΣT=0\\Sigma\_\{T\}=0\.

*Energy bound without truncation\.*OnJt=1J\_\{t\}=1, the truncated errors satisfy

∥𝔼t−1e^t∥≤Bt\+𝟏\{t∈𝒯\}mt1−p,𝔼t−1∥e^t∥2≤Vt,\\displaystyle\\lVert\\mathbb\{E\}\_\{t\-1\}\\hat\{e\}\_\{t\}\\rVert\\leq B\_\{t\}\+\\mathbf\{1\}\_\{\\\{t\\in\\mathcal\{T\}\\\}\}m\_\{t\}^\{1\-p\},\\qquad\\mathbb\{E\}\_\{t\-1\}\\lVert\\hat\{e\}\_\{t\}\\rVert^\{2\}\\leq V\_\{t\},∥e^t∥≤min⁡\{32​λt,mt\},∥e^t−𝔼t−1​e^t∥≤2​min⁡\{λt,mt\}\.\\displaystyle\\lVert\\hat\{e\}\_\{t\}\\rVert\\leq\\min\\\{\\tfrac\{3\}\{2\}\\lambda\_\{t\},m\_\{t\}\\\},\\qquad\\lVert\\hat\{e\}\_\{t\}\-\\mathbb\{E\}\_\{t\-1\}\\hat\{e\}\_\{t\}\\rVert\\leq 2\\min\\\{\\lambda\_\{t\},m\_\{t\}\\\}\.The first bound uses∥et∥𝟏\{∥et∥\>mt\}≤∥gt−∇f\(xt\)∥pmt1−p\\lVert e\_\{t\}\\rVert\\mathbf\{1\}\_\{\\\{\\lVert e\_\{t\}\\rVert\>m\_\{t\}\\\}\}\\leq\\lVert g\_\{t\}\-\\nabla f\(x\_\{t\}\)\\rVert^\{p\}m\_\{t\}^\{1\-p\}\. For the last,e^t\+∇f​\(xt\)\\hat\{e\}\_\{t\}\+\\nabla f\(x\_\{t\}\)equalsclip⁡\(gt,λt\)\\operatorname\{clip\}\(g\_\{t\},\\lambda\_\{t\}\)or∇f​\(xt\)\\nabla f\(x\_\{t\}\), both in the ball of radiusλt\\lambda\_\{t\}, and∥e^t∥≤mt\\lVert\\hat\{e\}\_\{t\}\\rVert\\leq m\_\{t\}\. PutP~m=δ2​w​Pm\\tilde\{P\}\_\{m\}=\\delta^\{2w\}P\_\{m\}\. OnℰT∩\{Jm=1\}\\mathcal\{E\}\_\{T\}\\cap\\\{J\_\{m\}=1\\\}, the recursion \([42](https://arxiv.org/html/2610.33381#A9.E42)\) holds withe^t\\hat\{e\}\_\{t\}in place ofete\_\{t\}, so

P~m≤P~k−1\+∑t=km\(2​δ2​w​𝖰t​∥e^t∥2\+⟨e^t,δ2​w​wt⟩\),∥δ2​w​wt∥≤δw​2​𝖰t​P~t−1\.\\tilde\{P\}\_\{m\}\\leq\\tilde\{P\}\_\{k\-1\}\+\\sum\_\{t=k\}^\{m\}\\bigl\(2\\delta^\{2w\}\\mathsf\{Q\}\_\{t\}\\lVert\\hat\{e\}\_\{t\}\\rVert^\{2\}\+\\langle\\hat\{e\}\_\{t\},\\delta^\{2w\}w\_\{t\}\\rangle\\bigr\),\\qquad\\lVert\\delta^\{2w\}w\_\{t\}\\rVert\\leq\\delta^\{w\}\\sqrt\{2\\mathsf\{Q\}\_\{t\}\}\\sqrt\{\\tilde\{P\}\_\{t\-1\}\}\.Apply Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)with the eventℰT\\mathcal\{E\}\_\{T\}, the errorse^t\\hat\{e\}\_\{t\},at=2​δ2​w​𝖰ta\_\{t\}=2\\delta^\{2w\}\\mathsf\{Q\}\_\{t\},st=δw​2​𝖰ts\_\{t\}=\\delta^\{w\}\\sqrt\{2\\mathsf\{Q\}\_\{t\}\},p0=h2/2p\_\{0\}=h^\{2\}/2, and exponentq=ιTq=\\iota\_\{T\}\. Lemma[21](https://arxiv.org/html/2610.33381#Thmtheorem21),ΣT≤1/2\\Sigma\_\{T\}\\leq 1/2, and the identitiesδw​𝖰t​mt1−p=M0​mt−p\\delta^\{w\}\\sqrt\{\\mathsf\{Q\}\_\{t\}\}m\_\{t\}^\{1\-p\}=M\_\{0\}m\_\{t\}^\{\-p\}andδ2​w​𝖰t​mt2=M02\\delta^\{2w\}\\mathsf\{Q\}\_\{t\}m\_\{t\}^\{2\}=M\_\{0\}^\{2\}fort\>T/2t\>T/2give

A≤2​K​cp2ℓ13,K0≤9​K​cp22​ℓ14,B0≤2​K​cpℓ1,V0≤2​K​cp2ℓ13,J0≤2​2​K​cpℓ12\.A\\leq\\frac\{2Kc\_\{p\}^\{2\}\}\{\\ell\_\{1\}^\{3\}\},\\quad K\_\{0\}\\leq\\frac\{9Kc\_\{p\}^\{2\}\}\{2\\ell\_\{1\}^\{4\}\},\\quad B\_\{0\}\\leq\\frac\{\\sqrt\{2\}Kc\_\{p\}\}\{\\ell\_\{1\}\},\\quad V\_\{0\}\\leq\\frac\{2Kc\_\{p\}^\{2\}\}\{\\ell\_\{1\}^\{3\}\},\\quad J\_\{0\}\\leq\\frac\{2\\sqrt\{2K\}c\_\{p\}\}\{\\ell\_\{1\}^\{2\}\}\.HenceC≤h2/2\+17​K​cp2​qC\\leq h^\{2\}/2\+17Kc\_\{p\}^\{2\}qandD≤11​K​cp​qD\\leq 11Kc\_\{p\}q, soC\+D≤\(1/2\+16​K​cp\)​q<q\\sqrt\{C\}\+D\\leq\(1/\\sqrt\{2\}\+16Kc\_\{p\}\)q<q, as in Appendix[I\.3](https://arxiv.org/html/2610.33381#A9.SS3)\. Onℛδ\\mathcal\{R\}\_\{\\delta\},P~k−1≤h2/2\\tilde\{P\}\_\{k\-1\}\\leq h^\{2\}/2and everyJt=1J\_\{t\}=1\. Thus, except on probabilitye−ιT≤δ/100e^\{\-\\iota\_\{T\}\}\\leq\\delta/100, every outcome inℛδ∩ℰT\\mathcal\{R\}\_\{\\delta\}\\cap\\mathcal\{E\}\_\{T\}hasP~T≤ιT2\\tilde\{P\}\_\{T\}\\leq\\iota\_\{T\}^\{2\}\.

*Conclusion\.*Onℛδ∩ℰT∩\{P~T≤ιT2\}\\mathcal\{R\}\_\{\\delta\}\\cap\\mathcal\{E\}\_\{T\}\\cap\\\{\\tilde\{P\}\_\{T\}\\leq\\iota\_\{T\}^\{2\}\\\}, the endpoint estimate \([25](https://arxiv.org/html/2610.33381#A4.E25)\),W≥SkW\\geq S\_\{k\}, and \([45](https://arxiv.org/html/2610.33381#A9.E45)\) give

GT\+1≤2​PTW≤2​δ−2​w​ιT2\(cp/2\)​δu​Tr/ℓT2≤Dp​T−r​δ−\(u\+2​w\)​ιT4,G\_\{T\+1\}\\leq\\frac\{2P\_\{T\}\}\{W\}\\leq\\frac\{2\\delta^\{\-2w\}\\iota\_\{T\}^\{2\}\}\{\(c\_\{p\}/2\)\\delta^\{u\}T^\{r\}/\\ell\_\{T\}^\{2\}\}\\leq D\_\{p\}T^\{\-r\}\\delta^\{\-\(u\+2w\)\}\\iota\_\{T\}^\{4\},sinceℓT≤ιT\\ell\_\{T\}\\leq\\iota\_\{T\}andDp=4/cpD\_\{p\}=4/c\_\{p\}\. The three exceptional events have total probability at mostδ/100\+δ/2\+δ/100<δ\\delta/100\+\\delta/2\+\\delta/100<\\delta, which proves \([44](https://arxiv.org/html/2610.33381#A9.E44)\)\.

## Appendix JProof of the One\-Dimensional Momentum Lower Bound

We prove Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)for rules that follow the heavy\-ball recursion \([14](https://arxiv.org/html/2610.33381#S6.E14)\) under the bounds \([15](https://arxiv.org/html/2610.33381#S6.E15)\), withclip⁡\(g,0\)=0\\operatorname\{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\), and step sizes may all adapt\. For an integerN≥1N\\geq 1andk≥0k\\geq 0, put

κN,k=exp⁡\(−ρ​\(k−t0\)\+​\(1\+N\)−a\)\.\\kappa\_\{N,k\}=\\exp\\bigl\(\-\\rho\(k\-t\_\{0\}\)\_\{\+\}\(1\+N\)^\{\-a\}\\bigr\)\.
###### Proposition 22\(Necessary momentum progress budget\)\.

Fix such a rule and a failure budget0<ε<1/20<\\varepsilon<1/2\. LetN≥1N\\geq 1and letb1,…,bNb\_\{1\},\\ldots,b\_\{N\}be positive\. Suppose every admissible instance satisfies

ℙ\{f\(xt\+1\)−f⋆≤btfor all1≤t≤N\}≥1−ε\.\\mathbb\{P\}\\\{f\(x\_\{t\+1\}\)\-f^\{\\star\}\\leq b\_\{t\}\\text\{ for all \}1\\leq t\\leq N\\\}\\geq 1\-\\varepsilon\.For every4​bN<μ≤1/24b\_\{N\}<\\mu\\leq 1/2, putA=\(2μ\)−1/\(p−1\)A=\(2\\mu\)^\{\-1/\(p\-1\)\},π=μ/A\\pi=\\mu/A,st=μ\+2​bts\_\{t\}=\\mu\+\\sqrt\{2b\_\{t\}\}, andHN=H​\(1\+N\)hH\_\{N\}=H\(1\+N\)^\{h\}\. Then

1−2​ε2≤π​∑t=1N∑k=0t−1min⁡\{st,HN​A​κN,k\}\.\\frac\{1\-2\\varepsilon\}\{2\}\\leq\\pi\\sum\_\{t=1\}^\{N\}\\sum\_\{k=0\}^\{t\-1\}\\min\\\{s\_\{t\},H\_\{N\}A\\kappa\_\{N,k\}\\\}\.\(49\)

ProofUse the translated family of Appendix[H\.2](https://arxiv.org/html/2610.33381#A8.SS2), fixed before the run:

Fμ,y​\(x,Y\)=12​\(x−y\+μ\)\+2−A​Y​x,y∈\[μ,1\],Y∼Bernoulli⁡\(π\)\.F\_\{\\mu,y\}\(x;Y\)=\\tfrac\{1\}\{2\}\(x\-y\+\\mu\)\_\{\+\}^\{2\}\-AYx,\\qquad y\\in\[\\mu,1\],\\qquad Y\\sim\\operatorname\{Bernoulli\}\(\\pi\)\.The population objective gap is given by \([28](https://arxiv.org/html/2610.33381#A8.E28)\), and forx≤y−μx\\leq y\-\\muthe stochastic gradient is−A​Y\-AY\. In particular, all sample and population properties stated in the theorem hold, with𝔼​\|μ−A​Y\|p≤μp\+μ​Ap−1≤1\\mathbb\{E\}\|\\mu\-AY\|^\{p\}\\leq\\mu^\{p\}\+\\mu A^\{p\-1\}\\leq 1\. Thus these instances satisfy the assumed prefix guarantee, and the rule meets the conditions of Lemma[19](https://arxiv.org/html/2610.33381#Thmtheorem19), with the velocity as auxiliary state\. LetXtX\_\{t\}andVtV\_\{t\}be the position and velocity of its reference run, withc=1/2c=1/2\. Before stopping, letRt=−VtR\_\{t\}=\-V\_\{t\}and write

Rt\+1=βt​Rt\+Yt​at,at=min⁡\{A,λt\}∈\[0,A\],Xt\+1=Xt\+Dt,Dt=ηt​Rt\+1,R\_\{t\+1\}=\\beta\_\{t\}R\_\{t\}\+Y\_\{t\}a\_\{t\},\\quad a\_\{t\}=\\min\\\{A,\\lambda\_\{t\}\\\}\\in\[0,A\],\\quad X\_\{t\+1\}=X\_\{t\}\+D\_\{t\},\\quad D\_\{t\}=\\eta\_\{t\}R\_\{t\+1\},withX1=R1=0X\_\{1\}=R\_\{1\}=0\. SetDt=0D\_\{t\}=0after stopping\. Unrolling the recursion givesRt\+1=∑j≤t\(∏i=j\+1tβi\)​Yj​ajR\_\{t\+1\}=\\sum\_\{j\\leq t\}\\bigl\(\\prod\_\{i=j\+1\}^\{t\}\\beta\_\{i\}\\bigr\)Y\_\{j\}a\_\{j\}\. Fort≤Nt\\leq N, each indexi≥t0i\\geq t\_\{0\}in the product satisfiesβi≤1−ρ​\(1\+N\)−a≤exp⁡\(−ρ​\(1\+N\)−a\)\\beta\_\{i\}\\leq 1\-\\rho\(1\+N\)^\{\-a\}\\leq\\exp\(\-\\rho\(1\+N\)^\{\-a\}\), and at least\(t−j−t0\)\+\(t\-j\-t\_\{0\}\)\_\{\+\}of its indices are at leastt0t\_\{0\}, so∏i=j\+1tβi≤κN,t−j\\prod\_\{i=j\+1\}^\{t\}\\beta\_\{i\}\\leq\\kappa\_\{N,t\-j\}\. Hence

0≤Dt≤HN​A​∑j=1tκN,t−j​Yj\(t≤N\)\.0\\leq D\_\{t\}\\leq H\_\{N\}A\\sum\_\{j=1\}^\{t\}\\kappa\_\{N,t\-j\}Y\_\{j\}\\quad\(t\\leq 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](https://arxiv.org/html/2610.33381#Thmtheorem19)and \([50](https://arxiv.org/html/2610.33381#A10.E50)\) give

c⁡\(1−2​ε\)≤𝔼​∑t=1Nmin⁡\{st,Dt\}≤π​∑t=1N∑k=0t−1min⁡\{st,HN​A​κN,k\}\.c\(1\-2\\varepsilon\)\\leq\\mathbb\{E\}\\sum\_\{t=1\}^\{N\}\\min\\\{s\_\{t\},D\_\{t\}\\\}\\leq\\pi\\sum\_\{t=1\}^\{N\}\\sum\_\{k=0\}^\{t\-1\}\\min\\\{s\_\{t\},H\_\{N\}A\\kappa\_\{N,k\}\\\}\.For the second inequality, usemin⁡\{s,∑jwj\}≤∑jmin⁡\{s,wj\}\\min\\\{s,\\sum\_\{j\}w\_\{j\}\\\}\\leq\\sum\_\{j\}\\min\\\{s,w\_\{j\}\\\}forwj≥0w\_\{j\}\\geq 0and𝔼​Yj=π\\mathbb\{E\}Y\_\{j\}=\\pi\.■\\blacksquare

Proofof Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\(i\)\.Suppose the asserted envelope holds on every instance\. Sincea<1a<1andβp≤2/5\\beta\_\{p\}\\leq 2/5, we have\(1\+a\)​βp<1\(1\+a\)\\beta\_\{p\}<1; choose\(1\+a\)​βp<u<min⁡\{r,1\}\(1\+a\)\\beta\_\{p\}<u<\\min\\\{r,1\\\}and putbt=bN,tb\_\{t\}=b\_\{N,t\}from \([31](https://arxiv.org/html/2610.33381#A8.E31)\), withDN=C​logm⁡\(e​N\)D\_\{N\}=C\\log^\{m\}\(eN\)\. This dominates the asserted envelope fort≤Nt\\leq N\. For sufficiently largeNN,4​bN<μ≤1/24b\_\{N\}<\\mu\\leq 1/2, and Proposition[22](https://arxiv.org/html/2610.33381#Thmtheorem22)applies withε=δ\\varepsilon=\\delta\. IfH=0H=0, the required progress is already impossible\. Otherwise split the inner sum at

KN=t0\+⌈\(1\+N\)aρ​log\+⁡\(HN​Aμ\)⌉,log\+⁡\(v\)=max⁡\{0,log⁡v\}\.K\_\{N\}=t\_\{0\}\+\\left\\lceil\\frac\{\(1\+N\)^\{a\}\}\{\\rho\}\\log\_\{\+\}\\Bigl\(\\frac\{H\_\{N\}A\}\{\\mu\}\\Bigr\)\\right\\rceil,\\qquad\\log\_\{\+\}\(v\)=\\max\\\{0,\\log v\\\}\.Fork≥KNk\\geq K\_\{N\},HN​A​κN,k≤μ​exp⁡\(−ρ⁡\(k−KN\)​\(1\+N\)−a\)H\_\{N\}A\\kappa\_\{N,k\}\\leq\\mu\\exp\(\-\\rho\(k\-K\_\{N\}\)\(1\+N\)^\{\-a\}\), and\(1−e−x\)−1≤1\+x−1\(1\-e^\{\-x\}\)^\{\-1\}\\leq 1\+x^\{\-1\}forx\>0x\>0, so

∑k=0t−1min⁡\{st,HN​A​κN,k\}≤st​\(KN\+1\+\(1\+N\)aρ\)\.\\sum\_\{k=0\}^\{t\-1\}\\min\\\{s\_\{t\},H\_\{N\}A\\kappa\_\{N,k\}\\\}\\leq s\_\{t\}\\left\(K\_\{N\}\+1\+\\frac\{\(1\+N\)^\{a\}\}\{\\rho\}\\right\)\.\(51\)The factor isO⁡\(Na​log⁡\(e​N\)\)O\(N^\{a\}\\log\(eN\)\), with constants depending onH,h,ρ,t0,aH,h,\\rho,t\_\{0\},a, sincelog⁡HN=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\)\}\.By \([32](https://arxiv.org/html/2610.33381#A8.E32)\) withKNK\_\{N\}replaced by this factor, the right side of \([49](https://arxiv.org/html/2610.33381#A10.E49)\) is

O⁡\(DNq\+1/2​log⁡\(e​N\)​N1\+a−u/βp\),O\\bigl\(D\_\{N\}^\{q\+1/2\}\\log\(eN\)\\,N^\{1\+a\-u/\\beta\_\{p\}\}\\bigr\),which tends to zero becauseu\>\(1\+a\)​βpu\>\(1\+a\)\\beta\_\{p\}; this contradicts\(1−2​δ\)/2\>0\(1\-2\\delta\)/2\>0\. The contradiction at one finiteNNyields a fixed admissible instance on which \([16](https://arxiv.org/html/2610.33381#S6.E16)\) holds\.■\\blacksquare

Proofof Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7)\(ii\)\.Suppose the envelope holds for everyδ\\delta, every deterministic time, and every instance\. Sincec<1−\(1\+a\)​βpc<1\-\(1\+a\)\\beta\_\{p\}andr\>\(1\+a\)​βp\+cr\>\(1\+a\)\\beta\_\{p\}\+c, choose\(1\+a\)​βp\+c<u<min⁡\{r,1\}\(1\+a\)\\beta\_\{p\}\+c<u<\\min\\\{r,1\\\}and putv=u−c\>\(1\+a\)​βpv=u\-c\>\(1\+a\)\\beta\_\{p\}\. For each deterministicNN, letδN\\delta\_\{N\},DND\_\{N\}, andbN,t=DN​Nc​t−ub\_\{N,t\}=D\_\{N\}N^\{c\}t^\{\-u\}be as in the proof of Theorem[6](https://arxiv.org/html/2610.33381#Thmtheorem6); the envelope ofruleδN\\mathrm\{rule\}\_\{\\delta\_\{N\}\}is at mostbN,tb\_\{N,t\}fort≤Nt\\leq N, and a union bound gives the prefix guarantee of Proposition[22](https://arxiv.org/html/2610.33381#Thmtheorem22)with failure budget1/41/4on every instance\. On this prefix,ηt≤HN:=H​\(4​N\)h0​\(1\+N\)h\\eta\_\{t\}\\leq H\_\{N\}:=H\(4N\)^\{h\_\{0\}\}\(1\+N\)^\{h\}, and the proof of that proposition uses the step sizes only through this bound, so it applies withμ=8​bN,N=8​DN​N−v\\mu=8b\_\{N,N\}=8D\_\{N\}N^\{\-v\}, which lies in\(4​bN,N,1/2\]\(4b\_\{N,N\},1/2\]for largeNN\. Splitting the inner sums as in \([51](https://arxiv.org/html/2610.33381#A10.E51)\), whose factor is againO⁡\(Na​log⁡\(e​N\)\)O\(N^\{a\}\\log\(eN\)\)becauselog⁡HN=O⁡\(log⁡\(e​N\)\)\\log H\_\{N\}=O\(\\log\(eN\)\), and summingsts\_\{t\}as in the proof of Theorem[6](https://arxiv.org/html/2610.33381#Thmtheorem6), the right side of \([49](https://arxiv.org/html/2610.33381#A10.E49)\) is

O⁡\(DNq\+1/2​log⁡\(e​N\)​N1\+a−v/βp\),O\\bigl\(D\_\{N\}^\{q\+1/2\}\\log\(eN\)\\,N^\{1\+a\-v/\\beta\_\{p\}\}\\bigr\),which tends to zero becausev\>\(1\+a\)​βpv\>\(1\+a\)\\beta\_\{p\}; this contradicts1/41/4\. At such anNN, some instance fixed before the run fails the prefix guarantee with probability above1/4=N​δN1/4=N\\delta\_\{N\}, and the union bound gives a deterministict≤Nt\\leq Nwhose fixed\-time failure probability exceedsδN\\delta\_\{N\}\.■\\blacksquare

## Appendix KA Dimension\-Uniform Momentum Lower Bound

We prove Theorem[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\. Throughout, the control and rate constants are common over dimensions, as required by𝒜unif​\(a\)\\mathcal\{A\}\_\{\\mathrm\{unif\}\}\(a\)\.

### K\.1A Pathwise Projection Identity

Fix the numerical scalar controls on a realized finite path; they may depend on the observations\. Writeclip⁡\(gs,λs\)=cs​gs\\operatorname\{clip\}\(g\_\{s\},\\lambda\_\{s\}\)=c\_\{s\}g\_\{s\}, withcs∈\[0,1\]c\_\{s\}\\in\[0,1\]andcs=0c\_\{s\}=0whengs=0g\_\{s\}=0\. Its nuisance block satisfiesvs\+1=βs​vs\+cs​\(ys\+ζs\)v\_\{s\+1\}=\\beta\_\{s\}v\_\{s\}\+c\_\{s\}\(y\_\{s\}\+\\zeta\_\{s\}\)andys\+1=ys−ηs​vs\+1y\_\{s\+1\}=y\_\{s\}\-\\eta\_\{s\}v\_\{s\+1\}, withy1=v1=0y\_\{1\}=v\_\{1\}=0\. An impulse of sizeAAat timeτ\\tauhas flat response

ht=A​cτ​∑s=τt−1ηs​∏i=τ\+1sβi\(t\>τ\),ht=0\(t≤τ\)\.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\\leq\\tau\)\.\(52\)Nonnegative controls makehth\_\{t\}nonnegative and nondecreasing\.

###### Lemma 23\(Orthogonal pulse budget\)\.

Suppose allζj\\zeta\_\{j\},1≤j<t1\\leq j<t, are nonzero and mutually orthogonal, withζj=Rj​ϵj​eJj\\zeta\_\{j\}=R\_\{j\}\\epsilon\_\{j\}e\_\{J\_\{j\}\},Rj≥B\>0R\_\{j\}\\geq B\>0, signsϵj∈\{−1,1\}\\epsilon\_\{j\}\\in\\\{\-1,1\\\}, and distinctJjJ\_\{j\}\. Forτ<t\\tau<twithRτ=AR\_\{\\tau\}=A, lethth\_\{t\}be \([52](https://arxiv.org/html/2610.33381#A11.E52)\)\. If‖yt‖≤R\\\|y\_\{t\}\\\|\\leq RandR​t−τ−1≤B/2R\\sqrt\{t\-\\tau\-1\}\\leq B/2, thenht≤2​Rh\_\{t\}\\leq 2R\.

ProofDefine the test vector

w=ζτA\+∑j=τ\+1t−1hjRj2​ζj\.w=\\frac\{\\zeta\_\{\\tau\}\}\{A\}\+\\sum\_\{j=\\tau\+1\}^\{t\-1\}\\frac\{h\_\{j\}\}\{R\_\{j\}^\{2\}\}\\zeta\_\{j\}\.Orthogonality gives⟨ζs,w⟩=hs\+A𝟏\{s=τ\}\\langle\\zeta\_\{s\},w\\rangle=h\_\{s\}\+A\\mathbf\{1\}\_\{\\\{s=\\tau\\\}\}fors<ts<t\. Letk1=0k\_\{1\}=0andks\+1=βsks\+Acs𝟏\{s=τ\}k\_\{s\+1\}=\\beta\_\{s\}k\_\{s\}\+Ac\_\{s\}\\mathbf\{1\}\_\{\\\{s=\\tau\\\}\}; then \([52](https://arxiv.org/html/2610.33381#A11.E52)\) giveshs\+1=hs\+ηs​ks\+1h\_\{s\+1\}=h\_\{s\}\+\\eta\_\{s\}k\_\{s\+1\}\. Induction in the nuisance recurrence yields⟨vs,w⟩=ks\\langle v\_\{s\},w\\rangle=k\_\{s\}and⟨ys,w⟩=−hs\\langle y\_\{s\},w\\rangle=\-h\_\{s\}fors≤ts\\leq t: the terms−hs\+hs\-h\_\{s\}\+h\_\{s\}cancel at every update\. Therefore

ht2≤‖yt‖2​‖w‖2=‖yt‖2​\(1\+∑j=τ\+1t−1hj2Rj2\)≤R2\+14​ht2\.h\_\{t\}^\{2\}\\leq\\\|y\_\{t\}\\\|^\{2\}\\\|w\\\|^\{2\}=\\\|y\_\{t\}\\\|^\{2\}\\left\(1\+\\sum\_\{j=\\tau\+1\}^\{t\-1\}\\frac\{h\_\{j\}^\{2\}\}\{R\_\{j\}^\{2\}\}\\right\)\\leq R^\{2\}\+\\tfrac\{1\}\{4\}h\_\{t\}^\{2\}\.Thusht≤2​R/3≤2​Rh\_\{t\}\\leq 2R/\\sqrt\{3\}\\leq 2R; as the identity is pathwise,wwmay be chosen after the path\.■\\blacksquare

### K\.2A Fixed I\.I\.D\. Witness and the Rate Contradiction

Proofof Theorem[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\(i\)\.Choosemax⁡\{βp,a\}<u<min⁡\{r,1\}\\max\\\{\\beta\_\{p\},a\\\}<u<\\min\\\{r,1\\\}\. A finite commonD\>0D\>0makesbt=D​t−ub\_\{t\}=Dt^\{\-u\}dominate the proposed logarithmic envelope\. Suppose this weaker envelope holds with probability at least1−δ1\-\\deltaon every finite\-dimensional instance\. For a large deterministicNN, set

μ=8​D​N−u,κ=1/128,B=1/16,A=\(κ/μ\)1/\(p−1\),π=μ/A\.\\mu=8DN^\{\-u\},\\quad\\kappa=1/128,\\quad B=1/16,\\quad A=\(\\kappa/\\mu\)^\{1/\(p\-1\)\},\\quad\\pi=\\mu/A\.Choose an integerdN≥2​N2/\(1−δ\)d\_\{N\}\\geq 2N^\{2\}/\(1\-\\delta\)\. TakeNNlarge enough thatμ≤1/2\\mu\\leq 1/2,A≥1A\\geq 1, andπ≤1/2\\pi\\leq 1/2\. Independently each round, drawY∼Bernoulli⁡\(π\)Y\\sim\\operatorname\{Bernoulli\}\(\\pi\), a uniformJ∈\{1,…,dN\}J\\in\\\{1,\\ldots,d\_\{N\}\\\}, and a uniform signϵ\\epsilon, independent within a sample as well\. LetR0=B,R1=AR\_\{0\}=B,R\_\{1\}=A, and define

F⁡\(x,y,Y,J,ϵ\)=12​\(x−1\+μ\)\+2−A​Y​x\+12​‖y‖2\+RY​ϵ​yJ\.F\(x,y;Y,J,\\epsilon\)=\\tfrac\{1\}\{2\}\(x\-1\+\\mu\)\_\{\+\}^\{2\}\-AYx\+\\tfrac\{1\}\{2\}\\\|y\\\|^\{2\}\+R\_\{Y\}\\epsilon y\_\{J\}\.
*Admissibility\.*Each sample is convex and globally11\-smooth: the two orthogonal Hessian blocks are bounded by one\. In the first coordinatexx, the sample loss attains its minimum at anyx≤1−μx\\leq 1\-\\muwhenY=0Y=0, and atx=1−μ\+Ax=1\-\\mu\+AwhenY=1Y=1; in the nuisance blockyy, its minimizer is−RY​ϵ​eJ\-R\_\{Y\}\\epsilon e\_\{J\}\. Thus every sample minimum is finite and attained\. The population isf⁡\(x,y\)=12​\(x−1\+μ\)\+2−μ​x\+12​‖y‖2f\(x,y\)=\\tfrac\{1\}\{2\}\(x\-1\+\\mu\)\_\{\+\}^\{2\}\-\\mu x\+\\tfrac\{1\}\{2\}\\\|y\\\|^\{2\}, with minimizer\(1,0\)\(1,0\)at initial distance one\. The fixed additive noiseξ=\(μ−A​Y,RY​ϵ​eJ\)\\xi=\(\\mu\-AY,R\_\{Y\}\\epsilon e\_\{J\}\)is centered\. Sinceπ​Ap=κ\\pi A^\{p\}=\\kappaandμ=π​A\\mu=\\pi A,

𝔼​\|μ−A​Y\|p≤2​κ,𝔼​‖ξ‖p≤2p−1​\(2​κ\+Bp\+κ\)≤6/128\+2/16<1\.\\mathbb\{E\}\|\\mu\-AY\|^\{p\}\\leq 2\\kappa,\\qquad\\mathbb\{E\}\\\|\\xi\\\|^\{p\}\\leq 2^\{p\-1\}\(2\\kappa\+B^\{p\}\+\\kappa\)\\leq 6/128\+2/16<1\.For every state the gap is at least‖y‖2/2\\\|y\\\|^\{2\}/2; whenx≤1/2x\\leq 1/2it is also at leastμ⁡\(1−x\)−μ2/2≥μ/4\\mu\(1\-x\)\-\\mu^\{2\}/2\\geq\\mu/4\.

*Coupling and useful events\.*Feed the rule reference gradients\(−A​Yt,yt\+RYt​ϵt​eJt\)\(\-AY\_\{t\},y\_\{t\}\+R\_\{Y\_\{t\}\}\\epsilon\_\{t\}e\_\{J\_\{t\}\}\)until the first update whose first coordinateXt\+1X\_\{t\+1\}exceeds1/21/2, or until roundNN\. Denote that last retained round byS≤NS\\leq N\. The first velocity is nonpositive, soXtX\_\{t\}is nondecreasing\. Under the shared random draws and seed, the reference and actual trajectories coincide through stepSS: prior to stepSS, every queried first coordinate satisfiesXt≤1/2≤1−μX\_\{t\}\\leq 1/2\\leq 1\-\\mu, so all stochastic gradients, histories, and controls coincide\. Let𝒢\\mathcal\{G\}be the actual instance’s success event for allt≤Nt\\leq N\. Thenℙ⁡\(𝒢\)≥1−δ\\mathbb\{P\}\(\\mathcal\{G\}\)\\geq 1\-\\delta\. On𝒢\\mathcal\{G\}a crossing occurs byNN, since otherwise the final gap is at leastμ/4=2​bN\\mu/4=2b\_\{N\}; also

‖yt‖≤2​bt−1\(2≤t≤S\+1\)\.\\\|y\_\{t\}\\\|\\leq\\sqrt\{2b\_\{t\-1\}\}\\quad\(2\\leq t\\leq S\+1\)\.\(53\)Let𝒞\\mathcal\{C\}mean thatJ1,…,JNJ\_\{1\},\\ldots,J\_\{N\}are distinct\. The union bound givesℙ⁡\(𝒞c\)≤N⁡\(N−1\)/\(2​dN\)≤\(1−δ\)/4\\mathbb\{P\}\(\\mathcal\{C\}^\{c\}\)\\leq N\(N\-1\)/\(2d\_\{N\}\)\\leq\(1\-\\delta\)/4\. ForQp=p/\(p−1\)Q\_\{p\}=p/\(p\-1\)choose0<θ<min⁡\{1,u​Qp\}0<\\theta<\\min\\\{1,uQ\_\{p\}\\\}and setn0=⌈Nθ⌉n\_\{0\}=\\lceil N^\{\\theta\}\\rceil\. Letℰ\\mathcal\{E\}meanYt=0Y\_\{t\}=0fort<n0t<n\_\{0\}\. Thenℙ⁡\(ℰc\)≤n0​π=O⁡\(Nθ−u​Qp\)→0\\mathbb\{P\}\(\\mathcal\{E\}^\{c\}\)\\leq n\_\{0\}\\pi=O\(N^\{\\theta\-uQ\_\{p\}\}\)\\to 0; the nuisance noise still acts\.

*Each pulse has a short useful window\.*SetP=h\+u/\(p−1\)\+5P=h\+u/\(p\-1\)\+5,Λ=3a​P/ρ\\Lambda=3^\{a\}P/\\rho, andwj=⌈Λ​\(1\+j\)a​log⁡N⌉w\_\{j\}=\\lceil\\Lambda\(1\+j\)^\{a\}\\log N\\rceil\. Uniformly forn0≤j≤Nn\_\{0\}\\leq j\\leq N, largeNNgivesj≥t0j\\geq t\_\{0\},wj≤jw\_\{j\}\\leq j, and

2​bj​wjB2=O⁡\(Nθ⁡\(a−u\)​log⁡N\+N−θ​u\)⟶0\.\\frac\{2b\_\{j\}w\_\{j\}\}\{B^\{2\}\}=O\\bigl\(N^\{\\theta\(a\-u\)\}\\log N\+N^\{\-\\theta u\}\\bigr\)\\longrightarrow 0\.\(54\)Fix the realized controls throughSS\. For a rare arrivalj≤Sj\\leq S, letht\(j\)h\_\{t\}^\{\(j\)\}be the impulse response \([52](https://arxiv.org/html/2610.33381#A11.E52)\) withτ=j\\tau=j, and puttj=min⁡\{S\+1,j\+wj\+1\}t\_\{j\}=\\min\\\{S\+1,j\+w\_\{j\}\+1\\\}\. On𝒢∩𝒞\\mathcal\{G\}\\cap\\mathcal\{C\}, the nuisance observationsζ1,…,ζtj−1\\zeta\_\{1\},\\ldots,\\zeta\_\{t\_\{j\}\-1\}are nonzero and orthogonal, each has norm at leastBB, and the vector atjjhas normAA\. Equation \([53](https://arxiv.org/html/2610.33381#A11.E53)\) gives‖ytj‖≤2​bj\\\|y\_\{t\_\{j\}\}\\\|\\leq\\sqrt\{2b\_\{j\}\}; thus Lemma[23](https://arxiv.org/html/2610.33381#Thmtheorem23)and \([54](https://arxiv.org/html/2610.33381#A11.E54)\) givehtj\(j\)≤2​2​bjh\_\{t\_\{j\}\}^\{\(j\)\}\\leq 2\\sqrt\{2b\_\{j\}\}for everyj≥n0j\\geq n\_\{0\}\.

Iftj<S\+1t\_\{j\}<S\+1, the firstwjw\_\{j\}subsequent momentum coefficients satisfy

∏i=j\+1j\+wjβi≤exp⁡\(−ρ​wj3a​\(1\+j\)a\)≤N−P\.\\prod\_\{i=j\+1\}^\{j\+w\_\{j\}\}\\beta\_\{i\}\\leq\\exp\\left\(\-\\frac\{\\rho w\_\{j\}\}\{3^\{a\}\(1\+j\)^\{a\}\}\\right\)\\leq N^\{\-P\}\.Every subsequent factor is at most one\. Sincecj≤1c\_\{j\}\\leq 1, the polynomial bound on the step sizes in \([17](https://arxiv.org/html/2610.33381#S6.E17)\) implies pathwise that

0≤hS\+1\(j\)−htj\(j\)≤A​H​N​\(1\+N\)h​N−P≤C0​N−4,0\\leq h\_\{S\+1\}^\{\(j\)\}\-h\_\{t\_\{j\}\}^\{\(j\)\}\\leq AHN\(1\+N\)^\{h\}N^\{\-P\}\\leq C\_\{0\}N^\{\-4\},\(55\)withC0C\_\{0\}depending only on common fixed parameters; indeedA=\(κ/\(8​D\)\)1/\(p−1\)​Nu/\(p−1\)A=\(\\kappa/\(8D\)\)^\{1/\(p\-1\)\}N^\{u/\(p\-1\)\}\. Fortj=S\+1t\_\{j\}=S\+1the tail is zero\.

*Contradiction on total progress\.*The displacement along the first coordinate isXS\+1=∑j≤SYj​hS\+1\(j\)X\_\{S\+1\}=\\sum\_\{j\\leq S\}Y\_\{j\}h\_\{S\+1\}^\{\(j\)\}\. On𝒢∩𝒞∩ℰ\\mathcal\{G\}\\cap\\mathcal\{C\}\\cap\\mathcal\{E\}, it must exceed1/21/2, but the preceding bounds give

12<XS\+1≤22​D∑j=n0NYjj−u/2\+C0N−3\.\\tfrac\{1\}\{2\}<X\_\{S\+1\}\\leq 2\\sqrt\{2D\}\\sum\_\{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𝔼​Yj=π\\mathbb\{E\}Y\_\{j\}=\\piyields

12ℙ\(𝒢∩𝒞∩ℰ\)≤22​Dπ∑j=1Nj−u/2\+C0N−3\.\\tfrac\{1\}\{2\}\\mathbb\{P\}\(\\mathcal\{G\}\\cap\\mathcal\{C\}\\cap\\mathcal\{E\}\)\\leq 2\\sqrt\{2D\}\\,\\pi\\sum\_\{j=1\}^\{N\}j^\{\-u/2\}\+C\_\{0\}N^\{\-3\}\.\(56\)The left side has liminf at least3​\(1−δ\)/83\(1\-\\delta\)/8\. The right side isO⁡\(N1−u⁡\(Qp\+1/2\)\)\+O⁡\(N−3\)→0O\(N^\{1\-u\(Q\_\{p\}\+1/2\)\}\)\+O\(N^\{\-3\}\)\\to 0becauseu\>βp=1/\(Qp\+1/2\)u\>\\beta\_\{p\}=1/\(Q\_\{p\}\+1/2\)andu<1u<1\. This contradiction gives prefix failure strictly greater thanδ\\deltafor one fixed law and finite dimension\.■\\blacksquare

Proofof Theorem[8](https://arxiv.org/html/2610.33381#Thmtheorem8)\(ii\)\.Suppose the envelope holds for everyδ\\delta, every deterministic time, and every finite\-dimensional instance\. Choosemax⁡\{βp,a\}<u<min⁡\{r,1\}\\max\\\{\\beta\_\{p\},a\\\}<u<\\min\\\{r,1\\\}\. For each deterministicNN, put

δN=14​N,DN=C​logk⁡\(4​e​N2\),bN,t=DN​t−u\.\\delta\_\{N\}=\\frac\{1\}\{4N\},\\qquad D\_\{N\}=C\\log^\{k\}\(4eN^\{2\}\),\\qquad b\_\{N,t\}=D\_\{N\}t^\{\-u\}\.Sincet−r≤t−ut^\{\-r\}\\leq t^\{\-u\}andlog⁡\(e​t/δN\)≤log⁡\(4​e​N2\)\\log\(et/\\delta\_\{N\}\)\\leq\\log\(4eN^\{2\}\)for1≤t≤N1\\leq t\\leq N, the envelope ofruleδN\\mathrm\{rule\}\_\{\\delta\_\{N\}\}is at mostbN,tb\_\{N,t\}on this prefix, and a union bound shows that, on every instance,f⁡\(xt\+1\)−f⋆≤bN,tf\(x\_\{t\+1\}\)\-f^\{\\star\}\\leq b\_\{N,t\}for allt≤Nt\\leq Nwith probability at least3/43/4; thereηt≤H​\(4​N\)h0​\(1\+N\)h\\eta\_\{t\}\\leq H\(4N\)^\{h\_\{0\}\}\(1\+N\)^\{h\}\.

Run the proof of part \(i\) forruleδN\\mathrm\{rule\}\_\{\\delta\_\{N\}\}, withDDreplaced byDND\_\{N\},1−δ1\-\\deltaby3/43/4, andPPbyh\+h0\+u/\(p−1\)\+5h\+h\_\{0\}\+u/\(p\-1\)\+5\. Its estimates depend on the rule only through the common constantsρ,t0,H,h,h0\\rho,t\_\{0\},H,h,h\_\{0\}, andC≤DN=No⁡\(1\)C\\leq D\_\{N\}=N^\{o\(1\)\}, so they hold for all largeNN, with constants independent ofNNand of the rule\. Explicitly,μ=8​DN​N−u→0\\mu=8D\_\{N\}N^\{\-u\}\\to 0,dN≥8​N2/3d\_\{N\}\\geq 8N^\{2\}/3givesℙ⁡\(𝒞c\)≤3/16\\mathbb\{P\}\(\\mathcal\{C\}^\{c\}\)\\leq 3/16, and, uniformly forn0≤j≤Nn\_\{0\}\\leq j\\leq N,

π=κ−1/\(p−1\)μQp=O\(DNQpN−u​Qp\),ℙ\(ℰc\)≤n0π=O\(DNQpNθ−u​Qp\),2​bN,j​wjB2=O⁡\(DN​\[Nθ⁡\(a−u\)​log⁡N\+N−θ​u\]\),\\begin\{gathered\}\\pi=\\kappa^\{\-1/\(p\-1\)\}\\mu^\{Q\_\{p\}\}=O\(D\_\{N\}^\{Q\_\{p\}\}N^\{\-uQ\_\{p\}\}\),\\qquad\\mathbb\{P\}\(\\mathcal\{E\}^\{c\}\)\\leq n\_\{0\}\\pi=O\(D\_\{N\}^\{Q\_\{p\}\}N^\{\\theta\-uQ\_\{p\}\}\),\\\\ \\frac\{2b\_\{N,j\}w\_\{j\}\}\{B^\{2\}\}=O\\bigl\(D\_\{N\}\[N^\{\\theta\(a\-u\)\}\\log N\+N^\{\-\\theta u\}\]\\bigr\),\\end\{gathered\}all of which tend to zero\. In \([55](https://arxiv.org/html/2610.33381#A11.E55)\),A≤\(κ/\(8​C\)\)1/\(p−1\)​Nu/\(p−1\)A\\leq\(\\kappa/\(8C\)\)^\{1/\(p\-1\)\}N^\{u/\(p\-1\)\}andηs≤H​\(4​N\)h0​\(1\+N\)h\\eta\_\{s\}\\leq H\(4N\)^\{h\_\{0\}\}\(1\+N\)^\{h\}; since1\+h\+h0\+u/\(p−1\)−P=−41\+h\+h\_\{0\}\+u/\(p\-1\)\-P=\-4, the tail is stillO⁡\(N−4\)O\(N^\{\-4\}\)\. The left side of \([56](https://arxiv.org/html/2610.33381#A11.E56)\) is at least\(3/4−3/16−o⁡\(1\)\)/2\(3/4\-3/16\-o\(1\)\)/2, with liminf at least9/329/32, whereas its right side isO⁡\(DNQp\+1/2​N1−u⁡\(Qp\+1/2\)\)\+O⁡\(N−3\)→0O\(D\_\{N\}^\{Q\_\{p\}\+1/2\}N^\{1\-u\(Q\_\{p\}\+1/2\)\}\)\+O\(N^\{\-3\}\)\\to 0asu\>βp=1/\(Qp\+1/2\)u\>\\beta\_\{p\}=1/\(Q\_\{p\}\+1/2\)\. Hence, for someNN, the instance of dimensiondNd\_\{N\}fails the prefix guarantee with probability above1/4=N​δN1/4=N\\delta\_\{N\}, and the union bound gives a deterministict≤Nt\\leq Nwith fixed\-time failure probability aboveδN\\delta\_\{N\}\.■\\blacksquare

## Appendix LTime\-Uniform Averaging Momentum

This appendix proves Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9)and Propositions[24](https://arxiv.org/html/2610.33381#Thmtheorem24)and[25](https://arxiv.org/html/2610.33381#Thmtheorem25)\.

Proofof Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9)\.WriteFt=f⁡\(xt\)−f⋆F\_\{t\}=f\(x\_\{t\}\)\-f^\{\\star\},μt=∇f​\(xt\)\\mu\_\{t\}=\\nabla f\(x\_\{t\}\), andDt=‖zt−x⋆‖D\_\{t\}=\\\|z\_\{t\}\-x^\{\\star\}\\\|\. The averaging update gives

xt=1t​∑s=1tzs,zt=t​xt−\(t−1\)​xt−1\.x\_\{t\}=\\frac\{1\}\{t\}\\sum\_\{s=1\}^\{t\}z\_\{s\},\\qquad z\_\{t\}=tx\_\{t\}\-\(t\-1\)x\_\{t\-1\}\.\(57\)Att=1t=1the second identity is independent ofx0x\_\{0\}\.

*A smooth online\-to\-batch inequality\.*By the standard inequality for smooth convex functions\[[Nesterov, 2004](https://arxiv.org/html/2610.33381#bib.bib42), Theorem 2\.1\.5\]and∇f​\(x⋆\)=0\\nabla f\(x^\{\\star\}\)=0, we have

⟨∇f​\(x\),x−x⋆⟩≥f⁡\(x\)−f⋆\+‖∇f​\(x\)‖22​L\.\\langle\\nabla f\(x\),x\-x^\{\\star\}\\rangle\\geq f\(x\)\-f^\{\\star\}\+\\frac\{\\\|\\nabla f\(x\)\\\|^\{2\}\}\{2L\}\.Combining it with \([57](https://arxiv.org/html/2610.33381#A12.E57)\) and⟨μt,xt−xt−1⟩≥Ft−Ft−1\\langle\\mu\_\{t\},x\_\{t\}\-x\_\{t\-1\}\\rangle\\geq F\_\{t\}\-F\_\{t\-1\}gives

⟨μt,zt−x⋆⟩≥t​Ft−\(t−1\)​Ft−1\+‖μt‖22​L\.\\langle\\mu\_\{t\},z\_\{t\}\-x^\{\\star\}\\rangle\\geq tF\_\{t\}\-\(t\-1\)F\_\{t\-1\}\+\\frac\{\\\|\\mu\_\{t\}\\\|^\{2\}\}\{2L\}\.\(58\)This is the smooth form of the anytime online\-to\-batch inequality\[[Cutkosky, 2019](https://arxiv.org/html/2610.33381#bib.bib9)\]\.

*A pathwise energy recursion\.*Letet=dt−μte\_\{t\}=d\_\{t\}\-\\mu\_\{t\}\. Expanding the update and using \([58](https://arxiv.org/html/2610.33381#A12.E58)\) and‖μt\+et‖2≤2​‖μt‖2\+2​‖et‖2\\\|\\mu\_\{t\}\+e\_\{t\}\\\|^\{2\}\\leq 2\\\|\\mu\_\{t\}\\\|^\{2\}\+2\\\|e\_\{t\}\\\|^\{2\}gives

Dt\+12≤Dt2−2​γt​\{t​Ft−\(t−1\)​Ft−1\}\+Δt,Δt=2​γt2​‖et‖2−2​γt​⟨et,zt−x⋆⟩\.D\_\{t\+1\}^\{2\}\\leq 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\.Here the omitted term involving‖μt‖2\\\|\\mu\_\{t\}\\\|^\{2\}is nonpositive sinceγt≤a/\(4​L​ℓt2\)≤1/\(2​L\)\\gamma\_\{t\}\\leq a/\(4L\\ell\_\{t\}^\{2\}\)\\leq 1/\(2L\)\. DefineW1=D12W\_\{1\}=D\_\{1\}^\{2\}and

Wt\+1=Dt\+12\+2​t​γt​Ft\+2​∑s=1t−1s⁡\(γs−γs\+1\)​Fs\.W\_\{t\+1\}=D\_\{t\+1\}^\{2\}\+2t\\gamma\_\{t\}F\_\{t\}\+2\\sum\_\{s=1\}^\{t\-1\}s\(\\gamma\_\{s\}\-\\gamma\_\{s\+1\}\)F\_\{s\}\.Sinceγt\\gamma\_\{t\}is nonincreasing,Wt≥Dt2≥0W\_\{t\}\\geq D\_\{t\}^\{2\}\\geq 0\. The exact differenceWt\+1−Wt=Dt\+12−Dt2\+2​γt​\{t​Ft−\(t−1\)​Ft−1\}W\_\{t\+1\}\-W\_\{t\}=D\_\{t\+1\}^\{2\}\-D\_\{t\}^\{2\}\+2\\gamma\_\{t\}\\\{tF\_\{t\}\-\(t\-1\)F\_\{t\-1\}\\\}therefore givesWt\+1≤Wt\+ΔtW\_\{t\+1\}\\leq W\_\{t\}\+\\Delta\_\{t\}, also att=1t=1without anF0F\_\{0\}term\.

*Predictable localization and conditional clipping\.*Letτ=inf\{t≥1:Wt≥2​R2\}\\tau=\\inf\\\{t\\geq 1:W\_\{t\}\\geq 2R^\{2\}\\\}andIt=𝟏\{t<τ\}I\_\{t\}=\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\. EachWsW\_\{s\}isℱs−1\\mathcal\{F\}\_\{s\-1\}\-measurable, soItI\_\{t\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable, that is, predictable, and nonincreasing intt\. Since‖ds‖≤λs\\\|d\_\{s\}\\\|\\leq\\lambda\_\{s\}, the statesztz\_\{t\},xtx\_\{t\}and the errorsete\_\{t\}are bounded at each fixedtt, soete\_\{t\}is integrable\. Ont<τt<\\tau, alls≤ts\\leq tsatisfyDs<2​RD\_\{s\}<\\sqrt\{2\}R\. Thus \([57](https://arxiv.org/html/2610.33381#A12.E57)\) gives‖xt−x⋆‖<2​R\\\|x\_\{t\}\-x^\{\\star\}\\\|<2Rand‖μt‖≤2​L​R≤λt/2\\\|\\mu\_\{t\}\\\|\\leq 2LR\\leq\\lambda\_\{t\}/2\. Lemma[12](https://arxiv.org/html/2610.33381#Thmtheorem12), applied conditionally on this predictable event, yields

‖et‖≤32​λt,‖𝔼t−1​et‖≤Bt:=2​σp​λt1−p,𝔼t−1​‖et‖2≤Vt:=2​σp​λt2−p\.\\\|e\_\{t\}\\\|\\leq\\frac\{3\}\{2\}\\lambda\_\{t\},\\qquad\\\|\\mathbb\{E\}\_\{t\-1\}e\_\{t\}\\\|\\leq B\_\{t\}:=2\\sigma^\{p\}\\lambda\_\{t\}^\{1\-p\},\\qquad\\mathbb\{E\}\_\{t\-1\}\\\|e\_\{t\}\\\|^\{2\}\\leq V\_\{t\}:=2\\sigma^\{p\}\\lambda\_\{t\}^\{2\-p\}\.\(59\)Forq\>1q\>1, integral comparison gives

∑t≥11t​\(h\+log⁡t\)q≤1hq\+1\(q−1\)​hq−1\.\\sum\_\{t\\geq 1\}\\frac\{1\}\{t\(h\+\\log t\)^\{q\}\}\\leq\\frac\{1\}\{h^\{q\}\}\+\\frac\{1\}\{\(q\-1\)h^\{q\-1\}\}\.Sinceλtp≥σp​t\\lambda\_\{t\}^\{p\}\\geq\\sigma^\{p\}t, the deterministic budgets are

∑tγt​Bt≤4​a​Rh,∑tγt2​Vt≤4​a2​R2h3,γt​λt=a​Rℓt2\.\\sum\_\{t\}\\gamma\_\{t\}B\_\{t\}\\leq\\frac\{4aR\}\{h\},\\qquad\\sum\_\{t\}\\gamma\_\{t\}^\{2\}V\_\{t\}\\leq\\frac\{4a^\{2\}R^\{2\}\}\{h^\{3\}\},\\qquad\\gamma\_\{t\}\\lambda\_\{t\}=\\frac\{aR\}\{\\ell\_\{t\}^\{2\}\}\.\(60\)These includeσ=0\\sigma=0, whenBt=Vt=0B\_\{t\}=V\_\{t\}=0\.

*One application of the common energy bound\.*Apply Lemma[15](https://arxiv.org/html/2610.33381#Thmtheorem15)withPm=Wm\+1P\_\{m\}=W\_\{m\+1\}form≥0m\\geq 0, the predictable indicatorsJt=ItJ\_\{t\}=I\_\{t\},ℰ=Ω\\mathcal\{E\}=\\Omega,p0=R2p\_\{0\}=R^\{2\},q=hq=h, and

at=2​γt2,wt=−2​γt​\(zt−x⋆\),st=2​γt,Mt=32​λt,Ut=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\}=\\tfrac\{3\}\{2\}\\lambda\_\{t\},\\qquad U\_\{t\}=2\\lambda\_\{t\}\.The pathwise recursionWt\+1≤Wt\+ΔtW\_\{t\+1\}\\leq W\_\{t\}\+\\Delta\_\{t\}is the required one,P0=D12≤R2P\_\{0\}=D\_\{1\}^\{2\}\\leq R^\{2\}, and‖wt‖≤st​Pt−1\\\|w\_\{t\}\\\|\\leq s\_\{t\}\\sqrt\{P\_\{t\-1\}\}becauseDt2≤WtD\_\{t\}^\{2\}\\leq W\_\{t\}\. OnIt=1I\_\{t\}=1, \([59](https://arxiv.org/html/2610.33381#A12.E59)\) givesBtB\_\{t\},VtV\_\{t\}, andMtM\_\{t\}, and Lemma[12](https://arxiv.org/html/2610.33381#Thmtheorem12)also gives‖et−𝔼t−1​et‖≤Ut\\\|e\_\{t\}\-\\mathbb\{E\}\_\{t\-1\}e\_\{t\}\\\|\\leq U\_\{t\}\. By \([60](https://arxiv.org/html/2610.33381#A12.E60)\) andγt​λt=a​R/ℓt2≤a​R/h2\\gamma\_\{t\}\\lambda\_\{t\}=aR/\\ell\_\{t\}^\{2\}\\leq aR/h^\{2\}, the budgets of the lemma satisfy

A≤8​a2​R2h3,K0≤9​a2​R22​h4,B0≤8​a​Rh,V0≤16​a2​R2h3,J0≤4​a​Rh2,A\\leq\\frac\{8a^\{2\}R^\{2\}\}\{h^\{3\}\},\\qquad K\_\{0\}\\leq\\frac\{9a^\{2\}R^\{2\}\}\{2h^\{4\}\},\\qquad B\_\{0\}\\leq\\frac\{8aR\}\{h\},\\qquad V\_\{0\}\\leq\\frac\{16a^\{2\}R^\{2\}\}\{h^\{3\}\},\\qquad J\_\{0\}\\leq\\frac\{4aR\}\{h^\{2\}\},soC≤R2​\(1\+29​a2/h3\)C\\leq R^\{2\}\(1\+29a^\{2\}/h^\{3\}\)andD≤24​a​R/hD\\leq 24aR/h\. Sincea=1/128a=1/128andh≥8h\\geq 8,\(C\+D\)2≤R2​\(1\+29​a2/h3\+24​a/h\)2<2​R2\(\\sqrt\{C\}\+D\)^\{2\}\\leq R^\{2\}\(1\+29a^\{2\}/h^\{3\}\+24a/h\)^\{2\}<2R^\{2\}\. Except on probabilitye−h<δe^\{\-h\}<\\delta, the lemma therefore givesWm\+1<2​R2W\_\{m\+1\}<2R^\{2\}wheneverIm=1I\_\{m\}=1\. Ifτ<∞\\tau<\\infty, thenτ≥2\\tau\\geq 2becauseW1≤R2W\_\{1\}\\leq R^\{2\}, andm=τ−1m=\\tau\-1hasIm=1I\_\{m\}=1butWm\+1=Wτ≥2​R2W\_\{m\+1\}=W\_\{\\tau\}\\geq 2R^\{2\}\. Henceτ=∞\\tau=\\inftyon this event, and simultaneously for everyT≥1T\\geq 1,

DT\+12\+2​T​γT​FT≤WT\+1<2​R2\.D\_\{T\+1\}^\{2\}\+2T\\gamma\_\{T\}F\_\{T\}\\leq W\_\{T\+1\}<2R^\{2\}\.In particular,DT\+1<2​RD\_\{T\+1\}<\\sqrt\{2\}RandFT≤R2/\(T​γT\)=128​R​λT​ℓT2/TF\_\{T\}\\leq R^\{2\}/\(T\\gamma\_\{T\}\)=128R\\lambda\_\{T\}\\ell\_\{T\}^\{2\}/T\.

*The last iterate\.*Convexity of the implemented update and smoothness at the minimizer give

f⁡\(xT\+1\)−f⋆\\displaystyle f\(x\_\{T\+1\}\)\-f^\{\\star\}≤TT\+1​FT\+f⁡\(zT\+1\)−f⋆T\+1\\displaystyle\\leq\\frac\{T\}\{T\+1\}F\_\{T\}\+\\frac\{f\(z\_\{T\+1\}\)\-f^\{\\star\}\}\{T\+1\}≤128​R​λT​ℓT2\+2​L​R2T\+1\.\\displaystyle\\leq\\frac\{128R\\lambda\_\{T\}\\ell\_\{T\}^\{2\}\+2LR^\{2\}\}\{T\+1\}\.Finally,λT≤4​L​R\+σ​T1/p\\lambda\_\{T\}\\leq 4LR\+\\sigma T^\{1/p\},ℓT≥1\\ell\_\{T\}\\geq 1, and\(T\+1\)−1≤T−1\(T\+1\)^\{\-1\}\\leq T^\{\-1\}prove \([22](https://arxiv.org/html/2610.33381#S6.E22)\)\.■\\blacksquare

###### Proposition 24\(Exact momentum conventions\)\.

The states in \([20](https://arxiv.org/html/2610.33381#S6.E20)\) obey

xt\+1=xt−ηt​dt\+β~t​\(xt−xt−1\),ηt=γtt\+1,β~t=t−1t\+1,x\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}d\_\{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\},withx0=x1x\_\{0\}=x\_\{1\}\. In the velocity conventionvt\+1=βt​vt\+dtv\_\{t\+1\}=\\beta\_\{t\}v\_\{t\}\+d\_\{t\},xt\+1=xt−ηt​vt\+1x\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}v\_\{t\+1\},v1=0v\_\{1\}=0, the equivalent parameters areβ1=0\\beta\_\{1\}=0and

βt=t−1tγt−1γt,αp2​t≤1−βt≤1t\(t≥2\),αp=p−1p\.\\beta\_\{t\}=\\frac\{t\-1\}\{t\}\\frac\{\\gamma\_\{t\-1\}\}\{\\gamma\_\{t\}\},\\qquad\\frac\{\\alpha\_\{p\}\}\{2t\}\\leq 1\-\\beta\_\{t\}\\leq\\frac\{1\}\{t\}\\quad\(t\\geq 2\),\\qquad\\alpha\_\{p\}=\\frac\{p\-1\}\{p\}\.The step sizes are uniformly bounded bya/\(8​L​h2\)a/\(8Lh^\{2\}\)\.

ProofUsezt−xt=\(t−1\)​\(xt−xt−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\}\. Forr⁡\(s\)=max⁡\{4​L​R,σ​s1/p\}​\(h\+log⁡s\)2r\(s\)=\\max\\\{4LR,\\sigma s^\{1/p\}\\\}\(h\+\\log s\)^\{2\},γt=a​R/r⁡\(t\)\\gamma\_\{t\}=aR/r\(t\), and almost everywhere

0≤d​log⁡r​\(s\)d​log⁡s≤1p\+2h≤1−αp2\.0\\leq\\frac\{d\\log r\(s\)\}\{d\\log s\}\\leq\\frac\{1\}\{p\}\+\\frac\{2\}\{h\}\\leq 1\-\\frac\{\\alpha\_\{p\}\}\{2\}\.Integrating over\[t−1,t\]\[t\-1,t\]proves

t−1t≤βt≤\(t−1t\)αp/2<1\.\\frac\{t\-1\}\{t\}\\leq\\beta\_\{t\}\\leq\\left\(\\frac\{t\-1\}\{t\}\\right\)^\{\\alpha\_\{p\}/2\}<1\.Concavity ofu↦uαp/2u\\mapsto u^\{\\alpha\_\{p\}/2\}yields the asserted lower bound on1−βt1\-\\beta\_\{t\}; the upper bound is immediate\. The bound on the step sizes follows fromλt≥4​L​R\\lambda\_\{t\}\\geq 4LRandt\+1≥2t\+1\\geq 2\.■\\blacksquare

###### Proposition 25\(Fixed momentum coefficient with unbounded step sizes\)\.

For every fixedb∈\(0,1\)b\\in\(0,1\), the trajectory in Theorem[9](https://arxiv.org/html/2610.33381#Thmtheorem9)admits the exact representation

wt\+1=b​wt\+clip⁡\(gt,Λt\),xt\+1=xt−Ht​wt\+1,w1=0,w\_\{t\+1\}=bw\_\{t\}\+\\operatorname\{clip\}\(g\_\{t\},\\Lambda\_\{t\}\),\\qquad x\_\{t\+1\}=x\_\{t\}\-H\_\{t\}w\_\{t\+1\},\\qquad w\_\{1\}=0,with deterministic finite step sizesHt→∞H\_\{t\}\\to\\inftyand clipping thresholdsΛt\\Lambda\_\{t\}that may depend on the current stochastic gradient\. In particular, a constant momentum coefficientb∈\(0,1\)b\\in\(0,1\)does not by itself force theβp\\beta\_\{p\}barrier if exponentially growing step sizesHtH\_\{t\}and clipping thresholds depending on the current gradient are permitted\. BecauseHtH\_\{t\}grows exponentially, it violates the polynomial bound on the step sizes in Theorem[7](https://arxiv.org/html/2610.33381#Thmtheorem7), so some restriction on the growth of the step sizes is needed there\.

ProofSet

H1=γ12​\(1−b\)2,Ht=H1​2​b−\(t−1\)t⁡\(t\+1\),st=t​γt​bt−12​H1,Λt=st​min⁡\{‖gt‖,λt\}\.H\_\{1\}=\\frac\{\\gamma\_\{1\}\}\{2\(1\-b\)^\{2\}\},\\quad H\_\{t\}=H\_\{1\}\\frac\{2b^\{\-\(t\-1\)\}\}\{t\(t\+1\)\},\\quad s\_\{t\}=\\frac\{t\\gamma\_\{t\}b^\{t\-1\}\}\{2H\_\{1\}\},\\quad\\Lambda\_\{t\}=s\_\{t\}\\min\\\{\\\|g\_\{t\}\\\|,\\lambda\_\{t\}\\\}\.Sinceγt≤γ1\\gamma\_\{t\}\\leq\\gamma\_\{1\}and∑t≥1t​bt−1=\(1−b\)−2\\sum\_\{t\\geq 1\}tb^\{t\-1\}=\(1\-b\)^\{\-2\},0<st≤10<s\_\{t\}\\leq 1\. Thereforeclip⁡\(gt,Λt\)=st​dt\\operatorname\{clip\}\(g\_\{t\},\\Lambda\_\{t\}\)=s\_\{t\}d\_\{t\}\. Att=1t=1the displacement is−γ1d1/2\-\\gamma\_\{1\}d\_\{1\}/2\. Fort≥2t\\geq 2, eliminatingwtw\_\{t\}gives

xt\+1−xt=b​HtHt−1​\(xt−xt−1\)−Ht​st​dt=t−1t\+1​\(xt−xt−1\)−γtt\+1​dt\.x\_\{t\+1\}\-x\_\{t\}=b\\frac\{H\_\{t\}\}\{H\_\{t\-1\}\}\(x\_\{t\}\-x\_\{t\-1\}\)\-H\_\{t\}s\_\{t\}d\_\{t\}=\\frac\{t\-1\}\{t\+1\}\(x\_\{t\}\-x\_\{t\-1\}\)\-\\frac\{\\gamma\_\{t\}\}\{t\+1\}d\_\{t\}\.This is exactly Proposition[24](https://arxiv.org/html/2610.33381#Thmtheorem24), path by path\. AlsoHt→∞H\_\{t\}\\to\\inftyexponentially\. Whengt=0g\_\{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\.■\\blacksquare

*Comparison with existing averaging methods\.*[Nguyen et al\. \[2023, Theorems C\.2 and D\.1\(2\)\]](https://arxiv.org/html/2610.33381#bib.bib44)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‖zt−x⋆‖≤2​R\\\|z\_\{t\}\-x^\{\\star\}\\\|\\leq 2Ron nested events over each finite prefix\. Combining their query relationxt=\(1−at\)​yt\+at​ztx\_\{t\}=\(1\-a\_\{t\}\)y\_\{t\}\+a\_\{t\}z\_\{t\}\(at=2/\(t\+1\)a\_\{t\}=2/\(t\+1\)\) with convexity andLL\-smoothness atx⋆x^\{\\star\}gives

f⁡\(xT\+1\)−f⋆≤f⁡\(yT\+1\)−f⋆\+4​L​R2T\+2\.f\(x\_\{T\+1\}\)\-f^\{\\star\}\\leq f\(y\_\{T\+1\}\)\-f^\{\\star\}\+\\frac\{4LR^\{2\}\}\{T\+2\}\.Intersecting these nested events yields a time\-uniform guarantee at the query statexT\+1x\_\{T\+1\}as well, although their three\-sequence accelerated scheme differs from the two\-sequence recursion \([20](https://arxiv.org/html/2610.33381#S6.E20)\)\. The high\-probability regret bounds of[Zhang and Cutkosky \[2022, Theorems 4 and 5\]](https://arxiv.org/html/2610.33381#bib.bib68)assume bounded expected gradients and a horizon\-dependent learner\.