# Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 11 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 1 of 1)

- [On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES](https://mlsanity.com/paper/2007.01996/) (2020)

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

- [Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations](https://mlsanity.com/paper/2311.02490/) (2023)

## Abstract (arXiv)

We study the asymptotic convergence of AA(m), i.e., Anderson acceleration with window size m for accelerating fixed-point methods xk+1=q(xk), xk ∈ Rn. Convergence acceleration by AA(m) has been widely observed but is not well understood. We consider the case where the fixed-point iteration function q(x) is differentiable and the convergence of the fixed-point method itself is root-linear. We identify numerically several conspicuous properties of AA(m) convergence: First, AA(m) sequences xk converge root-linearly but the root-linear convergence factor depends strongly on the initial condition. Second, the AA(m) acceleration coefficients β(k) do not converge but oscillate as xk converges to x^*. To shed light on these observations, we write the AA(m) iteration as an augmented fixed-point iteration zk+1 =Psi(zk), zk ∈ Rn(m+1) and analyze the continuity and differentiability properties of Psi(z) and β(z). We find that the vector of acceleration coefficients β(z) is not continuous at the fixed point z^*. However, we show that, despite the discontinuity of β(z), the iteration function Psi(z) is Lipschitz continuous and directionally differentiable at z^* for AA(1), and we generalize this to AA(m) with m>1 for most cases. Furthermore, we find that Psi(z) is not differentiable at z^*. We then discuss how these theoretical findings relate to the observed convergence behaviour of AA(m). The discontinuity of β(z) at z^* allows β(k) to oscillate as xk converges to x^*, and the non-differentiability of Psi(z) allows AA(m) sequences to converge with root-linear convergence factors that strongly depend on the initial condition. Additional numerical results illustrate our findings.