Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
Open Access
- 22 October 2025
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- p. 1-66
Abstract
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution—which we call the ravine—so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.Keywords
All Related Versions
Funding Information
- Alfred P. Sloan Foundation (Sloan Fellowship)
- National Science Foundation (DMS-2047637, DMS-2306322, CCF-1740551)
- Air Force Research Laboratory (FA9550-24-1-0092)
This publication has 50 references indexed in Scilit:
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition2016
- Optimality, identifiability, and sensitivityMathematical Programming, 2013
- Smooth Manifolds2013
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- The Analysis of Linear Partial Differential Operators III2007
- A -algorithm for convex minimizationMathematical Programming, 2005
- Local Minima and Convergence in Low-Rank Semidefinite ProgrammingMathematical Programming, 2004
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- Error bounds and convergence analysis of feasible descent methods: a general approachAnnals of Operations Research, 1993
- On Richardson's Method for Solving Linear Systems with Positive Definite MatricesJournal of Mathematics and Physics, 1953