Message passing and Monte Carlo algorithms: connecting fixed points with metastable states

Abstract

Mean field-like approximations (including naive mean field, Bethe and Kikuchi and more general Cluster Variational Methods) are known to stabilize ordered phases at temperatures higher than the thermodynamical transition. For example, in the Edwards-Anderson model in 2-dimensions these approximations predict a spin glass transition at finite $T$. Here we show that the spin glass solutions of the Cluster Variational Method (CVM) at plaquette level do describe well actual metastable states of the system. Moreover, we prove that these states can be used to predict non trivial statistical quantities, like the distribution of the overlap between two replicas. Our results support the idea that message passing algorithms can be helpful to accelerate Monte Carlo simulations in finite dimensional systems.

6 pages, 6 figures

References in corpus (17)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Coloring random graphs
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Approximate Inference and Constrained Optimization
• The cavity method at zero temperature
• Glassy dynamics near zero temperature
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Replica Cluster Variational Method
• Sample-to-sample fluctuations of the overlap distributions in the three-dimensional Edwards-Anderson spin glass
• Signature of the Ground-State Topology in the Low-Temperature Dynamics of Spin Glasses
• Belief Propagation and Loop Series on Planar Graphs
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Partition Function Expansion on Region-Graphs and Message-Passing Equations
• Belief-Propagation Guided Monte-Carlo Sampling

Cited by in corpus (5)

• A simple analytical description of the non-stationary dynamics in Ising spin systems
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems
• Loop-corrected belief propagation for lattice spin models
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model