Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses

Abstract

We study the problem of algorithmically optimizing the Hamiltonian of a spherical or Ising mean field spin glass. The maximum asymptotic value OPT of this random function 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 these functions up to a value 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, ALG can be strictly smaller than OPT, and no efficient algorithm producing a value exceeding ALG is known. We prove that when all interactions have even degree, no algorithm satisfying an overlap concentration property can produce an objective larger than ALG with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the random disorder coefficients of the objective. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving 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.

Topics & Concepts