Research map / Learning theory and algorithms / Sample complexity
Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a reverse-diffusion sampler whose intermediate scores are estimated by a self-normalized Monte Carlo estimator using only query access to the potential V, giving polynomial query complexity in fixed dimension for general Gaussian mixtures.
Problem
Sampling from multi-modal distributions (e.g. general Gaussian mixtures) with query complexity polynomial in the multi-modality parameters, in fixed dimension, without log-smoothness or prior knowledge of mode locations.
Approach
Combine reverse diffusion with a correlated self-normalized importance-sampling estimator of the intermediate scores (using Gaussian samples only), under a semi-log-convexity and dissipativity assumption that general Gaussian mixtures satisfy, with non-asymptotic quadratic error control.
Key results
- Theorem gives E[KL] ≲ ε β^{d+3}(b+d)/a^2 with O(d ε^{-2(d+2)}) queries to V, polynomial in parameters for fixed d.
- On a 16-mode 2D Gaussian mixture, the proposed method recovers all modes while ULA with 5x10^4 steps does not, at roughly one-minute runtime.
- In the 3-mode experiment with 10^6 query budget, the method yields the lowest Wasserstein error as the between-mode distance R grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use reverse diffusion with self-normalized importance sampling for score estimation | multi-modal sampling · 16-component Gaussian mixture with unit variance and centers in [-40, 40]^2 | mode recovery | Helped |
| use reverse diffusion with self-normalized importance sampling instead of ULA or RDMC | three-Gaussian mixture with different covariances · Wasserstein distance versus between-mode distance | Wasserstein distance | Helped |
Surprising findings
- Existing ULA-based and Föllmer-flow zeroth-order methods fail to converge on simple Gaussian mixtures in the experiments.
- General Gaussian mixtures can have gradients that are not Hölder continuous, so standard log-smoothness and weak-smoothness assumptions do not cover them.
Limitations
- Dimension-dependent complexity is exponential in d (poly(eps^{-d}) and O(eps^{-2(d+2)})), so only fixed dimension is covered.
- Dissipativity assumption is stronger than finite second moment and excludes heavy-tailed targets.
- Numerical experiments are small-scale (2D), with comparisons limited to ULA and RDMC.
Experimental setup
Datasets: synthetic Gaussian mixtures (16-component 2D, 3-component 2D)
Benchmarks: 16-mode 2D Gaussian mixture 3-mode 2D Gaussian mixture with varying between-mode distance
Metrics: KL divergence (theoretical) Wasserstein distance query complexity
Baselines: ULA RDMC Proposal-based sampling (Dwivedi-style) Föllmer flow zeroth-order method
Builds on: reverse diffusion sampling (Berner et al. / RDMC) Föllmer flows self-normalized importance sampling bounds (Agapiou et al.) Denoising score identity
Closest papers by meaning
- Learned Reference-based Diffusion Sampler for multi-modal distributions (ICLR 2025 · similarity 0.88)
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.88)
- Diffusive Gibbs Sampling (ICML 2024 · similarity 0.88)
- Reverse Diffusion Monte Carlo (ICLR 2024 · similarity 0.88)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.87)
- Particle Denoising Diffusion Sampler (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.