In this paper, we use Proximal Cubic regularized Newton Methods (PCNM) to optimize the sum of a smooth convex function and a non-smooth convex function, where we use inexact gradient and Hessian, and an inexact subsolver for the cubic regularized second-order subproblem. We propose inexact variants of PCNM and accelerated PCNM respectively, and show that both variants can achieve the same convergence rate as in the exact case, provided that the errors in the inexact gradient, Hessian and subsolver decrease at appropriate rates. Meanwhile, in the online stochastic setting where data comes endlessly, we give the overall complexity of the proposed algorithms and show that they are as competitive as the stochastic gradient descent. Moreover, we give the overall complexity of the proposed algorithms in the finite-sum setting and show that it is as competitive as the state of the art variance reduced algorithms. Finally, we propose an efficient algorithm for the cubic regularized second-order subproblem, which can converge to an enough small neighborhood of the optimal solution in a superlinear rate.
In the nonconvex setting, in order to reduce the high computational cost in optimizing the subproblem and maintain the convergence rate of the exact case at the same time, @cite_9 @cite_7 @cite_19 considered a subsampling strategy to obtain inexact gradient and Hessian, and a termination condition for optimizing , while the conditions of subsampling depend on the further iteration and thus is implementable, and the termination condition is specific to the Lanzcos method @cite_22 . @cite_11 used variance reduction strategy to reduce the complexity of computing the gradient and Hessian, while the complexity to update the variance reduced gradient and Hessian is @math and thus the SVRC method in @cite_11 is only suitable for the problem with small dimension @math . @cite_16 made a considerable progress that the stochastic cubic regularization method in @cite_16 needs @math stochastic gradient and stochastic Hessian-vector product evaluations to find an approximate local minima for general smooth, nonconvex functions, which matches the best known result, while it did not give the analysis of the convex setting. -0.1in
@cite_22 @cite_7 @cite_9 @cite_19 @cite_16 @cite_11
2950418232 1994974865 2156005216 2614389101 2962876518 2787156640
We provide convergence rates for Krylov subspace solutions to the trust-region and cubic-regularized (nonconvex) quadratic problems. Such solutions may be efficiently computed by the Lanczos method and have long been used in practice. We prove error bounds of the form @math and @math , where @math is a condition number for the problem, and @math is the Krylov subspace order (number of Lanczos iterations). We also provide lower bounds showing that our analysis is sharp. An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007 s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA 12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413–431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most @math iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy @math , and @math iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians. An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA 12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by (Optim Methods Softw 22(3):413–431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective function is determined, and this ensures a significant improvement in the objective so long as the Hessian of the objective is locally Lipschitz continuous. The new method uses an adaptive estimation of the local Lipschitz constant and approximations to the global model-minimizer which remain computationally-viable even for large-scale problems. We show that the excellent global and local convergence properties obtained by Nesterov and Polyak are retained, and sometimes extended to a wider class of problems, by our ARC approach. Preliminary numerical experiments with small-scale test problems from the CUTEr set show encouraging performance of the ARC algorithm when compared to a basic trust-region implementation. 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. This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only ˜ O (ϵ−3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the ˜ O (ϵ−4) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques. We propose a stochastic variance-reduced cubic regularized Newton method for non-convex optimization. At the core of our algorithm is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. We show that our algorithm is guaranteed to converge to an @math -approximately local minimum within @math second-order oracle calls, which outperforms the state-of-the-art cubic regularization algorithms including subsampled cubic regularization. Our work also sheds light on the application of variance reduction technique to high-order non-convex optimization methods. Thorough experiments on various non-convex optimization problems support our theory.