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