Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Download PDF

We study the problem of algorithmically optimizing the Hamiltonian H_N of a spherical or Ising mixed p-spin glass. The maximum asymptotic value \mathsf{OPT} of H_N/N is characterized by a variational principle known as the Parisi formula, proved first by Talagrand and in more generality by Panchenko. Recently developed approximate message passing algorithms efficiently optimize H_N/N up to a value \mathsf{ALG} given by an extended Parisi formula, which minimizes over a larger space of functional order parameters. These two objectives are equal for spin glasses exhibiting a no overlap gap property. However, \mathsf{ALG} < \mathsf{OPT} can also occur, and no efficient algorithm producing an objective value exceeding \mathsf{ALG} is known.
We prove that for mixed even p-spin models, no algorithm satisfying an overlap concentration property can produce an objective larger than \mathsf{ALG} with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the disorder coefficients of H_N. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving \mathsf{ALG} mentioned above. To prove this result, we substantially generalize the overlap gap property framework introduced by Gamarnik and Sudan to arbitrary ultrametric forbidden structures of solutions.