TAP free energy, spin glasses and variational inference

Zhou Fan, Mei Song, Andrea Montanari

Abstract: This research establishes a rigorous mathematical link between the statistical physics of spin glasses and high-dimensional Bayesian inference. By analyzing the Sherrington–Kirkpatrick model with ferromagnetic bias, the authors demonstrate that the Thouless–Anderson–Palmer (TAP) free energy accurately identifies the posterior mean in $\mathbb{Z}_2$ synchronization problems. Using the Kac–Rice formula and free probability theory, the study proves that local minimizers of the TAP energy landscape concentrate around the Bayes-optimal estimator in high signal-to-noise regimes, whereas standard mean-field approximations fail.

Introduction: The Challenge of High-Dimensional Estimation

In high-dimensional statistics, a fundamental challenge is estimating a hidden signal from noisy observations. A classic benchmark for this is the $\mathbb{Z}_2$ synchronization problem. In this model, one observes a noisy matrix $Y = \frac{\lambda}{n}xx^\top + W$, where $x$ is a vector of $\pm 1$ "spins" and $W$ represents Gaussian noise. The objective is to determine the "posterior mean"—the average of all possible signal configurations weighted by their likelihood given the data.

Calculating this mean exactly is computationally intractable for large systems, as it requires summing over $2^n$ possible configurations. To address this, researchers often turn to Variational Inference (VI), which transforms the integration problem into an optimization task: finding a probability distribution that minimizes a specific "free energy" function.

The TAP Advantage: Correcting for Self-Feedback

The standard approach in machine learning is the naive mean field (MF) approximation. While computationally efficient, naive MF is known to be biased in "dense" problems like synchronization. Statistical physics offers a more sophisticated alternative: the Thouless–Anderson–Palmer (TAP) free energy.

The critical difference lies in the Onsager correction term. In dense networks, each spin influences its neighbors, which in turn influence the original spin. The TAP energy includes a correction to account for this "self-feedback" noise. While physicists have long intuited that the TAP approach is superior, this paper provides the first rigorous proof that TAP minimizers actually track the true posterior mean in the large-system limit.

Methodology

The authors employ a suite of advanced mathematical tools to analyze the non-convex landscape of the TAP free energy:

  1. Kac–Rice Formula: Used to count the critical points (minima, maxima, and saddles) of the random energy function. This allows the authors to upper-bound the "complexity"—the exponential rate at which the number of critical points grows with system size.
  2. Free Probability Theory: To evaluate the Kac-Rice formula, one must understand the spectral behavior of the Hessian (the matrix of second derivatives). Since the Hessian is a sum of a random Wigner matrix and a diagonal matrix, free probability provides the necessary tools to characterize its eigenvalues.
  3. Large Deviations: By applying Sanov’s theorem and Varadhan’s lemma, the authors demonstrate that critical points located far from the true signal possess significantly higher energy, rendering them irrelevant in the large $n$ limit.

Key Insights and Results

The paper's findings confirm several long-standing conjectures in the physics of disordered systems:

  • Consistency of TAP (Theorem 1.2): For a sufficiently high signal-to-noise ratio (SNR), the distance between any low-energy local minimizer of the TAP free energy and the true posterior mean vanishes as $n \to \infty$. This validates TAP as a consistent estimator for synchronization.
  • Failure of Naive MF (Theorem 1.3): The authors rigorously prove that the naive mean field estimator remains at a strictly positive distance from the Bayes-optimal estimator, regardless of signal strength. This highlights the necessity of the Onsager correction.
  • Landscape Concentration: The research shows that at high SNR, the TAP landscape simplifies. Although it remains non-convex, all relevant local minimizers concentrate around the true signal, ensuring that the optimization problem is well-behaved.

Limitations and Future Work

While this work represents a major step forward, several questions remain. The current proof requires the signal-to-noise ratio $\lambda$ to be a "sufficiently large constant." It is not yet proven whether these results hold all the way down to the theoretical phase transition at $\lambda = 1$. Additionally, while the paper proves that good minimizers exist, it does not provide a guarantee that standard algorithms like gradient descent will always converge to them from a random start, though the success of Approximate Message Passing (AMP) suggests this is likely.

Future research may extend these proofs to higher-rank signals or different noise distributions, such as those found in the Stochastic Block Model, further bridging the gap between theoretical physics and practical machine learning.

Summary updated

Abstract

We consider the Sherrington–Kirkpatrick model of spin glasses with ferromagnetically biased couplings. For a specific choice of the couplings mean, the resulting Gibbs measure is equivalent to the Bayesian posterior for a high-dimensional estimation problem known as “${\mathbb{Z}}_{2}$ synchronization.” Statistical physics suggests to compute the expectation with respect to this Gibbs measure (the posterior mean in the synchronization problem), by minimizing the so-called Thouless–Anderson–Palmer (TAP) free energy, instead of the mean field (MF) free energy. We prove that this identification is correct, provided the ferromagnetic bias is larger than a constant (i.e., the noise level is small enough in synchronization). Namely, we prove that the scaled $\ell _{2}$ distance between any low energy local minimizers of the TAP free energy and the mean of the Gibbs measure vanishes in the large size limit. Our proof technique is based on upper bounding the expected number of critical points of the TAP free energy using the Kac–Rice formula.
BibTeX
@article{fan2021tap,
  author = {Zhou Fan and Mei Song and Andrea Montanari},
  title = {{TAP free energy, spin glasses and variational inference}},
  journal = {The Annals of Probability},
  year = {2021},
  doi = {10.1214/20-aop1443},
}
Figure