Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
This addresses a fundamental challenge in computational statistics and machine learning for applications requiring efficient sampling from complex distributions, representing a significant rather than incremental advance.
The paper tackles the problem of sampling from multi-modal distributions like Gaussian mixtures in fixed dimensions, achieving polynomial query complexity in parameters governing multi-modality without requiring prior knowledge of mode locations or log-smoothness assumptions.
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.