Escape saddle points by a simple gradient-descent based algorithm

Chenyi Zhang, Tongyang Li

Abstract

In nonconvex optimization, finding local minima is often hindered by saddle points. This paper introduces a simple, single-loop gradient-based algorithm that escapes saddle points significantly faster than previous state-of-the-art methods. By implementing a "robust Hessian power method" using only first-order gradients, the authors achieve a polynomial speedup in terms of problem dimension ($\log n$) while maintaining optimal precision complexity.

Introduction

Nonconvex optimization is the backbone of modern machine learning, including deep learning, PCA, and tensor decomposition. While finding a global minimum is NP-hard, reaching a "local minimum" is typically sufficient. However, the primary obstacles are saddle points: locations where the gradient is zero but the point is not a minimum. To escape these, an algorithm must identify directions of negative curvature.

Existing approaches generally fall into two categories: those that use random perturbations ("shakes") to stumble away from saddles—which is inefficient in high dimensions—and those that compute the Hessian matrix, which is computationally prohibitive for large-scale models.

Methodology: A Single-Loop Gradient Approach

The authors propose a streamlined "single-loop" algorithm that identifies negative curvature without explicit Hessian computation. The core innovation is a Robust Hessian Power Method built entirely on gradient queries.

The Gradient Trick

The algorithm exploits a fundamental relationship: the difference between two nearby gradient queries approximates a Hessian-vector product: $$\nabla f(\tilde{x} + r\mathbf{y}) - \nabla f(\tilde{x}) \approx H(\tilde{x}) \cdot r\mathbf{y}$$ This allows the algorithm to "feel" the local landscape. Unlike random perturbations that are "blind," this method acts as a compass, pointing directly toward the steepest descent.

Acceleration and Simplicity

The method integrates Nesterov’s Accelerated Gradient Descent (AGD) to speed up the escape from saddle points. Crucially, the algorithm maintains a single-loop structure, avoiding the complexity of nested loops found in prior state-of-the-art methods. This simplicity facilitates easier implementation, tuning, and numerical stability through renormalization steps that prevent vector explosion.

Key Results

The proposed algorithm demonstrates superior performance in both theoretical complexity and empirical tests.

Comparison of iteration complexity and simplicity across various optimization settings.

Theoretical Complexity

As shown in the table above, the algorithm achieves significant improvements:

  • Non-stochastic Setting: It reaches an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log n / \epsilon^{1.75})$ iterations. This matches the best-known precision dependence while providing a polynomial improvement in dimension ($n$).
  • Stochastic Setting: In noisy environments, the complexity is reduced to $\tilde{O}(\log^2 n / \epsilon^4)$, a major leap over previous benchmarks like $\tilde{O}(\log^{15} n)$.

Empirical Performance

In numerical experiments using synthetic high-dimensional functions (Quartic, Triangle, and Exponential types), the algorithm escaped saddle points in approximately one-third of the iterations required by standard methods like Perturbed Gradient Descent (PGD).

Conclusion

By replacing blind perturbations with gradient-informed directions, this work provides a faster, simpler path to local minima in high-dimensional spaces. While the current focus is on synthetic landscapes, the reduction in dimension dependence from $\log^6 n$ to $\log n$ marks a significant theoretical advancement for large-scale nonconvex optimization. Future research will focus on applying these techniques to massive real-world deep learning models.

Summary updated

Abstract

Escaping saddle points is a central research topic in nonconvex optimization. In this paper, we propose a simple gradient-based algorithm such that for a smooth function $f\colon\mathbb{R}^n\to\mathbb{R}$, it outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log n/\epsilon^{1.75})$ iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with $\tilde{O}(\log^4 n/\epsilon^{2})$ or $\tilde{O}(\log^6 n/\epsilon^{1.75})$ iterations, our algorithm is polynomially better in terms of $\log n$ and matches their complexities in terms of $1/\epsilon$. For the stochastic setting, our algorithm outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log^{2} n/\epsilon^{4})$ iterations. Technically, our main contribution is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve the polynomial speedup in $\log n$ compared to the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.
BibTeX
@inproceedings{zhang2021escape,
  author = {Chenyi Zhang and Tongyang Li},
  title = {{Escape saddle points by a simple gradient-descent based algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=_lfL4zDOmE},
}
Figure