Tensor methods for finding approximate stationary points of convex functions. (4th March 2022) - Grapiglia, G. N.; Nesterov, Yurii
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 p th 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.