Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives

Abstract

In this paper we study $p$-order methods for unconstrained minimization of convex functions that are $p$-times differentiable ($p\ge 2$) with $\hat{I}½$-Hölder continuous $p$th derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of $\mathcal{O}\left(\hat{I}{\mu }^{-1/(p+\hat{I}½-1)}\right)$ for reducing the functional residual below a given $\hat{I}\mu \in (0,1)$. Assuming that $\hat{I}½$ is known, we obtain an improved complexity bound of $\mathcal{O}\left(\hat{I}{\mu }^{-1/(p+\hat{I}½)}\right)$ for the corresponding accelerated scheme. For the case in which $\hat{I}½$ is unknown, we present a universal accelerated tensor scheme with iteration complexity of $\mathcal{O}\left(\hat{I}{\mu }^{-p/[(p+1)(p+\hat{I}½-1)]}\right)$. A lower complexity bound of $\mathcal{O}\left(\hat{I}{\mu }^{-2/[3(p+\hat{I}½)-2]}\right)$ is also obtained for this problem class.

arXiv admin note: text overlap with arXiv:1907.07053