Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness

# Why Clipping Matters in AdaGrad?Toward a High-Probability Theory under Generalized Smoothness
Source: [https://arxiv.org/html/2609.30276](https://arxiv.org/html/2609.30276)
Ayaan MohdAffiliation:Undergraduate Program, IISc BengaluruHarshit RawatAffiliation:Department of Computational Data Sciences, IISc BengaluruArnab RoyAffiliation:Robert Bosch Center for Cyber Physical Systems, IISc BengaluruAffiliation:Department of Computer Science and Automation, IISc BengaluruMayank BaranwalAffiliation:Tata Consultancy Services Research, MumbaiAffiliation:System and Control Engineering, IIT Bombay\{alokendum, ayaanmohd, harshitrawat, arnabroy, prathore\}@iisc\.ac\.inbaranwal\.mayank@tcs\.com,mbaranwal@iitb\.ac\.inPunit RathoreAffiliation:Robert Bosch Center for Cyber Physical Systems, IISc BengaluruAffiliation:Centre for Infrastructure, Sustainable Transportation and Urban Planning, IISc Bengaluru

###### Abstract

We analyze the original same\-step coordinate\-wise AdaGrad under generalized smoothness and heavy\-tailed noise with bounded variance\. In this setting, local curvature may grow sub\-quadratically with the gradient norm, and stochastic gradients are assumed to have only bounded conditional second moments\. We show that unclipped AdaGrad can become*anisotropically miscalibrated*: under heavy\-tailed noise, the adaptive denominator can learn the geometry of rare noise shocks rather than the local curvature of the objective, leading to a persistent directional distortion that blocks finite\-horizon Euclidean progress\. We then prove that clipping repairs this failure mode\. Our main result is a finite\-horizon high\-probability guarantee for the original non\-lagged AdaGrad update, yielding1T​∑t=0T−1‖∇f​\(xt\)‖2=𝒪⁡\(d⁡\(log⁡T\+log⁡1δ\)T\),\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}=\\mathcal\{O\}\\left\(\\frac\{d\\big\(\\sqrt\{\\log T\}\+\\log\\frac\{1\}\{\\delta\}\\big\)\}\{\\sqrt\{T\}\}\\right\),and hence𝒪~​\(ε−2\)\\widetilde\{\\mathcal\{O\}\}\(\\varepsilon^\{\-2\}\)complexity\. This shows that, for AdaGrad under heavy\-tailed noise, clipping is a structural stabilizer of the adaptive geometry rather than merely a robustness heuristic\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2609.30276#S1)1. [1\.1Our Contributions](https://arxiv.org/html/2609.30276#S1.SS1) 2. [1\.2Preliminaries](https://arxiv.org/html/2609.30276#S1.SS2)1. [1\.2\.1Generalized Smoothness](https://arxiv.org/html/2609.30276#S1.SS2.SSS1)
2. [2Anistropic Miscalibration and The Failure of AdaGrad](https://arxiv.org/html/2609.30276#S2)
3. [3Related Work](https://arxiv.org/html/2609.30276#S3)
4. [4New Upper Bounds](https://arxiv.org/html/2609.30276#S4)1. [4\.1Pathwise Localization](https://arxiv.org/html/2609.30276#S4.SS1) 2. [4\.2Calibrating Parameters](https://arxiv.org/html/2609.30276#S4.SS2)
5. [5Discussion of the Results and Conclusion](https://arxiv.org/html/2609.30276#S5)
6. [References](https://arxiv.org/html/2609.30276#bib)
7. [AProofs](https://arxiv.org/html/2609.30276#A1)1. [A\.1Anisotropic Miscalibration and Failure of AdaGrad](https://arxiv.org/html/2609.30276#A1.SS1) 2. [A\.2Proofs of Auxiliary Lemmas](https://arxiv.org/html/2609.30276#A1.SS2)1. [A\.2\.1Proof of Lemma](https://arxiv.org/html/2609.30276#A1.SS2.SSS1) 2. [A\.2\.2Bounding⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\right\\rangle\}](https://arxiv.org/html/2609.30276#A1.SS2.SSS2) 3. [A\.2\.3Bounding∑t<τEt\\sum\_\{t<\\tau\}E\_\{t\}](https://arxiv.org/html/2609.30276#A1.SS2.SSS3) 4. [A\.2\.4Bounding∑t<τ‖Dt\+1−1​g~t‖2\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}](https://arxiv.org/html/2609.30276#A1.SS2.SSS4) 5. [A\.2\.5Bounding∑t<τMt\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}M\_\{t\}\}](https://arxiv.org/html/2609.30276#A1.SS2.SSS5) 6. [A\.2\.6High probability upper bound onDtD\_\{t\}](https://arxiv.org/html/2609.30276#A1.SS2.SSS6) 7. [A\.2\.7Proof of Lemma](https://arxiv.org/html/2609.30276#A1.SS2.SSS7) 3. [A\.3Proof of Theorem](https://arxiv.org/html/2609.30276#A1.SS3)1. [A\.3\.1Discussion on specific choice ofF∘=2​Δ0F^\{\\circ\}=2\\Delta\_\{0\}](https://arxiv.org/html/2609.30276#A1.SS3.SSS1)

## 1Introduction

In this paper, we study the following optimization problem

minx∈𝒳⁡f⁡\(x\),\\min\_\{x\\in\\mathcal\{X\}\}f\(x\),\(1\)where𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}is the domain offf\. Classical textbook analyses\[[39](https://arxiv.org/html/2609.30276#bib.bib1);[40](https://arxiv.org/html/2609.30276#bib.bib53)\]of \([1](https://arxiv.org/html/2609.30276#S1.E1)\) often require the Lipschitz smoothness condition, which assumes‖∇2f​\(x\)‖≤L\\\|\\nabla^\{2\}f\(x\)\\\|\\leq Lalmost everywhere for someL≥0L\\geq 0called the smoothness constant\. This condition is restrictive: it imposes a single global curvature scale and implies that the objective is locally controlled above and below by quadratic models\.It effectively restricts the objective to a geometry whose curvature is globally controlled by a single number, and therefore excludes many functions whose local curvature naturally changes with the scale of the gradient\. In problems arising from modern machine learning, this rigidity is often difficult to justify\[[59](https://arxiv.org/html/2609.30276#bib.bib2);[14](https://arxiv.org/html/2609.30276#bib.bib3);[54](https://arxiv.org/html/2609.30276#bib.bib4);[50](https://arxiv.org/html/2609.30276#bib.bib9)\]\. The geometry seen by the iterates is typically far from uniform, and the relevant question is not whether the objective is globally well\-approximated by a quadratic everywhere, but whether it admits a useful*local*smoothness description along the optimization path\.

Recently,[25](https://arxiv.org/html/2609.30276#bib.bib10)proposed a generalized smoothness framework that relaxes global Lipschitz smoothness by allowing curvature to scale with the gradient,‖∇2f​\(x\)‖≤ℓ⁡\(‖∇f​\(x\)‖\)\\\|\\nabla^\{2\}f\(x\)\\\|\\leq\\ell\(\\\|\\nabla f\(x\)\\\|\), whereℓ\\ellis nondecreasing and typically sub\-quadratic\. This framework covers objectives beyond globally smooth ones and includes, as special or related cases, several relaxed smoothness models such as\(L0,L1\)\(L\_\{0\},L\_\{1\}\)\-smoothness\[[59](https://arxiv.org/html/2609.30276#bib.bib2)\]\. More importantly, it changes the logic of the analysis: rather than assuming a fixed global curvature bound, one controls the trajectory, derives gradient bounds from sublevel\-set control, and thereby obtains an effective local smoothness constant along the path\. In this sense, generalized smoothness replaces a static global geometry by a*trajectory\-dependent*one\.

This trajectory\-dependent perspective makes adaptive methods such as AdaGrad\[[48](https://arxiv.org/html/2609.30276#bib.bib40);[12](https://arxiv.org/html/2609.30276#bib.bib15)\]and Adam\[[24](https://arxiv.org/html/2609.30276#bib.bib16)\]especially natural for modern machine\-learning objectives\[[51](https://arxiv.org/html/2609.30276#bib.bib41);[56](https://arxiv.org/html/2609.30276#bib.bib42);[42](https://arxiv.org/html/2609.30276#bib.bib43);[28](https://arxiv.org/html/2609.30276#bib.bib44);[1](https://arxiv.org/html/2609.30276#bib.bib45);[31](https://arxiv.org/html/2609.30276#bib.bib46);[46](https://arxiv.org/html/2609.30276#bib.bib47);[34](https://arxiv.org/html/2609.30276#bib.bib48);[37](https://arxiv.org/html/2609.30276#bib.bib49);[47](https://arxiv.org/html/2609.30276#bib.bib50)\]\. If the local geometry changes with the gradient scale, then algorithms that rescale their steps according to observed gradient magnitudes should, at least in principle, be better matched to the landscape than fixed\-step methods\. AdaGrad is the canonical example: it accumulates coordinate\-wise squared gradients and uses them to define an adaptive diagonal metric\. In benign stochastic regimes, this mechanism can be interpreted as learning a useful coordinate\-wise scale for the problem\. Under heavy\-tailed noise, however, this interpretation becomes questionable\. The accumulator does not observe curvature directly; it observes squared stochastic gradients\. Our results show that rare extreme realizations can dominate particular coordinates, causing the learned metric to reflect the noise anisotropy over the objective anisotropy\.

Algorithm 1AdaGrad\[[12](https://arxiv.org/html/2609.30276#bib.bib15)\]\(Clipped and Unclipped\)1:Input:Initial

x0∈ℝdx\_\{0\}\\in\\mathbb\{R\}^\{d\}, accumulator

y0=yinit​𝟏y\_\{0\}=y\_\{\\mathrm\{init\}\}\\mathbf\{1\}, stepsize

h\>0h\>0, parameter

ϵ0\>0\\epsilon\_\{0\}\>0, clipping threshold

C\>0C\>0
2:for

t=0,1,…,T−1t=0,1,\\dots,T\-1do

3:

gt=∇f​\(xt\)\+ξtg\_\{t\}=\\nabla f\(x\_\{t\}\)\+\\xi\_\{t\}
4:

yt\+1≔yt\+gt⊙2y\_\{t\+1\}\\coloneqq y\_\{t\}\+g\_\{t\}^\{\\odot 2\}
5:

Dt\+1≔diag⁡\(yt\+1\+ϵ0\)D\_\{t\+1\}\\coloneqq\\operatorname\{diag\}\(\\sqrt\{y\_\{t\+1\}\}\+\\epsilon\_\{0\}\)
6:

xt\+1≔xt−h​Dt\+1−1​gtx\_\{t\+1\}\\coloneqq x\_\{t\}\-hD\_\{t\+1\}^\{\-1\}g\_\{t\}
7:endfor

This issue is not visible in the classical smooth theory at the level we need here\. Existing lower\-bound results for AdaGrad already reveal several distinct pathologies, but they do so from perspectives different from ours\. In the heavy\-tailed setting,[7](https://arxiv.org/html/2609.30276#bib.bib17)show that*AdaGrad\-Norm*and*Adam\-Norm*\(with and without delay\) can have provably poor high\-probability convergence, and that gradient clipping restores polylogarithmic dependence on the confidence level\. In the relaxed\-smoothness setting,[9](https://arxiv.org/html/2609.30276#bib.bib51)prove complexity lower bounds for several AdaGrad variants under\(L0,L1\)\(L\_\{0\},L\_\{1\}\)\-smoothness\[[59](https://arxiv.org/html/2609.30276#bib.bib2)\], showing that the dependence onΔ,L0,L1\\Delta,L\_\{0\},L\_\{1\}can be intrinsically worse than in the globally smooth case\. Under a different refined anisotropic model,[22](https://arxiv.org/html/2609.30276#bib.bib52)provide supporting lower bounds specific to AdaGrad to show tightness of their upper bounds and to separate AdaGrad from SGD\. These results are important, but they leave open a different question that becomes central in the generalized\-smoothness regime studied here:

> What geometric object is the unclipped adaptive metric actually learning?

Since generalized\-smoothness descent is local and path\-dependent, it is not enough for the adaptive denominator to merely stay finite; it must encode the*right directional scale*\. Our point is that, without clipping, this can fail in a sharper way than mere slowdown: the adaptive metric can become dominated by anisotropy in the noise rather than anisotropy in the objective\.

This leads to the central questions of the paper:

> Can unclipped AdaGrad preserve the correct adaptive geometry under generalized smoothness and heavy\-tailed noise? If not, can clipping repair this failure and yield finite\-horizon high\-probability guarantees?

Our answer is negative to the first question and positive to the second\.

### 1\.1Our Contributions

The main contributions of this work are summarized below\. We emphasize that the principal contribution of this paper is theoretical: we provide an in\-depth analysis of clipping mechanisms within established adaptive methods like AdaGrad, without aiming to present an empirical study\.

- •Negative Result for AdaGrad \(Proposition[1](https://arxiv.org/html/2609.30276#Thmproposition1)\)\.We prove a finite\-horizon lower bound showing that, under anisotropic heavy\-tailed noise, AdaGrad can mislearn the problem geometry\. Specifically, we construct a convex stochastic optimization problem with bounded conditional second moments in which a single rare shock distorts the adaptive denominator in the wrong coordinate and keeps the Euclidean stationarity average bounded away from zero\.
- •Clipping fixes AdaGrad and New Upper Bounds \(Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1)\)\.We show that gradient clipping repairs this failure mode\. Under sub\-quadratic generalized smoothness and heavy\-tailed noise with bounded conditional second moments, we prove a finite\-horizon high\-probability convergence guarantee for the original clipped AdaGrad update, yielding a𝒪~​\(ε−2\)\\widetilde\{\\mathcal\{O\}\}\(\\varepsilon^\{\-2\}\)complexity bound with polylogarithmic dependence on the failure probability\.
- •Analytical Parameter Regimes \(Section[4\.2](https://arxiv.org/html/2609.30276#S4.SS2)\)\.We provide explicit, theoretically constructible bounds for the stepsize, clipping level, and warm start\. This shows that trueε\\varepsilon\-target Euclidean stationarity is theoretically attainable under a strict, mathematically defined regime, solidifying the high\-probability bounds into a complete non\-asymptotic guarantee\.
- •Novel Proof Architecture for Same\-Step Updates \(Lemma[4](https://arxiv.org/html/2609.30276#Thmlemma4)\)\.A major theoretical hurdle in analyzing AdaGrad is the correlation between the current gradient and the concurrent adaptive denominatorDt\+1−1D\_\{t\+1\}^\{\-1\}\[[52](https://arxiv.org/html/2609.30276#bib.bib26);[15](https://arxiv.org/html/2609.30276#bib.bib19)\]\. We resolve this by cleanly decoupling the historical metric from the same\-step correction, bounding the latter via a deterministic telescoping argument\.

Most stochastic optimization guarantees are stated in expectation \(e\.g\.,𝔼​‖∇f​\(x\)‖2≤ε\\mathbb\{E\}\\\|\\nabla f\(x\)\\\|^\{2\}\\leq\\varepsilon\), obscuring the algorithm’s pathwise behavior\. Markov conversions give high probability only by requiring expected accuracyε​δ\\varepsilon\\delta; since standard nonconvex complexities scale as𝒪⁡\(ε−2\)\\mathcal\{O\}\(\\varepsilon^\{\-2\}\), this leads to a prohibitive𝒪⁡\(ε−2​δ−2\)\\mathcal\{O\}\(\\varepsilon^\{\-2\}\\delta^\{\-2\}\)dependence\. A meaningful high\-probability theory should instead incur only polylogarithmic dependence on1/δ1/\\delta\. This is challenging for adaptive methods because stepsizes are random and require pathwise control\[[30](https://arxiv.org/html/2609.30276#bib.bib18);[3](https://arxiv.org/html/2609.30276#bib.bib20);[7](https://arxiv.org/html/2609.30276#bib.bib17)\]\. In AdaGrad, the main obstacle is*same\-step dependence*: the metricDt\+1−1D\_\{t\+1\}^\{\-1\}uses the same stochastic gradient as the update\. Consequently, many prior analyses use delayed variants to recover conditional independence\[[29](https://arxiv.org/html/2609.30276#bib.bib21);[30](https://arxiv.org/html/2609.30276#bib.bib18);[15](https://arxiv.org/html/2609.30276#bib.bib19);[45](https://arxiv.org/html/2609.30276#bib.bib35);[4](https://arxiv.org/html/2609.30276#bib.bib34);[7](https://arxiv.org/html/2609.30276#bib.bib17)\]\. We analyze the original non\-lagged update directly\. Gradient clipping controls heavy\-tailed noise, while a deterministic telescoping argument isolates the same\-step correction, yielding a genuine𝒪~​\(ε−2​log⁡\(1/δ\)\)\\widetilde\{\\mathcal\{O\}\}\(\\varepsilon^\{\-2\}\\log\(1/\\delta\)\)complexity bound without delays or average\-case reductions\.

### 1\.2Preliminaries

In this section, we define the noise model and the class of functions to which the objectiveffbelongs\.

###### Assumption 1\.

The objective functionffis differentiable and closed within its open domaindom​\(f\)⊆ℝd\\text\{dom\}\(f\)\\subseteq\\mathbb\{R\}^\{d\}and is bounded from below, i\.e\.,f∗≔infxf⁡\(x\)\>−∞f^\{\*\}\\coloneqq\\inf\_\{x\}f\(x\)\>\-\\infty\.

#### 1\.2\.1Generalized Smoothness

We now formally introduce the generalized smoothness condition[25](https://arxiv.org/html/2609.30276#bib.bib10), and present its properties\.

###### Definition 1\(ℓ\\ell\-smoothness\)\.

A real\-valued differentiable functionf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}isℓ\\ell\-smooth for some non\-decreasing continuous functionℓ:\[0,\+∞\)→\(0,\+∞\)\\ell:\[0,\+\\infty\)\\to\(0,\+\\infty\)if

‖∇2f​\(x\)‖≤ℓ⁡\(‖∇f​\(x\)‖\)\\\|\\nabla^\{2\}f\(x\)\\\|\\leq\\ell\(\\\|\\nabla f\(x\)\\\|\)almost everywhere \(with respect to the Lebesgue measure\) in𝒳\\mathcal\{X\}\.

First, we provide the following lemma, which is very useful in our analyses in this paper\.

###### Lemma 1\([25](https://arxiv.org/html/2609.30276#bib.bib10)\)\.

Ifffisℓ\\ell\-smooth, for anyx∈𝒳x\\in\\mathcal\{X\}satisfying‖∇f​\(x\)‖≤G\\\|\\nabla f\(x\)\\\|\\leq G, we have \(1\)ℬ⁡\(x,G/L\)⊆𝒳\\mathcal\{B\}\(x,G/L\)\\subseteq\\mathcal\{X\}, and \(2\) for anyx1,x2∈ℬ⁡\(x,G/L\)x\_\{1\},x\_\{2\}\\in\\mathcal\{B\}\(x,G/L\),

‖∇f​\(x1\)−∇f​\(x2\)‖≤L​‖x1−x2‖,f⁡\(x1\)≤f⁡\(x2\)\+⟨∇f​\(x2\),x1−x2⟩\+L2​‖x1−x2‖2,\\\|\\nabla f\(x\_\{1\}\)\-\\nabla f\(x\_\{2\}\)\\\|\\leq L\\\|x\_\{1\}\-x\_\{2\}\\\|,\\quad f\(x\_\{1\}\)\\leq f\(x\_\{2\}\)\+\\langle\\nabla f\(x\_\{2\}\),x\_\{1\}\-x\_\{2\}\\rangle\+\\frac\{L\}\{2\}\\\|x\_\{1\}\-x\_\{2\}\\\|^\{2\},\(2\)whereL≔ℓ⁡\(2​G\)L\\coloneqq\\ell\(2G\)andℬ⁡\(x,R\)\\mathcal\{B\}\(x,R\)denotes euclidean ball with radiusRRand center atxx\.

Lemma[1](https://arxiv.org/html/2609.30276#Thmlemma1)states that, if the gradient atxxis bounded by some constantGG, then within its neighborhood with a radiusG/LG/L, we can obtain \([2](https://arxiv.org/html/2609.30276#S1.E2)\), the same inequalities that were derived in the textbook analyses\[[40](https://arxiv.org/html/2609.30276#bib.bib53)\]under the standard Lipschitz smoothness condition\. With \([2](https://arxiv.org/html/2609.30276#S1.E2)\), the analysis for generalized smoothness is not much harder than that for standard smoothness\. Since we mostly choosex=x2=xtx=x\_\{2\}=x\_\{t\}andx1=xt\+1x\_\{1\}=x\_\{t\+1\}in the analysis, in order to applyLemma[1](https://arxiv.org/html/2609.30276#Thmlemma1), we need two conditions:‖∇f​\(xt\)‖≤G\\\|\\nabla f\(x\_\{t\}\)\\\|\\leq Gand‖xt\+1−xt‖≤G/L\\\|x\_\{t\+1\}\-x\_\{t\}\\\|\\leq G/Lfor some constantGG\. The latter is usually directly implied by the former for most deterministic methods with a sufficiently small step size; furthermore, the former can be obtained via the approach by[25](https://arxiv.org/html/2609.30276#bib.bib10), which bounds the gradients along the trajectory\. We show it in the following lemma\.

###### Lemma 2\([25](https://arxiv.org/html/2609.30276#bib.bib10)\)\.

Assumeffisℓ\\ell\-smooth with sub\-quadraticℓ\\ell\. Iff⁡\(x\)−f⋆≤Ff\(x\)\-f^\{\\star\}\\leq Ffor somex∈𝒳x\\in\\mathcal\{X\}andF≥0F\\geq 0, defineG≔sup\{u≥0:u2≤2​ℓ​\(2​u\)​F\},G\\coloneqq\\sup\\Big\\\{u\\geq 0:\\ u^\{2\}\\leq 2\\,\\ell\(2u\)\\,F\\Big\\\},L≔ℓ⁡\(2​G\),L\\coloneqq\\ell\(2G\),then they satisfyG2=2​ℓ​\(2​G\)​FG^\{2\}=2\\ell\(2G\)Fand we haveG<∞G<\\inftyand‖∇f​\(x\)‖≤G\\\|\\nabla f\(x\)\\\|\\leq G\.

Therefore, in order to bound the gradients along the trajectory as we discussed inLemma[2](https://arxiv.org/html/2609.30276#Thmlemma2), it suffices to bound the function values, which is usually easier\.

###### Assumption 2\.

The objective functionffisℓ\\ell\-smooth with subquadraticℓ\\ell\.

The standard smooth function class is very restrictive as it only contains functions that are upper and lower bounded by quadratic functions\. The\(L0,L1\)\(L\_\{0\},L\_\{1\}\)smooth function class[59](https://arxiv.org/html/2609.30276#bib.bib2)is more general since it also contains, e\.g\., univariate polynomials and exponential functions\. Assumption[2](https://arxiv.org/html/2609.30276#Thmassumption2)is even more general and contains univariate rational functions, double exponential functions, etc\. Next, we make a standard assumption on the gradient noise model\.

At each iterationtt, we observe a stochastic gradientgt=∇f​\(xt\)\+ξtg\_\{t\}=\\nabla f\(x\_\{t\}\)\+\\xi\_\{t\}\. Hereξ\\xiis a random variable following some distribution that may be dependent onxxand time\. We define the filtrationℱt≔σ⁡\(g0,…,gt\)\\mathcal\{F\}\_\{t\}\\coloneqq\\sigma\(g\_\{0\},\\dots,g\_\{t\}\)and denote the conditional expectation as𝔼t−1\[⋅\]≔𝔼\[⋅\|ℱt−1\]\\mathbb\{E\}\_\{t\-1\}\[\\cdot\]\\coloneqq\\mathbb\{E\}\[\\cdot\|\\mathcal\{F\}\_\{t\-1\}\]\.gtg\_\{t\}might be unbounded due to potentially unbounded gradient noise\.

###### Assumption 3\([38](https://arxiv.org/html/2609.30276#bib.bib54);[16](https://arxiv.org/html/2609.30276#bib.bib55);[49](https://arxiv.org/html/2609.30276#bib.bib56);[25](https://arxiv.org/html/2609.30276#bib.bib10)\)\.

𝔼t−1​\[ξt\]=0\\mathbb\{E\}\_\{t\-1\}\[\\xi\_\{t\}\]=0and𝔼t−1​\[‖ξt‖2\]≤σ2\\mathbb\{E\}\_\{t\-1\}\[\\\|\\xi\_\{t\}\\\|^\{2\}\]\\leq\\sigma^\{2\}for someσ≥0\\sigma\\geq 0\.

## 2Anistropic Miscalibration and The Failure of AdaGrad

We demonstrate a negative convergence result for AdaGrad \(Algorithm[1](https://arxiv.org/html/2609.30276#alg1)\) caused by*anisotropic miscalibration*\. Heavy\-tailed noise in flat directions can dominate the adaptive metric, severely under\-updating steeper directions and misaligning with local geometry\.

###### Proposition 1\(Anisotropic miscalibration lower bound for AdaGrad\)\.

Let

f⁡\(x1,x2\)=14​x14\+12​x12\+8​x22f\(x\_\{1\},x\_\{2\}\)=\\frac\{1\}\{4\}x\_\{1\}^\{4\}\+\\frac\{1\}\{2\}x\_\{1\}^\{2\}\+8x\_\{2\}^\{2\}andx0=\(2,1\)x\_\{0\}=\(2,1\)\. RunAlgorithm[1](https://arxiv.org/html/2609.30276#alg1)withd=2d=2,h=1h=1,yinit=0y\_\{\\mathrm\{init\}\}=0, andϵ0=1\\epsilon\_\{0\}=1\. For every horizonT≥2T\\geq 2and every noise scaleσ\>0\\sigma\>0, there exists a stochastic oracle satisfying Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)with noise levelσ\\sigmasuch that, with probability at leastpT≔σ2\(32​\(T−1\)−10\)2\+σ2,p\_\{T\}\\coloneqq\\frac\{\\sigma^\{2\}\}\{\\bigl\(32\(T\-1\)\-10\\bigr\)^\{2\}\+\\sigma^\{2\}\},the following inequalities hold simultaneously for everyt=1,…,T−1t=1,\\dots,T\-1:

∂112f⁡\(xt\)<∂222f⁡\(xt\),\(Dt\)11\>169​\(T−1\)​\(Dt\)22,‖∇f​\(xt\)‖\>1\.\\partial\_\{11\}^\{2\}f\(x\_\{t\}\)<\\partial\_\{22\}^\{2\}f\(x\_\{t\}\),\\qquad\(D\_\{t\}\)\_\{11\}\>\\frac\{16\}\{9\}\(T\-1\)\(D\_\{t\}\)\_\{22\},\\qquad\\\|\\nabla f\(x\_\{t\}\)\\\|\>1\.Consequently, since‖∇f​\(x0\)‖\>1\\\|\\nabla f\(x\_\{0\}\)\\\|\>1, we haveℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2\>1\)≥pT\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\>1\\right\)\\geq p\_\{T\}\. Therefore, any uniform guarantee of the formℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2≤1\)≥1−δ\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq 1\\right\)\\geq 1\-\\deltaover all stochastic oracles satisfying Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)requiresT≥1\+132​\(10\+σ​1−δδ\)T\\geq 1\+\\frac\{1\}\{32\}\\left\(10\+\\sigma\\sqrt\{\\frac\{1\-\\delta\}\{\\delta\}\}\\right\)\.

###### Proof Sketch\.

We construct a heavy\-tailed oracle triggering a shockξ0=\(B,0\)\\xi\_\{0\}=\(B,0\)with probabilitypT=𝒪⁡\(σ2/B2\)p\_\{T\}=\\mathcal\{O\}\(\\sigma^\{2\}/B^\{2\}\), permanently inflating the adaptive metric to\(Dt\)11=Ω⁡\(T\)\(D\_\{t\}\)\_\{11\}=\\Omega\(T\)\. Under noiseless subsequent updates, the second coordinate contracts exponentially while the penalized first coordinate stalls \(xt,1\>7/8x\_\{t,1\}\>7/8\), establishing a strict anisotropic mismatch\(Dt\)11≫\(Dt\)22\(D\_\{t\}\)\_\{11\}\\gg\(D\_\{t\}\)\_\{22\}\. This learned metric inversion prevents Euclidean convergence, bounding the gradient norm‖∇f​\(xt\)‖\>1\\\|\\nabla f\(x\_\{t\}\)\\\|\>1for allt<Tt<T\. Forcing the stationarity failure probabilitypT≤δp\_\{T\}\\leq\\deltaalgebraically isolatesBBand mandates the finite\-horizon lower boundT=Ω⁡\(σ​1/δ\)T=\\Omega\\bigl\(\\sigma\\sqrt\{1/\\delta\}\\bigr\)\.*Proof is deferred to Appendix[A\.1](https://arxiv.org/html/2609.30276#A1.SS1)\.*∎

While\[[7](https://arxiv.org/html/2609.30276#bib.bib17), Theorem 2\.1\]shows that heavy\-tailed noise slows AdaGrad’s concentration, Proposition[1](https://arxiv.org/html/2609.30276#Thmproposition1)reveals a more fundamental obstruction: an irreversible collapse of the algorithm’s geometry\. This finite\-horizon failure leaves the average gradient norm strictly bounded away from zero, establishing the structural necessity of clipping\. Rather than a mere robustness heuristic, clipping is the exact mechanism required to prevent rare shocks from permanently poisoning the adaptive denominator\. Therefore, our contributions follow a clear trajectory: we formalize this structural failure of plain AdaGrad, prove that clipping systematically removes the obstruction, and develop a novel proof architecture to analyze the exact same\-step update\.

## 3Related Work

Table 1:Summary of existing high probability convergence results for AdaGrad\.None of these works show1T∑t=1T∥∇f\(xt\)∥2=𝒪~\(T−1/2\)\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}=\\tilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)for clipped AdaGrad under generalized smoothness\.\(1\) UsesL1L\_\{1\}average gradient norm stationarity\. \(2\) They assume the objective function is uniformly upper\-bounded\.$\\$denotes that the rates are given forα=2\\alpha=2\.Adaptive Methods and Classical Smoothness\.Adaptive methods like AdaGrad[12](https://arxiv.org/html/2609.30276#bib.bib15)and Adam\[[24](https://arxiv.org/html/2609.30276#bib.bib16)\]anchor stochastic optimization\. Extensive literature analyzes variants \(e\.g\., AMSGrad, Yogi, Padam, AdaBound\) to improve convergence guarantees and practical behavior[43](https://arxiv.org/html/2609.30276#bib.bib27);[58](https://arxiv.org/html/2609.30276#bib.bib28);[5](https://arxiv.org/html/2609.30276#bib.bib33);[35](https://arxiv.org/html/2609.30276#bib.bib31)\. While their convergence theory traditionally assumes standardLL\-smoothness, studies establish sharp nonconvex guarantees for AdaGrad under relaxed assumptions[55](https://arxiv.org/html/2609.30276#bib.bib32);[52](https://arxiv.org/html/2609.30276#bib.bib26);[19](https://arxiv.org/html/2609.30276#bib.bib24)\. Similarly, Adam’s convergence has been refined under various stochastic conditions[43](https://arxiv.org/html/2609.30276#bib.bib27);[61](https://arxiv.org/html/2609.30276#bib.bib29);[11](https://arxiv.org/html/2609.30276#bib.bib22);[18](https://arxiv.org/html/2609.30276#bib.bib6)\. Generalized Smoothness and Relaxed Curvature\.Recent works replace global smoothness with generalized conditions where local smoothness scales with the gradient norm\. Introduced via\(L0,L1\)\(L\_\{0\},L\_\{1\}\)\-smoothness[59](https://arxiv.org/html/2609.30276#bib.bib2), this framework has been expanded to sub\-quadratic generalized smoothness and variance\-reduced methods[25](https://arxiv.org/html/2609.30276#bib.bib10);[6](https://arxiv.org/html/2609.30276#bib.bib14), as well as parameter\-agnostic and mirror\-descent algorithms[21](https://arxiv.org/html/2609.30276#bib.bib13);[50](https://arxiv.org/html/2609.30276#bib.bib9);[57](https://arxiv.org/html/2609.30276#bib.bib12)\. Under these relaxed conditions, AdaGrad’s convergence has been analyzed[52](https://arxiv.org/html/2609.30276#bib.bib26), with evidence that coordinate\-wise adaptivity exploits directional curvature well[32](https://arxiv.org/html/2609.30276#bib.bib25)\. Adam has similarly been proven to effectively exploit non\-uniform smoothness[26](https://arxiv.org/html/2609.30276#bib.bib11);[54](https://arxiv.org/html/2609.30276#bib.bib4);[53](https://arxiv.org/html/2609.30276#bib.bib8);[8](https://arxiv.org/html/2609.30276#bib.bib5);[18](https://arxiv.org/html/2609.30276#bib.bib6)\. Gradient Clipping and Heavy\-Tailed Noise\.Gradient clipping is widely recognized as a robust stabilizer against non\-uniform curvature and rapidly growing objectives[59](https://arxiv.org/html/2609.30276#bib.bib2);[36](https://arxiv.org/html/2609.30276#bib.bib7), including in smooth convex optimization with heavy\-tailed noise[17](https://arxiv.org/html/2609.30276#bib.bib39)\. High\-probability guarantees under heavy\-tailed noise further demonstrate that combining clipping with momentum or normalization stabilizes trajectories[10](https://arxiv.org/html/2609.30276#bib.bib36);[20](https://arxiv.org/html/2609.30276#bib.bib38);[13](https://arxiv.org/html/2609.30276#bib.bib37);[21](https://arxiv.org/html/2609.30276#bib.bib13)\. Most relevant to our work,[7](https://arxiv.org/html/2609.30276#bib.bib17)shows that clipping repairs the vulnerability of AdaGrad/Adam\-Norm to heavy\-tailed shocks, yielding polylogarithmic confidence dependence\.

## 4New Upper Bounds

The theoretical analysis in this section is therefore structured to prevent*anisotropic miscalibration*, all while retaining the exact*same\-step*AdaGrad update\. The point is not simply that clipping reduces variance\. In the present generalized\-smoothness regime, descent is local and path\-dependent, so the adaptive denominator must encode a*usable*directional scale along the entire trajectory\. Once gradients are clipped, the only new difficulty in the original non\-lagged AdaGrad update is the*same\-step coupling*between the metricDt\+1−1D\_\{t\+1\}^\{\-1\}and the current clipped gradientg~t\\tilde\{g\}\_\{t\}as mentioned in Section[1\.1](https://arxiv.org/html/2609.30276#S1.SS1)\. To be precise, at iterationtt, predictability is understood with respect to the filtrationℱt≔σ⁡\(g0,…,gt\)\\mathcal\{F\}\_\{t\}\\coloneqq\\sigma\(g\_\{0\},\\dots,g\_\{t\}\)\. SinceDtD\_\{t\}depends only on\{g~0,…,g~t−1\}\\\{\\tilde\{g\}\_\{0\},\\dots,\\tilde\{g\}\_\{t\-1\}\\\}, the matrixDt−1D\_\{t\}^\{\-1\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable\. In contrast,Dt\+1−1D\_\{t\+1\}^\{\-1\}depends on the current clipped gradientg~t\\tilde\{g\}\_\{t\}throughyt\+1=yt\+g~t⊙2y\_\{t\+1\}=y\_\{t\}\+\\tilde\{g\}\_\{t\}^\{\\odot 2\}, and is therefore onlyℱt\\mathcal\{F\}\_\{t\}\-measurable\. HenceDt\+1−1D\_\{t\+1\}^\{\-1\}is not predictable\.

Clipped Noise:We decompose the clipped gradientg~t\\tilde\{g\}\_\{t\}into a predictable mean and a martingale part\. Define the clipping residualrt≔g~t−gtr\_\{t\}\\coloneqq\\tilde\{g\}\_\{t\}\\\!\-\\\!g\_\{t\}and the predictable meanμt≔𝔼t−1​\[g~t\]=∇f​\(xt\)\+𝔼t−1​\[rt\]\\mu\_\{t\}\\coloneqq\\mathbb\{E\}\_\{t\-1\}\[\\tilde\{g\}\_\{t\}\]=\\nabla f\(x\_\{t\}\)\+\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\. Then the clipped noise,ξ~t≔g~t−μt\\tilde\{\\xi\}\_\{t\}\\\!\\coloneqq\\\!\\tilde\{g\}\_\{t\}\\\!\-\\\!\\mu\_\{t\}, satisfies𝔼t−1​\[ξ~t\]=0,‖ξ~t‖≤2​C\\mathbb\{E\}\_\{t\-1\}\[\\tilde\{\\xi\}\_\{t\}\]\\\!=\\\!0,\\\|\\tilde\{\\xi\}\_\{t\}\\\|\\leq 2C\.

Furthermore, we show that this dependence can be exactly isolated as a deterministic correction, pathwise telescoped, and absorbed through a matched warm start combined with a cubic clipping calibration\. This establishes clipping not as a generic robustness heuristic, but as a structural stabilizer of the adaptive geometry, consistent with its recent applications in high\-probability optimization under heavy\-tailed noise\[[17](https://arxiv.org/html/2609.30276#bib.bib39);[10](https://arxiv.org/html/2609.30276#bib.bib36);[7](https://arxiv.org/html/2609.30276#bib.bib17)\]\. Methodologically, our generalized\-smoothness localization adopts the trajectory\-control perspective of[25](https://arxiv.org/html/2609.30276#bib.bib10), while successfully navigating the same\-step dependence that has notoriously complicated prior AdaGrad analyses\[[52](https://arxiv.org/html/2609.30276#bib.bib26);[15](https://arxiv.org/html/2609.30276#bib.bib19);[30](https://arxiv.org/html/2609.30276#bib.bib18)\]\.

Algorithm 2Clipped AdaGrad1:Input:Initial

x0∈ℝdx\_\{0\}\\in\\mathbb\{R\}^\{d\}, accumulator

y0=yinit​𝟏y\_\{0\}=y\_\{\\mathrm\{init\}\}\\mathbf\{1\}, stepsize

h\>0h\>0, parameter

ϵ0\>0\\epsilon\_\{0\}\>0, clipping threshold

C\>0C\>0\.

2:for

t=0,1,…,T−1t=0,1,\\dots,T\-1do

3:

gt=∇f​\(xt\)\+ξtg\_\{t\}=\\nabla f\(x\_\{t\}\)\+\\xi\_\{t\}
4:

g~t=clip⁡\(gt,C\)\\tilde\{g\}\_\{t\}=\\mathrm\{clip\}\(g\_\{t\};C\)
5:

yt\+1≔yt\+g~t⊙2y\_\{t\+1\}\\coloneqq y\_\{t\}\+\\tilde\{g\}\_\{t\}^\{\\odot 2\}
6:

Dt\+1≔diag⁡\(yt\+1\+ϵ0\)D\_\{t\+1\}\\coloneqq\\operatorname\{diag\}\(\\sqrt\{y\_\{t\+1\}\}\+\\epsilon\_\{0\}\)
7:

xt\+1≔xt−h​Dt\+1−1​g~tx\_\{t\+1\}\\coloneqq x\_\{t\}\-hD\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}
8:endfor

### 4\.1Pathwise Localization

Following the generalized\-smoothness framework, we first localize the trajectory to a level set where the objective admits an effective quadratic upper model \(Lemma[1](https://arxiv.org/html/2609.30276#Thmlemma1)\)\. Fixing a toleranceF≥f⁡\(x0\)−f∗F\\geq f\(x\_\{0\}\)\-f^\{\*\}, we define a predictable stopping time for horizonT≥1T\\geq 1as follows:

τ≔min⁡\{t≤T:f⁡\(xt\)−f⋆\>F\}∧T\.\\tau\\coloneqq\\min\\\{t\\leq T:f\(x\_\{t\}\)\-f^\{\\star\}\>F\\\}\\wedge T\.We define the localized second\-moment boundV≔\(G\)2\+σ2V\\coloneqq\(G\)^\{2\}\+\\sigma^\{2\}\. Fort<τt<\\tau, Lemma[2](https://arxiv.org/html/2609.30276#Thmlemma2)gives‖∇f​\(xt\)‖≤G\\\|\\nabla f\(x\_\{t\}\)\\\|\\leq G\. Thus, the generalized\-smoothness descent lemma \(Lemma[1](https://arxiv.org/html/2609.30276#Thmlemma1)\) applies with local smoothness constantL=ℓ⁡\(2​G\)L=\\ell\(2G\)as long as the step remains within the local radiusG/LG/L\. Clipping enforces‖g~t‖≤C\\\|\\tilde\{g\}\_\{t\}\\\|\\leq C, and the warm start guaranteesDt\+1⪰D¯​ID\_\{t\+1\}\\\!\\succeq\\\!\\underline\{D\}I, whereD¯≔yinit\+ϵ0\\underline\{D\}\\\!\\coloneqq\\\!\\sqrt\{y\_\{\\mathrm\{init\}\}\}\\\!\+\\\!\\epsilon\_\{0\}\. Consequently, for every step taken by Algorithm[2](https://arxiv.org/html/2609.30276#alg2)before the trajectory leaves the level set, the following holds:

‖xt\+1−xt‖=h​‖Dt\+1−1​g~t‖≤h​‖Dt\+1−1‖​‖g~t‖≤hD¯​C≤GL\.\\\|x\_\{t\+1\}\-x\_\{t\}\\\|=h\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|\\leq h\\\|D\_\{t\+1\}^\{\-1\}\\\|\\,\\\|\\tilde\{g\}\_\{t\}\\\|\\leq\\frac\{h\}\{\\underline\{D\}\}C\\leq\\frac\{G\}\{L\}\.\(3\)Hence, the condition for the updates of Algorithm[2](https://arxiv.org/html/2609.30276#alg2)to stay inside the generalized smoothness neighborhood is

hD¯​C≤GLfor stepsizeh\>0\.\\boxed\{\\quad\\frac\{h\}\{\\underline\{D\}\}C\\leq\\frac\{G\}\{L\}\\quad\}\\quad\\text\{for stepsize $h\>0$\.\}\(4\)
We now turn to the*same\-step dependence*\. We begin by bounding the one\-step progress using the local quadratic model\. Substituting the update rulext\+1−xt=−h​Dt\+1−1​g~tx\_\{t\+1\}\-x\_\{t\}=\-hD\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}into the local descent lemma \(Lemma[1](https://arxiv.org/html/2609.30276#Thmlemma1)\), we obtain

f⁡\(xt\+1\)−f⁡\(xt\)≤−h⁡⟨∇f​\(xt\),Dt\+1−1​g~t⟩\+L2​h2​‖Dt\+1−1​g~t‖2\.f\(x\_\{t\+1\}\)\-f\(x\_\{t\}\)\\leq\-h\\langle\\nabla f\(x\_\{t\}\),D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\rangle\+\\frac\{L\}\{2\}h^\{2\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\.\(5\)
The core difficulty lies in the inner product−⟨∇f​\(xt\),Dt\+1−1​g~t⟩\-\\langle\\nabla f\(x\_\{t\}\),D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\rangle, where the metricDt\+1−1D\_\{t\+1\}^\{\-1\}is correlated withg~t\\tilde\{g\}\_\{t\}\. To break this dependence, we add and subtract the prior metricDt−1D\_\{t\}^\{\-1\}:

−⟨∇f​\(xt\),Dt\+1−1​g~t⟩=−⟨∇f​\(xt\),Dt−1​g~t⟩\+⟨∇f​\(xt\),\(Dt−1−Dt\+1−1\)​g~t⟩⏟≔Et,\-\\langle\\nabla f\(x\_\{t\}\),D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\rangle=\-\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\rangle\+\{\\color\[rgb\]\{0,0\.5,0\}\\underbrace\{\\langle\\nabla f\(x\_\{t\}\),\(D\_\{t\}^\{\-1\}\-D\_\{t\+1\}^\{\-1\}\)\\tilde\{g\}\_\{t\}\\rangle\}\_\{\\coloneqq E\_\{t\}\}\},whereEtE\_\{t\}isolates the exact algebraic penalty incurred by the same\-step correction\. To cleanly handle the predictable inner product⟨∇f​\(xt\),Dt−1​g~t⟩\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\rangleabove, we decompose the clipped gradient into its conditional mean and martingale noise asg~t=μt\+ξ~t\\tilde\{g\}\_\{t\}=\\mu\_\{t\}\+\\tilde\{\\xi\}\_\{t\}, withμt≔∇f​\(xt\)\+𝔼t−1​\[rt\]\\mu\_\{t\}\\coloneqq\\nabla f\(x\_\{t\}\)\+\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\. This allows us to define the predictable preconditioned progressAt≔⟨∇f\(xt\),Dt−1∇f\(xt\)⟩A\_\{t\}\\coloneqq\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\rangleand the stopped martingale termMt≔⟨Dt−1∇f\(xt\),ξ~t⟩M\_\{t\}\\coloneqq\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\tilde\{\\xi\}\_\{t\}\\rangle\. Substituting these extracted components back into the descent inequality \([5](https://arxiv.org/html/2609.30276#S4.E5)\) establishes an one\-step progress bound, formalized below\.

###### Lemma 3\(One\-step descent with same\-step correction\)\.

Assume \([4](https://arxiv.org/html/2609.30276#S4.E4)\), for everyt<τt<\\tau,

f\(xt\+1\)−f\(xt\)≤−hAt−h⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩−hMt\+hEt\+L2h2∥Dt\+1−1g~t∥2\.f\(x\_\{t\+1\}\)\-f\(x\_\{t\}\)\\leq\-h\{\\color\[rgb\]\{0,0\.2969,0\.6016\}A\_\{t\}\}\-h\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\rangle\}\-h\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}M\_\{t\}\}\+h\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\+\\frac\{L\}\{2\}h^\{2\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}\.

###### Proof\.

Proof is deferred to Appendix[A\.2\.1](https://arxiv.org/html/2609.30276#A1.SS2.SSS1)\. ∎

The point of Lemma[3](https://arxiv.org/html/2609.30276#Thmlemma3)is that the same\-step issue has now been reduced to a single deterministic termEt\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\. We now move to boundEt\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\.

###### Lemma 4\(Deterministic bound on the cumulative same\-step correction\)\.

For every sample path,∑t<τ\|Et\|≤d​G​CD¯\.\\sum\_\{t<\\tau\}\|\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\|\\leq\\frac\{dGC\}\{\\underline\{D\}\}\.Consequently,∑t<τEt≤d​G​CD¯\.\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\\leq\\frac\{dGC\}\{\\underline\{D\}\}\.

###### Proof Sketch\.

Sinceyt\+1,i≥yt,iy\_\{t\+1,i\}\\geq y\_\{t,i\}, we haveDt\+1,i−1≤Dt,i−1D\_\{t\+1,i\}^\{\-1\}\\leq D\_\{t,i\}^\{\-1\}\. Hence, using\|∇if​\(xt\)\|≤G\|\\nabla\_\{i\}f\(x\_\{t\}\)\|\\leq Gand\|g~t,i\|≤C\|\\tilde\{g\}\_\{t,i\}\|\\leq C,\|Et\|≤G​C​∑i=1d\(Dt,i−1−Dt\+1,i−1\)\.\|E\_\{t\}\|\\leq GC\\sum\_\{i=1\}^\{d\}\\left\(D\_\{t,i\}^\{\-1\}\-D\_\{t\+1,i\}^\{\-1\}\\right\)\.Summing overt<τ\\\!t<\\\!\\tautelescopes coordinatewise:∑t<τ\|Et\|≤G​C​∑i=1d\(D0,i−1−Dτ,i−1\)≤G​C​∑i=1dD0,i−1=d​G​CD¯\.\\sum\_\{t<\\tau\}\\\!\|E\_\{t\}\|\\\!\\leq\\\!GC\\sum\_\{i=1\}^\{d\}\\\!\\left\(D\_\{0,i\}^\{\-1\}\\\!\-\\\!D\_\{\\tau,i\}^\{\-1\}\\\!\\right\)\\\!\\leq\\\!GC\\sum\_\{i=1\}^\{d\}\\\!D\_\{0,i\}^\{\-1\}\\\!=\\\!\\frac\{dGC\}\{\\underline\{D\}\}\.Full proof is deferred to Appendix[A\.2\.3](https://arxiv.org/html/2609.30276#A1.SS2.SSS3)\. ∎

At this stage, the*same\-step*dependence has been fully isolated using Lemma[4](https://arxiv.org/html/2609.30276#Thmlemma4)\. The remaining question is*under what parameter scales*the resulting error terms of Lemma[3](https://arxiv.org/html/2609.30276#Thmlemma3)can be made compatible with a finite\-horizon Euclidean target? This is where calibration enters\. We choose the stepsize\(h\)\(h\), clipping threshold\(C\)\(C\), and warm start so thesame\-step correctionandclipping residualcan be absorbed into the high\-probability preconditioned descent bound, while converting thepreconditioned estimateto a Euclidean bound still yields a genuine finite\-horizon target\.

### 4\.2Calibrating Parameters

To explicitly motivate our hyperparameter choices, we first establish a preconditioned descent estimate up to the stopping timeτ\\tau\.

###### Lemma 5\(Summed descent inequality up toτ\\tau\)\.

Assume the neighborhood condition \([4](https://arxiv.org/html/2609.30276#S4.E4)\) holds\. Then, for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, we have

f⁡\(xτ\)−f⋆\+h2​∑t<τAt≤Δ0\+h​T​V2D¯​C2⏟clipping\-residualcontribution\+L2​h2​HT⏟generalizedsmoothness remainder\+h​d​G​CD¯⏟same\-stepcorrection\+h​Γ​log⁡\(1/δ\),f\(x\_\{\\tau\}\)\-f^\{\\star\}\+\\frac\{h\}\{2\}\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.2969,0\.6016\}A\_\{t\}\}\\leq\\Delta\_\{0\}\+\\underbrace\{\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{clipping\-residual\}\\\\ \\text\{contribution\}\\end\{subarray\}\}\}\+\\quad\\underbrace\{\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\frac\{L\}\{2\}h^\{2\}H\_\{T\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{generalized\}\\\\ \\text\{smoothness remainder\}\\end\{subarray\}\}\}\+\\quad\\underbrace\{h\{\\color\[rgb\]\{0,0\.5,0\}\\frac\{dGC\}\{\\underline\{D\}\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{same\-step\}\\\\ \\text\{correction\}\\end\{subarray\}\}\}\+h\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}\\Gamma\\log\(1/\\delta\)\},\(6\)whereHT=d​log⁡\(1\+T​C2yinit\+ε02\)\+d​C2yinit\+ε02H\_\{T\}=d\\log\\left\(1\+\\frac\{TC^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\varepsilon\_\{0\}^\{2\}\}\\right\)\+d\\frac\{C^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\varepsilon\_\{0\}^\{2\}\}andΓ=2​V\+23​C​GD¯\\Gamma=\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}\.

###### Proof sketch\.

We sum Lemma[3](https://arxiv.org/html/2609.30276#Thmlemma3)over allt<τt<\\tau\. Besides the main progress term∑t<τAt\\sum\_\{t<\\tau\}A\_\{t\}, this produces four error contributions: theclipping\-residualterm, thesame\-step correctionterm, the quadraticgeneralized\-smoothness remainder, and themartingale fluctuationterm\. Theclipping\-residualterm is bounded by using Young’s inequality,\(a​b≤14​a2\+b2\)\\big\(ab\\leq\\frac\{1\}\{4\}a^\{2\}\+b^\{2\}\\big\)witha=Ata=\\sqrt\{A\_\{t\}\}andb=V/c​D¯b=V/c\\sqrt\{\\underline\{D\}\}, which then absorbs one quarter of the resulting term into∑t<τAt\\sum\_\{t<\\tau\}A\_\{t\}, leaving a deterministic remainder of orderT​V2/\(D¯​C2\)TV^\{2\}/\(\\underline\{D\}C^\{2\}\)\. The cumulativesame\-step termis controlled pathwise by Lemma[4](https://arxiv.org/html/2609.30276#Thmlemma4), giving a deterministic contribution of orderd​G​C/D¯dGC/\\underline\{D\}\. The quadraticgeneralized\-smoothness remainderis bounded by the pathwise estimate on∑t<τ‖Dt\+1−1​g~t‖2\\sum\_\{t<\\tau\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}, producing the termL2​h2​HT\\frac\{L\}\{2\}h^\{2\}H\_\{T\}\. Finally, themartingale termis controlled later with high probability by invoking a Bernstein–Freedman supermartingale bound with probability atleast1−δ1\-\\delta, which turns it into a contribution of order14​∑t<τAt\+2​V\+23​C​GD¯​log⁡\(1/δ\)\\frac\{1\}\{4\}\\sum\_\{t<\\tau\}A\_\{t\}\+\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}\\log\(1/\\delta\)\. Substituting these bounds into the summed form of Lemma[3](https://arxiv.org/html/2609.30276#Thmlemma3)and rearranging gives the stated inequality in \([6](https://arxiv.org/html/2609.30276#S4.E6)\)\. Full proof is deferred to Appendix[A\.2\.7](https://arxiv.org/html/2609.30276#A1.SS2.SSS7)\. ∎

After this preconditioned estimate is obtained, converting it into a Euclidean stationarity bound introduces the high\-probability upper bound onDt−1D^\{\-1\}\_\{t\}\.

###### Lemma 6\(High\-probability bound onDtD\_\{t\}\)\.

Define the stopped clipped\-gradient energyY~T≔∑t=0T−1∥g~t∥2𝟏\{t<τ\}\.\\widetilde\{Y\}\_\{T\}\\coloneqq\\sum\_\{t=0\}^\{T\-1\}\\\|\\tilde\{g\}\_\{t\}\\\|^\{2\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\.Then for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

Y~T≤BT,δ≔T​V\+2​T​C2​V​log⁡1δ\+2​C23​log⁡1δ\.\\widetilde\{Y\}\_\{T\}\\leq B\_\{T,\\delta\}\\coloneqq TV\+\\sqrt\{2TC^\{2\}V\\log\\frac\{1\}\{\\delta\}\}\+\\frac\{2C^\{2\}\}\{3\}\\log\\frac\{1\}\{\\delta\}\.Consequently, on\{τ=T\}∩\{Y~T≤BT,δ\}\\\{\\tau=T\\\}\\cap\\\{\\widetilde\{Y\}\_\{T\}\\leq B\_\{T,\\delta\}\\\}, we have,maxt≤T⁡‖Dt‖≤D¯δ≔yinit\+BT,δ\+ϵ0\.\\max\_\{t\\leq T\}\\\|D\_\{t\}\\\|\\leq\\overline\{D\}\_\{\\delta\}\\coloneqq\\sqrt\{y\_\{\\mathrm\{init\}\}\+B\_\{T,\\delta\}\}\+\\epsilon\_\{0\}\.

###### Proof\.

Proof is deferred to Appendix[A\.2\.6](https://arxiv.org/html/2609.30276#A1.SS2.SSS6)\. ∎

Lemma[5](https://arxiv.org/html/2609.30276#Thmlemma5)shows that, before we can prove a Euclidean guarantee, we must control all four error terms\. Among all the terms in the summed descent bound, theclipping\-residual contribution, thesame\-step correction, and the later preconditioned\-to\-Euclidean conversion \(Lemma[6](https://arxiv.org/html/2609.30276#Thmlemma6)\) are the ones that determine the joint choice ofhh,CC, and the warm\-start floorD¯\\underline\{D\}\. Indeed, before couplingD¯\\underline\{D\}toCC, these two deterministic terms pullCCin opposite directions:h​T​V2D¯​C2\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}decreases asCCgrows, whereash​d​G​CD¯\\frac\{hdGC\}\{\\underline\{D\}\}increases withCC\.This is the core calibration conflict\. IfD¯\\underline\{D\}were treated as independent ofCC, then balancing these two terms withhhessentially fixed would forceC3≍TC^\{3\}\\asymp T, and their common scale would still grow likeh​T1/3D¯\\frac\{hT^\{1/3\}\}\{\\underline\{D\}\}, hence unbounded\. The purpose of the matched warm start is therefore to remove this harmfulCC\-dependence from thesame\-step term\. By contrast, thequadratic generalized\-smoothness remainderand themartingale fluctuationare still present in the final bound, but they do not drive the mainhh–CC–D¯\\underline\{D\}coupling\.

This is why the calibration is chosen to keep the following three quantities at the right scale:

h​T​V2D¯​C2⏟clipping\-residual contribution,h​d​G​CD¯⏟same\-step correction,D¯δh​T⏟preconditioned\-to\-Euclidean conversion\.\\underbrace\{\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}\}\}\_\{\\text\{clipping\-residual contribution\}\},\\hskip 18\.49988pt\\underbrace\{\{\\color\[rgb\]\{0,0\.5,0\}\\frac\{hdGC\}\{\\underline\{D\}\}\}\}\_\{\\text\{same\-step correction\}\},\\hskip 18\.49988pt\\underbrace\{\\frac\{\\overline\{D\}\_\{\\delta\}\}\{hT\}\}\_\{\\text\{preconditioned\-to\-Euclidean conversion\}\}\.
First, we tie the warm\-start floor to the clipping scale by settingyinit=C2,y\_\{\\mathrm\{init\}\}=C^\{2\},ϵ0=C\.\\epsilon\_\{0\}=C\.ThenD¯=yinit\+ϵ0=2​C,\\underline\{D\}=\\sqrt\{y\_\{\\mathrm\{init\}\}\}\+\\epsilon\_\{0\}=2C,so thesame\-step correctionpenalty collapses fromh​d​G​CD¯\\frac\{hdGC\}\{\\underline\{D\}\}toh​d​G2\{\\color\[rgb\]\{0,0\.5,0\}\\frac\{h\\,dG\}\{2\}\}, leavingCCfree to control only theclipping\-residual contribution\.

Second, onceD¯=2​C\\underline\{D\}=2C, theclipping\-residualcontribution becomesh​T​V2/C3\{\\color\[rgb\]\{0\.7617,0\.3125,0\}hTV^\{2\}/C^\{3\}\}\. Since the feasibility condition is imposed at the fixed anchored levelFF, theclipping\-residual termh​T​V22​C3\\frac\{hTV^\{2\}\}\{2C^\{3\}\}must remain𝒪⁡\(1\)\\mathcal\{O\}\(1\)\. This requiresh​TC3=𝒪⁡\(1\)\\frac\{hT\}\{C^\{3\}\}=\\mathcal\{O\}\(1\), which leads to the natural cubic scaleC3≍h​TC^\{3\}\\asymp hT\. The remaining term,D¯δ/\(h​T\)\\overline\{D\}\_\{\\delta\}/\(hT\), then measures the cost of converting the resultingpreconditioned estimateinto a Euclidean bound\. To obtain a true finite\-horizon Euclidean target, we keephhalmost constant up to polylogarithmic factors and chooseCCon the cubic scale by setting, for parametersη,κ\>0\\eta,\\kappa\>0:

h=ηΛT,δ,C=κT1/3,ΛT,δ≔1\+log\(1\+T\)\+log22δ\.\\boxed\{h=\\frac\{\\eta\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\},\\qquad C=\\kappa T^\{1/3\},\\qquad\\Lambda\_\{T,\\delta\}\\coloneqq 1\+\\log\(1\+T\)\+\\log^\{2\}\\\!\\frac\{2\}\{\\delta\}\.\}\(7\)This is the logic behind the calibration\. It is not an ad hoc theorem\-only schedule\. It is the scale at which thesame\-step correctionstops growing withCC, theclipping\-residualcontribution stops growing withTT, and the Euclidean conversion still yields an𝒪~\(T−1/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)bound\.

*We can now state the main finite\-horizon theorem\.*

###### Theorem 1\(True finite\-horizon Euclidean stationarity for clipped same\-step AdaGrad\)\.

Suppose Assumptions[1](https://arxiv.org/html/2609.30276#Thmassumption1),[2](https://arxiv.org/html/2609.30276#Thmassumption2), and[3](https://arxiv.org/html/2609.30276#Thmassumption3)holds\. Let

Δ0≔f⁡\(x0\)−f⋆\>0,F∘≔2​Δ0,G∘≔G⁡\(F∘\),L∘≔ℓ⁡\(2​G∘\),V∘≔\(G∘\)2\+σ2\.\\Delta\_\{0\}\\coloneqq f\(x\_\{0\}\)\-f^\{\\star\}\>0,\\quad F^\{\\circ\}\\coloneqq 2\\Delta\_\{0\},\\quad G^\{\\circ\}\\coloneqq G\(F^\{\\circ\}\),\\quad L^\{\\circ\}\\coloneqq\\ell\(2G^\{\\circ\}\),\\quad V^\{\\circ\}\\coloneqq\(G^\{\\circ\}\)^\{2\}\+\\sigma^\{2\}\.Fixκ\>0\\kappa\>0, choose\(h,C\)\(h,C\)from \([7](https://arxiv.org/html/2609.30276#S4.E7)\), and setyinit≔C2,y\_\{\\mathrm\{init\}\}\\coloneqq C^\{2\},ϵ0≔C\\epsilon\_\{0\}\\coloneqq C\. Suppose moreover that

η≤min⁡\{2​G∘L∘,Δ04​L∘​d,Δ0​κ8​V∘,Δ0​κ34​\(V∘\)2,3​Δ08​G∘,Δ0d​G∘\},\\eta\\leq\\min\\left\\\{\\frac\{2G^\{\\circ\}\}\{L^\{\\circ\}\},\\sqrt\{\\frac\{\\Delta\_\{0\}\}\{4L^\{\\circ\}d\}\},\\frac\{\\Delta\_\{0\}\\kappa\}\{8V^\{\\circ\}\},\\frac\{\\Delta\_\{0\}\\kappa^\{3\}\}\{4\(V^\{\\circ\}\)^\{2\}\},\\frac\{3\\Delta\_\{0\}\}\{8G^\{\\circ\}\},\\frac\{\\Delta\_\{0\}\}\{dG^\{\\circ\}\}\\right\\\},then the neighborhood condition \([4](https://arxiv.org/html/2609.30276#S4.E4)\) holds atF∘F^\{\\circ\}\. Then, with probability at least1−δ1\-\\delta,

f⁡\(xt\)−f⋆≤2​Δ0for all​t=0,…,T,andf\(x\_\{t\}\)\-f^\{\\star\}\\leq 2\\Delta\_\{0\}\\qquad\\text\{for all \}t=0,\\dots,T,\\quad\\text\{and\}1T∑t=0T−1∥∇f\(xt\)∥2≤4​Δ0​ΛT,δη​T\[\(V∘\+κ2​V∘​log⁡2δT−1/6\+κ2\(\+23log2δ\)T−1/3\)1/2\+κT−1/6\]\.\\frac\{1\}\{T\}\\\!\\sum\_\{t=0\}^\{T\-1\}\\\!\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\\!\\leq\\\!\\frac\{4\\Delta\_\{0\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\{\\eta\\sqrt\{T\}\}\\\!\\\!\\left\[\\\!\\\!\\left\(\\\!V^\{\\circ\}\\\!\+\\\!\\kappa\\sqrt\{2V^\{\\circ\}\\log\\frac\{2\}\{\\delta\}\}\\,T^\{\-1/6\}\\\!\+\\\!\\kappa^\{2\}\\\!\\\!\\left\(\\\!1\\\!\+\\\!\\frac\{2\}\{3\}\\log\\frac\{2\}\{\\delta\}\\\!\\right\)\\\!T^\{\-1/3\}\\\!\\right\)^\{\\\!\\\!1/2\}\\\!\\\!\\\!\\\!\\\!\\\!\\\!\+\\\!\\kappa T^\{\-1/6\}\\\!\\right\]\\\!\\\!\.Consequently, for fixed problem parameters,1T​∑t=0T−1‖∇f​\(xt\)‖2≤ϵ⟹T=𝒪~​\(ϵ−2\)\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq\\epsilon\\quad\\Longrightarrow\\quad T=\\widetilde\{\\mathcal\{O\}\}\(\\epsilon^\{\-2\}\)\.

###### Proof\.

Proof is deferred to Appendix[A\.3](https://arxiv.org/html/2609.30276#A1.SS3)\. ∎

The choice to anchor Theorem 1 atF∘=2​Δ0F^\{\\circ\}=2\\Delta\_\{0\}is an analytic convenience rather than a strict algorithmic limitation\. Setting the target to twice the initial suboptimality constructs a symmetric feasibility budget: exactlyΔ0\\Delta\_\{0\}accounts for the initial gap, leaving an equal allowance ofΔ0\\Delta\_\{0\}to absorb the cumulative algorithmic and stochastic penalties from Lemma[5](https://arxiv.org/html/2609.30276#Thmlemma5)\(specifically: theclipping\-residual,same\-step correction,martingale fluctuation, andsmoothness remainder\)\. Importantly, the𝒪~\(T−1/2\)\\tilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)convergence guarantee holds for any arbitrary target levelF\>Δ0F\>\\Delta\_\{0\}\. For any strictly positive slackF−Δ0\>0F\-\\Delta\_\{0\}\>0, one can always scale down the step\-size parameterη\\etasufficiently to compress the error budget within this margin\. We refer the reader to Appendix[A\.3\.1](https://arxiv.org/html/2609.30276#A1.SS3.SSS1)for a longer discussion\.

## 5Discussion of the Results and Conclusion

Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1)establishes a finite\-horizon Euclidean stationarity bound for the original clipped same\-step AdaGrad update under generalized smoothness and heavy\-tailed noise, with polylogarithmic dependence on the confidence levelδ\\delta\. Crucially, our𝒪~​\(ϵ−2\)\\tilde\{\\mathcal\{O\}\}\(\\epsilon^\{\-2\}\)complexity matches theΩ⁡\(ϵ−2\)\\Omega\(\\epsilon^\{\-2\}\)information\-theoretic lower bound for standard non\-convex stochastic optimization\[[2](https://arxiv.org/html/2609.30276#bib.bib57)\]up to logarithmic factors\. While our high\-probability, heavy\-tail setting aligns with recent clipped stochastic analyses\[[10](https://arxiv.org/html/2609.30276#bib.bib36);[44](https://arxiv.org/html/2609.30276#bib.bib58);[41](https://arxiv.org/html/2609.30276#bib.bib59);[7](https://arxiv.org/html/2609.30276#bib.bib17)\], we distinctively resolve this for the original coordinate\-wise same\-step update\.

It is also important to distinguish the present theorem from recent analyses of adaptive methods under non\-uniform or generalized smoothness\. These works show that convergence can still be obtained when local curvature grows with the gradient norm, for settings ranging from adaptive SGD to AdaGrad and Adam \(and its variants\), but they do not provide the present finite\-horizon high\-probability Euclidean guarantee for the original same\-step coordinate\-wise AdaGrad update under heavy\-tailed noise\[[14](https://arxiv.org/html/2609.30276#bib.bib3);[52](https://arxiv.org/html/2609.30276#bib.bib26);[26](https://arxiv.org/html/2609.30276#bib.bib11);[54](https://arxiv.org/html/2609.30276#bib.bib4)\]\. Further, up to the differences in logarithmic factors, these complexities coincide with the best known ones for Clipped\-SGD\[[44](https://arxiv.org/html/2609.30276#bib.bib58);[41](https://arxiv.org/html/2609.30276#bib.bib59)\]111Their analysis assumesLLsmoothness\.\.

Compared with existing high\-probability AdaGrad analyses, our result applies in a more demanding regime\. Prior coordinate\-wise AdaGrad bounds obtain sharper dimension dependence, but assume classicalLL\-smoothness together with almost\-sure bounded gradients and sub\-Gaussian noise\[[60](https://arxiv.org/html/2609.30276#bib.bib30)\]; other results study either delayed AdaGrad under sub\-Gaussian noise\[[30](https://arxiv.org/html/2609.30276#bib.bib18)\]or scalar AdaGrad\-Norm rather than the original coordinate\-wise update\[[23](https://arxiv.org/html/2609.30276#bib.bib23)\]\. Heavy\-tailed clipped AdaGrad results are closer, but existing theorems either analyze scalar/norm\-based AdaGrad with an additional bounded\-risk assumptionf⁡\(x\)≤Mf\(x\)\\leq M\[[27](https://arxiv.org/html/2609.30276#bib.bib60)\], or treat delayed coordinate\-wise variants rather than the original same\-step update\[[7](https://arxiv.org/html/2609.30276#bib.bib17)\]\.

It is also worth mentioning that the existing high\-probability complexities for Adam/AdaGrad\-type \(without clipping\) methods either have inverse power dependence onδ\\delta[52](https://arxiv.org/html/2609.30276#bib.bib26)or have polylogarithmic dependence onδ\\deltabut rely on the assumption that the noise is sub\-Gaussian/bounded[30](https://arxiv.org/html/2609.30276#bib.bib18);[33](https://arxiv.org/html/2609.30276#bib.bib61);[26](https://arxiv.org/html/2609.30276#bib.bib11), which is stronger than bounded variance assumption\.

## References

- Abdukhakimovet al\.\(2024\)F\. Abdukhakimov, C\. Xiang, D\. Kamzolov, and M\. TakáčStochastic gradient descent with preconditioned polyak step\-size\.Computational Mathematics and Mathematical Physics64\(4\),pp\. 621–634\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Arjevaniet al\.\(2023\)Y\. Arjevani, Y\. Carmon, J\. C\. Duchi, D\. J\. Foster, N\. Srebro, and B\. WoodworthLower bounds for non\-convex stochastic optimization\.Mathematical Programming199\(1\),pp\. 165–214\.Cited by:[§5](https://arxiv.org/html/2609.30276#S5.p1.1)\.
- Attia and Koren \(2023\)A\. Attia and T\. KorenSGD with adagrad stepsizes: full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance\.InInternational Conference on Machine Learning,pp\. 1147–1171\.Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1),[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.5.1)\.
- Chakrabarti and Baranwal \(2024\)K\. Chakrabarti and M\. BaranwalA methodology establishing linear convergence of adaptive gradient methods under pl inequality\.arXiv preprint arXiv:2407\.12629\.Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1)\.
- Chenet al\.\(2018\)J\. Chen, D\. Zhou, Y\. Tang, Z\. Yang, Y\. Cao, and Q\. GuClosing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks\.arXiv preprint arXiv:1806\.06763\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Chenet al\.\(2023\)Z\. Chen, Y\. Zhou, Y\. Liang, and Z\. LuGeneralized\-Smooth Nonconvex Optimization is as Efficient as Smooth Nonconvex Optimization\.InInternational Conference on Machine Learning,pp\. 5396–5427\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Chezhegovet al\.\(2025\)S\. Chezhegov, K\. Yaroslav, A\. Semenov, A\. Beznosikov, A\. Gasnikov, S\. Horváth, M\. Takáč, and E\. GorbunovClipping improves adam\-norm and adagrad\-norm when the noise is heavy\-tailed\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=LNTepdaSLC)Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1),[§1](https://arxiv.org/html/2609.30276#S1.p4.1),[§2](https://arxiv.org/html/2609.30276#S2.p3.1),[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.9.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1),[§5](https://arxiv.org/html/2609.30276#S5.p1.1),[§5](https://arxiv.org/html/2609.30276#S5.p3.1)\.
- Crawshawet al\.\(2022\)M\. Crawshaw, M\. Liu, F\. Orabona, W\. Zhang, and Z\. ZhuangRobustness to Unbounded Smoothness of Generalized SignSGD\.Advances in Neural Information Processing Systems35,pp\. 9955–9968\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Crawshaw and Liu \(2025\)M\. Crawshaw and M\. LiuComplexity lower bounds of adaptive gradient algorithms for non\-convex stochastic optimization under relaxed smoothness\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ZjOXuAfS6l)Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p4.1)\.
- Cutkosky and Mehta \(2021\)A\. Cutkosky and H\. MehtaHigh\-Probability Bounds for Non\-Convex Stochastic Optimization with Heavy Tails\.Advances in Neural Information Processing Systems34,pp\. 4883–4895\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1),[§5](https://arxiv.org/html/2609.30276#S5.p1.1)\.
- Défossezet al\.\(2020\)A\. Défossez, L\. Bottou, F\. Bach, and N\. UsunierA Simple Convergence Proof of Adam and AdaGrad\.arXiv preprint arXiv:2003\.02395\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Duchiet al\.\(2011\)J\. Duchi, E\. Hazan, and Y\. SingerAdaptive Subgradient Methods for Online Learning and Stochastic Optimization\.Journal of Machine Learning Research12\(7\)\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[Algorithm 1](https://arxiv.org/html/2609.30276#alg1)\.
- Fatkhullinet al\.\(2025\)I\. Fatkhullin, F\. Hübler, and G\. LanCan SGD Handle Heavy\-Tailed Noise?\.arXiv preprint arXiv:2508\.04860\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Fawet al\.\(2023\)M\. Faw, L\. Rout, C\. Caramanis, and S\. ShakkottaiBeyond uniform smoothness: a stopped analysis of adaptive sgd\.InThe Thirty Sixth Annual Conference on Learning Theory,pp\. 89–160\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p1.2),[§5](https://arxiv.org/html/2609.30276#S5.p2.1)\.
- Fawet al\.\(2022\)M\. Faw, I\. Tziotis, C\. Caramanis, A\. Mokhtari, S\. Shakkottai, and R\. WardThe power of adaptivity in sgd: self\-tuning step sizes with unbounded gradients and affine variance\.InConference on Learning Theory,pp\. 313–355\.Cited by:[4th item](https://arxiv.org/html/2609.30276#S1.I1.i4.p1.1),[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1)\.
- Ghadimi and Lan \(2012\)S\. Ghadimi and G\. LanOptimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: a generic algorithmic framework\.SIAM Journal on Optimization22\(4\),pp\. 1469–1492\.Cited by:[Assumption 3](https://arxiv.org/html/2609.30276#Thmassumption3)\.
- Gorbunovet al\.\(2020\)E\. Gorbunov, M\. Danilova, and A\. GasnikovStochastic Optimization with Heavy\-Tailed Noise via Accelerated Gradient Clipping\.Advances in Neural Information Processing Systems33,pp\. 15042–15053\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1)\.
- Hong and Lin \(2024a\)Y\. Hong and J\. LinOn Convergence of Adam for Stochastic Optimization under Relaxed Assumptions\.Advances in Neural Information Processing Systems37,pp\. 10827–10877\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Hong and Lin \(2024b\)Y\. Hong and J\. LinRevisiting Convergence of AdaGrad with Relaxed Assumptions\.arXiv preprint arXiv:2402\.13794\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Hübleret al\.\(2024a\)F\. Hübler, I\. Fatkhullin, and N\. HeFrom Gradient Clipping to Normalization for Heavy Tailed SGD\.arXiv preprint arXiv:2410\.13849\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Hübleret al\.\(2024b\)F\. Hübler, J\. Yang, X\. Li, and N\. HeParameter\-Agnostic Optimization under Relaxed Smoothness\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 4861–4869\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Jianget al\.\(2025\)R\. Jiang, D\. Maladkar, and A\. MokhtariProvable complexity improvement of adagrad over sgd: upper and lower bounds in stochastic non\-convex optimization\.InProceedings of Thirty Eighth Conference on Learning Theory,N\. Haghtalab and A\. Moitra \(Eds\.\),Proceedings of Machine Learning Research, Vol\.291,pp\. 3124–3158\.External Links:[Link](https://proceedings.mlr.press/v291/jiang25c.html)Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p4.1)\.
- Kaviset al\.\(2022\)A\. Kavis, K\. Y\. Levy, and V\. CevherHigh probability bounds for a class of nonconvex algorithms with adagrad stepsize\.arXiv preprint arXiv:2204\.02833\.Cited by:[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.4.1),[§5](https://arxiv.org/html/2609.30276#S5.p3.1)\.
- Kingma and Ba \(2015\)D\. P\. Kingma and J\. BaAdam: A Method for Stochastic Optimization\.In3rd International Conference on Learning Representations, ICLR 2015,External Links:[Link](https://arxiv.org/abs/1412.6980)Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Liet al\.\(2023a\)H\. Li, J\. Qian, Y\. Tian, A\. Rakhlin, and A\. JadbabaieConvex and Non\-convex Optimization Under Generalized Smoothness\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36,pp\. 40238–40271\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/file/7e8bb8d17bb1cb24dfe972a2f8ff2500-Paper-Conference.pdf)Cited by:[§1\.2\.1](https://arxiv.org/html/2609.30276#S1.SS2.SSS1.p1.1),[§1\.2\.1](https://arxiv.org/html/2609.30276#S1.SS2.SSS1.p3.1),[§1](https://arxiv.org/html/2609.30276#S1.p2.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1),[Assumption 3](https://arxiv.org/html/2609.30276#Thmassumption3),[Lemma 1](https://arxiv.org/html/2609.30276#Thmlemma1),[Lemma 2](https://arxiv.org/html/2609.30276#Thmlemma2)\.
- Liet al\.\(2023b\)H\. Li, A\. Rakhlin, and A\. JadbabaieConvergence of Adam under Relaxed Assumptions\.Advances in Neural Information Processing Systems36,pp\. 52166–52196\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§5](https://arxiv.org/html/2609.30276#S5.p2.1),[§5](https://arxiv.org/html/2609.30276#S5.p4.1)\.
- Li and Liu \(2023\)S\. Li and Y\. LiuHigh probability analysis for non\-convex stochastic optimization with clipping\.InECAI 2023,pp\. 1406–1413\.Cited by:[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.7.1),[§5](https://arxiv.org/html/2609.30276#S5.p3.1)\.
- Liet al\.\(2022\)S\. Li, W\. J\. Swartworth, M\. Takáč, D\. Needell, and R\. M\. GowerSP2: a second order stochastic polyak method\.arXiv preprint arXiv:2207\.08171\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Li and Orabona \(2019\)X\. Li and F\. OrabonaOn the convergence of stochastic gradient descent with adaptive stepsizes\.InThe 22nd international conference on artificial intelligence and statistics,pp\. 983–992\.Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1)\.
- Li and Orabona \(2020\)X\. Li and F\. OrabonaA high probability analysis of adaptive sgd with momentum\.arXiv preprint arXiv:2007\.14294\.Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1),[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.3.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1),[§5](https://arxiv.org/html/2609.30276#S5.p3.1),[§5](https://arxiv.org/html/2609.30276#S5.p4.1)\.
- Liet al\.\(2024\)Y\. Li, R\. Yuan, C\. Fan, M\. Schmidt, S\. Horváth, R\. M\. Gower, and M\. TakáčEnhancing policy gradient with the polyak step\-size adaption\.arXiv preprint arXiv:2404\.07525\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Liuet al\.\(2024\)Y\. Liu, R\. Pan, and T\. ZhangAdaGrad under Anisotropic Smoothness\.arXiv preprint arXiv:2406\.15244\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Liuet al\.\(2023\)Z\. Liu, T\. D\. Nguyen, T\. H\. Nguyen, A\. Ene, and H\. NguyenHigh probability convergence of stochastic gradient methods\.InInternational conference on machine learning,pp\. 21884–21914\.Cited by:[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.6.1),[§5](https://arxiv.org/html/2609.30276#S5.p4.1)\.
- Loizouet al\.\(2021\)N\. Loizou, S\. Vaswani, I\. H\. Laradji, and S\. Lacoste\-JulienStochastic polyak step\-size for sgd: an adaptive learning rate for fast convergence\.InInternational conference on artificial intelligence and statistics,pp\. 1306–1314\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Luoet al\.\(2019\)L\. Luo, Y\. Xiong, Y\. Liu, and X\. SunAdaptive Gradient Methods with Dynamic Bound of Learning Rate\.arXiv preprint arXiv:1902\.09843\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Mai and Johansson \(2021\)V\. V\. Mai and M\. JohanssonStability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness\.InInternational Conference on Machine Learning,pp\. 7325–7335\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Moskvoretskiiet al\.\(2024\)V\. Moskvoretskii, A\. Panchenko, and I\. NikishinaAre large language models good at lexical semantics? a case of taxonomy learning\.InProceedings of the 2024 joint international conference on computational linguistics, language resources and evaluation \(LREC\-COLING 2024\),pp\. 1498–1510\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Nemirovskiet al\.\(2009\)A\. Nemirovski, A\. Juditsky, G\. Lan, and A\. ShapiroRobust stochastic approximation approach to stochastic programming\.SIAM Journal on optimization19\(4\),pp\. 1574–1609\.Cited by:[Assumption 3](https://arxiv.org/html/2609.30276#Thmassumption3)\.
- Nemirovskij and Yudin \(1983\)A\. S\. Nemirovskij and D\. B\. YudinProblem complexity and method efficiency in optimization\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p1.2)\.
- Nesterov \(2013\)Y\. NesterovIntroductory lectures on convex optimization: a basic course\.Vol\.87,Springer Science & Business Media\.Cited by:[§1\.2\.1](https://arxiv.org/html/2609.30276#S1.SS2.SSS1.p3.1),[§1](https://arxiv.org/html/2609.30276#S1.p1.2)\.
- Nguyenet al\.\(2023\)T\. D\. Nguyen, T\. H\. Nguyen, A\. Ene, and H\. NguyenImproved convergence in high probability of clipped gradient methods with heavy tailed noise\.Advances in Neural Information Processing Systems36,pp\. 24191–24222\.Cited by:[§5](https://arxiv.org/html/2609.30276#S5.p1.1),[§5](https://arxiv.org/html/2609.30276#S5.p2.1)\.
- Nikishinaet al\.\(2022\)I\. Nikishina, A\. Vakhitova, E\. Tutubalina, and A\. PanchenkoCross\-modal contextualized hidden state projection method for expanding of taxonomic graphs\.InProceedings of TextGraphs\-16: Graph\-based methods for natural language processing,pp\. 11–24\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Reddiet al\.\(2019\)S\. J\. Reddi, S\. Kale, and S\. KumarOn the Convergence of Adam and Beyond\.arXiv preprint arXiv:1904\.09237\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Sadievet al\.\(2023\)A\. Sadiev, M\. Danilova, E\. Gorbunov, S\. Horváth, G\. Gidel, P\. Dvurechensky, A\. Gasnikov, and P\. RichtárikHigh\-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 29563–29648\.External Links:[Link](https://proceedings.mlr.press/v202/sadiev23a.html)Cited by:[§5](https://arxiv.org/html/2609.30276#S5.p1.1),[§5](https://arxiv.org/html/2609.30276#S5.p2.1)\.
- Savareseet al\.\(2021\)P\. Savarese, D\. McAllester, S\. Babu, and M\. MaireDomain\-independent dominance of adaptive methods\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 16286–16295\.Cited by:[§1\.1](https://arxiv.org/html/2609.30276#S1.SS1.p3.1)\.
- Schaippet al\.\(2023\)F\. Schaipp, R\. Ohana, M\. Eickenberg, A\. Defazio, and R\. M\. GowerMomo: momentum models for adaptive learning rates\.arXiv preprint arXiv:2305\.07583\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Shiet al\.\(2021\)Z\. Shi, A\. Sadiev, N\. Loizou, P\. Richtárik, and M\. TakáčAI\-sarah: adaptive and implicit stochastic recursive gradient methods\.arXiv preprint arXiv:2102\.09700\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Streeter and McMahan \(2010\)M\. Streeter and H\. B\. McMahanLess regret via online conditioning\.arXiv preprint arXiv:1002\.4862\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Takácet al\.\(2013\)M\. Takác, A\. Bijral, P\. Richtárik, and N\. SrebroMini\-batch primal and dual methods for svms\.InInternational Conference on Machine Learning,pp\. 1022–1030\.Cited by:[Assumption 3](https://arxiv.org/html/2609.30276#Thmassumption3)\.
- Vankovet al\.\(2025\)D\. Vankov, A\. Rodomanov, A\. Nedić, L\. Sankar, and S\. U\. StichOPTIMIZING \(l0, l1\)\-smooth functions by gradient methods\.In13th International Conference on Learning Representations, ICLR 2025,pp\. 39615–39641\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p1.2),[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. PolosukhinAttention is all you need\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Wanget al\.\(2023\)B\. Wang, H\. Zhang, Z\. Ma, and W\. ChenConvergence of AdaGrad for Non\-Convex Objectives: Simple Proofs and Relaxed Assumptions\.InThe Thirty Sixth Annual Conference on Learning Theory,pp\. 161–190\.Cited by:[4th item](https://arxiv.org/html/2609.30276#S1.I1.i4.p1.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§4](https://arxiv.org/html/2609.30276#S4.p3.1),[§5](https://arxiv.org/html/2609.30276#S5.p2.1),[§5](https://arxiv.org/html/2609.30276#S5.p4.1)\.
- Wanget al\.\(2024a\)B\. Wang, H\. Zhang, Q\. Meng, R\. Sun, Z\. Ma, and W\. ChenOn the Convergence of Adam under Non\-Uniform Smoothness: Separability from SGDM and Beyond\.arXiv preprint arXiv:2403\.15146\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Wanget al\.\(2024b\)B\. Wang, Y\. Zhang, H\. Zhang, Q\. Meng, R\. Sun, Z\. Ma, T\. Liu, Z\. Luo, and W\. ChenProvable Adaptivity of Adam under Non\-Uniform Smoothness\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 2960–2969\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p1.2),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[§5](https://arxiv.org/html/2609.30276#S5.p2.1)\.
- Wardet al\.\(2020\)R\. Ward, X\. Wu, and L\. BottouAdaGrad Stepsizes: Sharp Convergence over Nonconvex Landscapes\.Journal of Machine Learning Research21\(219\),pp\. 1–30\.Cited by:[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.2.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Youet al\.\(2019\)Y\. You, J\. Li, S\. Reddi, J\. Hseu, S\. Kumar, S\. Bhojanapalli, X\. Song, J\. Demmel, K\. Keutzer, and C\. HsiehLarge batch optimization for deep learning: training bert in 76 minutes\.arXiv preprint arXiv:1904\.00962\.Cited by:[§1](https://arxiv.org/html/2609.30276#S1.p3.1)\.
- Yuet al\.\(2025\)D\. Yu, W\. Jiang, H\. Tao, Y\. Wan, and L\. ZhangMirror Descent under Generalized Smoothness\.arXiv preprint arXiv:2502\.00753\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Zaheeret al\.\(2018\)M\. Zaheer, S\. Reddi, D\. Sachan, S\. Kale, and S\. KumarAdaptive Methods for Nonconvex Optimization\.Advances in Neural Information Processing Systems31\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.
- Zhanget al\.\(2019\)J\. Zhang, T\. He, S\. Sra, and A\. JadbabaieWhy Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity\.arXiv preprint arXiv:1905\.11881\.Cited by:[§1\.2\.1](https://arxiv.org/html/2609.30276#S1.SS2.SSS1.p5.1),[§1](https://arxiv.org/html/2609.30276#S1.p1.2),[§1](https://arxiv.org/html/2609.30276#S1.p2.1),[§1](https://arxiv.org/html/2609.30276#S1.p4.1),[§3](https://arxiv.org/html/2609.30276#S3.p1.1),[Remark 1](https://arxiv.org/html/2609.30276#Thmremark1.p1.1)\.
- Zhouet al\.\(2024\)D\. Zhou, J\. Chen, Y\. Cao, Z\. Yang, and Q\. GuOn the Convergence of Adaptive Gradient Methods for Nonconvex Optimization\.Transactions on Machine Learning Research\.Note:Featured CertificationExternal Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=Gh0cxhbz3c)Cited by:[Table 1](https://arxiv.org/html/2609.30276#S3.T1.6.1.8.1),[§5](https://arxiv.org/html/2609.30276#S5.p3.1)\.
- Zouet al\.\(2019\)F\. Zou, L\. Shen, Z\. Jie, W\. Zhang, and W\. LiuA Sufficient Condition for Convergences of Adam and RMSProp\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 11127–11135\.Cited by:[§3](https://arxiv.org/html/2609.30276#S3.p1.1)\.

## Appendix AProofs

### A\.1Anisotropic Miscalibration and Failure of AdaGrad

###### Proposition 2\(Anisotropic miscalibration lower bound for AdaGrad\)\.

Let

f⁡\(x1,x2\)=14​x14\+12​x12\+8​x22f\(x\_\{1\},x\_\{2\}\)=\\frac\{1\}\{4\}x\_\{1\}^\{4\}\+\\frac\{1\}\{2\}x\_\{1\}^\{2\}\+8x\_\{2\}^\{2\}andx0=\(2,1\)x\_\{0\}=\(2,1\)\. RunAlgorithm[1](https://arxiv.org/html/2609.30276#alg1)withd=2d=2,h=1h=1,yinit=0y\_\{\\mathrm\{init\}\}=0, andϵ0=1\\epsilon\_\{0\}=1\. For every horizonT≥2T\\geq 2and every noise scaleσ\>0\\sigma\>0, there exists a stochastic oracle satisfying Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)with noise levelσ\\sigmasuch that, with probability at least

pT≔σ2\(32​\(T−1\)−10\)2\+σ2,p\_\{T\}\\coloneqq\\frac\{\\sigma^\{2\}\}\{\\bigl\(32\(T\-1\)\-10\\bigr\)^\{2\}\+\\sigma^\{2\}\},the following inequalities hold simultaneously for everyt=1,…,T−1t=1,\\dots,T\-1:

∂112f⁡\(xt\)<∂222f⁡\(xt\),\(Dt\)11\>169​\(T−1\)​\(Dt\)22,‖∇f​\(xt\)‖\>1\.\\partial\_\{11\}^\{2\}f\(x\_\{t\}\)<\\partial\_\{22\}^\{2\}f\(x\_\{t\}\),\\qquad\(D\_\{t\}\)\_\{11\}\>\\frac\{16\}\{9\}\(T\-1\)\(D\_\{t\}\)\_\{22\},\\qquad\\\|\\nabla f\(x\_\{t\}\)\\\|\>1\.Consequently, since‖∇f​\(x0\)‖\>1\\\|\\nabla f\(x\_\{0\}\)\\\|\>1, we have

ℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2\>1\)≥pT\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\>1\\right\)\\geq p\_\{T\}\. Therefore, any uniform guarantee of the form

ℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2≤1\)≥1−δ\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq 1\\right\)\\geq 1\-\\deltaover all stochastic oracles satisfying Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)requires

T≥1\+132​\(10\+σ​1−δδ\)T\\geq 1\+\\frac\{1\}\{32\}\\left\(10\+\\sigma\\sqrt\{\\frac\{1\-\\delta\}\{\\delta\}\}\\right\)\.

###### Proof\.

Set

B≔32​\(T−1\)−10,pT≔σ2B2\+σ2\.B\\coloneqq 32\(T\-1\)\-10,\\qquad p\_\{T\}\\coloneqq\\frac\{\\sigma^\{2\}\}\{B^\{2\}\+\\sigma^\{2\}\}\.We define the stochastic oracle as follows\. At timet=0t=0,

g0=∇f​\(x0\)\+ξ0,ξ0=\(ζ,0\),g\_\{0\}=\\nabla f\(x\_\{0\}\)\+\\xi\_\{0\},\\qquad\\xi\_\{0\}=\(\\zeta,0\),where

ζ=\{B,with probability​pT,−σ2B,with probability​1−pT\.\\zeta=\\begin\{cases\}B,&\\text\{with probability \}p\_\{T\},\\\\\[4\.30554pt\] \-\\dfrac\{\\sigma^\{2\}\}\{B\},&\\text\{with probability \}1\-p\_\{T\}\.\\end\{cases\}For everyt≥1t\\geq 1, we set

gt=∇f​\(xt\),i\.e\.ξt≡0\.g\_\{t\}=\\nabla f\(x\_\{t\}\),\\qquad\\text\{i\.e\.\}\\qquad\\xi\_\{t\}\\equiv 0\.
We first verify Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)\. Since

pT​B\+\(1−pT\)​\(−σ2B\)=0,p\_\{T\}B\+\\Bigl\(1\-p\_\{T\}\\Bigr\)\\Bigl\(\-\\frac\{\\sigma^\{2\}\}\{B\}\\Bigr\)=0,we have𝔼⁡\[ζ\]=0\\mathbb\{E\}\[\\zeta\]=0, hence𝔼⁡\[ξ0\]=0\\mathbb\{E\}\[\\xi\_\{0\}\]=0\. Also,

𝔼⁡\[ζ2\]=pT​B2\+\(1−pT\)​σ4B2=σ2​B2B2\+σ2\+B2B2\+σ2​σ4B2=σ2\.\\mathbb\{E\}\[\\zeta^\{2\}\]=p\_\{T\}B^\{2\}\+\\Bigl\(1\-p\_\{T\}\\Bigr\)\\frac\{\\sigma^\{4\}\}\{B^\{2\}\}=\\frac\{\\sigma^\{2\}B^\{2\}\}\{B^\{2\}\+\\sigma^\{2\}\}\+\\frac\{B^\{2\}\}\{B^\{2\}\+\\sigma^\{2\}\}\\frac\{\\sigma^\{4\}\}\{B^\{2\}\}=\\sigma^\{2\}\.Therefore

𝔼∥ξ0∥2=σ2,𝔼∥ξt∥2=0≤σ2\(t≥1\),\\mathbb\{E\}\\\|\\xi\_\{0\}\\\|^\{2\}=\\sigma^\{2\},\\qquad\\mathbb\{E\}\\\|\\xi\_\{t\}\\\|^\{2\}=0\\leq\\sigma^\{2\}\\quad\(t\\geq 1\),and the oracle satisfies Assumption[3](https://arxiv.org/html/2609.30276#Thmassumption3)\.

Now define the event

ℰ≔\{ζ=B\}\.\\mathcal\{E\}\\coloneqq\\\{\\zeta=B\\\}\.By construction,

ℙ⁡\(ℰ\)=pT\.\\mathbb\{P\}\(\\mathcal\{E\}\)=p\_\{T\}\.We will show that onℰ\\mathcal\{E\}, for everyt=1,…,T−1t=1,\\dots,T\-1,

∂112f⁡\(xt\)<∂222f⁡\(xt\),\(Dt\)11\>169​\(T−1\)​\(Dt\)22,‖∇f​\(xt\)‖\>1\.\\partial\_\{11\}^\{2\}f\(x\_\{t\}\)<\\partial\_\{22\}^\{2\}f\(x\_\{t\}\),\\qquad\(D\_\{t\}\)\_\{11\}\>\\frac\{16\}\{9\}\(T\-1\)\(D\_\{t\}\)\_\{22\},\\qquad\\\|\\nabla f\(x\_\{t\}\)\\\|\>1\.
Step 1: explicit first iterate and first denominator onℰ\\mathcal\{E\}\.

For

f⁡\(x1,x2\)=14​x14\+12​x12\+8​x22,f\(x\_\{1\},x\_\{2\}\)=\\frac\{1\}\{4\}x\_\{1\}^\{4\}\+\\frac\{1\}\{2\}x\_\{1\}^\{2\}\+8x\_\{2\}^\{2\},we have

∇f​\(x1,x2\)=\(x13\+x116​x2\),∇2f​\(x1,x2\)=\(3​x12\+10016\)\.\\nabla f\(x\_\{1\},x\_\{2\}\)=\\begin\{pmatrix\}x\_\{1\}^\{3\}\+x\_\{1\}\\\\ 16x\_\{2\}\\end\{pmatrix\},\\qquad\\nabla^\{2\}f\(x\_\{1\},x\_\{2\}\)=\\begin\{pmatrix\}3x\_\{1\}^\{2\}\+1&0\\\\ 0&16\\end\{pmatrix\}\.At the starting pointx0=\(2,1\)x\_\{0\}=\(2,1\),

∇f​\(x0\)=\(10,16\)\.\\nabla f\(x\_\{0\}\)=\(10,16\)\.Hence, onℰ\\mathcal\{E\},

g0=\(10\+B,16\)=\(32​\(T−1\),16\)\.g\_\{0\}=\(10\+B,16\)=\\bigl\(32\(T\-1\),16\\bigr\)\.Sinceyinit=0y\_\{\\mathrm\{init\}\}=0andϵ0=1\\epsilon\_\{0\}=1, the non\-lagged AdaGrad update gives

y1=g0⊙2=\(\(32​\(T−1\)\)2,162\),y\_\{1\}=g\_\{0\}^\{\\odot 2\}=\\bigl\(\(32\(T\-1\)\)^\{2\},16^\{2\}\\bigr\),and therefore

D1=diag⁡\(32​\(T−1\)\+1,17\)\.D\_\{1\}=\\mathrm\{diag\}\\bigl\(32\(T\-1\)\+1,17\\bigr\)\.Becauseh=1h=1,

x1=x0−D1−1​g0=\(2−32​\(T−1\)32​\(T−1\)\+1,1−1617\)=\(1\+132​\(T−1\)\+1,117\)\.x\_\{1\}=x\_\{0\}\-D\_\{1\}^\{\-1\}g\_\{0\}=\\left\(2\-\\frac\{32\(T\-1\)\}\{32\(T\-1\)\+1\},\\,1\-\\frac\{16\}\{17\}\\right\)=\\left\(1\+\\frac\{1\}\{32\(T\-1\)\+1\},\\,\\frac\{1\}\{17\}\\right\)\.In particular,

1<x1,1<43,x1,2=117\>0\.1<x\_\{1,1\}<\\frac\{4\}\{3\},\\qquad x\_\{1,2\}=\\frac\{1\}\{17\}\>0\.
Step 2: control of the second coordinate\.

For everyt≥1t\\geq 1, the oracle is noiseless, so

gt,2=16​xt,2,yt\+1,2=yt,2\+gt,22\.g\_\{t,2\}=16x\_\{t,2\},\\qquad y\_\{t\+1,2\}=y\_\{t,2\}\+g\_\{t,2\}^\{2\}\.We claim that for everyt≥1t\\geq 1,

0<xt,2≤117⋅9t−1,0<x\_\{t,2\}\\leq\\frac\{1\}\{17\\cdot 9^\{\\,t\-1\}\},\(A\.1\)and

yt,2<257\.y\_\{t,2\}<257\.\(A\.2\)
We prove both statements simultaneously by induction ontt\.

Fort=1t=1, we already computed

x1,2=117,y1,2=162=256<257,x\_\{1,2\}=\\frac\{1\}\{17\},\\qquad y\_\{1,2\}=16^\{2\}=256<257,so \([A\.1](https://arxiv.org/html/2609.30276#A1.E1)\)–\([A\.2](https://arxiv.org/html/2609.30276#A1.E2)\) hold\.

Now assume that for everys=1,…,ts=1,\\dots,t,

0<xs,2≤117⋅9s−1,ys,2<257\.0<x\_\{s,2\}\\leq\\frac\{1\}\{17\\cdot 9^\{\\,s\-1\}\},\\qquad y\_\{s,2\}<257\.We first boundyt\+1,2y\_\{t\+1,2\}\. Sincey1,2=256y\_\{1,2\}=256andgs,2=16​xs,2g\_\{s,2\}=16x\_\{s,2\}fors≥1s\\geq 1,

yt\+1,2=256\+∑s=1tgs,22=256\+∑s=1t\(16​xs,2\)2\.y\_\{t\+1,2\}=256\+\\sum\_\{s=1\}^\{t\}g\_\{s,2\}^\{2\}=256\+\\sum\_\{s=1\}^\{t\}\(16x\_\{s,2\}\)^\{2\}\.Using the induction hypothesis,

\(16​xs,2\)2≤256172​92​\(s−1\)=256289⋅181s−1\.\(16x\_\{s,2\}\)^\{2\}\\leq\\frac\{256\}\{17^\{2\}\\,9^\{\\,2\(s\-1\)\}\}=\\frac\{256\}\{289\}\\cdot\\frac\{1\}\{81^\{\\,s\-1\}\}\.Therefore

yt\+1,2≤256\+256289​∑j=0t−1181j<256\+256289⋅11−1/81=256\+256289⋅8180<257\.y\_\{t\+1,2\}\\leq 256\+\\frac\{256\}\{289\}\\sum\_\{j=0\}^\{t\-1\}\\frac\{1\}\{81^\{j\}\}<256\+\\frac\{256\}\{289\}\\cdot\\frac\{1\}\{1\-1/81\}=256\+\\frac\{256\}\{289\}\\cdot\\frac\{81\}\{80\}<257\.Thus \([A\.2](https://arxiv.org/html/2609.30276#A1.E2)\) holds at timet\+1t\+1\.

Next, sinceyt\+1,2≥y1,2=256y\_\{t\+1,2\}\\geq y\_\{1,2\}=256, we have

\(Dt\+1\)22=yt\+1,2\+1≥17,\(D\_\{t\+1\}\)\_\{22\}=\\sqrt\{y\_\{t\+1,2\}\}\+1\\geq 17,and sinceyt\+1,2<257y\_\{t\+1,2\}<257, we also have

\(Dt\+1\)22<257\+1<18\.\(D\_\{t\+1\}\)\_\{22\}<\\sqrt\{257\}\+1<18\.Hence

0<1−16\(Dt\+1\)22<1−1618=19\.0<1\-\\frac\{16\}\{\(D\_\{t\+1\}\)\_\{22\}\}<1\-\\frac\{16\}\{18\}=\\frac\{1\}\{9\}\.Therefore

xt\+1,2=xt,2−16​xt,2\(Dt\+1\)22=xt,2​\(1−16\(Dt\+1\)22\),x\_\{t\+1,2\}=x\_\{t,2\}\-\\frac\{16x\_\{t,2\}\}\{\(D\_\{t\+1\}\)\_\{22\}\}=x\_\{t,2\}\\left\(1\-\\frac\{16\}\{\(D\_\{t\+1\}\)\_\{22\}\}\\right\),so in particularxt\+1,2\>0x\_\{t\+1,2\}\>0, and moreover

xt\+1,2≤xt,29≤117⋅9t\.x\_\{t\+1,2\}\\leq\\frac\{x\_\{t,2\}\}\{9\}\\leq\\frac\{1\}\{17\\cdot 9^\{\\,t\}\}\.Thus \([A\.1](https://arxiv.org/html/2609.30276#A1.E1)\) holds at timet\+1t\+1, completing the induction\.

Consequently, for everyt≥1t\\geq 1,

\(Dt\)22=yt,2\+1<257\+1<18\.\(D\_\{t\}\)\_\{22\}=\\sqrt\{y\_\{t,2\}\}\+1<\\sqrt\{257\}\+1<18\.
Step 3: control of the first coordinate\.

For everyt≥1t\\geq 1, the oracle is noiseless, so

gt,1=xt,13\+xt,1\.g\_\{t,1\}=x\_\{t,1\}^\{3\}\+x\_\{t,1\}\.Sinceyt,1y\_\{t,1\}is nondecreasing andy1,1=\(32​\(T−1\)\)2y\_\{1,1\}=\(32\(T\-1\)\)^\{2\},

\(Dt\)11=yt,1\+1≥32​\(T−1\)\+1for all​t≥1\.\(D\_\{t\}\)\_\{11\}=\\sqrt\{y\_\{t,1\}\}\+1\\geq 32\(T\-1\)\+1\\qquad\\text\{for all \}t\\geq 1\.We first show thatxt,1x\_\{t,1\}stays below4/34/3\. Sincex1,1<4/3x\_\{1,1\}<4/3, it suffices to show thatxt,1x\_\{t,1\}is nonincreasing\. But ifxt,1\>0x\_\{t,1\}\>0, thengt,1=xt,13\+xt,1\>0g\_\{t,1\}=x\_\{t,1\}^\{3\}\+x\_\{t,1\}\>0, so

xt\+1,1=xt,1−gt,1\(Dt\+1\)11<xt,1\.x\_\{t\+1,1\}=x\_\{t,1\}\-\\frac\{g\_\{t,1\}\}\{\(D\_\{t\+1\}\)\_\{11\}\}<x\_\{t,1\}\.Thus, by induction,

0<xt,1≤x1,1<43for all​t≥1\.0<x\_\{t,1\}\\leq x\_\{1,1\}<\\frac\{4\}\{3\}\\qquad\\text\{for all \}t\\geq 1\.Usingxt,1<4/3x\_\{t,1\}<4/3, we obtain

gt,1=xt,13\+xt,1≤\(43\)3\+43=10027<4\.g\_\{t,1\}=x\_\{t,1\}^\{3\}\+x\_\{t,1\}\\leq\\left\(\\frac\{4\}\{3\}\\right\)^\{3\}\+\\frac\{4\}\{3\}=\\frac\{100\}\{27\}<4\.Hence, for everyt≥1t\\geq 1,

xt\+1,1=xt,1−gt,1\(Dt\+1\)11≥xt,1−432​\(T−1\)\+1\.x\_\{t\+1,1\}=x\_\{t,1\}\-\\frac\{g\_\{t,1\}\}\{\(D\_\{t\+1\}\)\_\{11\}\}\\geq x\_\{t,1\}\-\\frac\{4\}\{32\(T\-1\)\+1\}\.Iterating this bound from time11up to timet≤T−1t\\leq T\-1yields

xt,1≥x1,1−4​\(t−1\)32​\(T−1\)\+1≥x1,1−4​\(T−2\)32​\(T−1\)\+1\.x\_\{t,1\}\\geq x\_\{1,1\}\-\\frac\{4\(t\-1\)\}\{32\(T\-1\)\+1\}\\geq x\_\{1,1\}\-\\frac\{4\(T\-2\)\}\{32\(T\-1\)\+1\}\.Using the explicit formula forx1,1x\_\{1,1\},

xt,1≥1\+132​\(T−1\)\+1−4​\(T−2\)32​\(T−1\)\+1=28​T−2232​T−31\.x\_\{t,1\}\\geq 1\+\\frac\{1\}\{32\(T\-1\)\+1\}\-\\frac\{4\(T\-2\)\}\{32\(T\-1\)\+1\}=\\frac\{28T\-22\}\{32T\-31\}\.Since

8​\(28​T−22\)=224​T−176\>224​T−217=7​\(32​T−31\),8\(28T\-22\)=224T\-176\>224T\-217=7\(32T\-31\),we get

xt,1\>78for all​t=1,…,T−1\.x\_\{t,1\}\>\\frac\{7\}\{8\}\\qquad\\text\{for all \}t=1,\\dots,T\-1\.
Step 4: anisotropic miscalibration and nonstationarity onℰ\\mathcal\{E\}\.

Fixt∈\{1,…,T−1\}t\\in\\\{1,\\dots,T\-1\\\}\. Sincext,1<4/3x\_\{t,1\}<4/3,

∂112f⁡\(xt\)=3​xt,12\+1<3​\(43\)2\+1=193<16=∂222f⁡\(xt\)\.\\partial\_\{11\}^\{2\}f\(x\_\{t\}\)=3x\_\{t,1\}^\{2\}\+1<3\\left\(\\frac\{4\}\{3\}\\right\)^\{2\}\+1=\\frac\{19\}\{3\}<16=\\partial\_\{22\}^\{2\}f\(x\_\{t\}\)\.This proves

∂112f⁡\(xt\)<∂222f⁡\(xt\)\.\\partial\_\{11\}^\{2\}f\(x\_\{t\}\)<\\partial\_\{22\}^\{2\}f\(x\_\{t\}\)\.
Next, by Steps 2 and 3,

\(Dt\)11≥32​\(T−1\)\+1,\(Dt\)22<18\.\(D\_\{t\}\)\_\{11\}\\geq 32\(T\-1\)\+1,\\qquad\(D\_\{t\}\)\_\{22\}<18\.Therefore

\(Dt\)11\>32​\(T−1\)=169​\(T−1\)⋅18\>169​\(T−1\)​\(Dt\)22\.\(D\_\{t\}\)\_\{11\}\>32\(T\-1\)=\\frac\{16\}\{9\}\(T\-1\)\\cdot 18\>\\frac\{16\}\{9\}\(T\-1\)\(D\_\{t\}\)\_\{22\}\.This proves the claimed anisotropic denominator inflation\.

Finally, sincext,1\>7/8x\_\{t,1\}\>7/8,

∂1f⁡\(xt\)=xt,13\+xt,1\>\(78\)3\+78=343512\+448512=791512\>1\.\\partial\_\{1\}f\(x\_\{t\}\)=x\_\{t,1\}^\{3\}\+x\_\{t,1\}\>\\left\(\\frac\{7\}\{8\}\\right\)^\{3\}\+\\frac\{7\}\{8\}=\\frac\{343\}\{512\}\+\\frac\{448\}\{512\}=\\frac\{791\}\{512\}\>1\.Hence

‖∇f​\(xt\)‖≥\|∂1f⁡\(xt\)\|\>1\.\\\|\\nabla f\(x\_\{t\}\)\\\|\\geq\|\\partial\_\{1\}f\(x\_\{t\}\)\|\>1\.Thus all three displayed properties in the theorem hold for everyt=1,…,T−1t=1,\\dots,T\-1on the eventℰ\\mathcal\{E\}\.

Step 5: lower bound on the averaged Euclidean stationarity measure\.

Onℰ\\mathcal\{E\}, we have just shown that

‖∇f​\(xt\)‖\>1for all​t=1,…,T−1\.\\\|\\nabla f\(x\_\{t\}\)\\\|\>1\\qquad\\text\{for all \}t=1,\\dots,T\-1\.Also

‖∇f​\(x0\)‖2=102\+162=356\>1\.\\\|\\nabla f\(x\_\{0\}\)\\\|^\{2\}=10^\{2\}\+16^\{2\}=356\>1\.Therefore, onℰ\\mathcal\{E\},

1T​∑t=0T−1‖∇f​\(xt\)‖2\>1\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\>1\.Sinceℙ⁡\(ℰ\)=pT\\mathbb\{P\}\(\\mathcal\{E\}\)=p\_\{T\}, it follows that

ℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2\>1\)≥pT\.\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\>1\\right\)\\geq p\_\{T\}\.
Step 6: consequence for any\(1−δ\)\(1\-\\delta\)\-high\-probability guarantee\.

Suppose

ℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2≤1\)≥1−δ\.\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq 1\\right\)\\geq 1\-\\delta\.Then necessarily

ℙ⁡\(1T​∑t=0T−1‖∇f​\(xt\)‖2\>1\)≤δ\.\\mathbb\{P\}\\\!\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\>1\\right\)\\leq\\delta\.By the lower bound proved above, this implies

Using

pT=σ2B2\+σ2,B=32​\(T−1\)−10,p\_\{T\}=\\frac\{\\sigma^\{2\}\}\{B^\{2\}\+\\sigma^\{2\}\},\\qquad B=32\(T\-1\)\-10,we get

σ2B2\+σ2≤δ⟹σ2≤δ⁡\(B2\+σ2\)⟹\(1−δ\)​σ2≤δ​B2\.\\frac\{\\sigma^\{2\}\}\{B^\{2\}\+\\sigma^\{2\}\}\\leq\\delta\\quad\\Longrightarrow\\quad\\sigma^\{2\}\\leq\\delta\(B^\{2\}\+\\sigma^\{2\}\)\\quad\\Longrightarrow\\quad\(1\-\\delta\)\\sigma^\{2\}\\leq\\delta B^\{2\}\.Hence

B≥σ​1−δδ\.B\\geq\\sigma\\sqrt\{\\frac\{1\-\\delta\}\{\\delta\}\}\.Substituting backB=32​\(T−1\)−10B=32\(T\-1\)\-10yields

32​\(T−1\)−10≥σ​1−δδ,32\(T\-1\)\-10\\geq\\sigma\\sqrt\{\\frac\{1\-\\delta\}\{\\delta\}\},that is,

T≥1\+132​\(10\+σ​1−δδ\)\.T\\geq 1\+\\frac\{1\}\{32\}\\left\(10\+\\sigma\\sqrt\{\\frac\{1\-\\delta\}\{\\delta\}\}\\right\)\.This proves the theorem\. ∎

Before proving Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1), we introduce several auxiliary lemmas and definitions that will be used throughout the proof\.

### A\.2Proofs of Auxiliary Lemmas

###### Definition 2\(Predictable level\-set stopping time\)\.

Define

τ:=min⁡\{t≤T:f⁡\(xt\)−f⋆\>F\}∧T\.\\tau:=\\min\\\{t\\leq T:\\ f\(x\_\{t\}\)\-f^\{\\star\}\>F\\\}\\wedge T\.Then𝟏\{t<τ\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable\.

###### Lemma 7\(Beforeτ\\tau: gradient bound\)\.

For allt<τt<\\tau,f⁡\(xt\)−f⋆≤Ff\(x\_\{t\}\)\-f^\{\\star\}\\leq Fand thus‖∇f​\(xt\)‖≤G\\\|\\nabla f\(x\_\{t\}\)\\\|\\leq G\.

###### Proof\.

Immediate from Definition[2](https://arxiv.org/html/2609.30276#Thmdefinition2)and Lemma[2](https://arxiv.org/html/2609.30276#Thmlemma2)\. ∎

#### A\.2\.1Proof of Lemma[3](https://arxiv.org/html/2609.30276#Thmlemma3)

###### Lemma 8\(One\-step descent with same\-step correction\)\.

Assume \([4](https://arxiv.org/html/2609.30276#S4.E4)\), for everyt<τt<\\tau,

f\(xt\+1\)−f\(xt\)≤−hAt−h⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩−hMt\+hEt\+L2h2∥Dt\+1−1g~t∥2\.f\(x\_\{t\+1\}\)\-f\(x\_\{t\}\)\\leq\-h\{\\color\[rgb\]\{0,0\.2969,0\.6016\}A\_\{t\}\}\-h\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\rangle\}\-h\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}M\_\{t\}\}\+h\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\+\\frac\{L\}\{2\}h^\{2\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}\.\(A\.3\)

###### Proof\.

Fort<τt<\\tau, Lemma[7](https://arxiv.org/html/2609.30276#Thmlemma7)and \([3](https://arxiv.org/html/2609.30276#S4.E3)\) allow us to apply Lemma[1](https://arxiv.org/html/2609.30276#Thmlemma1)at\(xt,xt\+1\)\(x\_\{t\},x\_\{t\+1\}\)\. Substitutingxt\+1−xt=−h​Dt\+1−1​g~tx\_\{t\+1\}\-x\_\{t\}=\-hD\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}from Algorithm[2](https://arxiv.org/html/2609.30276#alg2)gives

f⁡\(xt\+1\)−f⁡\(xt\)≤−h⁡⟨∇f​\(xt\),Dt\+1−1​g~t⟩\+L2​h2​‖Dt\+1−1​g~t‖2\.f\(x\_\{t\+1\}\)\-f\(x\_\{t\}\)\\leq\-h\\left\\langle\\nabla f\(x\_\{t\}\),D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\right\\rangle\+\\frac\{L\}\{2\}h^\{2\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\.Add and subtractDt−1D\_\{t\}^\{\-1\}in the first\-order term:

−⟨∇f​\(xt\),Dt\+1−1​g~t⟩=−⟨∇f​\(xt\),Dt−1​g~t⟩\+Et,\-\\left\\langle\\nabla f\(x\_\{t\}\),D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\right\\rangle=\-\\left\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\right\\rangle\+E\_\{t\},whereEt=⟨∇f​\(xt\),\(Dt−1−Dt\+1−1\)​g~t⟩E\_\{t\}=\\langle\\nabla f\(x\_\{t\}\),\(D\_\{t\}^\{\-1\}\-D\_\{t\+1\}^\{\-1\}\)\\tilde\{g\}\_\{t\}\\rangle\. Now decomposeg~t=μt\+ξ~t\\tilde\{g\}\_\{t\}=\\mu\_\{t\}\+\\tilde\{\\xi\}\_\{t\}and recallμt=∇f​\(xt\)\+𝔼t−1​\[rt\]\\mu\_\{t\}=\\nabla f\(x\_\{t\}\)\+\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\(fromClippied Noiseparagraph of Section[4](https://arxiv.org/html/2609.30276#S4)\)\. This yields

−⟨∇f\(xt\),Dt−1g~t⟩=−At−⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩−Mt,\-\\left\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\right\\rangle=\-A\_\{t\}\-\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\right\\rangle\-M\_\{t\},which proves the claim\. ∎

Before presenting the proof of Lemma[5](https://arxiv.org/html/2609.30276#Thmlemma5), we must sum \([A\.3](https://arxiv.org/html/2609.30276#A1.E3)\) in Lemma[8](https://arxiv.org/html/2609.30276#Thmlemma8)and individually bound each resulting term\.

#### A\.2\.2Bounding⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\right\\rangle\}

###### Lemma 9\(Clipping residual first moment\)\.

For allt<τt<\\tau,

𝔼t−1​‖rt‖≤𝔼t−1​‖gt‖2C≤VC\.\\mathbb\{E\}\_\{t\-1\}\\\|r\_\{t\}\\\|\\leq\\frac\{\\mathbb\{E\}\_\{t\-1\}\\\|g\_\{t\}\\\|^\{2\}\}\{C\}\\leq\\frac\{V\}\{C\}\.

###### Proof\.

‖rt‖=\(‖gt‖−C\)\+≤‖gt‖2/C\\\|r\_\{t\}\\\|=\(\\\|g\_\{t\}\\\|\-C\)\_\{\+\}\\leq\\\|g\_\{t\}\\\|^\{2\}/Cimplies𝔼t−1​‖rt‖≤𝔼t−1​‖gt‖2/C\\mathbb\{E\}\_\{t\-1\}\\\|r\_\{t\}\\\|\\leq\\mathbb\{E\}\_\{t\-1\}\\\|g\_\{t\}\\\|^\{2\}/C\. Fort<τt<\\tau,‖∇f​\(xt\)‖≤G\\\|\\nabla f\(x\_\{t\}\)\\\|\\leq Gand𝔼t−1​‖ξt‖2≤σ2\\mathbb\{E\}\_\{t\-1\}\\\|\\xi\_\{t\}\\\|^\{2\}\\leq\\sigma^\{2\}give𝔼t−1​‖gt‖2=‖∇f​\(xt\)‖2\+𝔼t−1​‖ξt‖2≤G2\+σ2=V\\mathbb\{E\}\_\{t\-1\}\\\|g\_\{t\}\\\|^\{2\}=\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\+\\mathbb\{E\}\_\{t\-1\}\\\|\\xi\_\{t\}\\\|^\{2\}\\leq G^\{2\}\+\\sigma^\{2\}=V\. ∎

###### Lemma 10\(Bias coupled toAtA\_\{t\}\)\.

For allt<τt<\\tau,

\|⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩\|≤14At\+V2D¯​C2\.\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\Big\|\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\right\\rangle\\Big\|\}\\leq\\frac\{1\}\{4\}A\_\{t\}\+\\frac\{V^\{2\}\}\{\\underline\{D\}\\,C^\{2\}\}\.

###### Proof\.

∥Dt−1∇f\(xt\)∥2=⟨∇f\(xt\),Dt−2∇f\(xt\)⟩≤∥Dt−1∥At≤1D¯At\\\|D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\\|^\{2\}=\\left\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-2\}\\nabla f\(x\_\{t\}\)\\right\\rangle\\leq\\\|D\_\{t\}^\{\-1\}\\\|\\,A\_\{t\}\\leq\\frac\{1\}\{\\underline\{D\}\}A\_\{t\}\. Then

\|⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩\|≤∥Dt−1∇f\(xt\)∥∥𝔼t−1\[rt\]∥≤AtD¯𝔼t−1∥rt∥≤AtD¯VC,\\Big\|\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\right\\rangle\\Big\|\\leq\\\|D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\\|\\,\\\|\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\\|\\leq\\sqrt\{\\frac\{A\_\{t\}\}\{\\underline\{D\}\}\}\\;\\mathbb\{E\}\_\{t\-1\}\\\|r\_\{t\}\\\|\\leq\\sqrt\{\\frac\{A\_\{t\}\}\{\\underline\{D\}\}\}\\;\\frac\{V\}\{C\},and applya​b≤14​a2\+b2ab\\leq\\frac\{1\}\{4\}a^\{2\}\+b^\{2\}witha=Ata=\\sqrt\{A\_\{t\}\}andb=VC​D¯b=\\frac\{V\}\{C\\sqrt\{\\underline\{D\}\}\}\. ∎

#### A\.2\.3Bounding∑t<τEt\\sum\_\{t<\\tau\}E\_\{t\}

###### Lemma 11\(Deterministic bound on the cumulative same\-step correction\)\.

For every sample path,

∑t<τ\|Et\|≤d​G​CD¯\.\\sum\_\{t<\\tau\}\|E\_\{t\}\|\\leq\\frac\{dGC\}\{\\underline\{D\}\}\.Consequently,

∑t<τEt≤d​G​CD¯\.\\sum\_\{t<\\tau\}E\_\{t\}\\leq\\frac\{dGC\}\{\\underline\{D\}\}\.

###### Proof\.

Fix a coordinateii\. Becauseyt\+1,i≥yt,iy\_\{t\+1,i\}\\geq y\_\{t,i\}, the scalar sequence\(Dt,i−1\)t≥0\(D\_\{t,i\}^\{\-1\}\)\_\{t\\geq 0\}is nonincreasing, so

Dt,i−1−Dt\+1,i−1≥0\.D\_\{t,i\}^\{\-1\}\-D\_\{t\+1,i\}^\{\-1\}\\geq 0\.Fort<τt<\\tau, Lemma[7](https://arxiv.org/html/2609.30276#Thmlemma7)gives\|∇if​\(xt\)\|≤G\|\\nabla\_\{i\}f\(x\_\{t\}\)\|\\leq G, while clipping gives\|g~t,i\|≤C\|\\tilde\{g\}\_\{t,i\}\|\\leq C\. Hence

\|Et\|≤∑i=1d\|∇if​\(xt\)\|​\(Dt,i−1−Dt\+1,i−1\)​\|g~t,i\|≤G​C​∑i=1d\(Dt,i−1−Dt\+1,i−1\)\.\|E\_\{t\}\|\\leq\\sum\_\{i=1\}^\{d\}\|\\nabla\_\{i\}f\(x\_\{t\}\)\|\\,\(D\_\{t,i\}^\{\-1\}\-D\_\{t\+1,i\}^\{\-1\}\)\\,\|\\tilde\{g\}\_\{t,i\}\|\\leq GC\\sum\_\{i=1\}^\{d\}\(D\_\{t,i\}^\{\-1\}\-D\_\{t\+1,i\}^\{\-1\}\)\.Summing overt=0,…,τ−1t=0,\\dots,\\tau\-1telescopes coordinatewise:

∑t<τ\|Et\|≤G​C​∑i=1d∑t=0τ−1\(Dt,i−1−Dt\+1,i−1\)=G​C​∑i=1d\(D0,i−1−Dτ,i−1\)\.\\sum\_\{t<\\tau\}\|E\_\{t\}\|\\leq GC\\sum\_\{i=1\}^\{d\}\\sum\_\{t=0\}^\{\\tau\-1\}\(D\_\{t,i\}^\{\-1\}\-D\_\{t\+1,i\}^\{\-1\}\)=GC\\sum\_\{i=1\}^\{d\}\(D\_\{0,i\}^\{\-1\}\-D\_\{\\tau,i\}^\{\-1\}\)\.FinallyD0,i=yinit\+ϵ0=D¯D\_\{0,i\}=\\sqrt\{y\_\{\\mathrm\{init\}\}\}\+\\epsilon\_\{0\}=\\underline\{D\}andDτ,i−1≥0D\_\{\\tau,i\}^\{\-1\}\\geq 0, so

∑t<τ\|Et\|≤G​C​∑i=1dD0,i−1=d​G​CD¯\.\\sum\_\{t<\\tau\}\|E\_\{t\}\|\\leq GC\\sum\_\{i=1\}^\{d\}D\_\{0,i\}^\{\-1\}=\\frac\{dGC\}\{\\underline\{D\}\}\.The second claim is immediate from∑t<τEt≤∑t<τ\|Et\|\\sum\_\{t<\\tau\}E\_\{t\}\\leq\\sum\_\{t<\\tau\}\|E\_\{t\}\|\. ∎

#### A\.2\.4Bounding∑t<τ‖Dt\+1−1​g~t‖2\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}

For coordinateii, define

at:=g~t,i2,st:=yt,i\+ϵ02\.a\_\{t\}:=\\tilde\{g\}\_\{t,i\}^\{2\},\\qquad s\_\{t\}:=y\_\{t,i\}\+\\epsilon\_\{0\}^\{2\}\.Thenst\+1=st\+ats\_\{t\+1\}=s\_\{t\}\+a\_\{t\}andst≥s0=yinit\+ϵ02s\_\{t\}\\geq s\_\{0\}=y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}^\{2\}\.

###### Lemma 12\(Lagged harmonic bound\)\.

Assumeat≤C2a\_\{t\}\\leq C^\{2\}fort=0,…,T−1t=0,\\dots,T\-1\. Then

∑t=0T−1atst≤log⁡\(sTs0\)\+C2s0\.\\sum\_\{t=0\}^\{T\-1\}\\frac\{a\_\{t\}\}\{s\_\{t\}\}\\leq\\log\\Big\(\\frac\{s\_\{T\}\}\{s\_\{0\}\}\\Big\)\+\\frac\{C^\{2\}\}\{s\_\{0\}\}\.

###### Proof\.

Identity:atst=atst\+1\+at2st​st\+1\\frac\{a\_\{t\}\}\{s\_\{t\}\}=\\frac\{a\_\{t\}\}\{s\_\{t\+1\}\}\+\\frac\{a\_\{t\}^\{2\}\}\{s\_\{t\}s\_\{t\+1\}\}\. Alsolog⁡\(st\+1\)−log⁡\(st\)=log⁡\(1\+at/st\)≥atst\+1\\log\(s\_\{t\+1\}\)\-\\log\(s\_\{t\}\)=\\log\(1\+a\_\{t\}/s\_\{t\}\)\\geq\\frac\{a\_\{t\}\}\{s\_\{t\+1\}\}, so∑t=0T−1atst\+1≤log⁡\(sT/s0\)\\sum\_\{t=0\}^\{T\-1\}\\frac\{a\_\{t\}\}\{s\_\{t\+1\}\}\\leq\\log\(s\_\{T\}/s\_\{0\}\)\.

Exact telescoping:1st−1st\+1=atst​st\+1\\frac\{1\}\{s\_\{t\}\}\-\\frac\{1\}\{s\_\{t\+1\}\}=\\frac\{a\_\{t\}\}\{s\_\{t\}s\_\{t\+1\}\}impliesat2st​st\+1=at​\(1st−1st\+1\)≤C2​\(1st−1st\+1\)\\frac\{a\_\{t\}^\{2\}\}\{s\_\{t\}s\_\{t\+1\}\}=a\_\{t\}\(\\frac\{1\}\{s\_\{t\}\}\-\\frac\{1\}\{s\_\{t\+1\}\}\)\\leq C^\{2\}\(\\frac\{1\}\{s\_\{t\}\}\-\\frac\{1\}\{s\_\{t\+1\}\}\)\. Summing gives∑t=0T−1at2st​st\+1≤C2​\(1s0−1sT\)≤C2/s0\\sum\_\{t=0\}^\{T\-1\}\\frac\{a\_\{t\}^\{2\}\}\{s\_\{t\}s\_\{t\+1\}\}\\leq C^\{2\}\(\\frac\{1\}\{s\_\{0\}\}\-\\frac\{1\}\{s\_\{T\}\}\)\\leq C^\{2\}/s\_\{0\}\. ∎

###### Lemma 13\(Pathwise bound on∑t<τ‖Dt−1​g~t‖2\\sum\_\{t<\\tau\}\\\|D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\)\.

Lets0=yinit\+ϵ02s\_\{0\}=y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}^\{2\}\. Then almost surely,

∑t<τ‖Dt−1​g~t‖2≤HT:=d​log⁡\(1\+T​C2s0\)\+d​C2s0\.\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}\\leq H\_\{T\}:=d\\log\\Big\(1\+\\frac\{TC^\{2\}\}\{s\_\{0\}\}\\Big\)\+d\\,\\frac\{C^\{2\}\}\{s\_\{0\}\}\.

###### Proof\.

Fix a coordinateiiand sum only over the active timest=0,…,τ−1t=0,\\dots,\\tau\-1\. For such times,\(yt,i\+ϵ0\)2≥yt,i\+ϵ02=st\(\\sqrt\{y\_\{t,i\}\}\+\\epsilon\_\{0\}\)^\{2\}\\geq y\_\{t,i\}\+\\epsilon\_\{0\}^\{2\}=s\_\{t\}, hence

∑t<τg~t,i2\(yt,i\+ϵ0\)2≤∑t=0τ−1atst≤log⁡\(1\+τ​C2s0\)\+C2s0≤log⁡\(1\+T​C2s0\)\+C2s0,\\sum\_\{t<\\tau\}\\frac\{\\tilde\{g\}\_\{t,i\}^\{2\}\}\{\(\\sqrt\{y\_\{t,i\}\}\+\\epsilon\_\{0\}\)^\{2\}\}\\leq\\sum\_\{t=0\}^\{\\tau\-1\}\\frac\{a\_\{t\}\}\{s\_\{t\}\}\\leq\\log\\Big\(1\+\\frac\{\\tau C^\{2\}\}\{s\_\{0\}\}\\Big\)\+\\frac\{C^\{2\}\}\{s\_\{0\}\}\\leq\\log\\Big\(1\+\\frac\{TC^\{2\}\}\{s\_\{0\}\}\\Big\)\+\\frac\{C^\{2\}\}\{s\_\{0\}\},where we used Lemma[12](https://arxiv.org/html/2609.30276#Thmlemma12)and the boundτ≤T\\tau\\leq T\. Summing over coordinatesi=1,…,di=1,\\dots,dyields the claim\. ∎

#### A\.2\.5Bounding∑t<τMt\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}M\_\{t\}\}

###### Lemma 14\(Stopped martingale sum has zero mean\)\.

Define

Mt:=⟨Dt−1∇f\(xt\),ξ~t⟩\.M\_\{t\}:=\\left\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\tilde\{\\xi\}\_\{t\}\\right\\rangle\.Then𝔼t−1​\[Mt\]=0\\mathbb\{E\}\_\{t\-1\}\[M\_\{t\}\]=0and

𝔼⁡\[∑t<τMt\]=0\.\\mathbb\{E\}\\Big\[\\sum\_\{t<\\tau\}M\_\{t\}\\Big\]=0\.

###### Proof\.

Dt−1∇f\(xt\)D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable and𝔼t−1​\[ξ~t\]=0\\mathbb\{E\}\_\{t\-1\}\[\\tilde\{\\xi\}\_\{t\}\]=0, hence𝔼t−1​\[Mt\]=0\\mathbb\{E\}\_\{t\-1\}\[M\_\{t\}\]=0\. Because𝟏\{t<τ\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable \(Definition[2](https://arxiv.org/html/2609.30276#Thmdefinition2)\),𝔼\[Mt𝟏\{t<τ\}\]=𝔼\[𝟏\{t<τ\}𝔼t−1Mt\]=0\\mathbb\{E\}\[M\_\{t\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\]=\\mathbb\{E\}\[\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\\mathbb\{E\}\_\{t\-1\}M\_\{t\}\]=0\. Summing overt=0,…,T−1t=0,\\dots,T\-1yields the claim\. ∎

###### Lemma 15\(Freedman tradeoff for the stopped clipped\-noise martingale\)\.

For everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

−∑t<τMt≤14∑t<τAt\+Γlog1δ,Γ:=2​V\+23​C​GD¯\.\-\\sum\_\{t<\\tau\}M\_\{t\}\\leq\\frac\{1\}\{4\}\\sum\_\{t<\\tau\}A\_\{t\}\+\\Gamma\\log\\\!\\frac\{1\}\{\\delta\},\\qquad\\Gamma:=\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}\.

###### Proof\.

Define the stopped martingale\-difference sequence

Xt:=−Mt𝟏\{t<τ\}\.X\_\{t\}:=\-M\_\{t\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\.Then𝔼t−1​\[Xt\]=0\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}\]=0because𝟏\{t<τ\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable and Lemma[14](https://arxiv.org/html/2609.30276#Thmlemma14)gives𝔼t−1​\[Mt\]=0\\mathbb\{E\}\_\{t\-1\}\[M\_\{t\}\]=0\. Also,

\|Xt\|≤𝟏\{t<τ\}∥Dt−1∇f\(xt\)∥∥ξ~t∥≤2​C​GD¯=:b\.\|X\_\{t\}\|\\leq\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\\\|D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\\|\\,\\\|\\tilde\{\\xi\}\_\{t\}\\\|\\leq\\frac\{2CG\}\{\\underline\{D\}\}\\;=:\\;b\.Next,

𝔼t−1\[Xt2\]≤𝟏\{t<τ\}∥Dt−1∇f\(xt\)∥2𝔼t−1∥ξ~t∥2\.\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}^\{2\}\]\\leq\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\\\|D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\,\\mathbb\{E\}\_\{t\-1\}\\\|\\tilde\{\\xi\}\_\{t\}\\\|^\{2\}\.Since𝔼t−1​‖ξ~t‖2≤𝔼t−1​‖g~t‖2≤𝔼t−1​‖gt‖2≤V\\mathbb\{E\}\_\{t\-1\}\\\|\\tilde\{\\xi\}\_\{t\}\\\|^\{2\}\\leq\\mathbb\{E\}\_\{t\-1\}\\\|\\tilde\{g\}\_\{t\}\\\|^\{2\}\\leq\\mathbb\{E\}\_\{t\-1\}\\\|g\_\{t\}\\\|^\{2\}\\leq Vand∥Dt−1∇f\(xt\)∥2≤At/D¯\\\|D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq A\_\{t\}/\\underline\{D\}by the estimate used in Lemma[10](https://arxiv.org/html/2609.30276#Thmlemma10), we obtain

𝔼t−1\[Xt2\]≤VD¯At𝟏\{t<τ\}\.\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}^\{2\}\]\\leq\\frac\{V\}\{\\underline\{D\}\}A\_\{t\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\.A standard Bernstein\-Freedman exponential supermartingale bound therefore yields, for everyλ∈\(0,3/b\)\\lambda\\in\(0,3/b\),

ℙ⁡\(∑t=0T−1Xt\>λ2​\(1−λ​b/3\)​VD¯​∑t<τAt\+log⁡\(1/δ\)λ\)≤δ\.\\mathbb\{P\}\\\!\\left\(\\sum\_\{t=0\}^\{T\-1\}X\_\{t\}\>\\frac\{\\lambda\}\{2\(1\-\\lambda b/3\)\}\\frac\{V\}\{\\underline\{D\}\}\\sum\_\{t<\\tau\}A\_\{t\}\+\\frac\{\\log\(1/\\delta\)\}\{\\lambda\}\\right\)\\leq\\delta\.Choose

λ:=D¯2​V\+23​C​G\.\\lambda:=\\frac\{\\underline\{D\}\}\{2V\+\\frac\{2\}\{3\}CG\}\.Thenλ<3/b\\lambda<3/band

λ2​\(1−λ​b/3\)​VD¯=14,1λ=2​V\+23​C​GD¯=Γ\.\\frac\{\\lambda\}\{2\(1\-\\lambda b/3\)\}\\frac\{V\}\{\\underline\{D\}\}=\\frac\{1\}\{4\},\\qquad\\frac\{1\}\{\\lambda\}=\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}=\\Gamma\.Substituting this choice into the previous display gives the claim\. ∎

#### A\.2\.6High probability upper bound onDtD\_\{t\}

###### Lemma 16\(High\-probability bound onDtD\_\{t\}via the total stopped energy\)\.

Define the total stopped clipped\-gradient energy

Y~T:=∑t=0T−1∥g~t∥21\{t<τ\}\.\\widetilde\{Y\}\_\{T\}\\,:=\\,\\sum\_\{t=0\}^\{T\-1\}\\\|\\tilde\{g\}\_\{t\}\\\|^\{2\}\\,\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\.Then for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

Y~T≤T​V\+2​T​C2​V​log⁡1δ\+2​C23​log⁡1δ=:BT,δ\.\\widetilde\{Y\}\_\{T\}\\leq TV\+\\sqrt\{2TC^\{2\}V\\log\\\!\\frac\{1\}\{\\delta\}\}\+\\frac\{2C^\{2\}\}\{3\}\\log\\\!\\frac\{1\}\{\\delta\}\\;=:\\;B\_\{T,\\delta\}\.Consequently, on the intersection\{τ=T\}∩\{Y~T≤BT,δ\}\\\{\\tau=T\\\}\\cap\\\{\\widetilde\{Y\}\_\{T\}\\leq B\_\{T,\\delta\}\\\},

maxt≤T\|Dt\|≤yinit\+BT,δ\+ϵ0=:D¯δ\.\\max\_\{t\\leq T\}\\\|D\_\{t\}\\\|\\leq\\sqrt\{y\_\{\\mathrm\{init\}\}\+B\_\{T,\\delta\}\}\+\\epsilon\_\{0\}\\;=:\\;\\overline\{D\}\_\{\\delta\}\.

###### Proof\.

Set

Xt:=∥g~t∥2𝟏\{t<τ\},Zt:=Xt−𝔼t−1\[Xt\]\.X\_\{t\}:=\\\|\\tilde\{g\}\_\{t\}\\\|^\{2\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\},\\qquad Z\_\{t\}:=X\_\{t\}\-\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}\]\.Because𝟏\{t<τ\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}isℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable and‖g~t‖≤C\\\|\\tilde\{g\}\_\{t\}\\\|\\leq C, we have0≤Xt≤C20\\leq X\_\{t\}\\leq C^\{2\}, hence\|Zt\|≤C2\|Z\_\{t\}\|\\leq C^\{2\}\. Also, on\{t<τ\}\\\{t<\\tau\\\}we have‖∇f​\(xt\)‖≤G\\\|\\nabla f\(x\_\{t\}\)\\\|\\leq Gby Lemma[7](https://arxiv.org/html/2609.30276#Thmlemma7), so

𝔼t−1\[Xt\]≤𝔼t−1\[∥gt∥2𝟏\{t<τ\}\]=𝟏\{t<τ\}𝔼t−1∥gt∥2≤𝟏\{t<τ\}V≤V\.\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}\]\\leq\\mathbb\{E\}\_\{t\-1\}\[\\\|g\_\{t\}\\\|^\{2\}\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\]=\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}\\mathbb\{E\}\_\{t\-1\}\\\|g\_\{t\}\\\|^\{2\}\\leq\\mathbf\{1\}\_\{\\\{t<\\tau\\\}\}V\\leq V\.Moreover,

𝔼t−1​\[Zt2\]≤𝔼t−1​\[Xt2\]≤C2​𝔼t−1​\[Xt\]≤C2​V\.\\mathbb\{E\}\_\{t\-1\}\[Z\_\{t\}^\{2\}\]\\leq\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}^\{2\}\]\\leq C^\{2\}\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}\]\\leq C^\{2\}V\.Thus the predictable quadratic variation of∑s=0tZs\\sum\_\{s=0\}^\{t\}Z\_\{s\}is bounded byT​C2​VTC^\{2\}V\. Applying Freedman’s inequality to the martingale\-difference sequence\(Zt\)\(Z\_\{t\}\)with increment boundC2C^\{2\}gives, for everyδ∈\(0,1\)\\delta\\in\(0,1\),

ℙ⁡\(∑t=0T−1Zt\>2​T​C2​V​log⁡1δ\+2​C23​log⁡1δ\)≤δ\.\\mathbb\{P\}\\\!\\left\(\\sum\_\{t=0\}^\{T\-1\}Z\_\{t\}\>\\sqrt\{2TC^\{2\}V\\log\\\!\\frac\{1\}\{\\delta\}\}\+\\frac\{2C^\{2\}\}\{3\}\\log\\\!\\frac\{1\}\{\\delta\}\\right\)\\leq\\delta\.Since∑t=0T−1𝔼t−1​\[Xt\]≤T​V\\sum\_\{t=0\}^\{T\-1\}\\mathbb\{E\}\_\{t\-1\}\[X\_\{t\}\]\\leq TV, the displayed bound implies

Y~T=∑t=0T−1Xt≤T​V\+2​T​C2​V​log⁡1δ\+2​C23​log⁡1δ\\widetilde\{Y\}\_\{T\}=\\sum\_\{t=0\}^\{T\-1\}X\_\{t\}\\leq TV\+\\sqrt\{2TC^\{2\}V\\log\\\!\\frac\{1\}\{\\delta\}\}\+\\frac\{2C^\{2\}\}\{3\}\\log\\\!\\frac\{1\}\{\\delta\}with probability at least1−δ1\-\\delta\. Finally, on\{τ=T\}\\\{\\tau=T\\\}we have

yT,i=yinit\+∑t=0T−1g~t,i2≤yinit\+∑t=0T−1‖g~t‖2=yinit\+Y~T,y\_\{T,i\}=y\_\{\\mathrm\{init\}\}\+\\sum\_\{t=0\}^\{T\-1\}\\tilde\{g\}\_\{t,i\}^\{2\}\\leq y\_\{\\mathrm\{init\}\}\+\\sum\_\{t=0\}^\{T\-1\}\\\|\\tilde\{g\}\_\{t\}\\\|^\{2\}=y\_\{\\mathrm\{init\}\}\+\\widetilde\{Y\}\_\{T\},andyty\_\{t\}is coordinatewise nondecreasing, somaxt≤T⁡yt,i≤yT,i\\max\_\{t\\leq T\}y\_\{t,i\}\\leq y\_\{T,i\}\. Therefore on\{τ=T\}∩\{Y~T≤BT,δ\}\\\{\\tau=T\\\}\\cap\\\{\\widetilde\{Y\}\_\{T\}\\leq B\_\{T,\\delta\}\\\},

maxt≤T⁡Dt,i≤yinit\+BT,δ\+ϵ0for every​i,\\max\_\{t\\leq T\}D\_\{t,i\}\\leq\\sqrt\{y\_\{\\mathrm\{init\}\}\+B\_\{T,\\delta\}\}\+\\epsilon\_\{0\}\\qquad\\text\{for every \}i,which yields the claimed operator\-norm bound\. ∎

#### A\.2\.7Proof of Lemma[5](https://arxiv.org/html/2609.30276#Thmlemma5)

###### Lemma 17\(Summed descent inequality up toτ\\tau\)\.

Assume the neighborhood condition \([4](https://arxiv.org/html/2609.30276#S4.E4)\) holds\. Then, for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, we have

f⁡\(xτ\)−f⋆\+h2​∑t<τAt≤Δ0\+h​T​V2D¯​C2⏟clipping\-residualcontribution\+L2​h2​HT⏟generalizedsmoothness remainder\+h​d​G​CD¯⏟same\-stepcorrection\+h​Γ​log⁡\(1/δ\),f\(x\_\{\\tau\}\)\-f^\{\\star\}\+\\frac\{h\}\{2\}\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.2969,0\.6016\}A\_\{t\}\}\\leq\\Delta\_\{0\}\+\\underbrace\{\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{clipping\-residual\}\\\\ \\text\{contribution\}\\end\{subarray\}\}\}\+\\quad\\underbrace\{\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\frac\{L\}\{2\}h^\{2\}H\_\{T\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{generalized\}\\\\ \\text\{smoothness remainder\}\\end\{subarray\}\}\}\+\\quad\\underbrace\{h\{\\color\[rgb\]\{0,0\.5,0\}\\frac\{dGC\}\{\\underline\{D\}\}\}\}\_\{\\mathclap\{\\begin\{subarray\}\{c\}\\text\{same\-step\}\\\\ \\text\{correction\}\\end\{subarray\}\}\}\+h\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}\\Gamma\\log\(1/\\delta\)\},\(A\.4\), whereHT=d​log⁡\(1\+T​C2yinit\+ε02\)\+d​C2yinit\+ε02H\_\{T\}=d\\log\\left\(1\+\\frac\{TC^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\varepsilon\_\{0\}^\{2\}\}\\right\)\+d\\frac\{C^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\varepsilon\_\{0\}^\{2\}\}andΓ=2​V\+23​C​GD¯\\Gamma=\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}\.

###### Proof\.

Summing \([3](https://arxiv.org/html/2609.30276#S4.E3)\) fort<τt<\\taufrom Lemma[8](https://arxiv.org/html/2609.30276#Thmlemma8)we get

f\(xτ\)−f\(x0\)≤−h∑t<τAt−h∑t<τ⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩−h∑t<τMt\+h∑t<τEt\+L2h2∑t<τ∥Dt\+1−1g~t∥2f\(x\_\{\\tau\}\)\-f\(x\_\{0\}\)\\leq\-h\\sum\_\{t<\\tau\}A\_\{t\}\-h\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0\.7617,0\.3125,0\}\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\rangle\}\-h\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0\.4805,0\.1953,0\.582\}M\_\{t\}\}\+h\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5,0\}E\_\{t\}\}\+\\frac\{L\}\{2\}h^\{2\}\\sum\_\{t<\\tau\}\{\\color\[rgb\]\{0,0\.5117,0\.5117\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\}\(A\.5\)
We bound the four error terms on the right\-hand side separately:

- •Clipping Bias:Using Lemma[10](https://arxiv.org/html/2609.30276#Thmlemma10),−h∑t<τ⟨Dt−1∇f\(xt\),𝔼t−1\[rt\]⟩≤h4∑t<τAt\+h​T​V2D¯​C2\-h\\sum\_\{t<\\tau\}\\langle D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\),\\mathbb\{E\}\_\{t\-1\}\[r\_\{t\}\]\\rangle\\leq\\frac\{h\}\{4\}\\sum\_\{t<\\tau\}A\_\{t\}\+\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}\.
- •Same\-Step Correction:Using Lemma[11](https://arxiv.org/html/2609.30276#Thmlemma11),h​∑t<τEt≤h​d​G​CD¯h\\sum\_\{t<\\tau\}E\_\{t\}\\leq\\frac\{hdGC\}\{\\underline\{D\}\}\.
- •Smoothness Remainder:Using Lemma[12](https://arxiv.org/html/2609.30276#Thmlemma12),L2​h2​∑t<τ‖Dt\+1−1​g~t‖2≤L∘2​h2​HT\\frac\{L\}\{2\}h^\{2\}\\sum\_\{t<\\tau\}\\\|D\_\{t\+1\}^\{\-1\}\\tilde\{g\}\_\{t\}\\\|^\{2\}\\leq\\frac\{L^\{\\circ\}\}\{2\}h^\{2\}H\_\{T\}, whereHT=d​log⁡\(1\+T​C2yinit\+ϵ02\)\+d​C2yinit\+ϵ02H\_\{T\}=d\\log\(1\+\\frac\{TC^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}^\{2\}\}\)\+d\\frac\{C^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}^\{2\}\}\.
- •Martingale Fluctuation:Using Lemma[15](https://arxiv.org/html/2609.30276#Thmlemma15),−h∑t<τMt≤h4∑t<τAt\+hΓlog\(1/δ\)\-h\\sum\_\{t<\\tau\}M\_\{t\}\\leq\\frac\{h\}\{4\}\\sum\_\{t<\\tau\}A\_\{t\}\+h\\Gamma\\log\(1/\\delta\), whereΓ=2​V\+23​C​GD¯\\Gamma=\\frac\{2V\+\\frac\{2\}\{3\}CG\}\{\\underline\{D\}\}\.

Substituting these bounds in \([A\.5](https://arxiv.org/html/2609.30276#A1.E5)\) and rearranging, we obtain \([A\.4](https://arxiv.org/html/2609.30276#A1.E4)\):

f⁡\(xτ\)−f∗\+h2​∑t<τAt≤Δ0\+RT,δN​L​\(F\)f\(x\_\{\\tau\}\)\-f^\{\*\}\+\\frac\{h\}\{2\}\\sum\_\{t<\\tau\}A\_\{t\}\\leq\\Delta\_\{0\}\+R\_\{T,\\delta\}^\{NL\}\(F\)
whereRT,δN​L​\(F\):=h​T​V2D¯​C2\+L2​h2​HT\+h​Γ​log⁡\(1/δ\)\+h​d​G​CD¯R\_\{T,\\delta\}^\{NL\}\(F\):=\\frac\{hTV^\{2\}\}\{\\underline\{D\}C^\{2\}\}\+\\frac\{L\}\{2\}h^\{2\}H\_\{T\}\+h\\Gamma\\log\(1/\\delta\)\+h\\frac\{dGC\}\{\\underline\{D\}\}\.

∎

Now, we will prove Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1)\.

### A\.3Proof of Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1)

###### Theorem 2\(True finite\-horizon Euclidean stationarity for clipped same\-step AdaGrad\)\.

Suppose Assumptions[1](https://arxiv.org/html/2609.30276#Thmassumption1),[2](https://arxiv.org/html/2609.30276#Thmassumption2), and[3](https://arxiv.org/html/2609.30276#Thmassumption3)holds\. Let

Δ0≔f⁡\(x0\)−f⋆\>0,F∘≔2​Δ0,G∘≔G⁡\(F∘\),L∘≔ℓ⁡\(2​G∘\),V∘≔\(G∘\)2\+σ2\.\\Delta\_\{0\}\\coloneqq f\(x\_\{0\}\)\-f^\{\\star\}\>0,\\quad F^\{\\circ\}\\coloneqq 2\\Delta\_\{0\},\\quad G^\{\\circ\}\\coloneqq G\(F^\{\\circ\}\),\\quad L^\{\\circ\}\\coloneqq\\ell\(2G^\{\\circ\}\),\\quad V^\{\\circ\}\\coloneqq\(G^\{\\circ\}\)^\{2\}\+\\sigma^\{2\}\.Fixκ\>0\\kappa\>0, choose\(h,C\)\(h,C\)from \([7](https://arxiv.org/html/2609.30276#S4.E7)\), and setyinit≔C2,y\_\{\\mathrm\{init\}\}\\coloneqq C^\{2\},ϵ0≔C\\epsilon\_\{0\}\\coloneqq C\. Suppose moreover that

η≤min⁡\{2​G∘L∘,Δ04​L∘​d,Δ0​κ8​V∘,Δ0​κ34​\(V∘\)2,3​Δ08​G∘,Δ0d​G∘\},\\eta\\leq\\min\\left\\\{\\frac\{2G^\{\\circ\}\}\{L^\{\\circ\}\},\\sqrt\{\\frac\{\\Delta\_\{0\}\}\{4L^\{\\circ\}d\}\},\\frac\{\\Delta\_\{0\}\\kappa\}\{8V^\{\\circ\}\},\\frac\{\\Delta\_\{0\}\\kappa^\{3\}\}\{4\(V^\{\\circ\}\)^\{2\}\},\\frac\{3\\Delta\_\{0\}\}\{8G^\{\\circ\}\},\\frac\{\\Delta\_\{0\}\}\{dG^\{\\circ\}\}\\right\\\},\(A\.6\)then the neighborhood condition \([4](https://arxiv.org/html/2609.30276#S4.E4)\) holds atF∘F^\{\\circ\}\. Then, with probability at least1−δ1\-\\delta,

f⁡\(xt\)−f⋆≤2​Δ0for all​t=0,…,T,f\(x\_\{t\}\)\-f^\{\\star\}\\leq 2\\Delta\_\{0\}\\qquad\\text\{for all \}t=0,\\dots,T,and

1T∑t=0T−1∥∇f\(xt\)∥2≤4​Δ0​ΛT,δη​T\[\(V∘\+κ2​V∘​log⁡2δT−1/6\+κ2\(\+23log2δ\)T−1/3\)1/2\+κT−1/6\]\.\\frac\{1\}\{T\}\\\!\\sum\_\{t=0\}^\{T\-1\}\\\!\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\\!\\leq\\\!\\frac\{4\\Delta\_\{0\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\{\\eta\\sqrt\{T\}\}\\\!\\\!\\left\[\\\!\\\!\\left\(\\\!V^\{\\circ\}\\\!\+\\\!\\kappa\\sqrt\{2V^\{\\circ\}\\log\\frac\{2\}\{\\delta\}\}\\,T^\{\-1/6\}\\\!\+\\\!\\kappa^\{2\}\\\!\\\!\\left\(\\\!1\\\!\+\\\!\\frac\{2\}\{3\}\\log\\frac\{2\}\{\\delta\}\\\!\\right\)\\\!T^\{\-1/3\}\\\!\\right\)^\{\\\!\\\!1/2\}\\\!\\\!\\\!\\\!\\\!\\\!\\\!\+\\\!\\kappa T^\{\-1/6\}\\\!\\right\]\\\!\\\!\.Consequently, for fixed problem parameters,

1T​∑t=0T−1‖∇f​\(xt\)‖2≤ϵ⟹T=𝒪~​\(ϵ−2\)\.\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq\\epsilon\\qquad\\Longrightarrow\\qquad T=\\widetilde\{\\mathcal\{O\}\}\(\\epsilon^\{\-2\}\)\.

###### Proof\.

We define the predictable level\-set stopping timeτ:=min⁡\{t≤T:f⁡\(xt\)−f∗\>F∘\}∧T\\tau:=\\min\\\{t\\leq T:f\(x\_\{t\}\)\-f^\{\*\}\>F^\{\\circ\}\\\}\\wedge T, whereF∘:=2​Δ0F^\{\\circ\}:=2\\Delta\_\{0\}\. For allt<τt<\\tau, the trajectory remains in the generalized\-smoothness neighborhood, allowing us to apply the local descent inequality with local constantsG∘=G⁡\(F∘\)G^\{\\circ\}=G\(F^\{\\circ\}\),L∘=ℓ⁡\(2​G∘\)L^\{\\circ\}=\\ell\(2G^\{\\circ\}\), andV∘=\(G∘\)2\+σ2V^\{\\circ\}=\(G^\{\\circ\}\)^\{2\}\+\\sigma^\{2\}\.

Next, we invoke Lemma[17](https://arxiv.org/html/2609.30276#Thmlemma17)under the anchored choices of parameters induced byF∘F^\{\\circ\}\. Then, with probability at least1−δ/21\-\\delta/2, we obtain222The equation below holds when Lemma[15](https://arxiv.org/html/2609.30276#Thmlemma15)is applied with parameterδ/2\\delta/2\.:

f⁡\(xτ\)−f∗\+h2​∑t<τAt≤Δ0\+RT,δ/2N​L​\(F∘\)f\(x\_\{\\tau\}\)\-f^\{\*\}\+\\frac\{h\}\{2\}\\sum\_\{t<\\tau\}A\_\{t\}\\leq\\Delta\_\{0\}\+R\_\{T,\\delta/2\}^\{NL\}\(F^\{\\circ\}\)\(A\.7\)
where

RT,δ/2N​L​\(F∘\):=h​T​\(V∘\)2D¯​C2\+L2​h2​HT\+h​Γ∘​log⁡\(2/δ\)\+h​d​G∘​CD¯R\_\{T,\\delta/2\}^\{NL\}\(F^\{\\circ\}\):=\\frac\{hT\(V^\{\\circ\}\)^\{2\}\}\{\\underline\{D\}C^\{2\}\}\+\\frac\{L\}\{2\}h^\{2\}H\_\{T\}\+h\\Gamma^\{\\circ\}\\log\(2/\\delta\)\+h\\frac\{dG^\{\\circ\}C\}\{\\underline\{D\}\}\(A\.8\)\.

We now apply the calibrationyinit=C2y\_\{\\mathrm\{init\}\}=C^\{2\}andϵ0=C\\epsilon\_\{0\}=C, which ensuresD¯=2​C\\underline\{D\}=2C\. We seth=η/ΛT,δh=\\eta/\\sqrt\{\\Lambda\_\{T,\\delta\}\}andC=κ​T1/3C=\\kappa T^\{1/3\}\.

##### Step 1: Neighborhood condition\.

The neighborhood condition \([4](https://arxiv.org/html/2609.30276#S4.E4)\) is

h​CD¯≤G∘L∘\.\\frac\{hC\}\{\\underline\{D\}\}\\leq\\frac\{G\_\{\\circ\}\}\{L\_\{\\circ\}\}\.UsingD¯=2​C\\underline\{D\}=2Candh=η/ΛT,δh=\\eta/\\sqrt\{\\Lambda\_\{T,\\delta\}\}, the left\-hand side simplifies to

h​CD¯=12​ηΛT,δ≤η2\.\\frac\{hC\}\{\\underline\{D\}\}=\\frac\{1\}\{2\}\\,\\frac\{\\eta\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\leq\\frac\{\\eta\}\{2\}\.SinceΛT,δ≥1\\Lambda\_\{T,\\delta\}\\geq 1, the first bound in \([A\.6](https://arxiv.org/html/2609.30276#A1.E6)\) implies

η2≤G∘L∘,\\frac\{\\eta\}\{2\}\\leq\\frac\{G\_\{\\circ\}\}\{L\_\{\\circ\}\},and therefore \([4](https://arxiv.org/html/2609.30276#S4.E4)\) holds at the anchored levelF∘F\_\{\\circ\}\.

##### Step 2: Exact form ofRT,δ/2​\(F∘\)R\_\{T,\\delta/2\}\(F^\{\\circ\}\)\.

We now compute the four terms in

RT,δ/2​\(F∘\)=h​T​V∘2D¯​C2\+L∘2​h2​HT\+h​Γ∘​log⁡2δ\+h​d​G∘​CD¯,R\_\{T,\\delta/2\}\(F^\{\\circ\}\)=\\frac\{hTV\_\{\\circ\}^\{2\}\}\{\\underline\{D\}\\,C^\{2\}\}\+\\frac\{L\_\{\\circ\}\}\{2\}h^\{2\}H\_\{T\}\+h\\,\\Gamma^\{\\circ\}\\log\\frac\{2\}\{\\delta\}\+h\\frac\{dG^\{\\circ\}C\}\{\\underline\{D\}\},where

HT=d​log⁡\(1\+T​C2yinit\+ϵ0\)\+d​C2yinit\+ϵ0,Γ∘=2​V∘\+23​C​G∘D¯\.H\_\{T\}=d\\log\\\!\\Big\(1\+\\frac\{TC^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}\}\\Big\)\+d\\,\\frac\{C^\{2\}\}\{y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}\},\\qquad\\Gamma^\{\\circ\}=\\frac\{2V\_\{\\circ\}\+\\frac\{2\}\{3\}CG\_\{\\circ\}\}\{\\underline\{D\}\}\.
*First term\.*UsingD¯=2​C\\underline\{D\}=2C,

h​T​V∘2D¯​C2=h​T​V∘22​C3\.\\frac\{hTV\_\{\\circ\}^\{2\}\}\{\\underline\{D\}\\,C^\{2\}\}=\\frac\{hTV\_\{\\circ\}^\{2\}\}\{2C^\{3\}\}\.Now, from \([7](https://arxiv.org/html/2609.30276#S4.E7)\)

C3=κ3​T,h=ηΛT,δ,C^\{3\}=\\kappa^\{3\}T,\\qquad h=\\frac\{\\eta\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\},so the factorTTcancels and one gains an additionalΛT,δ−1/2\\Lambda\_\{T,\\delta\}^\{\-1/2\}improvement:

h​T​V∘22​C3=η​V∘22​κ3​ΛT,δ≤η​V∘22​κ3\.\\frac\{hTV\_\{\\circ\}^\{2\}\}\{2C^\{3\}\}=\\frac\{\\eta V\_\{\\circ\}^\{2\}\}\{2\\kappa^\{3\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\leq\\frac\{\\eta V\_\{\\circ\}^\{2\}\}\{2\\kappa^\{3\}\}\.Thus the bias term is uniformly bounded and is in fact smaller than before by the factorΛT,δ−1/2\\Lambda\_\{T,\\delta\}^\{\-1/2\}\.

*Second term\.*Lets0=yinit\+ϵ02s\_\{0\}=y\_\{\\mathrm\{init\}\}\+\\epsilon\_\{0\}^\{2\}, thens0=2​C2s\_\{0\}=2C^\{2\},

T​C2s0=T2,C2s0=12\.\\frac\{TC^\{2\}\}\{s\_\{0\}\}=\\frac\{T\}\{2\},\\qquad\\frac\{C^\{2\}\}\{s\_\{0\}\}=\\frac\{1\}\{2\}\.Therefore

HT=d​log⁡\(1\+T2\)\+d2\.H\_\{T\}=d\\log\\\!\\Big\(1\+\\frac\{T\}\{2\}\\Big\)\+\\frac\{d\}\{2\}\.Multiplying byh2=η2/ΛT,δh^\{2\}=\\eta^\{2\}/\\Lambda\_\{T,\\delta\}gives

L∘2​h2​HT=L∘​η22​ΛT,δ​\[d​log⁡\(1\+T2\)\+d2\]\.\\frac\{L\_\{\\circ\}\}\{2\}h^\{2\}H\_\{T\}=\\frac\{L\_\{\\circ\}\\eta^\{2\}\}\{2\\Lambda\_\{T,\\delta\}\}\\left\[d\\log\\\!\\Big\(1\+\\frac\{T\}\{2\}\\Big\)\+\\frac\{d\}\{2\}\\right\]\.Because

log⁡\(1\+T2\)≤log⁡\(1\+T\)and12≤1,\\log\\\!\\Big\(1\+\\frac\{T\}\{2\}\\Big\)\\leq\\log\(1\+T\)\\qquad\\text\{and\}\\qquad\\frac\{1\}\{2\}\\leq 1,we have

d​log⁡\(1\+T2\)\+d2≤d⁡\(log⁡\(1\+T\)\+1\)≤d​ΛT,δ\.d\\log\\\!\\Big\(1\+\\frac\{T\}\{2\}\\Big\)\+\\frac\{d\}\{2\}\\leq d\\bigl\(\\log\(1\+T\)\+1\\bigr\)\\leq d\\,\\Lambda\_\{T,\\delta\}\.Hence

L∘2​h2​HT≤L∘​d​η22\.\\frac\{L\_\{\\circ\}\}\{2\}h^\{2\}H\_\{T\}\\leq\\frac\{L\_\{\\circ\}d\\eta^\{2\}\}\{2\}\.
*Third term\.*We denoteλδ=log⁡2δ\\lambda\_\{\\delta\}=\\log\\frac\{2\}\{\\delta\}for simplicity\. SinceD¯=2​C\\underline\{D\}=2C, and ,

Γ∘=2​V∘\+23​C​G∘2​C=V∘C\+G∘3\.\\Gamma^\{\\circ\}=\\frac\{2V\_\{\\circ\}\+\\frac\{2\}\{3\}CG\_\{\\circ\}\}\{2C\}=\\frac\{V\_\{\\circ\}\}\{C\}\+\\frac\{G\_\{\\circ\}\}\{3\}\.Therefore

h​Γ∘​λδ=η​λδΛT,δ​\(V∘C\+G∘3\)\.h\\Gamma^\{\\circ\}\\lambda\_\{\\delta\}=\\frac\{\\eta\\lambda\_\{\\delta\}\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\left\(\\frac\{V\_\{\\circ\}\}\{C\}\+\\frac\{G\_\{\\circ\}\}\{3\}\\right\)\.We bound the two pieces separately\. For theV∘/CV\_\{\\circ\}/Cpiece, the calibration gives

1C=1κ​T1/3,\\frac\{1\}\{C\}=\\frac\{1\}\{\\kappa T^\{1/3\}\},so

η​λδΛT,δ⋅V∘C=η​V∘​λδκ​T1/3​ΛT,δ\.\\frac\{\\eta\\lambda\_\{\\delta\}\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\cdot\\frac\{V\_\{\\circ\}\}\{C\}=\\frac\{\\eta V\_\{\\circ\}\\lambda\_\{\\delta\}\}\{\\kappa T^\{1/3\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\.NowT≥1T\\geq 1impliesT−1/3≤1T^\{\-1/3\}\\leq 1, andλδ≤ΛT,δ\\lambda\_\{\\delta\}\\leq\\sqrt\{\\Lambda\_\{T,\\delta\}\}by definition ofΛT,δ\\Lambda\_\{T,\\delta\}\. Therefore

λδT1/3​ΛT,δ≤1,\\frac\{\\lambda\_\{\\delta\}\}\{T^\{1/3\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\leq 1,and hence

η​λδΛT,δ⋅V∘C≤η​V∘κ\.\\frac\{\\eta\\lambda\_\{\\delta\}\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\cdot\\frac\{V\_\{\\circ\}\}\{C\}\\leq\\frac\{\\eta V\_\{\\circ\}\}\{\\kappa\}\.For theG∘/3G\_\{\\circ\}/3piece, again usingλδ≤ΛT,δ\\lambda\_\{\\delta\}\\leq\\sqrt\{\\Lambda\_\{T,\\delta\}\},

η​λδΛT,δ⋅G∘3≤η​G∘3\.\\frac\{\\eta\\lambda\_\{\\delta\}\}\{\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\cdot\\frac\{G\_\{\\circ\}\}\{3\}\\leq\\frac\{\\eta G\_\{\\circ\}\}\{3\}\.Combining the two estimates yields

h​Γ∘​λδ≤η​V∘κ\+η​G∘3\.h\\Gamma^\{\\circ\}\\lambda\_\{\\delta\}\\leq\\frac\{\\eta V\_\{\\circ\}\}\{\\kappa\}\+\\frac\{\\eta G\_\{\\circ\}\}\{3\}\.
*Third term\.*BecauseD¯=2​C\\underline\{D\}=2C,

h​d​G∘​CD¯=h​d​G∘2=η​d​G∘2​ΛT,δ≤η​d​G∘2,h\\,\\frac\{dG\_\{\\circ\}C\}\{\\underline\{D\}\}=\\frac\{hdG\_\{\\circ\}\}\{2\}=\\frac\{\\eta dG\_\{\\circ\}\}\{2\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\\leq\\frac\{\\eta dG\_\{\\circ\}\}\{2\},where we again usedΛT,δ≥1\\Lambda\_\{T,\\delta\}\\geq 1\.

##### Step 3: Global bound onRT,δ/2​\(F∘\)R\_\{T,\\delta/2\}\(F^\{\\circ\}\)\.

Summing the four pieces established above gives

RT,δ/2​\(F∘\)≤η​V∘22​κ3\+L∘​d​η22\+η​V∘κ\+η​G∘3\+η​d​G∘2\.R\_\{T,\\delta/2\}\(F^\{\\circ\}\)\\leq\\frac\{\\eta V\_\{\\circ\}^\{2\}\}\{2\\kappa^\{3\}\}\+\\frac\{L\_\{\\circ\}d\\eta^\{2\}\}\{2\}\+\\frac\{\\eta V\_\{\\circ\}\}\{\\kappa\}\+\\frac\{\\eta G\_\{\\circ\}\}\{3\}\+\\frac\{\\eta dG\_\{\\circ\}\}\{2\}\.Now each term is controlled by one of the explicit bounds in \([A\.6](https://arxiv.org/html/2609.30276#A1.E6)\):

η​V∘22​κ3≤Δ08,L∘​d​η22≤Δ08,η​V∘κ≤Δ08,η​G∘3≤Δ08,η​d​G∘2≤Δ02\.\\frac\{\\eta V\_\{\\circ\}^\{2\}\}\{2\\kappa^\{3\}\}\\leq\\frac\{\\Delta\_\{0\}\}\{8\},\\qquad\\frac\{L\_\{\\circ\}d\\eta^\{2\}\}\{2\}\\leq\\frac\{\\Delta\_\{0\}\}\{8\},\\qquad\\frac\{\\eta V\_\{\\circ\}\}\{\\kappa\}\\leq\\frac\{\\Delta\_\{0\}\}\{8\},\\qquad\\frac\{\\eta G\_\{\\circ\}\}\{3\}\\leq\\frac\{\\Delta\_\{0\}\}\{8\},\\qquad\\frac\{\\eta dG\_\{\\circ\}\}\{2\}\\leq\\frac\{\\Delta\_\{0\}\}\{2\}\.Summing these upper bounds yeilds

RT,δ/2​\(F∘\)≤Δ0\.R\_\{T,\\delta/2\}\(F^\{\\circ\}\)\\leq\\Delta\_\{0\}\.Recalling thatF∘=2​Δ0F\_\{\\circ\}=2\\Delta\_\{0\}, we conclude that

F∘=2​Δ0≥Δ0\+RT,δ/2​\(F∘\),F\_\{\\circ\}=2\\Delta\_\{0\}\\geq\\Delta\_\{0\}\+R\_\{T,\\delta/2\}\(F\_\{\\circ\}\),
Consequently, \([A\.7](https://arxiv.org/html/2609.30276#A1.E7)\) simplifies tof⁡\(xτ\)−f∗≤2​Δ0=F∘f\(x\_\{\\tau\}\)\-f^\{\*\}\\leq 2\\Delta\_\{0\}=F^\{\\circ\}\. By definition of the stopping time, this strictly rules outτ<T\\tau<T, proving thatτ=T\\tau=T\(the trajectory never exits the level set\) and yielding:

1T​∑t=0T−1At≤2​F∘h​T=4​Δ0h​T\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}A\_\{t\}\\leq\\frac\{2F^\{\\circ\}\}\{hT\}=\\frac\{4\\Delta\_\{0\}\}\{hT\}\(A\.9\)with probability1−δ/21\-\\delta/2\.

##### Step 4: Euclidean Conversion and Final Complexity\.

To convert the preconditioned boundAtA\_\{t\}into an unconditioned Euclidean bound, we must formalize the intersection of two high\-probability events\.

First, letℰp​r​e\\mathcal\{E\}\_\{pre\}denote the event that our preconditioned descent bound from Step 4 holds, i\.e \([A\.9](https://arxiv.org/html/2609.30276#A1.E9)\)\. Specifically,

ℰp​r​e:=\{τ=Tand1T∑t=0T−1At≤4​Δ0h​T\}\.\\mathcal\{E\}\_\{pre\}:=\\left\\\{\\tau=T\\ \\text\{ and \}\\ \\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}A\_\{t\}\\leq\\frac\{4\\Delta\_\{0\}\}\{hT\}\\right\\\}\.Because this bound relies on the Bernstein Freedman supermartingale inequality applied with a confidence parameter ofδ/2\\delta/2333This holds when Lemma[15](https://arxiv.org/html/2609.30276#Thmlemma15)is applied with parameterδ/2\\delta/2\., we haveℙ⁡\(ℰp​r​e\)≥1−δ/2\\mathbb\{P\}\(\\mathcal\{E\}\_\{pre\}\)\\geq 1\-\\delta/2\. On this event,τ=T\\tau=Tand1T​∑t=0T−1At≤4​Δ0h​T\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}A\_\{t\}\\leq\\frac\{4\\Delta\_\{0\}\}\{hT\}\.

Second, letℰd​e​n\\mathcal\{E\}\_\{den\}denote the denominator concentration event, i\.eℰd​e​n:=\{Y~T≤BT,δ/2\}\\mathcal\{E\}\_\{den\}:=\\\{\\widetilde\{Y\}\_\{T\}\\leq B\_\{T,\\delta/2\}\\\}\. By Lemma[16](https://arxiv.org/html/2609.30276#Thmlemma16), applied to the stopped clipped\-gradient energyY~T\\tilde\{Y\}\_\{T\}with a confidence parameter ofδ/2\\delta/2, the total energy is bounded by:

BT,δ/2:=T​V∘\+2​T​C2​V∘​log⁡\(2/δ\)\+2​C23​log⁡\(2/δ\)B\_\{T,\\delta/2\}:=TV^\{\\circ\}\+\\sqrt\{2TC^\{2\}V^\{\\circ\}\\log\(2/\\delta\)\}\+\\frac\{2C^\{2\}\}\{3\}\\log\(2/\\delta\)This event also holds with probabilityℙ⁡\(ℰd​e​n\)≥1−δ/2\\mathbb\{P\}\(\\mathcal\{E\}\_\{den\}\)\\geq 1\-\\delta/2\.

To ensure both bounds hold simultaneously, we apply the union bound\. The probability that either event fails is at mostδ/2\+δ/2=δ\\delta/2\+\\delta/2=\\delta\. Therefore, the probability that both events hold is:

ℙ⁡\(ℰp​r​e∩ℰd​e​n\)≥1−δ\\mathbb\{P\}\(\\mathcal\{E\}\_\{pre\}\\cap\\mathcal\{E\}\_\{den\}\)\\geq 1\-\\deltaWe proceed on this intersection\. Onℰd​e​n\\mathcal\{E\}\_\{den\}, the maximum denominator norm is deterministically bounded for allt≤Tt\\leq T:

‖Dt‖≤D¯δ:=yinit\+BT,δ/2\+ϵ0\\\|D\_\{t\}\\\|\\leq\\overline\{D\}\_\{\\delta\}:=\\sqrt\{y\_\{\\mathrm\{init\}\}\+B\_\{T,\\delta/2\}\}\+\\epsilon\_\{0\}Because the diagonal metric satisfiesDt≤D¯δ​ID\_\{t\}\\leq\\overline\{D\}\_\{\\delta\}I, its inverse satisfiesDt−1≥D¯δ−1​ID\_\{t\}^\{\-1\}\\geq\\overline\{D\}\_\{\\delta\}^\{\-1\}I\. This allows us to lower\-bound the preconditioned gradient progress:

At=⟨∇f\(xt\),Dt−1∇f\(xt\)⟩≥D¯δ−1∥∇f\(xt\)∥2A\_\{t\}=\\langle\\nabla f\(x\_\{t\}\),D\_\{t\}^\{\-1\}\\nabla f\(x\_\{t\}\)\\rangle\\geq\\overline\{D\}\_\{\\delta\}^\{\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}Averaging this inequality over the horizonTTand applying the bound fromℰp​r​e\\mathcal\{E\}\_\{pre\}yields:

1T​∑t=0T−1‖∇f​\(xt\)‖2≤D¯δ​\(1T​∑t=0T−1At\)≤D¯δ​4​Δ0h​T\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}\\\|\\nabla f\(x\_\{t\}\)\\\|^\{2\}\\leq\\overline\{D\}\_\{\\delta\}\\left\(\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}A\_\{t\}\\right\)\\leq\\overline\{D\}\_\{\\delta\}\\frac\{4\\Delta\_\{0\}\}\{hT\}To isolate the explicit dependence on the horizonTT, we expandD¯δ\\overline\{D\}\_\{\\delta\}using our parameter calibrationsyinit=C2y\_\{\\mathrm\{init\}\}=C^\{2\},ϵ0=C\\epsilon\_\{0\}=C, andC=κ​T1/3C=\\kappa T^\{1/3\}:

D¯δ=C2\+T​V∘\+2​T​C2​V∘​log⁡\(2/δ\)\+2​C23​log⁡\(2/δ\)\+C\\overline\{D\}\_\{\\delta\}=\\sqrt\{C^\{2\}\+TV^\{\\circ\}\+\\sqrt\{2TC^\{2\}V^\{\\circ\}\\log\(2/\\delta\)\}\+\\frac\{2C^\{2\}\}\{3\}\\log\(2/\\delta\)\}\+CWe factor outT\\sqrt\{T\}from both terms\. Noting thatC2/T=κ2T−1/3C^\{2\}/T=\\kappa^\{2\}T^\{\-1/3\}andC/T=κT−1/6C/\\sqrt\{T\}=\\kappa T^\{\-1/6\}, we obtain:

D¯δ≤T\[\(V∘\+κ2​V∘​log⁡\(2/δ\)T−1/6\+κ2\(1\+23log\(2/δ\)\)T−1/3\)1/2\+κT−1/6\]\\overline\{D\}\_\{\\delta\}\\leq\\sqrt\{T\}\\left\[\\left\(V^\{\\circ\}\+\\kappa\\sqrt\{2V^\{\\circ\}\\log\(2/\\delta\)\}T^\{\-1/6\}\+\\kappa^\{2\}\\left\(1\+\\frac\{2\}\{3\}\\log\(2/\\delta\)\\right\)T^\{\-1/3\}\\right\)^\{1/2\}\+\\kappa T^\{\-1/6\}\\right\]Finally, we substitute this expandedD¯δ\\overline\{D\}\_\{\\delta\}and the calibrated step sizeh=η/ΛT,δh=\\eta/\\sqrt\{\\Lambda\_\{T,\\delta\}\}back into the Euclidean bound\. TheT\\sqrt\{T\}from the denominator bound and the1/T1/Tfrom the averaging cleanly collapse:

D¯δ​4​Δ0h​T=T​\[…\]⋅4​Δ0​ΛT,δη​T=4​Δ0​ΛT,δη​T​\[…\]\\overline\{D\}\_\{\\delta\}\\frac\{4\\Delta\_\{0\}\}\{hT\}=\\sqrt\{T\}\[\\dots\]\\cdot\\frac\{4\\Delta\_\{0\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\{\\eta T\}=\\frac\{4\\Delta\_\{0\}\\sqrt\{\\Lambda\_\{T,\\delta\}\}\}\{\\eta\\sqrt\{T\}\}\[\\dots\]This simplifies exactly to the finite\-horizon theorem guarantee\. Because the bracketed term limits toV∘\\sqrt\{V^\{\\circ\}\}asT→∞T\\to\\inftyandΛT,δ\\Lambda\_\{T,\\delta\}contributes only polylogarithmic factors, this directly validates the𝒪~\(T−1/2\)\\tilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)convergence rate\.

The actual rate is:

𝒪⁡\(d⁡\(log⁡T\+log⁡\(1/δ\)\)T\)\\mathcal\{O\}\\left\(\\frac\{d\\big\(\\sqrt\{\\log T\}\+\\log\(1/\\delta\)\\big\)\}\{\\sqrt\{T\}\}\\right\)\.

#### A\.3\.1Discussion on specific choice ofF∘=2​Δ0F^\{\\circ\}=2\\Delta\_\{0\}

While Theorem[1](https://arxiv.org/html/2609.30276#Thmtheorem1)explicitly anchors the analysis at the levelF∘=2​Δ0F^\{\\circ\}=2\\Delta\_\{0\}, this choice is an analytic convenience rather than an algorithmic limitation\. The𝒪~\(T−1/2\)\\tilde\{\\mathcal\{O\}\}\(T^\{\-1/2\}\)Euclidean stationarity guarantee natively extends to any arbitrary target levelF\>Δ0F\>\\Delta\_\{0\}\. For any such choice, the induced local generalized\-smoothness constantsG⁡\(F\)G\(F\)andL⁡\(F\)L\(F\)remain finite and fixed, yielding a strictly positive feasibility slackF−Δ0\>0F\-\\Delta\_\{0\}\>0\. Because the cumulative algorithmic and stochastic penalties, specifically the clipping\-residual bias, the deterministic same\-step correction, the martingale fluctuation, and the smoothness remainder, scale proportionately with the hyperparameters, there always exists a sufficiently small step\-size parameterη\\etacapable of compressing the total error budget entirely within this available slack\.We specifically highlightF∘=2​Δ0F^\{\\circ\}=2\\Delta\_\{0\}because it constructs an optimal, symmetric1:11:1feasibility partition: it dedicates exactlyΔ0\\Delta\_\{0\}to the initial suboptimality and leaves an equal maximum allowance ofΔ0\\Delta\_\{0\}for the noise budget\. To understand why this balance is critical, consider the mechanical tradeoff in the final Euclidean guarantee\. Selecting a substantially larger target level \(e\.g\.,F≫Δ0F\\gg\\Delta\_\{0\}\) artificially widens the error budget, which permissibly allows for a larger step\-size parameterη\\eta\. Sinceη\\etadictates the denominator of the final complexity bound, increasing it nominally improves the theoretical convergence rate\. However, under generalized smoothness, the localized gradient boundG⁡\(F\)G\(F\)and smoothness parameterL⁡\(F\)L\(F\)grow monotonically, and potentially rapidly, with the level\-set thresholdFF\. Because these geometric constants dictate the numerator of the final bound \(acting through the variance factorV⁡\(F\)V\(F\)and the denominator boundD¯δ\\overline\{D\}\_\{\\delta\}\), a largerFFcauses the numerator to inflate significantly faster than the step size improves\. Consequently, an overly largeFFseverely degrades the leading constants hidden within the asymptotic rate, rendering the theoretical upper bound loose and uninformative\. Thus, anchoring at2​Δ02\\Delta\_\{0\}serves as an elegant structural optimal: it provides exactly enough slack to ensure feasibility without unnecessarily deteriorating the problem’s local geometry\.

Conversely, while selecting a tighter target levelΔ0<F<2​Δ0\\Delta\_\{0\}<F<2\\Delta\_\{0\}would marginally improve the local curvature constants, it would severely shrink the available feasibility slack\. This would force a proportionally microscopic step sizeη\\eta, unnecessarily inflating the iteration complexity\.

∎