标题： 小世界MCMC与温控：遍历性与谱隙 显示英文标题

标题： Small World MCMC with Tempering: Ergodicity and Spectral Gap

摘要： 当对一个多模态分布 $\pi(x)$, $x\in \rr^d$ 进行采样时，局部提议的马尔可夫链通常混合较慢；而小世界采样器 \citep{guankrone} ——一种使用局部和长程提议混合的马尔可夫链——则能快速混合。 然而，由于其谱隙依赖于每个模式的体积，小世界采样器会受到维度灾难的影响。我们提出了一种新的采样器，结合了退火、小世界采样以及从伴生链（例如等能采样器）中生成长程提议的方法。 在最简单形式下，该采样器采用两个小世界链：探索链和采样链。探索链采样 $\pi_t(x) \propto \pi(x)^{1/t}$, $t\in [1,\infty)$，并构建经验分布。利用此经验分布作为其长程提议，设计采样链使其平稳分布为 $\pi(x)$。我们证明了该算法的遍历性，并研究了其收敛速度。 We show that the spectral gap of the exploring chain is enlarged by a factor of $t^{d}$ 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 $\pi_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 $\{t_k\}$ follow a geometric progression. If we allow $t_k \rightarrow 0$, the sampler becomes a global optimizer. 显示英文摘要

摘要： When sampling a multi-modal distribution $\pi(x)$, $x\in \rr^d$, a Markov chain with local proposals is often slowly mixing; while a Small-World sampler \citep{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 $\pi_t(x) \propto \pi(x)^{1/t}$, $t\in [1,\infty)$, 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 $\pi(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^{d}$ 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 $\pi_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 $\{t_k\}$ follow a geometric progression. If we allow $t_k \rightarrow 0$, the sampler becomes a global optimizer.