The Library
Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model [conference item]
Tools
Efthymiou, Charilaos, Hayes, Thomas, Štefankovič, Daniel, Vigoda, Eric and Yin, Yitong (2016) Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model [conference item]. In: 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), New Brunswick, New Jersey, USA, 9-11 Oct 2016. Published in: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) pp. 704-713. ISBN 9781509039333. doi:10.1109/FOCS.2016.80 ISSN 0272-5428.
|
PDF
WRAP-convergence-MCMC-loopy-BP-tree-uniqueness-Efthymiou-2016.pdf - Accepted Version - Requires a PDF viewer. Download (886Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS.2016.80
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 λ <; λ c (Δ). Sly (2010) showed that there is no FPRAS, unless NP=RP, when λ > λ c (Δ). The threshold λ c (Δ) 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 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 Δ 0 such that for all graphs with maximum degree Δ > Δ 0 and girth > 7 (i.e., no cycles of length ≤ 6), the mixing time of the Glauber dynamics is O(nlog n) when λ <; λ c (Δ). Our work complements that of Weitz which applies for small constant Δ whereas our work applies for all Δ at least a sufficiently large constant Δ 0 (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 λ <; λ c (Δ).
Item Type: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Markov processes, Monte Carlo method, Eigenvectors | ||||||||||||||||||
Series Name: | Annual IEEE Symposium on Foundations of Computer Science | ||||||||||||||||||
Journal or Publication Title: | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) | ||||||||||||||||||
Publisher: | IEEE | ||||||||||||||||||
ISBN: | 9781509039333 | ||||||||||||||||||
ISSN: | 0272-5428 | ||||||||||||||||||
Official Date: | 15 December 2016 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Page Range: | pp. 704-713 | ||||||||||||||||||
DOI: | 10.1109/FOCS.2016.80 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 13 March 2019 | ||||||||||||||||||
Date of first compliant Open Access: | 19 March 2019 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | New Brunswick, New Jersey, USA | ||||||||||||||||||
Date(s) of Event: | 9-11 Oct 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year