Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions

Approximating integrals with respect to a complicated, highdimensional probability distribution π is an important problem spanning multiple disciplines, such as Bayesian statistical inference, machine learning, statistical physics, and theoretical computer science [13, 17]. Sequential Monte Carlo (SMC) methods are a large class of stochastic approximation algorithms designed to solve these problems by combining Markov chain Monte Carlo (MCMC) methods and resampling strategies to sequentially sample from a series of probability distributions. Some examples of SMC algorithms include population Monte Carlo methods [2], annealed importance sampling [27], sequential particle filters [3], and population annealing [40], among many others [15]. Closely related - but purely MCMC - methods include parallel tempering (PT) [14] and simulated tempering (ST) [23], which have been referred to as population-based MCMC methods [15]. An SMC sampler is generally constructed as follows.