Statistical Physics Approaches to High-Dimensional Learning

These notes cover the second lecture on clustering with approximate message passing (AMP), together with its continuation at the start of Day 3. The running theme is that clustering a Gaussian mixture can be reframed as a planted spin-glass problem, and the cavity method — originally developed for the Sherrington–Kirkpatrick spin glass Thouless et al. (1977) — gives both the optimal achievable accuracy and a practical algorithm (AMP) for achieving it. The analysis follows Lesieur et al. (2016).

A note on perspective for PDE readers. AMP is an iterative algorithm whose exact large-$n$ behaviour is tracked by a scalar recursion called state evolution. The analogy to PDE numerics is this: state evolution is like a CFL-type analysis, but instead of stability it tracks the fixed points and basins of attraction of the algorithm. The “hard phase” — where reconstruction is information-theoretically possible but algorithmically intractable — is analogous to a regime where a numerical method is convergent but with a basin of attraction that shrinks as the mesh is refined.

The accompanying Jupyter notebook (ICTP_day2_notebook.ipynb) is organised into three parts. Part 1 implements the planted SK model, AMP, and state evolution for the rank-one case, and traces the AMP overlap transition around the IT threshold. Part 2 computes the Bethe free entropy as a function of the overlap order parameter for the Rademacher–Bernoulli prior, identifying the four regimes separated by $\lambda_\text{spi} < \lambda_\text{IT} < \lambda_\text{alg}$. Part 3 generalises to rank-$r$ asymmetric matrix estimation and runs Low-rank AMP on sampled GMM data.

Unsupervised Learning¶

The goal of unsupervised learning is to find hidden structure in unlabelled data. Three main families:

• Dimensionality reduction (PCA, t-SNE, autoencoders): represent high-dimensional data in a low-dimensional space that preserves relevant structure.

• Clustering (k-means, GMM): partition data into groups of similar points.

• Generative modelling (diffusion models, LLMs): learn the data distribution $p_\theta(\text{data})$ and sample new examples.

This lecture studies clustering for data drawn from a Gaussian mixture. The three central questions are: when is recovering the cluster memberships (i) information-theoretically (IT) possible, (ii) achievable by a polynomial-time algorithm, and (iii) is there a gap between these thresholds?

Setting Up the Model¶

Throughout, $n$ (dimension) and $m$ (sample size) go to infinity with the rank $r = \mathcal{O}(1)$ and the load $\alpha = m/n = \mathcal{O}(1)$ fixed.

Generative Model¶

Following Lesieur et al. (2016), each data point is drawn as

Here $V_k \in \mathbb{R}^n$ is the (unknown) centroid of cluster $k$, $t_i \in \{1,\ldots,r\}$ is the (unknown) cluster assignment of point $i$, and $u_i$ is observation noise. The signal strength $\rho$ plays the role of an inverse noise level: larger $\rho$ means more separated centroids and easier clustering.

Reformulation as Low-Rank Matrix Factorisation¶

Pack the unknowns into a centroid matrix $V \in \mathbb{R}^{n \times r}$ (columns = centroids) and a one-hot assignment matrix $S \in \{0,1\}^{m \times r}$ (each row has exactly one 1). The observation matrix $X \in \mathbb{R}^{n \times m}$ is:

This is a low-rank-plus-noise problem: recover $V$ and $S$ from a noisy rank-$r$ perturbation of a pure noise matrix. This structure appears throughout applied mathematics — in compressed sensing, matrix completion, community detection — and the physics tools apply to all of them.

Bayesian Posterior¶

Bayes’ rule gives the posterior over unknowns:

where $\mathcal{H}$ is the log-likelihood of observing $X$ given $(S,V)$ and $\mathcal{Z}(X)$ is the partition function. This has exactly the Gibbs-measure structure of Lecture 1: posterior = Boltzmann distribution, negative log-likelihood = energy, data = quenched disorder.

Nishimori Identities¶

In the Bayes-optimal setting (the assumed model perfectly matches the true one), there is a remarkable symmetry between the truth and posterior samples. For any test function $f$:

where $x^*$ is the true signal and $x$ is a sample from the posterior. The key practical consequence: the overlap between a posterior sample and the truth equals the overlap between two independent posterior samples,

In the replica language of Lecture 1, this collapses the two order parameters $m$ and $q$ into one, substantially simplifying the saddle-point equations. It is analogous to a symmetry that collapses the PDE system from order $2n$ to order $n$.

From Clustering to the Sherrington–Kirkpatrick Model¶

For $r = 1$ the observation matrix is symmetric and the problem reduces to the spiked Wigner model:

With an Ising ($\pm 1$) prior $P_X(x_i) = \frac{1}{2}(\delta_{x_i,1}+\delta_{x_i,-1})$, so $x_i^2 = 1$, the posterior Hamiltonian reduces to

which is precisely the planted Sherrington–Kirkpatrick (SK) Hamiltonian — a disordered ferromagnet with couplings $J_{ij} \propto Y_{ij}$ that contain a hidden rank-one signal $\sqrt{\lambda/n}\,x_i^*x_j^*$ planted in the noise. The pure SK model (no planted signal) was solved by the replica method Thouless et al. (1977)Mézard et al. (1987); here the structure is richer because the disorder is correlated.

The Cavity Method¶

The cavity method is an alternative to replicas that gives the same saddle-point equations but with a more algorithmic flavour. The idea is to ask: what is the marginal distribution of a single spin $x_0$ given all the others?

Step 1 (cavity field). Remove spin $x_0$ from an $n$-spin equilibrium system. The field it receives from the remaining spins is

This is a sum of $n-1$ weakly correlated terms; by the central limit theorem it converges as $n\to\infty$ to a Gaussian:

where $q = \frac{1}{n}\sum_i \langle x_i \rangle^2$ is the self-overlap of the posterior. This Gaussian approximation is the cavity assumption; it becomes exact as $n \to \infty$ due to the weak correlations between different spins.

Step 2 (self-consistency). Using the Nishimori identity $m = q$, the self-consistent state evolution fixed-point equation is:

where the expectation is over $z \sim \mathcal{N}(0,1)$ and $x_0^* = \pm 1$ uniformly. This is a scalar equation in one unknown $m \in [0,1]$; its fixed points and their stability determine whether the algorithm can recover the signal. The equation has the structure of a mean-field self-consistency equation — identical in spirit to those arising in continuum limits of interacting particle systems or mean-field PDEs.

From the Cavity Method to AMP¶

The cavity recursion suggests an iterative algorithm. Define the denoiser (posterior mean of $x$ given a Gaussian observation):

For the Ising prior, $\eta(A,B) = \tanh(B)/(1 + A\tanh(B)^2)$ approximately. The naive iteration of cavity equations suffers from a feedback problem: spin $i$’s own influence returns through its neighbours, causing double-counting. Correcting for this with a first-order Taylor expansion gives the Onsager correction term, and collecting everything yields Approximate Message Passing (AMP):

The Onsager correction removes the self-feedback of each spin, restoring the validity of the cavity (Gaussian) approximation at each step. Without it the algorithm diverges; with it the trajectory is described exactly in the $n \to \infty$ limit by the scalar state evolution recursion. This is a uniquely strong theoretical guarantee: in contrast to most iterative numerical methods where convergence analysis is approximate, AMP’s trajectory is provably tracked by a deterministic scalar map.

TAP equations. The fixed points of AMP are the solutions of the Thouless–Anderson–Palmer (TAP) equations Thouless et al. (1977):

These are the cavity-corrected mean-field equations; they coincide with the saddle-point equations of the replica calculation — a strong cross-check of both methods.

Low-Rank AMP for Clustering GMMs¶

The rank-one AMP extends straightforwardly to rank-$r$ asymmetric clustering by replacing scalars with length-$r$ vectors and matrices, giving the Low-rank AMP (Low-rAMP) algorithm of Lesieur et al. (2016). Low-rAMP achieves the Bayes-optimal MMSE and runs in time linear in the data size per iteration.

The Bethe Free Entropy¶

(Day 3 continuation.)

The cavity method gives fixed-point equations, but a single scalar potential — the Bethe free entropy — whose extremisation reproduces them also unlocks the full phase diagram.

Definition:

Derivation via telescoping. Write $\frac{1}{n}\log Z_n$ as a Cesàro mean of single-spin increments $\log(Z_i/Z_{i-1})$. By self-averaging, each increment has the same limiting value:

Using the CLT approximation for the cavity field and Stein’s lemma ($\mathbb{E}[g(Z)Z] = \mathbb{E}[g'(Z)]$ for $Z \sim \mathcal{N}(0,1)$) to handle the disorder-average correction term $\mathbb{E}[\xi_{ij}\langle x_i x_j\rangle] = \mathbb{E}[\langle x_i^2 x_j^2\rangle - \langle x_i x_j\rangle^2]$, one arrives at the closed-form expression:

Extremising $\phi_B$ over $m$ (using $m = q$ from Nishimori) recovers the state evolution fixed-point equation. The Bethe free entropy is thus the potential function that AMP implicitly optimises — the analogue of a Lyapunov function for the iteration.

Phase Diagrams and Statistical-to-Computational Gaps¶

The Bethe free entropy as a function of $m$ can have multiple local maxima, corresponding to distinct fixed points of state evolution. The global structure determines the phase diagram.

For $r < r_c = 4 + 2\alpha$ there is no hard phase: the IT and algorithmic thresholds coincide at $\rho_c(\alpha,r) = r/\alpha$. For $r > r_c$ three thresholds separate Lesieur et al. (2016):

The hard phase $\rho_\text{IT} < \rho < \rho_c$ is the regime where:

• The Bethe free entropy has a global maximum at a nontrivial $m > 0$ (so Bayes-optimal recovery is possible).

• But AMP initialised from $m = 0$ converges to the trivial fixed point $m = 0$ (failure to recover).

The hard phase is a statistical-to-computational gap: reconstruction is IT-possible but no known polynomial-time algorithm achieves it from an uninformative initialisation. This is believed (but not proved in general) to be a fundamental obstruction, not an artefact of AMP.

Analogy for PDE readers. Think of the Bethe free entropy landscape as the energy of a nonlinear system with multiple equilibria. The IT threshold is where a nontrivial equilibrium first appears (a saddle-node bifurcation). The algorithmic threshold is where the trivial equilibrium loses stability (a transcritical bifurcation). Between these two thresholds, both equilibria coexist: depending on initialisation, the system converges to one or the other.