# Convergence for score-based generative modeling with polynomial complexity

arXiv: https://arxiv.org/abs/2206.06227 · HTML: https://mlsanity.com/paper/2206.06227/

## Key facts

- Cited by 177 papers in the map (data through 14 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.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 30)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [SDEdit: Guided Image Synthesis and Editing with Stochastic Differential Equations](https://mlsanity.com/paper/2108.01073/) (2021)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [Maximum Likelihood Training of Score-Based Diffusion Models](https://mlsanity.com/paper/2101.09258/) (2021)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Solving Inverse Problems in Medical Imaging with Score-Based Generative Models](https://mlsanity.com/paper/2111.08005/) (2021)
- [Your Classifier is Secretly an Energy Based Model and You Should Treat it Like One](https://mlsanity.com/paper/1912.03263/) (2019)
- [Sliced Score Matching: A Scalable Approach to Density and Score Estimation](https://mlsanity.com/paper/1905.07088/) (2019)
- [Score-Based Generative Modeling with Critically-Damped Langevin Diffusion](https://mlsanity.com/paper/2112.07068/) (2021)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Energy-based Generative Adversarial Network](https://mlsanity.com/paper/1609.03126/) (2016)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Theoretical guarantees for sampling and inference in generative models with latent diffusions](https://mlsanity.com/paper/1903.01608/) (2019)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Subspace Diffusion Generative Models](https://mlsanity.com/paper/2205.01490/) (2022)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Non-asymptotic bounds for sampling algorithms without log-concavity](https://mlsanity.com/paper/1808.07105/) (2018)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Universal Approximation for Log-concave Distributions using Well-conditioned Normalizing Flows](https://mlsanity.com/paper/2107.02951/) (2021)

## Built on by (most cited first, 30 of 177)

- [Stochastic Interpolants: A Unifying Framework for Flows and Diffusions](https://mlsanity.com/paper/2303.08797/) (2023)
- [SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformers](https://mlsanity.com/paper/2401.08740/) (2024)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Dynamical Regimes of Diffusion Models](https://mlsanity.com/paper/2402.18491/) (2024)
- [An analytic theory of creativity in convolutional diffusion models](https://mlsanity.com/paper/2412.20292/) (2024)
- [Error Bounds for Flow Matching Methods](https://mlsanity.com/paper/2305.16860/) (2023)
- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [DiffFit: Unlocking Transferability of Large Diffusion Models via Simple Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2304.06648/) (2023)
- [Accelerating Convergence of Score-Based Diffusion Models, Provably](https://mlsanity.com/paper/2403.03852/) (2024)
- [Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers](https://mlsanity.com/paper/2303.03384/) (2023)
- [An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization](https://mlsanity.com/paper/2404.07771/) (2024)
- [Accelerating Diffusion Sampling with Optimized Time Steps](https://mlsanity.com/paper/2402.17376/) (2024)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [KL Convergence Guarantees for Score diffusion models under minimal data assumptions](https://mlsanity.com/paper/2308.12240/) (2023)
- [Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theory](https://mlsanity.com/paper/2403.11968/) (2024)
- [The Blessing of Randomness: SDE Beats ODE in General Diffusion-based Image Editing](https://mlsanity.com/paper/2311.01410/) (2023)
- [Optimal score estimation via empirical Bayes smoothing](https://mlsanity.com/paper/2402.07747/) (2024)
- [Gradient Guidance for Diffusion Models: An Optimization Perspective](https://mlsanity.com/paper/2404.14743/) (2024)
- [Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorial](https://mlsanity.com/paper/2402.07487/) (2024)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Convergence Analysis of Probability Flow ODE for Score-based Generative Models](https://mlsanity.com/paper/2404.09730/) (2024)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions](https://mlsanity.com/paper/2409.02426/) (2024)

## 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.