Research map / Probabilistic and scientific modeling / Variational and generative sampling
Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising 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 DDMC, an oracle-based denoising-diffusion Monte Carlo sampler whose score is estimated from conditional samples, and ZOD-MC, which implements that oracle with rejection sampling using only zeroth-order queries to sample non-log-concave targets.
Problem
Sampling from non-log-concave (multimodal, metastable, possibly discontinuous) unnormalized densities using only zeroth-order queries of the potential, without isoperimetric assumptions.
Approach
Estimate the denoising-diffusion score via Monte Carlo over the conditional p_{0|t}, which is an RGO with large step size; implement that RGO by rejection sampling from a Gaussian envelope using the global minimum of V, and prove KL/W2 guarantees for the resulting sampler with no isoperimetry assumption.
Key results
- ZOD-MC attains the lowest MMD and W2 among compared samplers on the asymmetric unbalanced 2D Gaussian mixture under matched oracle complexity.
- ZOD-MC is the least sensitive to mode separation and is the only method that correctly samples all modes of the Muller-Brown potential and the discontinuous Gaussian mixture.
- Theory gives zeroth-order query complexity exp(Otilde(d) log(1/eps)), which has exponential dimension dependence but better epsilon dependence than RDMC/RSDMC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ZOD-MC instead of competing samplers at fixed oracle complexity | 2D asymmetric, unbalanced Gaussian mixture · Gaussian mixtures | MMD | Helped |
| Use ZOD-MC instead of competing samplers at fixed oracle complexity | 2D asymmetric, unbalanced Gaussian mixture · Gaussian mixtures | $W_2$ | Helped |
| Use ZOD-MC rather than other methods as mode separation increases | Gaussian mixture sampler · Gaussian mixtures with increasing mode separation | mode coverage | Helped |
| Use ZOD-MC instead of other methods at fixed function evaluations | Gaussian mixture sampler · Gaussian mixtures across dimensions | $W_2$ | Helped |
| Use ZOD-MC instead of first-order methods for a discontinuous potential | Gaussian mixture sampler · Discontinuous Gaussian mixture | sampling accuracy | Helped |
| Use ZOD-MC instead of other methods | Müller Brown sampler · Müller Brown potential | mode coverage | Helped |
| Use ZOD-MC rather than RDMC or RSDMC for score estimation | Diffusion-based sampler on an unbalanced asymmetric 5D GMM · 5D Gaussian mixture | average $L^2$ score error | Helped |
| Use ZOD-MC instead of RDMC and RSDMC as dimension increases | Diffusion-based sampler · Gaussian mixtures across dimensions | dimension scaling | Mixed |
Surprising findings
- Zeroth-order ZOD-MC yields lower score approximation error than first-order diffusion-based methods RDMC and RSDMC, despite having a worse dimension dependence in theory.
Limitations
- Complexity grows exponentially with dimension (exp(Otilde(d))), so the method is practical mainly for low-dimensional targets.
- Requires an oracle for the global minimum of V; in practice a local minimum found by Newton's method is used.
- Theory requires the growth-type Assumption on V rather than smoothness, and results are only for KL of early-stopped distribution p_delta.
Experimental setup
Benchmarks: Gaussian mixture targets Gaussian mixture with discontinuous potential Muller-Brown potential
Metrics: MMD W2 average L2 score error KL divergence bound
Baselines: RDMC RSDMC SLIPS Proximal Sampler annealed importance sampling sequential Monte Carlo parallel tempering with MALA unadjusted Langevin Monte Carlo
Builds on: Reverse Diffusion Monte Carlo Recursive Score Diffusion Monte Carlo Proximal Sampler denoising diffusion score estimation
Closest papers by meaning
- Reverse Diffusion Sequential Monte Carlo Samplers (NeurIPS 2025 · similarity 0.90)
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.89)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.89)
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.88)
- Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference (NeurIPS 2024 · similarity 0.88)
- Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion (NeurIPS 2025 · similarity 0.88)
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.