# Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 29 May 2024.

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

- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Telescoping Density-Ratio Estimation](https://mlsanity.com/paper/2006.12204/) (2020)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition](https://mlsanity.com/paper/1812.00793/) (2018)
- [On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization](https://mlsanity.com/paper/2103.07459/) (2021)
- [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 on Multimodal Target Distributions](https://mlsanity.com/paper/2208.06672/) (2022)

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

- [Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics](https://mlsanity.com/paper/2410.09697/) (2024)
- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition](https://mlsanity.com/paper/2511.00708/) (2025)

## Abstract (arXiv)

We prove bounds on the variance of a function f under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm, with time complexity depending on local rather than global Markov chain mixing dynamics. SMC is a Markov Chain Monte Carlo (MCMC) method, which starts by drawing N particles from a known distribution, and then, through a sequence of distributions, re-weights and re-samples the particles, at each instance applying a Markov chain for smoothing. In principle, SMC tries to alleviate problems from multi-modality. However, most theoretical guarantees for SMC are obtained by assuming global mixing time bounds, which are only efficient in the uni-modal setting. We show that bounds can be obtained in the truly multi-modal setting, with mixing times that depend only on local MCMC dynamics.