About this Event
View mapSpeaker: Mark Sellke (Stanford University)
Title: Algorithmic Thresholds in Mean-Field Spin Glasses
Abstract: I will explain 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 these functions often include many bad local optima which impede optimization by efficient algorithms. In the positive direction, I will explain algorithms based on approximate message passing which asymptotically achieve a value ALG given by an extended Parisi formula. The case ALG=OPT has a "no overlap gap" or "full replica symmetry breaking" interpretation, but in general these algorithms may fail to reach asymptotic optimality. In the negative direction, I will explain why no algorithm with suitably Lipschitz dependence on the random disorder can surpass the threshold ALG. This result applies to many standard optimization algorithms, such as gradient descent and its variants on dimension-free time scales. Based on joint works with Ahmed El Alaoui, Brice Huang, and Andrea Montanari.