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
2398500126 2747280560 2530585400 2614389101
We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any @math ∈¯?(0,?), the algorithm requires at most @math O(∈-3 2) iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any @math ∈?(0,∈¯]. This improves upon the @math O(∈-2) bound known to hold for some other trust region algorithms and matches the @math O(∈-3 2) bound for the recently proposed Adaptive Regularisation framework using Cubics, also known as the arc algorithm. Our algorithm, entitled trace, follows a trust region framework, but employs modified step acceptance criteria and a novel trust region update mechanism that allow the algorithm to achieve such a worst-case global complexity bound. Importantly, we prove that our algorithm also attains global and fast local convergence guarantees under similar assumptions as for other trust region algorithms. We also prove a worst-case upper bound on the number of iterations, function evaluations, and derivative evaluations that the algorithm requires to obtain an approximate second-order stationary point. 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. In a recent paper, we introduced a trust-region method with variable norms for unconstrained minimization, we proved standard asymptotic convergence results, and we discussed the impact of this method in global optimization. Here we will show that, with a simple modification with respect to the sufficient descent condition and replacing the trust-region approach with a suitable cubic regularization, the complexity of this method for finding approximate first-order stationary points is @math O(ź-3 2). We also prove a complexity result with respect to second-order stationarity. Some numerical experiments are also presented to illustrate the effect of the modification on practical performance. We consider the minimization of non-convex functions that typically arise in machine learning. Specifically, we focus our attention on a variant of trust region methods known as cubic regularization. This approach is particularly attractive because it escapes strict saddle points and it provides stronger convergence guarantees than first- and second-order as well as classical trust region methods. However, it suffers from a high computational complexity that makes it impractical for large-scale learning. Here, we propose a novel method that uses sub-sampling to lower this computational cost. By the use of concentration inequalities we provide a sampling scheme that gives sufficiently accurate gradient and Hessian approximations to retain the strong global and local convergence guarantees of cubically regularized methods. To the best of our knowledge this is the first work that gives global convergence guarantees for a sub-sampled variant of cubic regularization on non-convex functions. Furthermore, we provide experimental results supporting our theory.