# Finite Sample Complexity of Sequential Monte Carlo Estimators

arXiv: https://arxiv.org/abs/1803.09365 · HTML: https://mlsanity.com/paper/1803.09365/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2018.

## Built on by (most cited first, 4 of 4)

- [Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions](https://mlsanity.com/paper/2208.06672/) (2022)
- [SMCEvolve: Principled Scientific Discovery via Sequential Monte Carlo Evolution](https://mlsanity.com/paper/2605.15308/) (2026)
- [Multilevel and Sequential Monte Carlo for Training-Free Diffusion Guidance](https://mlsanity.com/paper/2601.21104/) (2026)
- [Agentic Monte Carlo: Simulating Reinforcement Learning for Black-Box Agents](https://mlsanity.com/paper/2606.05296/) (2026)

## Abstract (arXiv)

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.