- This event has passed.
Sampling from the SK measure via algorithmic stochastic localization
October 28, 2022 @ 11:00 am - 12:00 pm
Ahmed El Alaoui, Cornell University
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.