Name
Title | ||
|---|---|---|
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model |
Abstract | ||
|---|---|---|
We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) λ > 0. For constant Δ, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree Δ when λ <; λ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub>
(Δ). Sly (2010) showed that there is no FPRAS, unless NP=RP, when λ > λ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub>
(Δ). The threshold λ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub>
(Δ) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite Δ-regular tree. The running time of Weitz's algorithm is exponential in log Δ. Here we present an FPRAS for the partition function whose running time is O* (n
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
). We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant Δ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub>
such that for all graphs with maximum degree Δ > Δ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub>
and girth > 7 (i.e., no cycles of length ≤ 6), the mixing time of the Glauber dynamics is O(nlog n) when λ <; λ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub>
(Δ). Our work complements that of Weitz which applies for small constant Δ whereas our work applies for all Δ at least a sufficiently large constant Δ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub>
(this includes Δ depending on n = IVI). Our proof utilizes loopy BP (belief propagation) which is a widely-used algorithm for inference in graphical models. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics, after a short burn-in period, converges close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth ≥ 6 and λ <; λ
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub>
(Δ). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/FOCS.2016.80 | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
Hard-Core model,MCMC,rapid mixing,Belief Propagation,convergence,Gibbs Tree Uniqueness | Conference | abs/1604.01422 |
ISSN | ISBN | Citations |
0272-5428 | 978-1-5090-3934-0 | 9 |
PageRank | References | Authors |
0.55 | 31 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charilaos Efthymiou | 1 | 209 | 15.44 |
| Thomas P. Hayes | 2 | 659 | 54.21 |
| Daniel Štefankovič | 3 | 201 | 16.34 |
| Eric Vigoda | 4 | 747 | 76.55 |
| Yitong Yin | 5 | 213 | 23.42 |