In this paper, we study the iteration complexity of cubic regularization of
Newton method for solving composite minimization problems with uniformly convex
objective. We introduce the notion of second-order condition number of a
certain degree and justify the linear rate of convergence in a nondegenerate
case for the method with an adaptive estimate of the regularization parameter.
The algorithm automatically achieves the best possible global complexity bound
among different problem classes of uniformly convex objective functions with
H\"older continuous Hessian of the smooth part of the objective. As a byproduct
of our developments, we justify an intuitively plausible result that the global
iteration complexity of the Newton method is always better than that of the
gradient method on the class of strongly convex functions with uniformly
bounded second derivative.

本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后，我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品，我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。