Skip to main content
Browse by:

Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

Event Image
Friday, October 07, 2022
3:30 pm - 4:30 pm
Mark Sellke, Assistant Professor, Dept. of Statistics, Harvard
Statistical Science Seminar

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.