Source-linked AI summary
Convergence of score-based generative modeling for general data distributions
Holden Lee, Jianfeng Lu, Yixin Tan
TL;DR
Existing convergence analyses for score-based generative modeling either have exponential parameter dependence or require strong distributional assumptions that practical data may violate. This paper analyzes denoising diffusion models and establishes polynomial-complexity convergence guarantees under minimal assumptions, including Wasserstein guarantees for bounded-support distributions.
Problem
Prior SGM convergence analyses either depend exponentially on parameters or assume functional inequalities or smoothness, while the central question of generated-distribution convergence remains unresolved.
Method
The paper analyzes denoising diffusion models by tracking reverse-SDE dynamics with a sequence of score functions and appropriate discretization.
Results
Polynomial-complexity guarantees are obtained for bounded-support distributions, including Wasserstein and total-variation error bounds under the stated assumptions.
Takeaways & Limitations
The analysis avoids requiring a global log-Sobolev inequality by decomposing bounded-support distributions into mixtures after moving a small amount of mass.
Takeaways & Limitations
The paper assumes an L2-accurate score estimate is obtainable, although learning one without further assumptions may require exponentially many samples in the dimension.
Abstract
from arXiv · showhide
Score-based generative modeling (SGM) has grown to be a hugely successful method for learning to generate samples from complex data distributions such as that of images and audio. It is based on evolving an SDE that transforms white noise into a sample from the learned distribution, using estimates of the score function, or gradient log-pdf. Previous convergence analyses for these methods have suffered either from strong assumptions on the data distribution or exponential dependencies, and hence fail to give efficient guarantees for the multimodal and non-smooth distributions that arise in practice and for which good empirical performance is observed. We consider a popular kind of SGM -- denoising diffusion models -- and give polynomial convergence guarantees for general data distributions, with no assumptions related to functional inequalities or smoothness. Assuming $L^2$-accurate score estimates, we obtain Wasserstein distance guarantees for any distribution of bounded support or sufficiently decaying tails, as well as TV guarantees for distributions with further smoothness assumptions.
1 Introduction
The paper studies whether score-based generative models converge efficiently under realistic data distributions and L2-accurate score estimates. It develops polynomial guarantees with minimal assumptions, including Wasserstein guarantees for broad distributions and TV guarantees under additional smoothness.
- Problem setting: SGM transforms white noise into data-distribution samples by following a stochastic differential equation driven by learned score functions.The score is the gradient of the log-pdf, and the reverse-time process is intended to generate samples from noise.
- Introduction: Prior convergence analyses either have exponential parameter dependence or require strong assumptions such as functional inequalities or smoothness.These assumptions are problematic for multimodal distributions and data supported on lower-dimensional manifolds.
- Contributions: The paper targets theoretical convergence guarantees with polynomial complexity under minimal assumptions on Pdata.Its stated scope includes distributions with bounded support or sufficiently decaying tails, without requiring functional inequalities.
- Problem setting: The central question is how close the generated distribution is to Pdata when the reverse process uses an L2-accurate score estimate and discretization.L2 error is more realistic than L∞ error but creates distinct analytical difficulties, including the need for medium-time analysis.
- Contributions: The resulting guarantees cover Wasserstein distance for general bounded-support or sufficiently light-tailed distributions and TV distance under additional smoothness assumptions.The bounds are intended to address multimodal and non-smooth distributions encountered in practice.
- Contributions: The proof removes global functional-inequality requirements by relating χ2-closeness to L2 score closeness and decomposing diffusion distributions into suitable mixtures.The analysis builds on a KL-divergence bound and modifies distributions so mixture components satisfy log-Sobolev inequalities.
2 Main results
The paper analyzes DDPM convergence under L2-accurate score estimates, obtaining polynomial-complexity Wasserstein and, with additional smoothness, total-variation guarantees for broad data distributions.
- Method: DDPM is analyzed as a denoising diffusion model whose reverse process uses estimated scores to generate samples from noise.The continuous process is equivalent to score-matching Langevin diffusion under time and space reparameterization.
- Assumptions: The analysis assumes L2 score error at selected reverse-process times, which is quantitatively weaker than a uniform-in-time bound.The score estimate must satisfy the stated L2 bound for the discretization times, with the error tending to zero as t approaches 0.
- Wasserstein guarantees: Bounded support or sufficiently fast tail decay suffices for polynomial Wasserstein guarantees without functional inequalities.The bounded-support assumption is particularly applicable to image generation because pixel values are bounded.
- Wasserstein and TV guarantees: Theorem 2.1 gives polynomial discretization complexity N = O(poly(d, R, 1/εTV, 1/εW)) and makes the DDPM output εTV-close to a distribution within εW in W2 of Pdata.Under the additional Hessian assumption, the required score-error bound improves up to logarithmic factors.
- Interpretation: The guarantees arise because reverse SDEs track a sequence of score functions and start from a prior close to the forward distribution at sufficiently large T.This distinguishes the analysis from standard Langevin Monte Carlo, where comparable guarantees require structural assumptions even with an exact score.
3 Proof overview
The proof converts L2 score accuracy into convergence control by combining bad-set arguments, divergence estimates, and a distribution-perturbation bound for scores.
- Proof strategy: The proof first interpolates the discretized process and derives a differential inequality for the process with an L∞-accurate estimated score.This provides the starting point for controlling the discretization and score-approximation errors.
- Divergence control: Small step sizes keep χ2(qt||pt) from growing quickly, while the forward process makes this divergence decay exponentially.The analysis uses the Donsker–Varadhan variational principle to express relevant expectations under pt.
- Divergence control: The KL term is controlled without a global log-Sobolev inequality by decomposing bounded-support distributions into mixtures after moving a small amount of mass.The mixture components satisfy log-Sobolev inequalities with the logarithm of the minimum mixture weight bounded below.
- Score perturbation: A perturbation lemma bounds the L2 difference between score functions of two distributions in terms of their χ2-divergence.The paper interprets the score as solving a Bayesian denoising problem, and notes the bound may be independently useful.
- Final error transfer: The proof reduces L2 to L∞ control by bounding visits to a bad set, then transfers error from the forward distribution at positive time to Pdata.The final transfer is Wasserstein in general and total variation under additional smoothness.
- Limitations: The analysis uses a high-probability Hessian bound, while a potentially sharper uniformity treatment is left as an open problem.The authors speculate that replacing a uniform Hessian bound with a high-probability bound could improve parameter dependencies.
4 DDPM with L∞-accurate score estimate
This section analyzes DDPM discretization with L∞-accurate score estimates, controlling the reverse-process error through smoothness, moment, divergence, and step-size bounds.
- Setup: The analysis compares the exact backward SDE with an exponential integrator using an L∞-accurate estimated score.A continuous-time interpolation connects the discrete process to the SDE analysis.
- Error decomposition: The main error bound requires controlling score error, time-discretization terms, KL divergence, and auxiliary state-norm quantities.These quantities are bounded using separate lemmas and the KL term receives a new treatment.
- Convergence conditions: The resulting theorem imposes polynomial-growth conditions on the relevant process parameters and specifies step sizes sufficient for the error bounds.Stronger smoothness assumptions permit larger step sizes than the baseline Hessian-bound analysis.
- Auxiliary bounds: A Hessian bound for distributions supported on a radius-R set controls the score's local regularity after Gaussian smoothing.The bound uses the covariance of a distribution supported on a bounded set.
- Auxiliary bounds: Subgaussian state-norm bounds and initial χ2-divergence estimates provide the remaining auxiliary controls needed by the discretization theorem.The subgaussian estimate applies when the initial distribution is supported on BR(0).
5 Bounding the KL divergence
This section bounds the central KL term without requiring a global log-Sobolev inequality by decomposing the smoothed distribution into suitable mixture components.
- Target quantity: The analysis targets K = KL(ψ_tq_t||p_t), where q_t may be any density rather than necessarily the discretized-process density.This flexibility makes the bound applicable within the broader convergence argument.
- Mixture structure: A mixture of distributions satisfying log-Sobolev inequalities suffices for an additive-slack bound when the minimum mixture weight is not too small.The dependence includes the logarithm of the minimum mixture weight.
- Approximation: Any bounded-support distribution can be approximated by such a mixture after moving a small amount of mass.This removes the need for the original distribution itself to satisfy a global log-Sobolev inequality.
- Construction: The construction partitions the support into small-diameter subsets and uses Gaussian smoothing to obtain components with log-Sobolev control.Covering-number bounds quantify the number of subsets required.
6 The effect of perturbing the data distribution on the score function
This section studies how perturbing the data distribution changes the score, interpreting score estimation as denoising under a prior and controlling mismatched-prior error by coupling.
- Interpretation: The score function is viewed as the solution to an inference problem that recovers the original data point from a noisy observation using the data distribution as prior.This interpretation enables perturbation bounds through denoising error.
- Main consequence: A coupling argument bounds the difference between score functions in terms of the distance between their underlying data distributions.The result supports replacing the data distribution by a nearby perturbed distribution in the KL analysis.
- χ2 perturbations: Under χ2 closeness between two distributions, the denoising analysis yields an L2 score-error bound after the forward DDPM evolution.The proof uses Bayes' rule and Gaussian-noise conditioning.
- TV perturbations: A related TV-based perturbation result uses Lipschitz control of the denoising map and coupling properties to control score differences.The argument combines total-variation, Cauchy–Schwarz, and concentration bounds.
- Small-time behavior: For smooth densities, the forward distribution remains close in TV to the initial density at sufficiently small positive time.The stated condition includes bounded first moment and L-smooth potential assumptions.
7 Guarantees under L2-accurate score estimate
This section converts L2 score accuracy into DDPM convergence guarantees by handling bad-score regions, discretization, tails, and the final small-time gap to the data distribution.
- Assumptions: The analysis assumes a tail function R(ε) satisfying P_data(B_R(ε)(0)) ≥ 1−ε, with sufficiently slow growth as ε approaches zero.Subexponential tails satisfy the condition, and bounded support is a special case.
- L2-to-L∞ reduction: The L2-to-L∞ reduction bounds the probability of entering regions where the score estimate is inaccurate and uses an interpolated reverse process for analysis.The interpolated process uses the estimated score on good regions and the exact score otherwise.
- Wasserstein guarantees: Theorem 7.2 establishes DDPM convergence under L2-accurate score estimates for distributions satisfying the stated tail and regularity conditions.The proof combines the interpolated-process comparison with step-size choices across coarse and fine timepoints.
- Main guarantees: Under additional smoothness, the result gives a purely TV guarantee, while truncation also yields purely Wasserstein guarantees in the general case.The final comparison passes through the forward distribution at a small positive time.
A High-probability bound on the Hessian
This section derives a high-probability bound on the Hessian of ln ept, equivalently the Jacobian of the score function. The argument controls conditional covariance using subgaussianity and an ε-net, yielding a bound with no dependence on the radius.
- The section bounds the Hessian of ln ept, which is the Jacobian of the score function.
- The analysis motivates a smaller typical Hessian through the Gaussian noise difference Y−X, while noting that the worst-case bound can occur at a point with exponentially small probability density.
- An ε-net argument and a union bound control the operator norm of the variance of a conditional distribution with high probability.
- Subgaussianity of X supplies the probabilistic control used in the variance bound, with Jensen’s and Markov’s inequalities appearing in the proof.
- The resulting high-probability bound applies to the law of the DDPM process at time t and has no dependence on the radius.
- The proof reduces the Hessian control to bounding the operator norm of a conditional covariance involving E[v⊤XX⊤v|F].