Nonlinear Acceleration of Momentum and Primal-Dual Algorithms

DOI10.1007/S10107-022-01775-XMaRDI QIDQ6307997arXivFDO

Authors Raghu Bollapragada, Damien Scieur, Alexandre d'Aspremont

Publication date 10 October 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10107-022-01775-X

Mathematics Subject Classification ID

Nonlinear programming (90C30)

arXiv classification

math.OC

Abstract: We describe convergence acceleration schemes for multistep optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the original optimization method. Our analysis does not need the underlying fixed-point operator to be symmetric, hence handles e.g. algorithms with momentum terms such as Nesterov's accelerated method, or primal-dual methods. The weights are computed via a simple linear system and we analyze performance in both online and offline modes. We use Crouzeix's conjecture to show that acceleration performance is controlled by the solution of a Chebyshev problem on the numerical range of a non-symmetric operator modeling the behavior of iterates near the optimum. Numerical experiments are detailed on logistic regression problems.

This page was built for publication: Nonlinear Acceleration of Momentum and Primal-Dual Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6307997)