In this paper we consider the problem of finding \epsilon-approximate stationary points of convex functions that are p-times differentiable with \nu-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(\epsilon^{-1/(p+\nu-1)}) iterations to reduce the norm of the gradient of the objective below a given \epsilon\in (0,1). For accelerated tensor schemes we establish improved complexity bounds of O(\epsilon^{-(p+\nu)/[(p+\nu-1)(p+\nu+1)]}) and O(|\log(\epsilon)|\epsilon^{-1/(p+\nu)}), when the Hölder parameter \nu\in [0,1] is known. For the case in which \nu is unknown, we obtain a bound of O(\epsilon^{-(p+1)/[(p+\nu-1)(p+2)]}) for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of O(\epsilon^{-2/[3(p+\nu)-2]}) for finding \epsilon-approximate stationary points using p-order tensor methods.
Citation
Optimization Methods and Software (2020), DOI: 10.1080/10556788.2020.1818082
Article
View Tensor Methods for Finding Approximate Stationary Points of Convex Functions