Super-Universal Regularized Newton Method

  • 2022-08-11 16:44:56
  • Nikita Doikov, Konstantin Mishchenko, Yurii Nesterov
  • 5

Abstract

We analyze the performance of a variant of Newton method with quadraticregularization for solving composite convex minimization problems. At each stepof our method, we choose regularization parameter proportional to a certainpower of the gradient norm at the current point. We introduce a family ofproblem classes characterized by H\"older continuity of either the second orthird derivative. Then we present the method with a simple adaptive searchprocedure allowing an automatic adjustment to the problem class with the bestglobal complexity bounds, without knowing specific parameters of the problem.In particular, for the class of functions with Lipschitz continuous thirdderivative, we get the global $O(1/k^3)$ rate, which was previously attributedto third-order tensor methods. When the objective function is uniformly convex,we justify an automatic acceleration of our scheme, resulting in a fasterglobal rate and local superlinear convergence. The switching between thedifferent rates (sublinear, linear, and superlinear) is automatic. Again, forthat, no a priori knowledge of parameters is needed.

 

Quick Read (beta)

loading the full paper ...