The SK model with a sparse variance profile: free energy and AMP algorithm for TAP equations at high temperature

This paper derives an asymptotic equivalent of the free energy and estimates the spin vector mean via an AMP algorithm for a generalized sparse Sherrington-Kirkpatrick spin glass model at high temperatures, adapting dynamical approaches originally developed for the classical SK model.

The Gist

Imagine a giant, chaotic dance floor filled with $n$ dancers. Each dancer can only face one of two directions: Left (representing a spin of -1) or Right (representing a spin of +1). This is the world of the Ising model, a classic way physicists try to understand how magnets work or how complex systems behave.

In the famous Sherrington-Kirkpatrick (SK) model, every single dancer is connected to every other dancer. They all influence each other equally, like a crowded room where everyone is shouting at everyone else. This creates a very complex, "spaghetti-like" web of interactions.

This paper introduces a new, more flexible version of that dance floor. Here, the connections aren't necessarily equal or universal. Some dancers are connected to many others, some to few, and the strength of their connection depends on a specific "variance profile" (a map of who talks to whom and how loudly). This map can be sparse, meaning most dancers only talk to a few neighbors, like a social network where you only interact with your close friends rather than the whole world.

Here is what the author, Walid Hachem, achieved in this paper, explained simply:

1. The Big Picture: Predicting the "Mood" of the System

The first goal was to calculate the Free Energy. In physics, think of this as the system's "overall mood" or stability. It tells you how likely the system is to settle into a calm state versus a chaotic one.

• The Challenge: Usually, to calculate this mood, you need to know the exact structure of the connections. If the connections are messy or sparse, the math gets incredibly hard.
• The Solution: The author proved that at high temperatures (think of the dancers moving fast and randomly, ignoring subtle whispers), you can predict the system's mood with a simple formula.
• The Surprise: It doesn't matter how the connections are arranged (whether they are sparse, dense, or random). As long as the temperature is high enough, the "mood" of this new, messy model looks exactly like the "mood" of the old, simple model. The specific shape of the connection map fades into the background.

2. The Algorithm: The "Gossip" Machine (AMP)

The second goal was to figure out what direction each dancer is facing on average. This is called the mean spin vector.

In the old, simple model, physicists use a clever trick called the TAP equations to guess the answer. To solve these equations, they use an AMP (Approximate Message Passing) algorithm.

• The Metaphor: Imagine a game of "Telephone." You start with a guess about the dance floor. Then, you ask each dancer, "What do your neighbors think?" You update your guess based on their answers. Then you ask again.
• The Innovation: The author adapted this "Telephone" game for the new, messy, sparse dance floor. They showed that even with the complex connection map, this iterative gossiping process converges to the correct answer.
• The Result: By running this algorithm enough times, you can accurately predict the average direction of every single dancer, even in a system where most people only talk to a few neighbors.

3. How They Did It: The "Interpolation" Trick

To prove these results, the author used a mathematical technique called Guerra's Interpolation.

• The Analogy: Imagine you want to measure the difficulty of climbing a steep, rocky mountain (the complex sparse model). It's too hard to measure directly. So, you build a smooth, gentle ramp (a simpler, solvable model) that starts at the bottom and slowly morphs into the rocky mountain at the top.
• The author showed that as you slide up this ramp, the "difficulty" (free energy) changes in a predictable way. Because the mountain is "high temperature" (chaotic), the rocky parts don't create unexpected cliffs; the path remains smooth enough to calculate the final height.

4. The "Sparse" Condition

The paper specifically focuses on cases where the number of connections per person ($K_n$) grows as the total number of people ($n$) grows, but remains much smaller than $n$.

• Why it matters: This models real-world networks (like social media or neural networks) where you don't know everyone. The paper proves that even in these "sparse" networks, the laws of physics that govern the simple, fully-connected models still hold true, provided the system is hot enough (chaotic enough) to wash out the specific details of the network structure.

Summary

In short, this paper says: "Even if you have a messy, sparse, and irregular network of interactions, if the system is chaotic enough (high temperature), you can still predict its overall behavior and the state of its individual parts using the same simple tools we use for perfectly organized systems."

The author provided the mathematical proof that these tools (Free Energy formulas and the AMP algorithm) work just as well for this messy, sparse world as they do for the classic, perfectly connected world.

Technical Summary

1. Problem Statement and Motivation

The paper addresses the Sherrington-Kirkpatrick (SK) model of spin glasses, a fundamental model in statistical physics describing systems with random interactions. While the classical SK model assumes that all spin interactions have identical variance ($1/n$), this work generalizes the model to allow for a general variance profile.

Key Generalizations:

• Variance Profile Matrix ($S^{(n)}$): The interaction matrix $W^{(n)}$ has entries $W^{(n)}_{ij} \sim \mathcal{N}(0, t s^{(n)}_{ij})$, where $S^{(n)} = (s^{(n)}_{ij})$ is a deterministic symmetric matrix with zero diagonal.
• Sparsity and Structure: The variance profile $S^{(n)}$ is allowed to be sparse (many zero entries) and lacks specific structural constraints (e.g., it does not need to be block-structured or positive semi-definite).
• Goals:
  1. Derive an asymptotic equivalent for the free energy in the high-temperature regime.
  2. Develop an Approximate Message Passing (AMP) algorithm to estimate the mean spin vector (magnetization) based on the Thouless-Anderson-Palmer (TAP) equations.

2. Mathematical Framework and Assumptions

The model is defined on the space of Ising spins $\Sigma_n = \{-1, +1\}^n$ with the Hamiltonian:
$$H^{(n)}(\sigma) = \frac{1}{2}\sigma^T W^{(n)} \sigma + h (\sigma \cdot \mathbf{1}_n)$$
where $h$ is an external field.

Key Assumptions:

• Assumption 1 (Boundedness & Sparsity): The entries of $S^{(n)}$ are bounded by $C_s K_n^{-1}$, and the maximum row sum norm is finite. $K_n$ is a sequence such that $K_n \to \infty$ and $K_n \leq n$. This covers "sparse" models where non-zero entries per row are $O(K_n)$.
• Assumption 2 (High Temperature): The inverse temperature parameter $t$ satisfies $t < \frac{\log 2}{\|S^{(n)}\|_{\text{row}}}$. This ensures the system is in a high-temperature phase where the Gibbs measure is unique and correlations decay.
• Assumption 3 (Strong Sparsity): For the AMP analysis, the number of non-zero entries per row is bounded by $C_{\text{card}} K_n$, and $K_n \geq \log n$.

3. Methodology

The paper employs a rigorous probabilistic and analytical approach, adapting techniques from statistical physics and random matrix theory.

A. Free Energy Analysis

• Guerra's Interpolation: The authors use Guerra's interpolation method to bound the free energy. They define an interpolated Hamiltonian $H_u(\sigma)$ connecting the target system ($u=1$) to a tractable reference system ($u=0$).
• Stochastic Calculus: Adapting the approach of Adhikari et al. (2021), the authors use Itô's lemma and Gaussian integration by parts to analyze the covariance structure of the spins.
• Key Lemma: They prove that the squared covariance between distinct spins, $E[m_{ij}^2]$, scales as $O(1/K_n)$. This decay is crucial for showing that the "annoying" terms in the interpolation vanish asymptotically, even without assuming $S^{(n)}$ is positive semi-definite.

B. Approximate Message Passing (AMP)

• TAP Equations: The mean spin vector $m = \langle \sigma \rangle$ is approximated using the TAP equations. In the classical SK model, this leads to a fixed-point iteration. Here, the authors generalize this to the variance profile setting.
• Algorithm Construction:
  1. Scalar Fixed Point: First, they solve a vector fixed-point equation $q^{(n)} = t S^{(n)} g(q^{(n)})$, where $g(x) = \mathbb{E}[\tanh^2(\sqrt{x}\xi + h)]$.
  2. Iterative Scheme: They construct an AMP algorithm (Equation 4) that iteratively updates the spin estimates $x^{(n), l}$.
  3. Onsager Correction: The algorithm includes a specific Onsager correction term involving $\text{diag}(t S^{(n)} \mathbf{1}_n - q^{(n), l+1})$ to account for the correlations induced by the variance profile.
• Proof Technique: The convergence proof relies on a "state evolution" analysis. The authors approximate the non-linear $\tanh$ function with polynomials and utilize Non-Backtracking (NB) tree expansions to track the dependencies between iterations. They show that the difference between the AMP iterates and the true magnetization vanishes as $n \to \infty$ and iterations $k \to \infty$.

4. Key Contributions and Results

1. Asymptotic Free Energy (Theorem 2)

The paper derives a precise asymptotic formula for the free energy density $F_n = \frac{1}{n} \mathbb{E}[\log Z^{(n)}]$:
$$F_n \approx \log 2 + \frac{1}{n} \sum_{i=1}^n \mathbb{E} \left[ \log \cosh(\sqrt{q^{(n)}_i} \xi + h) \right] + \frac{t}{4n} \left( \mathbf{1}_n - g(q^{(n)}) \right)^T S^{(n)} \left( \mathbf{1}_n - g(q^{(n)}) \right)$$

• Significance: This result holds for any variance profile $S^{(n)}$ (including indefinite and sparse matrices) as long as the high-temperature condition is met. It generalizes previous results limited to multi-species models with block structures or positive semi-definite matrices.

2. Corollaries for Specific Cases

• Doubly Stochastic Case: If $S^{(n)}$ is doubly stochastic, the result recovers the classical SK free energy expression.
• Banded Toeplitz: The results apply to models with interactions decaying over distance (banded matrices), relevant for physical systems with finite-range interactions.

3. AMP Algorithm Convergence (Theorem 5)

The paper proves that the proposed AMP algorithm converges to the true mean spin vector in the high-temperature regime:
$$\lim_{k \to \infty} \limsup_{n \to \infty} \mathbb{E} \left[ \| m^{(n)} - \tanh(x^{(n), k}) \|_n^2 \right] = 0$$

• Significance: This provides a computationally efficient algorithm (linear complexity per iteration) to solve the TAP equations for sparse, structured interaction matrices, extending the applicability of AMP beyond the i.i.d. Gaussian case.

5. Significance and Impact

• Relaxation of Structural Assumptions: Previous literature on SK models with variance profiles often required the matrix to be block-structured (multi-species) or positive semi-definite. This paper removes the positive semi-definite requirement and handles general sparse structures, significantly broadening the class of solvable models.
• Sparse Graph Inference: The results are directly applicable to graph inference problems (e.g., community detection on sparse graphs) and low-rank matrix estimation where the noise or interaction structure is not uniform.
• Rigorous AMP Theory: By adapting the stochastic calculus approach of Adhikari et al. to sparse variance profiles, the paper provides a rigorous foundation for using AMP in non-i.i.d. settings, bridging the gap between statistical physics and high-dimensional statistics.
• Methodological Innovation: The use of Non-Backtracking tree expansions combined with polynomial approximations of the activation function offers a robust framework for analyzing the dynamics of message-passing algorithms on sparse graphs.

In summary, this work provides a comprehensive theoretical framework for understanding and computing the properties of spin glasses with general, sparse interaction profiles, offering both a free energy formula and a convergent algorithm for state estimation in the high-temperature regime.