On Inexact Solution of Auxiliary Problems in Tensor Methods for Convex Optimization

Abstract

In this paper we study the auxiliary problems that appear in $p$-order tensor methods for unconstrained minimization of convex functions with $\hat{I}½$-Hölder continuous $p$th derivatives. This type of auxiliary problems corresponds to the minimization of a $(p+\hat{I}½)$-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 (\hat{I}{\mu }^{-1}))$ iterations to find either a suitable approximate stationary point of the tensor model or an $\hat{I}\mu$-approximate stationary point of the original objective function.