Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points
This work addresses the slow escape from saddle points in nonconvex optimization, a critical issue for training deep neural networks, by leveraging eigen-information from GD, though it is incremental as it builds on known connections and examples.
The paper establishes a connection between Gradient Descent (GD) with fixed step size and the Power Method (PM), showing that GD can provide eigen-information to escape saddle points more efficiently in nonconvex optimization. It demonstrates that with known eigenvalues, GD can converge in two iterations for quadratics in R^2 and proposes new step size strategies to improve practical performance.
This work shows that applying Gradient Descent (GD) with a fixed step size to minimize a (possibly nonconvex) quadratic function is equivalent to running the Power Method (PM) on the gradients. The connection between GD with a fixed step size and the PM, both with and without fixed momentum, is thus established. Consequently, valuable eigen-information is available via GD. Recent examples show that GD with a fixed step size, applied to locally quadratic nonconvex functions, can take exponential time to escape saddle points (Simon S. Du, Chi Jin, Jason D. Lee, Michael I. Jordan, Aarti Singh, and Barnabas Poczos: "Gradient descent can take exponential time to escape saddle points"; S. Paternain, A. Mokhtari, and A. Ribeiro: "A newton-based method for nonconvex optimization with fast evasion of saddle points"). Here, those examples are revisited and it is shown that eigenvalue information was missing, so that the examples may not provide a complete picture of the potential practical behaviour of GD. Thus, ongoing investigation of the behaviour of GD on nonconvex functions, possibly with an \emph{adaptive} or \emph{variable} step size, is warranted. It is shown that, in the special case of a quadratic in $R^2$, if an eigenvalue is known, then GD with a fixed step size will converge in two iterations, and a complete eigen-decomposition is available. By considering the dynamics of the gradients and iterates, new step size strategies are proposed to improve the practical performance of GD. Several numerical examples are presented, which demonstrate the advantages of exploiting the GD--PM connection.