Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Understand

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.