On inexact solution of auxiliary problems in tensor methods for convex optimization
G.N. Grapiglia, Yu. Nesterov · Optimization methods & software · 2020
In this paper we study the auxiliary problems that appear in $p$-order tensor methods for unconstrained minimization of convex functions with $ u$-H\"{o}lder continuous $p$th derivatives. This type of auxiliary problems corresponds to the minimization of a $(p+ u)$-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 $\mathcal{O}(\log(\epsilon^{-1}))$ iterations to find either a suitable approximate stationary point of the tensor model or an $\epsilon$-approximate stationary point of the original objective function.