design

The optimisers in this repository act on three kinds of state: parameters (OptimiserFactor, fit_em with SQUAREM), messages (a BP sweep, with damping) and, not yet, beliefs. Most proposals for faster or safer inference are modifiers of one of these maps: damping, momentum, Anderson or SQUAREM extrapolation, a mirror map, noise. This note asks how such pieces compose.

Two results. Fixed points compose; convergence does not. Each modifier keeps the base map’s fixed points, so any stack of them still satisfies condition (O) of The Regulariser and the Loss. But whether the stack converges, and how fast, depends on the spectrum of the linearised map, and two convergent pieces can compose into a divergent one. The spectrum also says which modifier to use: momentum where the slow eigenvalues are real and near 1, damping or Anderson where they are complex or near −1. That makes a spectral diagnostic the first tool to build, and a benchmark the way to decide the rest.

Measured on the divider graph (§4.1, bench/bp_spectrum.jl): every slow eigenvalue of a flooding sweep is complex, on a ring. Heavy ball diverges there for every β ≥ 0.07, damping gains at most 2% in rate, and the gain is in the schedule: one that goes round the loop in a sweep converges at ρ⁶ instead of ρ per sweep (38 sweeps instead of 326). A fixed order that goes once round the loop each way, or one built from a spanning tree with no knowledge of the loop, does that at flooding’s cost per sweep: about six times fewer message evaluations in every setting tried (§4.2, bench/bp_schedules.jl; now spanning_tree_schedule in Mycelium). Anderson acceleration composes well with that order: on top of it it saves up to half again on the divider, and where the loop gain is near 1 it turns 297 000 evaluations into 414; on top of flooding it costs 1.4 to 3.8 times more on the divider’s ordinary settings, or fails (§4.3, bench/bp_anderson.jl).

Why it works (§4.4, bench/bp_grid.jl): a spanning-tree sweep factors through its off-tree messages, so its Jacobian has at most two nonzero eigenvalues per independent loop (on the divider, two, both ), which a short memory cancels. On Gaussian grids up to 20 × 20 the spanning-tree order needs 0.17–0.29 of flooding’s sweeps, Anderson on top of it a further 5 to 19 times fewer in the slow regime, and there Anderson helps flooding too: the divider’s failure does not generalise.

Sources: Yedidia, Freeman & Weiss, Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms, IEEE TIT 51(7), 2005 (BP fixed points are the stationary points of the Bethe free energy); Polyak, Some Methods of Speeding Up the Convergence of Iteration Methods, 1964 (heavy ball); Walker & Ni, Anderson Acceleration for Fixed-Point Iterations, SIAM J. Numer. Anal. 49(4), 2011; Varadhan & Roland, SQUAREM, 2008; Raskutti & Mukherjee, The Information Geometry of Mirror Descent, IEEE TIT 61(3), 2015; Krichene, Bayen & Bartlett, Accelerated Mirror Descent in Continuous and Discrete Time, NeurIPS 2015; Wibisono, Wilson & Jordan, A Variational Perspective on Accelerated Methods in Optimization, PNAS 113(47), 2016; Andrychowicz et al., Learning to Learn by Gradient Descent by Gradient Descent, NeurIPS 2016; Cruttwell, Gavranović, Ghani, Wilson & Zanasi, Categorical Foundations of Gradient-Based Learning, ESOP 2022 (Def. 3.14, update lenses). The composition laws and the spectral reading are original to this vault; the table in §4 is a closed-form check, §4.1 is measured by bench/bp_spectrum.jl and §4.2 by bench/bp_schedules.jl, §4.3 by bench/bp_anderson.jl, §4.4 by bench/bp_grid.jl; Elidan, McGraw & Koller, Residual Belief Propagation, UAI 2006 (the priority queue of §4.2); Wainwright, Jaakkola & Willsky, Tree-Based Reparameterization Framework for Analysis of Sum-Product and Related Algorithms, IEEE TIT 49(5), 2003 (updates along spanning trees). code: lib/Mycelium.jl/src/anderson.jl (AndersonSchedule), bench/bp_spectrum.jl, bench/bp_schedules.jl, bench/bp_anderson.jl, bench/bp_grid.jl, bench/divider.jl, lib/Mycelium.jl/src/schedules.jl (spanning_tree_schedule), lib/Mycelium.jl/src/passing.jl (sweep!, damping), lib/Mycelium.jl/src/schedules.jl (AbstractSchedule), lib/Mycelium.jl/src/factors.jl (Momentum, Nesterov), lib/MyceliumLearning.jl/src/em.jl (SQUAREM)

Bibliography: Yedidia et al. 2005 · Polyak 1964 · Walker & Ni 2011 · Varadhan & Roland 2008 · Raskutti & Mukherjee 2015 · Krichene et al. 2015 · Wibisono et al. 2016 · Andrychowicz et al. 2016 · Cruttwell et al. 2022 · Elidan et al. 2006 · Wainwright et al. 2003

Theory (CT-ML wiki): Gradient Based Learning with Parametric Lenses · Variational Free Energy

1. Three maps to accelerate

statebase map its fixed pointsexists
parameters a gradient step , or an M-step (for EM: stationary points of the likelihood)OptimiserFactor, fit_em
messages one BP sweep (flooding, sequential, residual)stationary points of the Bethe free energy (Yedidia et al. 2005)sweep!, infer!
beliefs a step on in some geometrystationary points of on the constraint setmissing (no , no retraction: Feature Backlog, the Langevin row)

The second row is the one that matters most and is easiest to get wrong. A BP sweep is not a gradient step on . It is a fixed-point map whose fixed points happen to be ‘s stationary points. So BP satisfies (O), but nothing guarantees it descends on the way, and modifiers built for gradient descent (momentum, mirror maps) carry over only as fixed-point modifiers, with none of their descent guarantees.

2. The pieces: modifiers of a map

Each piece takes a map (with or without state) and returns another. Write for the residual.

modifierthe new mapstatefixed points
relaxation (damping), none, exactly
heavy ball (Polyak 1964), with , exactly
Anderson (Walker & Ni 2011), , minimising the last iteratescontains ; it can also stall at a non-fixed point, so convergence is judged by
SQUAREM (Varadhan & Roland 2008)a step along and , from one nonecontains (with a guard for )
mirror map (for a gradient map)none (on a constraint set, its KKT points)
acceleration of a mirror step (Krichene et al. 2015)a mirror step on a coupled pair of sequencesa second sequenceas for the mirror map
temperature (Langevin)add noise to a momentum step, the noisenone for : an invariant law , on the global minimisers as
learned (Andrychowicz et al. 2016)anythinganythingnot guaranteed: (O) must be checked or built in

The heavy-ball row in one line: a fixed point needs , so ; then gives , and . The same argument as for Momentum in The Regulariser and the Loss §3, applied to a residual in place of a gradient.

The mirror rows apply only where is a gradient step, so for BP they need the belief-row map of §1 first. Their use is geometric. With the log-partition as , mirror descent in the mean parameters is natural-gradient descent in the natural ones (Raskutti & Mukherjee 2015), so every iterate is a valid belief. Leaving that set is what broke the scratch heavy-ball test (Feature Backlog, the Langevin row: a negative precision, then NaN).

3. Three ways to compose, and what each keeps

Wrapping (a modifier around a map, or a stack of them). Every modifier above except temperature and a learned rule keeps , so a stack of them does too. Damping inside Anderson inside a schedule still satisfies (O). That is the good news, and it holds whatever the order.

Alternation on separate blocks (inference sweeps and parameter steps, as in EM or the proposed train!). If updates the beliefs given and the parameters given , the alternation is at rest exactly when and : the joint fixed points. When both blocks descend the same (condition (I)), those are its stationary points. When they descend different objectives, the fixed points are a game’s equilibria instead (The Two-Part Diagram §3).

Nesting (an inner solve to a tolerance inside each outer step). The outer fixed points are stationary only up to the inner tolerance, and the outer gradient is either unrolled through the inner iterations or taken at the inner fixed point by the implicit function theorem, which Mycelium already does (adjoint = :implicit in free_energy.jl). Inner tolerance becomes a hyperparameter of the composite.

What does not compose: convergence. Two maps that each converge can compose into one that diverges. For linear maps the rate is the spectral radius, and it is not submultiplicative:

Each converges in two steps; alternating them diverges. There is one positive law: if and are contractions in the same norm with factors and share a fixed point, their composite contracts with . Loopy BP is not a contraction in general, which is why no stack of modifiers on it comes with a guarantee for free.

4. The spectrum decides which modifier helps

Near a fixed point every map is its linearisation, . For a Gaussian graph the mean update is exactly linear once the precisions have converged, so can be computed. Then each modifier acts on each eigenvalue of separately:

  • relaxation maps : it pulls everything towards 1, so it cures eigenvalues near (oscillation) and complex ones, and slows those near ;
  • heavy ball (with ) turns each into the two roots of . For real it is stable exactly when , so it never destabilises a convergent real spectrum. At the best gives , about 10.5 times fewer iterations than 0.99. At , gives ;
  • but for complex momentum can destabilise a convergent map:
0.950.951.221.431.61
0.940.941.091.271.44
0.950.951.231.441.63

(spectral radius of the heavy-ball iteration; closed-form roots, computed in scratch.)

A BP sweep’s Jacobian is not symmetric, so complex eigenvalues are possible. Gradient descent on a smooth has a symmetric Jacobian and real eigenvalues, which is the setting momentum was designed for. On the divider graph a sweep’s slow eigenvalues are all complex (§4.1), and the linear analysis alone predicts the momentum failure.

Anderson needs no such case split. It fits the best combination of the last residuals, so on a linear map it is a Krylov method (GMRES-like) and handles complex spectra. That makes it the natural first accelerator for BP sweeps, and the cheapest to try: it wraps sweep! through AbstractSchedule and needs none of the belief-geometry additions.

4.1 Measured: the divider (experiment 1)

bench/bp_spectrum.jl linearises one flooding sweep of the resistive divider (test/runtests.jl: three variables, three constraints, one loop of six edges, weak priors of variance ) at its fixed point, by central differences over every message’s . The precisions do not depend on the means ( exactly), so the spectrum is the mean block’s and the precision block’s together.

mean eigenvalues: precision eigenvalues: flooding sweeps to an error
2, 3 (the test’s)0.93470.87360.6667326
1, 30.83270.69340.3333122
3, 20.93470.87360.6667322
2, 20.999840.999680.9990597 224 (§4.2)

(12 nonzero eigenvalues in each block, all of the same modulus to ; the error is the largest of the mean and precision errors, each relative to its block’s largest entry.)

  • All the slow eigenvalues are complex, on a ring. The mean eigenvalues sit at , and : the sixth roots of . The precision eigenvalues sit at , , and , the sixth roots of , with in every case. So one trip round the six-edge loop takes six flooding sweeps, and a mean comes back multiplied by . In the three unequal cases ; with equal resistors it is . That is an observation on four settings, not derived. The test’s divider is a benign case of a graph that flooding solves badly.
  • The prediction is exact. Undamped, the measured asymptotic rate is 0.9346, 0.8324 and 0.9347, against = 0.9347, 0.8327 and 0.9347.
  • Momentum is ruled out on this graph, not merely untuned. Heavy ball’s spectral radius on the test’s divider is 0.9864 at , 0.9964 at 0.06, 1.0062 at 0.07 and 1.2043 at 0.3. With equal resistors it diverges for every . The scratch failure for every (Feature Backlog, the Langevin row) is what the linear analysis predicts, before any precision goes negative.
  • Damping can barely help. Relaxation pulls a ring towards 1 and shrinks some eigenvalues at the expense of others: the best uniform gives 0.9260 against 0.9347. Mycelium’s damping relaxes only the factor-to-variable messages (passing.jl, _step!), so its Jacobian is with on those messages and 1 elsewhere, not on every eigenvalue. That prediction matches the measured rate at damping 0.5 (0.9167 and 0.9164) and 0.8 (0.9591 and 0.9591). At 0.25, and at 0.5 for , the runs converge faster than predicted, as a start that barely excites the leading modes would (not checked). And the rate is not the sweep count: damping 0.5 has the better rate (0.9167 against 0.9347) but needs 410 sweeps against 326, because the transients differ.
  • The schedule is the modifier that works. A residual schedule (the largest change first) converges at exactly per sweep, a trip round the loop in each sweep: 38 sweeps instead of 326, 15 instead of 122. Its sweeps cost more, though: it evaluates every task’s candidate before each commit, evaluations against flooding’s 18, so it needs about twice flooding’s message evaluations (12 312 against 5 868). Its order, replayed as a plain sequential sweep (with the tasks it skipped appended), keeps the rate at flooding’s cost per sweep for (462 evaluations against 2 196), partly for (1 620 against 5 868), and not for . A sequential sweep in flooding’s task order gets per sweep (two hops), at half flooding’s evaluations.

So on this graph the slow modes are a ring, momentum diverges, damping gains a few percent, and the gain is in the order. The expectation was per sweep at flooding’s cost for a schedule that follows the loop; the replays above reach it on one of three settings, and §4.2 tests it directly. Anderson stays the open candidate: the mean block has six distinct nonzero eigenvalues, so on the linear part a short memory should already cancel them (an expectation, experiment 3).

4.2 Measured: the order of a sweep (experiment 2)

bench/bp_schedules.jl runs the same 18 messages of the divider six ways and counts message evaluations (calls of the update rule, committed or not) until the error against the fixed point falls below (the error of §4.1, from a cold start):

  • flooding, double-buffered, 18 evaluations per sweep;
  • sequential, in place, in all_tasks order (edge by edge);
  • loop: the messages off the loop, then once round the loop each way (the cycle found by a depth-first search);
  • spanning: the messages off a spanning tree, then the tree’s inward and outward sweeps (_tree_sweeps from a variable; it needs no knowledge of the loop);
  • residual: ResidualSchedule, every candidate evaluated before each commit;
  • queue: residual BP with a priority queue (Elidan, McGraw & Koller, 2006): after a commit, only the messages that read the committed one are evaluated again (the dependencies of belief propagation; mean-field and EP nodes read more and are not covered).

Evaluations to an error , and as a fraction of flooding’s:

floodingsequentialloopspanningresidualqueue
2, 35 8682 970 (0.51)1 026 (0.17)1 008 (0.17)12 312 (2.10)1 418 (0.24)
1, 32 1961 134 (0.52)414 (0.19)396 (0.18)4 860 (2.21)562 (0.26)
3, 25 7962 862 (0.49)972 (0.17)972 (0.17)12 312 (2.12)1 383 (0.24)
2, 21 750 032875 016 (0.50)291 672 (0.17)297 144 (0.17)not run538 712 (0.31)
  • A fixed order round the loop is the whole gain. Loop and spanning converge at per sweep (measured 0.6666 and 0.6667 for ; 0.3335 and 0.3326 for ), the residual schedule’s rate, at flooding’s 18 evaluations per sweep: about six times fewer evaluations than flooding, in all four settings. The sequential sweep in edge order gets (0.8736), half.
  • The spanning-tree order needs no knowledge of the loop and matches the loop order to within 3%. It is the schedule to try first on graphs with several loops: every off-tree edge’s message is refreshed, then information crosses the whole tree in one sweep.
  • The priority queue removes the residual schedule’s quadratic cost (from 2.1 to 0.24 times flooding’s evaluations) but stays behind the static orders, at 0.24 to 0.31: its commits follow the loop like the residual schedule’s (690 commits, 38 sweeps’ worth, for ), and each commit costs about one more evaluation for its dependents. On this graph a fixed order is cheaper. Where the slow part of a graph is not known in advance, or moves, the queue is the adaptive option; that is untested.
  • With equal resistors flooding needs 97 224 sweeps, not the 145 000 that alone gives from an error of 1: the cold start puts little into the slowest modes (as for damping 0.25 in §4.1). The run’s rates over its last six sweeps are not asymptotic and are not reported; the fixed point is the loop order’s run to its rounding floor. With a residual at the floor could leave an error a thousand times larger; checked in §4.3, the same procedure’s reference is within of a fixed point with residual , so the criterion of holds.

So the cheapest acceleration of BP on this graph is a change of schedule, no modifier at all: a spanning-tree order, a sixfold saving that keeps the fixed points (§3: a schedule changes the map, not its fixed points). Whether it holds on graphs with several loops, where no one tree carries every loop’s information in one sweep, is the next measurement (a Gaussian grid, in the benchmark). The order is now a library schedule, spanning_tree_schedule(g) (Mycelium, schedules.md); with infer! on the test’s divider it converges in 82 sweeps against flooding’s 463, to the same marginals (test/runtests.jl).

4.3 Measured: Anderson around a sweep (experiment 3)

bench/bp_anderson.jl wraps a sweep (flooding or the spanning-tree order) in Anderson acceleration with memory (Walker & Ni, 2011, type II, undamped): with the least-squares fit of the newest residual by the differences of the last . It keeps ‘s fixed points. The least squares are taken in coordinates scaled per block (precisions are about ), with a ridge of of the trace; a step that would make a precision non-positive is replaced by the plain sweep and the memory cleared (a restart). Cost: 18 message evaluations per iteration, as before. The reference fixed point, the plain spanning-tree sweep run to its rounding floor, is within of Anderson(3) after 300 iterations in every setting.

Message evaluations to an error , as a fraction of plain flooding’s:

base123510
2, 3flooding1 (5 868)1.461.793.19failsfails
spanning0.170.190.130.130.130.15
1, 3flooding1 (2 196)1.461.952.232.383.79
spanning0.180.200.190.190.190.22
3, 2flooding1 (5 796)1.441.933.39fails152.9
spanning0.170.110.090.090.100.12
2, 2flooding1 (1 749 924)1.211.560.280.020.0019 (3 312)
spanning0.17 (297 108)4.5e-43.2e-42.4e-4 (414)3.4e-44.0e-4

(“fails”: not below within 400 000 iterations, restarting tens of thousands of times.)

  • On the divider, Anderson composes with the order, not with flooding. Around the spanning-tree order it loses at most a fifth (, : 0.22 against 0.18) and gains up to half (: 0.09 against 0.17). Around flooding it loses in all three ordinary settings, by 1.4 to 3.8 times, and with or 10 it can fail outright. Two pieces that each converge compose into one that does not: §3’s warning, measured.
  • Where the loop gain is near 1, Anderson is the cure. With equal resistors () the spanning-tree order needs 297 108 evaluations and Anderson(3) around it 414, about 700 times fewer (and 4 200 times fewer than flooding). Around flooding it needs a longer memory: gives 3 312. That fits §4.1’s expectation (a short memory cancels a few distinct eigenvalues; flooding’s ring has six per block); §4.4 computes the spanning-tree sweep’s spectrum: two eigenvalues.
  • Why Anderson hurts flooding in the ordinary cases is not known. It is not the positivity guard: with there are no restarts for and , and it still costs 1.46 and 1.44 times flooding. A candidate is the precision block, which is nonlinear and converges at from far away; untested.

So the composition to use on this graph is the spanning-tree order, with Anderson(2–3) on top when convergence is slow; on the divider, flooding should not be accelerated by Anderson (on grids it should, §4.4). That composition is now in the library: AndersonSchedule(spanning_tree_schedule(g); m = 3) (Mycelium, anderson.md), which by infer! converges in 51, 25, 34 and 24 sweeps where the plain spanning-tree order needs 82, 34, 80 and 20 881, and flooding 463, 187, 463 and 116 509 (bench/bp_anderson.jl, last table; the test’s divider in test/runtests.jl).

4.4 Why a short memory suffices, and grids with many loops

The spanning-tree sweep factors through its off-tree messages. A sweep of spanning_tree_schedule first updates the messages on the edges outside the tree, reading the old state, and then runs the tree’s inward and outward sweeps. On a tree each of those messages reads only messages computed earlier in the same sweep: an inward message reads its source’s children (already sent) and the off-tree edges (already updated), an outward message its source’s parent (already sent) and the rest. So after the first step nothing of the old state is read again, and the sweep is a map of the old state through the off-tree messages alone:

With scalar variables each off-tree edge has two messages, and a connected graph has one off-tree edge per independent loop ( of the factor graph), so per block the Jacobian has rank at most : at most nonzero eigenvalues, against flooding’s up to one per message. (Derived here, and checked below; with -dimensional variables, blocks of size .)

bench/bp_grid.jl computes both spectra at the fixed point (central differences, as in §4.1). The grids are Gaussian: scalar with priors and a smoothness constraint on each grid edge, so the exact means solve ( the grid Laplacian); a large is the slow regime.

graphloops flooding: nonzero, spanning tree: nonzero, , largest
divider, 112, 0.9347 (a ring)2, 0.6667, both
divider, 112, 0.999842, 0.99905, both
3 × 3 grid, 448, 0.94128, 0.7167, real positive
4 × 4 grid, 996, 0.995118, 0.9754, real positive

(mean blocks; the precision blocks have as many nonzero eigenvalues.) The count is exactly in all four. On the divider the two eigenvalues coincide, so on the linear part Anderson with already cancels them, which is why –3 sufficed in §4.3; on grids the leading eigenvalue is real, positive and well separated (0.9754 against 0.7203 next), the case where extrapolation pays most.

Grids with many loops. Sweeps by infer! to a message residual of (at most 20 000; every schedule sends the same messages per sweep), with the largest error of a mean against the exact in brackets:

grid, floodingspanning+ A(2)+ A(3)+ A(5)flooding + A(3)
5 × 5, 11012925242274
5 × 5, 1005 303894956747462
10 × 10, 11193327272778
10 × 10, 1007 2111 191140131111584
10 × 10, > 20 000 ()> 20 000 ()177 ()124 ()120 ()830 ()
20 × 20, 1007 8011 4252302962231 067
  • The spanning-tree order keeps its gain with many loops: 0.17–0.29 of flooding’s sweeps, the larger fractions in the fast regime. One tree is enough here; alternating trees were not needed.
  • Anderson on top of it is the large gain in the slow regime: 5 to 19 times fewer sweeps than the plain spanning-tree order at (with : 13, 9 and 5 times on the three grids), and convergence in about 120–180 sweeps where neither plain order reaches the tolerance in 20 000 (). The memory matters less than having one: are within a factor of two of each other, and not in order (20 × 20: 230, 296, 223); restarts were never needed around the spanning-tree order (0 in every run).
  • On grids Anderson helps flooding too: 0.08–0.73 of plain flooding’s sweeps, and 830 sweeps where flooding does not converge in 20 000, with a few restarts. So §4.3’s “Anderson hurts flooding” is a property of the divider (its ring of equal moduli), not of flooding; still, flooding + Anderson needs 3 to 7 times the sweeps of spanning + Anderson.
  • The stopping rule is not the error. At the same residual the plain spanning-tree order stops with errors of about , flooding with about : a residual bounds the error only by about , and the schedules differ in per sweep. With the errors at the tolerance are for the same reason.
  • Wall time follows the sweeps; Anderson’s least squares cost little (10 × 10, : 0.70 s for A(3) against 5.65 s plain and 33.7 s flooding; the first runs include compilation).

So, on every graph measured: use AndersonSchedule(spanning_tree_schedule(g); m = 3) when convergence is slow, and the plain spanning-tree order otherwise. Open: graphs where BP oscillates or diverges (not walk-summable, or non-Gaussian), where neither has been tried, and the choice of tree.

5. The design space, and why it needs a benchmark

The choices multiply: the state (θ, m, b) × the schedule × the stack of modifiers × their hyperparameters (α, β, , temperature) × nesting tolerances. Each claim so far was tried on one graph. Three consequences:

  1. A spectral diagnostic first. Report the leading eigenvalues of the linearised sweep at a fixed point (exact for Gaussian means; by finite differences or AD of sweep! otherwise). It says before any tuning whether momentum, damping or Anderson should help, and it can be checked against the observed iteration counts.
  2. A benchmark to compare stacks (Feature Backlog, Tooling): problems with reference answers where today’s methods are slow or fail, run by one script recording sweeps, wall time, error, the free energy reached and failures.
  3. A learned optimiser last. A learned trained on the benchmark can overfit it (its outer criterion is the benchmark), and must keep (O): the simplest way is to learn only the hyperparameters of a stack whose fixed points are fixed by construction (§3), not a free map.

A proposed order of experiments, cheapest first:

experimentneedsquestion
1spectrum of the linearised flooding sweep on the dividerfinite differences of sweep!done (§4.1): all complex, on a ring; heavy ball diverges for ; the schedule is what helps
2a loop-following sequential order, and the residual schedule with a priority queuethe cycle basis of the graph; LP-023’s queuedone on the divider (§4.2): loop and spanning-tree orders need 0.17–0.19 of flooding’s evaluations, the queue 0.24–0.31; graphs with several loops remain
3Anderson () around flooding and around experiment 2’s ordera schedule type wrapping sweep!done (§4.3–4.4): AndersonSchedule; around the spanning-tree order 5 to 19 times fewer sweeps in the slow regime, on the divider and on grids; around flooding worse on the divider, better on grids
4SQUAREM and Anderson on fit_em for the switch learningem.jldoes Anderson beat SQUAREM on the parameter block?
5mirror and accelerated mirror descent on beliefs, a mirror map, primal beliefsdo valid-by-construction iterates fix the momentum failure?
6Langevin with annealed temperatureexperiment 5’s interfacedoes it leave poor fixed points on multimodal graphs?

6. Open questions

  1. What is a composite’s (O) when the pieces descend different objectives? Damping a sweep that minimises the Bethe and an M-step that maximises a likelihood are both fine alone; the alternation’s fixed points are the joint stationary points only if the two objectives are one (§3).
  2. Is there a norm in which BP contracts on a given graph? Where there is, composition laws become rates (§3); the walk-summable Gaussian graphs are the candidates.
  3. Do accelerations compose in continuous time? Wibisono et al. (2016) derive accelerated methods as discretisations of one Lagrangian flow. If the modifiers above are discretisations of flows, composing them is adding terms to the flow, and the question becomes which discretisation keeps the rate.
  4. Optimiser composition as lens composition. An update rule is a lens (Cruttwell et al., Def. 3.14), and wrapping is a map from lenses to lenses that keeps the fixed points. Whether the modifiers of §2 form a category acting on update lenses, with (O) as a property it preserves, is unworked.

Related: The Regulariser and the Loss, The Inferencer and the Optimizer, The Two-Part Diagram, Schedules, Loopy Message Passing, Feature Backlog