Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

Sampling from high-dimensional, multimodal distributions is a computationally challenging and fundamental task. This talk will focus on a generic family of random instances of such problems described by random quadratic functions on the hypercube, and known as the Sherrington-Kirkpatrick model in statistical physics. I will describe an approximate sampling algorithm which succeeds at high temperature as well as matching low-temperature hardness results from "chaos". Our algorithm uses stochastic localization, which progressively tilts the desired measure towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure. Based on joint work with Ahmed El Alaoui and Andrea Montanari.