Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization
Authors: Yinbin Han
Meisam Razaviyayn
Renyuan Xu
Venue: ICLR 2024 poster (2024)
Keywords: diffusion models; score estimation; neural networks; neural tangent kernels
Primary area: generative models

Abstract: Diffusion models have emerged as a powerful tool rivaling GANs in generating high-quality samples with improved fidelity, flexibility, and robustness. A key component of these models is to learn the score function through score matching. Despite empirical success on various tasks,  it remains unclear whether gradient-based algorithms can learn the score function with a provable accuracy. As a first step toward answering this question, this paper establishes a mathematical framework for analyzing score estimation using neural networks trained by gradient descent. Our analysis covers both the optimization and the generalization aspects of the learning procedure. In particular, we propose a parametric form to formulate the denoising score-matching problem as a regression with noisy labels. Compared to the standard supervised learning setup, the score-matching problem introduces distinct challenges, including unbounded input, vector-valued output, and an additional time variable, preventing existing techniques from being applied directly. In this paper, we show that with proper designs, the evolution of neural networks during training can be accurately modeled by a series of kernel regression tasks. Furthermore, by applying an early-stopping rule for gradient descent and leveraging recent developments in neural tangent kernels, we establish the first generalization error (sample complexity) bounds for learning the score function with neural networks, despite the presence of noise in the observations. Our analysis is grounded in a novel parametric form of the neural network and an innovative connection between score matching and regression analysis, facilitating the application of advanced statistical and optimization techniques.

Published as a conference paper at ICLR 2024
NEURAL NETWORK-BASED SCORE ESTIMATION IN DIFFUSION MODELS: OPTIMIZATION AND GENERAL-
IZATION
Yinbin Han, Meisam Razaviyayn & Renyuan Xu Department of Industrial and Systems Engineering University of Southern Califoria (y i nbi nha, razaviya, renyuanx)@usc.een
ABSTRACT
Diffusion models have emerged as a powerful tool rivaling GANs in generating high-quality samples with improved fidelity, flexibility, and robustness. A key component of these models is to learn the score function through score matching. Despite empirical success on various tasks, remains unclear whether gradient- based algorithms can learn the score function with a provable accuracy. As a first step toward answering this question, this paper establishes mathematical framework for analyzing score estimation using neural networks trained by gra- dient descent. Our analysis covers both the optimization and the generalization aspects of the learning procedure. In particular, formulate the denoising score- matching problem as a regression with noisy labels. Compared the standard supervised learning setup. the score-matching problem introduces distinct challenges, including unbounded input, vector-valued output, and an additional time variable, preventing existing techniques from being applied directly. In this paper, we show that with proper designs, the evolution of neural networks during training can be accurately modeled by series of kernel regres- sion tasks. Furthermore, by applying an carly-stopping rule for gradient descent and leveraging recent developments in neural tangent kernels, we establish the first generalization error (sample complexity) bounds for learning the score func- tion with neural networks, despite the presence of noise the observations. Our analysis is grounded in novel parametric form of the neural network and an in- novative connection between score matching and regression analysis, facilitating the application of advanced statistical and optimization techniques.
propose parametric form
INTRODUCTION
Diffusion models excel in diverse generative tasks, spanning image, video, and audio generation (Dathathri et al., 2020; Ho et al., 2020; Song & Ermon, 2019; Song et al., 2021), often outper- forming their contemporaries, including GANs, VAEs, normalizing flows, and energy-based models (Goodfellow et al., 2014; Kingma & Welling, 2013; Rezende & Mohamed, 2015; Zhao et al., 2017).
typical diffusion model consists of two diffusion processes (Ho al., 2020; Sohl-Dickstein al., 2015; Song et al., 2021): one moving forward in time and the other moving backward. The forward process transforms given data sample into white noise in the limit by gradually injecting noise through the diffusion term, while the backward process transforms noise to sample from the data distribution by sequentially removing the added noise. The implementation of the backward process depends on the score function, defined as the gradient of the logarithmic density, at each timestamp of the forward process. In practice, however, the score function is unknown and one can only access the true data distribution via finitely many samples. To ensure the fidelity of the backward process in generating realistic samples, it is essential to develop efficient methods to estimate the score function using samples. This estimation is typically achieved through a process known score matching, employing powerful nonlinear functional approximations such as neural networks.
Despite the empirical success, it is theoretically less clear whether gradient-based algorithm can train a neural network to learn the score function. Existing theoretical work (Chen et al., 2023a;b;e; 2024; De Bortoli et al., 2021; Gao al., 2023; Lee et al., 2023; Li et al., 2023; 2024; Mei & Wu,

---

Published as a conference paper at ICLR 2024
2023: Oko et al., 2023; Shah et al., 2023; Tang & Zhao, 2024) predominantly focuses algorithm- agnostic properties of diffusion models such as score approximation, score estimation, and distri- bution recovery, leaving the theoretical performance of widely-used gradient-based algorithms an open problem. This paper bridges this gap between theory and practice. Our contributions are summarized follows.
Our Work and Contributions. This work investigates the training of a two-layer fully connected neural network via gradient descent (GD) learn the score function. First, we propose a neu- ral network-based parametric form for the score estimator based on the score decomposition (see Lemma 3. This novel design transforms the coore-mathhnng objective into a regression with noisy labels. To show the trained neural network minimizes the excess risk of this regression problem, we overcome three main challenges that do not exist in the traditional supervised learning set-ups: 1) unbounded input, 2) vector-valued output, and 3) an additional time variable. To handle unbounded input, we employ a truncation argument and control the tail behavior using the properties of diffusion processes (see Lemma 3.3). While neural networks alyzing them directly for such tasks is technically challenging. The idea is to couple neural network training with a series of regression models using neural tangent kernels (NTKs) and then leverage recent developments in NTK-based analysis. To do so, we establish universal approximation theo- rem with respect to the score function using the reproducing kernel Hilbert space (RKHS), induced by the NTK; see Theorem 3.6. Next, we leverage the recent NTK- analysis of neural networks to show the equivalence between neural network training and kernel regression (see Theorem 3.9). Consequently, we transform the score matching into kernel regression problem. Furthermore, we propose a virtual dataset to address the issue of target shifting caused by the approximation step. In the presence of multi-oufput labels, vector-valued localized Rademacher complexity bound is uti- lized to control the prediction error of two kernel regressions, the original one and the one with the shifted target (see Theorem 3.10). Finally, employ an carly-stopping rule for the kernel regres- sion to minimize the score-matching objective and provide the generalization result (see Theorem 3.12).
easy to implement and train in practice, an-
To the best of our knowledge, this is the first work to establish sample complexity bounds of GD- trained neural networks for score matching. Specifically, our paper is the first to employ NTK in establishing theoretical results for diffusion models. Although the idea of NTK has been used in many other fields, adapting existing techniques to the framework of diffusion models brings about its own significant challenges. Our analysis is grounded in a novel parametric form of the neural network and an innovative connection between score matching and regression analysis, facilitat- ing the application of advanced statistical and optimization techniques. In addition, the building blocks of our results can be applied to other supervised learning problems in non-standard forms such as conditional generative adversarial networks (Liao et al., 2020), conditional flow matching modeling (Gu et al., 2022; Smith et al., 2023) (with
(Lipman et al., 2022) and sequence-to-sequeen unbounded input and vector-valued output), which goes beyond score-matching problems.
Related Literature. Our work is related to three categorics of prior work:
First, our framework is closely related to the recent study of diffusion models. A line of work this topic provides theoretical guarantees of diffusion models for recovering data distribution, assuming access to accurate score estimator under T,2 or 0 norm (Chen et al., 2023a;c; 2024; De Bortoli et al., 2021; Gao et al., 2023; Lee et al., 2023; Li et al., 2023; Shah et al., 2023; Tang & Zhao, 2024). These results offer only a partial understanding of diffusion models as the score estimation part is omitted. To our best knowledge, Chen et al. (2023b) and Oko et al. (2023) are the only results that provide score estimation guarantees under L norm, assuming linear data structure compactly supported data density. However, their emphasis is on algorithm-agnostic analysis without evalu- ation of any specific algorithms, creating a gap between theory and practical implementation. In contrast, our work offers the first generalization error (sample complexity) bounds for GD-ttriindd neural networks.
Second, our techniques relate to the rich literature of deep learning theory. Inspired by the frame- work of NTK introduced by Jacot et al. (2018), recently Allen-Zhu et al. (2019b); Du et al. (2019; 201 1); Zou et al. (2020) establish linear convergence rate of neural networks for fitting random la- bels. One key property of GD-trained neural networks is the so-called implicit regularization of parameters. Namely, the minimizer of overparameterized neural networks is close to the random initialization. Combined with uniform convergence results in statistical learning, this implicit regu- larization leads to the generalization property of neural networks in the absence of label noise (Arora
2

---

Published as a conference paper at ICLR 2024
et al., 2019a). However, none of these works delves into the generalization ability of neural networks when confronted with noisy labels. Kuzborskij & Szepesvári (2022) is the only work that attempts to study the GD-trained neural networks with additive noise. To tackle the challenge posed by the score matching, our approach and, consequently, our theoretical results differ from the existing lit- erature on deep learning theory for supervised learning in three key aspects: 1) handling unbounded input, 2) dealing with vector-valued output, and 3) incorporating an additional time variable.
Lastly, our work is connected to a body of research focused on early-stopping rules in kernel regres- sion. See Celisse & Wahl (2021) for a comprehensive overview of this topic. Our work considers a oulti extension of the early-stopping rule developed in Raskutti al. (2014), which controls the complexity of the predictor class based on empirical distribution.
2 PRELIMINARIES AND PROBLEM STATEMENT
In this section, we introduce the mathematical framework of diffusion models (Song et al., 2021).
Forward Process. The forward process progressively injects noise into the original data distribu- tion. In the context of data generation, we have the flexibility work with any forward diffusson process of our choice. Common instances include variance-exploding and variance- variance-preservingg SDEs (Song al., 2021). For the sake of theoretical convenience, we adhere the standard convention in the literature (Ho et al., 2020; Song & Ermon, 2020) and focus on the process. In particular, we study a simple OU process with a deterministic weight function g(t) 0:
(OU)
dx, 2 (t) + Vo(t)dB, XD Po:
(1)
where (Be);20 is standard d-dimensional Brownian motion and po represents the unknown data distribution from which we have access to only limited number of samples. Our objective is to generate additional realistic samples from this distribution. The explicit solution to (I) is given by
X₁ = e fo fo(o)ds Xo + e So to(*)ds J- efa ta(u)du Vg(s)dB..
Consequently, the conditional distribution X1\Xo follows a multi-variate Gaussian distribution ((a(())xo T(()Ta) with a<I) exp (- 20(s)ds) and h(()= = 1 a2)).. Furthermore, under
mild assumptions, the OU process converges exponentially to the standard Gaussian distribution (Bakry al., 2014). In practice, the forward process (1) will terminate sufficiently large times- tamp T > 0 such that the distribution of X is close to the standard Gaussian distribution.
By reversing the forward process in time, we obtain a process X, := -Xr-t (well-defined under mild assumptions (Haussmann & Pardoux, 1986)) that transforms white noise into samples from the target data distribution, fulfilling the purpose of generative modeling. To start, let us first define backward process (time-reversed SDE) associated with (I):
Backward Process.
dy: ( +)Y, g(T V)V log) dt ttdB, YO~ 90
(2)
where (Bi) another d-dimensional Brownian motion, Ps the density of the forward process Xe. the score function V Pe()) is defined as the gradient of log density of Xt, and go is the initial distribution of the backward process. If the score function is known at each time and if we set Qu := Pr, under mild assumptions, the backward process (Yi)osesT has the same distribution as the time-reversed process (X (Xr=s)ss see Cattiaux et al. (2023); Föllmer (2005); Haussmann & Pardoux (1986) for details.
In practice, however, (2) cannot be directly used to generate samples from the target data distribution as both the score function and the distribution pr are unknown. To address this issue, it is common practice to replace pr by the standard Gaussian distribution as the initial distribution of the backward process. Then, we replace the ground-truth score V log (z(z) by estimator sp t). The estimator 89 is parameterized (and learned) by a neural network. With these modifications, we obtain an approximation of the backward process, which is practically implementable:
dy, (5 t)Y; + g(T (Yso())) dt + Vg(TT-tjdB, Yo ~ (0,
(3)
To generate data using (3), SDE solvers or discrete-time approximation schemes can be used (Chen al., 2023b;e; 2024; Ho al., 2020; Song et al., 2021).
3

---

Published as a conference paper at ICLR 2024
Score Matching. To implement the backward process, need samples to estimate the score function, A natural choice is to minimize the L loss between the estimated and actual scores:
["
A(1) [150 (x), - (logg((X.)))) dt,
min To To
(4)
where (() is the weight function that captures time inhomogeneity and ag is the estimator of the score function. Here, To O is some small value to prevent the score function from blowing up and to stabilize the training procedure (Chen et al., 2023b; Song & Ermon, 2019; Vahdat et al., 2021). major drawback of the score-matching loss (4) is its intractability as log Ps cannot be computed based on the available data samples. Thus, instead of minimizing the loss in (4), one can equivalently minimize the following denoising score matching as shown by Vincent (201 I):
[ T To To
1
min
X(t) (X,, - Pojo
dt.
(5)
Here, Pajo (X)o(X((Xx) denotes the conditional probability of X, given Xo. It is easy to show that the choice of our forward process in (1) implies
a(t) Xo
X, h(t)
V log Po Pr (x,1X))
(6)
h(t)
Now, we can plug (6) into (5) and learn the score function estimator. In practice, however, the score function estimator is parameterized by neural network. Next, we discuss such a parameterization.
Algorithm Sample Collection Procedure
1: Input: number of samples N and a small value To > 0
2: for j = .......... do
3: Sample Xo.j ~ Po
4: Sample fj ~ Uni 7]
5: Sample Xt, Peyjol (Xo,))
6: end for
7: return {( Xasr Xt,)
Neural Network-Based Parameterization. To parametrize the function 8o, we consider a two- layer ReLU neural network fw.a- (f of the following form:
==1
(w,
1 vm
Σ
m
(w (x, To)).
Here, (xr, (xx ...., 24 1) Rd+1 is the input vector, w. Bd+1 is weight vector in the first layer, a, E IR is a weight vector in the second layer, and (--) is the ReLU activation. The design term To introduced in the architecture plays an important role the theoretical analysis and also offers valuable insights in practice. For ease of exposition,
denote W (wi,..., wm)) E (d+1)xmm and a = [a:] E Rmdd We adopt the usual trick in the overparameterizztion literature (Allen-Zhu al., 2019b; Cai al., 2019; Wang al., 2020) with the parameter a fixed throughout training and only updating W. This seemingly shallow architecture poses significant challenges when analyzing the convergence of gradient- based algorithms due to its non-convex and non-smooth objective. On the other hand, its ability to effectively approximate a diverse set of functions makes it promising starting point for advancing theoretical developments.
To train the neural network, we need to have samples measuring the "goodness-of-fff of the neural network. We use Algorithm to generate N i.i.d. data samples. particular, for each 1,...., N, we first sample Xo,j from Po and a timestamp t, uniformly over the interval [To, 7). Given Xo.; and tj. we then sample Xz, from the Gaussian distribution Pt, (Xo.s). Given the output dataset
= [t), Xo.s, x1,))² / we train the neural network by minimizing a quadratic loss:
1 Σ min Z(W) = =
[N, -Xo
(8)
4

---

Published as a conference paper at ICLR 2024
Particularly, perform the gradient descent (GD) update rule:
(T(w,((T)
(T + 1) - -w,(T)= - -11 0mi (T)
To)l (u, (Xez:4) To) 2 0}
(9)
for I,.... m. Here, 17 >>>>>>>>000 is the learning rate and I denotes the indicator function. We initialize the parameter W and a according to the following neural tangent kernel (NTK) regime (Jacot et al., 2018):
(0) ~ (O( a,+ ~ Unif (-1,+1}, Vr E [m] and i E [d].
One can show that the training loss (8) is an empirical version of the denoising catch-ng loss defined in (5) under carefully chosen
Correspondingly, the finite sample performance of sø w.r.t. (4) referred to as generalization ability. We would like to remark that the two-layer neural network parameterization has not been explored in the literature for approximating score functions. While the work Chen et al. (2023b) considered multi-layer neural networks for score approximation, generalization, and distribution recovery; our work is complementary them as they did not analyze the optimization procedure and no specific learning algorithm is considered in their work.
Neural Tangent Kernels. For two-layer ReLU neural network of the form (7), we follow (Jacot et al., 2018 8) to introduce an associated NTK K Rd+1 x Rd+1 + Rdxd whose (i, k--th entry is defined as
1
Kilk (i, = lim
2
at (w, w. (0) 2 1 2
m-000 m
= aaja (0) ( 2 22)
where 2 (z. t- To) and 2= (a.8- To). Here, the expectation is taken over all the randomness of at. at and w1 (0). Similarly, we define scller-valued NTK Rd+1 Rd+ + R associated with each coordinate of the neural network:
x0 (z,, t), (Z. f) = 2 E [I (wI( 2 0) (0) T22 02
(2,
From the definition of the matrix-valuee NTK, is easy to see that is a diagonal matrix and in particular, K ((x, t), (z, ()) <((z, t), (z, La, where La is the d-dimensional identity matrix. Moreover, we let H be the reproducing Hilbert space (RKHS) induced by the matrix-valued NTK K and 74 be the RKHS induced by the scalar-valued NTK (Carmeli et al., 2010; Jacot et al., 2018). To), the Gram matrix H the kernel K is
Finally, given a dataset S and defining 2j = (X,, t2 defined as dN x dN block matrix with HIN
H11
: HNI
H = 22] 2e Iaja'I {2] wi(0) 2 O. 2 w1 (0) 2 0}] (10)
HNN
3 MAIN RESULTS
This section introduces main theoretical results. We first propose a parametric form of sø to simplify the score-matching loss in (4). Next, we show that the empirical version of DSM (5) is indeed equivalent upper bound on the loss function into four terms: a coupling term, a label mismatch term, a term related to early stopping, and an approximation error term. These terms are carefully analyzed later.
the quadratic loss defined in (8). Finally,
provide decomposition of an
To motivate our parametric form of sg, we start by the following decomposition of the score function: Lemma 3.1. The score function V logg (x) admits the following decomposition:
ott) E [Xo]X.
V (z)
x]]
(11)
h(t))
htt)
The proof, which follows the Gaussianity the transition kernel Pro. is deferred to the appendix. A similar decomposition has been proved in (Chen et al., 2023b, Lemma for data with linear struc-
ture, and in Li et al. (2023) for discrete time analysis and the concurrent work (Mei & Wu, 2023). Compared to the expression of V log (2 (2o) computed in (6), we replace Xo by E [X X.] to obtain the ground-trute score function in (11). Consequently, we call Xo the noisy label and [Xo] Xx) the true label. We also make the following assumption the diffusion models (1).
5

---

Published as a conference paper at ICLR 2024
Assumption 3.2. The target density function Po has a compact support with ||ool22 D almost surely, for some constant D >
Assumption 3.2 satisfied most practical settings, including the generation of images, videos, and audio. This assumption simplifies the subsequent analysis and can be relaxed to the sub- Gaussian tail assumption. Next, we propose the parametric form of so and A(t) in the score-matching loss (4):
a(t)
h(t)2
sw (2, t)
HI IID (a, h(t)
with X(t) a(t)?
h(t)
where HD the projection operator onto the L ball with radius centered at zero. With the choice of sw,a and A(t) specified above, the score-matching loss (4) becomes
min W
E [IIT((fW..(X...
fo (x(x,, dr,
(12)
T-
in which we define the target function as f+(x,t) == E[xo|XX,= and the expectation is taken over X₁. Given that only W is updated during optimization, in what follows, we omit in the subscript of the neural network. Our loss function (12) is also supported by empirical studies (Ho et al., 2020). In addition, (12) be viewed regression task with noisy labels. In what follows, we will show that neural networks trained on noisy labels generalize well w.r.t. (12).
One major challenge in the theoretical analysis, which distinguishes from the standard supervised learning problems, is the unboundedness of the input X, in the objective function. To overcome this challenge, employ a truncation argument with threshold R:
1
[[]] - (X,, 0)
To
To
1 To
[IIT - fx 01 (11x s R}] dt
(13)
To
/ T To To
E [IIT (x., 1 (1 R}] dt.
(14)
The next lemma controls the tail behavior in (14).
Lemma 3.3. Suppose Assumption 3.2 holds. Then, uniformly over all W, it holds that
1 T To Jo
/"
E (xxpl//(X.)))11xxx.)))))
m1]a di= -R//44))
Lemma 3.3 states the term (14) is exponentially small in the threshold R. Thus, it suffices to focus on the loss (13) over the ball with radius R. Inspired by Kuzborskij & Szepesvári (2022) for learning Lipschitz functions, we upper bound (13) by the following decomposition at each iteration T:
I
IT (fw +)) f- (X,, 1)1 (11xel22 s R} dt
4(T
To)
Ta
1
<
R
TTD (X,,))Xe
(X,,t) 1 (X,, 1) TI {1Ix,ll, s
R] dt
(coupling)
T
To
To
1
K (Xe,t) - - (x,, 1) ||: [11xxll1a s {R} de
+
E
(label mismatch)
T -
To
To
T
FK (Xert) - fxx(Xe t) [ s R}
E
(carly stopping)
T
To
JT
E [I[H((X,,,) - f-(,,, 1112 X1 & R3] dt.
(approximation)
T To
JT.
The first term the coupling error between neural networks /w(r) and function J.K defined as:
(x
(x. t) = K((X,,)))) (2, 7(T + 1) = x(7) (HH(()) -y),

---

Published as a conference paper at ICLR 2024
where 7(0) is initialized in (69) and (X.,. "., The fourth term is the approximation error of the target function f. by a function fH in the RKHS H. These two terms transform the training of neural networks into problem of kernel regression. To learn the function SN. we define an auxiliary function f.K. of the same functional form f.K. but trained different dataset S [(,,,, Xu,y X1, )35m with
Xo, tz) tEy, Ey= Xo. - fo fX(,,
Finally, we control the third term in the above decomposition by the early-stopping rule, which is introduced in the statistical learning literature (Raskutti et al., 2014; Wei et al., 2017).
3.1 APPROXIMATION
We start by analyzing the approximation term in our decomposition. This subsection focuses on the approximation error of the target function f. by function in the RKHS H induced by the NTK K. We start with a regularity assumption on the coefficient g(t) in the OU process.
Assumption 3.4. The function g is almost everywhere continuous and bounded on [0, oc).
Assumption 3.4 imposes minimal requirement to guarantee that both at)) and h(t) are well-defined at each timestamp t 2 O. In addition, the boundedness assumption of g is used to establish the Lipschitz property of the score function with respect t in the literature (Chen et al., 2023a;b;c).
We also make the following smoothness assumption on the target function fa.
Assumption 3.5. For all t) E gd x [To, oo), the function f. (x,t) is 31 -ipischcit in x, i.e, [f (x, f- t)l, S B1 I+ x' 2'112-
Assumption 3.5 implies the score function is Lipschitz w.r.t. the input This assumption is standard in the literature (Chen et al., 2023a;b;c). Yet the Lipschitz continuity in Assumption 3.5 only imposed on the regression function f., which is consequence of the score decomposition. To justify Assumption 3.5, we provide an upper bound for the Lipschitz constant 31 in Lemma G.1. The following theorem states a universal approximation theorem of using RKHS for score functions.
Theorem 3.6 (Universal Approximation of Score Function). Suppose Assumptions 3.2, 3.4 and 3.5 hold. Let R 2 T - To and Re be larger than a constant cj that depends only on There exists a function fu E H such that Ilf S dR and
['
T
- -1,,,, S R3} di S d R),
E [1Ixx(Xx:))
T T-T0 To .T
where A(RH, R) = (((R)
/Rx A(R)
log
VR A(R)
and A(R) = O(vaR2).
Theorem 3.6 provides an approximation of the target function by the RHKS under the I norm. For each given R, Rx is chosen large enough such that A(Rx, R) is arbitrarily small. We provide here a proof sketch of Theorem 3.6. We first construct an auxiliary function fx, = fx, [t| + To). One can show fo is Lipschitz continuous in (a, t) E IR++1, Then for each coordinate i, we apply an approximation result RKHS for Lipschitz functions over - (cf. Lemma C.2) to find function that approximates ft well. Since the NTK is not translation invariant kernel, we need to construct a shifted NTK such that fi E H₁ is close to ft after translation. The rest is to show that fH = ( lies in the vector-valued RKHS H. The complete proof is deferred to the appendix.
3.2 COUPLING
This subsection provides a coupling argument to control the error between the neural network train- ing and the kernel regression. We make the following assumption on the dataset S:
Assumption 3.7. There exists a function 6, (A, R) 10, such that + when + co and A + 0, and we have the following result holds with probability at least 1 - 51 (A, R),
t, E [To + A, and ||x,, 112 < R for all sample j.
'The constant e1 equal C(d + 1,0) in (Bach, 2017, Proposition 6).

---

Published as a conference paper at ICLR 2024
Assumption 3.7, which imposes regularity conditions the input data X1,) ), can be verified by utilizing the tail property of Xt, and the uniform sampling scheme for łj; see Lemma G.2 in the appendix. The next assumption is on the minimum eigenvalue of the Gram matrix H of the kernel K' and is standard in literature (Bartlett et al., 2021; Du et al., 2018; Nguyen et al., 2021; Suh & Cheng, 2024).
Assumption 3.8. There exists a constant d 2 1, dependent on d such that the smallest eigenvalue sttisfies Amin (H)= 2 Ao with probability at least 52(d), and ó2 -
increases.
As shown in the literature of deep learning theory (Allen-Zhi et al., 2019a; Arora et al., 2019a; Liu et al., 2022), the Gram matrix H is a fundamental quantity that determines the convergence rate of neural network optimization. We also remark that Assumption 3.8 is usually satisfied with sample-dependent lower bound Ao: see Lemma G.3 in the appendix for a justification and see also Nguyen et al. (2021)) for analysis of scalar NTK. Now we are ready state our main theorem for the coupling error. Let us denote Cmax /R + (T To)
Theorem 3,9 (Coupling Error). Suppose Assumptions 3.2, 3.7 and 3.8 hold. If we set initialize (,) ~ ~N(0, 1a+1) and of Unif 1) i.i.d. initialize 7(0) prop- then with probability at least f-r, all r 2 0 andd = ......m
(dN)) Cunax A
Ω
erty, and set 17- = O
Do (dN)-C
simultaneously, we have
[Ill (fwr)((X,, - ( (xx00)111 S R} dt
E
T To To
4 T +
d0
N9 max
/mAA8+A2
The proof deferred to the appendix. Theorem 3.9 controls the error between the neural network training and the kernel regression. One can choose m = Poly(d, N, R. A, λo, 6) and optimize over R and to make the error term small. For each fixed input data sample, (Arora et al., 2019b, Theorem 3.2) shows that the coupling error is small with high probability. Our analysis improves this result by showing that the L coupling error also remains small with high probability. To prove (cf. Theorem D.I). elin at each iteration т. (r)
Theorem 3.9, we first show that the training loss (8) converges with a linear rate
Next, we show that fw(r) performs similarly as a linearized function f
Finally, we argue that the L loss between the flin (W) and f is small because of the concentration of kernels and carefully chosen initialization 70) depending the neural network initialization.
3.3 LABEL MISMATCH
In this subsection, we provide an upper bound for the error term induced by the label mismatch. Recall that f. is trained by the kernel regression on the dataset S while f. is trained on the dataset S. We control the error induced by the label mismatch in the following theorem.
Theorem 3.10 (Label Mismatch). Suppose Assumptions 3.7 and 3.8 hold. If we initialize both fo and ju properly, then with probability at least - ō it holds simultaneously for all that
E 11 (z. (x,
(z. 1) 11 T [1lx s R3} di s dA(R R) + Co (ViA(Re, R)T + +T))
T To
Io
where
To = 2d dlog3/2 ( (eCimaxe (dN)3/2 A ((N R.)
A(RH R)Cmax +
1
2
Ao
Au
d² A222RRe R)
(log(1/6) + log (log N)),
Co is a constant defined in Lemma E.2 and Cmax is defined in Theorem 3.9.
Theorem 3.10 links the error between fK and fKK to the approximation error A(RR, R). The proof of Theorem 3.10 (deferred to the appendix) consists of two parts. We first utilize the kernel regression structure show that the predictions of fKK and j.K are similar over all the samples (t,, X. Next, we apply the vector-valued localized Rademacher complexity (cf. Lemma E.2) to show that the performance of these two functions is also close w.r.t. the population loss.
8

---

Published as a conference paper at ICLR 2024
3.4 EARLY STOPPING AND THE FINAL RESULT
Given the function jKK trained on the data set $ Xo.
and the target function
fu H that generates the virtual label Xo.j, transform the score matching problem to classical kernel regression problem. The next technical assumption allows us to reduce the excess risk bound for the early-stopped GD learning in RKHS to the excess risk bound for learning Lipschitz functions.
Assumption 3.11. Fix any fH H with llfrell I Rh and assume labels are generated as Xo,- = 1)) tey. Suppose jK is obtained by GD-trained kernel regression with the number
of iterations T. We assume that there exists e such that
1
[X
(1IXX,l)) S R) dt (N,
T T To
and ((N,T) + as N co.
Here, is data-dependent early-stopping rule control the excess risk of kernel regression. For supervised learning with noisy labels, an early-stopping rule for GD is necessary to minimize the excess risk (Bartlett & Mendelson, 2002; Hu et al., 2021; Li et al., 2020). We remark that, although T is defined through the kernel regression for analytical purposes, can be directly implemented in the neural network training. Assumption 3.11 can be satisfied by an extension of classical early- stopping rules. For the case of scalar-valued kernel regression, see (Raskutti et al., 2014). Next, we provide generalization result for the score estimator:
Theorem 3.12 (Score Estimation and Generalization). Suppose Assumptions 3.2, 3.4, 3.5, 3.7, 3.8 hold and we set m and 17 as prescribed in Theorem 3.9. Moreover, suppose T satisfies Assumption 3. II with corresponding c(N, T). Then for any large enough R and Ru and small enough A, with probability at least 8, it holds that
[" 1(t)
[1swc)) (X,,t) - dt
T To J..
16AD2
N
$ O e--d- R2/1)_1-1111000 +AdA2 R) + T-To +
VmABo+A?
+ 4dd(RH R) + 4Co (VdA(RH, (
R)T, + +T&) + 4c(NN, (C,,,)T. T),
where A(Ry, R) is defined in Theorem 3.6 and I is given in Theorem 3.10.
Theorem 3.12 shows that the carly-stopped neural network (T) learns the score function V log Pe well in the 2 sense over the interval [To, T". To the best of our knowledge, this is the first algorithm- based analysis for score estimation with neural network parameterization. Combined with recent findings in the distribution recovery property of diffusion models, we are the first to obtain an end- to-end guarantee with provably efficient algorithm for diffusion models. The proof of Theorem 3.12, which relies on Lemma 3.3 and Theorems 3.6, 3.9 and 3010, can be found the appendix.
4 CONCLUSION AND DISCUSSIONS
This paper establishes the first algorithm-dependen analysis of neural network-based score esti- mation in diffusion models. We demonstrate that training overparametrized neural networks with GD can learn the ground-truth score function with a sufficient number of samples under an early- stopping rule. Our work investigates all three aspects of the score estimation task: approximation, optimization, and generalization. The analytical framework laid out in this paper sheds light on the understanding of diffusion models and inspires innovative architectural design.
In addition, our work leaves several open questions for future investigation. For instance, the depen- dence of our convergence results on the dimension of the problem seems sub-optimal. To address this issue, one approach is to consider the manifold structure of the data distribution, such as the linear subspace assumption as suggested by Chen et al. (2023b) and Oko et al. (2023). Another di- rection is understand the role of neural network architectures like U-nets and transformers in the implementation of diffusion models for image tasks. Finally, the analysis of stochastic and adaptive algorithms such as SGD and Adam is crucial, closing the gap between theory and practice further.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by gift from the USC-Meta Center for Research and Education in AI, gift from Google, 3M NTFA award, and the NSF CAREER award DMSS-339222
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances neural information processing systems, 32, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International conference on machine learning, pp. 242-252. PMLR, 2019b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332 PMLR, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019b.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint.
Acta numerica, 30:87-201, 2021.
Qi Cai, Zhuoran Yang. Jason D Lee, and Zhaoran Wang. Neural temporal-diiffrence learning con- verges to global optima. Advances in Neural Information Processing Systems, 32, 2019.
Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and Veronica Umanitá. Vector valued repro- ducing kernel hilbert spaces and universality. Analysis and Applications, 1001):19-61, 2010.
Patrick Cattiaux, Giovanni Conforti, Ivan Gentil, and Christian Léonard. Time reversal of diffusion processes under a finite entropy condition. In Annales de l'Institut Henri Poincaré (B) Probabilités Statistiques, volume 59(4), pp. 1844-1881. Institut Henri Poincaré, 2023.
Alain Celisse and Martin Wahl. Analyzing the discrepancy principle for kereliieed spectral filter learning algorithms. The Journal of Machine Learning Research, 22(1):399833556 2021.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning. pp. 9735-4766 PMLR, 2023a.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning, pp. 4672-4712, PMLR, 2023b.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. International Conference on Learning Representations, 2023c.
Sitan Chen, Sinho Chewi. Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast. Advances in Neural Information Processing Systems, 36, 2024.
10

---

Published as a conference paper at ICLR 2024
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosin- ski, and Rosanne Liu. Plug and play language models: A simple approach to controlled text generation. International Conference Learning Representations, 2020.
Valentin De Bortoli, James Thornoo,, 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.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference machine learning, pp. 1675- 1685. PMLR, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint
2018.
Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
Hans Föllmer. An entropy approach the time reversal of diffusion processes. In Stochastic the IFIP-WG 7/1 Working Conference Marseille-Luminyy France, March 12-17, 1984, pp. 156-163. Springer, 2005.
Differential Systems Fültering and Control: Proceedings the
Xuefeng Gao, Hoang M Nguyen, and Lingjiong Zhu. Wasserstein convergence guarantees for general class of score-based generative models. arXiv preprint arXiv:2311. 2023.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neurul information processing systems, 27, 2014.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. International Conference on Learning Representations, 2022.
Uirich G Haussmann and Etienne Pardoux. Time reversal of diffusions. The Annals of Probability, pp. 1188-1201 1986.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 (6668066551,,,, 2020.
Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A nonparamet- ric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pp. 829-837. PMLR, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Diederik P Kingma and Max Welling. Auto-encoding variational Bayes. arXiv preprint arXiv:1312.611 14, 2013.
Ilja Kuzborskij and Csaba Szepesvári. Learning Lipschitz functions by GD-trained shallow overpa- rameterized ReLU neural networks. arXiv preprint arXiv:2212.13845 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pp. 946-985. PMLR, 2023.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejic Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint arXiv:2306. 09251, 2023.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping provably robust to label noise for overparameterized neural networks. In International conference on artificial intelligence and statistics, pp. 4313-4324. PMLR, 2020.
Puheng Li, Zhong Li. Huishuai Zhang, and Jiang Bian. On the generalization properties of diffusion models. Advances in Neural Information Processing Systems, 36, 2024.

---

Published as a conference paper at ICLR 2024
Shujian Liao, Hao Ni, Lukasz Szpruch, Magnus Wiese, Mare Sabate-Vidales. and Baoren Xiao. Conditional Sig- Wasserstein GANs for time series generation. arXiv preprint arXiv:2006.0542, 2020.
Yaron Lipman, Ricky TQ Chen, Heli Ben-Hamu, Maximilian Nickel, and Matt Le. Flow matching for generative modeling. International Conference Learning Representations; 2022.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-limg non-linear& systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
Song Mei and Yuchen Wu. Deep networks as denoising algorithms: Sample-efficient learning of diffusion models high-dimensional graphical models. arXiv preprint arXiv:2309.11420 2023.
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In International Conference Machine Learning, pp. 8119-8129. PMLR, 2021.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models minimax optimal distri- bution estimators. In International Conference on Machine Learning, pp. 26517-26582. PMLR, 2023.
Feng Qi and Jia-Qiang Mei. Some inequalities of the incomplete Gamma and related functions. Zeitschrift für Analysis und ihre Anwendungen, 18(3):793-799, 1999.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non con-parmmerri regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1): 335-366, 2014.
Henry Reeve and Ata Kaban. Optimistic bounds for multi-output learning. In International Confer- ence on Machine Learning, pp. 8030-8040. PMLR, 2020.
Danilo Rezende and Shakir Mohamed, Variational inference with normalizing flows. Interna- tional conference on machine learning, pp. 1530-1538. PMLR, 2015.
Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of Gaussians using the DDPM objective. arXiv preprint arXiv:2307.01 178.88 2023.
Jimmy TH Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. International Conference on Learning Representations, 2023.
Jascha Gohl-Dickstein Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learn- ing, pp. 2256-2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances in neural information processing systems, 11112228-12445 2020.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben
Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021.
Namjoon Suh and Guang Cheng. A survey statistical theory of deep learning: Approximation, training dynamics, and generative models. arXiv preprint 00::2400..07887 2024.
Wenpin Tang and Hanyang Zhao. Contractive diffusion probabilistic models. arXiv preprint 1rX11:2401.13115. 2024.
Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. Advances in Neural Information Processing Systems, 34:1 1287-1 11302, 2021.
12

---

Published as a conference paper at ICLR 2024
Pascal Vincent. A connection between matching and denoising autoencoders. Neural compu- tation, 23(7):1661-1674 2011.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang, Neural policy gradient methods: Global optimality and rates of convergence. International Conference on Learning Representations, 2020.
Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kemel boosting algorithms: A general analysis with localized complexities. Advances in Neural Information Processing Sys- tems, 30, 2017.
Junbo Zhao, Michael Mathieu, and Yann LeCun. Energy-based generative adversarial network. International Conference on Learning Representations, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine learning, 109:467-492, 2020.
13

---

Published as a conference paper at ICLR 2024
A PROOF OF LEMMA 3.1
Proof. Recall that the density function Pt can be written as
(x()) =
where the transition kernel Pej((1/z)) (2xh(1)) exp (-zntrs ||x - a(1)roll)) The domi- nated convergence theorem implies,
ll = Pt oo
(e(x)
(2th(())
4/2
x (0)))
1()
exp
|| 11=-a a00000
2h(())
po (r ddro
(x()
o())ro
Pr o (o0) dmo
h(t)
p((x))
/
a(t)z0
M(D)
(ol)Xx - Xx
E
X,
h(t))
(())
E [Xo] Xx = 28
h(t)
h(t)²
which completes the proof.
B PROOF OF LEMMA 3.3
Proof. The ideas in the proof are motivated by Chen et al. (2023b). First, note that
Peo(=z(=0) (2mh(tt)- 4/2 exp
|| a(t)xol1
2l((()
1
(1
s (2xh(t)) 4/2 exp
||| 12 -a² ||201
(t)
1
1
< (2mh(t))-442 exp
||, 12 |001|
(15)
2h(()
2
Denote the expectation with respect the marginal distribution of Xo as Ex With inequality (15), we have
T
[I - - fx,, [x +1 R3] dt
E
T
To
To
4D2
[" Ex 1/
VINI Polo(zs|Xooddy, dt
11
To
To
4
To
(2Th((1)-
-d/2Ex.
exp
||x0112 21((t)
(iallea exp
(-hh(t)
[[arell 4h(l)
dr. de
T
||ate|| 4h(t)
0
exp
dx
(16)
T
To J J12.RR
where the last step holds due to the facts that htt)) E [l(T)), A(T) and X < D. We bound the inner integral in (16) by using the polar coordinate (Folland, 1999, Corollary 2.51):
(- ||=,|| 112 4h((1)
4/2
22 y pd-idr
12 22
exp
(4hh())
dæ. T(d/2)
exp
4h(())
14

---

Published as a conference paper at ICLR 2024
(4h(t))a/2x412
exp (-u) u2/2-21
T(d/2) (R/(AN())
2(4h(1))4/27447
[(ee exp (-o2/t) de 8h(t) 1d-22 R2 2-R ((hht))
dT(d/2)
T(d/2)
where the last inequality follow from (Qi & Mei, 1999, Equation 10). Therefore, we conclude that
( - (x 1 (11x1l22 > R]] di
E
T To
To
8h(())4/2
2 (00-R//CMM //anN)) -
0
T To To
T(d/2)
C PROOF OF THEOREM 3.6
We first show that (x, t) is Lipschitz in for each fixed the following lemma:
Lemma C.I. Suppose Assumptions 3.2 and 3.4 hold. For each R > O, the regression function fa t) B2 Lipppsiiis in for all || R and [To, (C), i.e, (f-(x,t) (x, (2(R) It - t'), where (2) O(VaR).
Proof. We start with computing the derivative of f. with respect L. The dominated convergence theorem implies
0 σi
(x
Øi
0
ToPr o0pr0(()20))((z0) dzo
Øt
J pe (2))
/
8 ( dra
Pro (
Top: (20 Pa ("))) dro.
(17)
(J (1)o(=l21)))(rr )xy)
To proceed, recall that X, ~ X,, ((t) with att) = exp (- So o(s) ds) and h(t) =
2
1 - (t). By straightforward calculations,
0
0t (ro())20))
0
(2mh(()) d/2 exp
|| 11z-a(th --)a() -lt=)(()ooo
Øt
2h((t)
||- a(t)
_ - -
2h(1)
((==a(()xll))) [llv=a(()voll
2((r a(()ao)) ( x00'(1)
+ | (())xoll (()))))))1)())))))))))))))))))))
+ (2mh(t)) 4/2 exp
2h(t)
2h(t)
2h²(t)
zo0 (t)/(t) xoo((t)h(t) Since a' a'(1) -a()))(t)/2 and N((I) = -2((t)a (1) = (t))))t), we can rewrite (18) as
(-dh(t)h((t) + 2(x - a(t)))) T 21)(()
+ | - a(t)xol1 ht())
(18)
0
0r Pp)(((((oo)
15

---

Published as a conference paper at ICLR 2024
(-dh(t)a((t)o(() - (x- a(t)au) T
+ +
(t)
= (1)((//00))) a(t)g(t)
(-dh(t)a(t) - (a - -a(()))) a(t))
zgh(t) + -10
2t)(t)
al))(())
(-dh(t)a(()) at)) - (1+ a =a0))))))))
(19)
(t)
Plugging (19) back into (17), we have
/
To 2 Piu dro
(po a(t)a(t) E Xo
-1+ X, x [x+ x:= =
(12(1)
a())(l)) 212(1)
(-
x a 1=1 =d]
-(1+ || X, x a((1BB Xo 1 [x = =
and also
=oPr1o(1|2000puf 2 = dzo
(s p1
a(l)a(()
E
X -dh(t)a(t)+ + +100 x, a(l) 1x X, X,
(t)
a(())(()) E
ah(t)a(t)+ (()) | -1 x, at)) X +
E(xu| æc]
(t)
(tt))(t)
(=)))) 1
X, = 2] a(t) | Xx 21 B|Xo/Xx, z].
2t²(t)
Therefore, we conclude that
0t (x,
(t))
(a(()) ||xol (Xo [ X
212(t)
a(1+ (E |1 1x, = x || [X (nX)24 X, = =x]l²) )
(t))g(t) 212(1)
((()
| (Xo
E [xo X.))
X. = =| - (1 + a² (X)))oo(XX)X =x))) =))
The Pythagorean theorem implies that I|.oo E X X.I|| |1l < |Xoll Since ||ooll2 - D by As- sumption 3.2, we can apply the triangle inequality to obtain
s a(t)g(t) 2t²(t)
(x
(())
| 12 I|x, E|xo|Xxlll Xt x;=
sup (E(To.oo)
sup
0t
SR
+ +11 | (1 =x)
O(VaR) = B2(R),
where we have used the facts that att) < 1, h(t) 2 hT)) and gt) is uniformly bounded on (To, oo).
Next, we define two kernels without the bias term. Let H4, be the real-valued RKHS induced by the scalar-valued NTK R. Rd+1 Rd+1 - IR defined as
ā(z,ā)= = z E [ { w (0) T = 2 ( 0}].
16

---

Published as a conference paper at ICLR 2024
Similarly, let H be the veluur-valued RKHS induced by the matrix NTK K R xR Rdxd defined as
R (2, 2) = R(z, Ra
The following lemma shows the approximation of a Lipschitz target function by the RKHS Hi over a ball with radius R.
Lemma C.2. (Bach, 2017, Proposition 6) Let Ri, be larger than constant 01 that depends only on For any function f Rd++1 + R. such that for any ||2]|oo 111//1 S R, supl|=ll =R [f](())] & A
and [f(z) - f(=)1 - R 2| z1112. there exists fH, E Hi with [| 1l
I RR, and
- log
sup [5(z) Sú, (z) A(R A(RR))=ool an ( VR || SR
VRz A
A
Lemma C.2 is from (Bach, 2017, Proposition 6) by specifying the dimension as d + 1, 0 and = oc. Now we are ready to prove that the regression function f. can be approximated by a (z', (z', = K [(x, t To), Theorem C.3 (Approximation of the Score Function on a Ball). Suppose Assumptions 3.2, 3.4 and 3.5 hold. Let R 2 T To and Rx be larger than constant e₁ that depends only on d. There exists a function fn E with |ffxl S dRu and
function in the RKHS H induced by ((xx, t),
-o))..
V Rh A(R)
V VRH
sup ||ll| (E
sup (x,, fl( A(RH, R) (())
log
A(R)
where A(R)= = O(vare))
Proof. We define an auxiliary target function f. _ x R + RR ft(x,)) fxr, [8 + To). By Assumption 3.5 and Lemma C.1, the function f. (z, t) is 31 -ipLisschi in x and (R)(R))iipshhir in for all ||~ I R and E [To, oo); so is each coordinate map. Since sup (a.t)) <.. SR (1, t) s D and for all [1(x;
1l) S R. [_ [')'',1'
S | 1) - -i((r' /0/ +
= [z, +b) ft(('',(t + I1f=ao', [t| + To) - fa |t'l TT)ll2
< B1 || +1000 I'll
S (81 + (2()
-2:00)((2))))) ())))((()(()))))))))))) (
(20)
one can apply Lemma C.2 by choosing A(R) = max [1331 + {R))) follows that for each coordinate = 1,...,d d, there exists
E Hi with 1 < Ru such that
H2
2 log
R A(R)
VRR
f1(x,t) t) -kh, (x, 1) < A(RH, R) = c((()
sup [[ SR
A(R))
Defining (1,x)) = Fig (x,t To), we have
- - (a( S A(Ru, R).
sup
sup
|| R (++b))
Note that f7 Igd+1 + R lies in the RKHS induced by the kernel n((x, b), (x',t') R((x,t
To), (x', 1' To)) and ||
8
Paullz We next show that fH = (fh...., f in the
17

---

Published as a conference paper at ICLR 2024
RKHS induced by K. Since each coordinate of fit lies in the RKHS induced by R, by relabeling data points, without loss of generality, it suffices to consider
(x()) Σ t)p((ttt)p)))
(2, E Ro+1 o E R.
follows
d fx(-)
f2( = Σ
Σ
Σ
2
(12 t)p:.)
P e; =
Σ p=1
((((,t))g
t)p:)
d a
E H.
i=1
Moreover,
d
P
1|/ Σ (p)
Σ age
Σ K((xx ()s))
Σ ex
ΣΣ ag K (((x, (et, t)
P.q
1,k
d
a ( t) (x,
i=1
P-q
Eaja((nntor)))
q=l
Σ 2=1
S dRx.
(21)
Hi 12
Therefore, we have found a function SH Rd+1 + Rd in the RKHS induced by K such that [lfxll S dli and
sup |
sup R LE[Tb.]]
[1, fn((, A(RH, R).
As by-product of Theorem C.3, we can prove Theorem 3.6.
Proof of Theorem 3.6. For any R T and [To, T], we have [H((X,, () fx(x, (1] S R}
sup sup (x, fa(x, 1)1 S dAZ R), | S
which implies that
E [[ -| S R]] dt s d(T Ab) (Rx, R).
To
Dividing both sides by Ty will complete the proof.
D PROOF OF THEOREM 3.9
To prove Theorem 3.9, we first show linear convergence of the GD over the training dataset
S = X.,)) Recall the definition (X,,, t To). Consider a Gram matrix ((7) iRdNNdd xdN at each iteration 7 defined as the following block matrix:
(T1(T)
HIN(T)
H(T) =
(T)
2, z2
0 IT {2 (x(T) 2 0, 0, (x)()) 2 20.
(Ni(T)
HNN(T)
1=1
18

---

Published as a conference paper at ICLR 2024
One can check that H = E [0)] with the expectation taken over the random initialization. For ease of presentation, recall that we have set Cmax R2 -T- so that [[ 13=
To)lla
[A, Cmax] by Assumption 3.7. Moreover, we denote the activation pattern of neural w, for sample
j at iteration as (T) = I (T) 2j 2 03. The convergence of the GD algorithm is given in
the next theorem.
Theorem D.1 (Convergence Rate of GD). Suppose Assumptions 3.2, 3.7 and 3.8 hold. If we set with iidd initialization for w, ~ NO Ta+1) and o² ~ Unif [-1,1], and ). then with probability at least 1 - 6, for all T 2 0 and r = 1.....7 m
(dN) A mOx
m Q
Ao
we set 17 = simultaneously, we have
(dN) max
((W(T)) (1 mno) ((W(O))
(22)
and
dNC2
(1,,())-,(0))l S Rw: =
max VmAoVo
(23)
Proof. Following the ideas in Arora et al. (2019a): Du et al. (2018), we prove the convergence of GD) by double induction. The induction to show that (22) holds for all т. It is straightforward to see the inequality holds for 7 = 0. Assuming (22) holds for 0 S 7' S T, we will show is also true for r' = T 1+ Let u(T) = vec(u),.... (T) and y = vec
MN) with uy (T) = (X 4)) and yj Xo.s We first need the following result hold uniformly for all 7' O.....T + 1:
a((W(r"))
(10)(r') (,)(0)122=
Ow,(T")
2
(C(W(7"))
S 17
(ww((T")
7"=0
VdN [lu(r") 3/12
S max
(24)
vm
7"==0
T/Cax VdN
(1- 122 ||u(0) =ll2
(25)
V
===0
1/C V dN
- (l 2ll2
(26)
Vm
T"=0
2Cmax V /dN
[1((0) - 2ll2
(27)
vmdo
Here, have upper bound on gradient (9) to derive (24). Also, (25) and (26) follow from the induction hypothesis (22) and the fact that /1 - x I x/2. We further bound
E [la((0) v1ž] = Σ [ (0) - wil
Σ
[(u5)² 22 [1 [r'(W, a, (X,,,
+E ( a, (X,,,)))]
3.7
[(n))² C = O(dNCR m.
where we have used the facts that E [WW a, (Xe,, (b)) = 0, 0. ((P) a, (Xr, S C
and [|v; llz < D. Thus, the Markov's inequality yields [lu(0) - y1 = OdN / /8) with proba-
bility at least 8. Therefore, with probability at least - 8, we have
dN max
[/w((') w. (0)l2, S R. 0
VT
T 11r= I.... m. (28)
19

---

Published as a conference paper at ICLR 2024
Define the following index sets
=== fr e [m] : [(A,,)) = =0, fr f [m] : [[Arr)] #0},
where A3r (1mm v R.o Cmax) }. Note that
(T]),(()) * (0)) - [1(Arr} + +I(lllo((T))) w,)(1]l2 > Rw
(29)
To see this, note that if [[))(()) - (0)l2 S Ru it follows (=) 2j (,,, (0) zz] S Ru Caax. If w.)(0)
TO 2j > mmax. then (r)(r') 2j > O. Similarly, if w0)(0))= 2j < - Ru Cmax. then
(T)) 2j < O. Hence, we must have [r))(()) (0). From (28) and (29), we deduce that
with probability at least 5, all neurons with indices in Sj will not change their activation pattern on 2j during optimization, i.e.,
r rE Sj = (1,((T) = [0)) VT' = 0+...
(30)
With such a partition, we can write the dynamics of (T) as
1
1) - uz(())
a (T + 1) 24) - o(w,(T) 25)]
m
a (T +1 (o
(w)))))))) 2;)]
/m
rES,
- (T) 2j)]
(31)
rES,
By utilizing the condition (30), we bound the first term in (31) as
at [T(w,(T + 1)T2;) 23) (T) 2;)l
m
rES,
(T) (w,(T + 1) (T)
mm
rES;
Σ (())
(-\²
(-mm m
1
N
(u((T) - si )a)a 20 T
2j
(32)
m rES;
N d
(T) - -b/)2 zt Σ (T)
m
rES,
N
d
(u((T) - (7
(33)
where we set (5()) = = E -\)) the GD update rule and the definition of H (T) derive (32) and (33). We further bound the error term as
2t Eres, ((a((())1,-(())((((>))) Here, we
n max
|S /dN [|((T)
(e)
(w((7)
w ||ا | |S
v112- (34)
m
m
Next, we denote the second term in (31) by Z5 (7), which can be bounded as
Σ at
2,) (Tw
Vm
r
|a
(w= + (7))
(T)) 2z
(35)
rES,
20

---

Published as a conference paper at ICLR 2024
Cmax
Σ
10y (T +1 wo (T)
(36)
m'
rEB,
Cnax
N
d
(T) - -0)a
(37)
Vm
m
rES;
1JCmnx
N
2u (T) - v²² ||el|l
rES,
8=1 k=1
T max
[Spl vdN
[|
y11
(38)
m
where we apply the 1-Lipschitz property of the ReLU activation function to obtain (35). Also, employ the facts that |at_ < and || I Cmax in (36). The GD update rule is utilized to achieve
(37). Combining (31), (33) and (38), have
d
-
(w)(F)
k=k==
which can be further written in compact form via vectorization:
u(T 1) - u(() (nH(()(u(()) - v) + <(T) + ((r)
=-nH(uTT) - 3) + n H(T) v) + c(T) + E(()),
(39)
where e(T) and E(T) are defined similar way as (T) by vectorization.
We move on to show that (T) is close to Hl when the neural network is sufficiently wide. First, the Hoeffding's 's inequality implies that, with probability least 1 8',
2log(2/8)
()) - Hije
C2 max
Setting 8' = = and applying the union bound, obtain
2 2log(2
H - H(O) = Σ
HO - High 2 s (dN))CH max
(40)
with probability at least - 6. Next, note that (29) also implies
211
m
(14 s [AAr)) (004)+1([lww... ((llw, w,)0l)l2 > Ra for some r]
It follows
1
(T) - (0)=
- 2 zt
a (,
m
r=1
C2 m
I (T,, ( (0) + (e)}
m
C2 max
Σ [ (Apr) + [Arr)l 2T (1) - w. (0)l2 > R., for some r} )
m
Taking expectation on both sides and applying (28), we have
E (T) (0)l
Ch
202
2 E [1 + [A2,r] + max IT (1]w,(T) - -o,(0)l22 > Rw for some r}]
m
4R
3
20 max 8
max
(41)
2
21

---

Published as a conference paper at ICLR 2024
where we use the following anti cntieconcentattion inequality for Gaussian random variables:
BeyCmoxx
1
2R Mmax
E 10 (|=1 S maax)
<
Row Cmax /2T 2T 112g112
v 2 A
(42)
Hence, we have
E -H S 4(d.N)² Ruw
C max
2(dN)
E ([) - H())))
max 8.
V2T
m7
K.k.t.
Finally, by Markov's inequality, with probability at least - 5 it holds that
[M (0)) - (dN)* max
(43)
Therefore, combining (40) and (43), we have that
|| H - l(2 - || H H(O) + [I( - H(T)ll2 (dN)
= (dN) (dN) log((d
+ +0
m
VmAgg3322
(dN)&CH max VmAg63/22
(44)
remains bound two enror terms in (39). From (34) and (38), we know that
[|<(T) +(())+E(T)ll (|E(T) + +E(T))l
N
(T( + (T)
j=1 1=1
(Cmax + Clrax) Sj vdN
[|u(T)
2112
m
J=
2n max dy ddN
dvdN
N [[((T) v112 Σ
|
(45)
m
Furthermore, it follows from (28) and (42) that
m I(A
2m Cinax
Vm(dN) max
E
|
= E
V2TA
Aovo2
Thus, the Markov's inequality implies that Σjn11 |5 -
/mdN22 CB
max
with probability at least
A063/2A
1- 8.
Before proceeding to the induction hypothesis, we need the following result, which holds under same argument as in (38),
||u(T +1) 2012)2()11 ~ Σ Ju (T + -))
2.
(dN) (ncr VdN [| - 81122
= 1 (dN)) Cit [| -
(46)
With the prediction dynamics (39) and all the estimates (44), (45) and (46), can prove the induc- tion hypothesis:
[| 1) =1
22

---

Published as a conference paper at ICLR 2024
||u(T + - u(T) + - - vll
||l(()) vlا2 + ||u(T + - - 2(u(T+ + -(()))))))())))))))))))))))))))) (u(r)- - v)
= =Il((T) -ull2 + [| +) - -u(r)11 1 2n(u(T)- - -) H(u(r) ((()) -)
(2)((( (H H(r))(u(T) v) 2(((T) + +((r)) (w(T) y)
< 1 2mp20 - (nN) + M(dN)& max
[ max
)) [lu(T) - v12
+0
VmA2g63/2
VmAg03/23
(1 (>> [| - 2
where use the assumption Ao Amin 0 and the bounds Ω
and
77 O (aaNoo
Therefore, we finish the induction and conclude the proof by scaling 6.
To upper bound the coupling term in the decompasition, the non-expansive property of the projection operator and Assumption 3.2 imply that
1
||LD HI
- (X),) s R}] dt
E
To
To
TotA
[|TT (Jw()( 1.t (x., 01. (1xxxll sR}] de
E
T
To
To
IID (fwrt)(Xe.tt) - (x,, t) 1| f11x = {R]] dt
E
T
To
To-A
4
1
E
(1 - 12 111 (1 s n3] dt. (47)
T To
T To
To+A
To upper bound the second term (47), we introduce linearized neural network (W()) updated by
.V Σ
1
مlix (X,,, Xo.s 11
W (T + 1) = (T) 17 2 (w)(
Lli (()(W)= 2 j=1
where Wi (0) = (0) and
Ilima (w (I,
Vm Σ (, (z,t To)l (w))((w()))) (0) (z, (x)) 1 To) 2 23.
1
Our next lemma provides the coupling emror between fw(r) and flin Let Px, be the probability distribution induced by X,. Lemma D.2. Assume the same conditions in Theorem 3.9. With probability least 1 1-8, 8, it holds simultaneously for each T that
To+D 10l1sn / [ - plin -Wr (z, 1) oIl dPx, (z)dl= =0 d( 9 max
/ ( A3A2
T Jo
Proof. Denote by Ir(r) = (wr(t) - 2 0}. Note that for each = 1,... d we have
(WG)) 1) Mini (cx
de (w) (xr,1- -Ta))= - Vm Σ a w (z)(-TTOT,(0))
o (T) (x, (0,,-TT0 (co))
Σ (T) T (T))))))00)
Vm r=1
23

---

Published as a conference paper at ICLR 2024
77 (,, (1,
1
a u, (T)
(T)T)(())) (s, To)T.(0)
vm
1
m
(x, (T)
TT) (Z(()) +
mm Σ
1 m
- - - (x,) (2,t)))) (0)
m
(w,(r) - (0) T (x, t Io) (T) #L))
m
[wr - C. (T)) (x, t To) 10),
(48)
where we use the fact that
|a| T (sgn(a) * sgn(b)) S la - ba (sgn(a) & sgn(b)) Va, b ER.
Taking square on both sides (48) and applying the Jensen's 's inequality, we have that
(w))) plin,é (w,)((,)))
5 2
(w)( - (x,t-Tb) Tb) (
+ 2
(wr(T)- - (b)))) (x, - To) ur (0)
(49)
We start with the bound for the first term in (49). Recall that Theorem D.1 implies that with proba- bility at least 1 5, it holds simultaneously for all 2 0 and = 1.... that
dNC Vm
Ir, (T) w. (0)ll) S R. o
max
Combining the above result with the Cauchy- Schwwar inequality, we conclude that with probability least 1 - 6, it holds uniformly for all ||1||| S R and 1 E [To + A] that
n2
(w)(T) (o) (1, (-, (T)
$ [[,(T) - (0)1 (1 - -b)
(T.())
m
< R2 C2 max
(IL())((())))
(50)
Taking expectation over X, and integration overt E Ao+ T), the following holds with probability at least 1 1 d:
Σ
- (w, (x,) Ta)l -z,t)T))) - I1I((7) # 1,(0)) dPx, (x)df
|1 SR
< R22 02 max
(T1,(T) * 1,)) dPx, (x).
(51)
To+A
Next, similar to (29), we have for all ||0||| < R and E [To + A, 7' that
I [[I+(T) (0) < I w. (x, -T) R.g Cmax) } + I ([]),(()) w. (0) Rw, - (52)
Also, similar to (41), by taking expectation w.r.t. {w, (0) }m in (52), we have for all ||ا||| S R and e [T + A, 2' that
E
(1)(7) 4 ((()))
24

---

Published as a conference paper at ICLR 2024
E B tor (0) (xr, To)l & Rno Cmax }] + E (1lwr(T) -o-(0)]] > Ru for some r}]
Bup Tmax
+ 8.
(53)
V
Now integrating over (x, t), we get
TR
(T,(T) II
dPx, (z)dt
To+ 11
12mBin +
s (T To -
V2TA
Since the neural network is initialized independent of Xx, the Fubini's theorem and the Markov inequality imply that with probability at least - 6, the following inequality holds:
S E + +())) dPx, s (T To AA) To+o 1111SS
(2mBu Cmax +11
Therefore, applying the union bound, with probability at least
-2 it holds that
T To Jo+A /
((w (0)( (2z, (
To) ((,(()) + (0)) dPx, (x)df
Rmaxx
T - To -A
R22 C2
max
V2
1
T T To
2 max
(dN) max
( max
=0
(54)
m255
Vmm5b/223
We move on bound the second term in (48). Note that for all ||I1|/ S R and t Cauchy-Schwar incquality implies
To A, T1. the
(w,(T) (T(r)) (x., t To) T,(0)
1
(()(()) 22 (T)lla 11xz,t To)ll2
Cmax
(w,(T) - C. (T)12.
(55)
vm
Recall the GD update rule for wr (T) and (T) as follow:
w. + = w.( Vm
17
Σ (w)( 1f)a(,211 (w.(7) 2g 2 0},
w (+ + = (T(
1
(uy ( ( (w) 2j 07
lin.
mm
i=1
in which let (T) Bw(rr and u,
Jin. (5n.((7) (7)
W(r) be evaluated at the sample (Xt,, (j). Thus,
we can write
N / m
wr + 11 t. + = (-(()-)) - [T(
(1)(T) vf)ates (T,,()))I,,(0))
j=1 1=1
N
(T)(T)
u. ()) (222
j=1
25

---

Published as a conference paper at ICLR 2024
Taking the 2-norm on both sides and applying the Cauchy-Schwarz Schwarz ineuaaayy we have [ T + 1) - wr([ 1)
N
$ [|) - प. (T)122 + 7
(T)(T) - 113122221 - -1,.-
mm ==1 1=1
lin. (T) (T) mm ()) 4j
|a)| | (0)
WVdCmax
< [T) - Th (T)ll2 +
(1)(T) v;)²
1 (T), 11,)
Vm
7D max
N Σ
Σ
(T) u (T))
(0).
mm
Summing over all neurons and applying the Cauchy-Schwar inequality again, get
00, (T + 1) (r (r+ 1)ll2
m
m
N *
|u, (r) 1. (T) nV
ΣV (T)(T) 9;)²
jm1
1/v WVdCmmss max
((((T) - Ba (7))
2
Σ
m
N
(,,(
(56)
Since wi (0) = w,(()) telescoping sum over (56) leads to
m
T2
N
[T)))l nyVc max
[[((s) vll2
(1,
+ n/CC max
|u(r)-u(l ())(
ΣΣ
(0).
(57)
r=1j=1
Theorem D.1 implies that with probability at least 5,
ddVC2
[[u(T) 2112 < (1 1770)) [l((0) v1l2 = (1- - 00
max
(58)
8
Moreover, (53) leads
m EI ((,,,(()),,,, r=1j=1
S N
+ 8).
12
The Markov inequality implies with probability at least - 8, we have m
ΣΣ I(, (,, S SN(
(2mBBug Cmaxx
V2TA8 +1) 0
+ max
dN22 V C
(59)
AgA83/2
remains to provide a high probability bound for |u(T) - lin (T) From the definitions of u(() and u lin (7), we have
utf (T + 1) " Jin. (T 1)
1 Σ a (w, (T + +1)
Σ
m
a wr (T + (2)1..-00)
r=1
r=1
26

---

Published as a conference paper at ICLR 2024
m
1 m
d wr (T 2,1
+
a wr + 1) 23 (T (T+ - (T)( -)x
00 + 1) 20
r=1
m
wr(T) - O. (((W(T)) (T)
2)11,-(+++ + 1 m
vm Σ wr + +1)=+++) 23 (Tz,-(T + 1) - (T)r
m
(T) - a a (())))
dr
(T),(T)
201
m
2Z (3 I,- (f(W()))
T box(t1) 2j
= (T)
(T)
lin.
( +
Owr(T) 11
vm
(T)
a (T + 1) 23 (11 (T 1) - (T,((t))
m r=1
N
(T) u
Jin.& (r) +
link (r) (T) - vτ² H (0) Σ
(u) - (T)
Am1 1mm
Em km
ay Wr (r + 1) zj (Trr (T 1) [T,((T))
m
(T) (T)
lim.s (T) + +1] Ui
(ue
liak (aa - u ut) (0)
Σ (1 + 1) 2j (T, +1) (T)(
Here, we use the facts that (xx) x- 1fx 2 0} and the GD update rules for (r( and (T(
Define a block matrix Z(T) such that its (i,j)-th row is
1
( (T) = vm [ (T) ai 2, [n.m(T]]-
By vectorization, we rewrite the above equation in a compact form:
u(T 1) - 1in 1) u(r) u 1nmn (r) + (H) 'n (()) v)
+ (Z(T + (++
= (IaN - (O) u (T) - +1) ((()(())))) -v)
[((T)
+ [ - 1)
(60)
=((T)
Unrolling the recursion (60) and noting that u(0) = (0), we obtain
u(( - u lin (7) =
- (-()
==0
The summation should be understood as O when 7 = 0. Taking 2-norm on both sides and applying the Cauchy-Schward inequality and the triangle inequality, we get
||((]) TM (T) <
(n [1 - - (12 + (1(())
< (1
1)70)= (-) + 1|(())))
(61)
6=0
27

---

Published as a conference paper at ICLR 2024
2o/2 with Here, apply Assumption 3.8 and the Weyl's inequality show that Amin Amin(((0) (H probability at least 1 (Du et al., 2018, Lemma 3.2).
We now turn to bound [[())]l2 and ||{(s)]l2 Note that (43) and (58) imply that with probability at least 1 26,
[[(()][22 < ([H 11 (1) [l((s)) 1112
(dN) max (1 n700)012 (1-7)0))01
dN
VmAg83/24 =0
(dN) max (1 n7o)0/2)
0O
(62)
VmAg022
Next, bound ||{())]12 note that for each (entryy we have
m
[
5 Vm
afl
( (s 1) 23 (s 1) - [s)(
(r 1) w. (8) 23 [1rr + - [,)(
Cmax
|w, (s + +1 (s) 1) - (s)(
(63)
/
To proceed, apply the GD update rule get
N
(8 we (s)l22 v
(uf (s) 25)
Vm
1=1
mmma
[[((s) yl1 S WVdNC
l|u(s)
vl12.
(64)
mm
vm
Plugging (64) into (63), we have with probability at least 1 - 38 that
VVNC
[S(s
[u(s)
2112
m
7 VVNC2 max
-1++ (y 11 (,) + Σ ([((s) 2112 Σ
(s)r L,,- (001
m
r=1
CV
dN
22mBr Cumax + +1) +1))
max (1 1/22
m
V2T
Cs max (1 71)) //22
Vmmgdo2 A
Thus, with probability at least 35 we deduce that
N
{]() = o -00--00(00 (1((a))CG max (1 1220)%1))
||(()]]2 s [{(5]]|
=
Σ
/
(65)
1=
Note that
Σ (1 (1- 11-m T-1- = (1 - n7u))) 7
(1 ndo ---
sm0
< )770) 1-1
1
77
< 2(1 - Not
n,o
28

---

Published as a conference paper at ICLR 2024
Therefore, with probability least 1 56, it holds that
(((T)) - li (T) = O (dN) max (1 n770) =
(66)
Now, substituting (58), (59) and (66) back into (57), we have with probability at least 1 - 7 that
dN
VdNm 1/mmm//C2. C/ max
(T) (T)l2 S nVdC max
no)
5 /AOVA63/4
8=0
(dN))/=C
n dC max
max n7n
V
(dN (dN))/22 m/402/m//40/
(dN))
max
No 3/2 8//4
(d m 1/4
max
(67)
3/2 82 X
Since (67) holds with high probability uniformly over any given (ar, 1), we know that with probability least 1 78, (55) can be bounded uniformly over all ||I||| I R and t [To + A,T]
m
(dN)) max
- (r))) To) I.()
(68)
1/ 8/2822
Integrating over (48) and combining (54) and (68), with probability at least 96 it holds that
T To Tota /1 (w,)
1
-Wii (z, (2, e)) (x),(x)d
(d max
(dN))/2 max
2
(dN)) max Vmo+> 2?'22
I mm
mm//4 2//2///222 82
As consequence, with probability at least 96, we have
T T- Jo+A 1Rl, |[ -
fin ( (z, t)|l -
dPx. (x)dtt
(d(dN)) ( //m64122²
max
The proof completes by scaling 6.
Next, control the coupling error between the linearized neural network flin ( and the function f.K in the following lemma. Recall the update rule for 7(T) is given by
<T + 1) 7()) ()H v), (0) H-)
(69)
Consequently, multiplying both sides of the update rule by H leads to
u K 1)+
(HH (T) v), u K (0) = u()).
The update rule for can be viewed as a GD update rule under an alternative coordinate system. Let w = VHy and define the training objective
1 EK (w) [K(w)= = う ||u v112 -112=1 1 - | V/22 2
2
2
Here, we use the fact that u K Hy = HHw. Thus, the GD update rule for w is
w(7 + 1) w(7) w/H (7)
(70)
Multiplying both sides of (70) by H recover the update rule for (T).
29

---

Published as a conference paper at ICLR 2024
Lemma D.3. Assume the same conditions as in Theorem 3.9. If we initialize 7(0) =((0)
(0) (O), then holds with probability at least that
1
-
|
(2, 1 (a,
dxx Ö (z,
(x) 1|
(
(d m822 X/
max
T To Tot A Iallssn
Proof. Note that the gradient of the training loss is
aZin
a 1
I lin v12 Z(0) T (u y).
Övec ()
@vec W)
2
We first show that at T there is vector 7(0) E RdN such that vec W (0) Z(0). Note that our choice implies 7(0) = (0) = ()) )) (0). Let Z(0) = UEVT be the correspond- ing singular value decomposition. Since (0) has full row rank, we write the diagonal entries of Σ d1 OaN 0. Noting that u (0) Z(())ec(W(0)).
Z(0) (0)) = 2(0) (Z)))(()))) wi)(())
VΣ UT (UEV U -EV veol ((())
VΣ UT (
..... .2. JUEV veol (W())
IaN
V
V vee (W()))
0
TaN
0)
0)
JaN 0
9) rT Vevee(W(())))) vec vec(W(O)) (W()).
V
0
It follows for each r, there is vector 7(7) TRdN such that
vec( (W()) vec (T (((17-1))) 1)) n/((0) T (u lin (r 1) - Z(0) (())
Define matrix Z(x,t) Rdxm(d+1)) such that its i-th row is
-110011 [o, I,) ... on T (0)
(Z(x,t))
mm
Next, we rewrite
N
plin ( (2, 15 (x, = (lt,))vec[[(s
Σ
(1)
#=1
-Zzx - Σ K (x)
3=1
Z(x,t)Z(0) T 7(7) -
= Z(x,t) T (5(r) -(()) - (Z()) k(2, ((7), (71)
in which we define
k(z,t) t) = [K(,,,, &1), (a, t),. ((,,)),,,,(((,,,,, (N), (x,,)),, <(F) = (nT (T))...((((()))
Taking square on both sides of (71), get
(x, + (z, ||
(2(x (2) -k(x,t) x(7)) (7(7) - (7)))
2 Z(z, ()) -r))) + 7(x, (Z)) ((x, -<()) 1) (1x()))11-
Since (0)) (0) T and the Gram matrix of K is H, we have
=m) n K (7) H())7(T) HT(T))
30

---

Published as a conference paper at ICLR 2024
-((0)(((r) (H(()) (H)) H))(T).
We first upper bound | (T) - w² (T)l12- The GD update rules imply
( r + 1) u (T) (T) nH (O) v),
u ( 1) u (7) nH (T) y).
with u (0) uz (0) u0). It follows
Lin (T + 1) u (r + 1) n (r) - n (T) (H- ((0))(1 (r) y) (O) (7))
(Jax
uz (T)) - n ((O))(u y)
(72)
Unrolling (72), have
(T) (T) u (T) = (LaN (H) (u (0) -()0))=-()) (0))
u
11 (JaN-
-9)
=
Σ (JaN HH - v).
Taking 2-norm on both sides, we have
Ji (r) - u (*=x((()) (T) 1 - H(O)]l2
MaN
(0)11 - 1 (s) -vll2
7-1-8
S n H(O))l2 Σ
1 MAA
| (s) -v112
S 1n H(O)Il2
max
|| |1x(())
-112
r-1
1710
T-1-8
05+55-1
2
Note that with probability at least 1 - 5,
VdN. Cmax
max
|| (s) v/l2 ||u (|(((() -yll |l v1l2 0
(73)
vo
With (73), we deduce that the following holds with probability at least
25:
| (T) u (T) (7) ddNCmax V (dN)2/5)
VdNCCmax Vo
2
o
Vm
17Ão
= =ō ((aN))322(
( vmmgg
remains to bound [/((T)]22 The GD update rule leads to
+T+11) 7(7) 7(H y) = (LaN ( + my.
Unrolling the recursive formula, have
((T) = (JaN - (1) + Σ (JaN - nH)
==0
Taking 2-norm both sides, we have
r-1
[lx(T) < MaN - nHll [1(()) +
Σ
(JaN - m/1r"
l1l1.
31

---

Published as a conference paper at ICLR 2024
Note that
Σ (LaN - nHl)= (JaN (laN - - 3 1
where we choose small enough so that LaN nH is positive definite. Therefore, with probability least 1 - ((), we have
(oVdNCnmas
l1( S | [l((0)112 || 11 111l111122211111 =0
-ov88
Finally, we have
((aN)))2C) Vmdoō
[dNCmax V'm
VVNCCaax
(ddN)a//
2 (()())
max
max
2ov8
Vmdg6
With all the above results, now bound for all ||ll|
R and L E [To + A, 7]
that
(dN)* max
(w,) - f (x.t))] 2 Z(z ())()
mdjd2
k(x, 1) 1/2
[dNCmax max
+2 Z(r,
(74)
275
Since 11(x, - -Tooll2 S Cmax. we have
m
2
[Z(z, 1)112 -
(z, 11
ΣΣ
ax , -6)
S dC
mm
max
In addition,
d N
(
(0)
ΣΣΣ
- Ij. (0)
1
$ dNC
Vm
max
1=1
j=1
1= j= rm
Now integrating (74) over ||0||2 S R and t [Tb yields
yields
Sitte /
clin [W,)) t) - 1 (z, 101 dPx, (x)df
(x,
(
(ddN)
NC max Ô (m
max mx332
dP)
TotA |
1
Z(zxt)Z((0) - R k(x (xx,0)/ 1//30 0
(NCC
+2
max
TotA 1R
225
dNC2
T
((x)))Z(0)T - R(xx,t) 0)| dx)x
I 0
max
2/0
Tota 11111,5R
dd N'CS
+
max
(T TToo To -0-1) A).
52
Note that for each k, we can write
m
Z 2. z) 7) it
- a - To) (0),,,,)))I,(O),,,
which is a summation of independent random variables bounded by C when ||r||2 S R and
t e (To A, T). Taking expectation over the initialization, we have
C
F
(Z(x)
Rg (x.
Var (Z((r,))Z(()
max
m
32

---

Published as a conference paper at ICLR 2024
Integrating over and gives
- k7)(,, (2((,1))))
x (x)dt
dPx,
max m
(T (T- A).
The Fubini's 's theorem and the Markov inequality imply that, with probability at least 8/(dNN),
/ S Tota Ialsn
(Z ()(00)) 7, Kit (z,, 0 dPx (x)dd (
s o
Cdi N
"max
(T To - 4)
mā
Therefore, with probability at least - (55), we have I
plin ((T) (I, f t) dPx, (x)dt
T To To+a
dNC max
Cax dt N22
( max
I 0
+
2go
md
m2j02
N max
which finishes the proof.
Now we are ready to prove Theorem 3.9. Proof of Theorem 3.9. Note that
([f (x,t) f (z, 1) s $2 [2 Aii (x,,
| f (z. t)
Lemmas D.2 and D.3 imply that with probability at least 1 8, holds simultaneously over all 2 0 that
1
[ - - (x, (x. 1) dPx (z)
T To
TotA |1
2
T
|WWG) Min Nir () (Pxx
5
T To
TotA II
1001, (Wi)) f (z. dPx
+ T- To Jota
0 2(dN))CIL max
+ d N max
V
m88 X3
2 No C12
max 5mA35 A
This finishes the proof.
E PROOF OF THEOREM 3.10
In this section, we prove Theorem 3.10. Our target bound
5 (x, - f.h (z, t) 1 d (x))dt
T To To 1
Here, f.K and f. are trained with labels Xo.; and Xu,;- respectively. We first bound the performance of these two kernel regressions on training samples. With the same spirit as in the proof of Theorem D.I. let " (7) and ū (7) be the prediction of f and jK on the samples, respectively. The following lemma provides the label mismatch error the training samples.
33

---

Published as a conference paper at ICLR 2024
Lemma E.1. Assume the same conditions as in Theorem C.3 and suppose Assumption 3.7 holds. If set small enough and initialize fo and for with the same parameters (())- then have the following upper bound:
1 K (7) ūK (T) dN dN R)
Proof. Note that the GD update rule leads to
K (T 1) u (T) nH (u 1k (T) -yy y)
(JaN HH " (r) + +nHy
= -LaN nH) (0) + Σ (LaN - H s=0
-IaN - -H) + (JaN (IaN -nH y..
Similary, for ik(())) (T), we have
nK (T + 1) = - nH) (0) + (LaN - (LaN 7
By the design of the initialization, we have nz (0) = ū (0), yielding
u²xr) ūh (Lax (LaN n ) 17)
Taking 2-norm on both sides and applying Theorem C.3, we get | K (T) - 7th (-)1 11lxx - (laN - 1) - 2)11
Jaa (JaN - 17/ Ilv 51
N
I1mas SH.Sl12
j=1
Σ
[| SH.ill
j=1
dN
sup (
sup [I, fn(2 f=( I d.N ddN((Rx, Ry?.
Here, we utilize the assumptions that |Xt,l22 S R and 1y Too A,
To go from the training loss to the population loss, we need the following localized Rademacher complexity bound: Lemma E.2 (Reeve & Kaban, 2020, Theorem 1)). Let F = {s Rd [To, T] - [-3,3]4 for
some B > 1. Take d E (0, 1) and define
Tx(F) = 2d (Vdlog2/2 3/2 (eBdN) RaN (I+F)+
VN )
d32
+
N (log(1/5) + logg(og N)),
where the worst-case empirical Rademacher complexity is defined as
n Σ
(
sup
E, sup [EF n
Ceffe(
((
where the expectation is conditioned the given samples ((ze, is) There exists a numerical constant Co such that with probability at least simultaneously that
(RR x (To, x Id)"
5, it holds for all f E F
T To 1o / 11((,,0112 (x)dt
N
(V
1 N
I((,,, t>l Io(F) ((())+((07))
(f((e, Co
Σ
N
N
Ø=1
34

---

Published as a conference paper at ICLR 2024
Lemma E.2 is result of (Reeve & Kaban, 2020, Theorem 1) by setting X' = R [To, I1, V- [-3, 3] and = {0} _2 and letting [(v, y) || S dB², Note that the loss function C is
(2d, 1et11/2)llf-ouudddee Lipschitz as defined in Reeve & Kaban (2020) since for any v E V.
||ul - = ||| |1 (11lll2 + 110112) & 2d [Iull2 [eelle] -
1| vlloo
Now we are ready to prove Theorem 3.10. Recall that f. and ft are paremeterized by 7(T) and 7(7), respectively.
Proof of Theorem 3.10. To apply Lemma E.2, consider the following function class:
F = [xx,t) - (a. (,,,,, t) (1|=|12 S R) ((x, 8) Rd (To. T. H. II S pp.
Given {(EE, 8=) with =ạ = (t), we define an index set L fe: | ll2 S R2. The empirical Rademacher complexity of F& can be bounded as
R₂ (II F.))= - sup (1=2))))=
Ex sup
Eef
(2))
2 (11x s |R
11 Sp T
1=1
Σ Ces
Ee ((xe)e))
sup
sup
11ll Sp
EEL
sup
Ee
sup
Σ [el((z))
Teir Bie
((xdd)))
11lly n LEL
1 Σ ce (J, ((, ze)
sup
Ex
sup
(75)
11 n LEL
sup
E.
sup
J, Σ EeKi (e 2ie
{(xe,d))1__1
REL
LEEL EeK(, (eK(-,ze)es ze)es
sup [(x,,d))2_ 72
Ee
E Gek((,2))e 11 EEL
Σ EcK((
(76)
H
LT.E
Σ Ce (,, 20)
sup ((xe)ee)22
12
BEL
LE.
Σ EEK((, (;
sup ((
n
REL
< sup ((=2))))
E
Σ <x 2z 21)
(77)
FEL
14
sup ((sr.ir))
P
|| | 2x
(78)
n
REL
sup ((xe)
P
Σ REL
e,, K 2e)e
(79)
n
sup [L] n
P.
VIL
02 max
pCiax
Vni
Here, (75) holds due to the reproducing property:
(F,((,))c) T H.
35

---

Published as a conference paper at ICLR 2024
In addition, utilize the equality condition of Cauchy- -chwwazz inequality to obtain (76) and (77) a consequence of the Jensen's inequality. Moreover, we apply the facts that E [egce] = for
+ l' and [+]]
derive (78). Finally, we use the reproducing property again to get (79).
To apply Lemma E.2, we next calculate 3 associated with the function class F.P. Note that the reproducing property and the Cauchy-Schwaar inequality imply that
sup (a,))e** [To.7]
max
ff t) f||=]12 2 R}
IsiSd
sup sup
max
(f. ((, (z, t))
1 (e( Isidd
s sup sup
|lfll
max 1sid
[ (I, t))
S pCmax.
remains find a p such that |1,55
jk 7
S...
Note that
5 jk
{5(T))
Σ Σ (T)(7) - -T((T)) ((()))K(((,)))))) ()) (X) -2(7))
j=1
(T( -()) ((((T) -(7)).
Note that the GD update rule implies
(() - ((r) H - (JaN nHH 0)
Therefore, Assumption 3.8 and Theorem C.3 lead to
pK
|1(Tav (IaN -1H2) --71 H-1
$ H 1H-1l IaTl - -IaN - nH2) l1y Øll2
ly أll VdNA(Ra) R)
Ao
Ao
Here, we choose 7) small enough and use the fact that ||1 is finite. Now we put all the results together and apply Lemma E. conclude that with probability å that
T To 1'd J
5 (x,
f (x, (| aPx, (x)
Σ 1l -r) Co (1
1
1
Σ
u -ax(r)) Is + +1s
N
< dA(RM, R) Co (VdA(RH, R)Ts T's)
in which we define
Ta (R(
2
dg3
2d
VVllog3/2 (e3dN) RAN (1l (I
F)+ +
(log(1/6) + log(log N))
VN
N
pCmax
2
Cp C
s
VVilog3/2 (epCmaxdd)
(log + log(log N))
VaN
VN
N
(log3/22 eC (CCmax (d A(RR, R)
A( RR,, R)Cmaxx
2
2d
Ag
Ao
VN
36

---

Published as a conference paper at ICLR 2024
d8 A² (Rx: R)C (log(1/6) + log (log N)).
X
F PROOF OF THEOREM 3.12
In this section, we prove Theorem 3.12.
Proof of Theorem 3.12. Let Assumption 3.11 hold. The proof is immediately implied by combining Lemma 3.3, Theorems 3.6, 3.9, and 3.10:
X())E
(W - V log (x)
di
T To
Jo
T
(Fo(f((r) - fo (X, t) 1 dt
E
T To
To
T
E
[I 1)) fo (Xe, 111xel2 - R3] dt
T
To To
E. [ITT((/((X..)) - (x,, (11x1112 > R3] dt
T - To To
16AD2
N' max
+ 2 12/44 4dA2 R) T To
Vmijo'A2
4dA(RH, R) 4Co (VdA(RM, R)T& R)[o+T6) +T6) + 4c(NNT),
where the last inequality follows from the decomposition in Section 3. This finishes the proof.
G VERIFICATION OF ASSUMPTIONS
In this section, we verify Assumptions 3.5, 3.7 and 3.8. The following lemma provides an upper bound for B1 (defined in Assumption 3.5). Lemma G.1. Suppose that Assumption 3.2 holds. The Lipschitz constant 31 in Assumption 3.5 can be bounded
D
81 =
h(To))
Proof. The proof essentially follows from the Tweedie's formula. We first observe that
1
(o)(()/00) x exp
| - a(1)aro11)
(h(()
||
(a(t)x xo h(1))
a2 I 2
exp
exp
exp
(L)
(1(
Let ((x) = exp
| 2h(0)
and T( = (ott)xo//()) We can write
()o(())))) = (xx) exp (x T T(xx)) exp (vb(20))
Here, v5.) is a normalization function such that the integration of Pajo(1120) equals one. The Bayes' rule implies
(oje(zolz) = Pejo(ar (ejo(ar/zo)ooff (zo)) exp (-v(x) + TT(xo)) (oo)))
Pc(xx)
37

---

Published as a conference paper at ICLR 2024
in which we define v(x) = log(p((x))/
Since P is probability density, must have Po)c(zo|2)ddzo
0 = v
V (orue) / f ee (o )dzo
-Vu(()e--(a) / TT po pola doo
+c- / T(xo)e= T(zo) Po(aneetea))
=-V((x) / Pol( + / T( To (2olo)))
= -V((x) + (Xx) =
follows that Vu(x)) [T(G)) = 2²). Similarly, taking the second-order derivative yields
0 / /
= V - Vu(z)e-u()) / 60 T(To)) (ooe (2o) ddro
+ eu-u)) / T(xo)e" T(mo) pa (o ydoo
(v'v(z)e-uu)) (V(c)(V (-m()) /
6" TT(oo) po (aoe
Vu(x) (<v()) / Muosee T(wo) po Waoo))
T (<v()) |Too)e T(oo) T(oo) pa (roe po ((oo) dooo
Vu(x)
-e- / (IZO)T(ZO)T O0 T(OO))
((0)) dro
-V'v(z) - V=(E) (B X2 x)=)
( =]]
=-v²u(>) + (Tx,) TT TXx = x] (Xx)) X, (X) = ==))
We deduce that v2v(x) = Cov(T [x) xx,
= =x). Combined with the definition of T(Xo). we have
| = = a(t) Cov Cov(XolX, x))
=((())
Since att) < 1 and h(t)) > h(T,), Assumption 3.2 implies that
( D (((To))
81 < V E X X. =]122 =0
which finishes the proof.
We next justify Assumption 3.7. The following lemma shows that the input training dataset has concentration property.
Lemma G.2. Let {(t, Xo,5, X1,) ) be samples collected from Algorithm I. With probability at
least 1 - 8, we have
E E (oo
s R. |
where 0 = T-To
NA
(21
38

---

Published as a conference paper at ICLR 2024
Proof. Note that in the proof of Lemma 3.3, we have shown that for any t [To + A.T]
R)] O - E [
It then follows
1 T To
[[[ & RJ
(1 - [1-E[1[(X S RJ)
To+A
- To To+
O (
2 T To
Set = T-To
A
+0
+O
22 and we have
1
P( S R) 2 8' To To
We set N8' and apply the union bound. Therefore, with probability at least - 6, it holds that
4 (ToT+A,
||x, S R.
Finally, we provide a justification of Assumption 3.8. Recall that H denotes the Gram matrix of K and H = [H*] sk the Gram matrix of н (independent of i). For the scalar-valued NTK k, we refer the readers Nguyen et al. (2021) for comprehensive analysis on the properties of H Our next lemma showsthat H and H share the same smallest eigenvalue for all E [d].
Lemma G.3. Let H and H be the Gram matrices of matrix- valued NTK K and real-valued NTK respectively. Then, Amin (H) Amiu (H*).
Proof. Denote (UT ..... TT
RdN with By (u)).....,)) Rd Then,
N
N
N
d
d
d H -OO)TH
v. HU =
Heeve =
ΣΣ
1m1
1=1
8
i=1
kml
k=1
1=1
We first assume Amin (H) 2 Ao Let E [d] be fixed and consider e with x 0 for k + Then we have
v He= (v) H To(
which follows Aminn (H*) 2 Ao since v' is arbitrary. Conversely, suppose that Amin(H(i) 2 Ag. For any v, we must have
0 THe
Ho 2 No
Σ (6)) To
Since is arbitrary, can conclude that Amin H 2 An. Therefore, finish the proof.
39


Reviews:
[{"review_id": "vp29Rn8sde", "reviewer": "Reviewer_E1nm", "summary": "This paper studies score estimation using neural networks trained by gradient descent. In particular, they train a two-layer fully connected neural network through gradent descent to learn the score function. To establish a theoretical result, they introduce a parametric form for the score function and connect neural network learning with learning a kernel regression task. They separately upper bound the loss caused by (1) RKHS approximation to the score function, (2) difference between kernel regression and training a neural network. (3) label mismatch.", "questions": "1. Could the authors elaborate a little bit more on why is it reasonable to fix $a$ throught training and only update $W$? In a random feature model $a$ is trained while $W$ is generated randomly. In the NTK regime it is also assumed that $W$ does not change too much during training, hence the problem reduces to fitting a linear model with $a$ representing the coefficients. \n2. Why the authors propose to uniformly sample the time? In practice usually a non-uniform weight function is employed. How does the choice of weight function affect the result. \n3. I feel the most general form of Lemma 3.1 has already been established in many past works. See for example, section 5.1 of https://arxiv.org/pdf/2306.09251.pdf and the intro section of https://arxiv.org/pdf/2309.11420.pdf. I think the authors should at least cite these papers and discuss the relation. \n4. How is $\\gamma$ initialized? \n5. The notation $\\beta_x$ is a bit confusiong. I assume it should not depend on $x$. Maybe the authors can state what does it depend on? \n6. I think Assumption 3.5 is a fact instead of an assumption when the target is bounded, at least when $g$ is a positive constant. This is because taking the gradient of the conditional expectation gives the conditional covaraince, which has bounded operator norm when data is bounded.  \n7. In Theorem 3.6, should I interpret $c_1$ as a universal constant? If not, what does it depend on?\n8. I might have missed something, but I feel the upper bound given in Theorem 3.6 is pretty large. Like it could be much larger than $O(d)$, the scale of the noisy label. Why is it an interesting bound?\n9. In Assumption 3.6 you mean $1 - \\delta (\\Delta, R)$? \n10. There are two delta functions in Assumption 3.7 and 3.8, what are their relation? \n11. I feel the second term in Theorem 3.9 upper bound is huge. If it is not, maybe the authors can comment on it a little bit. \n12. Could the authors elaborate more on why \"Assump- tion 3.11 can be satisfied by an extension of classical early stopping rules for scalar-valued kernel regression.\" Maybe giving an example in which this assumption is satisfied would be helpful for readers to digest.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a framework that gives an end-to-end result for sampling with diffusion model, starting from using GD to learn neural network to score estimation. Their technical idea is highly-nontrivial: They connect GD training of a two-layer NN with kernel regression, and bound each component separately.", "weaknesses": "The paper's presentation is a bit dense and can be improved. Clarifying the dependency of constants and explaining why the assumptions are reasonable would be helpful. In addition, the upper bounds presented in the paper seem far from tight. It is not clear whether these bounds are useful for getting guarantee in specific contexts. Finally, the parametric form this paper proposes does not seem to be novel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cLzMeBdAmW", "reviewer": "Reviewer_zi6V", "summary": "In the paper, the authors analyze the generalization of diffusion models through the lens of Neural Tangent Kernels and their RKHS. Authors derive generalization bounds, universal approximation, and convergence of gradient descent and implications for early-stopping.", "questions": "In Lemma 3.3 bound depends exponentially on dimension d, which makes me wonder -- do we have the curse of dimensionality in those bounds? I guess, R can be varied to improve this dependency but what is final dependency in bounds on dimension? If this is exponential, this will somewhat limit applicability of the results, at least, make them good for low dimension setting but for high-res diffusion models dimension is enormous and, hence, might not be something that explains performance of diffusion models.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Well written with rigorous theoretical analysis, well stated assumotions, showing generalization/convergence of diffusion models, which is rather important area right now, and paper definitely worth attention for such theoretical analysis.", "weaknesses": "1. The curse of dimensionality not discussed. In particular, it is interesting to know for this problem exact dependency of all constants on dimension and discuss this in limitations of the work if exponential dependency is present.\n2. As training procedure considered gradient descent, not stochastic, which limits applicability, as noise for this setup should introduce another dimension dependent factors. But that's minor (and not important as results of the work are interesting by itself)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wo3BmDMjR6", "reviewer": "Reviewer_HzBc", "summary": "The authors analyzed score estimation with neural network parameterization.", "questions": "Can this analysis be extended to other architectures, let’s say, transformers?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a novel design that is a network-based parametrization for score estimation. \nThey tackled three difficulties in traditional supervised learning. \nTheir work built a connection between score matching and regression analysis.", "weaknesses": "This work is mainly limited to theoretical analysis and study of a narrowed case of training on a specific simple network (two-layer FCN) optimized through GD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5COAuDGM17", "reviewer": "Reviewer_NU4S", "summary": "The paper establishes a mathematical framework to analyze the accuracy of score estimation using neural networks trained by gradient descent. It introduces a parametric form for the denoising score-matching problem as a regression problem with noisy labels. The study demonstrates that, with a well-designed neural network, the score function can be accurately approximated, and it provides the first generalization error bounds for learning the score function in the presence of noise in observations.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper addresses a significant question: Can a neural network trained via gradient descent effectively learn the score function? This study has the potential to make a substantial impact on the deep learning community.\n\nThe paper introduces a framework for analyzing the convergence and generalization of neural networks trained using gradient descent for score-based generative models. In particular, the authors investigate the relationship between minimizing the score-matching problem (as defined in equation 5) and training neural networks (as defined in equation 8). The authors demonstrate that, under conditions of overparameterization, where the neural networks are sufficiently wide, minimizing the score-matching problem is equivalent to training the neural networks to directly learn input samples or images, as stated in Theorem 3.9 and Theorem 3.10.", "weaknesses": "1. The analysis strategy and framework presented in this paper do not entirely convince me. The primary contribution lies in establishing a connection between stochastic optimization (as defined in equation 5) and deterministic optimization (as defined in equation 8). Once this connection is made, the convergence and generation results appear as corollaries drawn from existing literature. Additionally, this connection is also not new, as it was proposed in [1].\n2. Building upon the first point, the results concerning convergence and generalization in this paper can be considered incremental, as they rely on NTK-type analysis, which is identical to previous work in the literature and does not introduce novel insights.\n3. However, if one were to directly analyze or train the stochastic optimization in equation 5, the results would likely differ significantly, even when employing NTK-type analysis. This is because, in this case, the NTK would encapsulate randomness arising from the Brownian motion.\n4. It's important to note that this work is purely theoretical and lacks empirical experimentation to validate its assumptions, such as Assumption 3.2, Assumption 3.4, Assumption 3.5, Assumption 3.7, Assumption 3.8, and Assumption 3.11.\n5. The authors categorize errors into four parts: coupling, label mismatch, early stopping, and approximation. Without conducting numerical experiments, it becomes challenging to determine which error contributes the most. As a result, this work does not provide substantial practical insights.\n\n[1]  Learning Lipschitz functions by gd-trained shallow overparameterized ReLU neural networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)