Tensor Methods for Finding Approximate Stationary Points of Convex Functions

DOI10.1080/10556788.2020.1818082MaRDI QIDQ6322188arXivFDO

Authors Geovani Nunes Grapiglia, Yuri Nesterov

Publication date 13 July 2019

Published in arXiv

Full work available at URL https://doi.org/10.1080/10556788.2020.1818082

Mathematics Subject Classification ID

Convexity of real functions of several variables, generalizations (26B25) Convex programming (90C25) Nonlinear programming (90C30)

arXiv classification

math.OC

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

This page was built for publication: Tensor Methods for Finding Approximate Stationary Points of Convex Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322188)