Sampling from the SK measure via algorithmic stochastic localization

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.