Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model

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.