Sampling from Multi-Modal Distributions with Polynomial Query Complexity in Fixed Dimension via Reverse Diffusion
Abstract
Even in low dimensions, sampling from multi-modal distributions is challenging. We provide the first sampling algorithm for a broad class of distributions --- including all Gaussian mixtures --- with a query complexity that is polynomial in the parameters governing multi-modality, assuming fixed dimension. Our sampling algorithm simulates a time-reversed diffusion process, using a self-normalized Monte Carlo estimator of the intermediate score functions. Unlike previous works, it avoids metastability, requires no prior knowledge of the mode locations, and relaxes the well-known log-smoothness assumption which excluded general Gaussian mixtures so far.
Cite
Text
Vacher et al. "Sampling from Multi-Modal Distributions with Polynomial Query Complexity in Fixed Dimension via Reverse Diffusion." Advances in Neural Information Processing Systems, 2025.Markdown
[Vacher et al. "Sampling from Multi-Modal Distributions with Polynomial Query Complexity in Fixed Dimension via Reverse Diffusion." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/vacher2025neurips-sampling/)BibTeX
@inproceedings{vacher2025neurips-sampling,
title = {{Sampling from Multi-Modal Distributions with Polynomial Query Complexity in Fixed Dimension via Reverse Diffusion}},
author = {Vacher, Adrien and Chehab, Omar and Korba, Anna},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/vacher2025neurips-sampling/}
}