  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.
