On inexact solution of auxiliary problems in tensor methods for convex optimization. (2nd January 2021) - Grapiglia, G.N.; Nesterov, Yu.
ABSTRACT: In this paper, we study the auxiliary problems that appear in p -order tensor methods for unconstrained minimization of convex functions with ν -Hölder continuous p th derivatives. This type of auxiliary problems corresponds to the minimization of a ( p + ν ) -order regularization of the p th-order Taylor approximation of the objective. For the case p = 3, we consider the use of Gradient Methods with Bregman distance. When the regularization parameter is sufficiently large, we prove that the referred methods take at most O ( log ⁡ ( ϵ − 1 ) ) iterations to find either a suitable approximate stationary point of the tensor model or an ε -approximate stationary point of the original objective function.