Abstract
We consider a one-step replica symmetry breaking description of the Edwards-Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a generalized belief propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter y, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to the Bethe approximation case for tree-like graphs, where it has been shown that 1RSB belief propagation equations admit a survey propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of generalized survey propagation equations for the single instance graph case.
Original language | English |
---|---|
Article number | 073305 |
Number of pages | 32 |
Journal | Journal of Statistical Mechanics: Theory and Experiment |
Volume | 2016 |
Issue number | 7 |
DOIs | |
Publication status | Published - Jul 2016 |
MoE publication type | A1 Journal article-refereed |
Keywords
- message-passing algorithms
- optimization over networks
- spin glasses (theory)
- cavity and replica method
- CLUSTER VARIATION METHOD
- METASTABLE STATES
- SATISFIABILITY
- PROPAGATION
- ALGORITHMS