# Algorithmic Thresholds in Mean Field Spin Glasses

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2020.

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

- [Injectivity of ReLU networks: perspectives from statistical physics](https://mlsanity.com/paper/2302.14112/) (2023)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Jailbreak Scaling Laws for Large Language Models: Polynomial-Exponential Crossover](https://mlsanity.com/paper/2603.11331/) (2026)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)

## Abstract (arXiv)

Optimizing a high-dimensional non-convex function is, in general, computationally hard and many problems of this type are hard to solve even approximately. Complexity theory characterizes the optimal approximation ratios achievable in polynomial time in the worst case. On the other hand, when the objective function is random, worst case approximation ratios are overly pessimistic. Mean field spin glasses are canonical families of random energy functions over the discrete hypercube -1,+1N. The near-optima of these energy landscapes are organized according to an ultrametric tree-like structure, which enjoys a high degree of universality. Recently, a precise connection has begun to emerge between this ultrametric structure and the optimal approximation ratio achievable in polynomial time in the typical case. A new approximate message passing (AMP) algorithm has been proposed that leverages this connection. The asymptotic behavior of this algorithm has been analyzed, conditional on the nature of the solution of a certain variational problem. In this paper we describe the first implementation of this algorithm and the first numerical solution of the associated variational problem. We test our approach on two prototypical mean-field spin glasses: the Sherrington-Kirkpatrick (SK) model, and the 3-spin Ising spin glass. We observe that the algorithm works well already at moderate sizes (Ngtrsim 1000) and its behavior is consistent with theoretical expectations. For the SK model it asymptotically achieves arbitrarily good approximations of the global optimum. For the 3-spin model, it achieves a constant approximation ratio that is predicted by the theory, and it appears to beat the `threshold energy' achieved by Glauber dynamics. Finally, we observe numerically that the intermediate states generated by the algorithm have the properties of ancestor states in the ultrametric tree.