Gradient regularization of Newton method with Bregman distances.

Area of Science:

• Optimization Theory
• Numerical Analysis
• Machine Learning

Background:

• Convex optimization problems are fundamental in various scientific domains.
• Existing second-order methods like Cubic Newton regularization offer strong convergence guarantees but can be computationally intensive.
• There is a need for efficient optimization schemes that balance convergence rates with computational simplicity.

Purpose of the Study:

• To propose a novel second-order optimization scheme utilizing arbitrary non-Euclidean norms and Bregman distances.
• To analyze the convergence properties of the proposed method for composite convex optimization.
• To offer a computationally simpler alternative to existing methods like Cubic Newton regularization.

Main Methods:

• Development of a second-order Newton-type iteration incorporating Bregman distances.
• Regularization parameter is set proportional to the square root of the gradient norm.
• Analysis of convergence rates under assumptions of Hessian Lipschitz continuity and various convexity types (uniform, strong).

Main Results:

• Established a global convergence rate of $$ for the basic scheme in terms of functional residual and subgradient norm.
• Proved global linear convergence for uniformly convex functions of degree three and local superlinear convergence for strongly convex functions.
• Proposed an accelerated scheme with a convergence rate of $$.

Conclusions:

• The proposed method provides a relaxation of Cubic Newton regularization, preserving convergence properties while simplifying the subproblem.
• The approach demonstrates robust convergence rates across different convexity assumptions.
• The adaptive search procedure for the regularization parameter enhances practical applicability.