Abstract
We consider the Hamiltonians of mean-field spin glasses, which are certain random polynomials defined on high-dimensional cubes or spheres in N dimensions. Their landscape is highly complex, often containing exponentially many bad local optima. Recently, new algorithms have achieved 1+o(1) multiplicative error for this optimization problem assuming absence of the "overlap gap property". In the other direction, Gamarnik, Jagannath, and Wein have shown that natural classes of algorithms fail at this task when the overlap property holds.
We will explain a new result with Brice Huang characterizing the optimal asymptotic value achievable by a natural class of algorithms. In particular, we show that no algorithm in this class can outperform the algorithms recently proposed in [Subag 18], [Montanari 19], [El Alaoui, Montanari, S 2020], [S 21] as long as the objective functions under consideration have only even degree terms. The proof is based on a branching tree version of the overlap gap property, and the full strength of our branching tree obstruction is in some sense necessary to establish the algorithmic threshold. Our result applies for instance to gradient descent, approximate message passing, and Langevin dynamics, all run for a dimension-free number of iterations or amount of time. The algorithmic threshold value, previously identified in [El Alaoui, Montanari, S 2020], is a generalization of the Parisi variational formula for the true maximum value obtained by minimizing over a larger family of functional order parameters.