Optimizing mean field spin glasses with external field

DOI10.1214/23-EJP1066MaRDI QIDQ6186448zbMATH OpenOpenAlexFDO

Authors Mark Sellke

Publication date 2 February 2024

Published in Electronic Journal of Probability (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.03506

zbMATH Keywords

approximate message passingoptimizationspin glasses

Mathematics Subject Classification ID

Gaussian processes (60G15)

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 an 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.

Recommendations

• Optimization of mean-field spin glasses
• Optimization algorithms for multi-species spherical spin glasses
• Optimization on sparse random hypergraphs and spin glasses
• Spherical spin glass model with external field
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models

Cites work

• A dynamic programming approach to the Parisi functional
• Accelerated methods for nonconvex optimization
• Algorithmic pure states for the negative spherical perceptron
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Approximate ground states of hypercube spin glasses are near corners
• Approximate message passing algorithms for rotationally invariant matrices
• Approximate ultrametricity for random measures and applications to spin glasses
• Asymptotic mutual information for the balanced binary stochastic block model
• Average Gromov hyperbolicity and the Parisi ansatz
• Complexity of random smooth functions on the high-dimensional sphere
• Exact theory of dense amorphous hard spheres in high dimension. III: The full replica symmetry breaking solution
• Finding a large submatrix of a Gaussian random matrix
• Finding approximate local minima faster than gradient descent
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Free energy of the spherical mean field model
• Geometry and temperature chaos in mixed spherical spin glasses at low temperature: the perturbative regime
• Hypercontractivity, sum-of-squares proofs, and their applications
• Local algorithms for independent sets are half-optimal
• Low temperature asymptotics of spherical mean field spin glasses
• On multiple peaks and moderate deviations for the supremum of a Gaussian field
• On Nonconvex Optimization for Machine Learning
• On the energy landscape of the mixed even \(p\)-spin model
• On the solution-space geometry of random constraint satisfaction problems
• Optimal low-degree hardness of maximum independent set
• Optimization of mean-field spin glasses
• Parisi formula for the ground state energy in the mixed \(p\)-spin model
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed \(p\)-spin models
• Performance of sequential local algorithms for the random NAE-K-SAT problem
• Random matrices and complexity of spin glasses
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Spectral gap estimates in mean field spin glasses
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Suboptimality of local algorithms for a class of max-cut problems
• The Aizenman-Sims-Starr scheme and Parisi formula for mixed \(p\)-spin spherical models
• The complexity of spherical p-spin models: a second moment approach
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The generalized TAP free energy. II
• The landscape of the spiked tensor model
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• The overlap gap property in principal submatrix recovery
• The Parisi formula
• The Parisi formula for mixed \(p\)-spin models
• The Parisi formula has a unique minimizer
• The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
• Universality in polytope phase transitions and message passing algorithms
• Universality of approximate message passing algorithms

Cited in

(9)

• Optimization of mean-field spin glasses
• Optimization algorithms for multi-species spherical spin glasses
• The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
• Tight Lipschitz hardness for optimizing mean field spin glasses
• On the free energy of vector spin glasses with nonconvex interactions
• Strong topological trivialization of multi-species spherical spin glasses
• Un-inverting the Parisi formula
• On marginal stability in low temperature spherical spin glasses
• Sharp phase transitions for the overlap gap property

This page was built for publication: Optimizing mean field spin glasses with external field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186448)