PaperlayerView exact revision on arXiv

Source-linked AI summary

A proof that Anderson acceleration improves the convergence rate in linearly converging fixed point methods (but not in those converging quadratically)

Claire Evans, Sara Pollock, Leo G. Rebholz, Mengying Xiao

arXiv:1810.08455v2math.NAcs.NA

TL;DR

Anderson acceleration has long been used to speed fixed-point iterations, but prior convergence theory had not shown that it improves their rate. This paper analyzes the method using residual relationships and an explicit optimization-stage gain, proving a gain-dependent first-order improvement for linearly converging iterations. The analysis also indicates convergence-radius expansion and explains why quadratic convergence is typically not accelerated.

  • Problem

    Prior convergence results showed local convergence for Anderson-accelerated iterations but did not prove an improved convergence rate over the underlying fixed-point iteration.

    Source: §1 · p. 2

  • Method

    The analysis relates consecutive-iterate differences to residuals and defines the optimization-stage gain as the ratio of its objective to that of an unaccelerated step.

    Source: §1 · p. 2, §3.2 · p. 7

  • Results

    For linearly converging fixed-point iterations, the rate at step k is θk((1 − βk−1) + βk−1κ), with 0 < βk−1 ≤ 1.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis indicates that AA can extend the radius of convergence, while its additional quadratic error terms mean it typically slightly slows quadratically converging methods.

    Source: §1 · p. 2, §6 · p. 21

    Increasing depth can make computational costs significant, and the tests found little improvement past m = 3.

    Source: §4 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The introduction identifies a gap between Anderson acceleration’s observed speedups and the available convergence theory. The paper proves a gain-dependent improvement for linearly converging fixed-point iterations and discusses quadratic-error and convergence-radius effects.

1 Introduction

  • Anderson acceleration uses a history of search directions and has been applied across many nonlinear-solver settings.The introduction cites applications including electronic structure, geometry optimization, flow problems, radiation diffusion, molecular interaction, and machine learning.Source: §1 · pp. 1–2
  • Earlier theory established local convergence but did not prove that Anderson acceleration improves the underlying fixed-point iteration’s convergence rate.The paper addresses the gap between those results and practitioners’ observed speedups and robustness.Source: §1 · p. 2
  • For general C2 fixed-point functions converging linearly at rate κ, the new rate at step k is θk((1 − βk−1) + βk−1κ), with 0 < βk−1 ≤ 1.The undamped iteration corresponds to βk−1 = 1; θk is the optimization-stage gain.Source: §1 · p. 2
  • The analysis adds quadratic error terms, consistent with AA typically not accelerating quadratically converging methods, and indicates AA and damping can extend the radius of convergence.The paper says the iteration may converge outside the domain where the fixed-point function is contractive.Source: §1 · p. 2

2 Anderson acceleration

The section sets up Anderson iteration on a Hilbert space and describes its history-based update. Its optimization gain is linked to how effectively the method reduces residuals.

2 Anderson acceleration

  • Anderson iteration applies a fixed-point operator g:X→X on a Hilbert space and uses depth m with damping factors 0 < βk ≤ 1.The algorithm begins with x0, takes an initial fixed-point step, and then uses the depth-limited iteration.Source: §2 · pp. 2–3
  • The method defines stage-k residual and error terms as wk := ˜xk − xk−1 and ek := xk − xk−1.These quantities provide the residual and consecutive-iterate differences used in the analysis.Source: §2 · p. 3
  • AA combines a history of steps using optimization coefficients, and the optimization’s success in reducing the residual is coupled to its stage gain θk.The gain characterizes the improvement in the fixed-point iteration’s contraction rate.Source: §2 · p. 3

3 Technical preliminaries

The technical preliminaries establish assumptions and tools for the convergence analysis. They expand the accelerated residual, bound iterate differences using residuals, and interpret the optimization gain geometrically.

3 Technical preliminaries

  • The preliminaries use a Hilbert-space setting; residual expansion requires g to be twice continuously differentiable, while the iterate-difference bounds assume it is contractive.Under the contractive assumption, residual convergence suffices to establish convergence of the fixed-point error.Source: §3 · p. 4

3.1 Expansion of the residual

  • Taylor expansions express the accelerated residual in terms of consecutive-iterate differences and higher-order terms.The resulting expansion is used to bound higher-order terms and establish accelerated convergence estimates.Source: §3.1 · pp. 5–6

3.2 Relating the difference of consecutive iterates to residuals

  • Under contractivity, the section derives bounds relating consecutive-iterate differences to residuals, extending estimates across greater Anderson depths.The general-depth estimates use two forms of the optimization problem; their leading coefficients are assumed bounded away from zero.Source: §3.2 · pp. 6–7

3.3 Explicit computation of the optimization gain

  • The optimization uses columns formed from consecutive residual differences, and θk is interpreted geometrically as a direction-sine.In the Hilbert-space setting, the gain can be computed from the least-squares residual associated with those columns.Source: §3.3 · p. 10

4 Convergence rates for depths m = 1 and m = 2

The analysis establishes residual convergence bounds for Anderson acceleration at depths 1, 2, and general depth under stated assumptions. It also indicates that damping and a sufficiently small optimization gain can support convergence from a larger effective domain.

4 Convergence rates for depths m = 1 and m = 2

  • At depth m = 1, the theorem establishes a residual bound under Assumptions 3.1 and 3.2 when the relevant optimization coefficients remain bounded and bounded away from zero.The proof combines the residual expansion with bounds for the depth-one case.Source: §4 · p. 11
  • Coefficient boundedness assumptions could be avoided with constrained optimization, which enforces bounded parameters but yields a modified gain θ̂k satisfying θk ≤ θ̂k ≤ 1.The coefficient assumptions are described as similar to those of.Source: §4 · p. 11
  • Even without global contractivity, sufficiently small error terms may contract when the search direction is favorable and the gain is sufficiently below one, particularly with damping.This supports the paper's observation that Anderson acceleration can enlarge the effective convergence domain.Source: §4 · p. 11
  • At depth m = 2, a corresponding residual bound holds under Assumptions 3.1 and 3.2 when the specified coefficients remain bounded away from zero.The proof combines the residual expansion with the depth-two bounds.Source: §4 · p. 12
  • For general depth m, the paper states a residual bound under Assumptions 3.1 and 3.2 when the specified coefficient remains bounded away from zero.The result is extrapolated from the preceding analysis.Source: §4 · pp. 12–13
  • Greater depth can improve the optimization gain despite accumulating higher-order terms, but its computational cost and solver accuracy matter; tests find little improvement past m = 3.The practical benefit of increasing depth must be weighed against those costs.Source: §4 · p. 13

5 Numerical tests

The numerical tests illustrate that Anderson acceleration speeds linear convergence, can slow quadratic convergence, and can increase the convergence radius. Damping tests show how damping can aid convergence in a difficult quasilinear problem.

5.1 Simple illustrative tests for the scalar case

  • In scalar tests, acceleration makes linear convergence superlinear, slightly worsens quadratic convergence, and expands the convergence radius for a noncontractive iteration.For the noncontractive example, the unaccelerated iteration grows exponentially, while the accelerated iteration converges from x0 = 4.Source: §5.1 · p. 14

5.2 Numerical tests for steady incompressible Navier-Stokes equation

  • At Re = 2500, m = 3 Picard reaches about O(10^-9) residual in 40 iterations; at Re = 6000, accelerated Newton converges only at m = 3.At Re = 2500, usual Newton diverges while accelerated Newton converges; at Re = 6000, m = 3 reaches O(10^-14) in 23 iterations.Source: Figure 3 · p. 17, §5.2 · p. 17, Figure 4 · p. 18
  • With m = 1, Picard converges through Re = 10000; increasing m to 2 or 3 provides additional gain.The table counts iterations to reach a nonlinear residual tolerance of 10^-8 in the H1 norm; failures mean not converging within 500 iterations.Source: §5.2 · p. 18, Table 1 · p. 19

5.3 Damping tests with a quasilinear equation

  • In the quasilinear example’s m = 0 plot, fixed-point iteration fails to converge to tolerance 10^-5 for β = 1, 0.8, and 0.6, though damping attains more accuracy.At the beginning of the calculation, when the operator is contractive, damping has the predicted linear effect on convergence rate.Source: §5.3 · p. 20, Figure 6 · p. 20
  • At depths m = 4, 6, and 8, the quasilinear tests converge with or without damping, generally performing better with some damping.The adaptive strategy uses the gain θ_k to design damping intended to stabilize convergence without extensive experimentation or additional computation.Source: §5.3 · pp. 20–21, Figure 7 · p. 21

6 Conclusion

Anderson acceleration improves the first-order convergence rate of fixed-point iterations, with the improvement depending on optimization gain and accompanied by quadratic error terms. The analysis also indicates increased convergence radius with greater depth and damping.

6 Conclusion

  • The first-order convergence-rate improvement depends on optimization-stage gain, while additional quadratic error terms also arise.The rate increases when the optimization gain dominates those terms.Source: §6 · p. 21
  • For linearly convergent fixed-point methods, an improved rate is expected; for quadratically convergent methods, convergence will typically be slightly slowed.Source: §6 · p. 21
  • Increasing depth and using damping are justified as ways to increase the method’s radius of convergence.Numerical tests illustrate the theory.Source: §6 · p. 21
Loading 1810.08455v2…