Fall 2020

Incremental Approximate Message Passing

Monday, September 21st, 2020 11:45 am12:45 pm

Add to Calendar


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.