Tensor methods for finding approximate stationary points of convex functions

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