Message Passing and the Algorithms That Reach the Limit

So far the physics has been diagnostic: it tells you which phase you are in. The remarkable turn is that the same machinery produces algorithms, and in many cases the best efficient algorithms known.

The logic connecting them is worth stating, because it explains why one set of tools does both jobs.

The quantity you want is the posterior distribution over the signal given the data. Computing it exactly requires summing over exponentially many configurations, which is infeasible.

Statistical physics faced the identical obstacle a century earlier. Computing the properties of a magnet requires summing over every configuration of its spins. The response was a family of mean-field methods: approximate the effect of all other variables on a given variable by an average, and solve the resulting self-consistent equations.

That approximation is a computation you can actually run. So the analysis of the problem and the algorithm for solving it come from the same source, which is why the theory predicts algorithmic thresholds rather than merely observing them.

The concrete realisation of that idea is belief propagation, and its structure is simple enough to describe fully.

Represent the problem as a graph. Variables are nodes; observations that couple several variables are factors connecting them.

Each node maintains a belief about its own value and sends messages to its neighbours. A message from variable i to factor a says: here is what I believe about my value, based on everything I have heard except from you. The factor combines incoming messages with its own constraint and sends back what it now believes about each participant.

Iterate until the messages stop changing.

The exclusion in that message rule is the crucial detail. Leaving out the recipient's own contribution prevents information from echoing back and being counted twice as if it were independent evidence.

On a tree, belief propagation is exact: it computes the true marginals. Real problem graphs have loops, so it is an approximation, and it can fail to converge. But on large sparse random graphs, loops are long and rare, the graph is locally tree-like, and the approximation becomes excellent.

The cavity method is the analytical counterpart of belief propagation, and it is the tool Decelle, Krzakala, Moore, and Zdeborova used to derive the block model phase diagram.

The idea is in the name. To understand variable i, remove it from the system, leaving a cavity. Analyse the remaining system, which is slightly smaller and, crucially, has one less source of correlation. Then ask what happens when you put i back.

In the large-system limit, the neighbours of the removed variable become effectively independent, because the loops that would correlate them are long. That independence makes the calculation tractable and yields self-consistent equations for the distribution of messages.

The payoff is that you can compute the free energy, which is the physicists' name for the quantity whose structure determines the phase diagram. From it you read off the Bayes-optimal error, the location of the information-theoretic threshold, and the point where the landscape fractures.

So the same construction yields both the map of the phases and a running algorithm. That duality is the field's central methodological asset.

Belief propagation assumes a sparse graph. Many important problems are dense: in compressed sensing every measurement touches every unknown, so the factor graph is complete and passing a message along every edge is quadratic work per iteration.

Approximate message passing (AMP) solves this. David Donoho, Arian Maleki, and Andrea Montanari introduced it in "Message-passing algorithms for compressed sensing", published in the Proceedings of the National Academy of Sciences, volume 106, number 45, pages 18914 to 18919, in November 2009.

The derivation starts from belief propagation on the dense graph, then observes that in high dimensions each individual message differs from the node's overall belief by a small amount. Expanding to first order collapses the messages: instead of tracking one message per edge, you track one estimate per variable.

What survives from the message structure is a single correction term, historically called the Onsager term, which subtracts the feedback each variable's own previous estimate contributed to what it is now hearing.

That term is the entire difference between AMP and ordinary iterative thresholding, and dropping it destroys the algorithm's properties.

The algorithm is short enough to read in full, which is part of why it is studied so heavily.

# recover sparse x from y = A x + noise
x = np.zeros(n)
resid = y.copy()

for t in range(iters):
    # 1. propose an update from the current residual
    prop = x + A.T @ resid

    # 2. apply the denoiser matched to the signal prior
    x_new = eta(prop, theta[t])          # e.g. soft thresholding

    # 3. Onsager correction: average derivative of the denoiser
    onsager = resid * eta_prime(prop, theta[t]).mean() * (n / m)

    # 4. residual with the memory term subtracted
    resid = y - A @ x_new + onsager
    x = x_new

Without line 3 this is iterative soft thresholding, a reasonable but unremarkable algorithm. With it, two things become true that are not true otherwise.

The error at each iteration is exactly predictable in the high-dimensional limit. And for a wide class of problems, AMP achieves the best error any polynomial-time algorithm is believed to achieve, matching the algorithmic threshold.

The denoiser is where problem knowledge enters. Soft thresholding for sparse signals; the appropriate posterior mean for other priors.

The property that makes AMP unusual among algorithms is state evolution, presented in the companion analysis paper by the same authors.

State evolution is a small set of deterministic equations that track a single scalar, the mean squared error, from one iteration to the next. In the high-dimensional limit these equations predict the algorithm's actual performance exactly.

The practical consequences are unusual.

You can know the final error before running the algorithm, by iterating a one-dimensional recursion instead of the full high-dimensional procedure.

You can determine the number of iterations needed without experimentation.

And you can locate the algorithmic threshold analytically. Sweep the data ratio and find where the state evolution recursion stops converging to the good fixed point. That value is the boundary of the easy phase.

This is what closes the loop with the previous lesson. The hard phase is not identified by trying algorithms and failing. It is the region where the state evolution of the best known algorithm gets stuck at a poor fixed point while the Bayes-optimal calculation says a better answer exists.

The unusual feature of this area is that analysis and algorithm are the same object viewed from different sides. That is why thresholds can be predicted analytically rather than discovered by trial.

The assumptions are restrictive, and knowing them tells you when to reach for these tools.

Two failure modes are worth recognising in practice. AMP's guarantees are tied to random measurement matrices with independent entries; on structured or strongly correlated matrices it can diverge outright, which motivated variants such as vector and orthogonal AMP. And belief propagation on graphs with short loops may simply fail to converge.

The honest summary of what this buys you: for a specific and well-studied class of problems, you get algorithms that provably reach the computational limit, plus exact analytical prediction of their behaviour.

That is a stronger guarantee than almost anything else in machine learning offers, purchased with much stronger assumptions than almost anything else requires. The final lesson asks what survives when the assumptions do not.