Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points

Rachael Tappenden, Martin Takác

TL;DR

This paper reveals a surprising connection between Gradient Descent (GD) and the Power Method (PM), showing that GD implicitly computes information about the Hessian's eigenvalues. This insight leads to a new algorithm, GD-EIG, that can better escape saddle points and estimate the leftmost eigen-pair of the Hessian, offering a more robust approach to nonconvex optimization.

What Problem Does This Paper Address?

Gradient Descent (GD) is a cornerstone of optimization, but its performance on nonconvex problems, particularly near saddle points, can be notoriously slow, sometimes requiring exponential time to escape. While GD is simple and widely applicable, it often wastes valuable information about the curvature of the objective function. This paper addresses the question of whether this "wasted" curvature information, specifically related to the Hessian's eigenvalues, can be leveraged to improve GD's behavior, especially in escaping saddle points and finding stationary points more efficiently.

Methods

The core of this work lies in establishing a formal connection between Gradient Descent with Momentum (GDM) and the Power Method with Momentum (PMM). The authors demonstrate that the gradient updates in GDM are equivalent to the iterates of the PMM applied to a shifted version of the Hessian matrix. This connection implies that GD, even without explicit momentum, implicitly computes approximations to the dominant eigen-pair of this shifted matrix.

Based on this insight, they propose GD-EIG (Gradient Descent with EIGenvalue Approximation). This algorithm is essentially GDM with a fixed step size, augmented by an explicit calculation of the dominant eigenvalue of the shifted Hessian using the Rayleigh quotient. This provides an estimate of the leftmost eigenvalue of the original Hessian.

Furthermore, they introduce GD-EIG-Kick, an extension that uses the estimated leftmost eigenvalue to occasionally take a larger "kick" step, aiming to accelerate escape from saddle points or speed up convergence. The paper also analyzes the behavior of GD in the special case of R², showing that with known eigenvalue information, convergence can be achieved in just two iterations.

Datasets

Not discussed in the paper. The experiments use randomly generated symmetric indefinite matrices and positive definite matrices for evaluation.

Key Insights and Ideas

  • GD is implicitly running the Power Method: The gradient updates in Gradient Descent with Momentum are mathematically equivalent to the iterates of the Power Method applied to a shifted Hessian matrix. This is a fundamental insight that underpins the entire paper.
  • GD provides "free" eigenvalue information: Because GD implicitly runs the Power Method, it naturally computes approximations to the dominant eigenvalue and eigenvector of the shifted Hessian. This information, specifically the leftmost eigenvalue of the original Hessian, is readily available without significant extra computational cost.
  • Eigenvalue information can improve saddle point escape: The paper argues that the slow escape from saddle points by vanilla GD is partly due to its failure to utilize this readily available curvature information. By incorporating this information, algorithms can be designed to escape more effectively.
  • R² is a special case for GD: In two dimensions, if the largest eigenvalue of the Hessian is known, GD can converge to a stationary point and fully characterize it (minimizer or saddle) in just two iterations.

Key Results

  • GD-EIG recovers leftmost eigen-pair: Numerical experiments demonstrate that GD-EIG can successfully estimate the leftmost eigenvalue and corresponding eigenvector of the Hessian, even for large matrices.
  • GD-EIG-Kick accelerates saddle point escape: Experiments show that GD-EIG-Kick significantly outperforms vanilla GD in escaping saddle points, especially in challenging nonconvex scenarios. The "kick" steps, guided by the estimated eigenvalue, lead to faster progress.
  • Improved step size strategies: The paper suggests that knowledge of the leftmost eigenvalue can inform better step size choices, potentially leading to faster convergence or more robust escape from saddle points. For instance, a step size of $2/\lambda_1$ with specific initialization is shown to guarantee convergence for positive definite matrices.

Limitations and Future Work

  • Quadratic assumption: The core connection between GD and PM is established for quadratic functions. Generalizing these ideas to non-quadratic functions is identified as a significant area for future work.
  • Newton-GD type algorithms: The authors suggest investigating Newton-GD type algorithms that build a quadratic model at each iterate and use GD-EIG to find a search direction, potentially of negative curvature.
  • Adaptive step sizes: While the paper explores fixed step sizes and a "kick" mechanism, further research into adaptive step size strategies informed by eigenvalue estimates is suggested.
  • Initialization sensitivity: While GD-EIG-Kick is shown to be robust, the paper notes that for the Power Method (and by extension, GD-EIG) to converge, the initial gradient must have a component in the direction of the leftmost eigenvector.

Summary updated

Abstract

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.
BibTeX
@misc{tappenden2022gradient,
  author = {Rachael Tappenden and Martin Takác},
  title = {{Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points}},
  year = {2022},
  eprint = {2211.00866},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.00866},
}
Figure