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 ν-Hölder continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most $$ iterations to reduce the norm of the gradient of the objective below given $$ . For accelerated tensor schemes, we establish improved complexity bounds of $$ and $$ , when the Hölder parameter $$ is known. For the case in which ν is unknown, we obtain a bound of $$ for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of $$ for finding ε-approximate stationary points using p-order tensor methods.