Fetching the paper…
Reading the bibliography…
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.
Analytic extensions of differentiable functions defined in closed sets
Hassler Whitney · 1934
Earlier work this paper cites.
Nonnegativity-, monotonicity-, or convexity-preserving cubic and quintic Hermite interpolation
Randall L Dougherty, Alan S Edelman, and James M Hyman · 1989
Earlier work this paper cites.
Nonconvergence to unstable points in urn models and stochastic approximations
Robin Pemantle · 1990
Earlier work this paper cites.
Stochastic Approximation and Recursive Algorithms and Applications , volume 35
G George Yin and Harold J Kushner · 2003
Earlier work this paper cites.
Cubic regularization of newton method and its global performance
Yurii Nesterov and Boris T Polyak · 2006
Earlier work this paper cites.
Geometric Theory of Dynamical Systems: An Introduction
J Jr Palis and Welington De Melo · 2012
Earlier work this paper cites.
Introductory Lectures on Convex Optimization: A Basic Course , volume 87
Yurii Nesterov · 2013
Earlier work this paper cites.
Phase retrieval using alternating minimization
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi · 2013
Earlier work this paper cites.
A trust region algorithm with a worst-case iteration complexity of O( ϵ − 3 / 2 \epsilon^{-3/2} ) for nonconvex optimization
Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi · 2014
Earlier work this paper cites.
Understanding alternating minimization for matrix completion
Moritz Hardt · 2014
Earlier work this paper cites.
Phase retrieval via Wirtinger flow: Theory and algorithms
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi · 2015
Earlier work this paper cites.
The Whitney extension theorem in high dimensions
Alan Chang · 2015
Cited alongside, same era.
Escaping from saddle points—online stochastic gradient for tensor decomposition
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan · 2015
Cited alongside, same era.
Global optimality of local search for low rank matrix recovery
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro · 2016
Cited alongside, same era.
Gradient descent efficiently finds the cubic-regularized non-convex Newton step
Yair Carmon and John C Duchi · 2016
Cited alongside, same era.
Accelerated methods for non-convex optimization
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
Blake E Woodworth and Nati Srebro · 2016
Later among the works it cites.
Fast algorithms for robust PCA via gradient descent
Xinyang Yi, Dohyung Park, Yudong Chen, and Constantine Caramanis · 2016
Later among the works it cites.
Finding Approximate Local Minima Faster Than Gradient Descent
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma · 2017
Closest in time.
When is a convolutional filter easy to learn?
Simon S Du, Jason D Lee, and Yuandong Tian · 2017
Closest in time.
No spurious local minima in nonconvex low rank problems: A unified geometric analysis
Rong Ge, Chi Jin, and Yi Zheng · 2017
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Matrix completion has no spurious local minimum
Rong Ge, Jason D Lee, and Tengyu Ma · 2016
Cited alongside, same era.
Gradient descent only converges to minimizers
Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht · 2016
Cited alongside, same era.
The power of normalization: Faster evasion of saddle points
Kfir Y Levy · 2016
Cited alongside, same era.
Symmetry, saddle points, and global geometry of nonconvex matrix factorization
Xingguo Li, Zhaoran Wang, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, and Tuo Zhao · 2016
Cited alongside, same era.
A geometric analysis of phase retrieval
Ju Sun, Qing Qu, and John Wright · 2016
Cited alongside, same era.
Guaranteed matrix completion via non-convex factorization
Ruoyu Sun and Zhi-Quan Luo · 2016
Cited alongside, same era.
Global convergence of non-convex gradient descent for computing matrix squareroot
Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli · 2017
Closest in time.
How to escape saddle points efficiently
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan · 2017
Closest in time.
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach
Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi · 2017
Closest in time.
Complete dictionary recovery over the sphere I: Overview and the geometric picture
Ju Sun, Qing Qu, and John Wright · 2017
Closest in time.
Stochastic variance-reduced gradient descent for low-rank matrix recovery from linear measurements
Xiao Zhang, Lingxiao Wang, and Quanquan Gu · 2017
Closest in time.