Gradient Regularization of Newton Method with Bregman Distances

Understand

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.