The overlap gap property and approximate message passing algorithms for p-spin models
From MaRDI portal
Publication:2227713
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)
Abstract: We consider the algorithmic problem of finding a near ground state (near optimal solution) of a -spin model. We show that for a class of algorithms broadly defined as Approximate Message Passing (AMP), the presence of the Overlap Gap Property (OGP), appropriately defined, is a barrier. We conjecture that when the model does indeed exhibits OGP (and prove it for the space of binary solutions). Assuming the validity of this conjecture, as an implication, the AMP fails to find near ground states in these models, per our result. We extend our result to the problem of finding pure states by means of Thouless, Anderson and Palmer (TAP) based iterations, which is yet another example of AMP type algorithms. We show that such iterations fail to find pure states approximately, subject to the conjecture that the space of pure states exhibits the OGP, appropriately stated, when .
Recommendations
- Universality of approximate message passing algorithms
- A Unifying Tutorial on Approximate Message Passing
- The spin-glass phase-transition in the Hopfield model with \(p\)-spin interactions
- Two solutions to diluted p-spin models and XORSAT problems
- State evolution for general approximate message passing algorithms, with applications to spatial coupling
Cites work
- A CDMA multiuser detection algorithm on the basis of belief propagation
- A dynamic programming approach to the Parisi functional
- Algorithmic thresholds for tensor PCA
- An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
- Bounding flows for spherical spin glass dynamics
- Bounds on the complexity of replica symmetry breaking for spherical spin glasses
- Finding a large submatrix of a Gaussian random matrix
- Free energy of the spherical mean field model
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- Limits of local algorithms over sparse random graphs
- Local algorithms for independent sets are half-optimal
- Low temperature asymptotics of spherical mean field spin glasses
- On properties of Parisi measures
- On the energy landscape of the mixed even \(p\)-spin model
- On the solution-space geometry of random constraint satisfaction problems
- Ordinary differential equations and dynamical systems
- Performance of sequential local algorithms for the random NAE-K-SAT problem
- Random Fields and Geometry
- Some properties of the phase diagram for mixed p-spin glasses
- Spectral gap estimates in mean field spin glasses
- State evolution for approximate message passing with non-separable functions
- 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 algorithmic hardness threshold for continuous random energy models
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The geometry of the Gibbs measure of pure spherical spin glasses
- The Sherrington-Kirkpatrick model
- The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
- Universality in polytope phase transitions and message passing algorithms
- Walksat Stalls Well Below Satisfiability
Cited in
(27)- On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
- Optimization of mean-field spin glasses
- Optimal low-degree hardness of maximum independent set
- Approximate message passing algorithms for rotationally invariant matrices
- Computational barriers to estimation from low-degree polynomials
- Efficient approximation of branching random walk Gibbs measures
- Approximate ground states of hypercube spin glasses are near corners
- Disordered systems insights on computational hardness
- Generalized TAP Free Energy
- Free Energy Wells and Overlap Gap Property in Sparse PCA
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- Optimization algorithms for multi-species spherical spin glasses
- Algorithmic obstructions in the random number partitioning problem
- Optimizing mean field spin glasses with external field
- Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
- A review on quantum approximate optimization algorithm and its variants
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- Tight Lipschitz hardness for optimizing mean field spin glasses
- Un-inverting the Parisi formula
- Shattering in the Ising p-spin glass model
- Bounds on the ground state energy of quantum p-spin Hamiltonians
- Shattering in pure spherical spin glasses
- Overlap gap and computational thresholds in the square wave perceptron
- Disorder chaos in short-range, diluted, and Lévy spin glasses
- Sharp phase transitions for the overlap gap property
- Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT
- Hypergraph counting and fluctuations of mixed p-spin Glass models at high temperature
This page was built for publication: The overlap gap property and approximate message passing algorithms for \(p\)-spin models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227713)
