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

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

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

## Placed in

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

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

- [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)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding](https://mlsanity.com/paper/2205.11487/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Building Normalizing Flows with Stochastic Interpolants](https://mlsanity.com/paper/2209.15571/) (2022)
- [Stochastic Interpolants: A Unifying Framework for Flows and Diffusions](https://mlsanity.com/paper/2303.08797/) (2023)
- [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)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)
- [GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation](https://mlsanity.com/paper/2203.02923/) (2022)
- [Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech](https://mlsanity.com/paper/2105.06337/) (2021)
- [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)
- [Diffusion probabilistic modeling of protein backbones in 3D for the motif-scaffolding problem](https://mlsanity.com/paper/2206.04119/) (2022)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [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)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Score-Based Generative Models Detect Manifolds](https://mlsanity.com/paper/2206.01018/) (2022)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [Let us Build Bridges: Understanding and Extending Diffusion Generative Models](https://mlsanity.com/paper/2208.14699/) (2022)
- [Error Bounds for Flow Matching Methods](https://mlsanity.com/paper/2305.16860/) (2023)

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

- [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)
- [Masked Autoencoders Are Effective Tokenizers for Diffusion Models](https://mlsanity.com/paper/2502.03444/) (2025)
- [Beyond First-Order Tweedie: Solving Inverse Problems using Latent Diffusion](https://mlsanity.com/paper/2312.00852/) (2023)
- [Accelerating Convergence of Score-Based Diffusion Models, Provably](https://mlsanity.com/paper/2403.03852/) (2024)
- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization](https://mlsanity.com/paper/2404.07771/) (2024)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [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)
- [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)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models](https://mlsanity.com/paper/2405.14861/) (2024)
- [Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions](https://mlsanity.com/paper/2409.02426/) (2024)
- [O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions](https://mlsanity.com/paper/2409.18959/) (2024)
- [What does guidance do? A fine-grained analysis in a simple setting](https://mlsanity.com/paper/2409.13074/) (2024)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions](https://mlsanity.com/paper/2402.15602/) (2024)
- [Critical windows: non-asymptotic theory for feature emergence in diffusion models](https://mlsanity.com/paper/2403.01633/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Models](https://mlsanity.com/paper/2403.01639/) (2024)
- [Linear Convergence of Diffusion Models Under the Manifold Hypothesis](https://mlsanity.com/paper/2410.09046/) (2024)
- [Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization](https://mlsanity.com/paper/2402.08095/) (2024)
- [Learning general Gaussian mixtures with efficient score matching](https://mlsanity.com/paper/2404.18893/) (2024)
- [Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality](https://mlsanity.com/paper/2410.18784/) (2024)
- [Learning Mixtures of Gaussians Using Diffusion Models](https://mlsanity.com/paper/2404.18869/) (2024)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)

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