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

Yi Xu, Jing Rong, Tianbao Yang

TL;DR

This paper introduces NEON (NEgative-curvature Originated-from-Noise), a clever first-order technique that allows stochastic optimization algorithms to escape saddle points in almost linear time relative to the problem's dimensionality. By using only gradients to mimic second-order curvature extraction, the authors bridge the gap between slow noise-injection methods and computationally heavy Hessian-based methods, achieving state-of-the-art convergence guarantees for non-convex problems.

What Problem Does This Paper Address?

In the world of non-convex optimization (such as training deep neural networks), algorithms often get "stuck" at saddle points—locations where the gradient is zero, but the algorithm hasn't reached a local minimum. While standard Stochastic Gradient Descent (SGD) is great at finding stationary points, it doesn't naturally know how to "slide down" the negative curvature of a saddle point to find better solutions.

Existing solutions generally fall into two camps:

  1. Noise-based methods: These add random noise to gradients (e.g., Noisy SGD). While simple, their efficiency plummets as the number of dimensions ($d$) grows, often scaling at $O(d^4)$.
  2. Hessian-based methods: These use second-order information (the Hessian matrix) to find directions of negative curvature. While fast in terms of iterations, computing the Hessian or even Hessian-vector products (HVP) can be computationally expensive or numerically unstable in high dimensions.

The authors seek a "middle way": a purely first-order (gradient-only) method that escapes saddle points as efficiently as second-order methods but scales linearly with the number of dimensions.

Methods

The core contribution is a pair of procedures called NEON and NEON+.

  • NEON: This is a first-order procedure designed to extract negative curvature. It starts by adding a small amount of noise to a potential saddle point and then runs a specific sequence of gradient descent steps. The authors prove that this sequence effectively mimics the "Power Method" (a classic linear algebra tool for finding eigenvalues) to identify directions where the function drops off sharply.
  • NEON+: This version incorporates Nesterov’s Accelerated Gradient (NAG). By using momentum, NEON+ speeds up the discovery of negative curvature, matching the iteration complexity of the more advanced Lanczos method ($1/\sqrt{\gamma}$ instead of $1/\gamma$) while remaining HVP-free.
Comparison of negative curvature extraction methods.
  • The Framework: The authors provide a "plug-and-play" framework. You can take an existing first-order algorithm (like SGD, SCSG, or Natasha) and wrap it with NEON. If the algorithm gets stuck at a point with a small gradient, NEON kicks in to see if it's a saddle point. If it finds a direction of negative curvature, the algorithm takes a "leap" in that direction to escape.

Datasets

The authors validated their approach using two main setups:

  1. Synthetic Non-Convex Function: A specifically designed function $f(x) = \sum_{i=1}^d \xi_i(x_i^4 - 4x_i^2)$ where the saddle points are known, allowing for a clear measurement of how quickly different algorithms escape them.
  2. Gisette Dataset: A high-dimensional binary classification dataset from the LIBSVM library ($n=6000$ examples, $d=5000$ features). They used this to test a non-linear least squares problem with a non-convex regularizer, representing a more "real-world" high-dimensional challenge.

Key Insights and Ideas

  • Gradients as Curvature Proxies: The most profound insight is that a sequence of gradients starting from a noise-perturbed point contains enough information to approximate the Hessian's smallest eigenvalue. You don't need to calculate the Hessian; you just need to observe how the gradients evolve.
  • Bridging Two Worlds: NEON connects noise-injection methods (like Perturbed Gradient Descent) with second-order methods. It shows that the "noise" isn't just for luck; it's the starting point for a principled search for negative curvature.
  • Acceleration Works for Escaping: It was previously unclear if Nesterov-style acceleration could help in the specific task of finding negative curvature directions. This paper proves that it does, leading to the faster NEON+ variant.

Key Results

  • Dimensionality Scaling: NEON-based algorithms achieve a time complexity that is almost linear in $d$. For example, NEON-SCSG finds a second-order stationary point in $\widetilde{O}(d/\epsilon^{3.5})$ time.
Theoretical time complexity comparison of various stochastic algorithms.
  • Superiority over Noisy SGD: In experiments, as the dimensionality $d$ increased from $10^3$ to $10^5$, the performance of Noisy SGD degraded significantly, while NEON-SGD remained efficient.
  • Competitive with Second-Order: As shown in the methods comparison, NEON+ performed similarly to (and sometimes better than) the Lanczos method, which requires Hessian-vector products. This is a major win for implementation simplicity, as HVPs can be difficult to code or computationally heavy in certain frameworks.

Limitations and Future Work

  • Hessian Smoothness: The theoretical guarantees rely on the Hessian being "Lipschitz continuous" (it doesn't change too abruptly). While common in theory, this might not hold for all neural network architectures (like those with ReLU activations).
  • Hyperparameter Sensitivity: Like many stochastic methods, the performance depends on choosing the right noise radius and step sizes. While the paper provides theoretical values, practical tuning is still required.
  • Stochastic Gradients: While the paper addresses the stochastic setting via mini-batching, the "purely stochastic" (batch size of 1) version of negative curvature extraction remains a challenging area for future refinement to further reduce the IFO (Incremental First-order Oracle) complexity.

Summary updated

Abstract

This is a theory paper) In this paper, we consider first-order methods for solving stochastic non-convex optimization problems. The key building block of the proposed algorithms is first-order procedures to extract negative curvature from the Hessian matrix through a principled sequence starting from noise, which are referred to {\it NEgative-curvature-Originated-from-Noise or NEON} and are of independent interest. Based on this building block, we design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in the problem's dimensionality). In particular, we develop a general framework of {\it first-order stochastic algorithms} with a second-order convergence guarantee based on our new technique and existing algorithms that may only converge to a first-order stationary point. For finding a nearly {\it second-order stationary point} $\x$ such that $\|\nabla F(\x)\|\leq \epsilon$ and $\nabla^2 F(\x)\geq -\sqrt{\epsilon}I$ (in high probability), the best time complexity of the presented algorithms is $\widetilde O(d/\epsilon^{3.5})$, where $F(\cdot)$ denotes the objective function and $d$ is the dimensionality of the problem. To the best of our knowledge, this is the first theoretical result of first-order stochastic algorithms with an almost linear time in terms of problem's dimensionality for finding second-order stationary points, which is even competitive with existing stochastic algorithms hinging on the second-order information.
BibTeX
@inproceedings{xu2018first,
  author = {Yi Xu and Jing Rong 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