# On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization

arXiv: https://arxiv.org/abs/1709.08571 · HTML: https://mlsanity.com/paper/1709.08571/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2017.

## Built on by (most cited first, 2 of 2)

- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Second-order step-size tuning of SGD for non-convex optimization](https://mlsanity.com/paper/2103.03570/) (2021)

## Abstract (arXiv)

The Hessian-vector product has been utilized to find a second-order stationary solution with strong complexity guarantee (e.g., almost linear time complexity in the problem's dimensionality). In this paper, we propose to further reduce the number of Hessian-vector products for faster non-convex optimization. Previous algorithms need to approximate the smallest eigen-value with a sufficient precision (e.g., ε2ll 1) in order to achieve a sufficiently accurate second-order stationary solution (i.e., λmin(nabla2 f(x))≥ -ε2). In contrast, the proposed algorithms only need to compute the smallest eigen-vector approximating the corresponding eigen-value up to a small power of current gradient's norm. As a result, it can dramatically reduce the number of Hessian-vector products during the course of optimization before reaching first-order stationary points (e.g., saddle points). The key building block of the proposed algorithms is a novel updating step named the NCG step, which lets a noisy negative curvature descent compete with the gradient descent. We show that the worst-case time complexity of the proposed algorithms with their favorable prescribed accuracy requirements can match the best in literature for achieving a second-order stationary point but with an arguably smaller per-iteration cost. We also show that the proposed algorithms can benefit from inexact Hessian by developing their variants accepting inexact Hessian under a mild condition for achieving the same goal. Moreover, we develop a stochastic algorithm for a finite or infinite sum non-convex optimization problem. To the best of our knowledge, the proposed stochastic algorithm is the first one that converges to a second-order stationary point in it high probability with a time complexity independent of the sample size and almost linear in dimensionality.