研究证明学习率衰减可让 SGD 全局优化指数级加速

论文的技术机制是把退火（annealing）对应到优化问题的非对数凹采样任务，通过弱 Poincaré 不等式的一个新颖应用，证明退火可以在多项式时间内完成该采样任务，从而在全局优化层面带来指数级加速。作者给出的函数类包含许多常用的非凸基准函数。

这项结果为深度学习实践中广泛采用的学习率调度（step decay、cosine 衰减等）提供了一个严格的理论解释：固定小步长的 SGD 在全局优化上确实存在渐近劣势，衰减不是仅有的工程经验。

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

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.

This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include SGD, 学习率衰减, 非凸优化, 退火.

Source attribution: curated from arXiv cs.LG (@Guneykan Ozgul, Dylan Herman, Junhyung Lyle Kim, Shree Hari Sureshbabu, Shouvanik Chakrabarti).