Sampling from the SK measure via algorithmic stochastic localization
Speaker
Ahmed El Alaoui, Cornell University
The Sherrington-Kirkpatrick measure is a random probability distribution on the hypercube, which is a central object of study in probability theory and in the mean-field theory of disordered statistical physics models.
In this talk I will present an algorithm which efficiently samples from the SK measure with no external field and at high temperature. The approach uses a discretized version of the stochastic localization process of Eldan, together with a subroutine for computing the mean vector, or magnetization, of a family of SK measures tilted by an appropriate external field. This approach is very general and has wide applicability.
Our analysis shows that the algorithm outputs an approximate sample (in a certain weak sense) from the the SK measure, for all inverse temperatures beta < 1/2. In a recent paper, Celentano (2022) shows that our algorithm succeeds up to the critical temperature beta < beta_c = 1.
Conversely, we show that in the ‘low temperature’ phase beta >1, no ‘stable’ algorithm can approximately sample from the SK measure. This exploits a newly established strong version of a property called `disorder chaos’ exhibited by SK in this regime.
The above two results settle the question of 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.
In-person sessions will be held at DL220, with an option of remote participation via zoom.
Password: 24
Or Telephone：203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
Meeting ID: 924 1107 7917