Algorithmic Thresholds in Mean Field Spin Glasses

A. El Alaoui, Andrea MontanariarXiv 2020 · DOI · arXiv

Abstract

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,+1\}^N$. 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 ($N\gtrsim 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.

Introduction

Optimizing high-dimensional, non-convex functions is a central challenge in computational science. While worst-case complexity often suggests these problems are intractable (NP-hard), many real-world and scientific scenarios involve "typical" instances that behave like random landscapes. Mean-field spin glasses serve as the gold standard for studying these random landscapes.

Physicists have long established that the near-optimal states in these models are not randomly distributed but are organized according to an ultrametric structure, resembling a hierarchical family tree. This structure, illustrated in Figure 1, defines how different states overlap and interact across the energy landscape.

The hierarchical organization of states in a mean-field spin glass landscape, showing levels of overlap q.

The Incremental Approximate Message Passing (IAMP) Algorithm

This paper presents the first practical implementation of the Incremental Approximate Message Passing (IAMP) algorithm. Unlike standard AMP, which takes discrete steps, IAMP evolves "incrementally" over a time interval $[0, 1]$. The algorithm's trajectory is guided by parameters derived from solving a variational problem related to the famous Parisi formula.

To implement this in practice, the authors numerically solve the Parisi Partial Differential Equation (PDE) using a Cole-Hopf transform. For finite system sizes, they introduce explicit orthogonalization and normalization steps to maintain numerical stability, ensuring that new search directions are always perpendicular to previous ones.

A core insight of this work is the relationship between the algorithm's progress and the physical structure of the spin glass. As the algorithm runs, its intermediate states correspond to "ancestor states" in the ultrametric tree. It effectively "descends" the hierarchy of states to locate a deep local minimum.

The IAMP algorithm's descent through the state hierarchy, where intermediate states correspond to ancestors in the ultrametric tree.

Experimental Results and Performance

The authors tested the IAMP algorithm on two primary models:

  1. Sherrington-Kirkpatrick (SK) Model: A 2-spin model with a continuous tree of states (no overlap gap). Here, the algorithm successfully reaches the predicted ground state energy of $\approx 0.7631$. As the system size $N$ increases, the error follows a $N^{-2/3}$ scaling law, consistent with random matrix theory expectations.
  2. 3-spin Ising Spin Glass: A more complex model featuring an "overlap gap." In this landscape, the algorithm hits an algorithmic threshold at an energy of $\approx 0.8004$. While this is below the true global optimum ($\approx 0.8132$), it matches theoretical predictions for this class of algorithms and outperforms traditional local search methods like Glauber dynamics (which reaches $\approx 0.788$).

Conclusion

The IAMP algorithm demonstrates that the geometric properties of a landscape—specifically the presence or absence of an overlap gap—dictate the limits of polynomial-time optimization. While the algorithm efficiently reaches the global optimum in models like SK, the "hard gap" in models like the 3-spin Ising glass remains a significant barrier. Future work will explore whether these message-passing techniques can be adapted for broader applications in high-dimensional inference and neural network training.

Summary updated

Abstract

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,+1\}^N$. 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 ($N\gtrsim 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.
BibTeX
@misc{alaoui2020algorithmic,
  author = {A. El Alaoui and Andrea Montanari},
  title = {{Algorithmic Thresholds in Mean Field Spin Glasses}},
  year = {2020},
  eprint = {2009.11481},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.11481},
}
Figure