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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 47 references that are in the map.
- First posted on arXiv 13 Aug 2022.

## Builds on (most cited first, 5 of 5)

- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Error Bounds for Sequential Monte Carlo Samplers for Multimodal Distributions](https://mlsanity.com/paper/1509.08775/) (2015)
- [Finite Sample Complexity of Sequential Monte Carlo Estimators](https://mlsanity.com/paper/1803.09365/) (2018)
- [Finite Sample Bounds for Sequential Monte Carlo and Adaptive Path Selection Using the L2 Norm](https://mlsanity.com/paper/1807.01346/) (2018)

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

- [Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems](https://mlsanity.com/paper/2405.06624/) (2024)
- [Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics](https://mlsanity.com/paper/2410.09697/) (2024)
- [Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition](https://mlsanity.com/paper/2405.19553/) (2024)

## Abstract (arXiv)

We prove finite sample complexities for sequential Monte Carlo (SMC) algorithms which require only local mixing times of the associated Markov kernels. Our bounds are particularly useful when the target distribution is multimodal and global mixing of the Markov kernel is slow; in such cases our approach establishes the benefits of SMC over the corresponding Markov chain Monte Carlo (MCMC) estimator. The lack of global mixing is addressed by sequentially controlling the bias introduced by SMC resampling procedures. We apply these results to obtain complexity bounds for approximating expectations under mixtures of log-concave distributions and show that SMC provides a fully polynomial time randomized approximation scheme for some difficult multimodal problems where the corresponding Markov chain sampler is exponentially slow. Finally, we compare the bounds obtained by our approach to existing bounds for tempered Markov chains on the same problems.