2012/11/20 by Yongtao Guan, Guan, Yongtao, Matthew Stephens +1
Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Methodology (stat.ME) #Probability (math.PR) #math.PR #stat.ME
paper · pdf · doi:10.48550/arxiv.1211.4675
24 pages, 3 figures
arxiv created 2012/11/20 · arxiv updated 2012/11/21
When sampling a multi-modal distribution π(x), x∈ \rrd, a Markov chain with local proposals is often slowly mixing; while a Small-World sampler \citepguankrone -- 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 πt(x) ∝ π(x)1/t, 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 td and that of the sampling chain is shrunk by a factor of t-d. Importantly, the spectral gap of the exploring chain depends on the "size" of πt(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 \tk\ follow a geometric progression. If we allow tk → 0, the sampler becomes a global optimizer.