Tensor Methods for Finding Approximate Stationary Points of Convex Functions

In this paper we consider the problem of finding ε-approximate stationary points of convex functions that are p-times differentiable with nu-H"older continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most Oleft(ε-1/(p+nu-1)right) iterations to reduce the norm of the gradient of the objective below a given ε∈ (0,1). For accelerated tensor schemes we establish improved complexity bounds of Oleft(ε-(p+nu)/[(p+nu-1)(p+nu+1)]right) and Oleft(|log(ε)|ε-1/(p+nu)right), when the H"older parameter nu∈ [0,1] is known. For the case in which nu is unknown, we obtain a bound of Oleft(ε-(p+1)/[(p+nu-1)(p+2)]right) for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of Oleft(ε-2/[3(p+nu)-2]right) for finding ε-approximate stationary points using p-order tensor methods.