Source-linked AI summary
Last-Iterate Convergence Rate of Normalized Gradient Descent under H\"older Smoothness
Yuki Takezawa, Eduard Gorbunov
TL;DR
Most analyses of normalized gradient descent bound the best or a weighted-average iterate, although practical implementations typically return the last iterate. The paper analyzes last-iterate convergence for convex Hölder-smooth objectives, using theoretical guarantees and PEP numerical evidence. Constant stepsizes incur a logarithmic overhead, while linear decay removes it and matches the best-iterate and weighted-average guarantees without knowledge of the Hölder parameters.
Problem
Existing normalized-gradient analyses mostly bound the best or a weighted-average iterate, while practical implementations typically return the last iterate.
Source: §1 · pp. 1–2Method
The paper analyzes last-iterate convergence for convex Hölder-smooth objectives, uses PEP to examine constant-step behavior in the smooth case, and studies a linearly decreasing stepsize.
Source: §1 · p. 2, §4.2 · p. 7, §5 · p. 8Results
Takeaways & Limitations
Linear decay gives a last-iterate guarantee matching best-iterate and weighted-average guarantees without requiring knowledge of ν or Mν.
Source: §6 · p. 9The PEP experiments cover only a limited range of T and a hand-picked gradient-norm family, so they neither identify the exact worst-case rate nor prove a logarithmic overhead for ν > 0.
Source: §4.2 · p. 8
Abstract
from arXiv · showhide
Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practical implementations typically return the last iterate. In this paper, we study the last-iterate convergence of normalized gradient descent for convex, $(\nu,M_\nu)$-H\"older-smooth objectives. For a constant stepsize, we establish an upper bound of $\mathcal{O}\bigl((\log^2(T)/T)^{(1+\nu)/2}\bigr)$, which contains a logarithmic overhead relative to the known $\mathcal{O}\bigl(T^{-(1+\nu)/2}\bigr)$ guarantees for the best and weighted-average iterates. For $\nu = 0$, this overhead is known to be unavoidable. We complement this analysis with numerical results based on the performance estimation problem (PEP), investigating the finite-horizon worst-case behavior in the smooth setting and whether the logarithmic overhead reflects an intrinsic limitation of constant-step normalized gradient descent. We then show that a linearly decreasing stepsize yields a last-iterate guarantee of $\mathcal{O}\bigl(T^{-(1+\nu)/2}\bigr)$, matching the order of the best-iterate/weighted-average guarantees without requiring knowledge of $\nu$ and $M_\nu$.
1 INTRODUCTION
The paper addresses the mismatch between analyses of best or averaged iterates and practical use of the last iterate. It establishes last-iterate guarantees for normalized gradient descent with constant and linearly decreasing stepsizes, and uses PEP to examine the smooth case.
1 INTRODUCTION
- The last-iterate question matters because practical implementations typically return the last iterate, while prior analyses usually bound the best iterate or a weighted average.Normalized gradient descent is also closely related to modern optimizers, including Adam and Muon.Source: §1 · p. 1
Last-iterate rate with a constant stepsize
- A constant stepsize gives a last-iterate rate with a logarithmic overhead over the known best-iterate and weighted-average rates.For ν = 0, the result is tight; PEP evidence indicates that in the smooth case the last iterate is slower than O(1/T).Source: §1 · p. 2
Numerical evidence via PEP
- PEP results indicate that with a constant stepsize, the smooth-case last iterate is slower than O(1/T), suggesting the overhead is not an artifact of the analysis.The numerical evidence examines the smooth case, ν = 1.Source: §1 · p. 2
Removing the overhead with a decreasing stepsize
- A linearly decreasing stepsize removes the logarithmic overhead and matches the best-iterate and weighted-average guarantees.The stepsize does not require knowledge of ν or Mν.Source: §1 · p. 2
2 RELATED WORK
Prior analyses of normalized gradient descent primarily bound the best or averaged iterate, while implementations typically return the last iterate. The paper situates its results among work on last-iterate guarantees and decaying stepsizes, and extends beyond the bounded-subgradient setting of the earlier normalized-gradient analysis.
Convergence Analysis of Normalized Gradient Descent
- Most normalized-gradient analyses study the best iterate, whereas Orabona (2023) analyzes a weighted average; practical implementations typically return the last iterate, and Zamani & Glineur (2025) is the only prior last-iterate work.Source: §2 · pp. 2–3
- Zamani & Glineur (2025) give a last-iterate guarantee for normalized gradient descent only for convex functions with bounded subgradients, excluding smooth objectives such as quadratics with unbounded gradients.Their linearly decreasing schedule improves the last-iterate rate to O(1/T).Source: §2 · p. 3
Last-Iterate Convergence of Optimization Methods
- Across optimization methods, last iterates can converge more slowly than best or averaged iterates, often by a logarithmic factor, while suitably decaying schedules can close the gap.Defazio et al. (2024a) provide a framework converting online-learning regret bounds into last-iterate guarantees, but it does not directly apply here because the regret bound concerns normalized gradients and gradient norms need not be bounded away from zero.Source: §2 · p. 3
- The paper studies the convex, deterministic setting, where the gap between last-iterate practice and best- or averaged-iterate analyses motivates direct last-iterate guarantees.The related-work discussion notes last-iterate analyses for stochastic gradient, subgradient, shuffling, momentum, and AdaGrad-Norm methods.Source: §2 · p. 3
3 PRELIMINARIES
The paper studies unconstrained minimization of a convex Hölder-smooth objective with a minimizer, using normalized gradient descent whose step length is set independently of gradient magnitude. Existing guarantees cover the best iterate and a weighted average, but not the practically returned last iterate across the full Hölder family.
3 PRELIMINARIES
- The setting is unconstrained minimization of an objective assumed to have a minimizer, and the analysis assumes convexity and Hölder smoothness.The smoothness parameter ν ranges from 0 to 1.Source: §3 · p. 3
- The normalized stepsize ˜η_t sets each step's length independently of gradient magnitude, while η_t is the effective stepsize applied to the gradient.If a gradient is zero, convexity makes the current point a minimizer, so the analysis assumes nonzero gradients without loss of generality.Source: §3 · p. 3
- At ν = 1, Hölder smoothness is standard smoothness and allows unbounded gradient norms; at ν = 0, it is essentially bounded-gradient smoothness and includes the normalized subgradient setting.For ν = 0, the results apply to normalized subgradient methods for nonsmooth convex functions.Source: §3 · pp. 3–4
3.1 EXISTING ANALYSIS OF NORMALIZED GRADIENT DESCENT
- Existing guarantees bound either the best iterate or a weighted average, whereas practical normalized gradient descent returns the last iterate.Before this work, the only known last-iterate guarantee for normalized gradient descent was restricted to ν = 0; the paper proceeds to analyze the full range ν ∈ [0, 1].Source: §3.1 · p. 4
4 NORMALIZED GRADIENT DESCENT WITH A CONSTANT STEPSIZE
With a constant stepsize, normalized gradient descent has a last-iterate guarantee for convex Hölder-smooth objectives, but its bound carries a logarithmic overhead over best-iterate and weighted-average guarantees. The proof sketch traces this overhead to a harmonic sum, while PEP experiments find slower-than-1/T decay in the smooth case without establishing the exact worst-case rate.
4 NORMALIZED GRADIENT DESCENT WITH A CONSTANT STEPSIZE
- The last-iterate bound extends the bounded-gradient result to convex Hölder-smooth objectives, but is worse than best-iterate and weighted-average guarantees by a factor of (1 + log(T))^(1+ν).For ν = 0, the overhead matches a lower bound and cannot be removed in general; for ν > 0, no such lower bound is known.Source: §4 · pp. 4–5
- In the smooth case, numerical results indicate that normalized gradient descent misses the O(1/T) last-iterate rate of gradient descent, despite matching its best-iterate order.The comparison concerns last-iterate behavior; normalization does not affect the best-iterate rate stated here.Source: §4 · p. 5
4.1 PROOF SKETCH
- A harmonic sum near the final iterations produces the additional logarithmic factor in the induction argument.The proof compares each iterate with a reference point formed as a convex combination of the optimum and previous iterates.Source: §4.1 · pp. 5, 7
4.2 NUMERICAL EVALUATION
- Across the tested horizons and three prescribed gradient-norm sequences, PEP finds worst-case decay slower than 1/T but faster than the theorem’s O(log^2(T)/T) bound.The experiments cover a limited horizon range and hand-picked gradient norms, so they neither identify the exact worst-case rate nor prove a logarithmic overhead.Source: §4.2 · p. 8, Figure 1 · p. 8
5 NORMALIZED GRADIENT DESCENT WITH A LINEARLY DECREASING STEPSIZE
A linearly decreasing stepsize removes the logarithmic overhead in the last-iterate guarantee for normalized gradient descent. The proof sketch attributes this to having suitably good iterates in progressively denser blocks near the end of the run.
5 NORMALIZED GRADIENT DESCENT WITH A LINEARLY DECREASING STEPSIZE
- The linearly decreasing stepsize yields the same last-iterate rate order as best-iterate and weighted-average guarantees across the Hölder family, without requiring ν or Mν.For ν = 0, this recovers the bounded-subgradient result up to absolute constants; the guarantee extends to ν ∈ [0, 1].Source: §5 · p. 9
5.1 PROOF SKETCH
- The analysis finds an iterate attaining the best-iterate rate in every geometrically shrinking block, with blocks denser near the run’s end, which avoids the harmonic-sum overhead.The final at most √T iterations are outside the blocks, but their total contribution is negligible.Source: §5.1 · p. 9
6 CONCLUSION
The conclusion compares constant and linearly decreasing stepsizes for last-iterate convergence. The constant-step logarithmic overhead is unavoidable for ν = 0, while the decreasing schedule removes that factor without requiring the Hölder parameters.
6 CONCLUSION
- A linearly decreasing stepsize removes the logarithmic factor from the last-iterate rate.The guarantee does not require knowledge of the Hölder parameters.Source: §6 · p. 9
- With a constant stepsize, the last-iterate rate is slower than known best-iterate and weighted-average rates by a logarithmic factor.The conclusion states that this factor is unavoidable for ν = 0.Source: §6 · p. 9
- PEP-based numerical results indicate that, in the smooth case, the last iterate is slower than O(1/T).The conclusion presents this as numerical evidence.Source: §6 · p. 9
AI USE STATEMENT
The authors report using generative AI for language editing and proofreading, but not for the main research ideas, theoretical derivations, or experimental code.
AI USE STATEMENT
- Generative AI tools were used for manuscript language editing and proofreading.The stated uses included improving grammar, clarity, and readability.Source: AI USE STATEMENT · p. 10
- The authors state that generative AI was not used to develop the main research ideas, derive theoretical results, or write experimental code.Source: AI USE STATEMENT · p. 10
- The authors reviewed AI-assisted work and accept responsibility for the final content.Source: AI USE STATEMENT · p. 10
A IMPORTANCE OF CONVERGENCE ANALYSIS IN THE CONVEX SETTING
The paper motivates convex-setting analysis as a way to avoid overly pessimistic worst-case guarantees under arbitrary non-convexity and to study behavior that may extend beyond convex problems.
A IMPORTANCE OF CONVERGENCE ANALYSIS IN THE CONVEX SETTING
- The authors argue that allowing arbitrary non-convex functions can make worst-case guarantees too conservative to reflect practical behavior.They note that non-convex smooth gradient descent has an optimal first-order rate for finding approximate stationary points.Source: A IMPORTANCE OF CONVERGENCE ANALYSIS… · p. 13
- Recent works report that predictions from convex optimization theory match neural-network training behavior, including learning-rate schedules.Source: A IMPORTANCE OF CONVERGENCE ANALYSIS… · p. 13
- The authors believe their convex-setting analysis of normalized gradient descent may inform its empirical effectiveness in broader non-convex problems.Source: A IMPORTANCE OF CONVERGENCE ANALYSIS… · p. 13
B USEFUL LEMMAS
The appendix states several lemmas under its assumptions and uses monotonicity, convexity, and inequality bounds in the proofs.
B USEFUL LEMMAS
- Lemma 5 gives a bound for nonnegative x, a, and b with ν in [0, 1], derived using Young’s inequality.The proof concludes x ≤ a^(1+ν) + 2b.Source: B USEFUL LEMMAS · p. 13
- Lemma 1 considers normalized gradient descent for a positive, nondecreasing sequence v_0 through v_T.The supplied statement does not include the resulting bound.Source: B USEFUL LEMMAS · p. 13
- A proof step combines inequalities over iterations by multiplying by 2η_t v_t, summing, and exchanging summation order.It also uses z_0 = x⋆ and nonnegativity of the squared norm.Source: B USEFUL LEMMAS · p. 14
C PROOF OF THEOREM 1
Theorem 1 is proved by induction on the iterate, using intermediate bounds to establish the claim at the final iteration. Substituting the chosen constant stepsize gives the theorem with an unoptimized absolute constant.
C PROOF OF THEOREM 1
- The proof establishes the induction base case and assumes the bound through T−1 before proving it at T.The induction hypothesis applies when the stepsize satisfies the stated distance-dependent condition.Source: C PROOF OF THEOREM 1 · p. 14
- In the induction step, the proof bounds v0 by dropping the s = T term, applies the induction hypothesis for every s ≤ T − 1, and uses Lemma 4 in the ensuing inequalities.Source: C PROOF OF THEOREM 1 · pp. 15–16
- Substituting the chosen stepsize and t = T proves Theorem 1 with absolute constant 1400, which the authors do not optimize.Source: C PROOF OF THEOREM 1 · p. 17
D PROOF OF THEOREM 2
Theorem 2 uses a linearly decreasing stepsize and bounds the last iterate by organizing the proof around consecutive index blocks. The proof treats short horizons separately and states that its absolute constant is unoptimized.
D PROOF OF THEOREM 2
- The proof uses the linearly decreasing stepsize ˜η_t = (1 − t/(T + 1))∥x_1−x⋆∥/√T.The notation passage specifies this schedule for the section.Source: D PROOF OF THEOREM 2 · pp. 17, 21
- For T ≥ 16, the proof partitions consecutive iterations into blocks I_0,…,I_J and bounds selected indices within them.The blocks cover consecutive intervals, with the final block ending no later than T−2.Source: D PROOF OF THEOREM 2 · pp. 17–19
- Within the block argument, the proof selects an index minimizing the objective on an interval and uses normalized-gradient updates to compare objective values.Lemma 7 uses this selection and sums the update identity over the interval.Source: D PROOF OF THEOREM 2 · p. 18
- The proof handles T < 16 separately and states that the absolute constant in the all-horizon result is not optimized.Source: D PROOF OF THEOREM 2 · p. 21