Tensor Methods for Finding Approximate Stationary Points of Convex Functions

Abstract

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

arXiv admin note: text overlap with arXiv:1904.12559