Algorithmic Thresholds for Mean-Field Spin Glasses

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, these functions often have many bad local optima which are believed to impede simple algorithms such as gradient descent. In the positive direction, I will discuss 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 ALG may be strictly smaller than OPT. In the negative direction, I will explain why no algorithm with suitably Lipschitz dependence on the random disorder can do better than ALG. The latter result applies to many standard optimization algorithms, including gradient descent and Langevin dynamics on dimension-free time scales.

Based on joint works with Ahmed El Alaoui, Brice Huang, and Andrea Montanari.