mlsanityData to 14 Oct 2026

Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization

arXiv 2308.03686 ↗First posted 7 Aug 2023stat.ML cs.LGcited by 235

On the map: Diffusion models → Diffusion foundations and sampling

Abstract (arXiv)

Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming L2-accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or required strong smoothness assumptions. We provide the first convergence bounds which are linear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most tilde O(fracd log2(1/δ)varepsilon2) steps to approximate an arbitrary distribution on ℝd corrupted with Gaussian noise of variance δ to within varepsilon2 in KL divergence. Our proof extends the Girsanov-based methods of previous works. We introduce a refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization.

Key facts. Cited by 235 papers in the map (data through 14 Oct 2026). Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models. Builds on 39 of its 65 references that are in the map. First posted on arXiv 7 Aug 2023.

Builds on

39 of 65 references.

Closest ancestors · 20

Same direction, newest first

  1. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models15 Jun
  2. 2023Error Bounds for Flow Matching Methods26 May
  3. 2023The probability flow ODE is provably fast19 May
  4. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers6 Mar
  5. 2023Diffusion Models are Minimax Optimal Distribution Estimators3 Mar
  6. 2023Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data14 Feb
  7. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  8. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  9. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  10. 2022Let us Build Bridges: Understanding and Extending Diffusion Generative Models31 Aug
  11. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug
  12. 2022Convergence for score-based generative modeling with polynomial complexity13 Jun
8 more
  1. 2022Score-Based Generative Models Detect Manifolds2 Jun
  2. 2022Fast Sampling of Diffusion Models with Exponential Integrator29 Apr
  3. 2021Structured Denoising Diffusion Models in Discrete State-Spaces7 Jul
  4. 2021Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling1 Jun
  5. 2021Diffusion Models Beat GANs on Image Synthesis11 May
  6. 2021Maximum Likelihood Training of Score-Based Diffusion Models22 Jan
  7. 2020Score-Based Generative Modeling through Stochastic Differential Equations26 Nov
  8. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 19

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  2. 2022Hierarchical Text-Conditional Image Generation with CLIP Latentscited by 6,585
  3. 2022Photorealistic Text-to-Image Diffusion Models with Deep Language Understandingcited by 6,355
  4. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
  5. 2022Building Normalizing Flows with Stochastic Interpolantscited by 995
  6. 2023Stochastic Interpolants: A Unifying Framework for Flows and Diffusionscited by 939
  7. 2022GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generationcited by 516
  8. 2021Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speechcited by 447
  9. 2022Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problemcited by 236
  10. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  11. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 146
  12. 2020Generative Modeling with Denoising Auto-Encoders and Langevin Samplingcited by 119
7 more
  1. 2017Convergence of Langevin MCMC in KL-divergencecited by 88
  2. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  3. 2023Sampling, Diffusions, and Stochastic Localizationcited by 40
  4. 2019Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexitycited by 39
  5. 2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
  6. 2022Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chainscited by 16
  7. 2016Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixingcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 13; 2024: 74; 2025: 77; 2026: 71.

235 papers.

Sort:

By area:

  1. 2024Dynamical Regimes of Diffusion Modelscited by 142
  2. 2024An analytic theory of creativity in convolutional diffusion modelscited by 104
  3. 2025Masked Autoencoders Are Effective Tokenizers for Diffusion Modelscited by 96
  4. 2023Beyond First-Order Tweedie: Solving Inverse Problems using Latent Diffusioncited by 78
  5. 2024Accelerating Convergence of Score-Based Diffusion Models, Provablycited by 76
  6. 2024Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstructioncited by 73
  7. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimizationcited by 73
  8. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Modelscited by 65
  9. 2023KL Convergence Guarantees for Score diffusion models under minimal data assumptionscited by 63
  10. 2024Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theorycited by 63
  11. 2024Optimal score estimation via empirical Bayes smoothingcited by 61
  12. 2024Gradient Guidance for Diffusion Models: An Optimization Perspectivecited by 61
38 more
  1. 2024Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorialcited by 60
  2. 2024Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distancescited by 56
  3. 2024Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Modelscited by 56
  4. 2024Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributionscited by 53
  5. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptionscited by 50
  6. 2024What does guidance do? A fine-grained analysis in a simple settingcited by 48
  7. 2024How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Frameworkcited by 48
  8. 2024Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptionscited by 47
  9. 2024Critical windows: non-asymptotic theory for feature emergence in diffusion modelscited by 47
  10. 2025Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithmscited by 47
  11. 2024Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Modelscited by 46
  12. 2024Linear Convergence of Diffusion Models Under the Manifold Hypothesiscited by 45
  13. 2024Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformizationcited by 44
  14. 2024Learning general Gaussian mixtures with efficient score matchingcited by 44
  15. 2024Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionalitycited by 44
  16. 2024Learning Mixtures of Gaussians Using Diffusion Modelscited by 42
  17. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  18. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
  19. 2023The statistical thermodynamics of generative diffusion models: Phase transitions, symmetry breaking and critical instabilitycited by 39
  20. 2024A Good Score Does not Lead to A Good Generative Modelcited by 36
  21. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 35
  22. 2024Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Modelscited by 35
  23. 2023Convergence of flow-based generative models via proximal gradient descent in Wasserstein spacecited by 34
  24. 2024Manifolds, Random Matrices and Spectral Gaps: The geometric phases of generative diffusioncited by 32
  25. 2024Contractive Diffusion Probabilistic Modelscited by 29
  26. 2024Flow matching achieves almost minimax optimal convergencecited by 29
  27. 2024Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallelcited by 29
  28. 2025Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distancecited by 29
  29. 2024Evaluating the design space of diffusion-based generative modelscited by 26
  30. 2023On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimatescited by 25
  31. 2025Optimal Inference Schedules for Masked Diffusion Modelscited by 25
  32. 2024Diffusion Model for Data-Driven Black-Box Optimizationcited by 24
  33. 2024Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysiscited by 24
  34. 2025Minimax Optimality of the Probability Flow ODE for Diffusion Modelscited by 23
  35. 2025Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixturescited by 23
  36. 2025Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Modelscited by 23
  37. 2023The Emergence of Reproducibility and Generalizability in Diffusion Modelscited by 21
  38. 2024Instance-dependent Convergence Theory for Diffusion Modelscited by 21

50 most cited of 235 All 235 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Statistical guarantees for denoising reflected diffusion models
  2. 2026Error Bounds for a Diffusion Model-Based Drift Estimator
  3. 2026Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis
  4. 2026Lower Bounds for Parallel Diffusion Sampling
  5. 2024Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective
  6. 2023Metropolis Sampling for Constrained Diffusion Models
  7. 2025Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics
  8. 2025Free Denoising Diffusion Models