pipette
ESEspañol

When Windowed Anderson Acceleration Converges Faster

Gilad Lerman, Teng Zhang

Preprint

In the authors' words

Windowed Anderson acceleration AA() combines at most recent iterates by least squares. For a real affine contraction with , we determine exactly when AA() converges from every starting point with an asymptotic factor below . 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 whose first cosine moments are . If such a distribution exists, we construct a starting point from which AA() 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 . The polynomial criterion also gives explicit convergence-rate bounds with constants independent of the dimension. When 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 , and a related moment condition gives a uniform upper bound strictly below that radius.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.