Last-Iterate Convergence Rate of Normalized Gradient Descent under H\"older Smoothness

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, $(\nu,M_\nu)$-Hölder-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$.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2610.06070 [math.OC]

(or arXiv:2610.06070v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.06070 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.