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) - Marques Alves, M.
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.