Abstract

This talk focuses on optimizing the random and non-convex Hamiltonians of spherical spin glasses with multiple species. Our main result identifies the best possible value ALG achievable by class of Lipschitz algorithms and gives a matching algorithm in this class based on approximate message passing. The threshold ALG is given by a certain variational problem, which surprisingly may possess multiple optimizers. Our hardness result is proved using the Branching OGP introduced in our previous work [H-Sellke 21] to identify ALG for single-species spin glasses. This and all other OGPs for spin glasses have been proved using Guerra's interpolation method. We introduce a new method to prove the Branching OGP which is both simpler and more robust. It works even for models in which the true maximum value of the objective function remains unknown.

Joint work with Mark Sellke.