Research
A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity
arXiv:2604.13393v1 Announce Type: cross Abstract: Davis, Drusvyatskiy, and Jiang showed that gradient descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions t
arXiv:2604.13393v1 Announce Type: cross Abstract: Davis, Drusvyatskiy, and Jiang showed that gradient descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions that grow at least quartically away from their minimizers. The argument is intricate, relying on monitoring the performance of the algorithm relative to a certain manifold of slow growth -- called the ravine. In this work, we provide a direct Lyapunov-based argument that bypasses these difficulties when the objective is in addition convex and a has a unique minimizer. As a byproduct of the argument, we obtain a more adaptive variant than the original algorithm with encouraging numerical performance.
Related
- Gradient Descent's Last Iterate is Often (slightly) Suboptimal
- Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
- Product-Stability: Provable Convergence for Gradient Descent on the Edge of Stability
- Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
- Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent
Source: arXiv cs.LG | 2026-04-16