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., @math ) in order to achieve a sufficiently accurate second-order stationary solution (i.e., @math . 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 high probability with a time complexity independent of the sample size and almost linear in dimensionality.
Earlier work using second-order information for non-convex optimization revolves around trust-region methods , in which each iteration solves a non-convex constrained quadratic problem known as the trust-region problem. The classical iteration complexity of trust-region methods for finding an @math -second-order stationary point is @math . Solving the trust-region problem may take a super-liner time in the dimensionality of the problem. For example, @cite_6 designed a first-order method that finds an @math -approximate solution to the trust-region problem with @math time complexity, where @math is the number of non-zero elements in the involved Hessian matrix that could be @math . Recently, @cite_8 designed an efficient variant of the trust-region method that allows for an inexact Hessian with the same iteration complexity @math . They also showed that the trust-region problem can be solved approximately by searching a direction in a two dimentional space consisting of the negative gradient and the negative curvature. Recent proposals on different variants of trust-region methods match the iteration complexity of 's cubic regularization method, i.e., @math . Nonetheless, their per-iteration costs could be still super-linear of the problem's dimensionality.
@cite_6 @cite_8
1483062147 2747280560
We consider the fundamental problem of minimizing a general quadratic function over an ellipsoidal domain, also known as the trust region (sub)problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an @math ∈-approximate solution in runtime of order N @math ∈, where N is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent, suitable for the special case in which the quadratic objective is convex, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic. We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve @math -approximate second-order optimality which have shown to be tight. Our Hessian approximation conditions constitute a major relaxation over the existing ones in the literature. Consequently, we are able to show that such mild conditions allow for the construction of the approximate Hessian through various random sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and cubic regularization methods.