Optimizing Mean Field Spin Glasses with External Field

Abstract

We consider the Hamiltonians of mean-field spin glasses, which are certain random functions $H_N$ defined on high-dimensional cubes or spheres in ${\mathbb{R}}^N$. The asymptotic maximum values of these functions were famously obtained by Talagrand and later by Panchenko and by Chen. The landscape of approximate maxima of $H_N$ is described by various forms of replica symmetry breaking exhibiting a broad range of possible behaviors. We study the problem of efficiently computing an approximate maximizer of $H_N$. We give a two-phase message pasing algorithm to approximately maximize $H_N$ when a no overlap-gap condition holds. This generalizes several recent works by allowing a non-trivial external field. For even Ising spin glasses with constant external field, our algorithm succeeds exactly when existing methods fail to rule out approximate maximization for a wide class of algorithms. Moreover we give a branching variant of our algorithm which constructs a full ultrametric tree of approximate maxima.

References in corpus (24)

• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Clustering of solutions in the random satisfiability problem
• Universality in polytope phase transitions and message passing algorithms
• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• Exact theory of dense amorphous hard spheres in high dimension. III. The full RSB solution
• Complexity of random smooth functions on the high-dimensional sphere
• The Parisi formula has a unique minimizer
• The Parisi formula for mixed $p$-spin models
• Local algorithms for independent sets are half-optimal
• A Dynamic Programming Approach to the Parisi Functional
• Suboptimality of local algorithms for a class of max-cut problems
• Disorder chaos and multiple valleys in spin glasses
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Spectral gap estimates in mean field spin glasses
• Approximate Ultrametricity for Random Measures and Applications to Spin Glasses
• On the energy landscape of the mixed even $p$-spin model
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• The generalized TAP free energy II
• Algorithmic Thresholds in Mean Field Spin Glasses
• The Overlap Gap Property in Principal Submatrix Recovery
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses

Cited by in corpus (4)

• Classical Annealing of Sherrington-Kirkpatrick Spin Glass Using Suzuki-Kubo Mean-field Ising Dynamics
• On the free energy of vector spin glasses with non-convex interactions
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• On Marginal Stability in Low Temperature Spherical Spin Glasses