Tensor Methods for Minimizing Convex Functions with H"older 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 nu-H"older continuous pth derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of Oleft(ε-1/(p+nu-1)right) for reducing the functional residual below a given ε∈ (0,1). Assuming that nu is known, we obtain an improved complexity bound of Oleft(ε-1/(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 Oleft(ε-p/[(p+1)(p+nu-1)]right). A lower complexity bound of Oleft(ε-2/[3(p+nu)-2]right) is also obtained for this problem class.