Finite Sample Bounds for Sequential Monte Carlo and Adaptive Path Selection Using the L2 Norm

We prove a bound on the finite sample error of sequential Monte Carlo (SMC) on static spaces using the L2 distance between interpolating distributions and the mixing times of Markov kernels. This result is unique in that it is the first finite sample convergence result for SMC that does not require an upper bound on the importance weights. Using this bound we show that careful selection of the interpolating distributions can lead to substantial improvements in the computational complexity of the algorithm. This result also justifies the adaptive selection of SMC distributions using the relative effective sample size commonly used in the literature, and we establish conditions guaranteeing the approximation accuracy of the adaptive SMC approach. We show that the commonly used data tempering approach fails to satisfy these conditions, and introduce a modified data tempering algorithm under which our guarantees do hold. We then demonstrate empirically that this procedure provides nearly-optimal sequences of distributions in an automatic fashion for realistic examples.