math.OCNov 9, 2026

Learning Rate Decay Can Exponentially Accelerate SGD for Global Optimization of Nonconvex Functions

Authors: Guneykan Ozgul, Dylan Herman, Junhyung Lyle Kim, Shree Hari Sureshbabu, Shouvanik Chakrabarti

Organizations: Global Technology Applied Research, JPMorganChase New York, NY 10001, USA

Abstract

Stochastic Gradient Descent (SGD) is a workhorse algorithm for continuous optimization. It is a folk belief among deep learning practitioners that learning rate decay in SGD substantially improves performance. However, it has remained unclear whether learning rate decay offers an asymptotic advantage for global nonconvex optimization. We answer this question in the affirmative by demonstrating a natural class of nonconvex functions for which, we prove that SGD with learning rate decay requires exponentially fewer gradient queries for global optimization than SGD with any fixed learning rate in the small-step size regime. To the best of our knowledge, this is the first exponential advantage that has been demonstrated for learning rate decay. The class of functions we consider includes many popular benchmark nonconvex functions. Our results provide a robust explanatory theory for the empirically observed benefits of learning rate decay for global optimization. We show that annealing performs the non-logconcave sampling task associated to the optimization problem in polynomial time, via a novel application of weak Poincaré inequalities.

Figures & tables

Explore similar work

Sep 8, 2026

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 psil=log⁡2(1+2)p_{\mathrm{sil}}=\log_2(1+\sqrt{2}), we prove an Ω(n−psil−O(log⁡log⁡n/log⁡n))Ω\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 Ω(n−2psil1+psil−O(log⁡log⁡n/log⁡n))Ω\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.
Nov 14, 2025

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.
May 4, 2026

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with  O~(ε−5/3)\tilde{\mkern1mu O}(ε^{-5/3}) Global Rate

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε−5/3log⁡(1/ε))O(ε^{-5/3}\log(1/ε)) oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.