mlsanityData to 7 Oct 2026

Convergence for score-based generative modeling with polynomial complexity

arXiv 2206.06227 ↗First posted 13 Jun 2022cs.LG math.PR math.STcited by 176

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Score-based generative modeling (SGM) is a highly successful approach for learning a probability distribution from data and generating further samples. We prove the first polynomial convergence guarantees for the core mechanic behind SGM: drawing samples from a probability density p given a score estimate (an estimate of nabla ln p) that is accurate in L2(p). Compared to previous works, we do not incur error that grows exponentially in time or that suffers from a curse of dimensionality. Our guarantee works for any smooth distribution and depends polynomially on its log-Sobolev constant. Using our guarantee, we give a theoretical analysis of score-based generative modeling, which transforms white-noise input into samples from a learned data distribution given score estimates at different noise scales. Our analysis gives theoretical grounding to the observation that an annealed procedure is required in practice to generate good samples, as our proof depends essentially on using annealing to obtain a warm start at each step. Moreover, we show that a predictor-corrector algorithm gives better convergence than using either portion alone.

Key facts. Cited by 176 papers in the map (data through 7 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 30 of its 43 references that are in the map. First posted on arXiv 13 Jun 2022.

Builds on

30 of 43 references.

Closest ancestors · 8

Same direction, newest first

  1. 2022Subspace Diffusion Generative Models3 May
  2. 2021Score-Based Generative Modeling with Critically-Damped Langevin Diffusion14 Dec
  3. 2021Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling1 Jun
  4. 2021Diffusion Models Beat GANs on Image Synthesis11 May
  5. 2021Maximum Likelihood Training of Score-Based Diffusion Models22 Jan
  6. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  7. 2020Denoising Diffusion Probabilistic Models19 Jun
  8. 2020Improved Techniques for Training Score-Based Generative Models16 Jun

Other references · 22

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  3. 2016Density estimation using Real NVPcited by 2,029
  4. 2021SDEdit: Guided Image Synthesis and Editing with Stochastic Differential Equationscited by 1,903
  5. 2019An Introduction to Variational Autoencoderscited by 997
  6. 2019Plug and Play Language Models: A Simple Approach to Controlled Text Generationcited by 793
  7. 2021Solving Inverse Problems in Medical Imaging with Score-Based Generative Modelscited by 514
  8. 2019Your Classifier is Secretly an Energy Based Model and You Should Treat it Like Onecited by 402
  9. 2019Sliced Score Matching: A Scalable Approach to Density and Score Estimationcited by 381
  10. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  11. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  12. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
10 more
  1. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  2. 2016Energy-based Generative Adversarial Networkcited by 119
  3. 2020Generative Modeling with Denoising Auto-Encoders and Langevin Samplingcited by 118
  4. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  5. 2019Theoretical guarantees for sampling and inference in generative models with latent diffusionscited by 97
  6. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  7. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  8. 2018Non-asymptotic bounds for sampling algorithms without log-concavitycited by 35
  9. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  10. 2021Universal Approximation for Log-concave Distributions using Well-conditioned Normalizing Flowscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 31; 2024: 64; 2025: 43; 2026: 30.

176 papers.

Sort:

By area:

  1. 2023Stochastic Interpolants: A Unifying Framework for Flows and Diffusionscited by 897
  2. 2024SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformerscited by 707
  3. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  4. 2022Convergence of denoising diffusion models under the manifold hypothesiscited by 237
  5. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
  6. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptionscited by 215
  7. 2022Convergence of score-based generative modeling for general data distributionscited by 179
  8. 2023Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Datacited by 171
  9. 2023The probability flow ODE is provably fastcited by 145
  10. 2024Dynamical Regimes of Diffusion Modelscited by 133
  11. 2024An analytic theory of creativity in convolutional diffusion modelscited by 103
  12. 2023Error Bounds for Flow Matching Methodscited by 88
38 more
  1. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Modelscited by 84
  2. 2023DiffFit: Unlocking Transferability of Large Diffusion Models via Simple Parameter-Efficient Fine-Tuningcited by 82
  3. 2024Accelerating Convergence of Score-Based Diffusion Models, Provablycited by 74
  4. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplerscited by 73
  5. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimizationcited by 72
  6. 2024Accelerating Diffusion Sampling with Optimized Time Stepscited by 67
  7. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Modelscited by 64
  8. 2022Statistical Efficiency of Score Matching: The View from Isoperimetrycited by 63
  9. 2023KL Convergence Guarantees for Score diffusion models under minimal data assumptionscited by 61
  10. 2023The Blessing of Randomness: SDE Beats ODE in General Diffusion-based Image Editingcited by 61
  11. 2024Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorialcited by 60
  12. 2024Optimal score estimation via empirical Bayes smoothingcited by 60
  13. 2024Gradient Guidance for Diffusion Models: An Optimization Perspectivecited by 59
  14. 2024Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theorycited by 58
  15. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  16. 2024Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distancescited by 56
  17. 2024Convergence Analysis of Probability Flow ODE for Score-based Generative Modelscited by 56
  18. 2024Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributionscited by 53
  19. 2023How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Controlcited by 50
  20. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptionscited by 48
  21. 2024How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Frameworkcited by 48
  22. 2024Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptionscited by 45
  23. 2024Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformizationcited by 44
  24. 2024Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionalitycited by 44
  25. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  26. 2023Reverse Diffusion Monte Carlocited by 41
  27. 2024Critical windows: non-asymptotic theory for feature emergence in diffusion modelscited by 41
  28. 2023Infinite-Dimensional Diffusion Modelscited by 38
  29. 2023Analysis of learning a flow-based generative model from limited sample complexitycited by 38
  30. 2024Understanding Generalizability of Diffusion Models Requires Rethinking the Hidden Gaussian Structurecited by 38
  31. 2023A Theoretical Justification for Image Inpainting using Denoising Diffusion Probabilistic Modelscited by 37
  32. 2024A Good Score Does not Lead to A Good Generative Modelcited by 36
  33. 2024Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Modelscited by 35
  34. 2023Convergence of flow-based generative models via proximal gradient descent in Wasserstein spacecited by 34
  35. 2023MINDE: Mutual Information Neural Diffusion Estimationcited by 31
  36. 2024Contractive Diffusion Probabilistic Modelscited by 29
  37. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  38. 2024From optimal score matching to optimal samplingcited by 27

50 most cited of 176 All 176 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2026Non-asymptotic Convergence of Stochastic Gradient Descent in Score-based Generative Models
  2. 2023Closed-Form Diffusion Models
  3. 2023Wasserstein Convergence Guarantees for a General Class of Score-Based Generative Models
  4. 2023Preconditioned Score-based Generative Models
  5. 2021Score-based Generative Modeling in Latent Space
  6. 2022Score-Based Generative Models Detect Manifolds
  7. 2024Score-based Generative Models with Adaptive Momentum
  8. 2022Wavelet Score-Based Generative Modeling