implementation

AndersonSchedule(inner; m = 3) (anderson.jl): Anderson acceleration of any static schedule. A sweep of inner is a map on the stored messages; the accelerated sweep replaces by the combination of the last images that best cancels their residuals . Same fixed points as inner, one sweep of inner per sweep, no convergence guarantee.

Sources: Walker & Ni, Anderson Acceleration for Fixed-Point Iterations, SIAM J. Numer. Anal.

Bibliography: Walker & Ni 2011 49(4), 2011 (the update used here, and its relation to GMRES on linear problems). code: anderson.jl, bench/bp_anderson.jl; vault: Composing Optimisers §4.3.

Theory

Write the stored messages as one vector and one sweep as , with residual . With the last iterates, let and hold the differences of consecutive residuals and images. Anderson (type II, undamped) steps to

At a fixed point , so and : the fixed points are ‘s. On a linear map with unlimited memory it is essentially GMRES on (Walker & Ni), which is why a short memory can cancel a Jacobian with few distinct eigenvalues; with a finite memory and off the linear regime nothing is guaranteed.

Implementation

  • What is mixed. Every stored Gaussian message in host Float64 arrays, in natural parameters: and the lower triangle of . If any stored message is of another kind (categorical, particles, a mixture, a device array, dual numbers) the sweep is inner’s unchanged. Messages not yet sent are left out; when the set of stored messages changes (a cold start, a message that appears) the memory is cleared.
  • Scaling. The least squares are taken in coordinates scaled by the largest and the largest , fixed when the memory starts, so that the precisions (about on the divider, the means about 1) do not decide the fit alone. Unscaled mixing was not measured.
  • Ridge. solves with by default: near convergence the columns of are nearly dependent.
  • Restarts. A step that is not finite, or would make a precision lose positive semidefiniteness (its smallest eigenvalue below of ‘s minus a rounding margin), is replaced by and the memory cleared. anderson_restarts(sched, store) counts them. The improper flag of each message is kept.
  • Memory per store. The history lives in a WeakKeyDict keyed by the MessageStore, so the schedule is reusable across stores (each infer! starts afresh) and a dropped store frees it.
  • Residual. sweep! returns inner’s residual, the distance from the stored messages to their images, which is the fixed-point residual in belief_distance. So propagate!’s tol means what it means for inner, and the default criterion is inner’s.
  • ResidualSchedule is refused: its sweep depends on the order of residuals and is not a fixed map.

Measured

On the resistive divider (bench/bp_anderson.jl, by infer! with tol = 1e-11):

floodingspanning tree+ Anderson(2)+ Anderson(3)flooding + Anderson(3)
2, 34638251511 168
1, 3187342525307
3, 2463803234920
2, 2116 50920 8813124> 20 000

On Gaussian grids up to 20 × 20 (bench/bp_grid.jl), Anderson(3) around the spanning-tree order needs 67–296 sweeps where the plain order needs 894–1 425 (), and 124 where it does not converge in 20 000 (). Why a short memory suffices: the spanning-tree sweep factors through its off-tree messages, so its Jacobian has at most two nonzero eigenvalues per independent loop (vault: Composing Optimisers §4.4).

The means agree with the plain spanning-tree order’s to (to for , where the plain order’s stopping point is the less accurate one). The bench’s own implementation, with a reference fixed point, gives the same picture in message evaluations (vault: Composing Optimisers §4.3).

What it does not do

  • Wrap flooding reliably. Around flooding it was slower in every divider setting above, and with it can fail (§4.3); on Gaussian grids it speeds flooding up (0.08–0.73 of its sweeps, bench/bp_grid.jl, §4.4). Around spanning_tree_schedule it helped everywhere measured, with no restarts on the grids. Why the divider differs is not known (its flooding spectrum is a ring of equal moduli).
  • Gradients. Schedule replay and the implicit adjoints do not know about the mixing; parameter gradients through an AndersonSchedule are not supported.
  • Non-Gaussian messages, plates batched on a device, and damping of the mixed step (Walker & Ni’s ): not implemented. damping is passed to inner.
  • Safeguards beyond positivity. No residual-decrease check (safeguarded Anderson); a step that increases the residual is kept.

Difficulties

The bench scales by the reference fixed point’s block maxima, which a library does not have; the scales are taken from the first image and frozen, because changing them between iterations would make the stored differences inconsistent. The library and the bench therefore mix in slightly different coordinates; both give the picture above.