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 n-Hölder continuous pth derivatives. This type of auxiliary problems corresponds to the minimization of a (p+n)-order regularization of the pth 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(e-1)) iterations to find either a suitable approximate stationary point of the tensor model or an e-approximate stationary point of the original objective function.