Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods

2021/02/03 by Alves, M. Marques · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2102.02045

Abstract

For solving strongly convex optimization problems, we propose and study the global convergence of variants of the A-HPE and large-step A-HPE algorithms of Monteiro and Svaiter. 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, obtaning 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 Newton-proximal algorithm with fast global O(k ^-k/3) convergence rate.

Cited by

• Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency

Related

• An Optimal High-Order Tensor Method for Convex Optimization
• OPTAMI: Global Superlinear Convergence of High-order Methods
• HNAG++: A Super-Fast Accelerated Gradient Method for Strongly Convex Optimization
• High-order methods beyond the classical complexity bounds, I: inexact high-order proximal-point methods
• Convergence of a greedy algorithm for high-dimensional convex nonlinear\n problems