Improved Sample Complexity Bounds For Diffusion Model Training Without Empirical Risk Minimizer Access
Authors: Mudit Gaur
Prashant Trivedi
Sasidhar Kunapuli
Amrit Singh Bedi
Vaneet Aggarwal
Venue: Accepted by TMLR ()

Abstract: Diffusion models have demonstrated state-of-the-art performance across vision, language, and scientific domains. Despite their empirical success, prior theoretical analyses of the sample complexity suffer from poor scaling with input data dimension or rely on unrealistic assumptions such as access to exact empirical risk minimizers. In this work, we provide a principled analysis of score estimation, establishing a sample complexity bound of $\mathcal{O}(\epsilon^{-4})$. Our approach leverages a structured decomposition of the score estimation error into statistical, approximation, and optimization errors, enabling us to eliminate the exponential dependence on neural network parameters that arises in prior analyses. It is the first such result that achieves sample complexity bounds without assuming access to the empirical risk minimizer of score function estimation loss.

Published in Transactions on Machine Learning Research (04/2026)
Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access
Mudit Gaur
mgaur edu
Purdue Universily
Prashant Trivedi
wth iitb.pt@gmail. com
University of Central Florida
Sasidhar Kunapuli Independent Rescorcher
sasidhar sasidhar kanapuli@gmmaillccoo
Amrit. Singh Bedi University of Central Florida
amrithedidtneef.ee
Vaneet Aggarwal
wwncce@ppurduc.. edu
Purdue Universily
Reviewed on OpenReview: https: // openreview. net/ forum? id= CFNNgql9Ov
Abstract
Diffusion models have demonstrated state-of-the-art performance across vision, language, and scientific domains. Despite their empirical success, prior theoretical analyses of the sample complexity suffer from poor scaling with imput data dimension or rely on unrealistic assumptions such access exact empirical risk minimizers. In this work, we provide principled analysis of score cstimation, establishing sample complexity bound of O(c=A). Our approach leverages structured decomposition of the score estimation error into sta- tistical, approximation, and optimization errors, enabling us to eliminate the exponential dependence on neural network parameters that arises prior analyses. It is the first such result that achieves sample complexity bounds without assuming access to the empirical risk minimizer of score fuuncton estimation loss.
1 Introduction
Diffusion models have emerged as a powerful class of generative models, achieving impressive performance across tasks such image synthesis, molecular design, and audio generation. Central the training of these models the estimation of the score function, which characterizes the reverse-time dynamics in the diffusion process. Diffusion models are widely adopted in computer vision and audio generation tasks (Ulhaq &
Akhtar 2022 Bansal el al. 2023). text generation (Li el al. 2022 sequential data modeling (Tashiro el al.
2021), reinforcement learning and control (Zhu et al. 2023). and life sciences (Jing et al. 2022 Malusare
& Aggarwal 2024). For a more comprehensive exposition of applications, we refer readers to survey paper
(Chen et al. 2024).
While diffusion models exhibit strong empirical performance, understanding their sample complexity is essential to guarantee their efficiency, generalization, and scalability, enabling high-quality generation with minimal data in real-world, resource-constrained scenarios. Some of the key works studying the sample complexity are summarized in Table 1 A key limitation of sample complexity analyses of diffusion models done thus far is the lack of the presence of finite-time sample complexity results under reasonable assumptions. This makes the theoretical analysis of diffusion models fall short other machine learning areas such as reinforcement Learning Kumar et al. 2023 Gaur et al. 2024). bi-level-otimmzzaionn
Grazzi et al. 2023

---

Published in Transactions on Machine Learning Research (04/2026)
Sample Complexity
Empirical Risk
Reference
Minimizer Assumption
Zhang et al.
2024
Yes
Wibisono et al. 2024
(--())
Yes
Oko et al.
2023
-ol))
Yes
Chen et al.
2023
-(dd)
Yes
Gupla et a.
2024
9c
Yes
This work
No
Table 1: Summary of sample complexity results for diffussin models, assuming no upper bound on score estimation crror.
2019). In this work we aim to bridge that gap and obtain a sample complexity results on the same footing as results from the aforementioned
Gaur et al. 2025 and graphical models (Fattahi ct al. 2019 Tran ct al.
areas. The iteration complexity or convergence has been studied in Li et al. (002bb); Benton et al. (2024):
Li & Yan (2024); Huang et al. (2026); Dou et al. (2024); Liang et al. 2025a b). while they assune bounded score estimates thus not providing the sample complexity which requires estimating the score function.
We note that works such (Zhang al. 2024 Wibisono et al.] 2024 Oko et al. 2023: Chen al. 2023
have sample complexity results that depend exponentially on the data dimension, making the result less useful in high-dimensional settings. Recently, Gupta et al. (2024) improved upon this by obtaining Ó(E sample complexity without exponential dependence on data dimension. However, this work assumes access to the empirical risk minimizer (ERM) of the score estimation loss, a significant restriction that was explicitly highlighted as an open problem in Gupta el al. (2024) itself. While this assupption is present in all prior works, it is an unrealistic assumption regardless.
In this paper, we do not make these assumptions and establish an improved state-of-the-art sample complexity bound of OO) This represents key step toward bridging the gap between the theory and practice of diffusion models. Specifically, we address the following fundamental question.
How many samples are required for a sufficiently expressive neural network to estimate the score function well enough to generate high-quality samples using a DDPM algorithm??
Our analysis directly connects the quality of the learned score function to the total variation distance wetween the generated and target distributions, offering more interpretable and practically relevant guarantees. Ad- ditionally, our work accounts for the umavailability of the empirical risk minimizer. Using our novel analysis of the score estimation error, we obtain the sample complexity bounds without exponential dependence on the data-dimension. Our principled analysis accounts for the statistical and optimization errors while not assuming access to the empirical risk minimizer of the score estimation loss, and achieves state-of- the-rrt sample complexity bounds.
The statistical error occurs due to the finite sample size used to obtain the score estimate. Existing methods used to bound statistical errors assume bounded loss functions, which is not true in the case of diffusion models. We thus use novel analysis that uses the conditional normality of the score function to obtain upper bounds for the statistical error.
Finally, the optimization error occurs due to a finite number of SGD steps during the estimation the score function. It is precisely the error that was not accounted for the previous works due to the assumption that they have access the empirical risk minimizer. We use the quadratic growth property implied by the Polyal-Lojasiewicz (PL) condition assumed in Assumption 2 and a novel recursive analysis of the error at each stochastic gradient descent (SGD) step to upper bound this error. While the PL assumption is restrictive and not globally applicable, PI. is essentially the weakest standard assumption that yields global convergence rates strong enough to close a finite-sample optimization analysis (Liu et al.) (002)). Our goal is to remove the assumption of access to an empirical risk minimizer and instead provide an explicit, finite-time SGD guarantee that appears as an optimization error term in the three-way decomposition. To achieve this,

---

Published in Transactions on Machine Learning Research (04/2026)
some form of global crror-gradient relationship required. Among commonly used assumptions, the PL inqquality is a canonical and comparatively mild choice: it is compatible with nonconvex landscapes and is significantly weaker than convexity, while still enabling global convergence guarantees for SGD.
The main contributions of our work are sunmarized as:
Finite time sample complexity bounds. We derive state-of-the-art sample complexity bound of O(e=)) for score-based diffusion models, without exponential dependence on the data dimension or neural network parameters. Our analysis avoids the unrealistic assumptions used in prior works such as access to empirical loss minimizer.
Principled error decomposition. We propose structured decomposition of the score estimation error into approximalion, statistical, and oplimization components, enabling the characterization of how each factor contributes to sample complexity.
Tt is to be noted that the sample complexity obtained in our work is exponential with respect to neural network parameters for our work in contrast with works such as (Gupta al.) (024)), where the sample complexity is polynomial with respect to the neural network parameters. We leave for future work results which obtain upper bounds without the ERM assumption which are polynomial in the neural network parameters.
Unconditional and Conditional Diffusion Models. Diffusion models have emerged as leading frame- works across vision, audio, and scientific domains. Foundational works such as Sohl-Dickstein et al. (2015) and Ho et al. (2020) introduced and refined Denoising Diffusion Probabilistic Models (DDPMs), enabling high-quality sample generation. Subsequent advances include improved noise schedules (Nichol & Dhariwal 2021), score-based SDE formulations (Song et al. 2021,, and efficient latent-space generation via Latent Diffusion Models (LDMss) (Rombach et al. 2022). Conditional diffusion models extend these techniques for guided generation tasks, with applications in time-scries (Tashiro et al. 2021), speech (Huang et al. 2022 and medical imaging (Dorjsembe et. al. 2023). Conditioning mechanisms range from classifier-based (Dhari- wal & Nichol 2021) to classifier-free free guidance (Ho Salimans 2022), which enabled text-to-image models
like Imagen (Saharia ct al., (2022) and Stable Diffusion (Rombach al. 2022]. Recent innovations focus
on adaptive control (Castillo et. al. 2025 compositionality (Liu el al. 2023). and multi-modal conditioning
(Avrahami et al.
2022
Despite the empirical success of diffusion models, thcorctical understanding regarding the sample complexity remains limited. Assuming accurate score estimates, authors in (Chen et al. 2022 showed that score-based generative models can efficiently sample from a sub-Gaussian data distribution.
Related Works:
Assuming a bounded score function, iteration complexity bounds have been extensively studied in recent
works Li et al. 2024bb Benton et al. [0244]] Li & Yan 2024 Huang et al., 2026 Dou al. 2024 Liang al. 2025a b). Some works, such as Zhang & Pilanci (2024), establish iteration complexity for score matching,
In particular, (Benton al.) 2024 Li al. 2024b) establishes iteration complexity guarantecs for DDPM
algorithms. Several studies propose accelerated denoising schedules to improve these rates (Li el al. 2024a
Liang et al. 2025b Dou et al. 2024). Additionally, improved convergence rates under low-dimensiona data assumptions are demonstrated in [Li & Yan 2024 Huang et al.] 2026 Liang et al.) 2025a). In contrast to
these works, our analysis addresses the sample complexity of score- based generative models, where the errors introduced by the neural work approximation, data sampling, and optimization are also accounted for.
Sample complexity bounds for diffusion models have been studied via diffusion SDEs under smoothness and spectral assumptions in (Chen et al.) 2023 Zhang et al.) 2024 Wibisono et al. 2024 Oko et al. 2028 However, these bounds are exponential in the data dimension. Further, authors of (Gupta et al. 2024 use the quantile-based approach to get the sample complexity bounds. In this work, we further improve on these guarantecs. The detailed comparison of sample complexities with the key approaches mentioned above is provided in Table

---

Published in Transactions on Machine Learning Research (04/2026)
2 Preliminaries and Problem Formulation
We begin by outlining the thoorctical basis of scorc-based diffusion models. In particular, we adopt the continuous-time stochastic differential equation (SDE) framework, which provides a principled basis for modeling the generative process. We then outline its practical discretization and formally define our problem.
Score-based generative models enable sampling from complex distribution Po by learning to reverse a noise- adding diffusion process. This approach introduces a continuous-time stochastic process that incrementally perturbs the data distribution into a tractable distribution (typically Gaussian), and then seeks to reverse that transformation.
A canonical forward process used in diffusion models is the 2003 defined by the following SDE
(OU) process Oksendal
dx, = x,dt V2dB, 2g ~ Po, R4,
(1)
where B, denotes standard Brownian motion. The solution of this SDE in closed form is given by
It ~ 'x0 20 + V1 e1-e-2te 2- with e~ 10,
(2)
As & + 0o, the process converges to the stationary distribution 1), Let ps denote the marginal distribu- tion of Tt. This defines a continuous-time smoothing of the data distribution, where pr becomes increasingly Gaussian over time.
The reverse process is typically achieved using stochastic time-reversal thoory (Anderson, 1982). which yields corresponding reverse-lime SDE as follows.
dær = (#T-1 + 2 log (ogrr-((FT-)) dt + v2dB,,
33)
where V log (r is known as the score function of the distribution pt. Simulating this reverse process starting from IT ~ Pr R NN I) yields approximate samples from the original distribution po- This motivates a sampling strategy where we begin from zT ~ 1), for sufficiently large T, and then integrate the reverse SDE backward to t using estimated score functions. In practice, the backward process run up fixed time point to known as the early stopping time and not 0. This is done in order to improve performance and training speed (Lyu et al. 2022 Favero al. 2025).
The continuous-tine reverse SDE (Equation is discretized over a finite sequence of times 0 < to < <4 < k) < T. The score function sz(z) := V log (x is approximated at these discrete
... ...tk... ....... ... < tk= = (T x)) points using a learned estimator 8t,- This discretization underlies the DDPM framework (Ho et al. 2020). where the reverse process is implemented by iteratively denoising the sample using the estimated scores at each time step. The detailed procedure provided in Algorithm [ the Appendix We employ stochastic gradient descent (SGD) to learn the score function at each th, using either a constant learning rate, justified in our analysis later.
Problem formulation: Let the score function at time l. be approximated using a parameterized family of neural networks F = {se : E Ok}, where each sp IRd x [0, + Hd is represented by a neural network of depth D and width W with smooth activation functions. Given n& i.i.d. samples {or)e_ from the data dist risuttition Pte the score network trained by minimizing the following loss:
(x) == Eerpe, [[]s0(z, tx) - V log (x)
(4)
Objective. Our goal is to quantify how well the learned generative model Pr. approximates the true data distribution p in terms of total variation (TV) distance. Specifically, we aim to show the number of samples needed so that with high probability, the TV distance (Pt. is bounded by O(e), where is the L estimation error of the score function. This reduces the generative performance analysis to establishing tight sample complexity bounds on the score estimation error. We additionally define the following probability

---

Published in Transactions on Machine Learning Research (04/2026)
distributions:
Pto = Distribution obtained after backward process till time to steps starting form pr
Pto Distribution obtained by backward process till time to starting from pr at discrelized time steps
Pto = Distribution obtained by backward process till time to starting from PT at discretized time steps using the estimated score functions
Pto = Distribution obtained by backward process till time to starting from N(0, T) discretized time steps using the estimated score functions where ln denotes the early stopping time.
3 Sample Complexity of Diffusion Models
In this section, we derive explicit sample complexity bounds for iiffusion-basedd generative models. By leveraging tools from stochastic optimization and statistical learning theory, we provide bounds on the num- ber of data samples required to accurately estimate the time-dependent score function 8x(x) == V log px(x) across the forward diffusion process. Note that accurate score estimation is critical for ensuring high-quality generation while sampling through the reverso-time SDE.
We first stale the assumptions required throughout this work.
Assumption 1 (Bounded Second Moment Data Distribution.). The data distribution po of the data variable To has an absobutely conlinuous CDF, is supported on a continuous T TRdd, and there erists constant Ci < oc such that [E( [oo I C1.
Works such as Guptt et al. 2024
Wibisono et al. 2024 also assume second bounded moment
2024 assumess a sub-gaussian assumption while works such (Chen et al., Oko et al. 2023). assume that the data distribution is supported on bounded set, thereby excluding commonly encountered distributions such as Gaussian and sub-Gaussian families. In contrast, our analysis only requires the data distribution to have a finite second moment, making our results applicable to a significantly broader class of distributions. Note that the works that assume sub-Gaussian assumption or bounded assumption are able account for the error incurred due a finite stopping time, while works such (Gupta al.] 2024) and this work do not. In this work, we show that if assume sub-Gaussian data distribution, can also account for the error due to finite stopping time.
have done here. (Zhang et al.
2022
Assumption 2 (Polyak Eojasiewicz (PL) condition.). The loss (x( for all k E [0, K] salisfies the Lojasiewiz condition, (.e., there ezists constant μ > O such that
) 2 (
VOEO
(5)
where 0* = arg mingee, (()) denotes the global minimizer of the population loss.
The Lolsiwi-ooasiewiiz (PL) condition is significantly weaker than strong convexity and is known to hold in many non-convex settings, including overparameterized noural networks trained with mcan squared error losses (Liu et al., 2022). Prior works such as (Gupta el al.
2024) and (Block et al., 2020) implicitly assume access to an exact empirical risk minimizer (ERM) for score function estimation, as reflected their sample complexity analyses (see Assumption A2 in (Gupta et al.
2024 and the definition of ff in Theorem 13 of (Block et al. ). This assumption, however, introduces a major limitation for practical implementations, where exact ERM is not attainable.
In contrast, the PL condition allows to derive sample complexity bounds under realistic optimization dynamics, without requiring exact ERM solutions. To our knowledge, this is the first theoretical analysis of score-based generative models that explicitly accounts for inexact optimization, addressing a key gap in existing literature. Additionally, we establish convergence guarantees with both constant and decreasing step sizes.

---

Published in Transactions on Machine Learning Research (04/2026)
Assumption (Approximation error of the Class of Neural Networks). For all E [0,T], there crists neural network porameter 0 O₂ such that
E Ba Bp-polls0(x, (x,
V log (cx))()) S Capprox
(6)
This error is independent of the sampling algorithm, and describes the error due to neural network parametrization. In learning theory, it is common to treat the approzimation error of a model class as constant so that analyzos can focus the cstimation/ optimization terms dependent the sample. This convention appears in standard excess-risk decompositions for fixed hypothesis classes (Shalev-Shwartz & Ben-Davie 2014). Tn PAC-Bayesian analyses, approximation errors are denoted by constant once the class is fixed [Mai] 2025p. In (NTK/RKHS) analyses of neural networks, where it is assumed the target function lies in, or is well approximated by the specified function class, the misspecification error is represented as a constant term (Bing et al.) 2025)- In reinforcement learning algorithm analysis such as policy gradient, task-dependent "inherent Bellman" or dunction-approximation error that remains constant while deriving performance rates (Mondal & Aggarwal 2024 Fu et al., 2021 Gaur et al.) 2024 Ganesh al. 2025). Note that in Gupta et al. (2024), Assumption A.2 states that the error in estimating the loss function is 'suffi- ciently small' In practice, this assumption is used to make the score function estimation error arbitrarily small, as is done in Theorem C.3, where it is stated that the there exists a neural network such that the error in estimating the loss function is O(e2). Thus, this is a stronger assumption as compared to our Assumption
Note that in certain works, such as (Jiao al. 2023), is shown that the network size has to be exponential in data dimension in order achieve a small approximation error. However, in practice, that would require impractically large neural network size. In practice neural network size is of the same order the data dimension. Thus for a fixed neural network size that we assume in this work, it makes sense to assume the approximation error as a constant.
Assumption (Smoothness and bounded gradient variance of the score loss.). For all E K], the population loss (0) is k-smooth with respect to the paramelers 0, i.e., for all 0, 0' E O2
[VCx - (L')l') S x|10- 0'11-
(7)
We assume that the estimators of the gradients V,, (0) have bounded variance.
V (0) (0)l
(8)
Together, these assumptions form minimal yet sufficient foundation for analyzing score estimation in practice. Smoothness and bounded gradient variance implied by the sub-Gaussian assumption are mild and generally satisficd for standard neural architectures such as GELU activations. The PL condition has been shown to emerge in over- parameterize networks or under lazy training regimes, where the function class is expressive enough to approximate the ground-truth score function (Liu et al. 2022).. Notably, these conditions are not only specific our setting they have been widely adopted in recent works studying the
optimization landscape of deep diffusion models (Salimans & Ho 2022 Liu et al. 2022 Note that in no prior works were such assumptions stated since they assumed access to the empirical risk minimizer.
It is to be noted that assumptions 2 3 and 4 are not included in prior works, since they assumed access to the ERM. Since we do not make that assumption, these additional assumptions are needed for oblaining upper bounds on the Total variation between the true and generated distributions.
Theorem 1 (Total Variation Distance Bound). Let Pt, denote the distribution obtained by the backward process till time to storting form pr, and Pr, (I:) be the distribution generated by the backward process at discretized time steps {t+}, starting from (0, using the estimated score functions š (x) where k E []. Let d be the dala dimension, and ny be the namber of samples for score estimation at time step 4x-
Assume that the data distribution satisfies Assumption the loss function (0) satisfies Assumptions for all l e [0, K] and the leorning rate for estimating (0) using SGD satisfies S 17 S x for all E 0. Further assume
(W2D (W2D..2..0g 2. log
4K 8
n&k = S
(9)
ox

---

Theorem D establishes that the total variation distance between the true data distribution and the diffuusion model's output be made arbitrarily small specifically, (cc) by properly scaling model capacity and algorithmic parameters. To the best of our knowledge, these are the only known sample complexity bounds Published in Transactions on Machine Learning Research (04/2026)
Then, with probability at least 8, the total variation distance between the Pto and Pro satisfies
1
( T + log +) + Capprox
< O(exp (0expp7)+ 0
0
(10)
VK
Furthermore, by setting T 52 (log (t)), = St(E) and K = S2(( 2), we obtain
TV(Pto: ) S O(c) + Capproz.
(11)
with probability at least 1 6.
for score-based diffusion models, improving upon the prior results discussed in the introduction without assuriin access to empirical risk minimizer for the score estimation loss.
Usage of Pto instead of Po in Theorem 1 We have shown that the estimated distribution Pto is O(e)- close in total variation (TV) to Pto where Pt, denotes the data distribution Po pushed forward by to steps of the forward process. We do not claim that ft, is ((e)-close in TV the true data distribution po (i.e., do not bound TV Pt,)), because doing would require additional assumptions Po- For example, Fu ct al. (2024) (in Lemma D.5) assumes a sub-Gaussian data distribution to show that TV(Po,Pta S ( log, 1/to)). We also note that all other works listed in Table 1 similarly provide upper bounds on TV Pto), not on TV(po.Pt.).
However, it is to noted that using the sub-Gaussian assumption, our analyis can extended to a bound TV Pio) via the triangle inequality:
TV & TV(po Pro)) + TV Pro).
We formally present the data assumption and the resulting theorem as follows
Assumption 5 SSub-Gaussian Data Distribution.). The data distribution po of the data variable To has absolulely continuous CDF, is supported a conlinuous set I E IRd, and there erists consland 0 < C2 < do
such that for every t 2 0 have P( 2 f) 2 exp
Theorem 2 (Total Variation Distance Bound Under Sub-Gaussian Assumption). Assume that the data distribution satisfies Assumption 5 the loss function (f) satisfies Assumptions 2 for all le E K] and the learning rate satisfies for estimating (0) using SGD satísfies 0 S for all k [0, Further assume
n& (W2D 2..DD.2.1..
d2. log ((K)
(=)))
(12)
or
Then, with probobility at least 1 8, the total variation distance between the and Pro satisfies
TV Pro) s O (otto log( l/to)) -(exp="))++++ +0 1
VK
(0(c./(T+118))
T log 1)) +0 10(c.1/
c.
+ Capprar
(13)
n.
Furthermore, by setting to = =((2), , T (log (2)) n = and K = S2(c-2) we obtain
(V((o,PPe)) x(e)) Eapproz:
(14)
with probability at least 1- 6.

---

Published in Transactions on Machine Learning Research (04/2026)
Proof of Theorem 1
Recall that Pro is derived via score-based sampling, using the triangle inequality repeatedly to decompose the TV distance between the true distribution Pto and Pto obtain
Tp Peo) - (p p + TV(p Pto)) + TV Pto)
(15)
The bounds on (V PPo and (Ptt,, (to) follow from Lemma B.4 of Guppa el al. 2024 and Proposition of (Benton et al. 2024). respectively to get
")
1 V
(P Pro) 5
+ TV(p') Pt.)) + O(exp(-T))
(16)
Note that we have used results from Gupta et al. 2024 and (Benton et al. 2024 which assume a bounded
second moment for the data distribution. This is satisfied by Assumption Now from lemma 4 TV Pt.) is upper bounded as follows
1
TV(p% dis Pho Expr,, |6 (x, tx) V log Pte (z)]l (tx)1 - tx)
(17)
In order upper bound TV Pto); we denote A(k) as
A(k) == Exnpie ||0t, (2r (x) - V log (x)]l²
(18)
Therefore, bounding the TV distance between Pt, and Pro translates to bounding the cunulative error in estimating the score function at different time steps. We now focus on bounding this term. Specifically, we have that
1 V
TV(p 5
A(k) (x) O(exp(-T)) k=
(19)
2
Now, for each time step k, we decompose the total score estimation error, denoted by A(k), into three primary components: approximation error, statistical error, and optimization error. Each of these error corresponds to a distinct aspect of learning the reverse-time score function a diffusion model as described below.
Exwpyr [18rr (x,
(x) (x,12) log (c))1²] 4 (w) |11l (x, (x) log (x)
E
cappiox
E Euwnyr (x) [1 (x, tx) s/ (ac, t+)
Exiar
E Exxppy (x) [1|sr (I, si (I,th)ll
(20)
gopt

---

Published in Transactions on Machine Learning Research (04/2026)
where, we define the parameters
0% arg min Ez Exape, AE
(1) (x)
V (xr
(21)
0% arg min 71
|5 tw) V tw)
(22)
and denole Sig and s as the estimated score functions associated with the parameters of and 0% respectively. Approzimation error &k Eapprox captures the error due to the limited expressiveness of the function class {so teee- The statistical error ex is the error from using a finite sample size. Finally, the optimization error Exp is due to not reaching the global minimum during training.
One of our key contributions lies in rigorously bounding each of these error components and showing how their interplay governs the overall generative error. In particular, we derive novel bounds that explicitly capture the dependencies on sample size, neural network capacity, and optimization parameters, without any assumption
the access to the empirical risk minimizer of the score estimation loss. We formalize
these results in the following lemmas. Detailed proofs are deferred to Appendices C.1. and C.2 respectively. Eupprox is defined as follows
Lemma 1 (Approximation Error). Ek
eapprox
mingge [[|so(z, tx) V log (2,(22)))11
(23)
c
Then, under Assumplion for all [0, K], we have
&k
capprox
Capproa
(24)
This result directly follows from Assumption and the definition of & capprox
Lemma (Statistical Error). Let ny denole the number of samples used to estimate the score function at time step tg. If the data distribution satisfies the Assumption and the loss function (x( satisfies Assumptions 2 for all is E [0, K], then with probability at least 8, we have
00 (WWW
log
Ek
-d.
(25)
n2k
Proof Outline We present the outline of the proof, full details are deferred to the Appendix.
(') = Ennpey |1vo(2, tx)) Nea (x))1
(26)
and
('x(0)) 1 Σ |1o (x) Uea (x::))1
(27)
Thus, we have
((02) Cx(OR) S Ca((%) (x()) + Ex(0)) - Ex(0))
(28)
We get the incquality by adding the term [(0g) Z(OB) to the right hand side of Equation 28 this is a positive quantity since 0 is the minimizer of L()), where the added term is non-negative due to the empirical optimality of oz.
Cx (02) C(0 < ((OO) Z(0g)
(((0)) Z(0g)
(29)
(I)
(1I)

---

Published in Transactions on Machine Learning Research (04/2026)
Now, note that the terms (I) and (II) are unbounded, and thus gencralization results such Lemma
(Theorem 26.5 of (Shalev-Swwarzz Ben-David 2014)), do not apply directly. Thus we define two
supplementary loss functions
L0) Errper (v((ttt)) u4a (x))1?
(30)
and
('x(0) 1 n
Σ
110 tx) 2/2 (x:))12
(31)
where we define the functions
(V (oogp(())))
if -
(vr()));
of
(32)
0
2
and
(vo(x;()); (sa(z, t))
---
S KK
(33)
p-c mn 2
Here (o((z)),(Vlloggp) (z)) ())(z,t),, and (so(e, t)), denote the jth co-ordinate of ve(2), (V log pa (x)). vo(x; and sa(x, 1) respectively. Further, -= denotes the jth co-ordinate of the 7th sample of the of score function in (0) which is given by log = 1 mma
Note that the functions (0) and (0) are bounded and thus the result from 5 (hherem 26.5 of (Shalev- Shwartz & Ben-David] 2014)) are applicable. Additionally, we bound the error due to the truncation in function given the initial data
the terms (0) and (0) using the conditional normality of the distribution as well bounded second moment of the initial data distribution. This is the component of the error that accounts for the fact that we have finite sample size and thus we solve empirical loss function given in (21h. The proof of this lemma follows from utilizing the definitions of sf and s² Existing analyses of statistical errors, such as those given in (Shalev-Shwartz & Ben- 2014), only work when the loss function bounded. This is not the case for diflusion models. Thus, we use novel analysis that uses the conditional normality of the score function as well the bounded second moment property of the data variable in Assumption D to obtain the upper bound on the statistical error. The details of the proof are given in Appendix C.1
Lemma 3 (Optimization Error). Let ng be the number of samples used to estimate the score function at time step lu- Assume that the score loss function (0) satisfies the Assumptions 3 and for all E [0, K], and the learning rate for estimating Lk using SGD satisfies S S 1. then with probebility at least - 5
W.D. (WD.de.
log (2) T&k
copt <0
(34)
Proof Outline
We study mini-batch SGD on the population loss La
(i) L-smoothness, (ii) the (PL) condition with constant μe, and (iii) unbiased mini-batch gradients with variance scaling as - The algorithm
b; bi
0 0, 28-n19 ng..
(35)
j=1
10

---

Published in Transactions on Machine Learning Research (04/2026)
with constant step size 1) S L and increasing batch size b, [.3.].
The proof starts from the smoothness (descent) inequality applied to the stochastic update:
(=(0++)) v( + Lij² 19:1
(36)
Taking conditional expectation given 0,, unbiasedness yields (0)) 9i) |0,] = [VV and the mini- batch variance bound implics 1199.12 0.] < |VV2x + o² /b,b.. Using 1 S 1/L to simplify constants, we obtain the one-step recursion
Lni²²²
(0++1) [i] S (1 mu) [O.) Li] +
(37)
2b;
where the PL condition converts ( into multiple of (x(0,) C Unrolling this recursion yields geometric "optimization" term plus "noise" term:
T-1 (Cx(Or) - 47) (1 mu) T- A + E1- mp) 7
LIPo²
A1 := [Cx(()) - 2x]-
(38)
2b,
t=1
The incrcasing batch schedule b, = [[tt] makes the variance term decay like 1/t; the geometric weights ensure the sum is bounded by constant multiple of 1/T, giving
(c(()) C2 s (1 mn) AI + O
1 T
(39)
Finally, if n Σf= by denotes the total number of samples, then b; i implies n O(T²) and hence 1/T 011 (n). Substituting this relation yields the stated sample- cample-based convergence rate
[Cx Li] S1 - (1--n))-iA, 0
=0 - -
(40)
and in the large-n regime the geometric transient negligible, giving (OT) L = O(n -1/2). We use the quadratic growth inequality and the result of Lemma 3 get the final result. The details of the analysis are given in Appendix C.2
Combining the decomposition in Eq. 20 along with Lemmas (defined in Eq. 18) with probability at least 1 -
3
obtain the following bound A(k)
log 2 Tik
log (
A(k) 5
W. d
+o WD wD.dd
d
+ Capprox
(41)
n2k
log
50
WD-d
+ Capprozi
(42)
11kk
where the second inequality we combine the first two terms appropriately. Setting the sample size
nuk Ω ( d2 log²
4K
(43)
we ensure that A(k) < 2 probability at least
o² 1-e शग- for all 1: E (0. K). Summing over all time steps, we obtain with
11

---

Published in Transactions on Machine Learning Research (04/2026)
K A(k)(ta+1 - (x)
K
2²
S
Σ
(fx+1 tx)
(44)
1
2(T
0=
k=0
T T-x
e---2(T-)) dl S 2² ( -
e²
(45)
Note that the term (log² (4)) appears in the upper bound for ny in Eq. (43) since we have to take union bound for Lemma 2 and Lemmn 3 and then take a union bound over K discrelization steps. Substituting this bound into Eq. and then substituting the result into Eq. 166. we obtain that with probability at least 1 6.
(12) VK
(+ (T+ log 22
(P S O(exp-() +
+0
(e.V
+ Capprox
(46)
Finally, by choosing T = 12 (log (2) A = 2(() and = ()(c we conclude that with probability at least
1-8 8
TV P(o) s O(e) + capproz:
(47)
completing the proof of Theorem
summary, our work provides principled decomposition of the errors in score-based generative models, highlighting how each component contributes to the overall sample complexity. This leads to the first finite sample complexity bound of ((e-t) for diffusion models without assuming access to the empirical minimizer of the score estimation function.
4 Conclusion and Future Work
In this work, investigate the sample complexity of training diffusion models via score estimation using neural networks. We derive sample complexity bound of O(e=)), which, to knowledge, is the first such result that does not assume access to empirical risk minimizer of the score estimation loss. Notably, our bound does not depend exponentially on the number of neural network parameters. For comparison, the best-known existing result achieves a bound of Ō(E-5) but crucially assumes access to an ERM. All prior results establishing sample complexity bounds for diffusion models have made this assumption. Our contribution is the first establish a sample complexity bound for diffusion models under the more realistic setting where exact. access to empirical risk minimizer of the score estimation loss is not available.
We note that although this work focuses continuous data distributions, subsequent work has established a 3 sample complexity for discrete-state diffusion models in (Srikanth et al. 2026). Whether an analogous ( sample complexity is achievable for continuous diffusson models remains open, although such result has recently been established for rectified flow matching in (Sahoo et al. 2026
12

---

Published in Transactions on Machine Learning Research (04/2026)
References
Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications,
12(3):313-326, 1982.
Omri Avrahami, Dani Lischinski, and Ohad Fried. Blended diffusion for text-driven editing of natural images. CVPR, 2022.
Arpit Bansal, Hong-Min Chu, Avi Schwarzschild, Soumyadip Sengupta, Micah Goldblum, Jonas Gciping, and Tom Goldstein. Universal guidance for diffussin models. In Proceedings of the IEEE/CVP Conference on Computer Vision and Pottern Recognition, pp. 843 852, 2023.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly SdS-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learn- ing Representations, 2024.
Xin Bing, Xin He, and Chao Wang. Kernel ridge regression with predicted feature inputs and applications to fastor-basod nonparametric regression. arXiv preprint arXiv:2505.2003 2025.
Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative modeling with denoising auto-cncoders and langevin sampling, arXiv preprint arXiv:2002.01007 2020.
Olivier Bousquet, Stéphanc Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer school on machine learning, pp. 169 207. Springer, 2003.
Angela Castillo, Jonas Kohler, Juan C Pérez, Juan Pablo Pérez, Albert Pumarola, Bernard Ghanem, Pablo Arbeláez, and Ali Thabet. Adaptive guidance: Training-free acceleration of conditional diffusion models. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pp. 1962-1970, 2025.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and dis- tribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning, pp. 4672-4712. PMLR, 2023.
Minshuo Chen, Song Mei, Jianqing Fan, and Mengdi Wang. An overview of diffusion models: Applications, guided generation, statistical rates and optimization. arXiv preprint arXiv:244,007711, 2024.
Sitan Chen, Sinho Chowi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as casy as learning the score: theory for diffusion models with minimal data assumptions. In NewrIPS 2022 Workshop on Score-Based Methods, 2022.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. In Adoances in Newral Information Processing Systems, volume 34, pp. 8780-8790 8794, 2021.
Zolnamar Dorjsembe, Hsing-Kun Pao, Sodtavilan Odonchimed, and Furen Xiao. Conditional diffusion models for semantic 3d medical image synthesis. imaging, 19:20, 2023.
Zehao Dou, Minshuo Chen, Mengdi Wang, and Zhuoran Yang. Theory of consistency diffusion models; Distribution estimation meets fast sampling. In Forty-first International Conference on Machine Learning, 2024.
Salar Fattahi, Richard Y. Zhang, and Somaych Sojoudi. Lincar-time algorithm for learning largo-scale sparse graphical models. IEEE Access, 7:12658 12672, 2019. doi: 10.1109 ACCESS. 2018 2018.8890583.
Alessandro Favero, Antonio Sclocchi, and Matthieu Wyart. Bigger isn't always memorizing: Early stopping overparameterized diffusion models. arXio preprint 1t::25055119999 2025.
Hengyu Fu, Zhuoran Yang, Mengdi Wang, and Minshuo Chen. Unveil conditional diffusson models with classifier-free guidance: A sharp statistical theory. arXiv preprint orXiv:2403. 11968, 2024.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy, In International Conference on Learning Representations, 2021.
13

---

Published in Transactions on Machine Learning Research (04/2026)
Swetha Ganesh, Washim Uddin Mondal, and Vancet Aggarwal. A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach. In Forty-second International Conference Machine Learning, 2025.
Mudit Gaur, Amrit Bedi, Di Wang, and Vaneet Aggarwal. Closing the gap: Achicving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization. In Interna- tional Conference on Machine Learning, pp. 15153-15179. PMLR, 2024.
Mudit Gaur, Utsav Singh, Amrit Singh Bedi, Raghu Pasupathy, and Vaneet Aggarwal. On the sample complexity bounds of bilevel reinforcement learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Research, 24(167):1-37, 2023.
Shivam Gupta, Aditya Parulekar, Eric Price, and Zhiyang Xun. Improved sample complexity bounds for diffusion model training. In The eightt- Annual Conference on Neural Information Processing Systems (updaled version at #rXi::2311.137555 Nov 2025), 2024.
Jonathan Ho and Tim Salimans. Classifier-free diffusion guidance. arXiv preprinl orxv::2077115000 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6857 2020.
Rongjie Huang, Max WY Lam, Jun Wang, Dan Su, Dong Yu, Yi Ren, and Zhou Zhao. Fastdiff: A fast conditional diffusion model for high-quality speech synthesis. arXiv preprint arXiv: 099944 2022.
Zhihan Huang, Yuting Wei, and Yuxin Chen. Denoising diffusson probabilistic models are optimally adaptive to unknown low dimensionality. Mathematics of Operations Research, 2026.
Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonparametric regression approximate manifolds: Nonasymptotic error bounds with polynomial prefactors. The Annals of Statistics, 51 (2): 691-716, 2023.
Bowen Jing, Gabriele Corso, Jeffrey Chang, Regina Barzilay, and Tommi Jaakkola. Torsional diffusson for molecular conformer generation. Advances in neural information processing systems, 35:24240-2445 2022.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, 112(7):2433 2467, 2023.
Gen Li and Yuling Yan. Adapting to unknown low-dimensional structures score-based diffusson models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yucjic Chi, and Yuxin Chen. Accelcrating convergence of score-based diffusion models, provably. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 27942 27954, 21-27 Jul 2024a.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408. 02320, 2024b.
Xiang Li, John Thickstun, Ishaan Gulrajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion-Im improves controllable text generation. Advances in neural information processing systems, 35:4328-444 4343, 2022.
14

---

Published in Transactions on Machine Learning Research (04/2026)
Jiadong Liang, Zhihan Huang, and Yuxin Chen. now-dimeniional adaptation of diffusion models: Conver- gence in total variation. In The Thirty Eighth Annual Conference on Learning Theory, pp. 3723 3723-3729. PMLR, 2025a.
Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Broadening target distributions for accelerated diffusion models via a novel analysis approach. In The Thirteenth International Conference on Learning Represenlations, 2025b.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterizee non- linear systems and neural networks. Applied and Computational Hormonic Analysis, 59:85-116, 2022.
Xihui Liu, Dong Huk Park, Samaneh Azadi, Gong Zhang, Arman Chopikyan, Yuxiao Hu, Humphrey Shi, Anna Rohrbach, and Trevor Darrell. More control for free! image synthesis with semantic diffusion guidance. In Proceedings of the IEEE/CVI winter conference on applications of compuler vision, pp. 289 299, 2023.
Zhaoyang Lyu, Xudong Xu, Ceyuan Yang, Dahua Lin, and Bo Dai. Accelerating diffusion models via early stop of the diffusion process, arXiv preprint 220.2225511224, 2022.
The Tien Mai. Pac-bayesian risk bounds for fully connected deep neural network with gaussian priors. arXiv preprint ar Xiv:2250.. 04341, 2025.
Aditya Malusare and Vaneet Aggarwal. Improving molecule generation and drug discovery with a knowledge-
enhanced generative model. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2024.
Washim U Mondal and Vaneet Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general paramcterization for infinite horizon discounted reward markov decision processes. In International Conference on Artificial Intelligence and Statistics, pp. 3097 3105. PMLR, 2024.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. International conference on machine learning, pp. 8162-877 8171. PMT.R, 2021.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution ostimators. In International Conference on Machine Learning, pp. 26517-26582. PMLR, 2023.
Bernt Øksendal. Stochastic differential equations. Springer, 2003.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10684-10695, 2022.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Bureu Karagol Ayan, Tim Salimans, et al. Photorealistic text- to-image diffusion models with deep language understanding. Advances in neural information processing systems, 35:36479 36494, 2022.
Hari Krishna Sahoo, Mudit Gaur, and Vancet Aggarwal. Order-optimal sample complexity of rectified flows. arXiv preprinl N.i:26011222555 2026.
Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. In International Conference on Learning Representations, 2022.
Shai Shalev-Shwarz and Shai Bev-David. Understanding machine learning: From theory to algorithmss. Cambridge university press, 2014.
Jascha Sohl-Dickstein, Eric A Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pp. 2256-2265, PMLR, 2015.
15

---

Published in Transactions on Machine Learning Research (04/2026)
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
Aadithya Srikanth, Mudit Gaur, and Vaneet Aggarwal. Discrete state diffusion models: A sample complexity perspective. The 29th International Conference on Artificial Intelligence and Statistics, 2026.
Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. Csdi: Conditional score-based diffusion models for probabilistic time series imputation. Advances in newrol information processing systems, 34: 14804-24816, 2021.
Nguyen Tran, Oleksii Abramenko, and Alexander Jung. On the sample complexity of graphical model selection from non-stationary samples. IEEE Transactions Signal Processing, 68:17-32, 2019.
Anwaar Ulhaq and Naveed Akhtar. Efficient diffusion models for vision: A survey. arXiv preprint arXi::2210.09202 2022.
Andre Wibisono, Yihong Wu, and Kaylee Yingxi Yang. Optimal score estimation via empirical bayes smoothing. The Thirty Seventh Annual Conference on Learning Theory, pp. 4958 4991. PMLR, 2024.
Fangzhao Zhang and Mert Pilanci. Analyzing neural network-based generative diffusion models through convex optimization, 2024. URL https://arxiv.. http:///wwwrrrab//./0000000
Kaihong Zhang, Heqi Yin, Feng Liang, and Jingbo Liu. Minimax optimality of scsre-based diffusion mod- cls: Beyond the density lower bound assumptions. In Forty-first International Conference on Machine Learning, 2024.
Zhengbang Zhu, Hanye Zhao, Haoran He, Yichao Zhong, Shenyu Zhang, Haoquan Guo, Tingting Chen, and Weinan Zhang. Diffusion models for reinforcement learning: survey, arXiv preprint 0rXw::331..01223, 2023.
16

---

Published in Transactions on Machine Learning Research (04/2026)
A Note about (Gupta et al., 2024)
We note that the comparison in this paper uses the results from the updated arXiv version of their work (in Nov 2025), which incorporates a correction to an error identified in the earlier version of our work (available at arXiv).
B Score Estimation Algorithm
In this section, we provide a detailed description of the algorithm used for estimating the score function in diffusion models.
Algorithm Denoising Diffusion Probabilistic Model (DDPM)
1: Input: Dataset D, timesteps T, stop time lstop; schedule (3:)==1 network ea, learning rate n, iterations K
Precompute: a₂ = 3r, a = IT.=1 as
Training (Score Estimation)
for i- to N do
Sample zj D, k ~ U1i, ~ N(O, 1) for i= I....,
5: Iτ, = = 24 + vI e 25
6: Compute loss: [(0) = ||,; co 1:)l12
7: Update + nh (o
end for
Sampling
Sample 2T N/0 T)
10: for T down ksopp + 1 do
11:
N(0, if > 1 else 0
12: ê = (2( t)
13: iu = vor
8
14: = The + VBe..
15: end for
16: Return Ftoto
C Proofs of Intermediate Lemmas
In this section, we present the proofs of intermediate lemmas used to bound the statistical error and opti- mization error in our analysis.
C.1 Bounding the Statistical Error
Proof. Let us define the population loss at time ty for & E [0, K] as
(x) Rappi, (1 4)) V Vlogpt, (x)
(48)
where se denotes the score function estimated by a neural network parameterized by 8, and x denotes samples at time used in Algorithm The corresponding empirical loss defined as:
(x) Σ
[ tx) V log (x:)
(49)
17

---

Published in Transactions on Machine Learning Research (04/2026)
Let o% and 2 be the minimizers of (x) and (0), respectively, corresponding to score functions s% and
i.. By the definitions of minimizers, we can write
(0 (02) - (0%) (x(( Ex( (0() v (a() 2.(0%) + (x(( (0
(50)
(51)
(1)
(1I)
Note that the right-hand side of 50 is greater than the left-handeft-hand side since we have added the quantity (, which is strictly positive since 0 is the minimizer of the function (0) by definition.
We then take the absolute value on both sides of the (51) to get
We now bound terms (I) and (II) using generalization results. From Lemma (Theorem 26.5 of (Shalev- Shwartz & Band-David 2014)), if the loss function Σ(0) is uniformly bounded over the parameter space
9" = 10% 0. then with probability at least - ô, we have
[L((0) -2(0))2((6)) s sR(e")+ +0 ( log 1
+0
AAEA"
(52)
where R(O") denotes the empirical Rademacher complexity of the function class restricted O". Now since is not bounded, this result does not hold. We then define the following two functions
L' (0) Encpe, [Ivo(z,ta) tx) Utc (x)]1
(53)
and
('x(0)= 1 Σ 11o(s;, (x) Utg (3::)11
(54)
where we define the functions
(vr(z)),
(V log po
if 2- 1
of
S K
(55)
0
o?
2
and
(so(2, ())
if -----ia
S
(vo(x, ());
(56)
0
2 K
Here (v((z)),,,Vloog))) (z))) (vo(I, t)), and (sa(x, t)), denote the jth co-ordinate of vx(x,, (V log (x))))
vo(x, 1) and s0 t) respectively. Further, 1 denotes the jth co-ordinate of the ith sample of the score function in (0) which is given by logp.(x) - of
Note that the functions ve(x) and vo( are uniformly bounded. Thus using Theorem 26.5 of Shalev- Shwartz & Ben-Davvd 2014) we have with probability at least 8,
(1 log 1
('x(0) - ['((0) < R(0)+
VOEG".
(57)
Since e" (0,,6,} a finite class (just two functions). We can apply Lemma E.5 to bound the empirical Rademacher complexity R((0) in terms of the Rademacher complexity R(A) of the function class O" Since R(()) E Imax E f(8)a:], applying Lemma E.5, we have with probability at least 1 - 26
d. WD O log 1
C'x(0) ['x(0)] s 1
(58)
n
18

---

Published in Transactions on Machine Learning Research (04/2026)
This yields that with probability least 8 have
log 5
-0x(0)-''x(0 5o d- L.WD
V
VDE@"
(59)
n
From this have
[[=2(00) [n(0)]| 0o d
log 3
(60)
Now consider the probability of the event
F4 - ---e((mm (xo); 2 K
Ar, =
(61)
of
Where
z:-e (zali
denotes the hth co-ordinate of of the th sample of the score function given by
0²
(2a):
We have the probability of this event upper bounded as
I₁
I, 2 xn
P
2 k
E.P
2 K xo
(62)
o
1
$ cxp
(-12 - -1))
(63)
exp
(-n²²
(64)
We get 63 from
62
since the score variable is conditionally normal given To-
Setting x log
dn
we have
5
P
2 S dn
(65)
o
If we denote the event A = (i(( = [(0)}, then by union bound we have P(A) P(Us,AAs)) 5 Eig P(Acs) & 6. Let event. B denote the failure of the generalization bound, i.e.,
log n
(C,(0)--.10) R((") +
(66)
From above, we know P(B) S under the boundedness condition. Therefore, by the union bound, we have
P)AUB) < P(A) - P(B) < 26, P(A B = P(AU B) 2 1 25.
(67)
(68)
19

---

Published in Transactions on Machine Learning Research (04/2026)
On this event (A9 n B²), we have (' Ž(0). Hence, with probability least 26, we have
[cx(0%) (x()) < (b() (10)
(x((f) E,(
(69)
Lx (02) (', (o((f) (2)
(70)
(02) - (0))
+ (02) - C'x(0
+ F (0%) - (0))
+ (A((2) (2,(0%)
(71)
log 1
- (09) - (0)) + (c,(()) - (. + +0
d W.D
(72)
n
In order bound [cx(0) [')( we have the following
-c) - (')
Ex ( ((s((x,t))) ((so0t) (Vlogpr, (x)) Ex ((rr(x))) (vo(x, t))1
(73)
Ery (
(VVlogm.) (x,t1)
(74)
j=1
- t(ooss
2x
(x
E Eny (wea)
(s)
(75)
1=1
- (xxo)
ze
2
x - e (xo)
2
E Exy (ume)
1
of
j=1
(sp)
2x
d
2E my (ue))
(so(x, t))31
(76)
j=1
x- (xxo)
2R
I - e (x00)
<
E B
1
j=1
2x
d
(vo)
Co" C Eg Eurn((urc)
(77)
o²
(mg)
1=1
20

---

Published in Transactions on Machine Learning Research (04/2026)
4
2C
d
$
Be (wrs))
|0r/
o,²
k=1
[pp)
2x
2 Beys(un)))
|xol31
(78)
x--- ((ra)
2R
We get Equation 76 from Equation
75
by using the identity (a b)2 < 2/a/2 + 2|6 We get Equation
77 from Equation 76 by using Lemma
We get Equation (78) from Equation 77) by using the identity
a b)2
< 2/a|2 + 2 b again. Now we separately obtain upper bounds for the terms and I/ as follows.
Exg ~ (s
10,1211
(79)
j=1
?
(co))
2x
E (
12
(80)
i=1
- Kang o7
2x
Ezz E (1rg)s10
|
(81)
2x
d
(mn)s
E E (me)al
|z 1
1
P
(82)
of
1=1
zy-o teoll
2x
d Σ
< Sexp (-x²)
Exg (uon( 10 |
(83)
j=l
xe-o Cxagls
2x
d
S Sexp (-x?²
Eyg
of + o
(84)
1 (1)
h=1
d
exp
(-x²)
Eg (2.0
(85)
k=1
0 eexp (-x²))
(86)
We get Equation
84 from Equation 83 by using Lemma 7 We get Equation 866 from Equation
85
from Assumption and by using the upper bound on the Mill's ration which implies that ((K)
S K
[-)(R)
21

---

Published in Transactions on Machine Learning Research (04/2026)
We get Equation 86 from Equation
85
from Assumption which implics that the second moment of
is bounded.
E Be (urels
|0l/11
(87)
1=1
2x
d
E Brg (urla
|
(88)
j=
mame Mopll
2x
d
Egz (ux))l)
|
(89)
j=1
2
d
Ik tzk
Exg E (
|
P
2 ki x
(90)
-
j=1
of
d
- exp (-x²2
Σ
Ezzo 12r01
(91)
==1
0 (exp (-x?))
(92)
Setting N. = log da 3 Plugging Equation
861
922
into Equation
78
Then we have
(Q) C' 30 (exp (-x²)),
v0 100, 0%)
(93)
6
00
(94)
dn
Now plugging Equation
93
into Equation
72
we get with probability at least 1 1-24 25
log
(x(()) (x(0)) 50 d. WD.
(95)
n
Finally, using the Polyal--.ojaseewicz (PL.) condition for (x), from Assumption we have from the quadratic growth condition of PL functions the following,
| 0/11 < Cx((%) -x
(96)
22

---

Published in Transactions on Machine Learning Research (04/2026)
and applying Lipschitz continuity of the velocity fields with respect to parameter x
|1 (x) - / (I,, 1x)l < L 110 - -2/11
(97)
S L / Cx(()) - (x(l
(98)
log N/
0 d. WD
(99)
Here L, is the Lipschitz parameter of the neural networks. It is always possible to obtain this Lipschitz constant as the quantity (x, - (xx I I is non-zero only over finite domain of x. Taking
expectation with respect to H, we obtain the following.
B (x, - s (xr (x)l & 2B 11 (1, 0 (z,
( (x) (f(x)) - (x))
+ 2
11 (x, (x) (x, 12)1
(100)
- 4E BEzwa,
11 (Ix (6,) (x, (x1
(101)
1 Exxme
11 (2x, (x) (x, 111l
+ 4E [1, - (x))1
(102)
log B
S 00(s 2) +
d- WD
(103)
S 0 8 ) + +0
1 B log
d. d.
(104)
dn
log
S d. WD_
(105)
n
and 4E [1(((x) of [x)]] are This completes the proof. Note that the quantities 4E Alg (2)) (2) bounded in the same manner is done in Equation 192
C.2 Bounding Optimization Error
The optimization error (Eopt) accounts for the fact that gradient-based optimization does not necessarily find the optimal parameters due to limited steps, local minima, or suboptimal learning rates. This can be bounded as follows.
Proof. By L-smoothness with 0.41 = 0; -19i
Ln² 11..112.
1(0(+1) S C(O.) - (VC()). g.)
Taking conditional expectation given 0, and using unbiasedness,
E(VC(())..) |0.] 1
Moreover,
E El11911 0.] [[IV + ( - 0.]
= [ E(l VC(,) 0.]
< [V 6,"
23

---

Published in Transactions on Machine Learning Research (04/2026)
Combining the last three displays,
Lif
(1V o²
B[C(0++1) 00.] S ((0:) =l
2
b;
Rearranging and using S 1 (so that 17 Ln²
2 ž 1/2),
B[C(0:+1) 0.] < (())) VC(0))1 + Lnfo
26;
Subtracting L and applying the PL inequality |V 2 2p(((0)) L** yields
(c(0)) - --) + Ln²²0²
B[c(0(+1) - 10: (1-
2b;
Taking total expectation gives the recursion
LnRo²
A+t S (1 ))))
(106)
2bg
Let = 10--14 nu E (0, 1) and choose the increasing batch size schedule
b [Bi]] for some constant >>0 0.
Unrolling 106 for i i= 1....,T T 1 gives
T-1
Lifo² 02
AT S p
D
+
T
(107)
26:
1=1
Since b. 2 Bl, we bound
T-1
T-1
Σ t=1
p
T 1-t
<
1
b
3
1=1
Let T 5o
= and k
0, 0,1...., T 2.
Then
T-1-1
1
1
<
k
T-1
T
7p
km
k=0
Plugging this into
107 yields
Lnda² 1
Lnd²
AT <
p
T
(108)
B
qp T-1
233μ
T
Thus, the suboptimality decays as O(1/T) up to a transient geometric term:
1 -
E[c(Or) L*] S (1 - m)) + o
Let denote the total number of samples used up to iteration T:
T
Σ
b
1=1
With b; [Bi], we have the crude lower bound
T
BT(T +
3T
9i
2
2
i=1
24

---

Published in Transactions on Machine Learning Research (04/2026)
hence
2 T
= o
I
2
T-1 1
Bn.
Substituting this into 108 gives
) + o
( -
[[((Or) - L1] S (1
(in
In particular, for sufficiently large (so the transient term is negligible),
B[((0r) o
Vn
Note that St, and & denote our estimate of the loss function and associated parameter obtained from the SGD. Also note that L the loss function correspouding whose minimizer is the neural network sf, and the neural parameter 0% is our estimated score parameter. Thus applying the quadratic growth inequality.
|| (x,ta) si. (z. tx) < L. -211 < II[C(0)) C*]l
(109)
1 vn
(110)
From lemma 2 we have with probability 1 - that
|| (x, tx) - s/ (I, tx)l < L.1107 - -1:12
(111)
s L.4 Lx (B+) (8%))
(112)
log
I 0 d WDD
(113)
n
Thus we have with probability at least 1 -
(1,, (x) - (x 1x)1 < 8/ (x,, (x)
5% (x, 1x)1 + 2. 11,, (ar, (x)
26 (x. 4x)l
(114)
)
1 11
log 3
0 log
+
d
(115)
log 2
<0
d WD
(116)
(117)
Taking expectation with respect to x Pts on both sides completes the proof.
D Intermediate Lemmas
Lemma 4 (TV bound via Girsanov for reverse diffusions). Let X and X on [0,T]] solve dX, (f(X,, t) o (t)s, (Xt, dt (t)) dW,,
dx (
t) + a(t) dW,
with the same nondegenerate diffusion (t) E Idxa (invertible for a.e. t) and the same initial law at time T. Let and Q be the path measures of X and & on C(, Assume Novikou's 's condition
Be Sgepp l (10())(0((())))) (X,,)) (x,, ()),))) <c.
25

---

Published in Transactions on Machine Learning Research (04/2026)
Then
1/2
1 TV(P, Q $ 2
Eo l (1(0))s((80,)) (x(e,t))) dt
Proof.
Write the drift difference as
Abx, -o2((((s(tt 8p (2 (2,
By Girsanov's 's theorem (under the stated Novikov condition), P < Q and the Radon -Nikodym derivative is the exponential martingale driven by u = att) Ab((x,,) = ((t)(s)()1 Martin formula yiclds
s. (X,, t)). The Cameron
L/
1
Be LT (o(0)((((xx))) s. (X., 1)112 dt
QL(PIIQ) - IE
|url2 de
Applying Pinsker's inequality TV(P, Q) S (KI(PIQQ) gives
1/2
1 1
Eg / |1a(0(00-s.))1)))) -s)]
- 2 TV(P,Q)
Finally, the evaluation map C((0, 77, Rd) divergences, CV(C(X)), S TV(P, Q)
Rd w + w(0), measurable, so by data processing for ʃ-
Let {ax and { be Euler schemes with the same Gaussian noises,
COoVAt rk-1 2k + (fx s. (x) At + oR aoVAt, At Ex. it-1 = ãn + (fx (FS +oov Atx Ek.
&x ~NO,1 iid. Then, with "traj" denoting trajectory measures,
N E (0o(so((xttt)) (x) - (xxx 12) Atx
KL trajo) 2
A=1
and hence by Pinsker's inequality we get.
N
1
TV(traj,, $ 2 ox - s1)112 Atk
Σ
Lemma 5 (Theorem 26.5 of (Shalev-Shwartz Shwartz & Ben- David 2014 ). Consider data E Z, the parametrized
hypothesis class hg, E O, and the loss function E(h, 2) R.a R, where (e(h, S c. We also define the following terms
LD(h) 2)(h,))
(118)
Ls(h)
Σ
8(h,2) 2))
(119)
m ES
which denote the expected and empirical loss functions respectively,
Then,
26

---

Published in Transactions on Machine Learning Research (04/2026)
With probability of at least 1 6, for all H,
2 2lm(4
(D(h) Ls(h) s ( 4oy m
(120)
where 2R(e θ 8) denotes the empirical Radamacher complerity over the loss function &, hypothesis pa- rometer set θ ond the dalaset S Lemma (Extewnsion of Massart's Lemma Bousquee et al. 2003 ) Let @" be a finite function class.
Then, for any E O", we have
(o+ d+ d+
L W
Eg
max
1(0),,
S 11((0))222 S (BW)²
(121)
"E0"
We get the second inequality by denoting L as the number of layers in the neural network, W and B constant such all parometers of the neural network upper bounded by B.
where o; are i.i.d random variables such that P(o, = 1) P(o; -1) z.
Proof. Let ho = and for l= 0,... L define the layer recursion
het1 (Wehe be),
where We E IR be E RR and ne I W for hidden layers. We work with the foo operator norm:
|| = max Ei())el s Bre S BW =a.
Since a is 1-Lipschitz with (0) 0, we have (l( I ||u|oo and thus
| < Wello lieell + libello S a hellellle + B.
With I/oolloc d, iterating this affine recursion yields the standard geometric-series bound
L-1 a and + B
- a-1
at-1 (a + 1),
| S a'd + B
1=0
and for a a= l/be|>> s d+ BL. The scalar output fa) is either coordinate of h2 or obtained by applying the same 1-Lipschitz activation to a linear form of h1; in either case, [f()) < ||hr,lo,, giving the stated bound.
For the a 2 simplification, use Σlel a' s Lab-11 to obtain
If(z) & a BLa = (BW) d+ L.
For < 1, since a² < E a' s L and hence 1f(x)] < d BL. Finally, substituting W = S/L gives the size-based form
If(z)) & (BS/L)" d+ (a=
I,2 s
Lemma 7 (Second Moment of a Symmetrically Truncated Normal). Let X ~ N(H, and let a > 0. Then the second moment of X conditioned on being outside the symmetric interval l1t a, + a) is given by
$ al 2² 0 oa 1 $
E|X² | X
where d(z) 1 is the standard normal probability density function (PDF), and ((2) is the standard /2a normal cumulative distribution function (CDF).
27

---

Published in Transactions on Machine Learning Research (04/2026)
Proof. Let X o(p, We aim compute the second moment of X conditioned on the event that lies outside an interval centered its mean
B|x21XX u1| a)
This represents the expected squared value of X, given that is in the tails of the distribution (i.c., more than a units away from the mean). By definition, the conditional expectation is
E[X2 1 1|x -1 P[[ - 11 > a)
E[X²
| |X - M a)
The numerator integrates X over the tail regions (-o0, 1 a) (u a, 00), while the denominator is the probability mass in those regions.
To simplify the integrals, we standardize X. Define the standard normal variable
X p 2
1) = x=u+o2
Define g. Then
-
& >
Our conditional second moment bocomes
E[x²
X
14] 1 a] E[(u+
+ |Z|
Expanding the square inside the expectation
(n + 02)0 = 1²2 + +uo + 2z
Taking the conditional expectation
Ei(4 + oZ)² [Z] a] - 2 2 |Z| > a) + e 112 > aj
Since the standard normal distribution is symmetric and the region Z > a is also symmetric, we have
2 1 a] =0
Thus, the expression simplifies to
X
XX ul al = + 12 > a)
By definition
J11 220(2) dz P(Z a)
2 2
f 220(2) dz
E Z Z a)
2(1 ((a))
1 ((a())
Using Intergration by Parts we get,
28

---

Published in Transactions on Machine Learning Research (04/2026)
Jo =0 =(a)))==
Therefore
E[Z² 11 a) Maja + 1 4(a)
aσ(aa) {()))
1 (a)
Substitute back into the expression for E[X² X - 14| > a]
1+ (1+ aσ(a)
E[x² | X - μ > dj = = +0²
4(a))
Recall that 3, the final expression becomes
o (()
E[x² ||x - 11 > a) = 12 + 0a
1 4 (#)
Lemma 8 (Linear Growth of Finite Neural Networks). Let Se Rd - R be the output of a feedforward neuraa nelwork with fonile number of layers and parameters and E θ where has a fivile nemmber of elements. Suppose that each activation function o R2 IK satisfies the growth condition
|o())] S A B|2,, for all E.
for constants A, B 2 0. Then there erists a constant Ce > 0 such that for all x E Rdd,
[s(x] < (1 + ||=]])
Proof. We proceed by induction on the number of layers in the network.
Base case: One-layer network. Let the network be single-layer function
[(x) = Σ a: (w, + b:).
where wi Rd, by E R, and E R. Then
[f(x)]
Σ
aasl lo( x + 6.)l.
1=1
Using the growth condition on a, we get
(o by)l < A+ Blw, x + bal s A B(I [|||=| (bcl).
Hence
&
If(x)) < | (A B(I + (b,)) = C. + C1 C1 ||]||
where Co. C1 are constants depending only on the network parameters. Therefore
[f(x)] s C(1 + ||=||) with C' max(Co, Ct}.
29

---

Published in Transactions on Machine Learning Research (04/2026)
Inductive step. Assume the result holds for all networks with layers, i.c,, for any such network fz)
[f(())] S Cr(1 + [x]]))
Now consider a network with L + 1 layers, defined by
[++1(x)= = = (0 (z)),
5=1
where each f (x) is an output of depth-L subnetwork. By the inductive hypothesis
(x))
Applying the activation bound
Io( A+ A I|x]))
Then
(f++(()) < Σ layl 105 0) (x)) (2)))))) - Σ
C1+1 + ||=])),
j=1
==1
for some constant C141 > 0. This completes the induction.
Examples of Valid Activation Functions
The condition |a(=)] < A + B|2| holds for most common activations
ReLU: (2) = max(0 (0, 2) - [x(2) S |
Leaky ReLU: bounded by linear function of [2]
Tanh: bounded by + A 1, =
Sigmoid: bounded by 1
30


Reviews:
[{"review_id": "ekb6Hva8DE", "reviewer": "Reviewer_xBMb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the sample complexity of learning a diffusion model under a PL condition, which is claimed to be a weaker form of convexity, rather than access to an empirical risk minimizer (ERM) as assumed by previous works. Under this assumption, it achieves a $O(\\epsilon^{-4})$  bound, which improves upon the $O(\\epsilon^{-5})$ from previous works", "claims_and_evidence_yn": "Yes", "claims_explanation": "This paper points out an error from Gupta et al (2024) which I appreciate -- it does seem that the paper reports the wrong bound in the simplified theorem in the main body of the paper -- however, it's also the case that if one just directly plugs in the bound on $K$\n stated in Theorem C.2 into the bound in equation (35), one recovers the correct $O(\\epsilon^{-5})$\n bound. Moreover, the main contribution of Gupta et al (2024) was to improve on the dependence on the Wasserstein error and dependence on depth of the neural network -- the dependence on $\\epsilon$ was not a focus.\n\nI also like that this paper does attempt to circumvent the need for ERM access assumed in previous works. The improvement in the $\\epsilon$ dependence as a result of the new PL assumption is interesting.\n\nHowever, I have a number of concerns, highlighted in future responses.", "audience_yn": "Yes", "audience_explanation": "The paper addresses a fundamental problem in diffusion models.", "requested_changes": "The PL assumption still seems quite strong -- it only seems to apply to local convergence for overparameterized neural networks, which is still a very restrictive setting. In general, the paper suffers from overselling its contributions -- it's not as though the authors are able to remove the (admittedly unrealistic) ERM access assumption altogether -- it is simply replaced with a different unrealistic assumption, that likely also does not hold in practice.\n\nThe flaw pointed out in Gupta et al (2024) is not stated with appropriate context -- it's the case Theorem C.5 as stated is correct, the error only appears in the simplified theorem statement.\n\nMoreover, unlike the polynomial dependence in Gupta et al (2024), this paper has an exponential dependence on the depth of the neural network.\n\nThere are several typos in the paper, and the presentation in general is quite poor. For instance, Assumption 1 is a second moment assumption on the data distribution, but immediately after, the authors say \"In contrast, our analysis only requires the data distribution to be sub-Gaussian, making our results applicable to a significantly broader class of distributions.\" which is much stronger than a second moment assumption.\n\nOverall, this paper has the potential to be a good contribution, but is not yet ready for publication in my opinion.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oV2sxEg7tF", "reviewer": "Reviewer_uAqs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The contributions of the paper are threefold:\n- Provides a finite-sample sample complexity bound for diffusion/DDPM training via score estimation that targets TV error between the generated distribution and the (early-stopped) forward-noised data distribution, improving the reported scaling to $\\mathcal{O}\\left(\\epsilon^{-4}\\right)$ (plus approximation error) without assuming access to an empirical risk minimizer (ERM). \n- Introduces a three-way decomposition of score estimation error into approximation, statistical, and optimization terms, and claims to bound each under (i) bounded second moment of data, (ii) a PL condition for the score loss, and (iii) smoothness + bounded gradient noise for SGD;\n- Re-analyzes prior work (notably Gupta et al.) and argues their claimed $\\mathcal{O}\\left(\\epsilon^{-3}\\right)$ effectively becomes $\\mathcal{O}\\left(\\epsilon^{-5}\\right)$ after accounting for accumulation/union bounds across discretization steps.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims appear to be supported, but I have some questions/comments before giving a positive answer to this question. \n\nWhile the overall proof structure is reasonable, the main $\\widetilde{O}(\\varepsilon^{-4})$ sample complexity claim is not fully clear for me. \n\nThe reduction of total variation error to a weighted sum of per-time score errors,\n$$\n\\sum_{k=1}^K \\frac{E_k}{\\sigma_k^2} \\;\\lesssim\\; \\varepsilon^2,\n$$\nis standard and sound. However, some key issues perhaps remain:\n\n- Optimization error:  \nThe optimization error bound\n$$\nE_k^{\\mathrm{opt}} \\;\\lesssim\\; W D d \\sqrt{\\frac{\\log(1/\\delta)}{n_k}}\n$$\nis derived under a PL condition but does not clearly account for the finite number of SGD iterations. Standard PL-based analyses depend explicitly on the iteration count $T$, which is not reflected in the final bounds.\n\n- Parameter dependence:  \nThe per-time error bounds scale as $W D d$, while the main theorem requires\n$$\nn_k = \\Omega\\!\\left(\nW^2 D \\, d^2 \\log\\!\\left(\\frac{K}{\\delta}\\right)\n\\varepsilon^{-4}\n\\sigma_k^{-4}\n\\right).\n$$\nThe apparent mismatch in depth dependence (missing a factor of $D$) is not explained.\n\n- Statistical analysis and assumptions:  \nThe statistical error argument relies on truncation and conditional Gaussianity but is difficult to verify as written. In addition, assuming a PL condition for each time-indexed loss $L_k(\\theta)$ is strong for realistic diffusion models, and the approximation error $\\varepsilon_{\\mathrm{approx}}$ is left uncontrolled.\n\nI would appreciate if the authors could clarify so that I can answer the question positively.\n\n*Edit: after the authors response, I am confident and validating the correctness of the paper and updated the answer to the question above to \"Yes\". Thank you.", "audience_yn": "Yes", "audience_explanation": "The paper addresses questions that are directly relevant to the theory-oriented portion of the TMLR audience, particularly researchers working on diffusion models, non-asymptotic generalization bounds, and optimization-aware learning theory. All topics that are of extreme interest right now. The attempt to remove the empirical risk minimization assumption and to analyze finite-time stochastic gradient descent in terms of total variation distance is timely and of clear theoretical interest.", "requested_changes": "My requested changes are mostly very technical and relate to the first question, of correctness:\n- Make the optimization analysis explicitly finite-time by stating the required number of SGD iterations per time step and incorporating this dependence into the final bounds.\n- Reconcile the dependence on network width $W$, depth $D$, and dimension $d$ between the per-time error bounds and the main sample complexity result.\n- Clarify and streamline the statistical error analysis, including precise definitions of truncation and a clear connection to the actual score-matching objective.\n- Clearly state whether the theory assumes separate models for each time step or a single time-conditioned network, and explain how the results extend to the shared-network setting.\n- Tighten the comparison with prior work by explicitly matching assumptions and carefully qualifying claims about improved rates.\n\nIt is relevant that some misunderstanding from my part is clarified or that some things are corrected / added of clarification.", "broader_impact_concerns": "This work is purely theoretical and does not introduce new modeling capabilities or deployment mechanisms. As such, it has no immediate societal impact. Any broader impact is indirect and stems from improved theoretical understanding of diffusion models, which may contribute to both beneficial applications and general dual-use risks associated with generative models. So the paper itself does not raise specific new ethical or safety concerns.", "additional_comments": "The distinction between bounding $\\mathrm{TV}(\\hat p_{t_0}, p_{t_0})$ and $\\mathrm{TV}(\\hat p_{t_0}, p_0)$ is important and is handled appropriately. However, the paper in general could perhaps benefit from a bit clearer exposition, more consistent notation, and tighter bookkeeping of constants and parameter dependencies. Improving readability, especially in the appendices, would help verifying the technical claims.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Cpjo3r8wte", "reviewer": "Reviewer_3dyA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work essentially provides a theoretical analysis of the error committed by diffusion models trained with score estimation. To my understanding, the main contribution of this work is to provide a similar bound to previous works regarding sample complexity ($\\mathcal{O}(\\epsilon^{-4})$ instead of the $\\mathcal{O}(\\epsilon^{-5})$ of previous works, where $\\epsilon$ is the total variation between real and estimated distributions) while relaxing the set of assumptions made. Most importantly, the authors only need to assume that the data distribution has bounded variance (instead of bounded domain) and do not need to assume access to a minimizer of the empirical risk. The paper is generally well-written and the proofs well explained (I have only looked at some of them, I didn't proof-read everything). While I miss some empirical confirmation of the theoretical results, these represent a step towards more realistic set of assumptions to what it was previously known and therefore a worthy contribution to the field.", "claims_and_evidence_yn": "Yes", "claims_explanation": "As I said above, the paper is in general really clearly written and even an outsider to the field like me can follow it up without many issues. While I would need to read every demonstration in details, the ones I have looked seem rather simple (in a good way) and clearly explained, which encourage me to lean towards trusting the theoretical results presented in the main pages of this submission.\n\nOnce again, I think the paper would greatly benefit of a small but convincing experiment (or existing results taken from previous works if computational budget is an issue) showing that indeed the sample complexity bound given in this paper holds in practice.", "audience_yn": "Yes", "audience_explanation": "Yes, diffusion models are still a hot topic in ML research and the theoretical understanding on the number of samples required to get a good approximation is of interest to the community.", "requested_changes": "I would request from the authors to make a deeper pass on the manuscript to polish notation and make it consistent across all pages (maybe using LaTeX macros?), as it can become distracting. For one example, in Eq. 18 it is defined as $A(k)$ but literally in the next equation the same is written as $A_k$. Similarly, I believe the dots in Eq. 25 and others are meant to be $\\cdot$ (`\\cdot`). Or in the problem formulation, it is defined $n_k$ but used $n$ right after.\n\nMoreover, I believe the $dx$ in Eq. 18 should be removed and the $(t_{k+1} - t_k)$ is wrongly duplicated in Eq. 19.\nIn the same spirit, I could spot some typos (\"establishes\" instead of \"establish\" in the related work, or \"so that analyzes\" instead of \"analyses\"). \n\nFinally, there are some notation and terms that would required further clarification. For example, $D$ is never introduced in the main text, and in the proof of Lemma 4 I would appreciate it if there were some references to the 3 different theorem and conditions thrown in the same paragraph.\n\nRegarding some empirical results, I think they would strengthen the paper significantly, but I do not consider them necessary for acceptance.", "broader_impact_concerns": "I do not think that there are any ethical concerns to consider in this particular work.", "additional_comments": "_Disclaimer:_ This is not my field and I am not familiar with the literature. My review is based on what it is shared by the authors and the limited literature review I have done during this review. I have looked superficially at some of the proofs but I have certainly not proof-read the appendices.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)