Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions
Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions
复制标题
多模态目标分布上顺序蒙特卡洛估计器的有限样本复杂度
DOI：
10.1214/23-aap1989
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Schmidler
中科院分区：
文献类型：
--
作者：
Joseph Mathews;S. Schmidler
我们证明了序列蒙特卡罗(SMC)算法的有限样本复杂性，该算法只需要相关马尔可夫核的局部混合时间。当目标分布是多峰分布并且马尔可夫核的全局混合很慢时，我们的界特别有用；在这种情况下，我们的方法建立了SMC相对于相应的马尔可夫链蒙特卡罗(MCMC)估计器的好处。通过顺序控制SMC重采样过程引入的偏差来解决缺乏全局混合的问题。应用这些结果，我们得到了对数凹分布混合情况下逼近期望的复杂性界，并证明了对于马尔可夫链采样器指数慢的一些困难的多峰问题，SMC提供了一个完全多项式时间随机化的逼近方案。最后，我们将我们的方法得到的界与现有的缓和马氏链在相同问题上的界进行了比较。
We prove finite sample complexities for sequential Monte Carlo (SMC) algorithms which require only local mixing times of the associated Markov kernels. Our bounds are particularly useful when the target distribution is multimodal and global mixing of the Markov kernel is slow; in such cases our approach establishes the benefits of SMC over the corresponding Markov chain Monte Carlo (MCMC) estimator. The lack of global mixing is addressed by sequentially controlling the bias introduced by SMC resampling procedures. We apply these results to obtain complexity bounds for approximating expectations under mixtures of log-concave distributions and show that SMC provides a fully polynomial time randomized approximation scheme for some difficult multimodal problems where the corresponding Markov chain sampler is exponentially slow. Finally, we compare the bounds obtained by our approach to existing bounds for tempered Markov chains on the same problems.
影响因子：
1.8
作者：
Beskos, Alexandros;Jasra, Ajay;Thiery, Alexandre
通讯作者：
Thiery, Alexandre