Fall 2020

Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

Tuesday, Jan. 11, 2022 9:30 am10:20 am PST

Add to Calendar


Ahmed El Alaoui (Cornell University)


Calvin Lab Auditorium

We propose an algorithm which efficiently samples from the SK measure with no external field at all inverse temperatures beta < 1/2.  The approach uses a discretized version of the Stochastic Localization (SL) process of Eldan (2013), and the analysis relies on a comparison with a planted model combined with a new information-theoretic interpretation of the SL process. We believe this algorithm should succeed for all beta<1. Finally, we show that due to disorder chaos, 'stable' algorithms cannot approximately sample from the SK measure for beta>1. This result, which pertains to sampling, parallels the use of the overlap gap property to show algorithmic impossibility results for random optimization problems.
This is a joint work with Andrea Montanari and Mark Sellke.