AndersonSchedule(inner; m = 3)(anderson.jl): Anderson acceleration of any static schedule. A sweep ofinneris 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 asinner, one sweep ofinnerper 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
Float64arrays, 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 isinner’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
WeakKeyDictkeyed by theMessageStore, so the schedule is reusable across stores (eachinfer!starts afresh) and a dropped store frees it. - Residual.
sweep!returnsinner’s residual, the distance from the stored messages to their images, which is the fixed-point residual inbelief_distance. Sopropagate!’stolmeans what it means forinner, and the default criterion isinner’s. ResidualScheduleis 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):
| flooding | spanning tree | + Anderson(2) | + Anderson(3) | flooding + Anderson(3) | |
|---|---|---|---|---|---|
| 2, 3 | 463 | 82 | 51 | 51 | 1 168 |
| 1, 3 | 187 | 34 | 25 | 25 | 307 |
| 3, 2 | 463 | 80 | 32 | 34 | 920 |
| 2, 2 | 116 509 | 20 881 | 31 | 24 | > 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). Aroundspanning_tree_scheduleit 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
AndersonScheduleare not supported. - Non-Gaussian messages, plates batched on a device, and damping of the mixed step (Walker &
Ni’s ): not implemented.
dampingis passed toinner. - 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.