Talks
Fall 2020
Incremental Approximate Message Passing
Monday, September 21st, 2020, 11:45 am–12:45 pm
Speaker:
Ahmed El Alaoui, Stanford University
I will describe a novel algorithmic approach for computing approximate ground states and free energies of mean-field spin glasses at low temperature. The algorithm is incremental in nature, and the sequence of iterates it produces has a scaling limit described by a stochastic control problem. The dual, in the sense of convex programming, of this control problem is an extension of the Parisi formula. We will show that this approach achieves optimality if the model has "no overlap gap", also known as "full replica symmetry breaking" in the physics literature.