Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Abstract

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.

arXiv comment84 pages, 2 figures, updated introduction

References in corpus (15)

• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The Parisi formula has a unique minimizer
• Local algorithms for independent sets are half-optimal
• A Dynamic Programming Approach to the Parisi Functional
• Disorder chaos and multiple valleys in spin glasses
• Complexity in Mean-Field Spin-Glass Models: Ising $p$-spin
• High-Dimensional Random Fields and Random Matrix Theory
• Triviality of the geometry of mixed $p$-spin spherical Hamiltonians with external field
• Algorithmic Thresholds in Mean Field Spin Glasses
• Concentration of the complexity of spherical pure $p$-spin models at arbitrary energies
• Optimizing Mean Field Spin Glasses with External Field
• Following the ground-states of full-RSB spherical spin glasses
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Computing the number of metastable states in infinite-range models

Cited by in corpus (1)

• Optimizing Mean Field Spin Glasses with External Field