S
Starscream
Text
Polynomial-Query Sampling of Multimodal Distributions via Reverse Diffusion
The first sampling algorithm for a broad class of multimodal distributions - including all Gaussian mixtures - whose query complexity is polynomial in the parameters governing multimodality, assuming fixed dimension. It draws samples by simulating a time-reversed diffusion process using a self-normalized Monte Carlo estimator of the intermediate score functions. Unlike prior approaches it avoids metastability, requires no prior knowledge of the mode locations, and relaxes the standard log-smoothness assumption that had previously excluded general Gaussian mixtures.