Abstract
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 O(ϵ-1/(p+ν-1)) iterations to reduce the norm of the gradient of the objective below given ϵ ∈ (0, 1) . For accelerated tensor schemes, we establish improved complexity bounds of O(ϵ-(p+ν)/[(p+ν-1)(p+ν+1)]) and O(|log(ϵ)|ϵ-1/(p+ν)) , when the Hölder parameter ν ∈ [0, 1] is known. For the case in which ν is unknown, we obtain a bound of O(ϵ-(p+1)/[(p+ν-1)(p+2)]) for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of O(ϵ-2/[3(p+ν)-2]) for finding ε-approximate stationary points using p-order tensor methods.