TAP free energy, spin glasses, and variational inference

Zhou Fan, Mei Song, Andrea Montanari

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.

Introduction

In the realm of high-dimensional statistics, a fundamental challenge is the estimation of a hidden signal—such as a vector $x \in \{+1, -1\}^n$—from noisy, high-dimensional observations. While the Bayesian posterior mean is the optimal estimator in terms of mean squared error, computing it directly is often computationally intractable. In a system of size $n$, the calculation requires summing over $2^n$ possible configurations, an exponential complexity that quickly becomes impossible as $n$ grows.

To address this, researchers frequently turn to Variational Inference (VI). VI reframes the estimation problem as an optimization task: finding a distribution within a tractable family that minimizes a "free energy" function. However, the most common approach, Naive Mean Field (MF), is known to fail for "dense" models like the Sherrington-Kirkpatrick (SK) model of spin glasses. This paper bridges a 40-year gap between physics heuristics and rigorous statistics by proving that a more sophisticated objective—the Thouless-Anderson-Palmer (TAP) free energy—correctly identifies the posterior mean in the $\mathbb{Z}_2$ synchronization problem.

The Variational Landscape: MF vs. TAP

The failure of Naive Mean Field in dense models stems from its inability to account for subtle correlations between variables. In the 1970s, physicists Thouless, Anderson, and Palmer introduced the "Onsager correction" term to the free energy. This correction accounts for the "reaction field"—the influence a variable has on itself through its neighbors.

While physicists have long used TAP-based heuristics to study spin glasses, providing a rigorous proof that TAP actually works for statistical inference has remained an open challenge. This paper demonstrates that the Onsager correction is not just a physical curiosity but a mathematical necessity. Without it, the variational landscape is biased, and its critical points remain at a strictly positive distance from the true solution, even in the limit of infinite data.

Methodology: Counting Critical Points

The authors employ a sophisticated toolkit from probability theory and statistical physics to analyze the TAP energy landscape:

  • Kac-Rice Formula: This serves as the core technical engine. It allows the authors to count the expected number of critical points (minima, maxima, and saddles) of the random TAP energy landscape. By bounding the "complexity" (the exponential growth rate of the number of critical points), they can characterize the shape of the energy surface.
  • Free Probability Theory: To evaluate the Hessian of the TAP energy, the authors utilize free probability to understand the spectral distribution of low-rank deformations of Wigner matrices. This is crucial for determining which critical points are stable local minima.
  • Large Deviations: Using Sanov’s Theorem and Varadhan’s Lemma, the authors bound the fluctuations of the energy function, ensuring that the global properties of the landscape hold with high probability.

Key Results

The paper provides three landmark theorems that formalize the relationship between TAP free energy and Bayesian inference:

  1. Rigorous Complexity Bounds (Theorem 1.1): The authors establish the first rigorous upper bound on the expected number of critical points for the SK model with a ferromagnetic bias. This confirms long-standing predictions made by physicists using the non-rigorous "replica method."
  2. TAP Success in the High-Signal Regime (Theorem 1.2): The central result proves that for a sufficiently high signal-to-noise ratio ($\lambda > \lambda_0$), any local minimizer of the TAP free energy with sufficiently low energy is asymptotically equivalent to the Bayes-optimal estimator. As the system size $n \to \infty$, the distance between the TAP minimizer and the posterior mean vanishes.
  3. Failure of Naive Mean Field (Theorem 1.3): The authors formally prove that the MF energy landscape is fundamentally flawed for this problem. Even under conditions of very strong signals, the critical points of the MF energy do not converge to the Bayes-optimal solution.

Implications and Future Directions

These results provide a firm theoretical foundation for Approximate Message Passing (AMP) algorithms. AMP iterations are essentially a dynamical way to find the stationary points of the TAP free energy; this work confirms that the points AMP seeks are indeed the correct ones for optimal estimation.

However, several questions remain. The current proof requires the signal-to-noise ratio $\lambda$ to be a sufficiently large constant. Whether these results hold all the way down to the information-theoretic phase transition at $\lambda = 1$ remains an open question. Furthermore, while the paper proves that the minima are optimal, it does not provide a guarantee that simple optimization algorithms will always reach these minima from a random initialization. Extending these rigorous Kac-Rice techniques to more complex models, such as $p$-spin glasses or multi-rank estimation problems, represents the next frontier in this synthesis of statistical physics and high-dimensional inference.

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 `$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