Sampling from spherical spin glasses: diffusions and simulated annealing

We consider the problem of algorithmically sampling from the Gibbs measure of a spherical mixed p-spin glass. We prove that two algorithms succeed for inverse temperatures up to a "stochastic localization threshold." Our first result shows that algorithmic stochastic localization samples from the Gibbs measure with vanishing total variation error; this improves the guarantee of vanishing Wasserstein error shown in earlier work. Our second result shows that simulated annealing of Langevin dynamics also succeeds. This is proved by a new local-to-global principle for analyzing simulated annealing, and is the first guarantee for a Markov chain in this problem beyond the "uniqueness threshold," where the Langevin dynamics mix slowly from a worst-case initialization. For the pure p-spin models, the inverse temperature we achieve is within an absolute (p-independent) constant of the "shattering transition," the conjectured computational threshold of this problem. Based on joint works with Andrea Montanari, Huy Tuan Pham, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu.