Tensor Methods for Finding Approximate Stationary Points of Convex Functions

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

Abstract: In this paper we consider the problem of finding \epsilon-approximate stationary points of convex functions that are p-times differentiable with \nu-Hölder continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most O(\epsilon^{-1/(p+\nu-1)}) iterations to reduce the norm of the gradient of the objective below a given \epsilon\in (0,1). For accelerated tensor schemes we establish improved complexity bounds of O(\epsilon^{-(p+\nu)/[(p+\nu-1)(p+\nu+1)]}) and O(|\log(\epsilon)|\epsilon^{-1/(p+\nu)}), when the Hölder parameter \nu\in [0,1] is known. For the case in which \nu is unknown, we obtain a bound of O(\epsilon^{-(p+1)/[(p+\nu-1)(p+2)]}) for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of O(\epsilon^{-2/[3(p+\nu)-2]}) for finding \epsilon-approximate stationary points using p-order tensor methods.

Keywords: unconstrained minimization, high-order methods, tensor methods, Hölder condition, worst-case complexity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Optimization Methods and Software (2020), DOI: 10.1080/10556788.2020.1818082

Download: [PDF]

Entry Submitted: 07/13/2019
Entry Accepted: 07/13/2019
Entry Last Modified: 05/22/2021

Modify/Update this entry