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.
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