Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives

Nunes Grapiglia, Geovani [UCL] Nesterov, Yurii [UCL]

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