Anderson acceleration fails under certain staleness in async computing

A new paper from Evan Coleman and Masha Sosonkina explores how asynchronous iterative methods handle stragglers in distributed computing. Using Ray, they tested three fixed-point algorithms: Jacobi for sparse linear systems, value iteration for Bellman equations, and Hartree-Fock SCF iterations. Results show universal speedups: 2.9x, 7.7x, and 16.9x respectively when a worker is delayed 100ms. However, they found that Anderson acceleration, a popular convergence accelerator, only works under one type of staleness mechanism.

The key insight: When stale worker outputs directly overwrite parts of the accelerated iterate (iterate-level corruption, as in block Jacobi), Anderson acceleration fails completely. But when staleness acts as a bounded perturbation to the fixed-point map evaluation (evaluation-level perturbation, as in VI and SCF), Anderson acceleration retains its benefits. This distinction, not contraction norms or smoothness, determines whether acceleration survives asynchrony. Practical implication: designers of distributed optimization and reinforcement learning systems must match their staleness model to acceleration strategies.