Sampling from the SK measure via algorithmic stochastic localization

Abstract: I will present an algorithm which efficiently samples from the Sherrington-Kirkpatrick (SK) measure with no external field at high temperature.

The approach is based on the stochastic localization process of Eldan, together with a subroutine for computing the mean vectors of a family of SK measures tilted by an appropriate external field. This approach is general and can potentially be applied to other discrete or continuous non-log-concave problems.

We show that the algorithm outputs a sample within vanishing rescaled Wasserstein distance to the SK measure, for all inverse temperatures beta < 1/2. In a recent development, Celentano (2022) shows that our algorithm succeeds for all beta < 1, i.e., in the entire high temperature phase.

Conversely, we show that in the low temperature phase beta >1, no ‘stable’ algorithm can approximately sample from the SK measure. In this case we show that the SK measure is unstable to perturbations in a certain sense. This settles the computational tractability of sampling from SK for all temperatures except the critical one.

This is based on a joint work with Andrea Montanari and Mark Sellke.

Bio: Ahmed El Alaoui joined the Statistics and Data Science faculty at Cornell University as an assistant professor in January 2021. He received his PhD in 2018 in Electrical Engineering and Computer Sciences from UC Berkeley, advised by Michael I. Jordan. He was afterwards a postdoctoral researcher at Stanford University, hosted by Andrea Montanari. He is currently a Simons-Berkeley research fellow at the Simons Institute for the Theory of Computing at UC Berkeley. His research interests revolve around high-dimensional phenomena in statistics and probability theory, statistical physics, algorithms, and problems where these areas meet.