Title: Finite Sample Complexity of Sequential Monte Carlo Estimators,
Abstract: We present bounds for the finite sample error of sequential Monte Carlo
samplers on static spaces. Our approach explicitly relates the performance of
the algorithm to properties of the chosen sequence of distributions and mixing
properties of the associated Markov kernels. This allows us to give the first
finite sample comparison to other Monte Carlo schemes. We obtain bounds for the
complexity of sequential Monte Carlo approximations for a variety of target
distributions including finite spaces, product measures, and log-concave
distributions including Bayesian logistic regression. The bounds obtained are
within a logarithmic factor of similar bounds obtainable for Markov chain Monte
Carlo.