Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimization

2019/08/19 by Vlaski, Stefan, Sayed, Ali H. · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1908.07023

Abstract

Recent years have seen increased interest in performance guarantees of gradient descent algorithms for non-convex 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.

Cited by

• Improved High-probability Convergence Guarantees of Decentralized SGD
• On the Escaping Efficiency of Distributed Adversarial Training Algorithms

Related

• Tackling benign nonconvexity with smoothing and stochastic gradients
• Escaping Saddles with Stochastic Gradients
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Second-order Properties of Noisy Distributed Gradient Descent
• Notes on Worst-case Inefficiency of Gradient Descent Even in R²