  In this paper, we propose a first second-order scheme based on arbitrary
non-Euclidean norms, incorporated by Bregman distances. They are introduced
directly in the Newton iterate with regularization parameter proportional to
the square root of the norm of the current gradient. For the basic scheme, as
applied to the composite optimization problem, we establish the global
convergence rate of the order $O(k^{-2})$ both in terms of the functional
residual and in the norm of subgradients. Our main assumption on the smooth
part of the objective is Lipschitz continuity of its Hessian. For uniformly
convex functions of degree three, we justify global linear rate, and for
strongly convex function we prove the local superlinear rate of convergence.
Our approach can be seen as a relaxation of the Cubic Regularization of the
Newton method, which preserves its convergence properties, while the auxiliary
subproblem at each iteration is simpler. We equip our method with adaptive line
search procedure for choosing the regularization parameter. We propose also an
accelerated scheme with convergence rate $O(k^{-3})$, where $k$ is the
iteration counter.
