Abstract:
A graphical model is a bipartite graph--some of whose vertices represent random variables, and some of whose vertices represent factors. Each factor is an arbitrary function of the variables to which it is connected by edges. The model is interpreted as a probability distribution over all possible assignments of values to the variables (vertices). The distribution factors as a product of the factor vertices.
Gibbs sampling is a well-established Monte Carlo Markov Chain used to sample from the joint distribution. The chain is known to converge (or mix) in the limit to the joint distribution. However, for many graphs and distributions, the convergence may be slow. In this paper, the authors prove that when a particular width parameter--which the authors introduce as hierarchy width--is bounded, and when the factors satisfy a certain natural property, the convergence time (or mixing time) of Gibbs sampling is polynomial in the size of the graph.
This paper appeared in NeurIPS 2015, and the arxiv link is: https://arxiv.org/abs/1510.00756