Tensor methods for minimizing convex functions with Hö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 ≥ 2) with n-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 O(e-1/(p+n-1))$ for reducing the functional residual below a given e Î\in (0,1). Assuming that n is known, we obtain an improved complexity bound of O(e-1/(p+n))$ for the corresponding accelerated scheme. For the case in which n is unknown, we present a universal accelerated tensor scheme with iteration complexity of O(e-p/[(p+1)(p+n-1)]). A lower complexity bound of O(e-2/[3(p+n)-2]) is also obtained for this problem class.