Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence

Mingrui Liu, Tianbao Yang

Abstract

Finding second-order stationary points (SOSP) in non-convex landscapes is a fundamental challenge in machine learning. While stochastic gradient descent (SGD) is the standard for first-order convergence, it often struggles with saddle points. This paper introduces SNCG-1 and SNCG-2, the first stochastic algorithms to guarantee convergence to a nearly second-order optimal point with high probability and near-linear time complexity. By utilizing a novel "competing directions" mechanism between gradient descent and negative curvature descent, these algorithms provide stronger guarantees than existing methods like Natasha2, which only offer convergence in expectation.

Introduction

In modern machine learning, particularly deep learning, optimization typically involves navigating complex non-convex objective functions. The standard tool, Stochastic Gradient Descent (SGD), guarantees convergence to a first-order stationary point where the gradient is zero. However, such points can be saddle points—locations that appear to be minima in some directions but maxima in others.

To ensure true optimization, algorithms must find second-order stationary points (SOSP), where the gradient is near zero and the Hessian matrix lacks significant negative eigenvalues. While deterministic methods for finding SOSPs exist, achieving this efficiently in a stochastic setting—where only noisy samples are available—with high-probability guarantees has remained an open problem.

Methods

The core of the proposed approach is the Stochastic Negative Curvature Gradient (NCG-S) step. This mechanism handles the exploration of the landscape through two primary strategies:

  1. Competing Directions: At each iteration, the algorithm calculates both a stochastic gradient and an approximate negative curvature direction (via Hessian-vector products). It evaluates which direction promises a more significant reduction in the objective function and proceeds with the "winner." This purposeful search for negative curvature allows the algorithm to escape saddle points more effectively than methods relying on isotropic noise.
  2. Adaptive Noise and Approximation: To maintain efficiency, the authors avoid expensive exact Hessian computations. Instead, they use adaptive noise levels and approximate PCA techniques (such as Oja’s algorithm).

The authors propose two variants: SNCG-1, which uses the NCG-S step at every iteration, and SNCG-2, a hybrid that behaves like standard SGD when gradients are large and only invokes the more computationally intensive NCG-S step when the gradient magnitude drops, suggesting proximity to a potential saddle point.

Results and Comparison

The SNCG algorithms represent a significant advancement in stochastic optimization. They are the first to achieve second-order convergence with high probability in almost linear time complexity relative to the dimensionality ($d$).

Comparison of SNCG with existing stochastic optimization algorithms in terms of oracle type, guarantees, and time complexity.

As shown in the comparison table above, SNCG provides a $(\epsilon, \epsilon^{1/2})$ second-order guarantee with high probability. This is a stronger guarantee than Natasha2, which only provides convergence in expectation. Furthermore, the time complexity of $\tilde{O}(d \cdot \epsilon^{-4})$ remains competitive with first-order methods while offering the robustness of second-order optimality. Unlike Noisy SGD, which requires $d^p$ complexity, SNCG maintains near-linear dependence on dimension.

Discussion and Limitations

While theoretically groundbreaking, the practical application of SNCG faces some hurdles. As a theoretical work, the "big-O" notation hides constants that might be large in practice, potentially making the algorithm slower than theory suggests for specific problems. Additionally, the algorithms require tuning several hyperparameters and knowledge of Lipschitz constants ($L_1, L_2$), which are often unknown in real-world deep learning tasks.

Future work may involve integrating these "competing direction" and adaptive noise concepts into finite-sum frameworks like SVRG to further reduce computational overhead and improve practical performance.

Summary updated

Abstract

In this paper, we study stochastic non-convex optimization with non-convex random functions. Recent studies on non-convex optimization revolve around establishing second-order convergence, i.e., converging to a nearly second-order optimal stationary points. However, existing results on stochastic non-convex optimization are limited, especially with a high probability second-order convergence. We propose a novel updating step (named NCG-S) by leveraging a stochastic gradient and a noisy negative curvature of a stochastic Hessian, where the stochastic gradient and Hessian are based on a proper mini-batch of random functions. Building on this step, we develop two algorithms and establish their high probability second-order convergence. To the best of our knowledge, the proposed stochastic algorithms are the first with a second-order convergence in {\it high probability} and a time complexity that is {\it almost linear} in the problem's dimensionality.
BibTeX
@misc{liu2017stochastic,
  author = {Mingrui Liu and Tianbao Yang},
  title = {{Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence}},
  year = {2017},
  eprint = {1710.09447},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.09447},
}
Figure