Second-Order Guarantees of Stochastic Gradient Descent in Nonconvex Optimization

• 成果类型: Article
• 署名作者: Vlaski, Stefan; Sayed, Ali H.
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of California System; University of California Los Angeles; Imperial College London
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3131963
• 发表日期: 2022
• 页码: 6489-6504
• 关键词: convergence; Upper bound; Perturbation methods; COSTS; Heuristic algorithms; cost function; Convex functions; adaptation; gradient noise; nonconvex cost; stationary points; stochastic optimization

摘要

Recent years have seen increased interest in performance guarantees of gradient descent algorithms for nonconvex optimization. A number of works have uncovered that gradient noise plays a critical role in the ability of gradient descent recursions to efficiently escape saddle-points and reach second-order stationary points. Most available works limit the gradient noise component to be bounded with probability one or sub-Gaussian and leverage concentration inequalities to arrive at high-probability results. We present an alternate approach, relying primarily on mean-square arguments and show that a more relaxed relative bound on the gradient noise variance is sufficient to ensure efficient escape from saddle points without the need to inject additional noise, employ alternating step sizes, or rely on a global dispersive noise assumption, as long as a gradient noise component is present in a descent direction for every saddle point.