Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions

Hongrui ChenHolden LeeJianfeng Lu

article2023ICML258 citations

Establishes tight polynomial convergence guarantees for score-based generative models assuming only an accurate $L^2$ score estimator and finite second moments, eliminating restrictive structural assumptions like log-concavity while offering concrete guidance on discretization schemes.

Listen

Score-based generative modeling (also known as diffusion modeling) has emerged as a state-of-the-art technique in generative artificial intelligence, driving major breakthroughs across computer vision, natural language processing, and structural biology. Despite its empirical success, theoretical guarantees explaining why and how efficiently these models work have remained limited. Existing theoretical analyses typically rely on restrictive assumptions—such as bounded data domains, log-concavity, or strong smoothness conditions across the entire diffusion path—that fail to capture complex, multi-modal, or low-dimensional real-world data.

The article provides an improved theoretical analysis of score-based generative modeling to establish efficient convergence guarantees under minimal assumptions. Specifically, it evaluates sampling performance across general data distributions using only finite second-order moments and an accurate score estimator evaluated in mean squared error (average L2 error).

To establish these guarantees, the authors introduced a novel analytical framework using high-probability Hessian bounds and differential inequality arguments rather than traditional Girsanov change-of-measure transformations. This allows them to avoid restrictive technical conditions (such as Novikov's condition) and analyze discrete approximations—specifically comparing standard Euler-Maruyama discretization against the exponential integrator scheme—under uniform, quadratic, and exponentially decaying step-size schedules.

The investigation yields four key findings. First, for general arbitrary data distributions with finite second moments, the exponential integrator scheme with early stopping generates samples close to the true perturbed target in an accuracy bound of epsilon using a number of steps that depends only logarithmically on the early-stopping threshold. Second, when the target distribution has an L-smooth score, the required sampling complexity scales proportionally to the square of log L rather than polynomial powers of L, meaning the model converges efficiently even if smoothness degrades exponentially with dimension. Third, the exponential integrator strictly outperforms the standard Euler-Maruyama discretization, exhibiting logarithmic rather than linear error scaling relative to the data's second moment. Fourth, combining exponentially decaying step sizes with early stopping minimizes discretization error, outperforming standard constant or linear step-size schedules.

These findings provide strong theoretical justification for why diffusion models excel at learning highly complex, multi-modal data where other gradient-based sampling methods fail. Practically, they show that standard denoising score matching objectives are theoretically optimal for generative modeling and demonstrate that adopting exponential integrator solvers alongside exponentially decaying step sizes can significantly reduce computational sampling overhead.

For practitioners and engineering teams, the article recommends adopting exponential integrator schemes in place of standard Euler discretizations and implementing exponentially decaying step sizes toward the end of the reverse process to minimize discretization errors without ballooning sampling time. When non-smooth data distributions are modeled, early stopping should be deployed as a principled trade-off between target fidelity and numerical stability.

While these results establish robust guarantees under minimal assumptions, the theoretical upper bound incurs a quadratic dependence on data dimension, whereas existing lower bounds scale linearly. Further research is required to close this dimensional gap and to extend the theoretical framework to other continuous diffusion processes, such as critically damped Langevin dynamics, as well as to fully characterize the sample complexity and neural network training dynamics of score estimation.

Duke University Johns Hopkins University Peking University computer vision diffusion probabilistic models mean square error Score-based Generative Modeling score matching Euler-Maruyama scheme

arXiv: 2211.01916

Paper: Score-Based Generative Modeling through Stochastic Differential Equations, Yang Song et al. (2021). Establishes the foundational continuous stochastic differential equation (SDE) and reverse-time ODE framework for score-based generative modeling that the source analyzes under relaxed smoothness assumptions.
Paper: Estimation of Non-Normalized Statistical Models by Score Matching, Aapo Hyvärinen (2005). Introduces the core mathematical principle of score matching used to train score estimators without computing intractable normalizing constants.
Paper: Generative Modeling by Estimating Gradients of the Data Distribution, Yang Song et al. (2019). Provides the foundational framework for generative modeling using noise-conditioned score networks and annealed Langevin dynamics.
Paper: DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps, Cheng Lu et al. (2022). Develops dedicated fast ODE solvers utilizing exponential integrators for diffusion models, which the source formally analyzes to prove superior convergence bounds.
Paper: Denoising Diffusion Probabilistic Models, Jonathan Ho et al. (2020). Establishes modern denoising diffusion probabilistic models and their connection to score matching objectives analyzed in the source.
Paper: Elucidating the Design Space of Diffusion-Based Generative Models, Tero Karras et al. (2022). Systematizes the design space, noise schedules, and higher-order discretization methods that motivate the source's exploration of optimal step schedules.
Paper: Improved Techniques for Training Score-Based Generative Models, Yang Song et al. (2020). Analyzes practical failure modes and geometric noise scheduling in score-based models, providing key context for non-smooth and multi-modal distribution behaviors.
Paper: Denoising Diffusion Implicit Models, Jiaming Song et al. (2021). Introduces non-Markovian deterministic sampling trajectories that set the stage for reverse ODE convergence theory.

Paper: A Mathematical Introduction to Diffusion Models, Jianfeng Lu (2026). Synthesizes mathematical error decompositions, finite-second-moment Euler-Maruyama bounds, and discrete extensions directly building on rigorous score-based convergence analysis.
Paper: Diffusion Models are Minimax Optimal Distribution Estimators, Kazusato Oko et al. (2023). Complements the source's discretization and sampling complexity bounds by proving minimax optimal statistical estimation rates under non-smooth Besov spaces.
Paper: Accelerating Diffusion Sampling with Optimized Time Steps, Shuchen Xue et al. (2024). Extends the source's findings on non-uniform step sizes by formulating a general optimization framework to compute optimal solver trajectories.
Paper: Fast ODE-based Sampling for Diffusion Models in Around 5 Steps, Zhenyu Zhou et al. (2024). Builds upon trajectory error bounds to design learned mean-direction ODE solvers capable of extreme few-step sampling.
Paper: Score-Based Diffusion Models in Function Space, Jae Hyun Lim 0001 et al. (2025). Generalizes score-based diffusion theory and discretization analysis from finite dimensions to infinite-dimensional function spaces.
Paper: Fast Sampling of Diffusion Models via Operator Learning, Hongkai Zheng et al. (2023). Applies operator learning to decode full diffusion ODE trajectories in parallel, building on the theoretical limits of iterative discretization.
Paper: Generalization in diffusion models arises from geometry-adaptive harmonic representations, Zahra Kadkhodaie et al. (2024). Investigates the inductive biases and empirical generalization mechanisms of score denoisers whose sampling guarantees are theoretically bounded in the source.
Paper: Reflected Diffusion Models, Aaron Lou et al. (2023). Extends diffusion modeling to bounded domains using reflected SDEs to address numerical divergence issues occurring under minimal smoothness.

Cover for Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions

Abstract

We give an improved theoretical analysis of score-based generative modeling. Under a score estimate with small L^2 error (averaged across timesteps), we provide efficient convergence guarantees for any data distribution with second-order moment, by either employing early stopping or assuming a smoothness condition on the score function of the data distribution. Our result does not rely on any log-concavity or functional inequality assumption and has a logarithmic dependence on the smoothness. In particular, we show that under only a finite second moment condition, approximating the following in reverse KL divergence in ε-accuracy can be done in Õ(d log(1/δ)/ε) steps: 1) the variance-δ Gaussian perturbation of any data distribution; 2) data distributions with 1/δ-smooth score functions. Our analysis also provides a quantitative comparison between different discrete approximations and may guide the choice of discretization points in practice.

Topics

computer vision diffusion probabilistic models mean square error natural language processing neural networks step size trade time discretization numerical solution distribution functions

Keywords

Score-based Generative Modeling score matching Euler-Maruyama scheme Ornstein-Uhlenbeck process Langevin dynamics Wasserstein distance KL divergence discretization error score estimation

1. Introduction
1.1. Background and Our Setting
1.2. Related Work
1.3. Our Contributions
1.4. Notations
2. Main Results
2.1. Analysis under the Trajectory Smoothness Condition
2.2. Results for General Distributions with Early Stopping
2.3. Result for Smooth Data Distributions
3. Proof sketches
3.1. Smooth setting (Theorem 2.1)
3.2. Non-smooth setting (Theorem 2.2)
3.3. Smooth p0 (Theorem 2.5)
4. Conclusion
Acknowledgement
References
A. Denoising Score Matching
B. Discussion on Choices of Discretization Points
C. Main Proof Ingredients
C.1. The High-probability Hessian Bound and Change of Measure
C.2. Stability of the Lipschitz Constant
D. Proofs for the Main Theorems
D.1. Proof of Theorem 2.1
D.2. Proof of Theorem 2.2
D.3. Proof of Corollary 2.3 and 2.4
D.4. Proof of Theorem 2.5
E. Lemmas for Computing Score Functions
F. Technical details for Proposition C.3

Knowls

Knowl 1 — Convergence of Score-Based Generative Modeling for General Distributions with Early Stopping
theoretical result
Let $P$ be an arbitrary probability distribution on $\mathbb{R}^d$ with finite second moment $M_2 := \mathbb{E}_{x \sim P}[\|x\|^2] < \infty$ . Let the forward Ornstein-Uhlenbeck process be defined by $\mathrm{d}x_t = -\frac{1}{2}x_t\mathrm{d}t + \mathrm{d}w_t$ with $x_0 \sim P$ , marginal densities $p_t$ , and conditional variances $\sigma_t^2 = 1 - e^{-t}$ . Let $s(x, t)$ be an estimated score function satisfying the weighted average $L^2$ error bound $\frac{1}{T} \sum_{k=1}^N h_k \mathbb{E}_{x \sim p_{t_k}}\left[\|\nabla \log p_{t_k}(x) - s(x, t_k)\|^2\right] \le \epsilon_0^2$ over discretization points $\delta = t_0 < t_1 < \dots < t_N = T$ with step sizes $h_k = t_k - t_{k-1}$ .

There exists a universal constant $K > 0$ such that for any total diffusion time $T \ge 2$ and early-stopping time $\delta \le 1/2$ , if the step sizes satisfy $\frac{h_k}{\sigma_{t_{k-1}}^2} \le \frac{1}{Kd}$ for all $k = 1, \dots, N$ , the distribution $\hat{q}_{T-\delta}$ generated by the exponential integrator discretization starting from standard Gaussian $\hat{q}_0 = \mathcal{N}(0, I_d)$ satisfies $\mathrm{KL}(p_\delta \parallel \hat{q}_{T-\delta}) \lesssim (d + M_2)\exp(-T) + T\epsilon_0^2 + d^2 \sum_{k=1}^N \frac{h_k^2}{\sigma_{t_{k-1}}^4}.$

In particular, using an exponentially decreasing step-size schedule $h_k = c \min\{t_k, 1\}$ with $c = \frac{\log(1/\delta) + T}{N} \le \frac{1}{Kd}$ ensures that $\sum_{k=1}^N \frac{h_k^2}{\sigma_{t_{k-1}}^4} \lesssim \frac{(\log(1/\delta) + T)^2}{N}$ . Setting $T = \log\left(\frac{M_2 + d}{\epsilon_0^2}\right)$ and $N = \Theta\left(\frac{d^2(\log(1/\delta) + T)^2}{\epsilon_0^2}\right)$ steps yields $\mathrm{KL}(p_\delta \parallel \hat{q}_{T-\delta}) = \tilde{O}(\epsilon_0^2)$ without requiring log-concavity, functional inequalities, or bounded support.
Knowl 2 — Convergence of SGM under Smooth Initial Density without Early Stopping
theoretical result
Suppose the data distribution on $\mathbb{R}^d$ has a density $p_0 \in C^2(\mathbb{R}^d)$ with bounded second moment $M_2 := \mathbb{E}_{p_0}[\|x\|^2] < \infty$ , and the initial score function $\nabla \log p_0$ is $L$ -Lipschitz. Let $s(x, t)$ be an estimated score function satisfying the average $L^2$ error condition $\frac{1}{T}\sum_{k=1}^N h_k \mathbb{E}_{p_{t_k}}[\|\nabla \log p_{t_k}(x) - s(x, t_k)\|^2] \le \epsilon_0^2$ .

There exists a universal constant $K > 0$ such that by choosing the exponentially decreasing and then constant step-size schedule $h_k = c\min\{\max\{t_k, 1/L\}, 1\}$ with $c = \frac{\log L + T}{N} \le \frac{1}{Kd}$ , the exponential integrator scheme run to time $T$ (with no early stopping, $\delta = 0$ ) produces a generated distribution $\hat{q}_T$ satisfying $\mathrm{KL}(p_0 \parallel \hat{q}_T) \lesssim (M_2 + d)\exp(-T) + T\epsilon_0^2 + \frac{d^2(\log L + T)^2}{N}.$

Choosing total time $T = \log\left(\frac{M_2 + d}{\epsilon_0^2}\right)$ and step count $N = \Theta\left(\frac{d^2(T + \log L)^2}{\epsilon_0^2}\right)$ yields $\mathrm{KL}(p_0 \parallel \hat{q}_T) = \tilde{O}(\epsilon_0^2)$ . The step complexity depends only logarithmically on the Lipschitz constant $L$ of $\nabla \log p_0$ , allowing $L$ to scale exponentially in $d$ while maintaining polynomial complexity.
Knowl 3 — High-Probability Frobenius Norm Bound for Hessian of Smoothed Score Functions
theoretical result
Let $P$ be any arbitrary probability distribution on $\mathbb{R}^d$ . Consider its Gaussian perturbation $p_\sigma(x) \propto \int_{\mathbb{R}^d} \exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right) \mathrm{d}P(y)$ with variance $\sigma^2 > 0$ . When $x \sim p_\sigma$ , the Frobenius norm of the Hessian matrix $\nabla^2 \log p_\sigma(x)$ satisfies the sub-exponential norm bound $\|\nabla^2 \log p_\sigma(x)\|_{F, \psi_1} \lesssim \frac{d}{\sigma^2},$ where for a matrix-valued random variable $M$ , $\|M\|_{F, \psi_1} := \inf\left\{t > 0 : \mathbb{E}\exp\left(\frac{\|M\|_F}{t}\right) \le 2\right\}$ .

This bound is established by expressing the Hessian via the posterior variance of the perturbation noise: $\nabla^2 \log p_\sigma(x) = \mathrm{Var}_{\tilde{P}_\sigma(y|x)}\left(\frac{y}{\sigma^2}\right) - \frac{I_d}{\sigma^2},$ where $\mathrm{d}\tilde{P}_\sigma(y|x) \propto \exp\left(-\frac{\|y-x\|^2}{2\sigma^2}\right)\mathrm{d}P(y)$ . This high-probability smoothing property holds for arbitrary distributions $P$ without bounded support or tail decay assumptions.
Knowl 4 — Convergence Guarantees under Trajectory-Smoothness Condition
theoretical result
Let $P$ be a data distribution on $\mathbb{R}^d$ with bounded second moment $M_2 = \mathbb{E}_P[\|x\|^2] < \infty$ . Assume that for all $t \in [0, T]$ , the score function $\nabla \log p_t$ of the forward Ornstein-Uhlenbeck process is $L$ -Lipschitz with $L \ge 1$ . Suppose the score estimator $s(x, t)$ has average $L^2$ error $\le \epsilon_0^2$ , and uniform step size $h_k = T/N \le 1$ with $T \ge 1$ .
1. For the exponential integrator discretization scheme: $\mathrm{KL}(p_0 \parallel \hat{q}_T) \lesssim (M_2 + d)e^{-T} + T\epsilon_0^2 + \frac{d T^2 L^2}{N}.$ Setting $T = \log\left(\frac{M_2+d}{\epsilon_0^2}\right)$ and $N = \Theta\left(\frac{d T^2 L^2}{\epsilon_0^2}\right)$ gives $\mathrm{KL}(p_0 \parallel \hat{q}_T) = \tilde{O}(\epsilon_0^2)$ .
2. For the Euler-Maruyama discretization scheme, an extra second-moment error term appears: $\mathrm{KL}(p_0 \parallel \hat{q}_T) \lesssim (M_2 + d)e^{-T} + T\epsilon_0^2 + \frac{d T^2 L^2}{N} + \frac{T^3 M_2}{N^2}.$
These reverse KL divergence bounds do not require the initial distribution $p_0$ to have finite KL divergence with respect to the standard Gaussian $\mathcal{N}(0, I_d)$ .
Knowl 5 — Wasserstein and KL Divergence Guarantees for Early-Stopped SGM
theoretical result
Let $P$ be any data distribution on $\mathbb{R}^d$ with second moment $M_2 = \mathbb{E}_P[\|x\|^2] < \infty$ , and let $p_\delta$ be the density at early-stopping time $\delta$ under the forward Ornstein-Uhlenbeck process. Let $M(x) = \exp(\delta / 2)x$ , and let $M_\sharp$ denote the pushforward map on measures.

Running the exponential integrator scheme with exponentially decreasing step size to generate $\hat{q}_{T-\delta}$ and defining $Q = M_\sharp \hat{q}_{T-\delta}$ , achieving $W_2^2(P, M_\sharp p_\delta) \le \epsilon_W^2 \le \frac{d}{2} \quad \text{and} \quad \mathrm{KL}(M_\sharp p_\delta \parallel Q) \le \epsilon_{\mathrm{KL}}^2 \le \frac{d + M_2}{2}$ requires early-stopping parameter $\delta = \Theta(\epsilon_W^2 / d)$ , total time $T = \Theta(\log((d+M_2)/\epsilon_{\mathrm{KL}}^2))$ , average score error $\epsilon_0^2 \le \frac{\epsilon_{\mathrm{KL}}^2}{K \log^2\left(\frac{d+M_2}{\epsilon_{\mathrm{KL}}^2}\right)},$ and a total number of discretization steps $N = \Theta\left(\frac{d^2 \log^2\left(\frac{(d+M_2)d}{\epsilon_{\mathrm{KL}}^2 \epsilon_W^2}\right)}{\epsilon_{\mathrm{KL}}^2}\right),$ where $K > 0$ is an absolute constant.
Knowl 6 — Pure Wasserstein Convergence Guarantee with Output Truncation
theoretical result
Let $P$ be a probability distribution on $\mathbb{R}^d$ with second moment $M_2 = \mathbb{E}_P[\|x\|^2] < \infty$ . Let $\hat{q}_{T-\delta}^{\mathrm{trunc}}$ be the distribution generated by the early-stopped exponential integrator scheme with an added truncation step: any generated sample $\hat{y}_{T-\delta} \sim \hat{q}_{T-\delta}$ falling outside the Euclidean ball $B_R(0)$ is mapped to $0$ .

Let $M(x) = \exp(\delta/2)x$ . If the truncation radius $R \ge M_2$ , stopping time $\delta$ , total time $T$ , and step count $N$ satisfy $\delta = \Theta\left(\frac{\epsilon_W^2}{d}\right), \quad R^2 \mathbb{P}_{x_\delta \sim p_\delta}(\|x_\delta\| \ge R) = O(\epsilon_W^2),$ $T = \Theta\left(\log\left(\frac{R^4(M_2 + d)}{\epsilon_W^4}\right)\right), \quad N = \Theta\left(\frac{d^2 R^4(\log(1/\delta) + T)^2}{\epsilon_W^4}\right),$ and the average score error satisfies $\epsilon_0 = O(\epsilon_W^2 / R^2)$ , then the scaled and truncated distribution satisfies $W_2^2(P, M_\sharp \hat{q}_{T-\delta}^{\mathrm{trunc}}) = \tilde{O}(\epsilon_W^2).$

For $K$ -sub-exponential data distributions, $R = \tilde{O}(1)$ depends only logarithmically on $1/\epsilon_W$ , yielding step complexity $N = \tilde{O}(d^2 K^4 / \epsilon_W^4)$ .
Knowl 7 — Time-Weighted Average L2 Score Estimation Error Condition
assumption
The score estimator $s(x, t)$ for the forward diffusion marginals $p_t$ on $\mathbb{R}^d$ is assumed to satisfy a discrete time-weighted average $L^2$ error bound over discretization points $t_1, \dots, t_N$ with step sizes $h_k = t_k - t_{k-1}$ : $\frac{1}{T} \sum_{k=1}^N h_k \mathbb{E}_{x \sim p_{t_k}}\left[\|\nabla \log p_{t_k}(x) - s(x, t_k)\|^2\right] \le \epsilon_0^2.$

This weighted average accommodates the divergence of pointwise score errors as $t \to 0$ . In denoising score matching with conditional variance $\sigma_t^2 = 1 - e^{-t} \sim t$ , the typical pointwise error scales as $\mathbb{E}_{p_{t_k}}[\|\nabla \log p_{t_k}(x) - s(x, t_k)\|^2] \lesssim \epsilon^2 / \sigma_{t_k}^2$ . Because $\int_{t_1}^1 \frac{1}{t}\mathrm{d}t = \log(1/t_1)$ , this assumption is satisfied with $\epsilon_0^2 = O(\epsilon^2 \log(1/t_1))$ .
Knowl 8 — Exponential Integrator and Euler-Maruyama Discretizations for Reverse-Time Diffusion
model/method
Given the forward Ornstein-Uhlenbeck SDE $\mathrm{d}x_t = -\frac{1}{2}x_t\mathrm{d}t + \mathrm{d}w_t$ ( $0 \le t \le T$ , $x_0 \sim P$ ), the time-reversed process $\tilde{x}_t := x_{T-t}$ satisfies the forward-in-time SDE $\mathrm{d}\tilde{x}_t = \left[\frac{1}{2}\tilde{x}_t + \nabla \log p_{T-t}(\tilde{x}_t)\right]\mathrm{d}t + \mathrm{d}w_t, \quad \tilde{x}_0 \sim p_T.$

Using an estimated score function $s(x, t)$ and reverse-time discretization points $t'_k = T - t_{N-k}$ ( $k = 0, \dots, N-1$ ) with reverse step size $h'_k = t'_{k+1} - t'_k$ , sample generation initializes from $\hat{y}_0 \sim \mathcal{N}(0, I_d)$ via one of two discretization schemes:
1. Exponential Integrator Scheme (integrates the linear drift term exactly): $\hat{y}_{t'_{k+1}} = e^{\frac{1}{2}(t'_{k+1}-t'_k)}\hat{y}_{t'_k} + 2\left(e^{\frac{1}{2}(t'_{k+1}-t'_k)} - 1\right)s(\hat{y}_{t'_k}, T - t'_k) + \sqrt{e^{t'_{k+1}-t'_k} - 1}\,\eta_k,$ where $\eta_k \sim \mathcal{N}(0, I_d)$ .
2. Euler-Maruyama Scheme: $\hat{y}_{t'_{k+1}} = \hat{y}_{t'_k} + \left[\frac{1}{2}\hat{y}_{t'_k} + s(\hat{y}_{t'_k}, T - t'_k)\right](t'_{k+1}-t'_k) + \sqrt{t'_{k+1}-t'_k}\,\eta_k.$
Knowl 9 — Optimality of Exponentially Decaying Step Sizes for Reverse Diffusion Discretization
theoretical result
The discretization error bound for score-based generative modeling with early stopping at $\delta$ depends on the quantity $\Pi := \sum_{k=1}^N \frac{h_k^2}{\sigma_{t_{k-1}}^4}$ , where $\sigma_t^2 = 1 - e^{-t}$ and $h_k = t_k - t_{k-1}$ :
1. Constant step sizes ( $t_k = \delta + kh$ with $h = \frac{T-\delta}{N}$ ) yield $\Pi \asymp \frac{T/\delta + T^2}{N}$ , having a linear dependence on $1/\delta$ .
2. Linear step sizes from quadratic grid points ( $t_k = (\sqrt{\delta} + kh)^2$ with $h = \frac{\sqrt{T} - \sqrt{\delta}}{N}$ ) yield $\Pi \asymp \frac{1}{N}\left(\sqrt{\frac{T}{\delta}} + T^2\right)$ , having a square-root dependence on $1/\delta$ .
3. Exponentially decaying step sizes ( $h_k = c\min\{t_k, 1\}$ ) yield $\Pi \asymp \frac{(\log(1/\delta) + T)^2}{N}$ , reducing the dependence to logarithmic in $1/\delta$ .
Setting $z_k = \log(t_k / t_{k-1}) > 0$ gives $\sum_{t_k \le 1} \frac{(t_k - t_{k-1})^2}{t_k^2} = \sum_{t_k \le 1} (1 - e^{-z_k})^2$ . Since $z \mapsto (1 - e^{-z})^2$ is convex, Jensen's inequality shows that equal logarithmic increments $z_k = \text{const}$ uniquely minimize the discretization error in the small-noise regime $t_k \le 1$ .
Knowl 10 — KL Divergence Evolution and Discretization Error Decomposition via Differential Inequality
theoretical result
Let $X_t, Y_t$ be two Itô processes on $\mathbb{R}^d$ driven by $\mathrm{d}X_t = F_1(X_t, t)\mathrm{d}t + g(t)\mathrm{d}w_t, \quad X_0 = a,$ $\mathrm{d}Y_t = F_2(Y_t, t)\mathrm{d}t + g(t)\mathrm{d}w_t, \quad Y_0 = a,$ with densities $p_t, q_t \in C^2(\mathbb{R}^d)$ for $t > 0$ . The evolution of the KL divergence is given by $\frac{\partial}{\partial t}\mathrm{KL}(p_t \parallel q_t) = -g(t)^2 J(p_t \parallel q_t) + \mathbb{E}\left[\left\langle F_1(X_t, t) - F_2(X_t, t), \nabla \log \frac{p_t(X_t)}{q_t(X_t)}\right\rangle\right],$ where $J(p_t \parallel q_t) = \int_{\mathbb{R}^d} p_t(x) \left\|\nabla \log \frac{p_t(x)}{q_t(x)}\right\|^2 \mathrm{d}x$ is the relative Fisher information.

Applying Young's inequality $\langle v, w \rangle \le \frac{1}{2}\|v\|^2 + \frac{1}{2}\|w\|^2$ bounds $\frac{\mathrm{d}}{\mathrm{d}t}\mathrm{KL}(p_t \parallel q_t) \le \frac{1}{2}\mathbb{E}[\|F_1(X_t, t) - F_2(X_t, t)\|^2]$ , sidestepping the technical requirement of verifying Novikov's condition and yielding the direct KL discretization error bound for diffusion reverse processes $\mathrm{KL}(p_\delta \parallel \hat{q}_{T-\delta}) \le \mathrm{KL}(p_T \parallel \gamma_d) + T\epsilon_0^2 + \sum_{k=1}^N \int_{t_{k-1}}^{t_k} \mathbb{E}_{x_t \sim p_t}\left[\|\nabla \log p_t(x_t) - \nabla \log p_{t_k}(x_{t_k})\|^2\right]\mathrm{d}t.$
Knowl 11 — Short-Time Preservation of Score Lipschitz Continuity
theoretical result
Let $p_0 \in C^2(\mathbb{R}^d)$ be a probability density such that $\nabla \log p_0$ is $L$ -Lipschitz on $\mathbb{R}^d$ . Let $p_t$ be the density at time $t$ under the Ornstein-Uhlenbeck forward process, with scaling factor $\alpha_t = e^{-t/2}$ and noise variance $\sigma_t^2 = 1 - e^{-t}$ .

For any time $t$ such that $\sigma_t^2 \le \frac{\alpha_t}{2L},$ the score function $\nabla \log p_t$ is $2L\alpha_t^{-1}$ -Lipschitz on $\mathbb{R}^d$ .

This holds because the conditional density $\tilde{q}_{\sigma_t}(y|x) \propto p_0(\alpha_t^{-1}y)\exp\left(-\frac{\|x-y\|^2}{2\sigma_t^2}\right)$ is $L\alpha_t^{-1}$ -strongly log-concave for $\sigma_t^2 \le \frac{\alpha_t}{2L}$ , hence satisfies the Poincaré inequality with constant $\alpha_t L^{-1}$ , which bounds the covariance term in the Hessian expansion $\nabla^2 \log p_t(x)$ .

Coverage note — None was omitted; all primary theoretical results, structural assumptions, discretization schemes, step-size optimality comparisons, and core analytic lemmas from the paper and its appendices have been extracted.

References

1.Alaoui, A. E., Montanari, A., and Sellke, M. Sampling from the sherrington-kirkpatrick gibbs measure via algorithmic stochastic localization. arXiv preprint arXiv:2203.05093, 2022.
2.Anderson, B. D. O. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12:313–326, 1982.
3.Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and van den Berg, R. Structured denoising diffusion models in discrete state-spaces. In NeurIPS, 2021.
4.Block, A., Mroueh, Y., and Rakhlin, A. Generative modeling with denoising auto-encoders and langevin sampling, 2020. arXiv:2002.00107.
5.Boffi, N. M. and Vanden-Eijnden, E. Probability flow solution of the fokker-planck equation, 2022. arXiv:2206.04642.
6.Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions, 2022. URL https://arxiv.org/abs/2209.11215.
7.Chewi, S., Erdogdu, M. A., Li, M., Shen, R., and Zhang, S. Analysis of langevin monte carlo from poincare to log-sobolev. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1–2. PMLR, 02–05 Jul 2022.
8.Chung, H., Sim, B., and Ye, J.-C. Come-closer-diffuse-faster: Accelerating conditional diffusion models for inverse problems through stochastic contraction, 2021. arXiv:2112.05146.
9.DeBortoli, V. Convergence of denoising diffusion models under the manifold hypothesis, 2022. arXiv:2208.05314.
10.DeBortoli, V., Thornton, J., Heng, J., and Doucet, A. Diffusion schrodinger bridge with applications to score-based generative modeling. In NeurIPS, 2021.
11.Dhariwal, P. and Nichol, A. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 2021.
12.Dockhorn, T., Vahdat, A., and Kreis, K. Score-based generative modeling with critically-damped langevin diffusion. arXiv preprint arXiv:2112.07068, 2021.
13.Gnaneshwar, D., Ramsundar, B., Gandhi, D., Kurchin, R. C., and Viswanathan, V. Score-based generative models for molecule generation, 2022. arXiv:2203.04698.
14.Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A. C., and Bengio, Y. Generative adversarial nets. In NIPS, 2014.
15.Karatzas, I. and Shreve, S. Brownian motion and stochastic calculus, volume 113. Springer Science & Business Media, 1991.
16.Kingma, D. P. and Welling, M. Auto-encoding variational bayes, 2014. arXiv:1312.6114.
17.Koehler, F., Heckett, A., and Risteski, A. Statistical efficiency of score matching: The view from isoperimetry, 2022. URL https://arxiv.org/abs/2210.00726.
18.Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 28:1302–1338, 2000.
19.Lee, H., Pabbaraju, C., Sevekari, A., and Risteski, A. Universal approximation for log-concave distributions using well-conditioned normalizing flows. arXiv preprint arXiv:2107.02951, 2021.
20.Lee, H., Lu, J., and Tan, Y. Convergence for score-based generative modeling with polynomial complexity, 2022a. URL https://arxiv.org/abs/2206.06227.
21.Lee, H., Lu, J., and Tan, Y. Convergence of score-based generative modeling for general data distributions, 2022b. URL https://arxiv.org/abs/2209.12381.
22.Rezende, D. J. and Mohamed, S. Variational inference with normalizing flows. In ICML, 2015.
23.Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. CVPR, 2021.
24.Shi, C., Luo, S., Xu, M., and Tang, J. Learning gradient fields for molecular conformation generation. In ICML, 2021.
25.Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models, 2021a. arXiv:2010.02502.
26.Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, volume 32, 2019.
27.Song, Y., Garg, S., Shi, J., and Ermon, S. Sliced score matching: A scalable approach to density and score estimation. In UAI, 2019.
28.Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2020.
29.Song, Y., Durkan, C., Murray, I., and Ermon, S. Maximum likelihood training of score-based diffusion models. In NeurIPS, 2021b.
30.Song, Y., Shen, L., Xing, L., and Ermon, S. Solving inverse problems in medical imaging with score-based generative models, 2022. arXiv:2111.08005.
31.Vempala, S. S. and Wibisono, A. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In NeurIPS, 2019.
32.Vincent, P. A connection between score matching and denoising autoencoders. Neural Computation, 23:1661–1674, 2011.
33.Wang, Z., Hunt, J. J., and Zhou, M. Diffusion policies as an expressive policy class for offline reinforcement learning, 2022. arXiv:2208.06193.
34.Wibisono, A. and Yang, K. Y. Convergence in kl divergence of the inexact langevin algorithm with application to score-based generative models, 2022. URL https://arxiv.org/abs/2211.01512.
35.Zhang, Q. and Chen, Y. Fast sampling of diffusion models with exponential integrator, 2022. arXiv:2204.13902.
36.Zhao, J. J., Mathieu, M., and LeCun, Y. Energy-based generative adversarial network, 2016. arXiv:1609.03126.

Citation

MLA

Chen, H., et al. “Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds Under Minimal Smoothness Assumptions”. International Conference on Machine Learning, vol. 202, 2023, pp. 4735–63, https://proceedings.mlr.press/v202/chen23q.html.

APA

Chen, H., Lee, H., & Lu, J. (2023). Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions. International Conference on Machine Learning, 202, 4735–4763. https://proceedings.mlr.press/v202/chen23q.html

Chicago

Chen, H., H. Lee, and J. Lu. 2023. “Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds Under Minimal Smoothness Assumptions”. International Conference on Machine Learning 202: 4735–63. https://proceedings.mlr.press/v202/chen23q.html.

Harvard

Chen, H., Lee, H. and Lu, J. (2023) “Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions”, International Conference on Machine Learning. PMLR, pp. 4735–4763. Available at: https://proceedings.mlr.press/v202/chen23q.html.

Vancouver

1. Chen H, Lee H, Lu J (2023) Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions. In: International Conference on Machine Learning. PMLR, pp 4735–4763

BibTeX

@InProceedings{pmlr-v202-chen23q,
  title = 	 {Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions},
  author =       {Chen, Hongrui and Lee, Holden and Lu, Jianfeng},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {4735--4763},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/chen23q/chen23q.pdf},
  url = 	 {https://proceedings.mlr.press/v202/chen23q.html},
  abstract = 	 {We give an improved theoretical analysis of score-based generative modeling. Under a score estimate with small $L^2$ error (averaged across timesteps), we provide efficient convergence guarantees for any data distribution with second-order moment, by either employing early stopping or assuming smoothness condition on the score function of the data distribution. Our result does not rely on any log-concavity or functional inequality assumption and has a logarithmic dependence on the smoothness. In particular, we show that under only a finite second moment condition, approximating the following in reverse KL divergence in $\epsilon$-accuracy can be done in $\tilde O\left(\frac{d \log (1/\delta)}{\epsilon}\right)$ steps: 1) the variance-$\delta$ Gaussian perturbation of any data distribution; 2) data distributions with $1/\delta$-smooth score functions. Our analysis also provides a quantitative comparison between different discrete approximations and may guide the choice of discretization points in practice.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Convergence of Score-Based Generative Modeling for General Distributions with Early Stopping

Knowl 2 — Convergence of SGM under Smooth Initial Density without Early Stopping

Knowl 3 — High-Probability Frobenius Norm Bound for Hessian of Smoothed Score Functions

Knowl 4 — Convergence Guarantees under Trajectory-Smoothness Condition

Knowl 5 — Wasserstein and KL Divergence Guarantees for Early-Stopped SGM

Knowl 6 — Pure Wasserstein Convergence Guarantee with Output Truncation

Knowl 7 — Time-Weighted Average L2 Score Estimation Error Condition

Knowl 8 — Exponential Integrator and Euler-Maruyama Discretizations for Reverse-Time Diffusion

Knowl 9 — Optimality of Exponentially Decaying Step Sizes for Reverse Diffusion Discretization

Knowl 10 — KL Divergence Evolution and Discretization Error Decomposition via Differential Inequality

Knowl 11 — Short-Time Preservation of Score Lipschitz Continuity

References

Citation

BibTeX

Access the Paper