A Good Score Does not Lead to A Good Generative Model

At the heart of our argument is that a simple Kernel Density Estimation (KDE) of the target ground-truth distribution can be arbitrarily close. Yet, drawing a sample from the ground-truth and drawing one from a KDE presents very different features. The latter fails on the task of “generation.”

To be mathematically more precise, let $p_{\ast}(x)$ be the ground-truth distribution, and $\{y_{i}\}_{i=1}^{N}$ be a set of i.i.d samples drawn from it. The empirical distribution is ${\mathsf{p}_{\ast}}:=\frac{1}{N}\sum_{i=1}^{N}\delta_{y_{i}}$. We denote $\mathsf{p}_{\ast}^{\gamma}:={\mathsf{p}_{\ast}}*\mathcal{N}_{\gamma}$ the distribution obtained by smoothing ${\mathsf{p}_{\ast}}$ with a Gaussian kernel $\mathcal{N}_{\gamma}:=\mathcal{N}(0,\gamma^{2}I_{d\times d})$. Such definition naturally puts $\mathsf{p}_{\ast}^{\gamma}$ as one kind of Kernel Density Estimation (KDE) of $p_{\ast}$ with the bandwidth $\gamma$.

It is intuitive that when the sample size $N$ is large, and the bandwidth $\gamma$ is properly chosen, the KDE $\mathsf{p}_{\ast}^{\gamma}$ approximates the true distribution $q$. In the most extreme case, when the bandwidth $\gamma\to 0$, the kernel density estimate $\mathsf{p}_{\ast}^{\gamma}$ degenerates to the empirical distribution ${\mathsf{p}_{\ast}}$. Throughout the paper we view the empirical distribution as a special case of KDE.

Though $p_{\ast}$ and $\mathsf{p}_{\ast}^{\gamma}$ are close, generating samples from $p_{\ast}$ and from $\mathsf{p}_{\ast}^{\gamma}$ are drastically different stories. Drawing from $p_{\ast}$ amounts to generate a completely new sample, independent of the dataset, while generating from $\mathsf{p}_{\ast}^{\gamma}$ essentially means selecting a sample uniformly from the set $\{y_{i}\}_{i=1}^{N}$ and then applying a Gaussian blurring. Regardless of how close $\mathsf{p}_{\ast}^{\gamma}$ approximates the ground-truth $p_{\ast}$, sampling from KDE ultimately gives replicas of the existing samples.

Would SGM be different from KDE? SGM is built on a complicated procedure, incorporating forward noise injection, score matching, and backward sampling processes. The machinery is significantly more convoluted than the straightforward KDE approach. Would it be able to generate new samples?

We are to show in this paper that the perfect SGM is actually a KDE itself. The mathematical statement is presented in Theorem 4.3. The “perfect” means the minimizer of the empirical score matching objective is achieved during the score-matching procedure. We term the learned score function the empirical optimal score function. Since SGM equiped with the empirical optimal score function is effectively a KDE, it sees the limitation of KDE and fails to “generate.” This phenomenon is clearly demonstrated in Figure 1 with the test conducted over the CIFAR10 dataset.

It is important to note that this observation does not contradict existing theories that suggest SGMs can approximate the target distribution $q$ when the score function is accurately learned. Indeed, in Theorem 3.1 we provide a sample complexity estimate and derive a lower bound of the sample size $N$. When the sample size is sufficiently large, the empirical optimal score function approximates the ground-truth score function. Consequently, according to the existing theories, the output of SGM is a distribution close to the ground-truth target distribution. Yet, two distribution being close is not sufficient for the task of generation.

The primary contribution of this paper is presenting a counter-example of score-based generative models (SGMs) with accurate approximated score function, yet producing unoriginal, replicated samples. Our findings are substantiated through the following two steps:

• •

  We establish in Theorem 3.1 the score-matching error of the empirical optimal score function, and present an explicit non-asymptotic error bound with the sample complexity. This result illustrates that the empirical optimal score function satisfies the standard $L^{2}$ bound on the score estimation error used in the convergence analysis in the existing literature (Chen et al., 2022, 2023c, 2023d; Benton et al., 2023a), which presumably should lead to the conclusion that SGMs equipped with the empirical optimal score function produces a distribution close to the target distribution.

• •

  We show in Theorem 4.3 that SGMs equipped with empirical optimal score function resembles a Gaussian KDE, and thus presents strong memorization effects and fails to produce novel samples.

These results combined rigorously demonstrates that the SGM with precise empirical score matching is capable to produce a distribution close to the target, but the procedure does not ensure the efficacy of an SGM in its ability to generate innovative and diverse samples. This observation underscores the limitation of current upper bound type guarantees and highlights the need for new theoretical criteria to assess the performance of generative models.

Notations: Let $\mathbb{R}^{d}$ to be the $d$-dimensional Euclidean space and $T>0$ is the time horizon. Denote $x=(x_{1},x_{2},\dots,x_{d})^{\top}\in\mathbb{R}^{d}$ and $t\in[0,T]$ to be the spatial variable and time variable respectively. We denote $p_{\ast}$ as the target data distribution supported on a subset of $\mathbb{R}^{d}$, and indicate the empirical distribution by ${\mathsf{p}_{\ast}}$. The Gaussian kernel with bandwidth $\gamma$ is denoted by $\mathcal{N}_{\gamma}:=\mathcal{N}(0,\gamma^{2}I_{d\times d})$. For the special case $\gamma=1$, i.e. standard Gaussian, we use notation $\pi^{d}:=\mathcal{N}(0,I_{d\times d})$. We denote the Gaussian KDE with bandwidth $\gamma$ as $\mathsf{p}_{\ast}^{\gamma}:={\mathsf{p}_{\ast}}*\mathcal{N}_{\gamma}$. In general, we use $p_{t}$ and $q_{t}$ (or ${\mathsf{p}}_{t}$ and ${\mathsf{q}}_{t}$) to represent the laws of forward and backward SDEs at time $t$ respectively (a thorough summary of PDEs and SDEs’ notations used in this paper is provided in Appendix A). We denote $\delta\in[0,T)$ to be the early stopping time for running SDEs.

We are mainly concerned of three distinct lines of research related to SGM performance, as summarized below.

Convergence of SGMs. The first line of research concerns theoretical convergence properties of SGMs. This addresses the most fundamental performance of the algorithm: What elements are needed for SGM to perform well? In this context, a good performance amounts to generating a new sample from the learned distribution that is close to the ground-truth. This line of research has garnered a large amount of interests, drawing its relation to sampling. For most studies, the analysis becomes quantifying the deviation between distributions generated by SGMs and the ground-truth distributions. This includes the earlier studies such as (Lee et al., 2022; Wibisono & Yingxi Yang, 2022; De Bortoli et al., 2021; De Bortoli, 2022; Kwon et al., 2022; Block et al., 2022), and later (Chen et al., 2022, 2023a, 2023b; Benton et al., 2023a; Li et al., 2023) that significantly relaxed the Lipschitz condition of the score function and achieved polynomial convergence rate. In these discoveries, Girsanov’s theorem turns out to be a crucial proof strategy. Parallel to these findings, convergence properties of ODE-based SGMs have also been explored (Chen et al., 2023c, d; Benton et al., 2023b; Albergo et al., 2023; Li et al., 2023), and comparison to SDE-based SGMs have been drawn.

Sample complexity studies of SGMs. Another line of research focuses on sample complexity. How many samples/training data points are needed to learn the score? In line with convergence rate analysis, the sample complexity study has been conducted with the criteria set to be $L^{2}$-approximation of the score function (Block et al., 2022; Cui et al., 2023; Chen et al., 2023b; Oko et al., 2023). The involved techniques range from deploying Rademarcher complexity for certain hypothesis classes, to utilizing specific neural network structures. Often in times, there are also assumptions made on the structure of data.

Memorization effect of SGMs. The third line of research on SGM concerns its memorizing effect. This line of research was triggered by some experimental discovery and was confirmed by some high profile lawsuits (New York Times, 2023). Experimentally it was found that SGMs, when trained well, tend to produce replicas of training samples (Somepalli et al., 2022, 2023; Carlini et al., 2023). This phenomenon draws serious privacy concerns, and motivates studies on the fundamental nature of SGMs: Are SGMs memorizers or generalizers? In (Yoon et al., 2023), the authors presented a dichotomy, showing through numerical experiments that SGMs can generate novel samples when they fail to memorize training data. Furthermore, when confined to a basis of harmonic functions adapted to the geometry of image features, (Kadkhodaie et al., 2023) suggest that neural network denoisers in SGMs might have an inductive bias, aiming the generation. In (Gu et al., 2023; Yi et al., 2023), the authors derive the optimal solution to the empirical score-matching problem and show that the SGMs equipped with this score function exhibit a strong memorization effect. This suggests that with limited amount of training data and a large neural network capacity, SGMs tend to memorize rather than generalize.

To summarize: the convergence results of SGMs suggest a well-learned score function can be called to produce a sample drawn from a distribution close to the ground-truth, and the studies on the memorization effect of SGMs suggest the new drawings are simple replicas of the training dataset. It is worth noting that the two sets of results do not contradict. In particular, the convergence results do not rule out the explicit dependence of new generated samples on the training data. The connection between the two aspects of SGM performance is yet to be developed, and this is our main task of the current paper. We show that SGMs, despite having favorable convergence properties, can still resort to memorization, in the form of kernel density estimation. The finding underscores the need for a new theoretical framework to evaluate SGMs’ performance, taking into account both imitation ability and creativity of SGMs.

The foundation for SGM stems from two mathematical observations. Firstly, a diffusion type partial differential equation (PDE) drives an arbitrary distribution to a Gaussian distribution, forming a bridge between the complex target distribution to the standard Gaussian, an easy-to-sample distribution. Secondly, such diffusion process can be simulated by its samples, translating the complicated PDE to a set of stochastic differential equations (SDEs) that are computationally easy to manipulate.

More precisely, denote $p_{t}(x)$ the solution to the PDE:

It can be shown that, for arbitrary initial data $p_{0}$, when $T$ is big enough,

and the convergence is exponentially fast (Bakry et al., 2014). In our context, we set the initial data $p_{0}=p_{\ast}$, the to-be-learned target distribution.

This PDE can be run backward in time. Denote $q_{t}=p_{T-t}$, a quick calculation shows

This means with the full knowledge of $\nabla\ln p_{T-t}$, the flow field $x+2\nabla\ln p_{T-t}(x)=x+2u(T-t,x)$ drives the standard Gaussian ($q_{0}=p_{T}\approx\pi^{d}$) back to its original distribution, the target $q_{T}=p_{0}=p_{\ast}$. The term $u(t,x)=\nabla\ln p_{t}(x)$ is called the score function.

Simulating these two PDEs (1) and (2) directly is computationally infeasible, especially when dimension $d\gg 1$, but both equations can be represented by samples whose dynamics satisfy the corresponding SDEs. In particular, letting

the standard OU process, and

where $B_{t}$ and $B_{t}^{\prime}$ are two Brownian motions, then, with proper initial conditions:

This relation translates directly simulating two PDEs (1) and (2) to running its representative samples governed by SDEs (3)-(4), significantly reducing the computational complexity. It is worth noting that if one draws $X_{t=0}^{\leftarrow}\sim p_{T}$ and runs (4), then:

meaning the dynamics of (4) returns a sample from the target distribution $p_{\ast}$, achieving the task of sampling. Here the notation $\sim$ stands for drawing an i.i.d. sample from.

It is clear the success of SGM, being able to draw a sample from the target distribution $p_{\ast}$, lies in finding a good approximation of the score function $u(t,x)$. In the idealized setting, this score function can be explicitly expressed. In the practical computation, this function is learned from existing dataset through the score-matching procedure.

To explicitly express the score function amounts to solving (1), or equivalently (3). Taking the SDE perspective, we analyze the OU process in (3) and obtain an explicit solution:

where $y$ is the initial data and $Z\sim\pi^{d}$. Equivalently, using the PDE perspective, one sets $p_{0}=\delta_{y}$ as the initial condition to run (1) to form a set of Green’s functions:

These functions are Gaussian functions of $x$ centered at $\mu(t)y$ with isotropic variance $\sigma(t)^{2}$. This set of functions is also referred to as the transition kernel from time $0$ conditioned on $X_{0}^{\rightarrow}=y$ to time $t$ with $X_{t}^{\rightarrow}=x$.

In the idealized setting with the target distribution $p_{\ast}$ fully known, then with $p_{0}=p_{\ast}$, the solution of (1) becomes the superposition of Green’s functions weighted by $p_{\ast}$, namely:

thus by definition, the score function is explicit:

where we called (7) and used the notation $u(t,x|y)=\nabla\ln p_{t}(x|y)$ to denote the conditional flow field. This function maps $\mathbb{R}_{+}\times\mathbb{R}^{d}$ to $\mathbb{R}^{d}$. Using the explicit formula (6), we have the explicit solution for the conditional flow field:

It is a linear function on $x$ with Lipschitz constant $\frac{1}{\sigma(t)^{2}}$ that blows up at $t=0$.

Intuitively, the NN should provide a function as close as possible to the true score function, meaning it solves:

where $t\sim U[0,T]$, the uniform distribution over the time interval, and $x\sim p_{t}(x)$. $\mathcal{F}$ is a hypothesis space, and in this context, the function space representable by a class of neural networks. However, neither $p_{t}$ nor $u(t,x)$ is known in the formulation, so we turn to an equivalent problem:

where $t\sim U[0,T]$, $y\sim p_{\ast}$ and $x\sim p_{t}(x|y)$. The subindex CSM stands for conditional-score-matching. The two problems can be shown to be mathematically equivalent, see Lemma B.1. Practically, however, this new problem is much more tractable, now with both $p_{t}(x|y)$ and $u(t,x|y)$ explicit, see (6) and (8).

The target distribution $p_{\ast}$ is still unknown. At hands, we have many samples drawn from it: $\{y_{i}\}_{i=1}^{N}$. This allows us to reformulate the problem into an empirical risk minimization (ERM) problem:

with $t\sim U[0,T]$ and $x\sim p_{t}(x|y_{i})$.

In the execution of a practical DDPM algorithm, (10) is first run to find an NN serving as a good approximation to the score function, termed $s(t,x)$, and the user end then deploys this $s(t,x)$ in (4) in place of $u(t,x)$ for generating a new sample from $p_{\ast}$. Sample $\bar{X}_{0}^{\leftarrow}\sim\pi^{d}$ and run:

The law is denoted to be $\bar{\mathsf{q}}_{t}:=\text{Law}(\bar{X}_{t}^{\leftarrow})$. We note two differences comparing (4) and (11): the initial data $p_{T}$ is replaced by $\pi^{d}$ and the score function $u(t,x)$ is replaced by the empirically learned score function $s(t,x)$. If both approximations are accurate, we expect $\bar{\mathsf{q}}_{t}\approx q_{t}$ for all $t$.

When minimizing the objective (10), noting the singularity at $t=0$ of $u(t,x|y_{i})$ as in (9), it is a standard practice to conduct “early stopping” (Song et al., 2020). This is to take out a small fraction around the origin of time in the training (10) and learn the score with $t\sim U[\delta,T]$. Consequently, the sampling is also only ran up to $T-\delta$. The algorithm returns samples $\bar{X}_{T-\delta}^{\leftarrow}$ drawn from $\bar{\mathsf{q}}_{T-\delta}$. The hope is $\bar{\mathsf{q}}_{T-\delta}$ approximates the target $p_{\ast}$ using the following approximation chain:

In the idealized setting, $T\to\infty$, $s(t,x)=u(t,x)$, $\delta\to 0$, and backward SDE (11) is run perfectly, then the sample initially drawn from Gaussian $\pi^{d}$ will represents the target distribution $p_{\ast}$ at $T$. Computationally, these assumptions all break: all four factors, finite $T$, nontrivial $\delta$, imperfect $s(t,x)$ and discretization error of (11) induce error. These errors were beautifully analyzed in (Chen et al., 2022; Benton et al., 2023a). We summarize their results briefly.

All analysis require the target distribution to have bounded second moment.

The learned score function is also assumed to be close to the ground-truth in $L_{2}(dt,p_{t}dx)$:

Under these assumptions, it was concluded DDPM samples well:

The discretization error in the original result is irrelevant to the discussion here and is omitted. This upper error bound consists of two parts. The first term $\varepsilon_{\text{score}}$ comes from the score approximation error, while the second term $\sqrt{d}\exp(-T)$ comes from the finite truncation, where we forcefully replace $p_{T}$ by $\pi^{d}$.

The theorem states that, when $T$ is large enough and the score function is approximated well in $L_{2}(dt,p_{t}dx)$ sense, the TV distance between the law of generated samples $\bar{\mathsf{q}}_{T-\delta}$ and $p_{\delta}\approx p_{\ast}$ is very small, concluding that DDPM is a good sampling strategy.

It is tempting to further this statement and claim that DDPM is also a good generative model. Indeed, on the surface, it is typically claimed that generative models are equivalent to drawing samples from a target distribution $p_{\ast}$. However, we should note a stark difference between sampling and generation: A meaningful generative model should be able to produce samples that are not mere replica of known ones. The error bound in Theorem 2.3 does not exclude this possibility. As will be shown in Section 3, it is possible to design a DDPM whose score function is learned well, so according to Theorem 2.3 produces a distribution close to the target. Yet in Section 4, we demonstrate that this model fails to be produce new samples. These two sections combined suggest DDPM with a well-learned score function does not necessarily produce a meaningful generative model.