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

Practitioners have long believed that decaying the learning rate helps stochastic gradient descent, but it was not known whether it gives an asymptotic advantage for global nonconvex optimisation. The paper proves that it can, exhibiting a class of functions, which includes many standard nonconvex benchmarks, on which the gap in query complexity is exponential in the small-step regime.

The argument treats annealed SGD as a sampler: decaying the step size performs the associated non-log-concave sampling task in polynomial time. The key tool is a weak Poincaré inequality, which controls mixing where a standard Poincaré constant would be exponentially bad. The authors say it is the first exponential separation shown for learning-rate decay.