Results 461 - 470 of 24716

Salil Vadhan

(Harvard University)

Prahladh Harsha

(Tata Institute of Fundamental Research)

Nikhil Srivastava

(Simons Institute, UC Berkeley)

Sitan Chen

(Harvard University)

Molei Tao

(Georgia Tech)

Andrej Risteski

(Carnegie Mellon University)

Andrea Montanari

(Stanford University)

Sinho Chewi

(Yale University)

A new class of algorithms for trajectory inference

Sampling from spherical spin glasses: diffusions and simulated annealing

We consider the problem of algorithmically sampling from the Gibbs measure of a mean field spin glass, a prototypical model of a "disordered" probability measure. We prove that two algorithms succeed at temperatures above a ''stochastic localization threshold'' temperature.
1) Our first result shows that a denoising diffusions-based algorithm samples from the Gibbs measure. This improves the guarantee of this algorithm over previous work, from vanishing Wasserstein to total variation error.
2) Our second result shows that simulated annealing of Langevin dynamics also succeeds, and is proved by a new local-to-global principle for analyzing simulated annealing. This 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 temperature we achieve is within an absolute (p-independent) constant of the ''shattering transition,'' which is 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.