Speaker
Description
I will present an algorithm which efficiently samples from the Sherrington-Kirkpatrick measure with no external field at high temperature.
The approach uses a discretized version of the stochastic localization process of Eldan, together with a subroutine for computing the mean vector, or magnetization, of a family of SK measures tilted by an appropriate external field. Our analysis shows that the algorithm outputs a sample with 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 up to the critical temperature beta < 1.
Conversely, we show that in the RSB regime beta >1, no 'stable' algorithm can approximately sample from the SK measure. This crucially exploits the property of disorder chaos exhibited by SK in this regime. 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.
