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

Aug 11, 2026math.OC

A lower bound for stepsize-based acceleration of gradient descent

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.

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

Ask PDF

Jul 24, 2026cs.LG

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

We study adaptive gradient descent for continuously differentiable, possibly nonconvex objectives under one-sided Hölder regularity. Unlike classical Hölder- or Lipschitz-gradient assumptions, which control the full gradient variation, our condition bounds only the directional term appearing in the descent inequality. This can allow less conservative step sizes when large gradient changes are orthogonal to, or favorable along, the update direction. We propose an adaptive scalar-step method based on an estimate of positive one-sided Hölder curvature, combined with a simple sufficient-decrease safeguard. For nonconvex objectives on a convex region containing the accepted update segments, we prove an explicit best-iterate stationarity bound with a rate determined by the Hölder exponent. Unlike predetermined diminishing step-size schemes, the method adapts to the local descent geometry. We evaluate the approach on two full-batch benchmarks designed to separate directional curvature from full gradient variation. On a binary classification problem, the method achieves the lowest final cross-entropy, objective value, and gradient norm, together with the largest classification margin among the compared scalar gradient methods. On a nonconvex Hölder regression problem, it attains the lowest final objective gap and gradient norm. These results indicate that one-sided Hölder curvature is an effective adaptive step-size signal when full-gradient variation is inflated by directions that do not hinder descent.

Arzu Ahmadova, Ismail Huseynov

Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · Physikalisch-Technische Bundesanstalt (PTB), Germany · Technical University of Berlin, Germany

Gradient Descent Descent Local Curvature

Ask PDF

Date pendingmath.OC

Silver Rate Is (Almost) Optimal for Gradient Descent

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing

p_{\mathrm{sil}}=\log_2(1+\sqrt{2})

, we prove an

\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)

non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error

\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)

. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.

Yuhan Ye, Kaizhao Liu

MIT

Step Accuracy Gradient Descent Convex Optimization Convergence Optimal Silver Bullet

Ask PDF