  Gradient descent (GD) and stochastic gradient descent (SGD) are the
workhorses of large-scale machine learning. While classical theory focused on
analyzing the performance of these methods in convex optimization problems, the
most notable successes in machine learning have involved nonconvex
optimization, and a gap has arisen between theory and practice. Indeed,
traditional analyses of GD and SGD show that both algorithms converge to
stationary points efficiently. But these analyses do not take into account the
possibility of converging to saddle points. More recent theory has shown that
GD and SGD can avoid saddle points, but the dependence on dimension in these
analyses is polynomial. For modern machine learning, where the dimension can be
in the millions, such dependence would be catastrophic. We analyze perturbed
versions of GD and SGD and show that they are truly efficient---their dimension
dependence is only polylogarithmic. Indeed, these algorithms converge to
second-order stationary points in essentially the same time as they take to
converge to classical first-order stationary points.
