Gradient Descent Can Take Exponential Time to Escape Saddle Points
Simon S Du, Chi Jin, Jason Lee, Michael I Jordan, Aarti Singh, Barnabas Poczos
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.
BibTeX
@inproceedings{NIPS2017_f79921bb,
author = {Du, Simon S and Jin, Chi and Lee, Jason D and Jordan, Michael I and Singh, Aarti and Poczos, Barnabas},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Gradient Descent Can Take Exponential Time to Escape Saddle Points},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/f79921bbae40a577928b76d2fc3edc2a-Paper.pdf},
volume = {30},
year = {2017}
}