Spring 2016

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Tuesday, May 3, 2016 4:45 pm5:30 pm PDT

Add to Calendar


Calvin Lab

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) \lambda>0.  For constant \Delta, previous work of Weitz (2006)  established an FPTAS for the partition function for graphs of maximum degree \Delta when \lambda<\lambda_c(\Delta). The threshold \lambda_c(\Delta) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite \Delta-regular trees.
Sly (2010) showed that there is no FPRAS, unless NP=RP, when \lambda>\lambda_c(\Delta). The running time of Weitz's algorithm is exponential in  \log{\Delta}. Here we present an FPRAS for the partition function whose running time is O^*(n^2). 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 \Delta_0 such that for all graphs with maximum degree \Delta\geq\Delta_0  and girth \geq 7 (i.e., no cycles of length \leq 6), the mixing time of the Glauber dynamics is O(n\log{n}) when \lambda<\lambda_c(\Delta). Our work complements that of Weitz which applies for small constant \Delta whereas our work applies for all \Delta  at least a sufficiently large constant \Delta_0  (this includes \Delta depending on n=|V|).
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 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 \geq 6 and \lambda<\lambda_c(\Delta)