Small World MCMC with Tempering: Ergodicity and Spectral Gap

Original · EN

When sampling a multi-modal distribution π(x), x∈ ᵈ, a Markov chain with local proposals is often slowly mixing; while a Small-World sampler guankrone -- a Markov chain that uses a mixture of local and long-range proposals -- is fast mixing. However, a Small-World sampler suffers from the curse of dimensionality because its spectral gap depends on the volume of each mode. We present a new sampler that combines tempering, Small-World sampling, and producing long-range proposals from samples in companion chains (e.g. Equi-Energy sampler). In its simplest form the sampler employs two Small-World chains: an exploring chain and a sampling chain. The exploring chain samples πₜ(x) ∝ π(x)¹/ᵗ, t∈ [1,∞), and builds up an empirical distribution. Using this empirical distribution as its long-range proposal, the sampling chain is designed to have a stationary distribution π(x). We prove ergodicity of the algorithm and study its convergence rate. We show that the spectral gap of the exploring chain is enlarged by a factor of tᵈ and that of the sampling chain is shrunk by a factor of t⁻ᵈ. Importantly, the spectral gap of the exploring chain depends on the "size" of πₜ(x) while that of sampling chain does not. Overall, the sampler enlarges a severe bottleneck at the cost of shrinking a mild one, hence achieves faster mixing. The penalty on the spectral gap of the sampling chain can be significantly alleviated when extending the algorithm to multiple chains whose temperatures {tₖ} follow a geometric progression. If we allow tₖ → 0, the sampler becomes a global optimizer.