3:00 pm Wednesday, October 5, 2016
Random Structures: Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model by
Charilaos Efthymiou (Goethe University) in RLM 8.136
We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter λ0. For constant Δ, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree Δ when λλc(Δ). The threshold λc(Δ) is the critical point for the phase transition for uniqueness/non-uniqueness on the infinite Δ-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP, when λλc(Δ). 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∗(n2). We analyze the simple single-site Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant Δ0 such that for all graphs with maximum degree Δ≥Δ0 and girth ≥7, the mixing time of the Glauber dynamics is O(nlog(n)) when λλc(Δ). Our work complements that of Weitz which applies for constant Δ whereas our work applies for all Δ≥Δ_0. We utilize loopy BP (belief propagation), a widely-used inference algorithm. 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 converges, after a short burn-in period, 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 λλc(Δ). This is a joint work with Tom Hayes, Daniel Stefankovic, Eric Vigoda and Yitong Yin Submitted by
|
|