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.
When the nonsmooth term @math exists, @math has @math -Lipschitz Hessian and @math is convex, by @cite_6 , APCNM can find an @math -accurate solution with @math iterations. Meanwhile by extending the result of the smooth setting trivially @cite_15 , we can know that PCNM can find an @math -accurate solution for with @math iterations. Except @cite_6 , the existing researches of inexact variants of CNM mainly focus on the smooth setting where the nonsmooth term @math does not exist.
@cite_15 @cite_6
2009941369 2792215433
In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique. In this paper, we study accelerated regularized Newton methods for minimizing objectives formed as a sum of two functions: one is convex and twice differentiable with Holder-continuous Hessian, and...