# Nonlinear Acceleration of Momentum and Primal-Dual Algorithms

arXiv: https://arxiv.org/abs/1810.04539 · HTML: https://mlsanity.com/paper/1810.04539/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2018.

## Built on by (most cited first, 4 of 4)

- [AdaSAM: Boosting Sharpness-Aware Minimization with Adaptive Learning Rate and Momentum for Training Deep Neural Networks](https://mlsanity.com/paper/2303.00565/) (2023)
- [Riemannian accelerated gradient methods via extrapolation](https://mlsanity.com/paper/2208.06619/) (2022)
- [Enhancing Electrical Impedance Tomography reconstruction using Learned Half-Quadratic Splitting Networks with Anderson Acceleration](https://mlsanity.com/paper/2304.14491/) (2023)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)

## Abstract (arXiv)

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.