Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization

We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no external field, and study the problem of sampling from the Gibbs distribution $\mu$ in polynomial time. We prove that, for any inverse temperature $\beta\lt 1/2$, there exists an algorithm with complexity $O(n^{2})$ that samples from a distribution $\mu^{\text{als}}$ which is close in normalized Wasserstein distance to $\mu$. Namely, there exists a coupling of $\mu$ and $\mu^{\text{alg}}$ such that if $(x,x^{\text{als}})\in\{-1,+1\}^{n}\times\{-1,+1\}^{n}$ is a pair drawn from this coupling, then $n^{-1}\mathbb{E}\{\|x-x^{\text{ald}}\|_{2}^{2}\}=o_{n}(1)$. The best previous results, by Bauerschmidt and Bodineau [BB19] and by Eldan, Koehler, Zeitouni [EKZ21], implied efficient algorithms to approximately sample (under a stronger metric) for $\beta\lt 1/4$. We complement this result with a negative one, by introducing a suitable “stability” property for sampling algorithms, which is verified by many standard techniques. We prove that no stable algorithm can approximately sample for $\beta$>1, even under the normalized Wasserstein metric. Our sampling method is based on an algorithmic implementation of stochastic localization, which progressively tilts the measure $\mu$ towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure.