First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time

Yi Xu, Rong Jin, Tianbao Yang

Abstract

Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the essence of added noise, which hinder further improvements of these algorithms. In this paper, we present a novel perspective of noise-adding technique, i.e., adding the noise into the first-order information can help extract the negative curvature from the Hessian matrix, and provide a formal reasoning of this perspective by analyzing a simple first-order procedure. More importantly, the proposed procedure enables one to design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in terms of the problem's dimensionality). In particular, we develop a first-order stochastic algorithm based on our new technique and an existing algorithm that only converges to a first-order stationary point to enjoy a time complexity of $\widetilde O(d/\epsilon^{3.5})$ for finding a nearly second-order stationary point $\mathbf{x}$ such that $\|\nabla F(\mathbf{x})\|\leq \epsilon$ and $\nabla^2 F(\mathbf{x})\geq -\sqrt{\epsilon}I$ (in high probability), where $F(\cdot)$ denotes the objective function and $d$ is the dimensionality of the problem. To the best of our knowledge, this is the best theoretical result of first-order algorithms for stochastic non-convex optimization, which is even competitive with if not better than existing stochastic algorithms hinging on the second-order information.

Introduction

In the landscape of non-convex optimization, particularly within deep learning, saddle points present a significant challenge. These are points where the gradient is zero, yet the location is not a local minimum; instead, the curvature is positive in some directions and negative in others. Standard First-order Stationary Point (FSP) algorithms, such as Stochastic Gradient Descent (SGD), frequently stall at these points because the gradient signal vanishes.

To reach a Second-order Stationary Point (SSP)—defined as a point where the gradient is small and the Hessian matrix has no significant negative eigenvalues—researchers have historically followed two paths. The first involves second-order methods that utilize Hessian-vector products to identify downward directions. While iteration-efficient, these are computationally demanding. The second path involves noise-injected first-order methods. Although simpler to implement, previous analyses suggested these methods suffered from a "curse of dimensionality," with time complexities scaling poorly (e.g., $d^4$) relative to the number of parameters $d$. This paper introduces NEON (NEgative-curvature-Originated-from-Noise), a framework that enables purely first-order methods to escape saddle points in almost linear time, making them viable for modern high-dimensional models.

The NEON Procedure

The core innovation of this work is the NEON procedure. Rather than viewing noise as a simple perturbation to "shake" an algorithm out of a local trap, NEON treats noise as a seed for a principled sequence of gradient evaluations designed to probe the local Hessian structure.

  • The Procedure: Starting with a small random noise vector $\mathbf{u}_0$, NEON performs the sequence: $\mathbf{u}_{\tau+1} = \mathbf{u}_\tau - \eta(\nabla f(\mathbf{x} + \mathbf{u}_\tau) - \nabla f(\mathbf{x}))$.
  • The Connection: The authors demonstrate that this sequence is a first-order approximation of the Power Method applied to the Hessian matrix. If negative curvature exists, this sequence rapidly amplifies the noise component aligned with the downward direction.
  • Acceleration: By integrating Nesterov-style acceleration, the authors developed NEON+, which achieves the iteration complexity of the Lanczos method while remaining strictly first-order.
  • Integration: The NEON-A framework acts as a wrapper. A standard first-order solver (like SVRG or SCSG) runs until the gradient becomes small, at which point NEON is invoked to detect negative curvature. If found, the algorithm follows the downward path; otherwise, it has likely reached an SSP.

Complexity and Empirical Results

The theoretical strength of NEON lies in its dimensionality scaling. By showing that NEON requires only $\tilde{O}(1)$ gradient evaluations to identify a negative curvature direction, the total time complexity becomes $\tilde{O}(d)$. This allows first-order methods to compete with, or even surpass, second-order methods in high-dimensional settings.

Table 1: Comparison of time complexity for finding an $(\epsilon, \sqrt{\epsilon})$-SSP. NEON-based methods (this work) achieve linear scaling in $d$ and remove the $d^p$ factor present in earlier noisy first-order methods.

As illustrated in the comparison table, NEON-based algorithms like NEON-SCSG and NEON-Natasha achieve state-of-the-art complexities such as $\tilde{O}(d/\epsilon^{3.5})$. Notably, these methods only require an Incremental First-order Oracle (IFO), whereas previous high-performance methods like Natasha2 or SVRG-Hessian required an Incremental Second-order Oracle (ISO). Empirically, simulations on the gisette dataset confirmed that NEON and NEON+ perform as well as the Power Method and Lanczos method, even when the latter were provided with exact Hessian-vector products.

Conclusion

NEON provides a formal theoretical bridge between perturbed gradient methods and eigenvalue-based second-order methods, proving they are essentially two sides of the same coin. While the current analysis assumes Hessian smoothness and focuses on non-degenerate saddle points, it establishes a new benchmark for first-order stochastic optimization. Future research may extend these techniques to degenerate saddle points or relax the Lipschitz continuity requirements to better suit architectures like those utilizing ReLU activations.

Summary updated

Abstract

Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the essence of added noise, which hinder further improvements of these algorithms. In this paper, we present a novel perspective of noise-adding technique, i.e., adding the noise into the first-order information can help extract the negative curvature from the Hessian matrix, and provide a formal reasoning of this perspective by analyzing a simple first-order procedure. More importantly, the proposed procedure enables one to design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in terms of the problem's dimensionality). In particular, we develop a {\bf first-order stochastic algorithm} based on our new technique and an existing algorithm that only converges to a first-order stationary point to enjoy a time complexity of {$\widetilde O(d/ε^{3.5})$ for finding a nearly second-order stationary point $\bf{x}$ such that $\|\nabla F(bf{x})\|\leq ε$ and $\nabla^2 F(bf{x})\geq -\sqrtεI$ (in high probability), where $F(\cdot)$ denotes the objective function and $d$ is the dimensionality of the problem. To the best of our knowledge, this is the best theoretical result of first-order algorithms for stochastic non-convex optimization, which is even competitive with if not better than existing stochastic algorithms hinging on the second-order information.
BibTeX
@inproceedings{xu2018first,
  author = {Yi Xu and Rong Jin and Tianbao Yang},
  title = {{First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=rkWOlP-_bS},
}
Figure