Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations

2023/11/04 by Casey Garner, Gilad Lerman, Garner, Casey +3
Computer Science · Mathematics · #Matrix Theory and Algorithms #Numerical methods for differential equations #Iterative Methods for Nonlinear Equations

paper · pdf · doi:10.48550/arxiv.2311.02490

Abstract

This paper studies the commonly utilized windowed Anderson acceleration (AA) algorithm for fixed-point methods, x^(k+1)=q(x^(k)). It provides the first proof that when the operator q is linear and symmetric the windowed AA, which uses a sliding window of prior iterates, improves the root-linear convergence factor over the fixed-point iterations. When q is nonlinear, yet has a symmetric Jacobian at a fixed point, a slightly modified AA algorithm is proved to have an analogous root-linear convergence factor improvement over fixed-point iterations. Simulations verify our observations. Furthermore, experiments with different data models demonstrate AA is significantly superior to the standard fixed-point methods for Tyler's M-estimation.

Related

• A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically)
• Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis
• Anderson Acceleration for Fixed-Point Iterations
• Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis
• Asymptotic convergence of restarted Anderson acceleration for certain normal linear systems