On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

Gino Del Ferraro; Chuang Wang; Hai-Jun Zhou; Erik Aurell

doi:10.1088/1742-5468/2016/07/073305

On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

Gino Del Ferraro^*, Chuang Wang, Hai-Jun Zhou, Erik Aurell

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

1 Citation (Scopus)

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	https://doi.org/10.1088/1742-5468/2016/07/073305
Publication status	Published - Jul 2016
MoE publication type	A1 Journal article-refereed

Funding

The authors warmly thank Alejandro Lage-Castellanos and Federico Ricci-Tersenghi for valuable discussions which helped us considerably improve upon a previous draft of the paper. Anonymous Referees are also acknowledged for useful comments during the reviewing process of the manuscript. This research is supported by FP7/2007-2013/grant agreement no 290038 (GDF), by the Swedish Science Council through grant 621-2012-2982 (EA), by the Academy of Finland through its Center of Excellence COIN (EA), and by the Natural Science Foundation of China through grant 11225526 (HJZ). GDF and EA thank the hospitality of KITPC and HJZ thanks the hospitality of KTH.

Keywords

message-passing algorithms
optimization over networks
spin glasses (theory)
cavity and replica method
CLUSTER VARIATION METHOD
METASTABLE STATES
SATISFIABILITY
PROPAGATION
ALGORITHMS

Access to Document

10.1088/1742-5468/2016/07/073305

Cite this

@article{ac35acb10fbd4b49a17bd587fc04d77f,

title = "On one-step replica symmetry breaking in the Edwards-Anderson spin glass model",

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.",

keywords = "message-passing algorithms, optimization over networks, spin glasses (theory), cavity and replica method, CLUSTER VARIATION METHOD, METASTABLE STATES, SATISFIABILITY, PROPAGATION, ALGORITHMS",

author = "\{Del Ferraro\}, Gino and Chuang Wang and Hai-Jun Zhou and Erik Aurell",

year = "2016",

month = jul,

doi = "10.1088/1742-5468/2016/07/073305",

language = "English",

volume = "2016",

journal = "Journal of Statistical Mechanics: Theory and Experiment",

issn = "1742-5468",

publisher = "Institute of Physics Publishing",

number = "7",

}

TY - JOUR

T1 - On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

AU - Del Ferraro, Gino

AU - Wang, Chuang

AU - Zhou, Hai-Jun

AU - Aurell, Erik

PY - 2016/7

Y1 - 2016/7

N2 - 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.

AB - 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.

KW - message-passing algorithms

KW - optimization over networks

KW - spin glasses (theory)

KW - cavity and replica method

KW - CLUSTER VARIATION METHOD

KW - METASTABLE STATES

KW - SATISFIABILITY

KW - PROPAGATION

KW - ALGORITHMS

UR - https://www.scopus.com/pages/publications/85014438156

U2 - 10.1088/1742-5468/2016/07/073305

DO - 10.1088/1742-5468/2016/07/073305

M3 - Article

SN - 1742-5468

VL - 2016

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

IS - 7

M1 - 073305

ER -

On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this