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
Figure 1: The trajectories of the SGD algorithm with fixed large and small step sizes (Columns 1 and 2, respectively) and a decaying learning rate on a toy problem. While a large step size allows the algorithm to explore the landscape efficiently, the small step size causes the algorithm to be trapped in a local minimum, leading to exponential runtime. The decaying step size allows the algorithm to visit the global minimum with high probability in polynomial time (Column 3).
Figure 2: Comparison of the weak Poincaré constant (normalized by 1/η ) to the standard Poincaré constant (normalized by 1/η ) for a 1-D toy function 1 1 1 The plot for the standard Poincaré constant is obtained by diagonalization of the actual generator of the dynamics. The plot for the weak Poincaré constant is obtained via Theorem A.1 by choosing various Gaussian distributions as base measure to get useful lower bound estimates causing some discontinuities in the plot. We expect the actual weak Poincaré constant to be smooth and even larger than our estimates. Since these are extensive quantities in 1/η for small η , we normalize the constants. . While the standard Poincaré constant decays exponentially, the weak Poincaré constant decays initially but then starts increasing, indicating that the effect of local minima can be benign with a proper annealing scheme.
Figure 3: Median number of iterations to convergence as a function of dimension d for fixed-rate SGD (blue) and annealed SGD (orange), both with hk=ηk . Error bars show the interquartile range over 10 runs. Dashed curves are descriptive fits; the coupled annealed power-law fit is weak.
d=100
d=200
d=300
d=400
Iterations ( ×105 )
Separable Double-Well
32.31±67.26
36.95±40.53
76.67±20.20
79.68±42.17
Rastrigin
0.0375±0.0036
0.1844±0.2210
3.0936±0.7004
4.1200±0.0013
Coupled Double-Well
0.1875±0.2942
0.2822±0.2131
0.2265±0.1189
0.5260±0.7577
Run time (seconds)
Separable Double-Well
4.20±8.75
9.42±10.34
29.60±8.03
41.57±21.87
Rastrigin
0.0076±0.0006
0.0671±0.0851
1.67±0.37
2.96±0.05
Coupled Double-Well
0.0251±0.0401
0.0742±0.0575
0.0905±0.0468
0.284±0.415
Table 1: Annealed SGD with arithmetic learning-rate decay and ht=ηt in high dimensions. Median recorded update counts ( ×105 ) and median run times (seconds), ± one empirical standard deviation over 10 trials per function and dimension. The stopping criterion is ∥x−x⋆∥∞<δ , with δ=0.5 for both double-well functions and δ=0.3 for Rastrigin.
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log2(1+2), we prove an Ω(n−psil−O(loglogn/logn)) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−1+psil2psil−O(loglogn/logn)). 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.
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.
We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε−5/3log(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.
Sichao Xiong, Sadok Jerad, Coralia Cartis
Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG