TENSOR METHODS FOR MINIMIZING CONVEX FUNCTIONS WITH HOLDER 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-Holder continuous pth derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of O (epsilon(-1/(p+nu-1))) for reducing the functional residual below a given epsilon is an element of (0, 1). Assuming that nu is known, we obtain an improved complexity bound of O (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 O (epsilon(-P/[(P+1)(P+nu-1)])). A lower complexity bound of O (epsilon(-2/[3(P+nu)-2])) is also obtained for this problem class.