Algorithmic Thresholds for Optimizing Mean-Field Spin Glasses
Speaker
Mark Sellke, Stanford University
I will survey recent progress on computing approximate ground states of mean-field spin glass Hamiltonians, which are certain random functions in high dimension. While the asymptotic ground state energy OPT is given by the famous Parisi formula, the landscape of H_N features many bad local optima impeding efficient optimization. In the positive direction, I will explain algorithms based on approximate message passing which achieve asymptotic value ALG given by an extended Parisi formula. The case ALG=OPT has a natural “no overlap gap” interpretation. In the negative direction, I will explain why no algorithm with suitably Lipschitz dependence on H_N can surpass ALG - this includes most standard optimization algorithms on dimension-free time scales. Based on joint works with Ahmed El Alaoui, Brice Huang, and Andrea Montanari.
Mark Sellke’s website
You are invited to a scheduled Zoom meeting.
Topic: Yale S&DS Department Seminar
Time: 4:00pm - 5:00pm
Password: 24
Or Telephone：203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
Meeting ID: 991 6970 0816