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

Geovani Grapiglia(grapigliaufpr.br)
Yurii Nesterov(yurii.nesterovuclouvain.be)

Abstract: In this paper we study the auxiliary problems that appear in p-order tensor methods for unconstrained minimization of convex functions with \nu-Holder continuous pth derivatives. This type of auxiliary problems corresponds to the minimization of a (p+\nu)-order regularization of the pth order Taylor approximation of the objective. For the case p=3, we consider the use of a Gradient Methods with Bregman distance. When the regularization parameter is sufficiently large, we prove that the referred methods take at most O(log(eps^{-1})) iterations to find either a suitable approximate stationary point of the tensor model or an eps-approximate stationary point of the original objective function.

Keywords: unconstrained minimization, high-order methods, tensor methods, Holder condition, worst-case global complexity bounds

Category 1: Convex and Nonsmooth Optimization

Citation:

Download: [PDF]

Entry Submitted: 07/30/2019
Entry Accepted: 07/30/2019
Entry Last Modified: 07/30/2019

Modify/Update this entry