When Windowed Anderson Acceleration Converges Faster
Abstract
Windowed Anderson acceleration AA(m) combines at most m+1 recent iterates by least squares. For a real affine contraction x↦ Wx+b with q=|W| ∈(0,1), we determine exactly when AA(m) converges from every starting point with an asymptotic factor below q. We give a polynomial criterion for this improvement and an equivalent spectral condition: there is no probability distribution on the phases of the eigenvalues of modulus q whose first m cosine moments are q,q2,…,qm. If such a distribution exists, we construct a starting point from which AA(m) reproduces fixed-point iteration at every step. Otherwise, over a fixed number of consecutive steps, every run contracts the residual norm by a common factor strictly smaller than the corresponding power of q. The polynomial criterion also gives explicit convergence-rate bounds with constants independent of the dimension. When q equals the spectral radius, this characterizes improvement over the asymptotic convergence factor of fixed-point iteration. For general affine contractions, the asymptotic factor never exceeds the numerical radius of W, and a related moment condition gives a uniform upper bound strictly below that radius.
Related
- An Equivalence result for sketched Anderson Acceleration and sketched GMRES
- A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- On a blended Anderson / NGMRES acceleration for the Navier-Stokes Picard iteration: convergence analysis and adaptive depth selection
- A Column-Wise Reflection Method with Safeguarded Anderson Acceleration for the Continuous Sylvester Matrix Equation
BibTeX
@misc{lerman2026when,
title = {{When Windowed Anderson Acceleration Converges Faster}},
author = {Gilad Lerman and Teng Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30073},
eprint = {2610.30073},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30073},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When Windowed Anderson Acceleration Converges Faster
AU - Gilad Lerman
AU - Teng Zhang
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30073
UR - https://arxiv.org/abs/2610.30073
AB - Windowed Anderson acceleration AA(m) combines at most m+1 recent iterates by least squares. For a real affine contraction x↦ Wx+b with q=|W| ∈(0,1), we determine exactly when AA(m) converges from every starting point with an asymptotic factor below q. We give a polynomial criterion for this improvement and an equivalent spectral condition: there is no probability distribution on the phases of the eigenvalues of modulus q whose first m cosine moments are q,q^2,…,q^m. If such a distribution exists, we construct a starting point from which AA(m) reproduces fixed-point iteration at every step. Otherwise, over a fixed number of consecutive steps, every run contracts the residual norm by a common factor strictly smaller than the corresponding power of q. The polynomial criterion also gives explicit convergence-rate bounds with constants independent of the dimension. When q equals the spectral radius, this characterizes improvement over the asymptotic convergence factor of fixed-point iteration. For general affine contractions, the asymptotic factor never exceeds the numerical radius of W, and a related moment condition gives a uniform upper bound strictly below that radius.
ER -