Tensor Methods for Minimizing Convex Functions with H\"{o}lder Continuous Higher-Order Derivatives

In this paper we study $p$-order methods for unconstrained minimization of convex functions that are $p$-times differentiable ($p\ge 2$) with $\nu$-H"{o}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({ϵ}^{-1\mathrm{/}(p+\nu -1)}\right)$ for reducing the functional residual below a given $ϵ\in (0,1)$. Assuming that $\nu$ is known, we obtain an improved complexity bound of $\mathcal{O}\left({ϵ}^{-1\mathrm{/}(p+\nu )}\right)$ for the corresponding accelerated scheme. For the case in which $\nu$ is unknown, we present a universal accelerated tensor scheme with iteration complexity of $\mathcal{O}\left({ϵ}^{-p\mathrm{/}[(p+1)(p+\nu -1)]}\right)$. A lower complexity bound of $\mathcal{O}\left({ϵ}^{-2\mathrm{/}[3(p+\nu )-2]}\right)$ is also obtained for this problem class.