How to Escape Saddle Points Efficiently
This work addresses a key bottleneck in non-convex optimization for machine learning practitioners, enabling more efficient training of models like deep neural networks by escaping saddle points almost for free.
The paper tackles the problem of efficiently escaping saddle points in non-convex optimization by showing that a perturbed gradient descent method converges to second-order stationary points with a dimension-free iteration count, matching the rate of gradient descent to first-order points up to log factors. This result applies to machine learning applications like deep learning and matrix factorization, where it establishes sharp global convergence rates.
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the well-known convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free. Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.