Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness

Yuki Takezawa; Eduard Gorbunov

math.OCOct 5, 2026

Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness

Authors: Yuki Takezawa, Eduard Gorbunov

Organizations: Toyota Motor Corporation · MBZUAI

Abstract

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, $(ν,M_ν)$ -Hölder-smooth objectives. For a constant stepsize, we establish an upper bound of $\mathcal{O}\bigl((\log^2(T)/T)^{(1+ν)/2}\bigr)$ , which contains a logarithmic overhead relative to the known $\mathcal{O}\bigl(T^{-(1+ν)/2}\bigr)$ guarantees for the best and weighted-average iterates. For $ν= 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+ν)/2}\bigr)$ , matching the order of the best-iterate/weighted-average guarantees without requiring knowledge of $ν$ and $M_ν$ .

Figures & tables

	Reference	Convergence Criteria	$\nu$	Stepsize	Rate
constant stepsize	Grimmer (2019)	$\min_{t}f({\bm{x}}_{t})-f({\bm{x}}^{\star})$	$\nu\in[0,1]$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}$	$M_{\nu}\left(\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\right)^{1+\nu}$
	Orabona (2023)	$f\left(\tfrac{1}{\sum_{t=1}^{T}\frac{1}{\\|\nabla f({\bm{x}}_{t})\\|}}\sum_{t=1}^{T}\tfrac{{\bm{x}}_{t}}{\\|\nabla f({\bm{x}}_{t})\\|}\right)-f({\bm{x}}^{\star})$	$\nu\in[0,1]$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}$	$M_{\nu}\left(\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\right)^{1+\nu}$
	Zamani and Glineur (2025)	$f({\bm{x}}_{T})-f({\bm{x}}^{\star})$	$\nu=0$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}$	$\tfrac{M_{\nu}\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}(1+\log(T))$
	Theorem 1 (new)	$f({\bm{x}}_{T})-f({\bm{x}}^{\star})$	$\nu\in[0,1]$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}$	$M_{\nu}\left(\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\right)^{1+\nu}(1+\log(T))^{1+\nu}$
linearly decreasing stepsize	Zamani and Glineur (2025)	$f({\bm{x}}_{T})-f({\bm{x}}^{\star})$	$\nu=0$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\left(1-\tfrac{t}{T}\right)$	$\tfrac{M_{\nu}\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}$
	Theorem 2 (new)	$f({\bm{x}}_{T})-f({\bm{x}}^{\star})$	$\nu\in[0,1]$	$\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\left(1-\tfrac{t}{T+1}\right)$	$M_{\nu}\left(\tfrac{\\|{\bm{x}}_{1}-{\bm{x}}^{\star}\\|}{\sqrt{T}}\right)^{1+\nu}$

Table 1: Summary of the convergence rates for normalized gradient descent assuming that

f

is convex and

(\nu,M_{\nu})

-Hölder smooth. Numerical constants are omitted in the rates.

Figure 1: Optimal value of Eq. 13 , i.e., the worst-case

f({\bm{x}}_{T})-f({\bm{x}}^{\star})

over convex

1

-smooth functions with

\|{\bm{x}}_{1}-{\bm{x}}^{\star}\|=1

and prescribed gradient norms

g_{t}=c/\sqrt{T}

, as a function of

T

(log–log scale) for

c=0.1

(left),

c=0.06

(middle), and

c=0.02

(right). The dotted and dash-dotted lines show the reference decays

1/T

and

(1+\log T)^{2}/T

up to constant factors. In all three cases, the observed decay is slower than

1/T

Explore similar work

A lower bound for stepsize-based acceleration of gradient descent
Aug 11, 2026Jianhao Ma, Yuxin ChenStep Accuracy Gradient Descent
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity
Jul 24, 2026Arzu Ahmadova, Ismail HuseynovGradient Descent Descent
Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · Physikalisch-Technische Bundesanstalt (PTB), Germany · Technical University of Berlin, Germany
Silver Rate Is (Almost) Optimal for Gradient Descent
Date pendingYuhan Ye, Kaizhao LiuStep Accuracy Gradient Descent
MIT

Aug 11, 2026, math.OCJ/K move · Enter open · S save

A lower bound for stepsize-based acceleration of gradient descent

Jianhao Ma, Yuxin Chen

Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania

Step Accuracy Gradient Descent Convergence Lower Bounds Zeroth-Order

Open paper AskPDF arXiv

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of

O(T^{-1})

(where

T

denotes the number of iterations) to

O\big(T^{-\log_2(1+\sqrt{2})}\big)

using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical

Ω(T^{-2})

benchmark for general first-order methods. In this work, we present a new lower bound of

Ω(T^{-1.9319})

for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal

O(T^{-2})

convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.

Abstract

Explore similar work

A lower bound for stepsize-based acceleration of gradient descent

Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity

Silver Rate Is (Almost) Optimal for Gradient Descent