Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition
This provides improved theoretical understanding for SMC methods in complex, multimodal scenarios, which is incremental but addresses a known bottleneck in computational statistics.
The paper tackles the problem of analyzing Sequential Monte Carlo (SMC) on multimodal distributions by proving variance bounds that depend on local Markov chain mixing dynamics rather than global ones, showing that efficient theoretical guarantees are possible in truly multimodal settings.
We prove bounds on the variance of a function $f$ under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm, with time complexity depending on local rather than global Markov chain mixing dynamics. SMC is a Markov Chain Monte Carlo (MCMC) method, which starts by drawing $N$ particles from a known distribution, and then, through a sequence of distributions, re-weights and re-samples the particles, at each instance applying a Markov chain for smoothing. In principle, SMC tries to alleviate problems from multi-modality. However, most theoretical guarantees for SMC are obtained by assuming global mixing time bounds, which are only efficient in the uni-modal setting. We show that bounds can be obtained in the truly multi-modal setting, with mixing times that depend only on local MCMC dynamics.