A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
arXiv:1102.3305 · doi:10.1103/PhysRevE.84.046706
Abstract
Starting from a Cluster Variational Method, and inspired by the correctness of the paramagnetic Ansatz (at high temperatures in general, and at any temperature in the 2D Edwards-Anderson model) we propose a novel message passing algorithm --- the Dual algorithm --- to estimate the marginal probabilities of spin glasses on finite dimensional lattices. We show that in a wide range of temperatures our algorithm compares very well with Monte Carlo simulations, with the Double Loop algorithm and with exact calculation of the ground state of 2D systems with bimodal and Gaussian interactions. Moreover it is usually 100 times faster than other provably convergent methods, as the Double Loop algorithm.
23 pages, 12 figures. v2: improved introduction
References in corpus (6)
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
- Replica Cluster Variational Method
- Exact Algorithm for Sampling the 2D Ising Spin Glass
- Near optimal configurations in mean field disordered systems
Cited by in corpus (10)
- Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
- Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
- Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
- Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
- Simplifying Generalized Belief Propagation on Redundant Region Graphs
- Cycle-based Cluster Variational Method for Direct and Inverse Inference
- Quantum Cluster Variational Method and Message Passing Algorithms Revisited
- Zero-temperature Monte Carlo simulations of two-dimensional quantum spin glasses guided by neural network states
- Loop-corrected belief propagation for lattice spin models
- Gauge-free cluster variational method by maximal messages and moment matching