Algorithmic Thresholds in Mean Field Spin Glasses

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.

28 pages; 16 pdf figures

References in corpus (10)

• Message Passing Algorithms for Compressed Sensing
• The structural glass transition and the entropy of the metastable states
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Analysis of the infinity-replica symmetry breaking solution of the Sherrington-Kirkpatrick model
• The Parisi formula has a unique minimizer
• A Dynamic Programming Approach to the Parisi Functional
• Suboptimality of local algorithms for a class of max-cut problems
• Replica-symmetry-breaking transitions and off-equilibrium dynamics
• Following the ground-states of full-RSB spherical spin glasses

Cited by in corpus (9)

• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Gradient descent dynamics in the mixed $p$-spin spherical model: finite size simulation and comparison with mean-field integration
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• On weak ergodicity breaking in mean-field spin glasses
• Optimizing Mean Field Spin Glasses with External Field
• Quenches in the Sherrington-Kirkpatrick model
• On the topology of solutions to random continuous constraint satisfaction problems
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• The Overlap Gap Property limits limit swapping in the QAOA