Small-World MCMC with Tempering: Ergodicity, Spectral Gap, and Applications

• Activity Number: 39
• Type: Contributed
• Date/Time: Sunday, August 1, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Yongtao Guan*+ and Matthew Stephens
• Companies: The University of Chicago and The University of Chicago
• Keywords: MCMC ; Small World Sampler ; Tempering ; Nonhomogeneous Markov Chain ; State Decomposition ; Spectal gap

Abstract

We present a novel sampler that is a combination of a small world sampler, whose defining feature is the mixture of local and long-range proposals, and tempering. In its simplest form the sampler employs two small world chains: an exploring chain that samples $\pi(x)^{1/t}$ to build up an empirical distribution, and a sampling chain that samples $\pi(x)$ using the empirical distribution as its long-range proposal. We show that the spectral gap of the exploring chain is increased by a factor of $t^d$ (d is dimension) at the cost of a penalty on the spectral gap of the sampling chain, which is proportional to $t^{-d}$. Overall, the sampler enlarges a severe bottleneck at the cost of shrinking a mild one to achieve faster mixing. The penalty can be significantly alleviated by extending the sampler to multiple chains. Continuing tempering, the sampler becomes a global optimizer.