Learning Rate Decay Can Exponentially Accelerate SGD for Global Optimization of Nonconvex Functions
The proof covers a class of nonconvex functions that includes many popular optimization benchmarks.
For this class, decaying the learning rate lets SGD reach a global optimum with exponentially fewer gradient queries than any fixed learning rate in the small-step-size regime. The authors say this is the first demonstrated exponential advantage for learning rate decay. Their analysis uses weak Poincaré inequalities to show that annealing solves the associated non-logconcave sampling problem in polynomial time. The result concerns the specified function class, rather than nonconvex optimization in general.
ArXiv · AI/CL/LG's note
For this class, decaying the learning rate lets SGD reach a global optimum with exponentially fewer gradient queries than any fixed learning rate in the small-step-size regime. The authors say this is the first demonstrated exponential advantage for learning rate decay. Their analysis uses weak Poincaré inequalities to show that annealing solves the associated non-logconcave sampling problem in polynomial time. The result concerns the specified function class, rather than nonconvex optimization in general.
ArXiv · AI/CL/LG's note
score 5