A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically)
For researchers and practitioners using fixed point iterations, this work provides the first rigorous theoretical justification for the long-observed empirical speedup of Anderson acceleration, resolving a decades-old open problem.
This paper provides the first proof that Anderson acceleration improves the convergence rate of general fixed point iterations, showing a first-order improvement by a factor of the gain at each step, and also increases the radius of convergence. The analysis reveals that while linear convergence is improved, additional quadratic terms explain why AA does not typically benefit quadratically converging methods.
This paper provides the first proof that Anderson acceleration (AA) improves the convergence rate of general fixed point iterations. AA has been used for decades to speed up nonlinear solvers in many applications, however a rigorous mathematical justification of the improved convergence rate has remained lacking. The key ideas of the analysis presented here are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed point iteration. The main result we prove is that AA improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step. In addition to improving the convergence rate, our results indicate that AA increases the radius of convergence. Lastly, our estimate shows that while the linear convergence rate is improved, additional quadratic terms arise in the estimate, which shows why AA does not typically improve convergence in quadratically converging fixed point iterations. Results of several numerical tests are given which illustrate the theory.