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: Optimization Methods and Software 36, 145-170 (2021)

Download: [PDF]

Entry Submitted: 07/30/2019
Entry Accepted: 07/30/2019
Entry Last Modified: 05/21/2021

Modify/Update this entry