Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods. (2nd November 2022)

• Record Type: Journal Article
• Authors: Marques Alves, M.
• Is Part Of: Optimization methods and software. Volume 37:Number 6(2022)
• Page Start: 2021
• Page End: 2051
• Publication Date: 2022-11-02
• Subjects: Convex optimization -- strongly convex -- accelerated methods -- proximal-point algorithm -- large-step -- high-order tensor methods -- superlinear convergence -- proximal-Newton method; 90C60 -- 90C25 -- 47H05 -- 65K10; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.2022148
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : For solving strongly convex optimization problems, we propose and study the global convergence of variants of the accelerated hybrid proximal extragradient (A-HPE) and large-step A-HPE algorithms of R.D.C. Monteiro and B.F. Svaiter [An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM J. Optim. 23 (2013), pp. 1092–1125.]. We prove linear and the superlinear O ( k − k ( p − 1 p + 1 ) ) global rates for the proposed variants of the A-HPE and large-step A-HPE methods, respectively. The parameter p ≥ 2 appears in the (high-order) large-step condition of the new large-step A-HPE algorithm. We apply our results to high-order tensor methods, obtaining a new inexact (relative-error) tensor method for (smooth) strongly convex optimization with iteration-complexity O ( k − k ( p − 1 p + 1 ) ) . In particular, for p = 2, we obtain an inexact proximal-Newton algorithm with fast global O ( k − k / 3 ) convergence rate.