Time-complexity of sampling from a multimodal distribution using sequential Monte Carlo
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912813181566976 |
|---|---|
| author | Han, Ruiyu Iyer, Gautam Slepčev, Dejan |
| author_facet | Han, Ruiyu Iyer, Gautam Slepčev, Dejan |
| contents | We study a sequential Monte Carlo algorithm to sample from the Gibbs measure with a non-convex energy function at a low temperature. We use the practical and popular geometric annealing schedule, and use a Langevin diffusion at each temperature level. The Langevin diffusion only needs to run for a time that is long enough to ensure local mixing within energy valleys, which is much shorter than the time required for global mixing. Our main result shows convergence of Monte Carlo estimators with time complexity that, approximately, scales like the fourth power of the inverse temperature, and the square of the inverse allowed error. We also study this algorithm in an illustrative model scenario where more explicit estimates can be given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02763 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time-complexity of sampling from a multimodal distribution using sequential Monte Carlo Han, Ruiyu Iyer, Gautam Slepčev, Dejan Statistics Theory Numerical Analysis Probability Computation Primary: 60J22, Secondary: 65C05, 65C40, 60J05, 60K35 We study a sequential Monte Carlo algorithm to sample from the Gibbs measure with a non-convex energy function at a low temperature. We use the practical and popular geometric annealing schedule, and use a Langevin diffusion at each temperature level. The Langevin diffusion only needs to run for a time that is long enough to ensure local mixing within energy valleys, which is much shorter than the time required for global mixing. Our main result shows convergence of Monte Carlo estimators with time complexity that, approximately, scales like the fourth power of the inverse temperature, and the square of the inverse allowed error. We also study this algorithm in an illustrative model scenario where more explicit estimates can be given. |
| title | Time-complexity of sampling from a multimodal distribution using sequential Monte Carlo |
| topic | Statistics Theory Numerical Analysis Probability Computation Primary: 60J22, Secondary: 65C05, 65C40, 60J05, 60K35 |
| url | https://arxiv.org/abs/2508.02763 |