Gradient Descent Can Take Exponential Time to Escape Saddle Points

Abstract

Although gradient descent (GD) almost always escapes saddle points asymptotically [Lee et al., 2016], this paper shows that even with fairly natural random initialization schemes and non-pathological functions, GD can be significantly slowed down by saddle points, taking exponential time to escape. On the other hand, gradient descent with perturbations [Ge et al., 2015, Jin et al., 2017] is not slowed down by saddle points - it can find an approximate local minimizer in polynomial time. This result implies that GD is inherently slower than perturbed GD, and justifies the importance of adding perturbations for efficient non-convex optimization. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.

arXiv commentAccepted by NIPS 2017

Cited by in corpus (24)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Multiplicative noise and heavy tails in stochastic optimization
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• On the distance between two neural networks and the stability of learning
• Escaping from saddle points on Riemannian manifolds
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Escaping Saddle Points Faster with Stochastic Momentum
• Stochastic Training is Not Necessary for Generalization
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• Distributed Stochastic Nested Optimization via Cubic Regularization
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Distributed Newton-like Algorithms and Learning for Optimized Power Dispatch
• Vanishing Curvature and the Power of Adaptive Methods in Randomly Initialized Deep Networks
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond