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 works need to approximate the smallest eigen-value with a sufficient precision (e.g., ǫ 2 ≪ 1) in order to achieve a sufficiently accurate second-order stationary solution (i.e., λ min (∇ 2 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 in the worst-case the proposed algorithms with their favorable prescribed accuracy requirements can match the best time complexity 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 (e.g., the sub-sampled Hessian for a finite-sum problem) 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, which only involves computing a sub-sampled gradient and a noisy negative curvature of a sub-sampled Hessian at each iteration. To the best of our knowledge, the proposed stochastic algorithm is the first one, which converges to a second-order stationary point in high probability with a time complexity independent of the sample size and almost linear in the problem's dimensionality.
The gradient descent has also been incorporated with the negative curvature descent in ; REF ; in order to converge to the second-order stationary points.
On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
arXiv: Optimization and Control
Mathematics