# Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth

arXiv: https://arxiv.org/abs/2409.19791 · HTML: https://mlsanity.com/paper/2409.19791/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2024.

## Built on by (most cited first, 10 of 10)

- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [Through the River: Understanding the Benefit of Schedule-Free Methods for Language Model Training](https://mlsanity.com/paper/2507.09846/) (2025)
- [A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models](https://mlsanity.com/paper/2505.11664/) (2025)
- [Towards Understanding Adam Convergence on Highly Degenerate Polynomials](https://mlsanity.com/paper/2603.09581/) (2026)
- [Understanding Quantization-Aware Training: Gradients at Quantized Weights Bias to the Low-Loss Basin](https://mlsanity.com/paper/2606.09012/) (2026)
- [Towards Understanding Momentum Acceleration in River-Valley Loss Landscape](https://mlsanity.com/paper/2609.30957/) (2026)
- [A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity](https://mlsanity.com/paper/2604.13393/) (2026)
- [Local linear convergence of gradient methods for overparameterized Gaussian mixtures](https://mlsanity.com/paper/2605.30936/) (2026)
- [Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing](https://mlsanity.com/paper/2609.37865/) (2026)
- [Hybrid Methods for Robust Tabular Data Imputation](https://mlsanity.com/paper/2609.39613/) (2026)

## Abstract (arXiv)

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.