Adaptive Negative Curvature Descent with Applications in Non-convex Optimization

Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, Tianbao YangNeurIPS 2018 · OpenReview

Introduction

In non-convex optimization—a cornerstone of training deep neural networks—finding a simple stationary point where the gradient is zero is often insufficient. Simple gradient descent algorithms frequently get trapped at saddle points, where the gradient is zero but the Hessian matrix contains negative eigenvalues, indicating that further "downhill" directions exist.

To escape these saddle points and find true local minima, researchers employ Negative Curvature Descent (NCD). However, standard NCD algorithms are computationally expensive. They require approximating the smallest eigenvalue of the Hessian matrix to a very high, fixed precision ($\epsilon_2$), typically using the Lanczos method. This necessitates numerous costly Hessian-vector products.

This paper introduces Adaptive Negative Curvature Descent (AdaNCD), a method that varies the precision of Hessian eigenvalue approximations based on the current gradient's magnitude. By recognizing that a highly precise negative curvature direction is unnecessary when the gradient is already large, AdaNCD significantly reduces computational overhead without sacrificing theoretical guarantees.

The Adaptive NCD Approach

The core innovation of this work is the transition from a fixed-precision requirement to an Adaptive NCD step.

Adaptive Precision

Instead of demanding a strict, fixed precision, the algorithm allows for an approximation error that adapts to the current state of the optimization landscape. The noise level permitted in approximating the smallest eigenvalue is set to $\max(\epsilon_2, \|\nabla f(\mathbf{x})\|^\alpha)$, where $\alpha \in (0, 1]$. In practical terms, if the gradient is large (meaning the algorithm is on a steep slope), it settles for a "noisier," cheaper estimate of the negative curvature.

Competition Mechanism

To ensure continuous progress, the algorithm employs a competition mechanism. It compares the predicted decrease in the objective function from a potentially noisy NCD step against a standard gradient descent step, executing whichever direction is more promising.

Algorithmic Variants

The authors successfully integrate this adaptive step into several optimization frameworks:

  • AdaNCG: A straightforward deterministic version.
  • S-AdaNCG: A stochastic version tailored for large-scale datasets.
  • AdaNCG+: An accelerated deterministic version designed to match state-of-the-art time complexities.
  • AdaNCD-SCSG: A variant combined with variance reduction techniques (SCSG).

Experimental Validation

The researchers evaluated the AdaNCD algorithms across three distinct problem settings:

  1. Cubic Regularization: A synthetic landscape specifically designed to test an algorithm's ability to escape saddle points.
  2. Regularized Non-linear Least-Squares: Evaluated using the w1a dataset (2,477 samples, 300 features) from the LIBSVM library.
  3. Neural Network Training: A one-hidden-layer network (7,872 parameters) trained on the MNIST dataset for binary classification (digits 0 and 1).

Key Insights and Results

  • Precision as a Lever: The primary insight is that you do not need a perfect map to navigate out of a valley if you are already on a steep slope. By relaxing the requirements for the Lanczos method when gradients are high, AdaNCD drastically cuts down on "oracle calls" (Hessian-vector products).
  • Maintained Complexity Bounds: Surprisingly, this "lazier" approach to computing curvature does not degrade worst-case iteration complexity. The authors prove that their adaptive methods match the best-known theoretical bounds, such as $O(\epsilon^{-1.75})$ for deterministic accelerated versions. Furthermore, for finding an $(\epsilon_1, \sqrt{\epsilon_1})$-second-order stationary point, the improved stochastic algorithm matches the state-of-the-art complexity of $O(d/\epsilon_1^{3.5})$.
  • Empirical Speedups: In practice, AdaNCD variants consistently reached lower objective values with significantly fewer oracle calls than their non-adaptive counterparts. On the cubic regularization task, the adaptive methods escaped the saddle point at the origin much faster than traditional methods. Additionally, S-AdaNCG demonstrated a nearly linear relationship with problem dimensionality, outperforming many noisy SGD methods in high-dimensional spaces.

Limitations and Future Directions

While AdaNCD presents a significant step forward, it does come with limitations:

  • Hyperparameter Sensitivity: The algorithms introduce new parameters, such as $\alpha$, and require knowledge or estimation of Lipschitz constants ($L_1$ and $L_2$). Estimating these constants can be notoriously difficult for complex deep neural networks.
  • Inherent Costs: Although the number of Hessian-vector products is reduced, they remain fundamentally more complex to implement and computationally heavier than simple first-order gradients.
  • Generalization to Deep Architectures: The empirical tests in the paper were limited to relatively shallow architectures (e.g., one hidden layer). Validating the scalability and efficiency of adaptive NCD on very deep or convolutional neural networks remains an important open area for future research.

Summary updated

Abstract

Negative curvature descent (NCD) method has been utilized to design deterministic or stochastic algorithms for non-convex optimization aiming at finding second-order stationary points or local minima. In existing studies, NCD needs to approximate the smallest eigen-value of the Hessian matrix with a sufficient precision (e.g., $\epsilon_2\ll 1$) in order to achieve a sufficiently accurate second-order stationary solution (i.e., $\lambda_{\min}(\nabla^2 f(\x))\geq -\epsilon_2)$. One issue with this approach is that the target precision $\epsilon_2$ is usually set to be very small in order to find a high quality solution, which increases the complexity for computing a negative curvature. To address this issue, we propose an adaptive NCD to allow for an adaptive error dependent on the current gradient's magnitude in approximating the smallest eigen-value of the Hessian, and to encourage competition between a noisy NCD step and gradient descent step. We consider the applications of the proposed adaptive NCD for both deterministic and stochastic non-convex optimization, and demonstrate that it can help reduce the the overall complexity in computing the negative curvatures during the course of optimization without sacrificing the iteration complexity.
BibTeX
@inproceedings{liu2018adaptive,
  author = {Mingrui Liu and Zhe Li and Xiaoyu Wang and Jinfeng Yi and Tianbao Yang},
  title = {{Adaptive Negative Curvature Descent with Applications in Non-convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SyZvnvWuZH},
}
Figure