mlsanityData to 14 Oct 2026

Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion

arXiv 2402.17886 ↗First posted 27 Feb 2024stat.ML cs.LG math.PRcited by 19

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

This paper considers the problem of sampling from non-logconcave distribution, based on queries of its unnormalized density. It first describes a framework, Denoising Diffusion Monte Carlo (DDMC), based on the simulation of a denoising diffusion process with its score function approximated by a generic Monte Carlo estimator. DDMC is an oracle-based meta-algorithm, where its oracle is the assumed access to samples that generate a Monte Carlo score estimator. Then we provide an implementation of this oracle, based on rejection sampling, and this turns DDMC into a true algorithm, termed Zeroth-Order Diffusion Monte Carlo (ZOD-MC). We provide convergence analyses by first constructing a general framework, i.e. a performance guarantee for DDMC, without assuming the target distribution to be log-concave or satisfying any isoperimetric inequality. Then we prove that ZOD-MC admits an inverse polynomial dependence on the desired sampling accuracy, albeit still suffering from the curse of dimensionality. Consequently, for low dimensional distributions, ZOD-MC is a very efficient sampler, with performance exceeding latest samplers, including also-denoising-diffusion-based RDMC and RSDMC. Last, we experimentally demonstrate the insensitivity of ZOD-MC to increasingly higher barriers between modes or discontinuity in non-convex potential.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 38 of its 62 references that are in the map. First posted on arXiv 27 Feb 2024.

Builds on

38 of 62 references.

Closest ancestors · 9

Same direction, newest first

  1. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  2. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models15 Jun
  3. 2023Denoising Diffusion Samplers27 Feb
  4. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  5. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  6. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  7. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug
  8. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  9. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 29

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  2. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  3. 2021Path Integral Sampler: a stochastic control approach for samplingcited by 181
  4. 2017Stein Variational Gradient Descent as Gradient Flowcited by 152
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  6. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  7. 2023Improved sampling via learned diffusionscited by 104
  8. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 86
  9. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 78
  10. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  11. 2020SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergencecited by 64
  12. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
17 more
  1. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 62
  2. 2021Bayesian Learning via Neural Schr"odinger-F"ollmer Flowscited by 56
  3. 2023Reverse Diffusion Monte Carlocited by 41
  4. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  5. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 30
  6. 2024Stochastic Localization via Iterative Posterior Samplingcited by 28
  7. 2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
  8. 2020On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Methodcited by 23
  9. 2022A Proximal Algorithm for Samplingcited by 22
  10. 2021A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1cited by 21
  11. 2022Regularized Stein Variational Gradient Flowcited by 19
  12. 2022Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chainscited by 16
  13. 2024Faster Sampling without Isoperimetry via Diffusion-based Monte Carlocited by 15
  14. 2023Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimationcited by 10
  15. 2023A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetrycited by 7
  16. 2023Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Samplingcited by 4
  17. 2023Improved Bound for Mixing Time of Parallel Temperingcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 8; 2026: 5.

19 papers.

Sort:

By area:

  1. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  2. 2024Evaluating the design space of diffusion-based generative modelscited by 26
  3. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  4. 2025MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Controlcited by 21
  5. 2025Proximal Diffusion Neural Samplercited by 16
  6. 2025Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyondcited by 11
  7. 2024Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamicscited by 10
  8. 2025Improving the evaluation of samplers on multi-modal targetscited by 9
  9. 2024A Practical Diffusion Path for Samplingcited by 5
  10. 2025On the query complexity of sampling from non-log-concave distributionscited by 5
  11. 2024Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusioncited by 4
  12. 2026Diffusion Path Samplers via Sequential Monte Carlocited by 4
7 more
  1. 2025Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributionscited by 1
  2. 2025Sampling by averaging: A multiscale approach to score estimationcited by 1
  3. 2026Alternating Diffusion for Proximal Sampling with Zeroth Order Queriescited by 1
  4. 2026Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problemscited by 1
  5. 2025Improved sampling algorithms and functional inequalities for non-log-concave distributionscited by 0
  6. 2026Sampling via Stochastic Interpolants by Langevin-based Velocity and Initialization Estimation in Flow ODEscited by 0
  7. 2026Total Variation Guarantees for Sampling with Stochastic Localizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Sublinear iterations can suffice even for DDPMs
  2. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers
  3. 2026Exact Global MCMC with Denoising Diffusion
  4. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
  5. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions
  6. 2026Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
  7. 2026Connections between the F"ollmer process and the denoising diffusion probabilistic model
  8. 2022Denoising MCMC for Accelerating Diffusion-Based Generative Models