Convergence of score-based generative modeling for general data distributions

Introduction

Diffusion models have gained huge popularity in recent years in machine learning, as a method to learn and generate new samples from a data distribution. Score-based generative modeling (SGM), as a particular kind of diffusion model, uses learned score functions (gradients of the log-pdf) to transform white noise to the data distribution through following a stochatic differential equation. While SGM has achieved state-of-the-art performance for artificial image and audio generation [SE19, Dat+19, Gra+19, SE20, Son+20, Men+21, Son+21a, Son+21, Jin+22], including being a key component of text-to-image systems [Ram+22], our theoretical understanding of these models is still nascent.

In particular, basic questions on the convergence of the generated distribution to the data distribution remain unanswered. Recent theoretical work on SGM has attempted to answer these questions [De ̵+21, LLT22, De ̵22], but they either suffer from exponential dependence on parameters or rely on strong assumptions on the data distribution such as functional inequalities or smoothness, which are rarely satisfied in practical situations. For example, considering the hallmark application of generating images from text, we expect the distribution of images to be (a) multimodal, and hence not satisfying functional inequalities with reasonable constants, and (b) supported on lower-dimensional manifolds, and hence not smooth. However, SGM still performs remarkably well in these settings. Indeed, this is one relative advantage to other approaches to generative modeling such as generative adversarial networks, which can struggle to learn multimodal distributions [ARZ18].

In this work, we aim to develop theoretical convergence guarantees with polynomial complexity for SGM under minimal data assumptions.

Given samples from a data distribution $P_{\textup{data}}$, the problem of generative modeling is to learn the distribution in a way that allows generation of new samples. A general framework for many score-based generative models is where noise is injected into $P_{\textup{data}}$ via a forward SDE [Son+20]

where $\widetilde{x}_{0}\sim\widetilde{P}_{0}:=P_{\textup{data}}$. Let $\widetilde{p}_{t}$ denote the density of $\widetilde{x}_{t}$. Remarkably, $\widetilde{x}_{t}$ also satisfies a reverse-time SDE,

where $\widetilde{w}_{t}$ is a backward Brownian motion [And82]. Because the forward process transforms the data distribution to noise, the hope is to use the backwards process to transform noise into samples.

Given $L^{2}$-error bounds of the score function, how close is the distribution generated by (2) (with score estimate $s(x,t)$ in place of $\nabla\ln\widetilde{p}_{t}$, and appropriate discretization) to the data distribution $P_{\textup{data}}$?

We note it is more realistic to consider $L^{2}$ rather than $L^{\infty}$-error, and this makes the analysis more challenging. Indeed, prior work on Langevin Monte Carlo [EHZ21] and related sampling algorithms only apply when the score function is known exactly, or with suitable modification, known up to $L^{\infty}$-error. $L^{2}$-error has a genuinely different effect from $L^{\infty}$-error, as it can cause the stationary distribution for Langevin Monte Carlo to be arbitrarily diffferent [LLT22], necessitating a “medium-time" analysis.

In addition, we hope to obtain a result with as few structural assumptions as possible on $P_{\textup{data}}$, so that it can be useful in realistic scenarios where SGM is applied.

2 Prior work on convergence guarantees

We highlight two recent works which make progress on this problem. [LLT22] are the first to give polynomial convergence guarantees in TV distance under $L^{2}$-accurate score for a reasonable family of distributions. They introduce a framework to reduce the analysis under $L^{2}$-accurate score to $L^{\infty}$-accurate score. However, they rely on the data distribution satisfying smoothness conditions and a log-Sobolev inequality—a strong assumption which essentially limits the guarantees to unimodal distributions.

[De ̵22] instead make minimal data assumptions, giving convergence in Wasserstein distance for distributions with bounded support $\mathcal{M}$. In particular, this covers the case of distributions supported on lower-dimensional manifolds, where guarantees in TV distance are unattainable. However, for general distributions, their guarantees have exponential dependence on the diameter of $\mathcal{M}$ and the inverse of the desired error ($\exp(O(\operatorname{diam}(\mathcal{M})^{2}/\varepsilon))$), and for smooth distributions, an improved, but still exponential dependence on the growth rate of the Hessian $\nabla^{2}\ln\widetilde{p}_{t}$ as the noise approaches 0 ($\exp(\widetilde{O}(\Gamma))$ for distributions with $\left\|{\nabla^{2}\ln\widetilde{p}_{t}}\right\|\leq\Gamma/\sigma_{t}^{2}$).

We note that other works also analyze the generalization error of a learned score estimate [BMR20, De ̵22]. This is an important question because without further assumptions, learning an $L^{2}$-accurate score estimate requires a number of samples exponential in the dimension. As this is beyond the scope of our paper, we assume that an $L^{2}$-accurate score estimate is obtainable.

3 Our contributions

In this work, we analyze convergence in the most general setting of distributions of bounded support, as in [De ̵22]. We give Wasserstein bounds for any distribution of bounded support (or sufficiently decaying tails), and TV bounds for distributions under smoothness assumptions, that are polynomial in all parameters, and do not rely on the data distribution satisfying any functional inequality. This gives theoretical grounding to the empirical success of SGM on data distributions that are often multimodal and non-smooth.

We streamline the $\chi^{2}$-based analysis of [LLT22], with significant changes as to completely remove the use of functional inequalities. In particular, the biggest challenge—and our key improvement—is to bound a certain KL-divergence without reliance on a global functional inequality. For this, we prove a key lemma that distributions which are close in $\chi^{2}$-divergence have score functions that are close in $L^{2}$ (which may be of independent interest), and then a structural result that the distributions arising from the diffusion process can be slightly modified as to satisfy the desired inequality, through decomposition into distributions that do satisfy a log-Sobolev inequality.

Upon finishing our paper, we learned of a concurrent and independent work [Che+22] which obtained theoretical guarantees for score-based generative modeling under similarly general assumptions on the data distribution. We note that although our bounds are obtained under similar assumptions (with our assumption of the score estimate accuracy slightly weaker than theirs), our proof techniques are quite different. Following the “bad set” idea from [LLT22], we derived a change-of-measure inequality with Theorem 7.1, while the analysis in [Che+22] is based on the Girsanov approach.

Main results

To state our results, we will consider a specific type of SGM called denoising diffusion probabilistic modeling (DDPM) [HJA20], where in the forward SDE (1), $f(x,t)=-\frac{1}{2}g(t)^{2}x$ for some non-decreasing function $g$ to be chosen. The forward process is an Ornstein-Uhlenbeck process with time rescaling: $\widetilde{x}_{t}$ has the same distribution as

Given an estimate score function $s(x,t)$ approximating $\nabla\ln\widetilde{p}_{t}(x)$, we can simulate the reverse process (reparameterizing $t\mapsfrom T-t$ and denoting $p_{t}:=\widetilde{p}_{T-t}$)

with the exponential integrator discretization [ZC22], where $h_{k}=t_{k+1}-t_{k}$ and $\eta_{k+1}\sim N(0,I_{d})$:

We initialize $z_{0}$ with a prior distribution that approximates $p_{0}=\widetilde{p}_{T}$ for sufficiently large $T$:

While we focus on DDPM, we note that the continuous process underlying DDPM is equivalent to that of score-matching Langevin diffusion (SMLD) under reparameterization in time and space (see [LLT22, §C.2]). We will further take $g\equiv 1$ for convenience in stating our results.

Our goal is to obtain a quantitative guarantee for the distance between the distribution $q_{t_{K}}$ for $z_{t_{K}}$ (for appropriate $t_{K}\approx T$) and $P_{\textup{data}}$, under a $L^{2}$-score error guarantee. In the following, we assume a sequence of discretization points $0=t_{0}<t_{1}<\cdots<t_{K}\leq T$ has been chosen.

For any $t\in\{T-t_{0},\ldots,T-t_{K}\}$, the error in the score estimate is bounded in $L^{2}(\widetilde{p}_{t})$:

We note that the gradient $\nabla\ln\widetilde{p}_{t}$ grows as $\frac{1}{\sigma_{t}^{2}}$ as $t\to 0$, so this is a reasonable assumption, and quantitatively weaker than a uniform bound over $t$.

For simplicity, we assume bounded support when stating our main theorems, but note that our results generalize to distributions with sufficiently fast power decay. In the application of image generation, pixel values are bounded, so Assumption 2 is satisfied with $R$ typically on the order of $\sqrt{d}$.

These are the only assumptions we need to obtain a polynomial complexity guarantee. We also consider the following stronger smoothness assumption, which is Assumption A.6 in [De ̵22] and will give better dependencies. Note that [De ̵22, Theorem I.8] shows a (nonuniform) version of Assumption 3 holds when $p_{0}$ is a smooth density on a convex submanifold.

The following bound of the Hessian of the log-pdf holds for any $t>0$ and $x$:

Finally, the following smoothness assumption on $\widetilde{p}_{0}$ will allow us to obtain TV guarantees.

$P_{\textup{data}}$ admits a density $\widetilde{p}_{0}\propto e^{-V(x)}$ where $V(x)$ is $L$-smooth.

We are now ready to state our main theorems.

Suppose that Assumption 1 and 2 hold with $R\geq\sqrt{d}$. Then there is a sequence of discretization points $0=t_{0}<t_{1}<\cdots<t_{N}<T$ with $N=O(\operatorname{poly}(d,R,1/\varepsilon_{\operatorname{TV}},1/\varepsilon_{\textup{W}}))$ such that if $\varepsilon_{\sigma}=\widetilde{O}\left({\frac{\varepsilon_{\operatorname{TV}}^{6.5}\varepsilon_{\textup{W}}^{5}}{R^{9}d^{2.25}}}\right)$, then the distribution $q_{t_{N}}$ of the output $z_{t_{N}}$ of DDPM is $\varepsilon_{\operatorname{TV}}$-close in TV distance to a distribution that is $\varepsilon_{W}$ in $W_{2}$-distance from $P_{\textup{data}}$. If in addition Assumption 3 holds with $C\geq R^{2}$, it suffices for $\varepsilon_{\sigma}=\widetilde{O}\left({\frac{\varepsilon_{\operatorname{TV}}^{4}}{C^{2}d}}\right)$ (note that the $\widetilde{O}(\cdot)$ hides logarithmic dependence on $\varepsilon_{\textup{W}}$).

This result is perhaps surprising at first glance, as it is well known that for sampling algorithms such as Langevin Monte Carlo, structural assumptions on the target distribution—such as a log-Sobolev inequality—are required to obtain similar theoretical guarantees, even with the knowledge of the exact score function. The key reason that we can do better is that we utilize a sequence of score functions $s_{t}$ along the reverse SDE, which is not available in standard sampling settings. Moreover, we choose $T$ large enough so that $q_{0}=p_{\textup{prior}}$ is close to $p_{0}$, and it suffices to track the evolution of the true process (2), that is, maintain rather than decrease the error. To some extent, this result shows the power of DDPM and other reverse SDE-based methods compared with generative modeling based on standard Langevin Monte Carlo.

A statement with more precise dependencies, and which works for unbounded distributions with sufficiently decaying tails, can be found as Theorem 7.2. We note that under the Hessian bound (Assumption 3), up to logarithmic factors, the same score error bound suffices to obtain a fixed TV distance to a distribution arbitrarily close in $W_{2}$ distance. By truncating the resulting distribution, we can also obtain purely Wasserstein error bounds.

In the same setting as Theorem 2.1, consider the distribution $\widehat{q}_{t_{N}}$ of the truncated output $\widehat{x}_{t_{N}}$ of DDPM. If Assumptions 1 and 2 hold with $R\geq\sqrt{d}$ and $\varepsilon_{\sigma}=\widetilde{O}\left({\frac{\varepsilon_{\textup{W}}^{18}}{R^{22}d^{2.25}}}\right)$, then with appropriate (polynomial) choice of parameters, $W_{2}(\widehat{q}_{t_{K}},P_{\textup{data}})\leq\varepsilon_{\textup{W}}$. If in addition Assumption 3 holds with $C\geq R^{2}$, then $\varepsilon_{\sigma}=\widetilde{O}\left({\frac{\varepsilon_{\textup{W}}^{8}}{C^{2}R^{8}d}}\right)$ suffices.

With an extra assumption on the smoothness of $P_{\text{data}}$, we can also obtain purely TV error bounds:

A more precise statement can be found as Theorem 7.3, which also works more generally with sufficient tail decay. We note that this result can be derived directly by combining Theorem 7.2 and a TV error bound between $P_{\text{data}}$ and $p_{t_{N}}$ (Lemma 6.4) depending on the smoothness of $P_{\text{data}}$.

Proof overview

Our proof uses the framework by [LLT22] to convert guarantees under $L^{\infty}$-accurate score function to under $L^{2}$-accurate score function. For the analysis under $L^{\infty}$-accurate score function, we interpolate the discrete process with estimated score, $z_{t}\sim q_{t}$, and derive a differential inequality

We bound resulting error terms, making ample use of the Donsker-Varadhan variational principle to convert expectations to be under $p_{t}$. Under small enough step sizes, this shows that $\chi^{2}(q_{t}||p_{t})$ grows slowly (Theorem 4.10), which suffices as $\chi^{2}$-divergence decays exponentially in the forward process.

The most challenging error term to deal with is the KL divergence term $\operatorname{KL}(q_{t}\psi_{t}||p_{t})$. Our main innovation over the analysis of [LLT22] is bounding this term without a global log-Sobolev inequality for $p_{t}$. We note that it suffices for $p_{t}$ to be a mixture of distributions each satisfying a log-Sobolev inequality, with the logarithm of the minimum mixture weight bounded below, and in Lemma 5.2, we show that we can decompose any distributed of bounded support in this manner if we move a small amount of its mass.

In Section 6, we show that this does not significantly affect the estimate of the score function, by interpreting the score function as solving a Bayesian inference problem: that of de-noising a noised data point. More precisely, we show in Lemma 6.5 that the difference between the score functions of two different distributions can be bounded in $L^{2}$ in terms of their $\chi^{2}$-divergence, which may be of independent interest.

Finally, we reduce from the $L^{2}$ to $L^{\infty}$ setting by bounding the probabilities of hitting a bad set where the score error is large, and carefully choose parameters (Section 7). This gives a TV error bound to $\widetilde{p}_{\delta}$—the forward distribution at small positive time. Finally, we can bound the Wasserstein distance of $\widetilde{p}_{\delta}$ to $\widetilde{P}_{0}$ (in the general case) or the TV distance (under additional smoothness of $\widetilde{P}_{0}$.)

In Section A we show that the Hessian is always bounded by $O\left({\frac{d}{\sigma_{t}^{2}}}\right)$ with high probability (cf. Assumption 3). We speculate that a high-probability rather than uniform bound on the Hessian (as in Lemma 4.13) can be used to obtain better dependencies, and leave this as an open problem.

We let $\widetilde{p}_{t}$ denote the density of $\widetilde{x}_{t}$ under the forward process (1). Note that $x_{0}\sim\widetilde{P}_{0}$ may not admit a density, but $\widetilde{x}_{t}$ will for $t>0$. For the reverse process, we use the notation $p_{t}=\widetilde{p}_{T-t}$, $x_{t}=\widetilde{x}_{T-t}$. We defined $m_{t}$ and $\sigma_{t}$ in (2),

and note that $\widetilde{p}_{t}=(M_{m_{t}\sharp}\widetilde{P}_{0})*\varphi_{\sigma_{t}^{2}}$, where $M_{m}(x)=mx$ denotes multiplication by $m$, $F_{\sharp}P$ denotes the pushforward of the measure $P$ by $F$, and $\varphi_{\sigma^{2}}$ is the density of $N(0,\sigma^{2}I_{d})$. When $g\equiv 1$, we note the bound $\sigma_{t}^{2}\leq\min\{1,t\}$ and $\sigma_{t}^{2}=\Theta(\min\{1,t\})$.

We will let $z_{t}$ denote the (interpolated) discrete process (see (12)) and let $q_{t}$ be the density of $z_{t}$. We define

and note that $q_{t}\psi_{t}$ is a probability density. We defined $G_{t^{\prime},t}=\int_{t^{\prime}}^{t}g(T-s)^{2}\,ds$ in (6).

We denote the estimated score function by either $s(x,t)$ and $s_{t}(x)$ interchangeably.

A random variable $X$ is subgaussian with constant $C$ if

We consider the error between the exact backwards SDE (4) and the exponential integrator with estimated score (5). In this section, we bound the error assuming that the score estimate $s$ is accurate in $L^{\infty}$.

For any $t\in\{T-t_{0},\ldots,T-t_{K}\}$, the error in the score estimate is bounded:

for some non-decreasing function $\varepsilon_{\infty,t}^{2}$.

In Section 7, we will relax this condition to score function being accurate in $L^{2}$.

First, we construct the following continuous-time process which interpolates the discrete-time process (5), for $t\in[t_{k},t_{k+1}]$:

where $G_{t^{\prime},t}$ is defined in (6).

Letting $q_{t}$ be the distribution of $z_{t}$ and $p_{t}$ be the distribution of $x_{t}$, we have by [LLT22, Lemma A.2] that

To bound (14), we use the following lemma.

Suppose that (11) holds for $t=T-t_{k}$, $\nabla\ln p_{t_{k}}(x)$ is $L_{T-t_{k}}$-Lipschitz, $g$ is non-decreasing, and that $h_{k}\leq\frac{1}{20L_{T-t_{k}}g(T-t_{k})^{2}}$. Then we have for $t\in[t_{k},t_{k+1}]$ that

We bound the second term on the RHS of (14). By Lemma 4.1,

by definition of $\varepsilon_{\infty,t}$, so by Lemma 4.3,

The condition on $h_{k}$ and the fact that $g$ is non-decreasing implies $192G_{t_{k},t}^{2}L_{T-t_{k}}^{2}\leq\frac{1}{2}$. Rearranging gives

Substituting into (15) and that inequality into (14) give the conclusion. ∎

Suppose that $h_{k}\leq\frac{1}{2g(T-t_{k})^{2}}$. Then for $t\in[t_{k+1},t_{k}]$,

Consider (13). The assumption on $h_{k}$ implies $G_{t_{k},t}\leq G_{t_{k},t_{k+1}}\leq\frac{1}{2}$, so $\exp\left({\frac{1}{2}G_{t_{k},t}}\right)-1\leq G_{t_{k},t}$. Let $Y$ denote the last term of (13). Then

Again using $G_{t_{k},t}\leq\frac{1}{2}$, rearranging gives

Note that $Y:=\int_{t_{k}}^{t}\exp\left({\frac{1}{2}\int_{t_{k}}^{t^{\prime}}g(T-t^{\prime\prime})^{2}\,dt^{\prime\prime}}\right)g(t^{\prime})\,dw_{t^{\prime}}$ is a Gaussian random vector with variance

(Note that this calculation shows that the continuous-time process (12) does agree with the discrete-time process (5) at $t=t_{k+1}$.) Using the Donsker-Varadhan variational principle, for any random variable $X$,

Now following [Che+21, Theorem 4], we set $c=\frac{1}{8(\exp(G_{t_{k},t})-1)}$, so that

Substituting everything into (17) gives the desired inequality. ∎

In order to bound the RHS in Lemma 4.2, we need to bound all four of these quantities, which we do in Lemma 4.5, 4.6, 4.8, and Section 5, respectively. The main innovation in our analysis compared to [LLT22] is a new way to bound $K$, which we present in a separate section.

(In other words, this is the usual Orlicz norm applied to $\left\|{X}\right\|_{2}$.)

By the Donsker-Varadhan variational principle,

The following bounds $K_{V}$; note that the proof does not depend on the definition of $q_{t}$, only that it is a probability density.

We use the following lemma to bound $K_{\Delta V}$ in Lemma 4.8.

Suppose that $h_{k}\leq\frac{1}{4Lg(T-t_{k})^{2}}$ where $\nabla\ln p_{t}$ is $L_{T-t}$-smooth ($L_{T-t}\geq 1$) and $L=\max_{t\in[t_{k},t_{k+1}]}L_{T-t}$. For $t\in[t_{k},t_{k+1}]$,

We have the following relationship for $t\in[t_{k},t_{k+1}]$:

where $p_{\alpha}(x)=\alpha^{d}p(\alpha x)$, $\alpha=e^{\frac{1}{2}\int_{t_{k}}^{t}g(T-s)^{2}\,ds}$ and $\sigma^{2}=1-e^{-\int_{t_{k}}^{t}g(T-s)^{2}\,ds}$. Observe that since $h_{k}\leq\frac{1}{4g(T-t_{k})^{2}}$,

so the hypothesis of Lemma 4.7 is satisfied. Using Lemma 4.7, we obtain

Now we put everything together. Write $G_{t}=G_{t_{k},t}$ for short. Suppose $L_{t}$ is non-increasing. By Lemma 4.2,

By Lemma 4.8, $K_{\Delta V}\leq 25L_{T-t}^{2}(8G_{t}d+G_{t}^{2}K_{z})+100L_{T-t}^{2}G_{t}^{2}K_{V}$, so

By Lemma 4.5, $K_{z}\leq\left\|{x_{t}}\right\|_{2,\psi_{2}}^{2}(K+\ln 2)$, and by Corollary 4.6, $K_{V}\leq\frac{4}{\chi^{2}(q_{t}||p_{t})+1}\cdot\mathscr{E}_{p_{t}}\left({\frac{q_{t}}{p_{t}}}\right)+2dL$, so

Now, if $h_{k}\leq\frac{\varepsilon^{\prime}_{h_{k}}}{20g(T-t_{k})^{2}L_{T-t_{k+1}}}$, then

Let $M_{T-t}:=\left\|{x_{t}}\right\|_{2,\psi_{2}}^{2}$. Assume that $K\leq\frac{A_{T-t}}{\chi^{2}(q_{t}||p_{t})+1}+B_{T-t}$. Then we obtain

If $\varepsilon^{\prime}_{h_{k}}\leq\min\left\{{\frac{1}{\sqrt{48(A_{T-t}M_{T-t}+4)}},\frac{1}{128L_{T-t}A_{T-t}}}\right\}$, then

If $\varepsilon^{\prime}_{h_{k}}\leq\min\left\{{\frac{\sqrt{\varepsilon^{\prime}}}{g(T-t)\sqrt{24(T-t_{k})((B_{T-t}+\ln 2)M_{T-t}+2dL_{T-t})}},\frac{\varepsilon^{\prime}}{24g(T-t)^{2}(T-t)L_{T-t}(8B_{T-t}+6d+16\ln 2)}}\right\}$, we get

Taking $\varepsilon^{\prime}=\frac{\varepsilon}{\ln\left({\frac{T}{T-t_{N}}}\right)}$ then gives the following Theorem 4.10. We first introduce a technical assumption.

Assumption 5 holds for $\varepsilon_{\infty,t}$.

$\left\|{\widetilde{x}_{t}}\right\|_{2,\psi_{2}}^{2}\leq M_{t}$.

The KL bound $\operatorname{KL}(\psi_{t}q_{t}||p_{t})\leq\frac{A_{T-t}}{\chi^{2}(q_{t}||p_{t})+1}+B_{T-t}$ holds for any density $q_{t}$ and $t<t_{N}$, where $\psi_{t}(x)=\frac{q_{t}(x)/p_{t}(x)}{\chi^{2}(q_{t}||p_{t})+1}$.

$g(t),A_{t},B_{t},L_{t},M_{t}$ have at most polynomial growth and decay (with some constant $c$).

Then there is some constant $c^{\prime}$ (depending on $c$) such that if the step sizes satisfy

This follows from the above calculations and the observation that if we replace $F(T-t)$ by $F(T-t_{k})$, for some $F$ satisfying the power growth and decay assumption, then we change the bound by at most a constant factor, because the step size satisfies $h_{k}=t_{k+1}-t_{k}\leq\frac{T-t_{k}}{2}$. ∎

We specialize this theorem in the case of distributions with bounded support. Note that although not every initial distribution $\widetilde{p}_{t}$ may satisfy a KL inequality as required by condition 3 of Theorem 30, Lemma 5.2 will give the existence of a distribution that does, and is close in TV-error. Later in Section 6, we show that this will have a small effect on the score function, and hence allow us to prove our main theorems.

Suppose that Assumptions 5 and 2 hold, $R^{2}\geq d$, $g\equiv 1$, and that $\widetilde{P}_{0}$ is such that the KL inequality (30) holds. Let $\delta=T-t_{N}$. If $0<\delta,\varepsilon<\frac{1}{2}$, $h_{k}=O\left({\frac{\varepsilon}{\max\{T-t_{k},(T-t_{k})^{-3}\}R^{4}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R}{\delta\varepsilon_{K}}}\right)}}\right)$, then for any $0\leq k\leq N$,

For $g\equiv 1$, note that $\sigma_{T-t}^{2}=\Theta(\min\{T-t,1\})$. From Lemma 4.13, we can choose

We now check the requirements on $h_{k}$. We need

As long as $R^{2}=\Omega(d)$ and $\varepsilon<1$, the last equation implies all the others. Plugging this into Theorem 4.10 gives the result. ∎

Above, we use the Hessian bound $\left\|{\nabla^{2}\ln p_{t}(x)}\right\|\leq\frac{R^{2}}{\sigma_{t}^{4}}$ given in Lemma 4.13. Under the stronger smoothness assumption given by Assumption 3, we can take the step sizes to be larger.

Suppose that Assumptions 5, 2, 3 hold, $C\geq R^{2}\geq d$, $g\equiv 1$, and that $\widetilde{P}_{0}$ is such that the KL inequality (30) holds. Let $\delta=T-t_{N}$. If $0<\delta,ep<\frac{1}{2}$ and $\varepsilon<1/\sqrt{T}$, $h_{k}=O\left({\frac{\varepsilon}{\max\{T-t_{k},(T-t_{k})^{-1}\}C^{2}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R}{\delta\varepsilon_{K}}}\right)}}\right)$, then for any $0\leq k\leq N$,

We instead have the bound $L_{t}=\frac{C}{\sigma_{t}^{2}}$. The requirement (22) stays the same, while (23) is implied by $\varepsilon^{\prime}_{h_{k}}=O(1/C)$. Inequality (24), for $T-t_{k}\leq 1$, is implied by

Finally, the last requirement is implied by

and for $C\geq R^{2}$, $\varepsilon\leq 1/\sqrt{T}$, implies all the others. ∎

In this section we give bounds on the Hessian ($L_{t}$, Lemma 4.13), initial $\chi^{2}$ divergence $\chi^{2}(q_{0}||p_{0})$ (Lemma 4.14), and Orlicz norm ($M_{t}$, Lemma 4.15).

Therefore, for $\widetilde{P}_{0}$ supported on $B_{R}(0)$, $R\geq 1$, we have

The covariance of a distribution supported on a set of radius $R$ is bounded by $R^{2}$ in operator norm. Inequality (25) then follows from (28).

For (26), note that $\widetilde{p}_{t}=M_{m_{t}\sharp}\widetilde{P}_{0}*\varphi_{\sigma_{t}^{2}}$, where $m_{t}$ is given by (2) and $M_{m}$ denotes multiplication by $m$. Since $M_{m_{t}\sharp}\widetilde{P}_{0}$ is supported on $B_{m_{t}R}(0)\subset B_{R}(0)$ and $\sigma_{t}\leq 1$, the result follows. ∎

Suppose that $\widetilde{P}_{0}$ is supported on $B_{R}(0)$. Let $p_{\textup{prior}}=N(0,(1-e^{G_{0,t}})I_{d})$. Then

and for $0<\varepsilon<\frac{1}{2}$ and $G_{0,T}\geq\ln\left({\frac{4R^{2}}{\varepsilon^{2}}}\right)\vee 1$, we have $\chi^{2}(p_{\textup{prior}}||\widetilde{p}_{T})\leq\varepsilon^{2}$.

We have for $x_{0}\sim\widetilde{P}_{0}$ that

Using convexity of $\chi^{2}$-divergence then gives the result. For $G_{0,T}\geq\ln\left({\frac{4R^{2}}{\varepsilon^{2}}}\right)\vee 1$, we have

Suppose $\widetilde{P}_{0}$ is supported on $B_{R}(0)$. Then for $X\sim\widetilde{p}_{t}$,

where $m_{t},\sigma_{t}$ are as in (2) and $C_{1}$ is an absolute constant.

Let $Y\sim\widetilde{P}_{0}$ s.t. $X=m_{t}Y+\sigma_{t}\xi$ for some $\xi\sim N(0,I_{d})$ independent of $Y$. Define $U=\left\|{X}\right\|_{2}:=\left({\sum_{i=1}^{d}X_{i}^{2}}\right)^{1/2}$, then for $p\geq 1$,

where $\Gamma$ is the commonly used gamma function and $C_{1}$ is an absolute constant. Therefore

where $K=2m_{t}R+3C_{1}\sigma_{t}\sqrt{d}$. Now consider $V=U/K$, then for some $\lambda>0$ small enough, by Taylor expansion,

provided that $2e\lambda^{2}<1$, in which case the geometric series above converges. To bound this quantity further, we can use the numeric inequality $1/(1-x)\leq e^{2x}$ which is valid for $x\in[0,1/2]$. It follows that

Bounding the KL divergence

In this section, we bound the quantity $K=\operatorname{KL}(\psi_{t}q_{t}||p_{t})$, where $\psi_{t}$ is as in (8). While $p_{t}$ is defined by the DDPM process, in this section we do not assume $q_{t}$ is the density of the discretized process; rather, it is any density for which $\mathscr{E}_{p_{t}}\left({\frac{q_{t}}{p_{t}}}\right)$ and $\chi^{2}(q_{t}||p_{t})$ are finite.

where $w_{j}>0$, $\sum_{j=1}^{m}w_{j}=1$, and each $\widetilde{P}_{j,0}$ is a probability measure. For $t>0$, let $\widetilde{p}_{t}$ and $\widetilde{p}_{j,t}$ be the densities obtained by running the forward DDPM process (1) for time $t$, and $p_{t}=\widetilde{p}_{T-t}$, $p_{j,t}=\widetilde{p}_{j,T-t}$. Let $w_{\min}=\min_{1\leq j\leq m}w_{j}$ and suppose all the $\widetilde{P}_{j,t}$ satisfy a log-Sobolev constant with constant $C_{t}$. Then for any $q_{t}$, where $\psi_{t}$ is as in (8)

While we need $p_{t}$ to satisfy a log-Sobolev inequality to get a bound of the form $\frac{C}{\chi^{2}(q_{t}||p_{t})+1}\mathscr{E}_{p_{t}}\left({\frac{q_{t}}{p_{t}}}\right)$ ([LLT22, Lemma C.8]), we note that if we allow additive slack, it suffices for $p_{t}$ to be a mixture of distributions satisfying a log-Sobolev inequality, with the logarithm of the minimum mixture weight bounded below. In Lemma 5.2 we will see that we can almost decompose any distribution of bounded support in this manner, if we move a small amount of the mass.

By decomposition of entropy and the fact that each $P_{i,t}$ satisfies LSI with constant $C_{T-t}$,

where the last inequality follows from noting $w_{j}\overline{f}_{t}(j)$ is a probability mass function on $[m]$, so that $\overline{f}_{t}(j)\leq\frac{1}{w_{j}}$ and

Suppose $0<\varepsilon_{K}<\frac{1}{2}$, and that $\overline{P}_{0}$ is a probability measure such that $\overline{P}_{0}(\mathcal{M})\geq 1-\frac{\varepsilon_{K}}{8}$. Let $\mathcal{N}\left({\mathcal{M},\frac{\sigma_{t}}{2}}\right)$ denote the covering number of $\mathcal{M}$ with balls of radius $\sigma_{t}$. Given $\delta>0$, there exists a distribution $\widetilde{P}_{0}$ such that $\chi^{2}(\widetilde{P}_{0}||\overline{P}_{0})\leq\varepsilon_{K}$ and considering the DDPM process started with $\widetilde{P}_{0}$, for all $0\leq t\leq T-\delta$,

Partition $\mathcal{M}$ into disjoint subsets $\mathcal{M}_{j}$, $1\leq j\leq N:=\mathcal{N}(\mathcal{M},\sigma_{\delta}/2)$ of diameter at most $\sigma_{\delta}$, and decompose

where $p_{j}$ is supported on $\mathcal{M}_{j}$ and $P_{*}=\overline{P}_{0}(\cdot|\mathcal{M}^{c})$. We will zero out the coefficients of all small components: let $Z=\sum_{j:w_{j}\geq\frac{\varepsilon_{K}}{8N}}w_{j}$ and

Note that $Z\geq 1-\frac{\varepsilon_{K}}{8}-\sum_{j:w_{j}\leq\frac{\varepsilon_{K}}{8N}}\geq 1-\frac{\varepsilon_{K}}{4}$. As probability distributions on $[m]\cup\{*\}$,

and hence the same bound holds for $\chi^{2}(\widetilde{P}_{0}||\overline{P}_{0})$. Note each $M_{m_{t}\sharp}\widetilde{P}_{j,0}$ is supported on a set of diameter $m_{t}\sigma\leq\sigma$. By Theorem 1 of [CCN21], noting that

when $\Sigma=\sigma^{2}I$ and $\left\|{\mu_{2}-\mu_{1}}\right\|\leq\sigma$, $\widetilde{P}_{j,t}=(M_{m_{t}\sharp}\widetilde{P}_{j,0})*\varphi_{\sigma^{2}}$ satisfies a log-Sobolev inequality with constant $6(1+e)\sigma_{t}^{2}$. The result then follows from Lemma 5.1. For $\mathcal{M}=B_{R}(0)$, we use the bound $\mathcal{N}(B_{R}(0),\sigma_{\delta}/2)\leq\left({1+\frac{4R}{\sigma_{\delta}}}\right)^{d}$ [Ver18, Corollary 4.2.13]. ∎

In the next section, we show that we can move a small amount of mass $\varepsilon$ without significantly affecting the score function. This is necessary, as our guarantees on the score estimate are for the original distribution and not the perturbed one in Lemma 5.2.

The effect of perturbing the data distribution on the score function

In this section we consider the effect of perturbing the data distribution on the score function. The key observation is that the score function can be interpreted as the solution to an inference problem, that of recovering the original data point from a noisy sample, with data distribution as the given prior distribution. We show through a coupling argument that we can bound the difference between the score functions in terms of the distance between the two data distributions. This will allow us to “massage” the data distribution in order to optimally bound $\operatorname{KL}(\psi_{t}q_{t}||p_{t})$ in Section 5.

We first give a general lemma on denoising error from a mismatched prior.

Let $\varepsilon_{\operatorname{TV}}=\operatorname{TV}(P_{0,x},P_{1,x})$ and $\varepsilon_{\chi}^{2}=\chi^{2}(P_{0,x}||P_{1,x})$. Then

For $\varphi=\varphi_{\sigma^{2}}$, the upper bound is $O\left({\sigma^{2}\varepsilon_{\chi}\left({d+\ln\left({\frac{1}{\varepsilon_{\operatorname{TV}}}}\right)}\right)}\right)$.

Note the tricky part of the proof is to deal with $P_{1}(dx_{1}|y_{0})$, which can be thought of as inferring $x$ assuming the incorrect prior $P_{1,x}$, rather than the actual prior $P_{0,x}$.

so $Q$ is absolutely continuous with respect to $P_{0,y}$ and $P_{1,y}$, and by assumption on the coupling,

Under $P_{0,1}$, when $y_{0}=y_{1}$, we can couple $P_{0}(d\widehat{x}_{0}|y_{0})$ and $P_{1}(d\widehat{x}_{1}|y_{0})$ so that $x_{0}=x_{1}$ with probability $\min\left\{{\frac{dQ}{dP_{0,y}},\frac{dQ}{dP_{1,y}}}\right\}$. Let $\widehat{P}(d\widehat{x}_{0},d\widehat{x}_{1}|y_{0})$ denote this coupled distribution. Then as in Lemma 6.5,

which follows from the two inequalities (using (31))

From (32), and the fact that the distribution of $(x_{i},y_{i})$ is the same as $(\widehat{x}_{i},y_{i})$ by Nishimori’s identity, we obtain

The first term satisfies $\int_{\{y_{0}\neq y_{1}\}}P_{0,1,y}(dy_{0},dy_{1})\left\|{r_{0}(y_{0})}\right\|^{2}\leq m^{(2)}(\varepsilon_{\operatorname{TV}})$. For the second term, we note that Cauchy-Schwarz gives for any measures $P$ and $Q$ that

to switch from the measure $P_{0,y}$ to $P_{1,y}$:

(Note that intentionally, the measure is $P_{1,y}$, though we use $y_{0}$ for the variable.) Hence,

where we used the data processing inequality.

For $\varphi=\varphi_{\sigma^{2}}$, we obtain by Lemma 6.6 that the bound is

We use this lemma to obtain a bound on the $L^{2}$ score error under perturbation of the distribution, by interpreting the score as the solution to a de-noising problem.

Let $\widetilde{p}_{t}^{(i)}$ be the density resulting from running (1) starting from $\widetilde{P}^{(i)}$, and let $\sigma_{t}$ be as in (2). Then for any $t>0$,

where $\widetilde{P}^{(i)}_{y,\sigma^{2}}$ is the “tilted" probability distribution defined by

By Bayes’s rule, this can be viewed as the conditional probability that $x_{0}=x$ given $x_{t}=y$, where $x_{0}\sim\widetilde{P}^{(i)}$ and $y=x_{0}+\sigma\xi$, $\xi\sim N(0,I_{d})$. Hence this fits in the framework of Lemma 6.1 and

For part 2, note that $\widetilde{p}^{(i)}_{t}=(M_{m_{t}\sharp}\widetilde{P}^{(i)})*\varphi_{\sigma_{t}^{2}}$. Applying part 1 with $\widetilde{P}^{(i)}\mapsfrom M_{m_{t}\sharp}\widetilde{P}^{(i)}$ (which preserves $\chi^{2}$-divergence) and $\sigma=\sigma_{t}$ gives the result.

Finally, we argue that a score estimate that is accurate with respect to $\widetilde{p}^{(1)}_{t}$ will still be accurate with respect to $\widetilde{p}^{(0)}_{t}$, with high probability. When using this lemma, we will substitute in the bound from Lemma 6.2.

for $t\in(0,T]$, and $\nabla\ln\widetilde{p}_{t}^{(0)}$ is $L_{t}$-Lipschitz. Then for $t\in(0,T]$ and any $\varepsilon_{\infty}>0$,

The first term is bounded by $\operatorname{TV}(\widetilde{P}^{(0)},\widetilde{P}^{(1)})\leq\varepsilon$. For the second term, by Chebyshev’s Inequality,

For the last term, again by Chebyshev’s Inequality,

We conclude the proof by combining the these three inequalities. ∎

Finally, we will need the following to obtain a TV error bound to $\widetilde{p}_{0}$ in Theorem 2.3.

where in the second inequality, we use the fact that $1-e^{x}\leq\left|{x}\right|$ for all $x\leq 0$. Thus

where $\varphi(y)$ is the density of the $d$-dimensional standard Gaussian distribution. Apply Minkowski’s inequality for integrals:

Now we conclude the proof by combining the bounds for $\operatorname{TV}(\widetilde{p}_{t},\widetilde{q}_{t})$ and $\operatorname{TV}(\widetilde{p}_{0},\widetilde{q}_{t})$:

where we use the fact that $\ln x\leq x-1$ for all $x\geq 1$. Recall that $\alpha_{t}=1/m_{t}=e^{t/2}$ and $\sigma_{t}^{2}=1-e^{-t}$ when $g\equiv 1$. It suffices for

2 Perturbation under TV error

Although we will not need it in our proof, we note that we can derive a similar perturbation result under TV error, which might be of independent interest.

$x_{0}=x_{1}$ with probability $1-\varepsilon$,

For notational clarity, we will denote draws from the conditional distribution as $\widehat{x}_{0}$ and $\widehat{x}_{1}$, for example $P_{0}(d\widehat{x}_{0}|y_{0})$. We have

As in Lemma 6.2, under $P_{0,1}$, when $y_{0}=y_{1}$, we can couple $P_{0}(d\widehat{x}_{0}|y_{0})$ and $P_{1}(d\widehat{x}_{1}|y_{0})$ so that $x_{0}=x_{1}$ with probability $\min\left\{{\frac{dQ}{dP_{0,y}},\frac{dQ}{dP_{1,y}}}\right\}$. Let $\widehat{P}(d\widehat{x}_{0},d\widehat{x}_{1}|y_{0})$ denote this coupled distribution. Then

Finally, for the second term (II), we use the fact that $r_{1}$ is $L_{1}$ Lipschitz and the coupling to conclude

We conclude the proof by combining the inequalities for (i), (ii), and (II).

3 Gaussian tail calculation

We use the following Gaussian tail calculation in the proof of Lemma 6.2.

Let $\mu$ be the standard Gaussian measure on $N(0,I_{d})$. Then

By the $\chi^{2}$ tail bound in [LM00], for $t\geq 0$,

so $\left\|{X}\right\|^{2}$ is stochastically dominated by a random variable with cdf $F(y)=1-e^{-\frac{y-2d}{3}}$. Then letting $P_{Y}$ be the measure corresponding to $F$,

We will state our results under a more general tail bound assumption.

$R:\to[0,\infty)$ is a function such that $P_{\textup{data}}(B_{R(\varepsilon)}(0))\geq 1-\varepsilon$.

Our result will require $R(\varepsilon)$ to grow at most as a sufficiently small power of $\varepsilon^{-1}$ as $\varepsilon\to 0$; in particular, this holds for subexponential distributions. By taking $R$ to be a constant function, this contains the assumption of bounded support (Assumption 2) as a special case.

We follow the framework of [LLT22] to convert guarantees under $L^{\infty}$-accurate score estimate, to guarantees under $L^{2}$-accurate score estimate.

If $Z_{k}\in B_{k}^{c}$ for all $0\leq k\leq n-1$, then $Z_{n}=\overline{Z}_{n}$.

$\chi^{2}(\overline{q}_{n}||p_{n})\leq D_{n}^{2}$.

Let $0<\varepsilon_{\chi},\varepsilon_{\operatorname{TV}},\delta<\frac{1}{2}$. Suppose that Assumption 6 for a sufficiently small value of $c$ that $R_{0}$ is such that $R\left({\frac{c\varepsilon_{\operatorname{TV}}^{3}\delta^{6}\varepsilon_{\chi}^{12}}{R_{0}^{19}d^{5}}}\right)\leq R_{0}$, and $R_{0}^{2}\geq d$. Suppose one of the following cases holds.

Let $P_{\textup{data}},s(\cdot,t)$ be such that Assumption 1 holds, with $R_{0}^{2}\geq d$. Suppose that

where $B=R_{0}^{4}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R_{0}d}{\delta\varepsilon_{\operatorname{TV}}\varepsilon_{\chi}}}\right)$, and we run (5) starting from $p_{\textup{prior}}$ for time $T=\ln\left({\frac{16R_{0}^{2}}{\varepsilon_{\chi}^{2}}}\right)$, $N=O\left({\frac{B\left({T+\frac{1}{\delta^{2}}}\right)}{\varepsilon_{\chi}^{2}}}\right)$ steps with step sizes satisfying $h_{k}=O\left({\frac{\varepsilon_{\chi}^{2}}{B\max\{T-t_{k},(T-t_{k})^{-3}\}}}\right)$.

Let $P_{\textup{data}},s(\cdot,t)$ be such that Assumptions 1 and 3 hold, with $C\geq R_{0}^{2}$. Suppose

where $B=C^{2}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R_{0}d}{\delta\varepsilon_{\operatorname{TV}}\varepsilon_{\chi}}}\right)$, and we run (5) starting from $p_{\textup{prior}}$ for time $T=\ln\left({\frac{16R_{0}^{2}}{\varepsilon_{\chi}^{2}}}\right)$, $N=O\left({\frac{B\left({T+\ln\left({\frac{1}{\delta}}\right)}\right)}{\varepsilon_{\chi}^{2}}}\right)$ steps with step sizes satisfying $h_{k}=O\left({\frac{\varepsilon_{\chi}^{2}}{B\max\{T-t_{k},(T-t_{k})^{-1}\}}}\right)$.

Then the resulting distribution $q_{t_{N}}$ is such that $q_{t_{N}}$ is $\varepsilon_{\operatorname{TV}}$-far in TV distance from a distribution $\overline{q}_{t_{N}}$, where $\overline{q}_{t_{N}}$ satisfies $\chi^{2}(\overline{q}_{t_{N}}||p_{t_{N}})\leq\varepsilon_{\chi}^{2}$. In particular, taking $\varepsilon_{\chi}=\varepsilon_{\operatorname{TV}}$, we have $\operatorname{TV}(q_{T},P_{\textup{data}})\leq 2\varepsilon_{\operatorname{TV}}$.

Note that the condition on $R$ can be satisfied if $R(\varepsilon)=o(R^{-1/19})$ (no effort has been made to optimize the exponent).

We invoke Lemma 5.2 for a $\varepsilon_{K}$ to be chosen, to obtain a distribution $\widetilde{P}_{0}$ on $B_{R_{0}}(0)$, where $R_{0}\geq R(\varepsilon_{K}/8)$. Let $B=R_{0}^{4}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R_{0}}{\delta\varepsilon_{K}}}\right)$ and $B=C^{2}d\ln\left({\frac{T}{\delta}}\right)\ln\left({\frac{R_{0}}{\delta\varepsilon_{K}}}\right)$ in case 1 and case 2, respectively; our choice of $\varepsilon_{K}=O\left({\frac{\varepsilon_{\operatorname{TV}}^{2}\delta^{6}}{n^{2}R_{0}^{6}}}\right)$ will give the definition of $B$ in the theorem statement. In the following, we define $\widetilde{p}_{t}$ with $\widetilde{P}_{0}$, rather than $P_{\textup{data}}$, as the initial distribution. Note that since $\operatorname{TV}(P_{\textup{data}},\widetilde{P}_{0})\leq\sqrt{\varepsilon_{K}}=o(\varepsilon_{\operatorname{TV}})$ (and the same holds for their evolutions under (1)), it suffices to consider convergence to $\widetilde{p}_{\delta}$.

We first define the bad sets where the error in the score estimate is large,

for some $\varepsilon_{\infty,t}$ to be chosen.

Given $t\geq 0$, let $t_{-}=t_{k}$ where $k$ is such that $t\in[t_{k},t_{k+1})$. Given bad sets $B_{t}$, define the interpolated process on $[t_{k},t_{k+1})$ by