On the Generalization Properties of Diffusion Models
Authors: Puheng Li
Zhong Li
Huishuai Zhang
Jiang Bian
Venue: NeurIPS 2023 poster (2023)
Keywords: diffusion models
training dynamics
generalization gap
modes shift
TL;DR: We propose a data-independent estimate of the generalization error for score-based diffusion models, and extend it to a data-dependent "modes shift" scenario.

Abstract: Diffusion models are a class of generative models that serve to establish a stochastic transport map between an empirically observed, yet unknown, target distribution and a known prior. Despite their remarkable success in real-world applications, a theoretical understanding of their generalization capabilities remains underdeveloped. This work embarks on a comprehensive theoretical exploration of the generalization attributes of diffusion models. We establish the theoretical estimates of the generalization gap that evolves in tandem with the training dynamics of score-based diffusion models, suggesting a polynomially small generalization error ($O(n^{-2/5}+m^{-4/5})$) on both the sample size $n$ and the model capacity $m$, evading the curse of dimensionality (i.e., independent of the data dimension) when *early-stopped*. Furthermore, we extend our quantitative analysis to a *data-dependent* scenario, wherein target distributions are portrayed as a succession of densities with progressively increasing distances between modes. This precisely elucidates the *adverse* effect of "*modes shift*'' in ground truths on the model generalization. Furthermore, these estimates are not solely theoretical constructs but have also been confirmed through numerical simulations. Our findings contribute to the rigorous understanding of diffusion models' generalization properties and provide insights that may guide practical applications.

On the Generalization Properties of Diffusion Models
Pubeng Li* Department of Statistics Stanford University puhengli@stant ord edu
Zhong Li*t Machine Learning Group Microsoft Research Asia Izhong@microsste com
Huishuai Zhang?
Jiang Bian
Machine Learning Group
Machine Learning Group Microsoft Research Asia j abi wwwmfrosootttcommmmmmmmmmm com
Microsoft Research Asia
huzhang@mi www.oot.oooo.o..oo.oooo com
Abstract
Diffusion models class of generative models that serve establish a stochastic transport map between an empirically observed, yet unknown, target distribution and known prior. Despite their remarkable success in real-world applications, a theoretical understanding of their generalization capabilities remains underde- veloped. This work embarks on a comprehensive theoretical exploration of the generalization attributes of diffusion models. We establish theoretical estimates of the generalization gap that evolves in tandem with the training dynamics of score-based diffusion models, suggesting polynomially small generalization error (O(n + m -4/5)) on both the sample size n and the model capacity m, evading the curse of dimensionality (i.e., not exponentially large in the data dimension) when early-stopped. Furthermore, we extend our quantitative analysis to a data- dependent scenario, wherein target distributions are portrayed as a succession of densities with progressively increasing distances between modes. This precisely elucidates the adverse effect "modes shift" in ground truths on the model gener- alization. Moreover, these estimates are not solely theoretical constructs but have also been confirmed through numerical simulations. Our findings contribute to the rigorous understanding of diffusion models' generalization properties and provide insights that may guide practical applications.
Introduction
have experienced a surge in popularity, owing to their unparalleled performance in wide range of applications
As an emerging family of deep generative models, diffusion models (DMs; [16 45
63 53)). This has led to notable commercial successes, such as DALL-E 34) Imagen (38) and Stable Diffusion ([36)). Mathematically, diffusion models learn
([22 39
68 15
35
60
33 69
64
an unknown underlying distribution through a two-stage process: (i) first, successively and gradually injecting random noises (forward process); (ii) then reversing the forward process through denoising for sampling purposes (reverse process). To achieve this, an equivalent formulation of diffusion models called score-based generative models (SGMs; [50 52) is employed. SGMs implement
the aforementioned two-stage process via the continuous dynamics represented by a joint group of coupled stochastic differential equations (SDEs) (54] 20)).
"This work done when Puheng Li undergraduate student Peking University and research intern at MSRA. The first two authors contributed equally this work and are ordered alphabetically. *Coresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Despite their impressive empirical performance. the theoretical foundation of DMs/SGMs remains underexplored. Generally, fundamental theoretical questions can be categorized into several aspects. By considering machine learning models as mathematical function classes from certain spaces, one can identify three central aspects: approximation, optimization and generalization. At the forefront lies the generalization problem, which aims to characterize the learning error between the learned and ground truth distributions.
The development of generalization theory for diffusion models is pressing due to both theoretical and practical concern::
In theory, the generalization issues of generative modeling (or learning for distributions) may exhibit as the memorization phenomenon, if the modeled distribution is eventually trained to converge to the empirical distribution only associated with training samples. Intuitively, memorization arises from two reasons: (i) it is useful for the hypothesis space to be large enough to approximate highly complex underlying target distributions (universal convergence; [65]); (ii) the underlying distribution is unknown in practice, and one can only use a dataset with finite samples drawn from the target distribution. Rigorous mathematical characterizations of memorization are developed for bias potential models and GANs in [66] and [671, respectively. A natural question is, does a similar phenomenon occur for diffusion models? To answer this, thorough investigation of generalization properties for DMs/SGMs required.
In practice, the generalization capability of diffusion models is also an essential requirement, as the memorization can lead to potential privacy and copyright risks when models are de- ployed. Similar other generative models and large language models (LLMs) [5] 70 19 6). diffusion models can also memorize and leak training samples [5] 46], hence can be subse-
quently attacked using specific procedures and algorithms (28
18 62 Although there are
defense methods developed to meet privacy and copyright standards (11 [4] 58)), these approaches are often heuristic, without providing sufficient quantitative understandings particularly on diffusion models. Therefore, a comprehensive investigation of the general- ization foundation of diffusion models, including both theoretical and empirical aspects, is of utmost importance in improving principled tutorial guidance in practice.
The current work develops the generalization theory of diffusion models in mathematically rigorous manner. Our main results include the following:
We derive an upper bound of the generalization gap for diffusion models along the training dynamics. This result suggests, with early-stopping, the generalization error of diffusion models scales polynomially small on the sample size (O(n (2/5)) and the model capacity (D(m=4/5)) Notably, the generalization error also escapes from the curse of dimensionality,
This "uniform" bound is further extended to a data-dependent setting, where a sequence of unidimensional Gaussian mixtures distributions with increasing modes' distance is considered as the ground truth. This result characterizes the effect of "modes shift" quanti- tatively, which implies that the generalization capability of diffusion models is adversely affected by the distance between high-density regions of target distributions.
The theoretical findings are numerically verified in simulations.
The rest of this paper is organized as follows. In Section 2 we discuss the related work on the convergence and training fronts of diffusion models and also the generalization aspects of other generative modeling methods. Section 3s the central part, which includes the problem formulation, main results, and consequences. Section]Jincludes numerical verifications on synthetic and worldworld datasets All the details of proofs and experiments are found in the appendices.
2 Related Work
We review the related work on diffusion models concerning the central results in this paper.
First, on the convergence theory, 7 9 established elaborate error estimates between the modeled and target distribution given the discretization and time-dependent score matching
given
CCode is available at httpee///ggtttaa..oooppeee//e/ss http://aie....atttaoooooooooaaaa www.:essooon.eeeeeiiiiiiiioo

---

((0)
du = f(a, Ojdt + g(i)dW
x(T)
x (0)
de = [[a,)) -g² 200 log log di 9())WW
x x(T)
mvlle)
Ao(Wa (e(())
Target: Himilely-supported prob. & mixtures
Notations:
Low: Time-dependeni score matching (Eqq (7))
SDE time
T: maximal SDE time
2 known prior
Algorithm:
Gradient flow
T: training time
Figure 1: Illustration of the problem formulation and important notations.
tolerance. Compared the present work, they did not evolve the concrete training dynamics since the setting therein focuses on the properties of optimizers.
Second, the training front, [51 proposed set of techniques to enhance the training performance of score-based generative models, scaling diffusion models to images of higher resolution, but without any characterization of possible generalization improvements. Similar to 7 91. 49 also provided error estimates between the modeled and target distributions in point-wiss wise sense and again did not evolve the detailed training dynamics.
Third, the generalization and memorization side, corresponding theories developed for bias potential models and GANs in [66] and (67, respectively, where the modeled distribution learns the ground truth with early-stopping and diverges converges the empirical distribution only associated with training samples after sufficiently long training
time. The current work extends the mathematical analysis the case of diffusion models under a data-dependent setting.
As a supplement, we also discuss related literature regarding low-density learning. (50) illustrated the difficulty learning from low-density regions with toy formulations and simulations, which motivates the sampling method of annealed Langevin dynamics as the predecessor of (score-based diffusion models. [21] restudied similar problems under
the pure score matching regime (without the denoising or time-dependent dynamics) and attributed the difficulty to increasing isoperimetry of distributions with modes shift. [41] defined the Hardness score and numerically justified that decreasing manifold densities leads to the increasing Hardness score, and consequently applied the Hardness score as the regularization to the sampling process to enhance synthetic images from low-density regions. As comparison, this work establishes a mathematically rigorous estimate on the generalization gap that quantitatively depends on the range of low-density regions (between modes) target distributions for (score- based) diffusion models that requires denoising.
3
Formulation and Results
In this section, we first introduce the problem setup. Next, we state the main theoretical results, subsequent consequences, and possible connections. The numerical illustration is provided last.
3.1 Problem Formulation
Since DMs/SGMs have already grown into large family of generative models with an enormous number variants, there are various ways to define the parameterization diffusion models. Here, we adopt (one of) the most fundamental architectures proposed in [54). where the forward perturbation and reverse sampling process are both implemented by a joint group of coupled (stochastic) differential equations. See Figure for illustration of the problem formulation.

---

Forward perturbation. We start with the setting of unsupervised learning. Given an unlabeled
itd. dataset Dæ = Ji_ C Rd with the sample 2; ~ Pu(z), where pu denotes the underlying (ground truth or target) distribution, the forward diffusion process is defined
dæ = f(æ, t)dt + g(t)dW, x(0) ~ Po-
(I)
Here, the drift coefficient f(.,)) 12d + IR is a time-dependent vector-valued function, and the diffusion coefficient (()) : R20 + R is a scalar function, and W; denotes the standard Wiener process (a.k.a., Brownian motion). The SDE (T) has unique, strong solution under certain regularity conditions (i.e., globally Lipschitz coefficients in both state and time; see (31). From now on, we denote by (e(x(t) the marginal distribution of æ(t), and let (a)=(((t) (x))) be the (perturbation) transition kernel from ((s) to xtt). 0 < s < S T < oo with I as the time horizon. By appropriately selecting f and g. one can force the SDE
[ to converge to a prior distribution (typically a Gaussian). Common examples include the (lime-reccald)) frmstein-Uhlenbed (OU) process which is special case of the linear version of
dæ [(1)adl + g())d,, xx0) po-
(2)
Reverse sampling. According to 1 and [54, both the following reverse-time SDE and probability flow ODE share the same marginal distribution as the forward-time SDE [I:
dæ
f(x, (
( log dt + g(t)
(3)
dx [xx 1 (1) log dl,
where W, is standard Wiener process when time flows backwards from T to 0, and dt is an infinitesimal negative time step. With the initial condition x(T) ~ PT == where I is known prior distribution such as the Gaussian noise, one can (numerically) solve (3) or (4) to transform noises into samples from Po, which is exactly the goal of generative modeling.
Loss objectives. The only remaining task is estimate the unknown (Stein) score function Ve log (z)). This is achieved by minimizing the following weighted sum of denoising score matching ((57)) objectives:
C(0; X(-)) = (, [A(I)= Bp( (e(())p [l(+),0(2((() - V (()) log
(5)
with 0* := arg min L(0; X(-)), where ((, denotes the uniform distribution over [0. T7. and x()) [0, + R4 is weighting function, which is typically selected
X(1) x 1/v E (I V (e)
(6)
according (154) The score function $1.0 : R2d + Rd is time-dependent and can be parameter- ized as a neural network (encoded with the time information) such as the (J-ne(((7] architecture commonly applied in the field of image segmentation. Alternatively, one can also define the time- dependent score matching loss
2(0; A()) = EL- [A(1) (a [(==))(==(())) - Ve(ee log Pr ((r
which is equivalent to 55) up to constant independent of 0 by [57 49
In practice, expectations in the objective (5) can be respectively estimated with empirical means over time steps in [0. 7). data samples from Po and Prjo- which is efficient when the drift coefficient f(, t) linear. Specifically, if the forward-time SDE takes the form of (2). the transition kernel Prjo has
closed form (4
Pro( (0)) = ((())))())))(()))))))))))))))
where \aa:; p. Σ) denotes the multivariate Gaussian distribution evaluated at x with the expectation Ia and covariance Σ, and r(1) == e /(S)45 v()) = J g dç.
'The OU process is the unique time-honee home--oooonnousss Markov process which is also a Gaussian process, with the stationary distribution as the standard Gaussian distribution.

---

Training.
We aim to investigate the gradient flow training dynamics over the empirical loss
d
= (..
(0) = 0%
(9)
dr
where Ln is the Monte-Carie estimation of L defined in (5) on the training dataset with auxiliary gradient flow over the population loss
(()) = - Vo ((0())(())
= -0
(10)
dr
In both cases, the weighting function X(-) is selected in (6). Denote the score function learned at the training time 7 evaluated at the SDE time with respect to the empirical loss and population loss
as $ (,,,,(r) (ax(t) and (t,((r) (a=))), respectively. The corresponding density functions, denoted by
(r) (ar(L) and (a:())) are obtained by solving
Ve) log LogPe.6. (r) = 0r,0.(n) (r) (z)()), Ve(1) log ((() = (x(()))
(11)
and then normalizing, respectively.
Score networks. We parameterize the score function 81,0 as the following random feature model
1
(1.(())= = ( + Ue(t)) = (w x + u. e(t)),
(12)
where a is the ReLU activation function, A = (a1,-. am) E Rdxm is the trainable parameter, while W = (w....., Wnn) E Rnxd and = (u1,... Um) mmxd are randomly initialized and frozen during training, and e Rzo + Rdd is the embedding function concerning the time information. Assume that a, w, and u, are i.i.d. sampled from an underlying distribution p. Then, as m > XG, we get
(1,0(x)) - ((,((x) == w,a,w, (w x JrTTell [T(())]]]]]])))))))))
(13) with aww, u) Pa(w.a) JRd sp(a, w, u)da and po(we, u) Sg p(a, w, u)da. By the positive homogeneity property of the ReLU activation, we can assume that ||l]|| + || I w.l.o.g.
(F [a(ur, u) x + u TuuTe(( e(())]
One can view (x,(()) as continuous version of the random feature model. Correspond- ingly, the optimal solution is denoted 0" when replacing the parameterized score func- tion (1) in the loss objective (5) or (7) by (z,) Define the kernel kpp (x. x') == (w [a(w x + u (e(e))or x + e(()), and let Hepo be the induced reproducing kernel Hilbert space (RKHS; 2), we have 8,00 Hipo if the RKHS norm || (w (1r u)]l ||Ia
< xc, and the corresponding discrete version can be defined by the empirical average, i.e., ||8.,011 = =
Σ. [la(w,,,))lb
Remark 1. There are more modern and complex mathematical tools such as neural tangent kernels (NTKs) and mean fields that can be selected as the score networks. Employing these modern tools valuable at least for theoretical completeness and we leave these as the future work
The goal is to measure and bound the generalization error evolving with the gradient flow training dynamics (9) between the learned distribution and target distribution, using the common Kull- back-Leibler (KL) divergence.
Definition 1 (KL divergence). Given two distributions p and g, the KL divergence from is
defined as DKt. (pllg) = Se. p(æ) log
p(a)]
dx.
Based on the above definitions, the generalization gap along the gradient flow training dynamics formulated as DKT. (pollPo.e..r)) which is only a function of the training time r. The goal is to
estimate DKL (pollPo.e.t
Recall the dataset Da = Hin C Rd, and we take D, {t. 'For example, the extension to NTKs is possible, since the training of random feature models follows specific NTK regime (only the last layer updated) in the output space (instead of the parameter space), which can be properly analyzed in the infinite-width regime.
1 C [0, T'] for convenience.
5

---

3.2 Main Results
In this section, we state the main results of the generalization capability of the (score-based) diffusion models and how it evolves as the training proceeds. Based on the formulation in Section [31] we theoretically derive several upper bounds to estimate DKL (pullPo.
under different settings. The results cover both the positive and negative aspects: in the data-independent setting where the target distribution has finite support, the generalization gap is proved to be small; while in the data-dependent setting where the target distribution possesses shift modes, the generalization is adversely affected by the modes' distance.
3.2.1 Date-Independent Generalization Gap
In this section, we provide the characterization of the generalization capability for diffusion models given a target distribution defined on a finite domain. Generally, the KL divergence from the learned distribution (r) the training time to the target distribution po can be estimated as follows.
Theorem 1. Suppose that the target distribution po is continuously differentiable and has a compact support set, i.e., || oc is uniformly bounded, and there exists reproducing kernel Hilbert space (RKHS) H (:=Hi such that 8.,0- E H. Assume that the initial loss, trainable parameters, the embedding function e(I) and weighting function X() are all bounded. Then for any 8 >> 0, 8 & 1, with the probability of at least 1 8, have
DKL (polIPo.d.I))
1
+ +2 =00) + DRL (pTllT), T21, +0()
TI
where S hides the term d llog(d+ 1), the polynomials of log ( finite RKHS norms and universal positive constants only depending on T.
Remark Since Po is compactly supported, the target score function (a) = V log Pu P)()) is also defined on compact domain. According to [T2 [3]. So is contained in the Barron function space with a finite Barron norm, and hence in a certain RKHS with a finite RKHS norm. Therefore, reasonable to require that the global minimizer So,0- or 80.ō- is also contained in some RKHS.
Proof sketch.
Theorem
I proved via the following procedure.
1. According to Theorem 1 in 49 the KL divergence on the left-hand side can be upper bounded by the population loss of the trained model up to a small error. That is.
DKL (pollPo.e..r)) I ((O,(T))
DKL. (prl(T).
(14)
2. We use the model trained with respect to the population loss (TO) perform the decomposi- tion:
[())(T)) ( ((((T) ((((T))
x -
((((T)) Monte Carlo A I + In + Is. (15)
where omit the weighting function g²(-) for simplicity. Here, 2 is the loss objective obtained by replacing $1,0 in L (defined in 7 by š,,0, and Ig summarizes the resulting Monte Carlo error.
3. I3 can be estimated via similar argument as in 24 (Lemma 48).
4. Iz can be upper bounded via standard analysis the gradient flow dynamics over convex objectives.
5. 1 can reduced as the norm product of (r) 80,0(T) and their gap, then
(a) the former can be bounded with square-root rate growth via general norm estimate of parameters trained under the gradient flow dynamics;
(b) the latter can be estimated by the Rademacher complexity (see e.g., Chapter 26 in 43
Combining all above gives the desired result. The detailed proof is found in Appendix A.I

---

Discussion on error bounds. The three error terms are further analyzed as follows.
The first term is the main error, which implies an early-stopping generalization gap. In fact, if one selects an
time Tes as Tes = θ (nz and let m ~ n, we have
DKL (polIPo.e. 2 (1/m) + (1/m)*
(16)
The second term is m-depeedent and corresponds to the approximation error, which is (1) when m > 1. In fact, the random feature model is a universal approximator to Lipschitz continuous functions on a compact domain (Theorem in (7). See more details in Appendix A.. (the last paragraph).
The third term is exponentially small in T since x (e.g. the Gaussian density) is log-Soboley according to classical result in e.g. [55] (Theorem 3.20, Theorem 3.24 and Remark 3 3.26). Remark 3. In practice, it is common to use the test error to evaluate the generalization performance. For diffusion models, a straightforward approach is to compute the negative log- aogllikelhood (averaged in bits/dim; equivalent the KL divergence) the test dataset during training with the instantaneous formula (18) and probability flow ODE (defined in (4) where the true score function V log Pt is replaced by (1,)())(c)).
Remark 4. Previous literature has established similar bounds for bias potential models (1661) and GANs (1671). Theorem Seeemm@exxter extends the corresponding results to the setting of diffusion models. Furthermore, this upper bound finer in the sense that it incorporates the information regarding the model capacity (the hidden dimension m in this cuse), which shows that more parameters benefit the learning and generulization, as expected.
3.2.2 Data-Dependent Generalization Gap
In Section 3.2. we derive estimates on the generalization error for diffusion models along the training dynamies, where the target distribution is assumed be finitely supported. In reality, this is often not the case, where target distributions usually possess distant multi-modes, from simple Gaussian mixtures to complicated Boltzmann distributions of physical systems ([29 30 Under these settings, the above analysis in Section I.2.1 can not directly apply since the data domain unbounded. remains a problem quantitatively characterize the generalization behavior of diffusion models given these target distributions with distant multi-modes or modes shift.
To provide a fine- fine-grained demonstration of the generalization capability of diffusion models when applied to learn distributions with distant multi-modes, as an illustrating example, the Gaussian mixture with two modes is selected as the target distribution.
Theorem 2. Suppose the target distribution po is a one-dimensional 2-mode Gaussian mixture: Po(x)= = (a;; -H,1) + 92N(x; μ. 1). where u > /log(1/82), 91, 92 > with qı + 92 are all constants. Under the conditions of Theorem 7 (except the uniform boundness of inputs), we have
DKL. (pollPone..)) 2 (p))
( + [(rr + DKL. (PT](T).
mn
m²
m
where 2 1, S. hides the polynomials of log log(1/8²), finite RKHS norms and universal positive constants only depending on T.
Proof sketch. Theorem 2 is proved following similar procedure with Theorem except the input data x does not have a uniform bound here. This problem mainly affects the last step (5 (b)) in the proof sketch of Theorem I and can be handled by using the fact
|x| E [I Vlo((1/8)) 14 + [oo([1/2))]= (p)) (17) given the target Gaussian mixture distribution. The de- tailed proof is found in Appendix[A.2 [A.2]
Remark 5. Theorem 2 indicates that, even for simple Figure 2: An illustration of modes shift. target distribution (e.g. a one-dimensional 2-mode Gaussian mixture), the generalization error of diffusion models can be polynomially large regarding the modes' distance. Although Theorem 2 provides only an upper bound, the modes shift effect holds due to the model-target inconsistency (the last paragraph in Appendix A.2) and the following consistent experiments (Section 4.1.2..
7

---

Numerical Verifications
In this section, we numerically verify the previous theoretical results and insights (early-stopping generalization and modes shift effect) both synthetic datasets and real-world datasets.
4.1
Simulations Synthetic Datasets
4.1.1
Early-Stopping Generalization
First, we illustrate the early-stopping generalization gap established in Theorem | We select the one-hidden-layer neural network with Swish activations as the score network, which is trained using the SGD optimizer with a fixed learning rate 0.5. The target distribution set to be a one- dimensional 2-mode Gaussian mixture with the modes' distance equalling 6, and the number of data samples is 1000. We measure the KL divergence from the trained model to the target distribution DKL (pulIPo.0..())) along with the training epochs.
From Figure 3 one can observe that the KL divergence achieves its minimum at approximately the 800-th training epoch, and starts to increase after this turning point. The experimental results are consistent with Theorem (over multiple runs), which states that there exist carly-stopping times when diffusion models can generalize well, indicating the effectiveness of our upper bound. Further, the KL divergence begins to oscillate after the minimum point, which may suggest a phase transition in the training dynamics, and the transition point is around the (optimal) early-stopping time.
Repottin
12-
Pepettiio
30-
0:3
0.4
1000
1220
1500
1750
623dh
Figure 3: The KL divergence dynamics.
4.1.2 Modes Shift Effect
Next, we numerically test the relationship between the modes' distance and generalization (density estimation) performance. All the configurations remain the same as Section 4.1.1 except that the target Gaussian mixtures have different modes' distances.
In Figure 4 the modeled distributions exhibit the following two-stage dynamics: (i) first gradually fitting the two modes (epoch 100 1000); (ii) then diverging (epoch 1000 - 1900). This aligns with the KL divergence dynamics (Figure 3 and again verifies the corresponding theoretical results (Theorem []. However, F that when the modes distant from each other, there difficulty in the Tearning process. In Figure(5) the optimal generalization is achieved at epoch = 100, but still far from well generalizing. As the training proceeds, the learned model is almost always a single-mode distribution (epoch = 1000, 1900). This phenomenon is aligned with the results which states that when there are distant modes in the target distribution,
established in Theorem 2 the generalization performance is relatively poor.
0
Figure The training dynamics when the distance between two modes is (p 3).

---

206
3.20
40
Figure 5: The training dynamics when the distance between two modes is 30 (μ1 = 15).
4.2 Simulations on Real-World Datasets
In this subsection, we verify our results on the MNIST dataset using the standard U-net architecture as the score network, which suggests that the adverse effect of modes shift on the generalization performance of diffusion models also appears in general.
The setup is as follows. First, perform K-means clustering on (D denote the MNIST dataset) to get = - Dr. and F. as the center of Da. = 1,2,... K. Let (i", (²) == arg max;y; [ DD.- UD,.. 'D Decarest is similarly constructed by arg min indices. Then, by randomly selecting the same number data samples and using the same configuration, we train two separate diffusion models on Parthest and D Dearest. respectively, and then perform inference (sampling). The training loss curves and sampling results are shown in Figure and Figure 7 respectively. One observe significant performance gap: the diffusion model trained Dathesa appears higher learning loss and worse sampling quality compared to those of D mearess-
a 22112. and farthest
Farthest
140
Taining 055
120
80
1000
Epoch
Figure 6: The training loss dynamics.
- L27
5
0
3
8
8
2
3
8
4 b 2.6 6 4na
8
3
2
3
$
3
3
0 0,3547330
5
3
8
3
9
3
8 8 2 8
4 3/3253444
8
3
3
3
3
2
8
8
3
8
2
5 3 5
9..7 3 / 3
2
8
8
3
3
22 12972220
5
5
5
3
2
2
3
3
3
S
2
8
2
Figure Sampling of the farthest (left) and nearest (right) clusters.

---

4.3 Discussion
We compare the results developed in this work with former corresponding literature as follows:
The previous work [2] also studied the adverse effect of modes shift, which particularly reported a contrastive simulation indicating the degraded performance when modeling Gaussian mixtures with the increasing distance between modes (see Figure in [2T and compare with Figure g and Figure[). However, the results therein are established and tested under the "pure" score matching setting, without the denoising or time-dependent dynamics. As a comparison, Theorem 2 estaabishes a theoretical estimate on the generalization gap for diffusion models that requires denoising, and this upper bound directly depends on the distance between modes of target distributions, instead of a circuitous characterization in [2]) to attribute the difficulty of learning modes shift to increased isoperimetry of corresponding target distributions.
Similar adverse effect of modes shift has also been theoretically analyzed and numerically verified on recurrent neural networks (RNNs). see e.g., [23] 24]. There, the modes shift is understood as type of long-term memory. This is the phenomenon of the "curse of memory": When there is long-term memory in the target, it requires a large number of parameters for the approximation. Meanwhile, the training process will suffer from severe slowdowns. Both of these effects can be exponentially more pronounced with increasing memory or modes shift.
The very recent work 42 also considered the problem of learning Gaussian mixtures using the denoising diffusion probabilistic model (DDPM) objective, but under a teacher-student setting. That is, given the Gaussian mixtures target, [42) parametrized the score network model in the same form of the score function target, with the goal to identify true parameters. Consequently, there are all positive convergence results developed in 42 despite that the time and sample complexity increases with the distance between modes. As comparison, Theorem Sareomm@adee adopts a pre-selected score network model without incorporating any information from the ground truth, and hence establish negative results concerning the modes shift. In fact, if the goal is to identify only true positions of the target Gaussian mixture (this is exactly the setting of [42)) D the teacher-student setup seems not necessary (see Figure 5 where the true position is also learned efficiently using the one-hidden-layer Swish neural network as the score network, but the modes always weighed incorrectly). In addition, [42] did not take the whole denoising dynamics into account. That is, the gradient descent (GD) analysis therein was performed on the denoising score matching objective successively at only two time stages: a larger ( ("high noise"") and a smaller l2 ("low noise"), which is often not the case in practice.
5 Conclusion
In this paper, we provide a theoretical analysis of the fundamental generalization aspect of training diffusion models under both the data-independent and data-dependent settings, and early-stopping estimates of the generalization gap along the training dynamics are derived. Quantitatively, the data-independent results indicate polynomially small generalization error that escapes from the curse of dimensionality, while the data-dependem results suggest the adverse effect of modes shift in target distributions. Numerical simulations have illustrated and verified these theoretical analyses. This work forms a basic starting point for understanding the intricacies of modern deep generative modeling and corresponding central concerns such memorization, privacy, and copyright arising from practical applications and business products. More broadly, the approach here may have the potential to be extended to other variants in the diffusion models family, including general SDE- based design space (20)). consistency models (148), rectified flows (27 26)). Schrödinger bridges
([59 56 10
47 25 etc. These are certainly worthy of future exploration.
Acknowledgements
feedback and insightful suggestions improve this work. We would like to thank Dr. Hongkang Yang for helpful discussions, and all the reviewers' valuable
10

---

References
[1] Brian D. O. Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326, 1982.
[2] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathemati- cal Society, 68(3):337-404, 1950.
[3] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances Neural Information Processing Systems, 34:17981-18 119993, 2021.
[4] Omri Avrahami, Dani Lischinski, and Ohad Fried. Blended diffusion for text-driven editing of natural images. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 18208-18 18208-18218, 2022.
[5] Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In USENIX Security Symposium, pages 5253-5270, 2023.
[6] Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In International Conference on Learning Representations, 2023.
[7] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative mod- eling: User-friendly bounds under minimal smoothness assumptions. International Conference on Machine Learning, 202:4735-4763, 2023.
[8] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K. Duvenaud. Neural ordinary differential equations. Advances Neural Information Processing Systems, 11165571-653, 2018.
[9] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: Theory for diffusion models with minimal data assumptions. In International Conference Learning Representations, 2023.
[10] Valentin De Bortoli, James Thorton,, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695-17709, 2021.
[11] Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially private diffusion models. Transactions on Machine Learning Research, 2023.
[12] Weinan E, Chao Ma, and Lei Wu. A priori estimates of the population risk for two-layer neural networks. Communications in Mathematical Sciences, 1755):1407-1425 2019.
[13] Weinan E, Chao Ma, and Lei Wu. The Barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369-406, 2022.
[14] Sahra Ghalebikesabi, Leonard Berrada, Sven Gowal, Ira Ktena, Robert Stanforth, Jamie Hayes, Soham De, Samuel I. Smith, Olivia Wiles, and Borja Balle. Differentially private diffusion models generate useful synthetic images. In International Workshop on Trustworthy Federated Learning in Conjunction with IJCAI, 2023.
[15] Shansan Gong, Mukai Li, Jiangtao Feng, Zhiyong Wu, and Lingpeng Kong. Diffuseq: Sequence to sequence text generation with diffusion models. In International Conference on Learning Representations, 2023.
[16] Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 13:6540-6851, 2020.
[17] Daniel Hsu, Clayton H. Sanford, Rocco Servedio, and Emmanouil Vasileios Vlatakis- Gkaragkounis. On the approximation power of two-layer networks of random ReLUs. Confer- ence on Learning Theory, 134:2423-24611 2021.

---

[18] Hailong Hu and Jun Pang. Membership inference of diffusion models. arXiv preprint Stti:22301.099555 2023.
[19] Matthew Jagielski, Om Thakkar, Florian Tramer, Daphne Ippolito, Katherine Lee, Nicholas Carlini, Eric Wallace, Shuang Song, Abhradeep Guha Thakurta, Nicolas Papernot, and Chiyuan Zhang. Measuring forgetting of memorized training examples. In International Conference on Learning Representations, 2023.
[20] Tero Karras, Miik Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. Advances in Neural Information Processing Systems, 35:26565-26577, 2022.
[21] Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score match- ing: The view from isoperimetry. In International Conference on Learning Representations. 2023.
[22] Haoying Li, Yifan Yang, Meng Chang, Shiqi Chen, Huajun Feng, Zhihai Xu, Qi Li, and Yueting Chen. Srdiff: Single image super-resolution with diffusion probabilistic models. Neurocomputing, 479:47-59, 2022.
[23] Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. On the curse of memory in recurrent neural networks: Approximation and optimization analysis. In International Conference Learning Representations, 2021.
[24] Zhong Li, Jiequn Han, Weinan E, and Qianxiao Li. Approximation and optimization theory for linear continuous-time recurrent neural networks. Journal of Machine Learning Research, 23(42): 85, 2022.
[25] Guan-Horng Liu, Arash Vahdat, De-An Huang. Evangelos Theodorou, Weili Nic, and Anima Anandkumar. I²SB: tmagee Schrödinger bridge. International Conference on Machine Learning, 11:220042-220666 2023.
[26] Qiang Liu. Rectified flow: A marginal preserving approach to optimal transport. arXiv preprint 2wX.v:2209.14577 2022.
[27] Xingchao Liu, Chengyue Gong, and Qiang Liu. Flow straight and fast: Learning to generate and transfer data with rectified flow. In International Conference on Learning Representations, 2023.
[28] Tomoya Matsumoto, Takayuki Miura, and Naoto Yanai. Membership inference attacks against diffusion models. In IEEE Security and Privacy Workshops, pages 77-83, 2023.
[29] Laurence Illing Midgley, Vincent Stimper, Gregor N. C. Simm, Bernhard Schölkopf, and José Miguel Hernández-Lobato. Flow annealed importance sampling bootstrap. In International Conference on Learning Representations, 2023.
[30] Frank Noé, Simon Olsson, Jonas Köhler, and Hao Wu. Boltzmann generators: Sampling equilibrium states of many-body systems with deep learning. Science, 365(645)) 147, 2019.
[31] Bernt Øksendal. Stochastic Differential Equations. Springer, 2003.
[32] Jakiw Pidstrigach. Score-based generative models detect manifolds. Advances in Neural Information Processing Systems, 35:35852-35865, 2022.
[33] Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail Kudinov. Grad- tts: A diffusion probabilistic model for text-to-speech. International Conference Machine Learning, 139:8599-8666 8608, 2021.
[34] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hicrarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125, 2022.
[35] Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. International Conference on Machine Learning, 139:8857-8868, 2021.
12

---

[36] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 10684-10695, 2022.
[37] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Compuler-Assisted Inter- vention, pages 234-241. Springer, 2015.
[38] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo-Lppes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi. Photorealistic sik-to-imaae diffusion models with deep language understanding. Advances in Neural Information Processing Systems, 35:36479-36494, 2022.
[39] Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J. Fleet, and Mohammad Norouzi. Image super-resolution via iterative refinement. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4713-477 2023.
[40] Simo Särkkä and Arno Solin. Applied Stochastic Differential Equations, volume 10. Cambridge University Press, 2019.
[41] Vikash Sehwag, Caner Hazirbas, Albert Gordo, Firat Ozgenel, and Cristian Canton. Generating high fidelity data from low-density regions using diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1 11492-11501, 2022.
[42] Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the DDPM objective. Advances in Neural Information Processing Systems, 36, 2023.
[43] Shai Chalev-Shwartz and Shai Ben- David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[44] Yuyang Shi, Valentin De Bortoli, Andrew Campbell, and Arnaud Doucet. Diffusion Schrödinger bridge matching. Advances in Neural Information Processing Systems, 36, 2023.
[45] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, 37:2256-2265. 2015.
[46] Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Diffu- sion art or digital forgery? investigating data replication in diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2023.
[47] Vignesh Ram Somnath, Matteo Pariset, Ya-Ping Hsieh, Maria Rodriguez Martinez, Andreas Krause, and Charlotte Bunne. Aligned diffusion Schrödinger bridges. Conference on Uncer- tainty in Artificial Intelligence, 216: 1985- 2023.
[48] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. Consistency models. Interna- tional Conference on Machine Learning, 202:322 100:32211-32222 1-32252, 2023.
[49] Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training of score-based diffusion models. Advances in Neural Information Processing Systems, 34:1415- 1428, 2021.
[50] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
[51] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances in Neural Information Processing Systems, 33:12438-1222 2020.
[52] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. Conference on Uncertainty Artificial Intelligence, 115:574-584, 2020.
13

---

[53] Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medi- cal imaging with score-based generative models. In International Conference on Learning Representations, 2022.
[54] Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-basee generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
[55] Ramon Van Handel. Probability in high dimension. Lecture Notes (Princeton University), 2014.
[56] Francisco Vargas, Pierre Thodoroff, Austen Lamacraft, and Neil Lawrence. Solving Schrödinger bridges via maximum likelihood. Entropy, 23(9): 134, 2021.
[57] Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Computation,
2011.
[58] Nikhil Vyas, Sham M. Kakade, and Boaz Barak. On provable copyright protection for generative models. International Conference Machine Learning, 000:35277-352999 2023.
[59] Gefei Wang, Yuling Jiao, Qian Xu, Yang Wang, and Can Yang. Deep generative learning via Schrödinger bridge. International Conference on Machine Learning, 139:10794-10804, 2021.
[60] Jay Zhangjie Wu, Yixiao Ge, Xintao Wang, Stan Weixian Lei, Yuchao Gu, Yufei Shi, Wynne Hsu, Ying Shan, Xiaohu Qie, and Mike Zheng Shou. Tune-a-video: One-shot tuning image diffusion models for text-to-video generation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7623-7633, 2023.
[61] Lei Wu and Weijie Su. The implicit regularization of dynamical stability in stochastic gradient descent. International Conference on Machine Learning, 202:37656-37688 2023.
[62] Yixin Wu, Ning Yu, Zheng Li, Michael Backes, and Yang Zhang. Membership inference attacks against text-to-image generation models. arXiv preprint (tXXi:22100006663 2022.
[63] Tian Xie, Xiang Fu, Octavian-Eugen Ganea, Regina Barzilay, and Tommi S. Jaakkola. Crystal diffusion variational autoencoder for periodic material generation. In International Conference on Learning Representations, 2022.
[64] Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geometric diffusion model for molecular conformation generation. In International Conference on Learning Representations, 2022.
[65] Hongkang Yang. A mathematical framework for learning probability distributions. Journal of Machine Learning, 1(4):373-431, 2022.
[66] Hongkang Yang and Weinan E. Generalization and memorization: The bias potential model. Mathematical and Scientific Machine Learning, 145:1013-1043, 2022.
[67] Hongkang Yang and Weinan E. Generalization error of GAN from the diseriminator's perspec- tive. Research in the Mathematical Sciences, 91)::131,, 2022.
[68] Ruihan Yang, Prakhar Srivastava, and Stephan Mandt. Diffusion probabilistic modeling for video generation. Entropy, 25(10):1469, 2023.
[69] Jongmin Yoon, Sung Ju Hwang, and Juho Lee. Adversarial purification with score-based generative models. International Conference Machine Learning, 139: 2021.
[70] Chiyuan Zhang, Daphne Ippolito. Katherine Lee, Matthew Jagielski, Florian Tramèr, and Nicholas Carlini. Counterfactual memorization in neural language models. Advances in Neural Information Processing Systems, 36, 2023.
14

---

A Technical Results and Proofs
A.1 Data-Independent Generalization Gap
To derive the theorem for the generalization error of this score- base-based generative model, we first give the following lemmas.
Lemma (Forward perturbation estimates). Consider the forward diffusion process with the linear drift coefficient For any 5 > 0, 8 < 1, with the probability of at least 1 - 6, we have
|x(()] or (112(0)l + vlog(1/52))
(18)
where CT := max (r))))))))u(().
rE(o,T]
Proof. When the drift coefficient f(.,t) Rd + Re is linear to i... f(x,t) f(t)æ, the transition kernel Pejo has closed form
P=)o(((t)(2(0)) = (()),,)) with r(() = ed (()) v(l) = v 5o (())
(19)
gا dç. Hence, we have
x(t) (0) + ((t)u(t)z ~~,(0,
(20)
For any ~ -V(0 1), c 1. we have
P(e: |c| c) 2
1
x² 12
2t
too
t00
2
2xe xx"
12
e a02 dx
-0
-
V
V2T 02
Let 8= (223) we get
Pfcc | S Vlog(1/22) 2 1 5.
(21)
Hence, for any 5 (0, 1) with 5 < 1, with the probability of at least - 6, we have
| 2 Cr [I=(0)]l + vlog(1/82))
(22)
with Cr == max (r(f),((t)u(t)) The proof is completed. tE(o,]]
Lemma 2 (Theorem in [49). We have
DKL. (pollPo. - (()((T)) DKL (prl(x).
Lemma 3. Both of the loss objectives Ż(0; (()) and ž(0; X(-) are quadratic (and hence convex).
Proof. The convexity arises from the following points: (i) The score matching loss objectives ž(0; X()) (defined in 77) and Ž(0; X()) are L2-metrics between the score network model and target score function; (ii) The score networks are defined as random feature models (see (12) and (13) that are linear to trainable parameters. Therefore, using some trace techniques and basic variational calculations, is not hard to derive the fact that the loss objectives quadratic and hence convex with respect to trainable parameters.
(1) For E(0; (())) recall that 8t (x,((((1)) Ao((((()) Ue(t)), and let (x(()) Væ((t) log (t) hy (z, f) = (W))
+Ue()) (2. t) = (((t)s((x)) we have
Ž(0; X()) = EI.- hh (a(() (A/p://mmmA////a//a (A/Vm)/((((t)..
(z() (4) t)] constant.
15

---

Since for any h, h, B. we have
E2 (1) (a
(taca (z()), ()(())
trace (B, Ba ((())) (z()),))),
we further get
((); 1 trace AB:)
2
trace (ABc) constant,
17
Vm
where
B1 == E Be(()p (x((1, () (a((),,)), B2 = ( ( (2))), (ar(1), 4)..
Here, B, is a positive semi-definite matrix, since v B E,E ( (x)()))))) 2 0 for any v. Notice that for any A, B,
trace(A T AB) = trace trace(AAA))
= Σ (A.)) A. vec(A) ()
trace (BB) = Σ ( (B
(B )B. = vec( A) )).
where @ denotes the Kronecker product. Hence
(()) = vec( A) (B, @ ())e - Vm
vec B, (ve(AA) + constant
(23)
a quadratic function. is straightforward to show that the eigenvalues of B @ I are the same as B1 but with multiplicityy lmplying that B₁ @ I is also positive semi- denindefinite. Therefore,
v2((0;A()) V) X()) = 2(B & I)
positive semi-definite, i.e., the loss is convex with respect to trainable parameters.
(2) For (())( notice that
( 12 (u [o(w x + u e((e)t)aa)))) (w, u)] B w''-po [alw', u')o(w" x + e(t))
= ((..w)) w')~p [a" T (w, u)) x uT (())(o))(w"" a n' ((T(())a(w''uu)))
Let (w. u), o' (wo', (t), z(t) (x (1), (1)) get
((0)((-)) B (tt) (II (x 2s (x(t)) + ((s) (())))))__((()))+++((((((()))))
E (Eo. (v)oo(( (w))o(=T(()))(((( 2()))((0' =())a(()))
2s (a(t)) Eu-po (a (()))) + constant
((v))(v
Eu,u'~po aa (v) (2tt (att (t))(( 2(t))((v' ((())))((')]
2B (Bene Ex (1))8 (a(1))o(vv ((0))))(o=()))))aaa
constant.
"In fact, if A Rax" B BER have the eigenvalues {wg ) (ps ) respectively, the cigenvalues A @ B are vilty, i 1, n. I.... .,. This due following argument. By -hhevllley decomposition, there exist invertible matrices P, Q.Q such that A = PAP B QAQ where A, are
upper triangular matrices. Therefore, we have
& B (PAP-1) 1)& @ (QaQ = (P & (A & P) & Q- (P & (A & A) & Q)
That is, the matrices A @ B and A @ A are similar. Notice that A @ A is still an upper triangular matrix with diagonal elements Vi44,
n2, ... m, obatain the desired result.
16

---

Then for any Φ E (po), by symmetry we have
8L(;A()))00c Φj
lim (E + co:: (()) ((0;(()))
c-0
E, [ T (B) Ba Ba(()~
+a (v) (B) (Bo (At))(() (00)
2Em
[a (1000000000000000000000000000010
2 p (()))(()) -(:;))))) -
where
K(O, K( ((-) = (on [(t))((o
(( ( ((1)))((((((()))
k(v; X(-) :- Batt (X)))((()))))
This yields
6É(:)(0) 2 [K (( 2k(0; X(-)),
(24)
50
and
(((()(-))
[(01;A()) +
02
01
((1);A()))
50
Ø=
LP(p))
= -o [a (v) 0'; (()))aa(')) 2u [k' T (0: ((:))((()1[]]]
+ 2
K(v, v²: (())aa - k(0; X(-)), a2(v) (1(1)) (P()))
- -Ep
a (v) u' a2 (v') + 2B 1k ((;)(-))a2(0)
Eupu' (a2(v) 01 (v) K (1, 0. x(-)) 1 a1
(OOL(OOT)B<(()>>0 (1()) [X()) (12 (1)) =(1))((v' ((0)(a(((')))))))))))))))))))))) - ai (+'))]
F (A(t) F. Eewpp (a2(1) (1))o [x)))]]] S
hence the functional ~(0; X(-)) is convex with respect to 0 (given any positive weighting function X(-)). The proof is completed.
Since the weighting function is fixed in our analysis, we omit the notation X(.) without ambiguity in the following contents.
Lemma 4. For any > 0 and O, O. we have
5 1x + B0,01l2 2(()) S
80,00 1x
|10000 1
-((())))((0)
T
Proof. (1) For the loss objective E, define the Lyapunov function
=(r):== ((r)==(((((r)) -2 (0) (
2 |a - alli71000
Then, we have
d B(7) (²(0()) - 2()) d7
d 2 (0(7) + a. a, d
dt ar
dt
L2()))
$ (((0()))(((0))
ar 80 0=0(T)
17(00)
17

---

where the last inequality holds since
(((r))
d
82
8L
8())
30. 0.
dr
50
(r)
dr
12(p))
60
(-)(())
50
(-
12(p0)
By convexity, for any T2, it holds that
8L
(0(T)) + ar2 O:1
80
0 (-)(())) I:P(p))
hence o E(() S We conclude that E(T) S E(O), or equivalently
(0(())
(2)r)))2((6) - -(0))
+ 2 aa, - al alli2(mo) - 2 a. - al (002
Therefore, note that ||0.00|| 1 Epo |||||||]] (let 71 Hano ) obtain
(0(T)) - (0) x
|| aa al alli((0)) x
10,00
H
+
3 B0
which gives the desired estimate.
(2) For the loss objective Ê, the argument almost the same, except replacing the Lyapunov function by
E(r) 7
- ((())
2m | Ali² p
and (5)) by (s.). Note that vec(A)/ / and
|$0.0 1 = || /m, we obtain
-() S | - A
80.00 1 + ||80.011
MT
which completes the proof.
Lemma 5. Suppose that the loss objectives Ê, Zim), E, [() are bounded at the initialization, then for any > we have
I + V m²
|500000) 11x /|50..0.cool Il S
$0.0% Im + VT.
$0.00
Proof. It's sufficient to prove
(0,
S VT, and the rest part follows similarly.
Since
d ar. dr ar
8L
||a)1lr2(00) di ||a (arll12(00) = dr
||a, (1(p(00)
ar, 50 0=0(r)/ I2(0o)
Lz(Po)
applying Cauchy-Schwarzz Schwartz inequality yields
dr ||a |arl112(00)
d
a
8C
| (10())
50 0=
å (0))).
80 ō Ō()))
dr
LP(P))
Thus, again by inequality, for any
TO 2 0, we have
d E (0(s)) ds
|| |ar1l1?(00) - ||a I|aTo r. <
ds
S /T To
-2 (ō(T)) 2 (ō(m))
VF 2 (Ø(0))
18

---

By choosing 7o O, we have ||a, (av) 2
50,000)
H Tv
hence (0,0(T)
x
50,0(0)
7
VT, which completes the proof.
Lemma 6 (Monte Carlo estimates). Define the Monte Carlo error
Errvc = EOrMo(O, (()) := EE-u((,T) [A(t) Ex(()~pp -. (25)
1, and the trainable parameter and embedding function e(-) are both bounded. Then, given any 0, for any < 1, with the probability of at least 6, there exists O such that
Suppose that [0(0)]
log2 d,
Errnc S
(26)
where S hides universal positive constants only depending on
Proof. Fix any 0. According to Lemmal for any 5 > 0, 8 < 1, with the probability of at least
1 6, we have
(t)1 2 CT (1 Vlog(1/02) & CT.
(27)
Based on the representation Rmxd. with (w, u,) ~ Pu. 11 m, let A = (a....., am) E Rdxm with a; == a Wi ui)
13 for any W = (WI,..., Wm) T E Rmxd U = (ui,.... Um) E
for -, m,, and
m,
1 Σ (w x + ut e(l)),
(0. = Ao =
(28)
then Ew [[ = (mm aaw, w) T x + u T e(t)) = =,,0(x)). For k = 1, d,
Ze kW,, (W,U)
()) { 126)) E2/2 () {,)x
1
= =E//2
(w x + u e(t)) w, [ax(w, u)o + u uT e(())]
m
If (W. Ú) is different from (W, U') at only one component indexed by i, we have
Zi,(WWU) Ze, ū)
[().01())) 3,,0, ((6)) (000)()) 1.3 3,0x(()) (3(p))
(2. - (z)x( 13()))
I x + u e(t)) (w, x + ū, ((Te(t)) L((
(laua) oo x (TTe(t))ll==e) ( + [ a a, e(t)))))))))))
(1. + [
778
1A3 WV
(lar + +@ā,,))) (Crs
(Cr,s + Cr,e),
where (i is from the triangle inequality, (ii) is due to the fact that [a())] = |ReLU(y)] < lvl for any y E IR. the triangle and Hölder's inequality and (27). (iii) follows from the positive homogeneity property of the ReLU activation, and (iv) is due to the boundness of the trainable parameter and
19

---

embedding function e(-). By McDiarmid's inequality (see e.g., Lemma 26.4 in 43 ) for any d > 0,
with the probability of at least have
1 (Cr,5 + Cr.e) /mlog(2/6)/2
Z., U) Ew,
(29)
m
log(1/0)
(C + Cr.e)
(30)
m
Since
Ew,u
(W,(W,
=Ew.U Eurpee [1) 56,0. (,)x1
(v) Bawpe
Ewwu [(L0,((0)) {L,x(()))
Burp
E
00, - ue e(t)) e(t))
(ww lax(w, u))(w x + +uu =Te(()))))
m²
(w x + u. e(l)) Ew [an w)o( T x + +u e((())))
Burpi
E u
m
+
Exupr
Ew.u
[anko(w; u e(t)) (wm [axww, w)o T a + u (ete(t)))
m²
x [a)uo(W) x e(t)) (w, laslw, u)o(w x u [(])
772
(an(wo: u)o u e(()) ( (ax(w, ww u e(()) )²
E Exapi
E w. ui
m
(ario( x uu e(t)) Eew () w) u e(())
+
1 Derrope
Σ (a iデン
m
(01N0 + uz e()) B(w [ax(w,)jo(w u)o(w T x + u e(t))
x (uwyy,us))
B( w (anten x - Te(()) - E( u) x n [T(()) 2
Emmp
m
(w) x u e((t)) 'I]
E Pp
E (10,ne)--o
(ii)
(ax ui)l ([1) Cr,, [|[elalle(t||l=)))) )"]
E Spm-ps
E (1u, 10)
(1))
(w) [ee())l=²) '
E Eu
m
(iv)
Ex-pp
B((mau)~no
[Cr, + Cr,c)
(31)
S (Cr, + Cr.c)² m²
(32)
where (v) is due to Fubini's theorem, and (ii), (iii), (iv) is the same before. By the triangle inequality, Jensen's inequality, (29) and (31) we obtain
Egpop [1])),((x) [x,(())
Σ Egppr (s)0)(2)) [ 3,,6,
20

---

22,x (W.U)
(W, - Ew (W, + Ew w (W (W,
[ZZ,A U) Ew Lww.uZZe U)]] Ew u www (W. U1)
(Tr.8 + Cr.,)² log(1/6) (Cr,8 + Or,e)² log(1/6) d
(33)
which gives
(T) EπTMC T /-" A(t) Exrp. [1(),0(x)) 3x0(( dt
$ (Cr,6 + Cr,e) log(1/6) d.
T /'' A(t)dt
1
log (1/8%)
d.
Obviously, 1 m |||
m Σ [a 4 || l
00. The proof is completed.
Now are ready to prove the main theorem.
Proof of Theorem
1 Based on Lemma]
2 we have
DKL. po (pollPo.6..m)) s ((0,(T);
+ DKL. (prl(z).
To bound the term ((0
the following decomposition:
[T),(T)) [T)) [(((T)) +(((TT)
x [(O)(T)) - [(((T)) -((((=)) Monte Carlo & 1 + I2 Tz.
According to Lemma
we obtain
1 S 5 1 (1 [100,0.11 |B0.8- l1t)
The term 13 can be further divided into
I3 = E.-(((.)))
x(t) (e(())=
(())0(()((((())) (1,0(1) (t) [1)
S Ba-u(O,27 (x(() Em(t)
[[+,0(()(<((11) 8,00- (a)
E.~U(O.T)
[A(t) (t
|||50,0 (zxt)) 5, (xx
E..7((.T) [A(t) (.)(())pp
[[(8)))))((((t)) -1,0- (x)
=: I3,1
I3.2 I3.3:
where 0* is the Monte Carlo estimator 0* By Lemma for any 8 > 0, << 1, with the probability of at least
5, holds that
log (1/52)
Ia. (fr (T,:((('00
m d.
(34)
while Lemma 4 gives
Ia. & ((0(7)) +2()) In 2(0)) $ - 200)) + (115,,0 2
|0,000 l
21

---

and similarly,
1.3 - ((0) + 1 (1100.001 1 + || 1/24
Hence, for any 8> 0, 6 < 1, with the probability of at least 8, it holds that
log" (1/6*) d (00) + =((0)) + (1150.0. llx + 11,0,. 11 + 1100,00 lit -1000.00 174
Ia 2
m
For the term 11, we have
V [(()(T)) V(((())
(Eneno.T (a(t)= Em(t)pp (=())))))(((())))))))))))))))))) Va(t (og
}}
(EINU(OTT) [A(1) Be(urp (11()))6)(<((())) - Ve(1 log
B Bx(()r:
(x(()) - x0) log (a (1))
[( Ea) Va(1) (og [6]
X(0)]l (x(()) (x)())
B Ballwwp
A(1)
m Σ m
1
a x ueee()) 1 m
Σ
a.())(ww x+() + (TTe(())
m
Notice that
1
(a(T)) (w) x(t) + ut e(t))
m
[Tā:(T) a.(T)ll2 (w: x(1) + u e(())
m
[(ā((T) - a.(T)]1
(w T xx() + uu e(()))
m
m
m
((á((T) (,(r)
(m0) ((1) + +lu e(t)))
m 2
((ā(T)) a.(r)l1 Σ (Iw: (1)11 ul (le(t)))(t)
m2
[(a((T) 2 Σ
(Ch, + C7,c).
m
which gives
v [(0m(())) ((((T)) $
Σ [((((T) - ai(7)]1 (c + C..)
1 Σ (T, ai(T))12
(Cr,8 + Cr.e)
Here, the triangle inequality, Cauchy-Schwartz inequality, the fact that [a()) |eeL.Ug)) s lvl for any E R. Hölder's inequality, the positive homogeneity property of the ReLU activation, and
22

---

the boundness of the input data, embedding function e(t) and weighting function X(t). Thus, we get
[(),(T)) - [()(T))
1
(c7 Ct,e) Σ (la((t) (((O(T) Cree)
1
Σ
a. (T) a,(T)
m
+ - (150,00l12 (1100,0-13)) (CT, Cr,e) [( +
m
[(a(()) a. -
1 (C7,6 + cr,a)
a (T) (
]=1
where the last inequality follows from Lemma We further deduce that
m
(á,(T)) - a;(T)l1
m
(ā.(To) (T(T)))
dro
1.'" ((0(T)) V Von. (., C dru
2
/'"" 2lELuI(T (t))) [(s)0((t)(x((t) Va(t) log oww o(wTxx()) + u. e.]eett)]]
Σ
m
1=1
a(t (()rd)))))(((t))) -
an(t) (xg)) oww, æ(t) + u, e(t)]] dro
-(,
where (n) denotes the empirical distribution p.. Note that
||013 ||vec A) 1) |||| / = |l
(35)
by Lemma we get [T(T) = || (0.0 2 ||...e, 1 + VT/m. For any t E [0, T), define the function space
= (f(((((()))))))))))()(()))) fi E F2 F2,e
where
Fl.
{ (z(()) log | (T) 2 10.00l1 + VT/m
F2,1 = (o(w] x(t) u e(t)) ||||| + ||u|| S 1)
Then, according Theorem A.5 in [61], for any 5 (0, 1), with the probability at least 8 over the choice of the dataset D. = { [x; Y it holds that
Em(t)>p [(s1,0(=((x(()) Va(1) log)) ow x(() + u. e(())
- ((91,6. (xx))) V (og)) aw (1)) + ufe(())
< (o) (((,0()((2(()) Va(ty logg:
x(1) e()))
Ea()))(") (x())))))(((() Va( logp,
x(t) e(t))
E ((()))(()))) (n) [(.,0())((((1)) V Va log mw a1)) + "I e())
E -2(())p(")) (m)
(x())) Va(t) logp: oww, x(t) + + e(t))
1/g(2/8)
S Rad, +
sup
[f(x(t))
JEF,, Ce
n
+ E Be(t
[(0,000)(((1)) 8,,0,(r) (zr owo x011 + u e(1)) =: J1 + J2 + Jz.
23

---

where Rad, denotes the (empirical) Rademacher complexity of F; on Dr ((x))_ and all the inequalities hold in the element- sense.
(i) For J1, according to Lemma A.6 [61, we have
Rad (Fi) 1
sup fieFi.t: ((t)e(- Cr, (Fi,) + Radn (F2.))
[f((x(t))1+
sup (hEl
lf((((()))
Note that
loww JauT x(() + uT [T(e(t)] - w (wT=(t)) + u e())
x
||]|)||>((||| + |bllilee()))
CT + Cr.e:
(36)
which yields
m
(xx0()))2(())) =
0 (T) xxt) + e(t))
m
m
0 ( (ww x(1) e(t)))
m
(Cr,s + CT,e)
0((T))
Vm
i=1
(Cr,s + Cr,e) [10(T]]12
$ (Cr,s + Cr,a)
(110,0001æx + V VT/m),
(37)
and hence
[f(()(t))] = (z(())) - Va(1) logp)(<(())
I (Cr.8 - Cr,e) (1100.00l1x + VT/m) + C7,
[f2(x(t))] = (o (x()) + u (Te(ett))) e(t)) $ Cr Cr.e.
where CG, = max,(()((-C....C..pp) Va(tt) log Pa (x(t)) This gives
(ad & (CT,s + CT. |1 VT/m+11 1) (Radn(Fi.)) + Radn (Fee)
Let
Fí, = (x.()) [[((T]l2 x ||00.00 11 + VT/m/
according to Lemma 26.6 43
we get Rad, (Fi,)
Rad (Fi.). Since
RRad, = Ee
sup
E (1,((()))
|
80.0g
r/m f=1
Ee
sup
Ej m
Σ 0,(7)o(w, 21(1) e()))
||0())]|
80.00
m
n
< Vm
Egg
sup
0,(T) 1=1
{ xx,(t + u, e(t))
||0())]>>5
s0.00
T 1=1
|1 + |////111 (E
24

---

m
1 Soolw 2²(1) + uj e(l))
Be
sup
0:(TT]
sup
m
[10(7)122.5 80.00
T/
[wlll uu 1,
f=1
R
1 Bg
sup
(T)
sup
Goo( xx((t) + u e(t))
[10 |10(+)12,]|| 00.0000 t//m
||
$ (1) $0.00 11x VT/m²) Bg
{oo(w 2,(t) + u eeTe(tt)
sup ||l|l
+
S1
j=1
where the {& independent random variables with the distribution P(ş: 1) PP -1) = 1/2, and obviously,
sup || +luul $1 5=1
Eolw ( 22(1) JJeTe e(t)) Σ
0,
we have
(ww az((t) (ax(t) + -u e(()))
sup 1 S1
< max
sup
Σ Soo(w a0((),)())))) +u" T e((),,
sup
Eowo "0((()))) Tay(() + T e(())
||wl|+lulll $1 1=1
+|ll+ $1 ==1
Ejo(w (t,(()) e(t))
Σ
(E)) T 2z,(t) + u e(t)),
sup
sup
|| wilb
[| |all $1
and by symmetry
Eg
sup
Σ Solw> xz(() + Te(t))
|m|] ||
j=1
n Σ /=1
< Rgg
sup
Σ (oo(w (1)(1) + uT e(t))
+ Eg
sup
(- (a,(1)) u T(()))
|||] ++////1 [1/l111111 $1 /=1
will + +|u/
n Σ (oo(w ( + u e(())) 1=1
2
sup [|w]|+|||ul
2nRad, (F2.)):
ie., Rad, (Fi.) & Rad, (Fi.) $ [100,0001x + VT/m)
Rad, (F2,)). According to Lemma 26.9
(contraction lemma) and Lemma 26. 43 have
Rad,, (F2,) < (1|=(t)]l<< + (Ie(()]l=)) 2 2log(4d)
log(d+ +
S (Cr, + Cr,e) V
Combining above, we obtain
J1 = (F)) S (Cr,s + Cr.a)² (110,,ullx + VT/m+11² /loy(d+ + 1)
(ii) For Jg. by
36 and
37
we get
[f((tt)) = (x(()) - Vanc logr) o( x(t) + u e(t))
$ (CT.s + Cr.a)" (1150.00l1, 1l + VT/m) Cr, (Cr,s Cr,,),
25

---

which gives
J2 S (Cr,8 + Cr.o)² (150,00112 + vT/m m//m+1 1)) V
1og(1/0)
n
(iii) For J3, we similarly have
1.00 (z) (x)(t) & ( Cri)) (1100,0lllxx vT/m)
hence by 36) and 37 we get
J3 - EE (t)) (())~))))))) (m)
- (,,00())(((((()) ((00)::((())),...r)())()) o(w, x(t) + u e(t))
2 (Cr,5 + Cr.e)² (110,001lz + vT/m)
Combining (i), (ii) and (iii), we obtain
m
m
1// Eme(On) [A(1)() + 12 + Ja) d7o
(ā.(T) - a.(T))l
m
(Jr J2 + Jz) Ja)o
m
(J1 + J2 + Jz)272 d
72 d m
(Cr,5 Cr,e)*
(1150.0011z + - log(1/8)
m +1)
log(d + 1)
+ (1/50.00)
Ilx + m
-
n1
which gives
-((0,(7))-2(011)
(Vi(0+)+ VF (1150.0.1l + || [100)01112)
m {
E [|a,(T) (T( (7,)))
$ (Cr,8 Cr.e)
m
+ +C7,5 + C7.e)
(á,(T) a,(7)
m
1 (Vzior) +
(Cr,, + Cr,a)*
Vr (1100,00l1x + (110,0011z))
d VT m
(11000olle +l+ll++++++1)++))
(Vo)))Vooeee /log(d+ + 1)
log 1og(1/0)
||50.00 11x + +V m
n
+ - d m
(Cr,5 + Cr.e) (11s0ee lre +
2
log(d+ + 1)
1og(1/8)
+ (1150.001i)
11 + -
+
n
S (Cr,s + Cr,e) TV
(T+ 1) (1 (Loe(d + 1)
(1/)
+
|| Aolll
+
T
n
Vm
m
(2(0r)
Allll + [|A.
Vmr
+ +Tv d m
log(d +1)
log log(1/8)
|
(T+1)
+
+
(38)
72
m m
26

---

d
log(d+1 1)
1og(1/6) n
log (L/00
11
+
m
11
m
m
log(d
log(1/0)
1
(T (1+1)
+
ViIT
m
71
n
m
m
where S hides universal positive constants only depending on T. Combining all above estimates yields
DKL (polIPo...(7)
S h + 12 + 13 + DKr. (pTl(T)
3 llog" (1/8%)T d
(v
log(d + 1)
log(1/0)
(1+1)
+
(1 vF)
(loo(dd 1) / /log(100) (V
}}
[(00)
+ T
(T 11+1)
1 (1 + vT) ++++)
vmT
n
vm
+ +2(0)) + log" 2 (1/02)
1
11 + 1 ll + 1100.00 + | Ilx) + DKL (PTlIT).
d
50.0
If one only focuses on the (m, n) dependdene,, i.e. the dependence on the model capacity and sample size, this upper bound can be further simplified as
DKL. (pollpo.a.1))
(vi)
7²
+ -VVVT)
(vi10r)
72
TVT
Vmn
Vmr
Vmn
m
+
[ (0-) + +((0))
+
1
+
+ DKL (Pr((T)
2
1
72
TvT
+ (2(8')+ + +((0)) + 1
+-+ + + DKL (prllT)
((00) +
+
+
/
Vmn
m
((00)
+
4
3
= (ž(0-) + ((00))
+ _ + DKL (PTlIT)
1
1T
mn
m²
m
1
33
(z + 2(0)) + DKL (pr(IT),
+ m
+
mn
m
(vi) where we assume T > for simplicity, and X hides the term d doog(d + 1), the polynomials of log(1/8 (82) and finite RKHS norms || I| The proof is completed.
Approximation errors. For the (universal) approximation, we discuss in two points:
First, the approximation is separate problem that can be analyzed independently of training and generalization. While it beyond the scope of current work, we have included the approximation eитor in the final estimates. When the approximation by random feature models fails, the generalization error is supposed to be significant.
In addition, the random feature model can approximate Lipschitz continuous functions on compact domain (Theorem in [7]). Notice that the forward diffusion process defines a random path (ar))), Queoo contained in rectangular domain RT, := [-Cr,a, Cr,s) x
[0, T] C d++1 with Cr,5 == Cr(C2 + (log(1//5)) ()/22) (use Lemma 1 and the boundness of inputs), one can apply Theorem in [17 to bound on the domain Rr, Rd+1 obtain approximation results for Lipschitz continuous target score functions.
27

---

A.2 Data-Dependent Generalization Gap
Lemma 7 (Forward perturbation estimates, Gaussian mixtures). Suppose that sampled
one-dimensional 2-mode Gaussian mixture: Po(z) = ( -, + (2; p. 1), where > 0,
91, 92 with F1 + 92 are all constants. Then for any ó > 0, 8 < L, Vlog(1/0²), with
the probability of at least ö, we have
[x(+|| - Cr (u+ (log(1/62) & Cr.
(39)
Proof. It is straightforward to verify that
IP {< |x ul S Vlog(1/52)) U 1x: x 14 S Vlog(1/82))
| p Vlog(1/82) P2 : |x p S / log(l/////// [/)2a] + Pa
v (og(1/52)
at logooo(1/83)
po(x)do + (og(1162)
- (oE(188)
(1o((1889)
a+ Mog(1/52)
2 92
Na 1)dx 91
N(:; ,e, 1) 1)dr
(o8(11522)
(og(1/62)
1og(1/62)
Nx; 0, 1)dx
Nx;; 0, 1)dx
92
(16(1/62)
1og(1/82)
(01
92)
[e |e| S Vlog(1/82)
where the last inequality applies 21 1 - 6, we have
That is, for any > 0, < with the probability of at least
|x|| E [I
v log((1/2)),
log = O()).
(40)
Hence, Lemma gives
[x(t)] S Cr (u+ vlog(1/82))
(41)
which completes the proof.
Lemma 8 (Monte Carlo estimates, Gaussian mixtures). Define the Monte Carlo error
Errnc ErrMo(O, O, (()) Em-unoo [A(t) En(()) [[])),((x(t)) (,,(((()))
(42) Suppose that the trainable parameter and embedding function e(-) are both bounded, and is
sampled from a dieddimesionnl 2-mode Gaussian mixture: po(x) = (x>(<; -2; 1) + 92N μ., 1).
where μ >> 0, qı, Q2 > O with qı 92 1 are all constants. Then, given any 0. for any 5 > 0, 6 << 1.
/ 1og(1 1 ( with the probability of at least
there exists O such that
ERTMC S nta log(1/5)
(43)
m
where S hides universal positive constants only depending on
Proof. According to Lemma 7, we just need to follow the proof of Lemma by replacing Cr,6 by Cr, Notably, based (33) the proof of Lemma 6 can finally derive
EITMC S 2 1og(1/5)
m
which gives the desired estimates.
Proof of Theorem We decompose the loss (T), in the same way in the proof of Theorem is similarly proved by replacing Cr,5 in the proof of Theorem by Cr Note
In fact, Theorem
that Cr = Cr + vlog(1/82) S i for μ > 1, the proof is completed.
28

---

Remark 6. A standard variance is used here for convenience. In general. if o(μ) as - too (e.g. a bounded var). similar analysis and results are supposed hold. However, this different when var = (p)) as - +Xc, since the modes are not separated in this case, and we can not characterize modes shift by simply varying μ..
Remark 7. Simply scaling down inputs seems not to resolve the adverse effect of modes shift, since the ground truth y unknown. One use the imput scale approximate μ on toy datasets, but it is not that trivial in practice, particularly for real-world applications with multiple high-dimensional modes in varied scales.
The model-target inconsistency. Informally, there is inconsistency between the score network model and target score function. In fact, given the target Gaussian mixture Po(r) Nz: -,, 1) (2N((;; fs, 1). the target score function is
(2: - (M; 1) so(x)
+)) 1, 14,
which gives so(x) -I + u. 0 and so(x) - μ4 O. While the score network model is
(z.0(x) =
Σ
a,W x Σ
am e(0)
s:w,, 20
where "<=" holds since |x|| have unmatched scales in slopes and intercepts: O(1) and (μ²) for su, but both ((a)'s 's for Su,0- That is, modeling Gaussian mixtures with large modes distances random feature models is inconsistent.
(p) by 40 (μ >> 1). Both and so,9 are linear functions, but they
Remark 8. Recall that the goal of this work is to estimate DKL (pollPu.e..r)) which aims at the density estimation characterization. This is different from [32), where the equivalence of learned and target data manifolds (support sets) is studied.
B Additional Experiments
B.1 Early-Stopping Generalization
We illustrate the strly-stopping generalization gap established in Theorem Dusing the Adam optimizer. All the configurations remain the same as Section 4.1 except that the learning rate now 1.
From Figure 8 one can observe that the KL divergence achieves its minimum at the 1000th training epoch, and starts to increase after this turning point. The plot is aligned with Theorem [ which states that there exists optimal carly-stopping time when the model can generalize well, indicating effectiveness of the upper bound. Further, the KL divergence begins to oscillate after the minimum point (1000th training epoch), which may suggest phase transition in the KI. divergence dynamics, and the transition point is around the optimal early-stopping time. The finding is aligned with SGD setting.
29

---

0.6
0.5
0.4
0.2
0.1
0.0
epoch
Figure 8: The KI. divergence dynamics under the Adam optimizer.
B.2 Modes Shift Effect
We further test the relationship between the modes' distance and the generalization performance using the Adam optimizer under the same configurations.
In Figure 9 and Figure 10 it is shown that the training of modeled distributions exhibits the same two-stage dynamics as the SGD setting, indicating that the modes shift effect holds not particularly for certain optimizer.
1331
3.5
0.4
1.00
Figure 9: The Adam training dynamics when the distance between modes is 6 (μx 3).
435
5.X
113
Figure 10: The Adam training dynamics when the distance between modes is 30 (Jr 15).
B.3 Model Capacity Dependency
We also numerically study the dependency of generalization the model capacity. Following the same configurations Section 4.1.1 we conduct experiments for different hidden dimensions varying from 2 to 2!1
30

---

In Figure 11 the left plot shows the KL divergence from the trained distribution at the 1000th training epoch to the target distribution, and the right plot shows the time duration the modeled distribution to generalize. Here, the generalization criterion we select is DRL. I 10-1, and we stop training at epoch 10000. Both the two plots in Figure indicate that increasing model capacity benefits the generalization, which also verifies the corresponding theoretical results (m-ddependency in Theorem and Theorem 2
1.2
16-
0.-
0000
0.
02
2
24
20
Figure 11: Left: The KL divergence from the model trained after 1000 epochs the target distribution under different hidden dimensions. Right: The carliest training epoch when DEL S 10-1, Here, "x" means that the model does not generalize when the training stopped at the maximum training epoch 10000.
31


Reviews:
[{"review_id": "rf3QMah75u", "reviewer": "Reviewer_ab6x", "summary": "\n This paper proves generalization bounds for diffusion models. With specific stopping, they show that the generalization error goes to zero, with a specific upper bound on the rate that scales polynomially with the sample size and the model capacity. Theorem 1 is the main convergence result, while in Theorem 2 they extend their results to the data-dependent setting. The paper is concluded with some supporting experiments.\n    \n\n", "questions": "\nThis is a nice theoretical result. Here are some comments/questions.\n\n\n- Equation 3: there are two $dt$'s there, is that right, or it's a typo? Please make it clear\n\n\n- Theorem 1: do you need to know that RKHS to run the algorithm? Or do you just use it in the proofs? This is not that much clear from the context\n\n\n- it is stressed that the upper bound on the generalization is dimension-free, while there is dependence on $d$ in the bound (Equation 18)\n\n\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- well-motivated problem and novel formulation\n- nice theoretical results\n- enough citations to prior works\n", "weaknesses": "\n- while it's generally well-written, it could've been better (e.g., a figure could've been used for problem formulation to make it better readable)\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer ab6x\n\nThank you for your comprehensive review and your valuable feedback to help us improve the paper. We detail our response below, and please kindly let us know whether our response addresses your concerns.\n\n---\n\n> **Q1**: While it's generally well-written, it could've been better (e.g., a figure could've been used for problem formulation to make it better readable).\n\n**A1**: This is a useful suggestion to further improve the readability. We have followed this suggestion to plot a figure (refer to **Figure 5** in the **pdf attachment**) to illustrate our problem formulation, including the diffusion process, (score matching) loss objectives, the random feature score network model, *different* target distributions, the gradient flow training dynamics and other important notations. We will also include this figure in the final version.\n\n---\n\n> **Q2**: Equation 3: there are two $dt$'s there, is that right, or it's a typo? Please make it clear.\n\n**A2**: Yes, it is a typo. We have fixed it in the updated version.\n\n---\n\n> **Q3**: Theorem 1: do you need to know that RKHS to run the algorithm? Or do you just use it in the proofs? This is not that much clear from the context.\n\n**A3**: The RKHS norm $\\||\\cdot\\||_\\mathcal{H}$ in Theorem 1 is the shorthand of $\\||\\cdot\\||\\_{\\mathcal{H}\\_{k\\_{\\rho\\_0}}}$ , which is defined in lines 163-167. In short, $\\rho_0$ is the distribution to initialize inner parameters $(\\pmb{w},\\pmb{u})$, $k\\_{\\rho\\_0}$ is the induced kernel, and $\\mathcal{H}\\_{k\\_{\\rho\\_0}}$ is the induced RKHS. We certainly use it in the proofs, and notice that the RKHS norm is just a weighted $L^2$-norm averaged on $\\rho_0$ (see the definition in lines 166-167), and hence can be easily estimated by the Monte Carlo method (e.g. an empirical mean) when specifying $\\rho_0$. \n\n---\n\n> **Q4**: It is stressed that the upper bound on the generalization is dimension-free, while there is dependence on $d$ in the bound (Equation 18).\n\n**A4**: By saying \"dimension-independent\", we mean escaping from the curse of dimensionality (CoD), i.e., the upper bound does not exponentially depend on the data dimension. We will remove the term \"dimension-independent\" to avoid misunderstanding in the final version. \n\n---"}, {"review_id": "tGLLHRssY8", "reviewer": "Reviewer_4Zu3", "summary": "The paper aims to characterize the generalization gap of score-based diffusion models. The setting is as follows. The input is $n$ samples from some unknown distribution $p_0$, and the goal is to approximate $p_0$ by a distribution $p_{0,\\hat{\\theta}_n}$ \nwhere the parameter $\\hat{\\theta}_n$  is a minimizer of the empirical loss function obtained by running gradient descent up to some time $\\tau.$ \n\nThe loss function is the expected difference between the gradients of the log density function of distributions along the trajectories of 2 SDEs (see equation (2)), one initialized at $p_0$ and the other at $p_{0,\\hat{\\theta}_n}.$\n \nThe paper proves a bound on the KL divergence between the true distribution $p_0$ and the learned distribution $p_{0,\\hat{\\theta}_n}$ in terms of the training time $\\tau$ for gradient descent, the sample size $n$ and model parameter $m.$ The bound is obtained by using [Song, Durkan, Murray, Ermon’21]’s main result to bound the aforementioned KL divergence in terms of the empirical loss plus a negligible term, then bound the empirical loss by the population loss. The paper states a general result (theorem 1), then shows how to apply it to the specific case when the target distribution is a mixture of two 1-dimensional Gaussians with the same covariance. They quantitatively show that the error grows when the distance between the two modes of the Gaussians increases, the KL divergence between the true distribution and the learned one becomes worse, which matches the qualitative result given in [Koehler, Heckett, Risteski—ICLR’23].", "questions": "1/ In proof of lemma 3, the top line of page 15 of the supplement, does “by convexity” refer to the fact that the loss function is a convex function? If so, this assumption should be clearly stated as part of theorem 1 or theorem 3.\n2/ In the neural net setup, lines 156 and 157 of the supplement, does A essentially play the role of theta? If so, this should be clearly stated.\n3/ If lemma 3 requires the assumption that the loss function is convex, then can the authors justify that the loss function for Gaussian mixtures is convex? Else, theorem 2 cannot use lemma 3 like it currently does.", "limitations": "The paper's proof might be incorrect.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper explicitly bounds the generalization error, which is defined as the KL divergence between the true distribution and the learned one, in the model parameters and the sample size. Similar bounds are shown before by [Koehler, Heckett, Risteski—ICLR’23] but this previous work doesn’t make explicit the dependency on the sample size and the model parameters, and further requires that the learned distribution. The results appear to be interesting, if correct.", "weaknesses": "The paper might be incorrect, or at least currently doesn’t do a good job of convincing me otherwise. I believe the statement of theorem 1/theorem 3 in the appendix lacks the important assumption that the loss function is convex (see the top line of page 15 of the supplement (proof of Lemma 3) and my 1st question for details). However, the loss function of mixtures of Gaussians appears non-convex (or at least it’s unclear to me why it should be so), so lemma 3 couldn’t be used in the proof of theorem 2 as the paper currently does.\nAside from that, the paper is quite hard to understand, and the definition of many terms are not easy to find. For ease of understanding, the author should make clear the difference between $T$, the time to run the diffusion models so that $p_T$ is close to the known prior distribution $\\pi$ (e.g. Gaussian), and $\\tau,$ the time to train the neural net for gradient estimation. These definitions, along with the definition of $p_T$ and $\\pi$, should be clearly stated in the statement of theorem 1. The preconditions of the main theorem (theorem 1) should be stated upfront in the main text instead of in the appendix of the supplement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 4Zu3\n\nThank you for your detailed review and feedback to help us improve the paper. We detail our response below, and please kindly let us know whether our response addresses your concerns.\n\n---\n\n> **Weakness 1**: Convexity concern. \n\n**A1**: The convexity arises from the following two points: \n\n1. We analyze the score-matching loss Eq. (7), which is a $L^2$-metric between the score network model and target score function; \n\n2. The score network is defined as a random feature model Eq. (12) that is linear to trainable parameters. \n\nTherefore, using some trace techniques, it is not hard to derive the fact that the loss is quadratic and hence convex w.r.t. trainable parameters $\\text{vec}(\\pmb{A})$ (i.e. the vectorization of $\\pmb{A}$). \n\nConcretely,  recall $\\pmb{s}\\_{t, \\pmb{\\theta}}(\\pmb{x}(t)) = \\pmb{A} \\sigma(\\pmb{W}\\pmb{x}(t) + \\pmb{U} \\pmb{e}(t))$, and let $\\pmb{s}\\_{t}(\\pmb{x}(t)):=\\nabla\\_{\\pmb{x}(t)} \\log p\\_{t}(\\pmb{x}(t))$, $\\pmb{h}_1(\\pmb{x},t):=\\sqrt{\\lambda (t)}\\sigma(\\pmb{W}\\pmb{x} + \\pmb{U} \\pmb{e}(t))$,  $\\pmb{h}_2(\\pmb{x},t):=\\sqrt{\\lambda (t)}\\pmb{s}\\_{t}(\\pmb{x})$, we have\n$$\n\\tilde{\\mathcal{L}} (\\pmb{\\theta};\\lambda(\\cdot)) =\n    \\mathbb{E}\\_{t \\sim \\mathcal{U} (0,T)} \n    \\mathbb{E}\\_{\\pmb{x}(t) \\sim p\\_{t}} \n    [\\pmb{h}_1^{\\top}(\\pmb{x}(t),t)\\pmb{A}^{\\top} \\pmb{A} \\pmb{h}_1(\\pmb{x}(t),t) - 2\\pmb{h}_2^{\\top}(\\pmb{x}(t),t)\\pmb{A}\\pmb{h}_1(\\pmb{x}(t),t)] + \\text{constant}.\n$$\nSince for any $\\pmb{h}, \\bar{\\pmb{h}}, \\pmb{B}$, we have\n$$\n\\begin{aligned}\n\\mathbb{E}\\_{t} \n\\mathbb{E}\\_{\\pmb{x}(t)} \n    [\\pmb{h}^{\\top}(\\pmb{x}(t),t) \\pmb{B} \\bar{\\pmb{h}}(\\pmb{x}(t),t)] \n&= \\mathbb{E}\\_{t} \\mathbb{E}\\_{\\pmb{x}(t)} \n    [\\text{trace}(\\pmb{B} \\bar{\\pmb{h}}(\\pmb{x}(t),t)\\pmb{h}^{\\top}(\\pmb{x}(t),t))] \\\\\\\\\n&= \\text{trace}(\\pmb{B} \\mathbb{E}\\_{t} \n\\mathbb{E}\\_{\\pmb{x}(t)} \n    [\\bar{\\pmb{h}}(\\pmb{x}(t),t)\\pmb{h}^{\\top}(\\pmb{x}(t),t)]),\n\\end{aligned}\n$$\nwe further obtain\n$$\n\\tilde{\\mathcal{L}} (\\pmb{\\theta};\\lambda(\\cdot)) \n= \\text{trace}(\\pmb{A}^{\\top}\\pmb{A} \\pmb{B}_1) \n-2 \\text{trace}(\\pmb{A} \\pmb{B}_2)  + \\text{constant},\n$$\nwhere $\\pmb{B}_1:=\\mathbb{E}\\_{t} \n\\mathbb{E}\\_{\\pmb{x}(t)} \n    [\\pmb{h}_1(\\pmb{x}(t),t)\\pmb{h}_1^{\\top}(\\pmb{x}(t),t)]$ and $\\pmb{B}_2:=\\mathbb{E}\\_{t} \n\\mathbb{E}\\_{\\pmb{x}(t)} \n    [\\pmb{h}_1(\\pmb{x}(t),t)\\pmb{h}_2^{\\top}(\\pmb{x}(t),t)]$. Here, $\\pmb{B}_1$ is a positive semi-definite matrix, since $\\pmb{v}^{\\top}\\pmb{B}_1\\pmb{v}=\\mathbb{E}\\_{t} \n\\mathbb{E}\\_{\\pmb{x}(t)} \n    [(\\pmb{v}^{\\top}\\pmb{h}_1(\\pmb{x}(t),t))^2]\\ge 0$ for any $\\pmb{v}$. Notice that for any $\\pmb{A}, \\pmb{B}$,\n$$\n\\begin{aligned}\n\\text{trace}(\\pmb{A}^{\\top}\\pmb{A} \\pmb{B}) \n&=\\text{trace}(\\pmb{A} \\pmb{B}\\pmb{A}^{\\top})  \n=\\sum\\_{i,j}\\pmb{B}\\_{ij}(\\pmb{A}\\_{:,j})^{\\top}\\pmb{A}\\_{:,i}\n=\\text{vec}(\\pmb{A})^{\\top} (\\pmb{B} \\otimes \\pmb{I}) \\text{vec}(\\pmb{A}), \\\\\\\\\n\\text{trace}(\\pmb{A} \\pmb{B}) \n&= \\sum\\_{j} (\\pmb{A}\\_{:,j})^{\\top}(\\pmb{B}^{\\top})\\_{:,j} \n=\\text{vec}(\\pmb{A})^{\\top} \\text{vec}(\\pmb{B}^{\\top}), \n\\end{aligned} \n$$ \nwhere $\\otimes$ denotes the Kronecker product. Hence \n$$\n\\tilde{\\mathcal{L}} (\\pmb{\\theta};\\lambda(\\cdot)) \n= \\text{vec}(\\pmb{A})^{\\top} (\\pmb{B}_1 \\otimes \\pmb{I}) \\text{vec}(\\pmb{A}) - 2 \\text{vec}(\\pmb{B}_2^{\\top})^{\\top}\\text{vec}(\\pmb{A}) + \\text{constant}.\n$$\nIt is straightforward to show that the eigenvalues of $\\pmb{B}_1 \\otimes \\pmb{I}$ are the same as $\\pmb{B}_1$ but with multiplicity (see Lemma 0 below), implying that $\\pmb{B}_1 \\otimes \\pmb{I}$ is also positive semi-definite. Therefore, \n$$\n\\nabla\\_{\\pmb{\\theta}}^2 \\tilde{\\mathcal{L}} (\\pmb{\\theta};\\lambda(\\cdot)) \n= \\nabla\\_{\\text{vec}(\\pmb{A})}^2 \\tilde{\\mathcal{L}} (\\pmb{\\theta};\\lambda(\\cdot)) \n=2(\\pmb{B}_1 \\otimes \\pmb{I})\n$$\nis positive semi-definite, i.e., the loss is convex to trainable parameters. \n\n**Lemma 0**: Let $A\\in \\mathbb R^{n\\times n}$, $B\\in \\mathbb R^{m\\times m}$ have the eigenvalues $\\\\{\\nu_i\\\\}_{i=1}^n$, $\\\\{\\mu_j\\\\}\\_{j=1}^m$, respectively. Then, the eigenvalues of $A \\otimes B$ are $\\nu_i\\mu_j$, $i=1,\\cdots,n$, $j=1,\\cdots,m$. \n\n*Proof.* By Jordan–Chevalley decomposition, there exist invertible matrices $P, Q$ such that $A=P\\Lambda P^{-1}$, $B=Q\\Delta Q^{-1}$, where $\\Lambda, \\Delta$ are upper triangular matrices. Therefore, \n$$\n\\begin{aligned}\nA \\otimes B \n= (P\\Lambda P^{-1}) \\otimes (Q\\Delta Q^{-1})\n= (P \\otimes Q) (\\Lambda \\otimes \\Delta) (P^{-1} \\otimes Q^{-1})\n= (P \\otimes Q) (\\Lambda \\otimes \\Delta) (P \\otimes Q)^{-1}. \n\\end{aligned} \n$$\nThat is, $A \\otimes B$ and $\\Lambda \\otimes \\Delta$ are similar. Notice that $\\Lambda \\otimes \\Delta$ is still an upper triangular matrix with diagonal elements $\\nu_i\\mu_j$, $i=1,\\cdots,n$, $j=1,\\cdots,m$, we complete the proof. \n\n---\n\n> **Weakness 2**: Definitions of notations and theorem statement. \n\n**A2**: To clarify, we have added a figure (refer to **Figure 5** in the **pdf attachment**) to illustrate the problem formulation and important notations, as is also suggested by **Reviewer ab6x** (see **Q1** and **A1** there). We hope this plot will further improve the readability. We will also add the omitted conditions in Theorem 1 back from the appendix in the updated version. \n\n---\n\n> **Question 1**: Convexity. \n\n**A3**: As is discussed in **A1**, the loss function is a convex function w.r.t. trainable parameters ($\\text{vec}(\\pmb{A})$). We do not need an additional assumption on convexity. \n\n---\n\n> **Question 2**: Trainable parameters.\n\n**A4**: Only the outer layer is trainable in the setting of random feature models. We will clarify and emphasize this point when introducing score networks in the updated version.   \n\n---\n\n> **Question 3**: Convexity with different target distributions.\n\n**A5**: As is discussed in **A1**, the loss function is a quadratic and hence convex function w.r.t. trainable parameters ($\\text{vec}(\\pmb{A})$), and this fact holds for any given target score function, including the Gaussian mixture. \n\n---"}, {"review_id": "pkYDY5t45F", "reviewer": "Reviewer_WQ2A", "summary": "This paper provides some generalization bounds for Diffusion Models when seen as score-based models. These bounds are similar to previous literature for GANs and consider two scenarios. In the first one, the target distribution has compact support, and in the second case, it corresponds to a one-dimensional 2-mode Gaussian mixture.\n", "questions": "\"early-stopping estimates\" better generalize, do you have a practical approach to early stopping here?  ", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written and provides some generalization bounds on a general and toy problem and a numerical experiment. The sketches of the proofs are well detailed and explained.\n", "weaknesses": "Some of the motivations of the paper can seem obscure and a bit misleading. For instance, from the introduction, it feels that the authors will provide a general result for mode shift distribution while they only provide a theorem for the case of a 1-dimensional mixture of 2 Gaussian. It seems fine to study that toy problem, but it should be advertised as is. Also, the first two paragraphs on Page 2 were a bit obscure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer WQ2A\n\nThank you for your comprehensive review and your valuable feedback to help us improve the paper. We detail our response below, and please kindly let us know whether our response addresses your concerns.\n\n---\n\n> **Q1**: Some of the motivations of the paper can seem obscure and a bit misleading. For instance, from the introduction, it feels that the authors will provide a general result for mode shift distribution while they only provide a theorem for the case of a 1-dimensional mixture of 2 Gaussian. It seems fine to study that toy problem, but it should be advertised as is. Also, the first two paragraphs on Page 2 were a bit obscure.\n\n**A1**: We answer the questions on introduction as follows: \n\n- For the analysis on modes shift distributions, we indeed investigate a specific setting in theory, with additional experiments on density estimation comparison (Figure 3 and Figure 4). Notably, we provide a new simulation result on a real dataset (refer to **Point 1** in **Summary of new results (as required)** and  **Figure 1** in the **pdf attachment** for more details), which suggests that the adverse effect of modes shift on the performance of diffusion models may appear in general. But anyway, this is still not a general rigorous mathematical analysis on the practical setting, and we will follow your advice to tone down a bit in the corresponding statements. We plan to modify lines 65-67 to:  \n\"This \"uniform\" bound is further extended to a *data-dependent* setting, where a sequence of unidimensional Gaussian mixtures distributions with an increasing modes' distance $\\mu$ is considered as the ground truth. \nThis result characterizes the effect of ``modes shift'' quantitatively, which implies that...\" in the final version. \n\n- The first two paragraphs on Page 2 mainly conveys the information that generative models may possess the memorization property, which has been already proved for bias potential models and GANs in theory and shown for large language models in applications, leading to potential privacy and copyright risks. This is our motivation to investigate the generalization properties of diffusion models. To clarify, we plan to modify these two paragraphs to the following. \n    - \"In theory, the generalization issues of generative modeling (or learning for distributions) may exhibit as the *memorization* phenomenon, if the modeled distribution is eventually trained to converge to the empirical distribution only associated with training samples. Intuitively, memorization arises from two reasons: (i) it is useful for the hypothesis space to be large enough to approximate highly complex underlying target distributions (universal convergence; [59]); (ii) the underlying distribution is unknown in practice, and one can only use a dataset with finite samples drawn from the target distribution. Rigorous mathematical characterizations of memorization are developed for bias potential models and GANs in [60] and [61], respectively. A natural question is, does a similar phenomenon occur for diffusion models? To answer this, a thorough investigation of generalization properties for DMs/SGMs is required.\"\n    - \"In practice, the generalization capability of diffusion models is also an essential requirement, as the memorization can lead to potential privacy and copyright risks when models are deployed. Similar to other generative models and large language models (LLMs) ([5, 64, 17, 6]), diffusion models can also memorize and leak training samples ([5, 42]), hence can be subsequently attacked using specific procedures and algorithms ([26, 16, 56]). Although there are defense methods developed to meet privacy and copyright standards ([10, 13, 55 53]), these approaches are often heuristic, without providing sufficient quantitative understandings particularly on diffusion models. Therefore, a comprehensive investigation of the generalization foundation of diffusion models, including both theoretical and empirical aspects, is of utmost importance in improving principled tutorial guidance in practice.\"\n\n---\n\n> **Q2**: \"Early-stopping estimates\" better generalize, do you have a practical approach to early stopping here?\n\n**A2**: It is a common practice to use the test error to evaluate the generalization performance. For diffusion models, a straightforward approach is to compute the negative log-likelihood (averaged in bits/dim) on the test dataset *during training* with the instantaneous change-of-variable formula ([1]) and probability flow ODE Eq. (4), where the true score function $\\nabla\\_{\\pmb{x}} \\log p\\_{t}(\\pmb{x})$ is replaced by $\\pmb{s}\\_{t, \\pmb{\\theta}(\\tau)}(\\pmb{x})$. \n\n---\n\n**References**\n\n[1] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, David K. Duvenaud. Neural ordinary\ndifferential equations. In *Advances in Neural Information Processing Systems*, pp. 6571–6583,\n2018.\n\n---"}, {"review_id": "bf1dTeLWRI", "reviewer": "Reviewer_uaj6", "summary": "This paper studies theoretical bounds on score-matching diffusion models' generalization ability, in terms of KL divergence between the true distribution and the learned distribution generated by the model. It is assumed that the score model is parametrized as a time-dependent (time refers to $t$ in the diffusion process) 2-layer random feature model, and that the training process is the continuous-time gradient flow with respect to the score matching loss $\\tilde{\\mathcal{L}}$. The authors characterize the generalization bound as a decreasing function of $n$ (the sample size) and $m$ (the model capacity; the hidden layer size), and shows that the error decreases polynomially in $n$ with appropriately chosen early-stopping time $\\tau$, under the setup where the target distribution has compact support. They also study the effect of distance between the modes on the theoretical bound in the toy case of fitting a 2-Gaussian-mixture.", "questions": "- What is the role of the time embedding function $\\mathbf{e}$? Does it have any meaningful effect on the analysis?\n- In Lemma 3, the authors use the convexity of the diffusion loss $\\bar{\\tilde{\\mathcal{L}}}$ with respect to the trainable parameter $\\bar{\\mathbf{a}}$, and maybe this is why they consider the random feature model. But won't similar analyses be possible in more general setups using e.g., neural tangent kernels?\n- Please clarify the second point from the \"Weaknesses\" section.\n- In Theorem 2, how does variance of the Gaussian distributions comprising the mixture affect the bound? If the variance is not important, does simply scaling down all the data resolve the adverse modes shift effect claimed in Section 3.2.2?\n- In the equation right before Line 511 in the appendix, is the minus sign missing in front of $\\frac{d}{d\\tau} \\tilde{\\mathcal{L}}(\\boldsymbol{\\theta}(s))$? I think the subsequent lines using the integral Cauchy-Schwarz inequality also share the sign issue.\n- In the experiments, do the authors observe that their theory provide quantitative predictions on the optimal early-stopping time (the \"transition point\" in the training dynamics), or is it just a post-hoc observation? Were the results consistent over multiple runs? ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper successfully builds the setup where the generalization of diffusion models is theoretically analyzable in terms of sample size, model capacity and training time, using common machineries used in ML theory. \n- The analysis carefully deals with the necessary technical components for bounding the generalization error for diffusion models and the proofs seem sound (legitimate arguments assigned to each component of the analysis).\n- Overall, I think the paper provides a good starting point for the theoretical study on the generalization of diffusion models and identifies some interesting questions on diffusion model training such as dimension dependency or the choice of optimal early stopping time.", "weaknesses": "- Of course, the investigated setup is limited (dealing with 2-layer random feature models) and is far away from what is being used in practice. To some extent this is understandable, considering that the similar limitation is shared among most of the relevant works in the field. However, one can still argue that the setup is obsolete as there are now more 'modern' tools like the neural tangent kernels or mean field limits for performing theoretical analyses on neural networks.\n- I think the paper has insufficient discussion regarding the optimal solution $\\bar{\\boldsymbol{\\theta}}^\\ast$. It does not discuss, e.g., the universal approximation property of the random feature parametrization with respect to the score-matching loss $\\tilde{\\mathcal{L}}$ which is a sort of modified $L^2$ norm. So it is confusing whether the authors are assuming that the true score function is representable as a continuous random feature model not (so, if $\\bar{\\tilde{\\mathcal{L}}}(\\bar{\\boldsymbol{\\theta}}^\\ast)=0$ or not); the term $\\bar{\\tilde{\\mathcal{L}}}(\\bar{\\boldsymbol{\\theta}}^\\ast)$ is present in Theorems 1, 2 while absent in Corollaries 1, 2. It is also confusing whether $\\mathcal{H}$ in Theorem 1 coincides with the RKHS induced by $k_{\\rho_{0}}$.\n- The value of Section 3.2.2 is unclear to me. It deals only with the toy case of 1D Gaussian mixture with two modes. Additionally, it provides an upper bound that is adversely affected by $\\mu$, but there is no guarantee of tightness so it does not sufficiently \"explain\" the modes shift effect (to do so, one might rather need some sort of lower bound).\n- Experiments are minimal and loosely designed. It is performed over a single toy case (1D 2-Gaussian-mixture) and it is not reported how many repetitions were tried and whether the results were consistent. Also, it is inconsistent with the theory, which deals with the continuous-time gradient flow. Why use Adam optimizer for the experiments?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer uaj6\n\nThank you for your comprehensive review and valuable feedback to help improve the paper. We detail our response below, and please kindly let us know whether our response addresses your concerns.\n\n---\n\n**Weakness 1**:  There are two points regarding the setup concern: \n\n- First, we choose the random feature model (RFM) as the score network because it is simple to analyze, and still possesses universal approximation capability ([1]). We want to emphasize the insights gained from diffusion models rather than the neural network parametrization, which is relatively more developed in both theory and practice.\n\n- In addition, while the mathematical tools such as NTKs and mean fields may seem modern, they are more complex and require the infinite-width regime to achieve meaningful results, which is less practical in real-world applications. Nevertheless, employing these modern tools in the future work is valuable at least for theoretical completeness.  \n\n---\n\n**Weakness 2**: $\\||\\cdot\\||_\\mathcal{H}:=\\||\\cdot\\||\\_{\\mathcal{H}\\_{k\\_{\\rho\\_0}}}$ (refer to **A3** in **Response to Reviewer ab6x** for more details). For the universal approximation, we discuss in two points:\n\n- First, the approximation is a separate problem that can be analyzed independently of training and generalization. While it is beyond the scope of current work, we have included the approximation error in the final estimates. When approximation by RFMs fails, the generalization error is supposed to be significant.\n\n- In addition, the RFM can approximate Lipschitz continuous functions on a compact domain (Theorem 6 in [1]). Notice that the forward diffusion process defines a random path $(\\pmb{x}(t),t)\\_{t \\in [0,T]}$ contained in a rectangular domain $R_{T,\\delta}:=[-C\\_{T, \\delta}, C\\_{T, \\delta}]^d \\times [0,T] \\subset \\mathbb{R}^{d+1}$ with $C\\_{T, \\delta}:=C\\_T (C_{\\pmb{x}} + \\sqrt{\\log (1/\\delta^2)})$ (use Lemma 1 and the boundness of inputs), one can apply Theorem 6 in [1] to bound Eq. (7) on the domain $R_{T,\\delta}$ in $\\mathbb{R}^{d+1}$ to obtain approximation results. \n\n---\n\n**Weakness 3**: Three points:   \n\n- Informally, there may be inconsistency between the score network model and target score function. In fact, given the target Gaussian mixture $p_0(x) = q_1 \\mathcal{N}(x; -\\mu, 1) + q_2 \\mathcal{N}(x; \\mu, 1)$, the score function is\n$$s_0(x)=-x+\\frac{q_2 \\mathcal{N}(x; \\mu, 1)-q_1 \\mathcal{N}(x; -\\mu, 1)}{q_2 \\mathcal{N}(x; \\mu, 1)+q_1 \\mathcal{N}(x; -\\mu, 1)}\\mu,\n$$\nwhich gives \n$s_0(x) \\approx -x+\\mu$, $x\\ge 0$ and $s_0(x) \\approx -x-\\mu$, $x\\le 0$. While the score network is \n$$\ns_{0,\\theta}(x)\n\\approx \\left(\\frac{1}{m} \\sum\\_{i: w\\_i>0} a_i w_i\\right) x+\\left(\\frac{1}{m} \\sum\\_{i: w\\_i>0} a_i\\pmb{u}_i^{\\top} \\pmb{e}(0)\\right), \n$$\nwhere \"$\\approx$\" holds since $x=\\Theta(\\mu)$ (Eq. (38)). Both $s_0$ and $s\\_{0,\\theta}$ are linear functions, but they have unmatched scales in slopes and intercepts: $O(1)$ and $O(\\mu)$ for $s_0$, but both $O(a)$'s for $s\\_{0,\\theta}$. That is, modeling Gaussian mixtures with large modes distances as RFMs may be inconsistent (a rigorous lower bound is needed in the future). \n\n- Our experimental results (Figures 3 and 4) demonstrate a significant gap in the density estimation performance for different modes shifts. \n\n- Our new simulation on MNIST with the U-net score network (refer to **Point 1** in **Summary of new results (as required)** and **Figure 1** in the **pdf attachment** for details) suggests that modes shift may adversely affect the performance of diffusion models in general.\n\n---\n\n**Weakness 4**: The experiment is strengthened on a real dataset (see above). For consistency, we reproduce original figures trained with (S)GD for many repetitions, including Figure 2 (studying the KL divergence dynamics), and Figure 3, 4 (studying the modes shift effect). Refer to **Figure 2, 3, 4** in the **pdf attachment**. It is shown that our experimental results are consistent with the theory and replicated over multiple runs. A different optimizer (e.g. Adam) is used only for faster training.\n\n---\n\n**Question 1**: The embedding function $\\pmb{e}(t)$ is required to be bounded on a compact interval, and hence has no meaningful effect on the analysis. \n\n---\n\n**Question 2**: The extension to NTKs is possible, since the training of RFMs follows a specific NTK regime (only the last layer is updated) in the output space (instead of parameter space). We leave these as the future work. \n\n---\n\n**Question 3**: Please refer to the response to **Weakness 2**.\n\n---\n\n**Question 4**: A standard variance is used now for convenience. In general, if $\\text{var} = o(\\mu)$ as $\\mu \\to +\\infty$ (e.g. a bounded $\\text{var}$), similar analysis and results are supposed to hold. However, this is different when $\\text{var} = \\Theta(\\mu)$ as $\\mu \\to +\\infty$, since the modes are not *separated* in this case, and we can not characterize modes shift by simply varying $\\mu$. \n\nSimply scaling down inputs seems not to resolve the adverse modes shift effect, since the ground truth $\\mu$ is unknown. One may use the input scale to approximate $\\mu$ on toy datasets, but it is not that trivial in practice, particularly for real-world problems with multiple high-dimensional modes in varied scales. \n\n---\n\n**Question 5**: The typo is fixed.\n\n---\n\n**Question 6**: Currently, it is difficult to predict the optimal early-stopping time quantitatively due to upper bound estimates and unknown universal constants. However, the reproduced plot on the KL divergence dynamics shows consistency in transition points (refer to **Figure 2** in the **pdf attachment**). For other consistency concerns, refer to the response to **Weakness 4**.  \n\n---\n\n**References**\n\n[1] Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis. On the approximation power of two-layer networks of random ReLUs. *Proceedings of Thirty Fourth Conference on Learning Theory*, PMLR 134:2423-2461, 2021.\n\n---"}]

Author rebuttal:
# Summary of new results (as required)

We sincerely appreciate all reviewers for their insightful and constructive feedback. Besides answering questions in detail to address all of the reviewers’ comments, we want to summarize and highlight new key results as follows, and all of the results are included in the **pdf attachment** and will be added in the final version.  

1. We provide a new simulation result (refer to **Figure 1** in the **pdf attachment**) on the MNIST dataset with modeling the score function as the commonly-used U-net architecture, which suggests that the adverse effect of modes shift on the performance of diffusion models may appear in general. The setup procedure is as follows: (i) construct datasets from MNIST with different distances between modes; (ii) train diffusion models and evaluate respective performance on different scales of modes distances. 

    - Concretely, let $\mathcal{D}$ denote the whole MNIST dataset, we first perform a $K$-Means clustering on $\mathcal{D}$ to get $\mathcal{D}=\bigcup_{k=1}^K \mathcal{D}_k$, and $\bar{\pmb{x}}_k$ as the center of $\mathcal{D}_k$, $k=1,\cdots,K$. Let $(i^*,j^*):=\arg\max\_{i \ne j} \||\bar{\pmb{x}}_i-\bar{\pmb{x}}_j\||$, and $\mathcal{D}\_{\text{farthest}}:=\mathcal{D}\_{i^*} \cup \mathcal{D}\_{j^*}$ ($\mathcal{D}\_{\text{nearest}}$ is similarly defined by corresponding $\arg\min$ indices). By randomly selecting the same number of data samples and using the same (hyper-parameters) configuration, we train two separate diffusion models on $\mathcal{D}\_{\text{farthest}}$ and $\mathcal{D}\_{\text{nearest}}$, respectively, and then perform inference (sampling). The training loss curves are shown in **Figure 1 (a)**, and the sampling results are shown in **Figure 1 (b)** for $\mathcal{D}\_{\text{farthest}}$ and **Figure 1 (c)** for $\mathcal{D}\_{\text{nearest}}$. One can observe a clear performance gap: the diffusion model trained on  $\mathcal{D}\_{\text{farthest}}$ appears a higher learning loss and worse sampling quality compared to those of $\mathcal{D}\_{\text{nearest}}$. 

2. We reproduce original Figure 2 (studying the KL divergence dynamics) in the current paper by using (S)GD for training with many repetitions (refer to **Figure 2** in the **pdf attachment**), as is suggested by Reviewer uaj6. It is shown that the original experimental results are consistent with the theory and over multiple runs. 

3. We reproduce original Figure 3 and Figure 4 (studying the modes shift effect) in the current paper by using (S)GD for training (refer to **Figure 3** and **Figure 4** in the **pdf attachment**), as is suggested by Reviewer uaj6. It is shown that the original experimental results are consistent with the theory. 

4. We add a figure to illustrate our problem
formulation (refer to **Figure 5** in the **pdf attachment**), as is suggested by Reviewer ab6x. 

Meta-review: The paper presents some interesting novel theoretical results on the KL divergence between the true distribution and the learned distribution of scored based diffusion models, which might inspire an avenue of future work on the generalization of diffusion models. 

The author responses to the reviewers comments satisfactorily addresses key concerns. We therefore urge the authors to incorporate the additional material and clarifying points provided in their feedback. 

In particular it would be important to add a remark to prevent potential confusion on convexity, incorporate the novel experiment results and figure depicting the overall formulation, and include the discussion on the error bounds.
Decision: Accept (poster)