# Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

arXiv: https://arxiv.org/abs/2110.07847 · HTML: https://mlsanity.com/paper/2110.07847/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2021.

## Built on by (most cited first, 9 of 9)

- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Random Function Descent](https://mlsanity.com/paper/2305.01377/) (2023)
- [Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply](https://mlsanity.com/paper/2306.02555/) (2023)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

We study the problem of algorithmically optimizing the Hamiltonian HN of a spherical or Ising mixed p-spin glass. The maximum asymptotic value mathsfOPT of HN/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 HN/N up to a value mathsfALG 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, mathsfALG < mathsfOPT can also occur, and no efficient algorithm producing an objective value exceeding mathsfALG is known. We prove that for mixed even p-spin models, no algorithm satisfying an overlap concentration property can produce an objective larger than mathsfALG with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the disorder coefficients of HN. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving mathsfALG 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.