Tensor methods for finding approximate stationary points of convex functions. (4th March 2022)

• Record Type: Journal Article
• Authors: Grapiglia, G. N.; Nesterov, Yurii
• Is Part Of: Optimization methods and software. Volume 37:Number 2(2022)
• Page Start: 605
• Page End: 638
• Publication Date: 2022-03-04
• Subjects: Unconstrained minimization -- high-order methods -- tensor methods -- Hölder condition -- worst-case complexity; 49M15 -- 49M37 -- 58C15 -- 90C25 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1818082
• Languages: English
• ISSNs: 1055-6788

Abstract

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.