Optimization of the Sherrington-Kirkpatrick Hamiltonian

Andrea Montanari
Professor, Department of Electrical Engineering, Department of Statistics Stanford University

This lecture is in conjunction with the LIDS Student Conference.

Abstract: Let A be n × n symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing x^T Ax over binary vectors with ±1 entries. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any > 0, outputs a feasible solution that is at least 1 − of the optimum value, with probability converging to one as n goes to infinity. The algorithm’s time complexity is 0(n²). It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the celebrated Thouless-Anderson-Palmer equations.

Biography: Andrea Montanari received a Laurea degree in Physics in 1997, and a Ph. D. in Theoretical Physics in 2001 (both from Scuola Normale Superiore in Pisa, Italy). He has been post-doctoral fellow at Laboratoire de Physique Théorique de l’Ecole Normale Supérieure (LPTENS), Paris, France, and the Mathematical Sciences Research Institute, Berkeley, USA. Since 2002 he is Chargé de Recherche (with Centre National de la Recherche Scientifique, CNRS) at LPTENS. In September 2006 he joined Stanford University as a faculty, and since 2015 he is Full Professor in the Departments of Electrical Engineering and Statistics.

He was co-awarded the ACM SIGMETRICS best paper award in 2008. He received the CNRS bronze medal for theoretical physics in 2006, the National Science Foundation CAREER award in 2008, the Okawa Foundation Research Grant in 2013, and the Applied Probability Society Best Publication Award in 2015. He is an Information Theory Society distinguished lecturer for 2015-2016. In 2016 he received the James L. Massey Research & Teaching Award of the Information Theory Society for young scholars. In 2018 he was an invited sectional speaker at the International Congress of Mathematicians.

MIT Statistics and Data Science Center host guest lecturers from around the world in this weekly seminar.