Generalization of the cavity method for adiabatic evolution of Gibbs states

Abstract

Mean field glassy systems have a complicated energy landscape and an enormous number of different Gibbs states. In this paper, we introduce a generalization of the cavity method in order to describe the adiabatic evolution of these glassy Gibbs states as an external parameter, such as the temperature, is tuned. We give a general derivation of the method and describe in details the solution of the resulting equations for the fully connected p-spin model, the XOR-SAT problem and the anti-ferromagnetic Potts glass (or "coloring" problem). As direct results of the states following method, we present a study of very slow Monte-Carlo annealings, the demonstration of the presence of temperature chaos in these systems, and the identification of a easy/hard transition for simulated annealing in constraint optimization problems. We also discuss the relation between our approach and the Franz-Parisi potential, as well as with the reconstruction problem on trees in computer science. A mapping between the states following method and the physics on the Nishimori line is also presented.

37 pages

References in corpus (63)

• Quantum Annealing in the Transverse Ising Model
• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The Bethe lattice spin glass revisited
• Mean field theory of hard sphere glasses and jamming
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the Out of Equilibrium Relaxation of the Sherrington - Kirkpatrick model
• Thermodynamics of glasses: a first principle computation
• Phase Transitions in the Coloring of Random Graphs
• Recipes for metastable states in Spin Glasses
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Phase diagram of glassy systems in an external field
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• Reconstruction on trees and spin glass transition
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Aging, rejuvenation and memory effects in Ising and Heisenberg spin glasses
• Survey Propagation as local equilibrium equations
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Simplest random K-satisfiability problem
• A ferromagnet with a glass transition
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Statistical mechanics of image restoration and error-correcting codes
• The critical behavior of three-dimensional Ising spin glass models
• Polynomial iterative algorithms for coloring and analyzing random graphs
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Effective potential in glassy systems: theory and simulations
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses
• Focused Local Search for Random 3-Satisfiability
• Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Chaos in temperature in the Sherrington-Kirkpatrick model
• Elusive Glassy Phase in the Random Field Ising Model
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Symmetrical Temperature-Chaos Effect with Positive and Negative Temperature Shifts in a Spin Glass
• Evidences Against Temperature Chaos in Mean Field and Realistic Spin Glasses
• Reconstruction of Random Colourings
• Complexity in Mean-Field Spin-Glass Models: Ising $p$-spin
• Why temperature chaos in spin glasses is hard to observe
• Chaotic temperature dependence in a model of spin glasses
• Potts Glass on Random Graphs
• Random Graph Coloring - a Statistical Physics Approach
• Random subcubes as a toy model for constraint satisfaction problems
• Multispin Ising spin glasses with ferromagnetic interactions
• Marginal States in Mean Field Glasses
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Memory Effect, Rejuvenation and Chaos Effect in the Multi-layer Random Energy Model
• On chaos in mean field spin glasses
• Chaos in Glassy Systems from a TAP Perspective
• Against Chaos in Temperature in Mean-Field Spin-Glass Models
• Against temperature chaos in naive Thouless-Anderson-Palmer equations
• Structural glass on a lattice in the limit of infinite dimensions
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Cavity Method for Supersymmetry Breaking Spin Glasses
• Tap Complexity, the Cavity Method and Supersymmetry
• Off-equilibrium confined dynamics in a glassy system with level-crossing states
• Temperature chaos in a replica symmetry broken spin glass model - A hierarchical model with temperature chaos -

Cited by in corpus (43)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Exact theory of dense amorphous hard spheres in high dimension. II. The high density regime and the Gardner transition
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Following the evolution of glassy states under external perturbations: compression and shear-strain
• On quantum mean-field models and their quantum annealing
• Origin of the computational hardness for learning with binary synapses
• Numerical detection of the Gardner transition in a mean-field glass former
• Following the evolution of glassy states under external perturbations: the full replica symmetry breaking solution
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Nature of excitations and defects in structural glasses
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Spin-glass--like aging in colloidal and granular glasses
• Marginally stable phases in mean-field structural glasses
• Entropy landscape of solutions in the binary perceptron problem
• Performance of simulated annealing in p-spin glasses
• Out-of-equilibrium dynamical equations of infinite-dimensional particle systems. I. The isotropic case
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Biased landscapes for random Constraint Satisfaction Problems
• Mean field stability map of hard-sphere glasses
• Approximate Survey Propagation for Statistical Inference
• The large deviations of the whitening process in random constraint satisfaction problems
• Quasi-equilibrium in glassy dynamics: an algebraic view
• Role of fluctuations in the phase transitions of coupled plaquette spin models of glasses
• Numerical Solution-Space Analysis of Satisfiability Problems
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Replica symmetry breaking, complexity and spin representation in the generalized random energy model
• Introduction to the dynamics of disordered systems: equilibrium and gradient descent
• Following states in temperature in the spherical s+p-spin glass model
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Belief-Propagation Guided Monte-Carlo Sampling
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• Replica analysis of Franz-Parisi potential for sparse systems
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Following the evolution of metastable glassy states under external perturbations: compression and shear-strain