Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
summary
Analyzes sampling and inference for the hard-core model (independent sets) on graphs, focusing on the tree uniqueness region. Shows convergence guarantees for Glauber dynamics MCMC and for loopy belief propagation, using properties tied to uniqueness on trees to bound mixing and BP fixed-point behavior.
AI-written summary · about
chapters (27)
- 0:00Intro
- 0:24Hard-Core Model
- 1:08Partition function
- 1:33Approximation Algorithms' Approach
- 3:27How well can we approximate
- 5:20Gibbs Uniqueness
- 7:39Deterministic Algorithms
- 9:48Performance Weitz's algorithm
- 10:42Randomized Algorithm
- 11:57The dynamics
- 13:23Our Results
- 15:09O(nlog n) mocing for Random Graphs
- 16:22Belief Propagation on trees
- 19:39(Loopy) Belief Propagation
- 20:26BP Convergence for girth 26
- 25:59Path Coupling for Rapid Mixing
- 27:38Key Results
- 28:45Path Coupling Example
- 31:27Unblocked Neighbors and loopy BP
- 32:12Back to Path Coupling
- 32:42Finding
- 34:06Connections with Loopy BP
- 36:08Covergence from loopy BP
- 38:17Local Uniformity with Loopy BP fixed points
- 39:45Rapid Mixing with uniformity
- 46:44Iterations in space and time
- 49:26Concluding Remarks
related talks
23mDynamic inference in probabilistic graphical models
48mLocally Private Bayesian Inference for Count Models
20mNonparametric Involutive Markov Chain Monte Carlo
01h 27mFlexible Statistical Modeling
24mExact Bayesian Inference for Loopy Probabilistic Programs Using Generating Functions
01h 06mNonparametric Bayesian Methods: Models, Algorithms, and Applications I
35mParameter Estimation For Undirected Graphical Models With Hard Constraints
43mIdentifying Mixtures Of Bayesian Network Distributions