Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
Adrien Vacher, Omar Chehab, Anna Korba
Sampling from multi-modal distributions is challenging, even in low dimensions. 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 specific Monte Carlo estimator of the intermediate score functions. Unlike previous works, it avoids metastability, requires no prior knowledge of the mode locations, and does not rely on restrictive smoothness assumptions that exclude general Gaussian mixtures. We illustrate this result on a low-dimensional but challenging multi-modal sampling task, where our algorithm significantly outperforms existing approaches.