Dimension-free Score Matching and Time Bootstrapping for Diffusion Models
Authors: Syamantak Kumar
Dheeraj Mysore Nagaraj
Purnamrita Sarkar
Venue: NeurIPS 2025 poster ()
Keywords: Diffusion Models
Score Matching
Empirical Risk Minimization
Generalization
Markov Chain
Learning from Markov Dependent Data
Primary area: theory

Abstract: Diffusion models generate samples by estimating the score function of the target distribution at various noise levels. The model is trained using samples drawn from the target distribution, progressively adding noise. Previous sample complexity bounds have a polynomial dependence on the dimension $d$, apart from $\log({|\mathcal{H}|})$, where $\mathcal{H}$ is the hypothesis class. In this work, we establish the first (nearly) dimension-free sample complexity bounds, modulo any dependence due to $\log( |\mathcal{H}|)$, for learning these score functions, achieving a double exponential improvement in dimension over prior results. A key aspect of our analysis is to use a single function approximator to jointly estimate scores across noise levels, a critical feature in practice which enables generalization across timesteps. We introduce a novel martingale-based error decomposition and sharp variance bounds, enabling efficient learning from dependent data generated by Markov processes, which may be of independent interest. Building on these insights, we propose Bootstrapped Score Matching (BSM), a variance reduction technique that utilizes previously learned scores to improve accuracy at higher noise levels. These results provide crucial insights into the efficiency and effectiveness of diffusion models for generative modeling.

Dimension-free Score Matching and Time Bootstrapping for Diffusion Models
Syamantak Kumar" University of Texas at Austin syamantak@utexas.o edu
Dheeraj Nagaraj Google DeepMind
jheerajaaggraa@@oogleecoo com
Purnamrita Sarkar
University of Texas at Austin purna. sarkarSutera edu
Abstract
Diffusion models generate samples by estimating the score function of the target distribution at various noise levels. The model trained using samples drawn from the target distribution, progressively adding noise. Previous sample com- plexity bounds have a polynomial dependence on the dimension d, apart from log ()H(). where H is the hypothesis class. In this work, we establish the first (nearly) dimension-free sample complexity bounds, modulo any dependence due log({H)). for learning these score functions, achieving double exponential improvement in dimension over prior results. A key aspect of our analysis is to use a single function approximator to jointly estimate scores across noise levels, a critical feature in practice which enables generalization across timesteps. We introduce novel martingale- enabling efficient learning from dependent data generated by Markov processes, which may be of independent interest. Building on these insights, we propose Bootstrapped Score Matching (BSM), variance reduction technique that utilizes previously learned scores to improve accuracy at higher noise levels. These results provide crucial insights into the efficiency and effectiveness of diffusion models for generative modeling.
еггог decomposition and sharp variance bounds,
Introduction
Score-based diffusion models video generation 38
43 are generative models that have transformed image and 36.. enabling foundation models to produce photorealistic and stylized images from text prompts. Their adaptability extends diverse domains such as audio 24 I0], text
40
37
13
15
29 49] molecule [18 19,, and layout generation [1 28 They generate additional samples
given i.i.d. samples from target distribution (T)) using trained neural network that learns the score function at different noise levels. In contrast, the classical Markov Chain Monte Carlo (MCMC) methods which seek to sample from distribution given access to underlying density function. While MCMC methods can be slow for multi-modal distributions, diffusion models can sample efficiently with minimal assumptions, provided the score functions are learned accurately [6] [..
Given m i.i.d. samples from the target distribution, the first step (called the forward process) obtains noised samples from a noising Markov process converging to the Gaussian distribution at various noise levels. The second step estimates score functions of the distribution at each noise level using Denoising Score Matching (DSM) [5T]. This approach relies on learning from dependent data from
Work partly done during internship at Google DeepMind
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

multiple trajectories of a Markov process in contrast to learning with i..d. data in traditional settings. Prior works 3 provide theoretical guarantees for score function approximation separately at each noise level using the same samples. However, in practice, single function approximator is commonly used at all noise levels, which is considered by [16]. (4] show that despite the problem of distribution estimation suffering from the curse of dimensionality [5] 351, the existence of low-dimensions structures allows neural networks to learn the score functions. All of these existing bounds exhibit polynomial dependence on the dimension, d. We establish that under suitable smoothness conditions for a given function class, score matching with a single function approximator jointly across all timesteps achieves nearly dimension-free sample complexity that depends the smoothness parameter and grows only as log log(d).
1.1 Our Contributions
(1) We analyze the sample complexity of denoising score matching across noise levels using single function approximator, achieving a double-exponential reduction in dimension dependence.
(2) We present a novel martingale decomposition of the error, which allows us bound the error despite being composed of samples from multiple trajectories of dependent data.
(3) We use second-order Tweedie-type formulae to obtain a sharp bound on the error variance, crucial for establishing almost dimension-free convergence rates.
(4) Inspired by the above, we present Rootstrapped Score Matching. Here the score at a given noise level is learned by bootstrapping the learned score function lower noise level, achieving variance reduction. This shows improved performance compared to DSM in simple empirical studies.
1.2 Related work
Score matching and diffusion models: Score Matching was introduced in the context of statistical estimation in (20) with algorithm now called Implicit Score Matching (ISM). Diffusion models are trained using Denoising Score Matching (DSM) introduced in [5T], and is based on Tweedie's s formula. Several algorithms have been introduced since, such as Sliced Score Matching [44] and
Target Score Matching 77]. Prior works have analyzed the complexity of Denoising Score Matching in various settings (5 35 14 3 [2). We consider the setting in [14 3 where the score functions of the given distribution can be accurately approximated by a function approximator class (ex: neural networks), instead of the worst case parameerri analysis in
[12.. These bounds then be used 6 27 to guarantee the quality of the generated samples.
with the discretization analyses in
Learning from dependent data: Learning with data from a markov trajectory has been explored in literature in the context of system identification, time series forecasting and reinforcement learning
26 46 Many of these works analyze the rates of convergence with data derived from mixing Markov chain, when the number of data points available is much higher than the mixing time, Tmik- In our context, the Markov chain contains mTTixx data points created by progressively noising samples from the target distributions, where Ô hides logarithmic factors. This similar to the setting in 48), which considered linear regression and linear system identification.
8 42 34
25 48 53
2 Problem setup and preliminaries
Notation: We use [r]] to denote (i E N i n)). I Rddd represents the d-dimensional identity matrix. We use ((a, Σ) to denote the multivariate normal distribution with specified mean, / and covariance matrix Σ. I|-ll, denotes the la euclidean norm for vectors and II-Ilop denotes the operator norm for matrices. E [X] denotes the expectation of the random variable X and Cov(X) denotes its covariance matrix. For b E I. we write S b if and only if there exists an absolute constant C' > 0 such that a < Cb. Ô, Å represent order notations with logarithmic factors. We also define a coarser notion of subGaussianity used subsequently in our proof sketch,
Definition 1 ((32, -ubbuuuaussiianytty A mean-zero random variable Y is said be (B2 K)-
subGaussian if satisfies IP( (Y| > A) < K exp( 28z
A²

---

process: Consider a target distribution over R., Suppose a and 2t solve the following Stochastic Differential Equation (SDE):
dr. = -tddt + v2dB,,
(I)
where B₁ is the standard Brownian Motion over R An application of Ito's formula demonstrates that 2, Zhe + where 2 ~ (0, of1) is independent of zo and o, vI-e e- This is the forward noising process, which progressively noises the initial sample into a standard Gaussian vector. Ito's formula also relates Lt; Zy for any timesteps / > 2 0 to obtain, It = Tre
- (t-t') + 2 where Z,,-" (f II is independent of zy and 0=-a' = v1 - e 2t-8), Fort [0. 7). let Pr be the probability density function of Tt. Given in ~ pr and standard Rd Brownian motion B, then the denoising process is:
dā. = E, + 2V Pog + v2dB,
is the time reversal of the noising process which implies ïy ~ π
Score matching: Given i.i.d. data points x(1), ....,,((m) from the target distribution æ. diffusion models learn the score function stt, x):: :R+ R x Rd + Rd defined as s(t, = st (α) == V log pt (x)
..... x!m)
via denoising score matching (DSM). Tweedie's formula states that
(1, = R[ |[ oी [
(3)
Let H be a finite class of functions which map R+ x Rd to Rd with functions (1,x) + ffffe (t, =
fo (x). Let T {t......tt .NN S []. Let z! denote the solution of Equation TT at time t with
00 = =x() = and define 2/ = zt - e (x(() We consider the joint DSM objective to be:
m
(() MN
Σ LET
f(t
(4)
Thus, optimizing is a regression task with noisy labels. The two sources of error are: i) By (3). while / _t = s (t), o is noisy conditioned on and ii) æ; Pe itself is random. The empirical risk minimizer is defined as f = arg inf sew L(ʃ). The results established in I states that the error in sampling arising from using the estimated score function f is given by:
B.wp. [llf(t..)) s(t,, 2)113] where y; == t ti-1
(5)
Our goal is to bound this error. For simplicity, consider 4 iA for some step size A (0, 1).
3 Main results
We operate under the following smoothness assumption the function class, H. Assumption 1 (Smoothness of function class). Let the true score function, E H.
0. log is continuously differentiable for every L R
1. Lipschitzness: : For all t E T,, 21, 22 E Rd, f E H: llf f(t, 12) 1 || x2l
2. Local Time Regularity: There exists a set Bs,, such that Pe (Bs,)) 2 1 1 8, Vt 2 T
Ba Vf E H.
(0000) |le (t- f(t,2) e x2) S e S - 1") log(
Assumption (1) is a standard Lipschitz continuity assumption followed in the literature (see e.g. Assumption (2) assumes Hölder continuity with respect to the time variable. This is natural assumption because Lemma 10 shows that Assumption [-1 implies Assumption [ for the true score
WWe note that our results generalize to time-varying Lipschitz parameter L(t). This lets us replace the worst case Lipschitz constant its time-averaged variant.
3

---

function, s(t, We also note that the assumption s E H. can be relaxed to assume that 38 E H. with sufficiently small &g error, similar to [14. While we assume a finite function class, H. we can extend it to infinite classes by standard covering argument in learning theory or consider H to be the finite class of floating point quantized models such neural networks.
Equation (I demonstrates that 2; forms a Markov chain, leading to the noise random variables,
2,, being dependent. Additionally, ①I is typically iterated for 7 = Ō [mixx) timesteps, until pr close gaussian distribution. This setup falls outside the scope of conventional analyses of learning from dependent data (see Section 1.2). Such analyses usually assume a significantly larger number of datapoints. where datapoints separated by Tmix in time are approximately independent, and the convergence rates align with their i.i.d. counterparts, adjusted for an effective sample size reduced by a factor of Tmix In contrast, our setting involves substantially fewer datapoints. To address this challenge, we propose novel martingale decomposition (stated in Lemma 2 and proved in Lemma 20 of the error and establish sharp concentration bounds to account for these dependencies.
Recall the DSM objective in (4). As explained before, there are two sources of noise: (1) due to 2 conditioned on T2, (2) due T, Pt. We demonstrate the effect of fluctuations in žạ (2 in
Theorem and then deal with the random fluctuations due to 2t in Theorem 2
Empirical L2 error per parameter
10
Error per parameter
Empirical L.2 error per parameter
Error per parameter
Empirical L2 Error Fit: slopa=-0.02
0.010
Empirical L2 Error
depedence
0.008
8 10
x 7
0.006
6x 10
5x 10
0.000
125
30
125
Dimension
Dimension d (b)
(a)
Figure 1: (a) Empirical L2 error (44), scaled inversely by log ((H() log log (d). on log log scale. A linear fit to the points shows a nearly zero slope, consistent with our log log d dimension dependence. (b) Comparison of scaled empirical L2 error, vs. the scaled error if there were linear dimension dependence as in prior works. As discussed subsequently, all previous works provide scaled error bounds with atleast linear dependence.
Our first result in Theorem D provides dimension-fine bound the empirical squared error, wherein we show how to control the noise due to 24, conditioned on the data, Iz.- Theorem 1 (Empirical L2 Bound). Let Assumption 7 hold. Fix 8 (0, 1). For all j E [N), let
= Aj and 7/3 == A. Let B = log ((L + 1) dmn log (1) /A) for absolute constant C' > 0, and let A log' { )d log" (2d) log 3 (2
log'
B
< 1 and NA < C'oog( Then for
(L 1)²
B 8
m
log
NA
2
with probability at least 1 8,
Ya f
(4)
(t, (4)
)1
Σ
SE[m].JE[N]
74 12 have at least a linear dimension dependence apart from the log (lH)). In contrast, modulo log H)), our bounds nearly dimension-free ( log log (d) dependence due to B), and instead depend on the smoothness parameter L. Therefore, we bring down the complexity from poly(d) log((H)) to log((H)) which is meaningful in high dimensions.
Remark 1. All prior works such as 3
To put our results context, prior work (12) shows that score matching suffers from exponential dependence on d in the worst case. In contrast, show that when the target distribution admits

---

suitable class of estimators with mild smoothness assumptions, score estimation becomes sample- efficient. This closes the gap between theoretical results and empirical findings in diffusion models, where global optimization reliably learns accurate score functions for natural images, despite the worst-case guarantees for training neural networks.
In Figure 7 (see Appendix Section for details of experimental setup), we train a 2-layer neural network with a fixed hidden dimension and sample size, to sample from N (0, 22), and measure the L2 error across timesteps, described in ( scaled inversely by log (I+)) log log (d). Here we use the fact that log (1Hl) scales linearly with the number of parameters for neural networks (with quantization). Figure is consistent with the dimension-free bounds in Theorem 7
Remark 2. Theorem [ requires the time- time-discretization A ((1/d²). However. this is not problem
during training due to the use of stochastic optimization algorithms which obtain minibatches of datapoints at randomll sampled times. We illustrate this further by distinguishing between the statistical and optimization questions underlying our results.
Statistical question:
The standard loss formulation in both theory and practice has time discretization
= O, corresponding to an entegrallxpeccationn over time. See Equation (17) in [17] and Equation (7) in 143/. We consider fine approximation of the integral with A = O 1 due to purely technical reasons since a log log (1/A) term appears in the ervor bound. Note that A can be made much smaller than O (1/d9) due to dependence. In fact, due to assumption 1, the difference between
the integral (i.e, A = 0) and our loss is O(V A). Therefore, our framework allows for considering the standard integral formulation of the loss as well.
Optimization question: The integral or the large sum in the loss function is computationally in- tractable to optimize directly. Hence stochastic optimization algorithms such as SGD Adam are used. Here random batches of datapoints are drawn to evaluate the stochastic gradients. When the times are sampled randomly, we obtain unbiased estimators for the gradients of this loss, even when (or when it is very small). Therefore, practical training can be performed efficiently even when A = O()/d)).
We further note that this does not adversely affect inference since Theorem 3 shows that one can use larger step sizes during inference without deteriorating quality.
The parameter B arises from our partingale-basede concentration analysis, which involves subGaussian random variables whose subGaussianity parameters are themselves random. We show that with high probability, these parameters are uniformly O (cxp(B)) via a union-bound leading to the log (B) factor. Refer to Lemma 17 in the Appendix for the detailed argument.
Remark 3.
Theorem is the first step in proving the expectation bound in Theorem 2 and may be of independent interest. Theorem[ deals with the noise arising from the data I; ~ Pt. Our next assumption, called 'hypercontractivity" controls the 4th 4mmmoment of the error bound with respect to the momentt, which can be used to prove the generalization of the score function in L error. This mild
assumption, standard in statistics and learning theory under heavy tails 330 23 33
Assumption 2. Let K > be a fixed constant. Then, for every f E H. and V2 ~ Pt, we have:
El1S(1, xx) - -(,))))(((,)))))))) (1) < xE]I - s(1, x: 113
1 can be bounded (up to multiplicative constants) by the kurtosis of [(1, xx.) ((,, 2²). Assumption 2 follows from the smoothness and strong convexity of neural networks in the parameter space (not s.). shows that near the global minimizer of the population loss, many smooth non-convex losses exhibit local strong convexity.
as shown in Lemma i0 in the Appendix. Recent work [32 52
Under Assumptions T and 2 we state our main result in Theorem 2 In this result, we use Theorem and handle the noise due to x4 ~ Pe in the DSM objective.
Theorem 2 (L2 Error Bound). Let Assumptions 7 and 2 hold. Fix 6 E (0, 1). For all j E [N], let t, = Aj and 73- == A. Let B == C' log ((L + 1) dmN log (t) /A) for an absolute constant C' > 0, and let A log A )dd log (2d) log 3 ( (2Nm) log B
< 1 and NA < Clog(()) 1) If
N σ
(L + 1)² N A
B 8
Z x² max
log
log
22
5

---

then with probability at least 1 8,
Σ
Tr Ba [II (t,, (ty, [1 Se²
JE[N]
Remark 4. In addition to the sample complexity of Theorem the sample complexity for the generalization bound in Theorem 2 additionally has a factor of k due the local strong convexity assumption formalized formallzze in Lemma 40
We note that Theorem 2 considers small values of time discretization A, which
issue during training (see Remark 2 However, we can accelerate inference by using larger timestep-size to discretize the diffusion process, shown in Theorem [ and proved in Theorem 5
Theorem 3 (Fast Inference). Under the same assumptions as Theorem 2 partition the timesteps [ - JEN into k disjoint subsets Si, S2..... Sk, where each subset St contains timesteps of the form tj A(i + nk) for N. Define 7 := k& for all in any subset S,. Then, there exists at least one subset S; such that, with probability at least 1 5.
EnEEa, [1((())))))) - - It, 1|2 Se:
JES:
The subsets S; allow for much coarser discretization with differences being & instead of A. While the error due to discretization of the SDE might become worse, as shown by the bounds in (. Theorem demonstrates that the score estimation error does not degrade.
Comparison with prior work: 3 and [14] analyze the DSM objective 4 by independently
bounding the error at each timestep and applying union bound over all t E T. 3 assume bounded
support over an & ball radius R and L-Lipschitz score functions, and derive (up to logarithmic factors) the following per-timestep bound using Rademacher complexity:
| [t.22)) (t.20)
Exg
(6)
where (H) is the Rademacher complexity of H. When using uniform step size A, this leads I
to sample complexity scaling pol((A), with at least linear dependence d, especially since
R ((vd) in practice.
14 improve the dependence of sample complexity for Wasserstein error, removing smoothness assumptions on the score function and relaxing the Eg error. They show that learning f E H. satisfying the relaxed criterion for each / suffices for sampling, with a per-timestep sample complexity of
2 dlog
[
/e2, again using union bound over time. Their bound avoids dependence on 1.
but retains linear scaling with d.
[16] study gradient descent for optimizing ( when is L-Lipschitz and the target distribution is within an & ball of radius R. They model time as an input and use a kernel regression perspective to jointly learn across timesteps. While conceptually similar to our approach, their sample complexity (Theorem 3.12) still exhibits polynomial dependence on d.
12 analyze the paramearittic setting under the assumption that the score belongs to a Hölder class with 3-smoothness. This leads to exponential sample complexity in d unless 3 = (cd), aligning with worst-case lower bounds. In contrast, our work avoids this curse of dimensionality by making more pragmatic assumptions inspired by empirical diffusion model performance: (a) only needs to approximate the target's s score function; (b) mild time regularity; and (c) second-order differentiability
of the den-dtysty. These assumptions, also common in prior work [50] 3 6 35 enable nearly dimension- free generalization bounds.
Technical results
In this section we describe our proof techniques and key technical results. Figure summarizes the key results in this section and how they work together lead to Theorem
For ease of exposition, we introduce some additional notation. For all timesteps { wherever
its clear from context, we denote di, o, and for all samples E [m]] we denote x = 2 and
(4)

---

Lemmall 1
Linear to- Quadratic Reduction
Lemma 2
Martingale Decomposition
Lemma
Lemma 4
Conditional Sub-sanssyy
Variance Control
Lemma Martingalc Concentration
Lemma t E2 Conversion
Theorem I
Empirical & Error Bound
Figure 2: Dependency graph of the key lemmas leading Theorem 1
2, 2) For all appropriately defined function f. g. we denote the empirical expectations as Exy [f (Iy) = m Emjjm]] ((x and E.r,,,, (I,, 2,)] = 1 Lig(m) g(m)) _.()). ). For any random variable we denote the conditional expectation as Ex,, [v] := 1
(1)
We start by bounding the empirical squared error in terms of linear form in Lemma | This relates the empirical error, L of the minimizer with the score function, While we assume for simplicity, it can be relaxed to assume that 3s E H with sufficiently small le error, similar to 14]
Lemma 1. For f E H.
C())= = E Be [1)(()))))) - s 21)))))))
SEINI
-2 --s(stt))))) H1 Σ Ty (f(t,) s(tr,zz);
JEIN]
Let 2 be as defined in 4 If E H then f = arg inf sen B(f), we have L(f) < H!,
(7)
Let j be the minimizer of É(J). Lemmal (proved in Lemma 35 bounds L(J), the loss of f against
the true and unknown score function with H$, We will show high probability bound on H defined to control L(f). Interestingly, as shown Lemma 2 (and proved in Lemma 20). for fixed is possible decompose H' as martingale difference sequence.
The martingale difference decomposition of H', exploiting the Markovian structure of (I. has terms of the form Q: = (G,, Y; E [-])F adapted to the filtration (F) where G2 is Fi-1 measurable random variable. The proof primarily uses the fact that for i l2 ls. [i,, 14 = E [r [iz)] due to the Markov property.
Lemma 2. Let Ç = --1 for any f E H. Define
Tge (4,- (t)-tt) 20)
(t,,
G
G
Σ
03
o3
N=N-k+2
and define Rajs
(G.,
E (1))
for k [N 1],
Ri, :
(G,, - 1E, 12, 12)
for k = N.
7

---

and R = 0 k Define to = 0. Consider the filtration defined by the sequence of a-algebras,
Fi,k = = : satisfying the total ordering ((11:)1) < (22, if < i2 or i = 12 J1 < j2}. Then,
: < i,j E [ U { ] 2 - k)),
[m]] and k E (O....,
1. For k 11, Gia+1 is measurable with respect Fi, and G Fx-1-measurable.
2. For E [m], k E [O) (Ra,) (s,e) forms martingale difference sequence with respect to the filtration above.
3. H Lig[m)] EKE[N] Ri,. where H$ is defined Lemma 1
In the above Lemma (and proved in Lemma 20 Rsa denotes the martingale difference sequence arising from the Doob decomposition (see e.g. 9 Our aim is to bound H by bound H uniformly for every f. using martingale concentration. In the next lemma, we show that conditioned on F,-1. Q: is subGaussian. To gain intuition into how subGaussianity comes into play in our context, we note that Lemma F.3. in [14] shows that the score function, s(t, 1z). 1/or-
We develop fine-grained grained argument exploiting the smoothness of the score function to show subGaussianity (Definition [ for our sequence. The proof provided in Lemma 30
more fine-
Lemma 3. Fix ò (0, 1). Consider R.,k and Fs.k as defined in Lemma 2 and let A := tN -+-1+1 EN-K ko Under Assumption y following the definition in Definition [ conditioned on Fik-1, R., is ( Wi,k)- (..k)-suGGuussan where Kr,k: Wi,k are Fi,k-1 measurable random variables such
that W I log (3) with probability at at-least 1 8 and
(L + 1) e Ad IEIN- 1], Br, = 4vAd, k=N
However, the subGaussianity parameters in Lemma 3 depend polynomially the data dimension, d along with G; and the step size, A. Solely relying on this leads to a simension-dependen bound. bound, we evaluate the variance of Q;
To further refine analysis and show dimension- conditioned on F;-1- As shown in the next Lemma (Lemma 4 (and proved in Lemma 29 the variance depends only the smoothness parameter, L, along with G3 and A.
Lemma (Variance bound for martingale difference sequence). Consider the martingale difference sequence R, and the predictable sequence G with respect to the filtration Fs,k from Lemma Define A = LN-K+1 - -N- Then,
1 S vi, where
C(LA2 A + L2 2 k+1 G (1,441 11: E 1], C(LA² I|?
pi, {
N
where C > 0 is absolute constant and v²,K 0 k 0.
The proof of Lemma 4 involved when he (x) = 2 (Pt) (x:) is not assumed to be Lipschtiz in x. Starting with the martingale difference sequence defined in Lemma an application of the second-order tweedie's s formula (see Lemma p2 reduces the problem to bounding the operator norm Cov(s (t', xee) (zz)) for - l' A > 0, i.e. the conditional covariance matrix of the score function given the future. Exploiting the smoothness assumption on the score function, an application of the mean value theorem reduces our problem to bounding the operator norm of:
EE he (ye (x (x) āe) he (Nw) [ T
<t
for Te,, Zt i.i.d conditioned on De and yr = Ary + (1 A)ār, X E (0, 1). Notice that yo |., is dependent Zet, Ze / which does not allow the use of Tweedie's second-order formula (Lemma 22) to bound E [xxy Ze (x Ev.) ) [ and derive variance bounds that are dimension-free To approximately allow this argument, we decompose he (yr) ) into two components:
by (ge) = he. (yr) + (he (ye) here (ye)).
The first term, le. (ye). represents a hessian after being smoothed with an appropriately chosen distribution, which we show satisfies Lipschitz continuity. This allows us to approximate he.e(v)) se

---

(e,c(c and bound the variance with Tweedie's 's second order formula. The second term, which represents the deviation between the original and mollified Hessians, bound using Lusin's theorem (Lemma 27 to provide approximate uniform continuity for by, as developed further in Lemma 28
Putting together Lemma X and Lemma we provide general concentration tool for martingale difference sequences with bounded variance and subGaussianity in Lemma We follow a similar proof strategy via supermartingale argument as in the proof Freedman's is inequality (see for e.g. 47), but diverge in dealing with subGaussianity instead of almost surely bounded random variables.
be such that Lemma 5. Let Mn Σi= (G,, Y E[ Mo and the filtration {Fiiie()) G3 is F,-1 measurable and
1. (G, Y, F--I) is (8]1,, K₂) sub- Sab-Gaussian conditioned on Fi-1 (where B3, K; are random variables measurable with respect to Fi-1)
2. var(
-X S Il and define J; == max(1, R. log
pK, of
Pick À > O and let A,(A) ( S. co) for some small enough universal constant co- Then, there exists a universal constant > 0 such that
Ve > O, P((MM, > CX²) Σ [ n A.(A)) S exp(-w)
Observe that the concentration result developed in Lemma 5 (and proved in Lemma 16 has two parts. Optimizing the choice of X, it can be shown that the bound M,, depends on two terms: (1) an l term, Eietn 2²2 ||Gx ||2 and (2) an Po term, suPse[m] Ja ||G,ll 3.v K, When applied in our context, these two terms in turn depend on norms, Ilf - 2||2 and Il. *Il This is where the timerregularity assumption in Assumption [ plays crucial role in analysis. Specifically, it enables to bridge the fox and f2 norm bounds derived from the martingale concentration results in Lemma The proof of Lemma 6 leverages this assumption to relate |If (t kA, a2+* to |l (t, 244 2l shown by:
II (t + KA, FL+AA 212 e Ilf (t, (1)l1 2 (((VVkk))
Exploiting this property over carefully selected range of k values allows us to relate to and lg norm bounds as we show in the following Lemma.
Lemma 6. Under Assumption 7 with probability 1 - for universal constant C > 0 the following
holds uniformly for every f E ET:
Nm
sup (tg, - xt,,,))11 ic [m] JE(N
S CA
Σ im|m
st,
CL log
JE(N]
Lemma establishes that the simultaneous analysis of all timesteps uses the smoothness across time. In the absence of this approach, the smoothness assumption in the sp-eeae would lack dependence on A and could grow as large as the Lipschitz constant L. This is essential for establishing nearly dimension-indeeeedden bounds. The proof of this result can be found in Lemma 39 the Appendix.
5 Bootstrapped score matching
In Section 4
used time regularity and could prove nearly d-independent bounds. Learning with the same function class across timesteps and Assumption was critical to our proof.
We now attempt to exploit the dependence across timesteps explicitly and reduce variance in estima- tion. Using the Markovian nature of (I). we show that for any L' < L and a, E RR s (1, xx.) = Elg [xr]]
for Je := _/2 - (s target for the score function. This in contrast to the target yt = At used in (4) The advantage of
(s(( (t', xT) 2nd ). This shows that T/ can also be used to construct a learning
of
ÿt over is in the lower variance of Tt. as shown in Lemma 7 (proved in Lemmas
A03 Lemma 7 (Bootstrap Properties). Let Pt := 0t 10--s( st,, xz). For t' < t, ler A = t-t' and ot == of
Then, under Assumption we have E [ = 0 and | [=o]llopp = 0 0122
(12+111)

---

To compare with y1 3 we note that an application of the second order tweedie's formula along with Assumption shows the variance || (v) - x(),,,)) p to be of the order
O L. Therefore, although both and it are unbiased, the variance of in has an additional step size (A) factor in the numerator (see Lemma]) 7
The BSM algorithm (described in detail in Appendix G operates sequentially over discretized < εy = 'T' and builds upon the principles of DSM while
time horizon 0 to < f introducing a novel bootstrapping mechanism to mitigate the increasing variance of the DSM loss in later timesteps. Given dataset D = { hiefm] sampled from the data distribution, the perturbed samples at timestep & are generated as zi, = ( e + 2t% z(" ~ (0, of, where of = 1 1-e-2h, The task at each timestep l is to estimate an approximate score function St,, (x) to optimize Ex,, (1) Se, (z) For the initial timesteps 4 with & < ko, the algorithm employs DSM.
The score functiin St,, is obtained by solving 3r2 = arg Jen Eie(m) m
[ 2
For later timesteps is with ko, the algorithm transitions to BSM. At each timestep, the algorithm -= with the previously estimated of
constructs bootstrapped targets ū!!"" by combining the DSM target score 8 Specifically, the targets are defined as:
(e) 2/ +
(() Via = (1 aR)
tas
Stx 94 (2th
2t
cla
Unbiased Target
Biased Target
----1 I-e 2ig with *k- tx ---1- Given access to the true score function.
where ag = e e-
s(tx-1,.), then (() would form an unbiased target with lower variance, as shown in Lemma 7
However, since we only have access the estimated score function, St._1 the previous timestep,
(6) 9h. is biased target, and the parameter og. weighs between the biased and unbiased targets. The
score function, stg is then learned as: &r, < arg minjeH, Exe(m) [ x(() Vig
((() |
6 Conclusion
To our knowledge, this is first work to establish (nearly) dimension-fre sample complexity bounds for learning score functions across noise levels. We show that a mild assumption of time-regularity can significantly improve over previous bounds which have polynomial dependence on d. We achieve this with a novel martingale- based analysis with sharp variance bounds, addressing the complexities of learning from dependent data generated by multiple Markov process trajectories. Furthermore, we introduce the Bootstrapped Score Matching (BSM) method, which effectively leverages temporal information to reduce variance and enhance the learning of score functions. While we provide theoretical insights into the training of diffusion models, several open questions still remain. One potential direction is extending our framework to flow-matching models where such bounds could yield further insights. Additionally, while BSM is a compelling algorithm, establishing rigorous theoretical and empirical performance guarantees is an open problem which we leave for future work.
Acknowledgments and Disclosure of Funding
We gratefully acknowledge NSF grants 2217069 2019844, and DMS 2109155, Additionally, part of this work was carried out while Syamantak was an intern at Google DeepMind.
References
[1] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear convergence bounds for diffusion models via stochastic localization. The Twelfth International Conference Learning Representations, 2024.
10

---

[2] Jalaj Bhandari. Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691- 1692. PMLR, 2018.
[3] Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint arXiv:2002.001007 2020.
[4] Nicholas M Boffi, Arthur Jacot, Stephen Tu, and Ingvar Ziemann. Shallow diffuusion networks provably learn hidden low-dimensional structure. arXiv preprint arX1v:2410.11275,000 2024.
[5] 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, pages 4672-4712. PMLR, 2023.
[6] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint wrXiv:2209.112155 2022.
[7] Valentin De Bortoli, Michael Hutchinson, Peter Wirnsberger, and Arnaud Doucet. Target score matching. arXiv preprint wwxiv22402.08677 2024.
[8] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1577 2012.
[9] Rick Durrett. Probability: theory and examples, volume 49, Cambridge university press, 2019.
[10] Zach Evans, CJ Carr, Josiah Taylor, Scott H. Hawley, and Jordi Pons. Fast timing-conditioned latent audio diffusion. In Forty-first International Conference on Machine Learning, 2024.
[11] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, 1999.
[12] Hengyu Fu, Zhuoran Yang. Mengdi Wang, and Minshuo Chen. Unveil conditional diffusion models with classifier-free guidance: A sharp statistical theory, 2024.
[13] Ishaan Gulrajani and Tatsunori B Hashimoto. Likelihood-based diffusion language models. Advances Neural Information Processing Systems, 36, 2024.
[14] Shivam Gupta, Aditya Parulekar, Eric Price, and Zhiyang Xun. Improved sample complexity bounds for diffusion model training. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[15] Xiaochuang Han, Sachin Kumar, and Yulia Tsvetkov. Ssd-Im: Semi-auttregressive simplex- based diffusion language model for text generation and modular control. arXiv preprint MrXiv:2210.17432. 2022.
[16] Yinbin Han, Meisam Razaviyayn, and Renyuan Xu. Neural network-based score estimation in diffusion models: Optimization and generalization. arXiv preprint arXiv:2401.15604, 2024.
[17] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:684006851, 2020.
[18] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International conference on machine learning, pages 8867-8887. PMLR, 2022.
[19] Chenqing Hua, Sitao Luan, Minkai Xu, Zhitao Ying. Jie Fu, Stefano Ermon, and Doina Precup. Mudiff: Unified diffusion for complete molecule generation. Learning on Graphs Conference, pages 33-1. PMLR, 2024.
[20] Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
11

---

[21] Naoto Inoue, Kotaro Kikuchi, Edgar Simo-Serra Mayu Otani, and Kota Yamaguchi. Layoutdm: Discrete diffusion model for controllable layout generation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 10167-10176, 2023.
[22] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736, 2019.
[23] Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
[24] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations 2021.
[25] Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances in Neural Information Processing Systems, 34:8518-8531, 2021.
[26] Syamantak Kumar and Purnamrita Sarkar. Streaming pea for markovian data. Advances in Neural Information Processing Systems, 36, 2024.
[27] Holden Lec, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pages 946-985, PMLR, 2023.
[28] Elad Levi, Eli Brosh, Mykola Mykhailych, and Meir Perez. Dit: Conditioned layout generation with joint discrete-continuuut diffusion layout transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2106-2115, 2023.
[29] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. 2023.
[30] Shahar Mendelson and Nikita Zhivotovskiy. Robust covariance estimation under 1_4-1_ norm equivalence. 2020.
[31] Chenlin Meng, Yang Song. Wenzhe Li, and Stefano Ermon. Estimating high order gradients of the data distribution by denoising, Advances in Neural Information Processing Systems, 34:25359-25366 2021.
[32] Tristan Milne. Piecewise strong convexity of neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[33] Stanislav Minsker. Sub-gaussian estimators of the mean of a random matrix with heavy-tailed entries. The Annals of Statistics, 46(6A))2871-299) 2018
[34] Dheeraj Nagaraj. Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 166666666666, 2020.
[35] Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models minimax optimal distribution estimators. In International Conference on Machine Learning, pages 26517-26582.
PMLR, 2023.
[36] Dustin Podell, Zion English, Kyle Lacey, Andreas Blattmann, Tim Dockhorn, Jonas Müller, Joe Penna, and Robin Rombach. Sdxl: Improving latent diffusion models for high-resolution image synthesis. arXiv preprint 23Xiv.2307.01952 2023.
[37] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06123, 1(2):3 2022.
[38] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pages 10684-10695, 2022.
12

---

[39] Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill, 1976.
[40] 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 9900499999444,, 2022.
[41] Daria Schymura. An upper bound on the volume of the symmetric difference of a body and a congruent copy. Advances in Geometry, 14(2)287-229, 2014.
[42] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[43] Jascha Sohk-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages
PMLR, 2015.
[44] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pages 574-584, PMLR,, 2020.
[45] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:201 13.556 2020.
[46] R Srikant. Rates of convergence in the central limit theorem for markov chains, with an application to td learning. arXiv preprint 15177:2401.15719, 2024.
[47] Joel Tropp. Freedman's inequality for matrix martingales. 2011.
[48] Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi. Learning from many trajectories. Journal of Machine Learning Research, 25(216):1-109, 2024.
Discrete diffusion models via binary classification.. arXiv preprint arXiv:2405. 17035, 2024. [49] Harshit Varma, Dheeraj Nagaraj, and Karthikeyan Shanmugam. Glauber generative model:
[50] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In H. Wallach, H. Larochelle, Beygelzimer, d' d'Alché-BBl Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[51] Pascal Vincent. A connection between score matching and denoising autoencoders. Neural computation, 3(7):1661-1674 2011.
[52] Mingyang Yi, Ruoyu Wang, and Zhi-Ming Ma. Characterization of excess risk for locally strongly convex population risk. Advances Newral Information Processing Systems, 35:21270- 21 21285, 2022.
[53] Ingvar Ziemann and Stephen Tu. Learning with little mixing. Advances in Neural Information Processing Systems, 35:4626-4637, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide a clear description of the scope of our result and a detailed comparison with prior work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide descriptions of our limitations and a scope for future work as part of the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
We provide detailed proof' of all claims made in our work.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide clear description of the experimental setup in the Appendix for reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our primary contributions are theoretical and our experiments are on syn- thetically generated data for simple data distributions which we describe in detail in the Appendix. We provide code for our experiments in the supplement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.com cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
wwwp://wweeeeeeeeee Saaieees/oooSemmiiiiaa SonroddeummsssiooPPe.. wwwiiisssoiiiiiiiiooi for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide clear description of the experimental setup in the Appendix for reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In first experiment, overlay best-fit linear regression whose slope is virtually zero, thereby substantiating the statistical significance of our near-dimension-fiet claim.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments are provided on a single Google Colab CPU. We provide this detail in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:///wwrrip...cppppp////teaea
Answer: [Yes]
Justification: Our contribution is theoretical, where we show how to analyse the sample of diffusion models to obtain dimension-free bound.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Our contribution is theoretical, where we show how to analyse the sample diffusion models obtain dimension- free bound for the well-known DDPM training algorithm. As such, we do not introduce any new socictal impacts.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do release any new models. Our contribution is thcoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
There are no new assets introduced in the paper. Our contribution is theoretical.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets introduced in the paper. Our contribution is theoretical.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
There is no human subject study conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: There is no human subject study conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not use L.Mss apart from writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

The Appendix is organized as follows:
1. Section A provides some utility results which will be useful in subsequent proofs.
2. Section provides variance calculation for the martingale decomposition.
3. Section B analyzes concentration properties for martingales with bounded variance and subGausstamity, which may be of independent interest.
4. SectionDaanalyee convergence of the empirical squared enror by providing the martingale decomposition and exploiting the results developed in Sections and
5. Section provides generalization bounds to achieve guarantees for the expected squared error.
6. Section provides details for the experiment conducted in Figure D the manuscript.
7. Section provides details about the Bootstrapped Score Matching Algorithm descrihed in Section
A Utility Results
Definition (norm subGaussian). We will call a random vector X E Id to be norm subGaussian iXX 0 and
Eexp( [| 2.
Definition 3. We will call a random vector X E Rd to be subGaussian if EX 0 and for every v E TRd and E we have:
Eexp(A(v. x)) S exp( Xollo
Lemma 8. Let X ~ N (0,02)) Then, X is 2a norm subGaussian.
Proof. Consider the random variable = | with degrees of freedom. Therefore, for any 1
Then, y ~ x(d) follows the chi-squared distribution
| 2 2
]
E
exp
(1 2t)
o²
Setting t 1d we have
-2d 1
|
(11
1 2d
E
exp
(2cr)
2d
Lemma 9. For all f. >> 0, I1, E Rd, consider any function u. Rdd - Rd satisfying I|u (a,) - u (x2) ll2 I S $1a; F2 P2llz- where S > is fixed constant. For timesteps t' consider the random variable
at = u (xx) - (xx) [xt]
where Ft is defined in IT. Then, au is @v norm subGaussian for
o: = 4Se 11-
where A = 1!. 1!.
Proof. We first note that
Ex,zy 1gr. = Ex,, [urr (xv) - Er. [E [uter (xter) | = 0
21

---

[1 112
)}
Using Lemma from 22 we show that Exr,,
exp
ald
2. Let ay be an iid copy of
Ie', conditioned on 24. Then, we have,
|| 11 6²d
11 1/3 d2dd
Ex,,a at exp
Ex,
Ex,
exp
[
(xxr) - Iis,, [ee (zzz) |000
Exz
exp
1 (xxx) Eer, Iu (xr(e) [00c]
En,
Exe'
exp
14
(8)
o2d
|| Iu (Ire) - (x(te) [xt]]
2
Ex,
Exz
exp
2
o2d
Exy [|u (20e) - 2 (2/r )12
20
<
E
E
Exp
exp
It
d2d
1u (IN2 - u (srke)11
< Ex,
E teuiat
exp
62d
S2 ||arer - 2/rel12
< En,
Exe s
exp
I
(9)
@2d
Note that using Therefore, from
I De = Axy + Waee = e A-A + wwirr for wa why ~ N (0, v.)
|1gre 2 odd
S2 |/00 weuellz)
exp
< Exee
B Bur
exp
It
o2d
22
|
wherr 112
exp
d2d
282 24
(Ilwe.er 112 +
|l 113)
Ewgr wyy
exp
&2dd
24
| 112 )
245222
| 122
exp
exp
2
2dd
2d d
2 2
where the last inequality follows since w why ~ N 02 marginally (but not necessarily conditionally).
Lemma 10. 8ix > O. t.. Then, under Assumption (1), (), with probability at least 1 over It.
((-(t_())(txzz))) s(t', e(t,et())))) s elt-r') LV 8d(t t') log
2 (
8
where of == 1-e 2((--)) < 2 t').
Proof. Using Corollary 2.4 from 77.
8 st, = ct- (t', (())))))) [xd
(10)
22

---

Using D.
Tt - (t- 2 for 21,0 ~ N (0, (0,
(II)
Where Z is independent of xe. Let Ve e e- (1-1 (t- x2) - s(1' s(t', a(!',el(-))s))) Then,
|le (1-00(000 s(l', (((,,e(t-))) 25))]
||T (s (1', xx) [2ox] - s(1', elt ett-+)xxe)l
- -|IB [sw (elt-t) 2nr)) - s(l', (1',,ed elc-
,e,ee (xx)))))))
S e' LE e1|ze,e [m2)
Note that since Zt, ~ N (0, 02
| 12
exp
40²
$ 2, using Lemma
Therefore, with probability at least 1 - over Iz:
||
2
E
exp
40 d
2
It
8*
using Markov's inequality
Using Jensen's inequality,
ze,er 1l
are
1 112
2
exp
E
exp
S
40 d
40 t-
8
The result then follows by taking log on both sides.
Lemma 11. Let Wa.r = to (1, sort 1' 2 0. Then, Wa is Va v norm subGaussiar for ur = 40
Proof. Notice that It = cl'-'ax + 21,1" Using Tweedic's formula, (t, = -EE D1
Therefore,
'-c' po + e-- 82 = -[er
Wt.t = xx + Ele" -t tee [tce]]
Applying Lemma with u(x)= = - -t (which is et' Lipschitz), we conclude the result.
Lemma 12. Suppose Assumption (1) holds. Let U4.er = E[xgla+] -E fort > t' 2 Then.
Vee is PL / norm subGaussian for
Pe. = (L 1'''o
Proof. Using Tweedie's formula, for all 1>> 0.
E [xolæx]] = [e" (Iz - 21) [x]] = e' + e'E(12/ = e' (x, + ofs 21))
Note that de = el- (xe ). Furthermore, note that
E [ [ar] -o (t, (t, [ss (IT) [ar] = (1--2)) (t)
Therefore, have
Ur e (2E, oz st, xe)) el (sy (xe) - - (1-t1) (1,
Using Lemma 11
T is 4e 4d'or-eVd norn subGaussian. Using Lemma Tz is
4T et Roreedd ALe' aaeaaao norm subGaussian. Therefore, the result follows using the sum of subGaussian random variables.
23

---

Lemma 13. Let A > 0 and A < for some universal constant co. Then,
1. EN jobk (1-e- S 1-e-2s (N + 1-e-za)
2. Σ ال I
2ز=1 (1-ج-ممحا (1 (1-0-2533
2
- 3. Eド=1 I-c 25y
S I-c 25 + logi x
Proof. Let us start with the first bound. We have,
N N
N
j
(((-1)
ΣΣ
(1-e-2a))²
22j)²
j=1
N
1
((())))
-2 2
e
k=1
1
25
(1 -1-6
(1-e-25) 201)
c
22l
2A
N
1
25
1-e-
j=l
Consider the function f (x) = 255- Then, f (x) is positive, convex and decreasing. Therefore,
N
L
'N
Σ
1 e- 2Ar dx
e 2Δj
1=1
N
+
In (E25e -1)
1- 6-ee--4 2A
2A
+
In (e2AN - 1)
1 e 24
2A
N
e 22
which completes the first result. Now for the second result,
N
226-11
24
(1---201)²
2-ر 2
Consider the function, (z) = c -20 function. Therefore,
(I- 20rj2. For x > 0, 0,g (I) is a positive, decreasing and convex
N
e 2Aj
r + L" N
gz)
c 2Di}²
(1- 22-)2 + N -22
22
dx
(1 - (2-x-2
2A
+ 24 (1 2Ax
(1-e-2a) 2-22
22
+ 2A (1 c
(1 (1-e-25)²
-2NN
20 -2A
222
24

---

which completes the proof. Finally for the third result, consider the function h (3) == I-e-2x3 For 0, h (a: is a positive, decreasing and convex function. Therefore,
L N h (x)
sh(1+
2Aj
e-a
e-
e-e-2 dx
1-e-26
N
1
+
log (tanh (Az))
1- - 2-22
2A
e A
log (tanh (A))
1 1-6-2
2A
e e
log (1 - -2
2A
2A
log( 1)
e
A
25
2A
B Martingale Concentration
Lemma 14. Let Y be a (6², K) -ubGaaussii random variable following definition with (K 2 1). Then, for any integer k > O and some universal constant 0:
E [ < gk + C* k1,22k
Proof. By Definition for any A >
1a P( A) S K exp
2/2
Using the tail-integration representation of moments, have
P( 2k > t) dt = / |[ > (/12k) dt.
2k
Make the change of variables i 2.2h that dt 2k 2h dr. Then
2k 2k PP(Y) > x)) dx s 2k 1 2k- min (1, e exp( 250 ) dx.
B
miin11cc
Let Fo K
|||LY 2 < 2k [ 50
2B 22 dr + 2k
x _2k 2k 1
m, dx
2
K)* 2k
I. 2k-1
K
252 dr
(x-rg)²
<2 + 2k
1 2k-1
6
252 dx
20
(e xg)
$ k)* + 22R-1 1b
(x0
+ (x - 20) 2k
25
dx
In the second step have used the fact that whenever 2 No. must have K In the third step we have used the fact that 2k < 22 20) 20 2k-1
x²
S
(z-zo)²
23a
23
2
2k
whenever Z0.
25

---

A standard Camma-function integral yields
J 2h-1 exp
2 dr
(2 r(k),
and for integer k, r'k = (k 1)!. Substituting this to the equation above, we conclude that for some universal constant C1, have:
]|[ < (2 + (k.82k kk- + 32%
We then conclude the result using the fact that K 2 and As < 2²
Lemma 15. Let Y be (3², K) -usbaaussiin random variable following definition 1
such that
K 1, [Y] 0 and E [y S v². Then, for a sufficiently small universal constant co such that, AB S Co, and any arbitrary A > O, we have:
Eexp(>?y2) 1
{ x
+ -XX exp( 43
A2
C
Proof. For some À > 0, consider:
2 2
[exp(A>X23) = =1 +
(12)
k!
A22
Now, using Lemma 14 consider
E y 2k
E [ 26 1(11) A)] +B 2 1(| A)]
I Y skj P(L > A) + Y2 2
E| /P(X A) + +2² 2h-
Bak (2)) C 3th 3 2 exp( K -12
*5z²) + 2 22R-2
S ((20)*1183* C* 5ah K exp(
132
1² v² 2
(13)
Here, we have used the fact that (2k)! < 4 (k!)). Plugging this back in Equation that whenever A, S co for some small enough constant co. we have:
12
we conclude
E [exp() < 2 exp(>2A²) K exp K A
3C
(14)
Theorem 4. Let be (32, K) -ubGaussian random variable following definition ! such that
K 2 1, B 0 and E [Y]] S v², Set A 2 8/ 4 4ogg( SK + 3/2KKKK and X S % for some small enough constant On 0. Then, there exists a constant such that:
E [exp(XPy2)) cx+0x02
Proof. The result follows from Lemma 15 substituting the values of À and A.
Lemma 16. Let Mn = E (G,, Y, F, Mo = 1 and define the filtration (Fi) (Fibeejn) such that:
1. G, F measurable.
2. (G,, - -(----)) is (P K2) uub-Gaussian conditioned on Fi- (where 3, K; random variables measurable with respect to F(-1)
26

---

3. var Y, || S Gil? and define J, max(1, Ri
Ki log
of
Pick A > 0 and let A, (NA co) for some small enough universal constant co- Then, there exists universal constan! C >> 0 such that:
exp(AM, - CX2 CX Ei= 4 G
((A(A)) a super-martingale with respect to the
filtration F,
2. Va > O, P((M CARE G. + at n= A.(A)) S exp(-a)
Proof.
Let Ln
= i= exp((AM, E. || ((4,())). Then we have,
Ln F Fn
1n exp (A(Gm. -1, C2 [[G,1) (An (2)) Fi-1)
(-CXP02 eex (AIG Y, E(r,(F=-1))) (J.AAI VR, S co)) Fn-
Ln-1 exp
1n-1eepp
(-CX222 |[ exp
using Theorem and the definition of A, (A)
Tm--1
The second result follows from a standard Chernoff bound argument.
Lemma 17. Under the setting of Lemma 16 let X = V GII and Amin
sup, Ji [G.ll& /K: Let B E N be arbitrary and consider the event: B= = fe I min( Amia) S
max(X", Amin) S ". Then, for some universal constant C1 and any 0.
(Mr > C2A Σ 1.ll + +1 Amia 1B & (2B + 1)
Proof. We apply union bound over X E AB = le-B,e-B+1 with union bound,
B+1
B). Using Lemma 16 along
P(UxEAR (AM, > CX2 Σ
2 + 22 A(O)) s (2B + 1) exp((-a)
1=1
Consider the following events:
1. Event 1: E; {max(A*, (X", Amin) eB}
2. Event 2: &g
(min(X Amia) <e-
3. Event 3: E3 {E-B X Amin 5 B)
4. Event 4: E = (e-B < Amin
< x < B)
In the event E4, almost surely there exists random À Ag such that X/ Amin E 12 e] and such that the event n ((() holds. Thus, we have:
(M, > Cex* Σ G +
сa Tn& C (M, > CeAmin Σ G + ea
n
Amia
Amin
(M, > Cτ Σ 2 G S n (M, > Ci EuNGGI - n
(USEAnLAM, > CX² 5
+ 1
(15)
27

---

Similarly, under the event Eg, there exists a random X E Ag such that: X E 1/ e]. such that the event (xA,()*) holds. Therefore, must have:
(M, > Ced Ced E o I.l.
ea x (M, > CX Cx of A|G..11
Jn&
-(M, > Cx- Σ &fIG i 0
(AMa (Meea CX2
Ean
Σ
11 + at n= Ar(A))
(16)
Notice that X is chosen such that
Cex² Σ 2211,,1+
ca = e(C + 1), 1) al Σ 1/11G.113)
=e(C + 1)A² Σ 12
(17)
se(C+ 1)X Σ 12 G
(18)
Amin
Combining these equations, we conclude that for some constant C O, must have
G. ))((ELEE))) S (USEARfAM, > CX²
G + n. A(1)) )
(M, > Ci(1* v
Amin
Noting that B = E3 U Eq, we conclude the result.
C Martingale Decomposition and Variance Calculation
In this section, we will consider the quantity similar to H in Lemma 35 decompose it into a sum of martingale difference sequence, and then bounds its variance using the Tweedie's formula. In this section, assume that we are given Ç : IR+ x Rd + IRd and consider the quantity:
::= Σ TET.E||m] of (C(t, 2( - B[e(() (2((1)
We suppose that [(1, x1, (0) has a finite second moment. Where 7. 0 is some sequence. When
Ç 8-f this yields us H we show in Lemma 19 We define the sigma algebras: r-algebra
F, = ( 1 i < m, 2 (N-j+1) for E [N] and Fo is the trivial o-algebra. We want to filter H through the filtration Fj obtain a martingale decomposition. To this end, define:
H, = E ij NO....,NI
(19)
Lemma 18.
1. Ift < -N-141 then
Bi(((t, x (1) ) 2/ - E|z |o 11) = 0
2. 1ft > IN-jt1, then
[[( 2( 20
2(())
E| (8) 1 (1)))
e x 1[ (1 [0x
=
28

---

Proof.
1. Using the fact that (0) forms Markov process and that (122)) 2220 (1xx
)=20
are
independent when i o J. we have via the Markov property:
a( 2(t Blet" 2 1 (i (1) 2t E
Eize"
s11l
=E E((S(t, Fi (0) )) 2t - (2 Ma
(8) - -iN- 1| |
(20)
In the second step, we have used the tower property of the conditional expectation. Now,
2/4) It
(i) e
=x00 By the Markov Property, have:
Biz |x
Biy wial
(9)
Elzo pt 1. Plugging this in, have:
(6)
E[(((t, 24 ) 4 Ei2 1 M
Fyl
1 (((t, 24 ) E|2,
AN
512
(21)
2. Notice that 200 = 2111) - 0 Clearly, zt (a) measurable with respect to Fj. Therefore,
(1)
[[(C(t, 24 (1) 2t E[z,
(2)
1 Fyl = -e -c- xx(t, "(" [F
E[r (x/"))
1
Now, consider the fact that (1) (6)
Lt ... is a Markov chain. Therefore, the Markov property states that 20 (x. 8 2 T has the same law as x z.() Therefore, we must have: (9) (i)
|| E[a0) 1 1 Plugging this into the display equation above, we conclude the result.
We connect the quantity H defined above to the quantity H related to the excess risk.
(1 og
Lemma 19. Let Vi
f E H and
(0) yi, 7s (5 (t), (,),2
s(t), 2i,
H/ =
E
m
iE(m)]JEIM
Suppose we pick Ç = s-f in the definition of H. Then,
m
=$=(H -HN) Σ
(H₂ Ha-1)
k=2
such that
m
11)g3s 7/
H- HN
(S(1i, Itz
(1)
(3)
E[ |=!
N
H - H
(C(tz. T2
(0)
E(r
1 x12]
-B(rro
(6) Iie
wnnl)
NIj==N+F k+2
Proof. By Tweedie's formula, notice that v - st,
x
(8)
Els 20 This shows us that
H Hl when we pick ( s-f, The proof follows due to Lemma almost surely
18 once note that Hi
G.. = EN Ej=N- Tye a (15()=))))
z (c(()
(0)
Lemma 20. Define G, = Ej=1 of Ri,k
and
of
for k = 0
R
(G E[r
(6)
E
(2)
1 []
for k E {l..... N 1}. (22)
+11
(G
(6) E
22
(1)
4
for k N
29

---

Let to O. Consider the filtration defined by the sequence of o-algebras, Fa,k == o : I
j < i, E Ti { t 2 IN -x= for E [m]] and k E (O....,N), satisfying the total ordering
((11.11 (22 ifft 22
12 < J2). Then
1. For k E [N- - 11. G is measurable with respect to Fix-1 and G; FN-1 measurable.
2. For i E [m].K k E {0) U [M] (Ri,k)s forms martingale difference sequence with respect to the filtration above.
3. H = Eie(m) EME(N] R.
Proof.
1. We first note that for A - (N-++1] S F- Therefore,
Gi 1 is measurable with respect to Fi, Furthermore, if k = N, then G, is measurable with respect to Fi,k-1.
2. First note that R,, is Fi, measurable.
(r,R+, Ef
(6)
(6)
E
[[
(1) p
FIF =0;
when & [N - -1].
E [R
G
1E
(6) 26
FaM-1
E
(4)
0.
when k = N
The case Rıo is straightforward.
3. This follows from Lemma 19
Lemma 21. Consider the setting Lemma 20
Define:
if = 0
ViA+
E a
(K)
[ bx
(8)
1 k
if (I....., N 1}
(23)
k
(1)
2
if = N
Let Ei,k [V[ V.T. Fi, -1.-1.. Then, we have:
C
ifk:
E RR
G. GTT Di G. En
if E , N 1}
(24)
ifk=
Proof. This follows from a straightforward application of Lemma 20
Let U be any random vector over Rd independent of o')) Let W + VV and let p be the density of W, V logp and h V log Then, second order Tweedie's formula states (Theorem 1, 31
E = - + o ssW)s T (W) + oT
Lemma 22. Let St Rd + Rdd be continuously differentiable for every 0. Let t' < t and x2 - (1-r() xy + 20 where 22,0" ~ N (0, (T) as defined in Section 2 Then,
E 22 [21] oir (xx) + oivs (t, x1) + o E (1' Nx ) (t', xx:) | (t)
+e20' 20'- (xx) Elhe (xe) [xt]]
where by (zx) = 22 (p. (2:)).
30

---

Proof. Applying second order Tweedie's formula:
[,,0' [ = oi (xt) + o (t, s (t, 2c) + to and,
(25)
2 [xv] sf xx)) xs)s (xv) o
(26)
By Markov property, must have for any measurable function g:
= [ B[B]g( ) [m
Applying this to (6
of Els ze)s (t', (e [2x]] 2f [x]] -0,11 - (h
(t
(27)
Now, note that e + e² -2 + +z,.. Taking yo -== + ze,e', we have: It = y0 c² -1zz. Therefore, applying the second order Tweedie's 's formula again, we must have:
2( "[ [x=] - e(t'' ca(t'- o2 (t))(( 21) + e ell o + 2(1
That is E 2 [2,]] c st
200-000 oRI. Substituting this in
Equation (27 we have:
([s((, 20)) (e) 22 (0(,))))((),))(1 + 22 (1,( Blyy (are [are]
Lemma 23, Let 87 Rdd + Rdd be continuously differentiable for every T > O. For > 1' > 0. ler 0e,0 E [xoo (ro [. then,
E [ur [re]
20 (oi (are) va) 20 ofB
(s(( (1,20) (s
e (1-(0) (1. 1oo
where he (IL) = 2 log (pt (x:)) is the hessian of the log-density function.
Proof. Using Tweedie's formula, for all > 0, E [xoo=x]] = [ee (xz - ze) [x]] = e' x, + e [-2/ = e (xx + ofs (t,
Note that or = el (wie ). Furthermore, note from Tweedie's formula and Corollary 2.4 7 that:
E [ZL, [ata] = - - (t, [ (t', ox) [a2 = ((-rr) (t.
Therefore, we have
vt, = e (2W + oi (t, 2z)) - e" os (f((,zz) e (t-t') (t,
Then, using Lemma 22 and the fact that (a + b)(a + T)T = 2aa T + 26b
ve [
3 2I (BEN + of us 2:)) (ze, + oz (t,zz)) [2t
+ 2e 20 OfE (s(t) (t, (s (t' 2x) ((--1) (t,))s(t |
= 20 (0 (zz) + oz
+ 2e ofB (s(1),z)) - E e (1-11) (1, (s (x( - (e-10) ((,))) lore
31

---

[s((e, (t(,,e)) z0) - -e-(t-)) (t, mi)) (s - 21)
To derive an upper bound for
100
op
we adopt a strategy of partitioning the interval [ into smaller subintervals. Specifically, we divide 7B. where B > By leveraging the smoothness of the score function s, (x) over each subinterval [T.. Te+1l. we express the deviations between Sr, and 87,41 in terms of the Hessian, (z)
[t', f] as L' - To Ti <.... TB-1
1olgg p. (z). This decomposition allows us to quantify the overall deviation of the score function across the interval [t', t) in terms of contributions from each subinterval, controlled by the Hessian, (a). The following lemma formalizes this approach, establishing an upper bound for the given operator norm in terms of the Hessian and a carefully constructed decomposition. This result will serve as the foundation for subsequent analysis.
Lemma 24, Let 8+ Rdd + Rdd be continuously disferentiable for every > 0. Let B E N and let To =1' <n < T2
< < TB-1 <t:= :1 TB for B 2 and define Vt, he (xt) == 42 log (pe (x+)).
Then,
s (t) - e (1-1)) s (t. (s (stt, c (1--() (t.2z)) (t,
E
op
B 1 E
Ex Rr, Bere
Mre (Frede) (IT - Iz) (IT: Tzys)) T be (ITr)))) ) |
op
where ā., is an independent copy of Ir, when conditioned on Rr de is uniformly distributed over [0, 1] independent of the random variables defined above and Fra,d= = >5 + (1 Ae) Tr.
Proof. Let E 10, 1).
:=:=T+1 - -T,- Then,
B-1
(d,xx)-c-(11 (t,
Σ 0=0
a (T - - (1+1)) cu 1, c+1 = --
Therefore.
E
8 (1, (ee
-e-(te))) (l.))) (s(( e (1-r)) (1, (1,22)) la0z
Σ Gej (T(Ti)t7)) - ( (Te4))) (s (T US1
- - -0(1111)) (Tz+1 Ery 1) T l
E
op
For f j. assuming i j WLOG, using the Markovian property,
[T)) - e (t--ri (T++1, Rn..)) )) (s (1,) - e (1s411 (141))22441) 1og)
E
E
E
8 (T,, (T.) - E (1441-1)) s (T#+1, +7 (T))217) - - (15t1-71) (T)
(rsee lora
s (Tr, - e (T++ 1) (Te41, |tor [ ]myon] (s (T,, - c n)) (T5t1: lar)
E
E
E
E
E 8 (Ti, (T.) - e (t & (T(+1, |o7]]] (iyy, (s (T., - -e (1)t1- (13t1,00191)) 1o0
Therefore,
8 (x) (1-0)) (1.z)) (s
(t, |mt
B-1
E
o s -
c- 11)1 ( (T+4)) (Tr
c - 1-1)) (Tot1, Rrsr))
op
B
E
Σ
ci
- (s(T)2z))) - ( (TezI) (Tr - (1111-77)) (14z2)
|one 1
op
32

---

Note that E ss (T, 2x [T_1]] e 1 (T41)) Therefore,
(x) c (1-e() (t,zi) (t(( c (-(x-)) (t,
B
axa op
(28)
B
x
E
Σ
B (s (1), Sn, (Tr;)) (s (Ti, - 8T, (EiT)) T [
(29)
op
Using the fundamental theorem of calculus, for Triid == Metly + (1 - 21) Eees d E (0, 1), we have,
s (Ti: 2r.) - (Zr)) = [-" hr (Eruse) (ET, - Dr. dd
= Ex-21(0.1) [ (ETnA) (Ir, - Ty,))
Substituting in (29 and using the fact that I 1 completes proof.
We aim to derive a sharp bound on the quantities stated in the previous lemma. Since the Hessian is assumed to be Lipschitz continuous, directly bounding these quantities can be challenging. To address this, we employ a mollification technique. Mollification smooths a function by averaging over small neighborhood, effectively regularizing ensure desirable continuity properties. This approach is particularly useful when dealing with functions that may not be smooth or Lipschitz continuous, allows to derive meaningful bounds by working with the mollified version of the function.
In our case, the Hessian is mollified by integrating over uniformly distributed random variable small ball of radius c. This process ensures that the mollified Hessian exhibits controlled variation, enabling bound the difference between its values two points and y- The following lemma formalizes this construction and provides a bound on the operator norm of the difference between the mollified Hessians and y.-
Lemma 25. Let h Rd - R such that Vo E RR,, 1/ (x))lop S L. Let a be uniformly distributed over the unit L2 ball. For > O, define he (xx) == Ez(he(x + +z)]]. Then, for all x, E Rd.
2Ld
[1)((x) ho -
1x-y212
Proof. Define B (a, It) be the ball of radius A around Define the set B(x, E) n Bly E) and denote dip to be the lebesgue measure over B (0. Then,
he(x) helv) / M(x |n(e ()dpe(Z) / NWV + ('dpe(ZZ))
1
(ECOn) h(w)dw f B(y.e)
h(y)dy
[B(O, e)l
( h(w)dw - J h(y)dy
1
[B(O,)) c)
(30)
[1b((x) (v) < 2L Vol(s
((Oe)()
Using Theorem from 41
we have
Vol(sC) ~|1 1|1--10 v/2 Surf (B(0,e))
Therefore,
Surf (B(0,c) c))
(xr) (1) < 21, Vol (0, <)) x || vll
We have for B(0, <),
Surf( Surf( B(0,c)) = d/c which completes our result. Vok(((0,))
33

---

Lemma 25 demonstrates that the mollified Hessian he becomes Lipschitz due to the smoothing introduced by the uniform averaging over the ball 2, even though the original Hessian does not have this property. This insight is crucial when dealing with expressions such as
Bx Se he (x) (xv By) (Ee .v)) by (Zv |mg]
which arise from Lemma 24
When and E' are close, one would hope exploit the smoothness of the Hessian h, with respect to time. Specifically, if h; were smooth in the time parameter, this would allow the expectation to move inside, enabling the use of Tweedie's 's second-order formula (Lemma 22) to derive variance bounds that are dimension-free and independent of strong assumptions on the Hessian.
However, directly imposing such strong assumptions on the Hessian is restrictive. To address this, we decompose the Hessian by (zv,)) into two components:
by (ze ,) = by (I + (hy (Ir - hyre (x),
Here, the first term. hy (xv,x), leverages the Lipschitz continuity of the mollified Hessian and can be analyzed by conditioning on ze. The second term, which represents the deviation between the original and mollified Hessians, requires finer analysis that draws upon Lusin's theorem, as developed further in Lemma
The decomposition allows us to systematically address each term: The Lipschitz property of hy' helps bound the first term cleanly. The second term is bounded using probabilistic arguments based on the regularity properties introduced by mollification.
The following lemma formalizes this decomposition and provides the necessary bounds to proceed with the analysis.
Lemma 26. Suppose Assumption (0) and (1) hold. Let 1 > 1' 0 and define the following quantities:
1. Let Ze be an independent copy of ze when conditioned on Zt.
2. Ler X ~ Unif (0, 1) independent of the variables above.
3. Let Te,A Aay + (1 X) Fee, Z (t--t)))
4. Let he (-)== 2 log (pe (-)).
5. For be uniformly distributed over the unit Th ball and O, define he cxx) = Eiglhe (x+ Ez)].
6. Let ge (I = (hv (Iv. - hy, (evv)()))))))
Then, there exists a random d matrix M such that [|M llop S 2ld [1(1 A) Zn, + AZe,rll2 and
Ex The (xe.)) (Ee - ze) (I - )x)² he (x) (xre 1,p
I I (e)(t- / (ctt' 21) (ot (xx) + r hore (e' xe
+ (Branze [IAM lap || Zr. l |uo
+ Eupre 2e |IEx Igv.c (Te (x)l)))l || - Tx late]
Proof. By assumption, we have VI E Rd, |l (x)ll2 s L. Note that conditioned on Tt. we have
2 e (t-t') xp 21,1 e - (t-t') Fy + Ee,'
Where λτ, ~ N(0, If Ia) marginally. Therefore,
Ze.A d'' - -- ((1 A) 2 + AZe,e)
Using Lemma 25
he.e (zv,x) = hv. (0' 21) + +M for || < 2Ld
|| A) 20, + A
34

---

Then.
Lemma 27 provides a corollary of Lusin's theorem (see for e.g. [1] to assert that any measurable function, such as the Hessian (xr) 2 log (zr),, can be approximated uniformly compact subset Gy C [t', t] x F, where the excluded measure is arbitrarily small. This result ensures that be (x be heree + (he (x he e
he xe) + M (he (IN - (x0,)
Let qt = Ex he (are,)) (xe Te) (Ix - bn) by (I [ and ge.e (Iv
(he (xv - ber ( ()). Then, using the fact that (a+b+00 () (a+ b c) I 3(aa T + bb + tcc for arbitrary vectors a, b, Rd,, we have:
Qr 3 3 au Ihe.c (c- (IV Tx.) (ev - Tt)) Nose (et 21) l00
I=
M (xe - Te) (ow kx)) M ait
+ 3 Ba
=12
+ 3 BAngir ggrie (2V (IV- - Tx) (ov āc) gove (xv,)) l
T
Let's first deal with Ti. We use the fact that 2 = e (t-1)) xx + 20, = (t-r() ((-())xx ee + Z along with first order and second order Tweedie's formula in Lemma 22
T (c-(()) (er (e*+ (oi (2xe) + or o her (e (6- T
Now, for T2, we have
T2 = Expre :i
M (ox - Txx) (x01 - -xr) M lose
[IMe 11a0 - ze 10 lopp loo Id
3 Exiee dee
and similarly for T3.
T3 < E Ri
|IEx Leer, (fre |a - Tr ll |
Ia
which completes our proof.
hx(x)) uniformly continuous on G.,, with its continuity quantified by modulus of continuity w.GC depending only on 7. See (39] for Heine-Cantor theorem which implies uniform continuity due to compactness.
Lemma 27 (Corollary of Lusin's Theorem). Let F be convex, compact set over Rd and A be the Lebesgue measure. Let h4(x) = 2 V2 lo be measurable. For any "y > O, there exists a compact set G. C [t', x F such that A(l', (] F) G.) < and (t, he(x)) is uniformly continuous over GT, Let us call the corresponding modulus of continuity as w., O. which depends only on 7
Building on Lemma 27 Lemma 28 aims to bound the fourth moment of the operator norm of the difference hy, (z),.) h (TT.A.) which arises from the deviation between the Hessian and its mollified counterpart. To achieve this, the interval [t' []] is partitioned into smaller subintervals To, Ti...., TB. allowing the analysis to proceed incrementally. The lemma exploits the uniform continuity of (a:) on G,, to tightly control this difference using the modulus of continuity wi (c). Contributions from outside the compact subset G, are accounted for separately using indicator functions, with their impact controlled by the boundedness of the Hessian, [/ < L. The
resulting bound consists of two key terms: a primary term proportional to (w) capturing the uniform continuity of the Hessian on Gy, and a residual term proportional to the probability of (x) lying outside G.,, which is effectively managed by the boundedness assumption. This decomposition is crucial for controlling the variance of the Hessian and ensuring the residual terms remain small.
35

---

Lemma 28. Fix a B E. <1 ... < TB-1 <t:= TB- Let Assumption 7
(0)(1) hold. Let (,)x),,,c( be defined as Lemma 26 1 ball in IR,,, independent of everything else. Then for any 7 0:
Let Z be uniformly distributed on the unir
B-1
Bx., R., [|EAUUi((o.1) [1T,, (Irede) - le ( (TT |r; 1 1|
2=0
B-1
Ex,, Rig [o [[((T) (ri))) GG) + 1( Trad + +ZZ) & G.y G2)dd
(e) + 16L
Σ
1=0
where vr, is an i.dd copy u., conditioned on Eran and TTAAA == ATn, + (1 - X) _., for any given [0, and why, Gr are as defined in Lemma 27
Proof. Let consider Lusin's 's theorem (Lemma over [t', t) x F endowed with the Lebesgue measure A. By Assumption I (0)(1)) we have l x I L for every almost everywhere under the Lebesgue measure on Rdd We denote (n)-Ui(((01)) as Ex and only in the set of equations below, we denote expectation with respect to IT, T conditioned on Tra41 by E:
I [ITE (er, (Mira)) - lead (1TT,))))) [T:11]
(31)
= =1e =1 Il.. Lo Ne, ((TT))))))) - 1 Jdl [rt+
- [|||
bn, (x=T))) - h7, (ETu, + eZ) d
< E / 1((T,,
c2) E (c)
E / [1((T), GT) 1 2 G+) 16
S (e)(e)+ +B [1((T,, & GT) 1((T) Fr. + cZ) $ G.)) 16L'ds
(32)
Therefore, must have:
B
Σ
E
Ny, (xTr))) - -er,, ( (dd1))))
1=0
B-1
s Bwu(d) + 161
E
1((T,) & GG) + I(Tii + E G.)
The following lemma consolidates the results and arguments developed so far to provide a variance bound for a martingale difference sequence. Our goal is bound the variance of the terms in the sequence R,,k, which is determined by both the predictable sequence G and the smoothness properties of the score function and its Hessian. To achieve this, we build on several key results:
1. Lemma 28 which establishes bounds for the difference between the Hessian and its mollified counterpart by leveraging the compactness provided by Lusin's 's theorem.
2. Lemma 26
which shows how the mollified Hessian can be used to control variance terms using its Lipschitz properties.
3. Lemma 24
which provides decomposition of the conditional variance in terms of contri- butions from smaller subintervals.
The argument proceeds by partitioning the time interval [ (o--K,A---11 k+ into smaller subintervals and analyzing the contributions to the variance over each subinterval. Using mollification and uniform
36

---

continuity on compact subsets, we control the deviations arising from the lack of Lipschitz continuity in the Hessian. Furthermore, the variance bounds incorporate the contributions from outside the compact subset, which are managed via Lusin's s theorem. By carefully summing these contributions and leveraging smoothing techniques, we arrive
sharp variance bound that scales with the parameters A (the interval size) and L (the bound on the Hessian)
The final result, formalized in Lemma 29 also uses the second-order Tweedie formula handle the special case of the last time step (k N) in the martingale sequence. This lemma serves as culmination of our efforts, combining mollification, decomposition, and smoothness assumptions to derive a practical variance bound that is essential for analyzing the concentration of the martingale difference sequence.
Lemma 29 (Variance bound for martingale difference sequence). Consider the martingale difference sequence Ri.k, predictable sequence Gi with respect to the filtration Fi,k as considered in Lemma 27 Define A = IN-K+1 IN-K
ifk =
1-1
CiLL A + L2 2 N G||||| C(LA² |)
if {1, , N N-1} (33)
if = N
Proof. Consider the case k E (1...., W-1]. J. For the sake of clarity, we let t = tN 1 tN-k-
Then, A t' and let B N. We decompose [t', t follows:
It, f = 2
:= [t' + (Í-1A
1 7
For Vi E [B], T, (1 Z, X, Fr, Zr,A.. Ir, as in Lemma 28 and with Z, A, (z. )220 indepenent of (Ti),, J. Define the
Uni ......, .)) Given Tr, define the random variables
random variable 7" = TJ. X Fr X A + eZ. Notice that 7 uniformly distributed over t].
Let P3 = Ts+1 - T3 S B
Using Lemma along with the Cauchy- Sechha- inequality, we have
Irre (Franee) (Ioz xx) (Ir, 2n.)) he (Irenee)
[2
< 66 2r
| (e" (ot br, (Ir:)) + on Ia) Niye (e"txr))
op
22
Ex [1(11 - 2) Zrceii + AZrusi llz (rruts)
Ex Mrc [1 - 2r. 110p 1 2
?²
+ 3E _iz [IBBA 1hi, (KTLAr) o (Fr. Tr44]]
Exiaetsrr, [1a27. 2r llip 1
(34)
Using Lemma 24 along with 34 and Cauchy Schwarz inequality, we have
8 (t', 2v) - (1-t) 22)) (s (t(,xx)) (x)) - - ((-r))((tzzz)) (t, |0|
E
B
E B Brd Mnr (Etwnee) (IT, xe.) (It+ T ny, (Krwne)
ct
op
B-1
$ 6
Σ
2
Aine (e (othhr (It.) + of, Ia) hi,e (c") 11.0 1
12
B-1
Ex,r Are [1[1 2) 27un + Xurun 11 [mtm)] Exarectte [Ilaze Sr. Mopp 1
lase
c2
1=0
B-1
[1x,, ( (ITr.de) - W ( [TTe1]] Exiieegare [1a22 Rr, 11 |
y/2
+3
E
E Tir
1220
1=0
37

---

B-1
< 6
Σ
I zz) (o, Nr, (IT)) + of oe) bose (+")
11mp 12
1=0
12L'd d2
B-1
E2 Exier arc [l|C A) 2retain + Xur 11 [
|1 Tr, Ilop 1
laze
2²
$
[BBx, Mere (ETrdd)) l (E Mlllop ( )
+ 3E
Σ
Σ
E Exsee, Rr,,
|
Tr. llop (creus))
laze
(35)
35) and the observation that Exiier, Hr.. [1Lers - Fr, llop [
b/2 = 0 -0 0 ( we
Using
have
8 (v) - (e
(1.21) (s (1(( -e ((((()) (1,22)) (1,
E
|Bxx Mher (Errede) hro,e (er Illop (erets) 1) 1
LZA
1d
3Ad
B-1
3Be "
+
Σ
Ex, Be.
12
B
Be
VB
1=0
Using Lemma 28
|iE (Pim (Zr)) - n ( [ 1) 3
B-1 1
Bz,, Rr
1=
B
V. I((TE) & GG) + 1((TI, TAnT + +eZi) & G.))dda)) )
< VBwu(e)) + 2L2
E
S /BBu 2T? (B (P((T, X) E G2) + ((T,)X)) & G.)))
Therefore,
-(((()))ss s (t',, (v) - (et(t-t)s (t. (s(t'ze)) - e (1-r) (1-1)s st. |2]
E
(LAA²
L2A
12A
I 6Be
B² +
+
(T) Be² + +II-Ad (P((()+(P((TTX))) & G.) P(T, & G.))
B
Notice that none of wy. Gy. distribution of T, X depend on B. Therefore pick e - 0 and B + 0 such that 1 - and (c) + O. (T, X2) + (T) almost surely as e + O. Then, we BeZ
take y 0 and argue via continuity of the law of (T, () with respect to Lebesgue measure that
P((T,X) & G-) - PPT(TT X) & [t', f) x F). Since F is arbitrary compact convex set, we let F 1 Rd to conclude the following:
E
((',,)) -e e (1-t) (1, x.)) (s (U,
e (1-+() (1.)
10z
- (36)
op
Using Lemma 23 we have
E
(E
[ [r]]
E [rr bo (E [mooars] E [xol [
$ 2t
(o (zx) + o. llop
+ 26 26 of
12 ((() - c (1-10) (1,21)) (1( (1-1") (1.)2)) (t.
10t
lp
00 (LA² 2 + A + 1²A))
The result for N then follows due to Lemma 21
Now, consider the case = N. Recall Σj, defined in Lemma formula (Lemma 22) we have Σ,,, = of hi (ate) + of la S A + A. Combining this with Lemma 21 we conclude the result.
21 Then by second order Tweedie
D
38

---

We state useful corollary which is subsequently useful for time bootstrapping and is implicit in the above proof.
Corollary 1. Let t' < and A = t-t'. Then, under Assumption 7
s (t,,z)) - c- (t-t)s (1,02)) (s xx) e (((1-()s
l0t oo
- -
Proof. The proof is implicit due to 36
Lemma 30. Fix ā E (0, Consider Ri,k and Fixk as defined in Lemma 2 and let A = LN-K+1 tN-k- Under Assumption
7 following the definition in Definition 7 conditioned on Fi,k-1, Rr (B "s.))-suGGuussinn where Br W., are Fak-1 measurable random variables such that Wi,k I log (?) with probability at-least 1 and
[8 + 1) ex anvddd [N 1),
Bi,k 14V N
Proof. We have,
P (( B[10 (8) | [ Bizb
(8) (5)
JeN- | 2 aFFFn-i)
P ((..++ Biay PN-- - B[1
(1) (1)
1)( 2 a aF(Fio-1)
eN
IP exp ( (i (2)
Blu (1) (8) )
2 exp (Aa?) |Fi
< exp (-Aa²) ?)
E
exp
G B[r0
(5)
2
Bi1 [ix- .1)
|Fr
2)
exp
(-Aa²) E
> GG
(1)
Bl1
|F
S cxp (-Xa²) 2)
E
exp A A|I
11
B|a0
(8)
- E Blz0
PiN 1/²
(1)
Since Gi is measurable with respect to Fi,k-1, set
1G Bogd for pa defined in Lemma
Pk = 8 + 1) - Jm
Therefore.
E(10 (2) (3) P (1 GiA,,,,,
E[ 2 FeN- 1) 2 alFF.a-1)
(8)
E[ (4) (8)
S exp
E
exp
Fro-1
||G 112 p&d
RRd
Note that Lemma 11 shows that Elar
(9)
<12] - B 1 .I is pk vd norm subGaussian
(2) (8)
Biro
(8) (5)
[ - -B(z0" (2) (3) 1
| 2
exp
2
pZ.d
Therefore, using Markov's 's inequality, with probablity atleast 1 - 8,
B[r
(4)
E|-00 1o1 (5)
E
exp
Foa-11
pfd
1irr (3) |2
(6)
1
Blar
++
2
EE
E
exp
F
5
(37)
15.d
39

---

Pluggint these equations above, we conclude that with probability at-least 1 - 6. for every a > 0,
we have: P (1 (G.,,+1. H|=0 ( | a11
E
( I .)) 2 a F _ which
(6)
proves the result for & E [N-1]
For = N, we similarly use the definition of vs Lemma 12
:= 40
we have,
(
P (((o,
-E
(8)
(1) (8) |> 2 al
Fi. S exp
a² ||C;
l uRd
E
exp
E
v
12
Frre-1
The conclusion follows by a similar argument (37
Based on the bounds established in Lemma 29 and Lemma 30 we establish the following results.
Lemma 31. For j [N), Let 1j == Aj and 7 A. Then, for some universal constant C > 0 the following equations hold:
Σ
& S +1
N 1-
+ TT- Σ Σ [((tt,
[E[M],NE[N]
(E(m) j=1
and
max
sup (E/m]
3i,N N W ||
[Gil,
sup sE(m] KE(N-1) []
3,, Wi, Gis+tll
s C(L+ 10+4
dsup Wa, sup [I((te, al)) ( i,k
i.
Proof.
Define -6 = (LAA² + A + I2A).. Applying Lemma
29
we conclude:
Σ
E[R FF S Σ
(LA + 1)
Σ
(LA2 + LE - 2 1|
[E[
kE(m]
kEIM),EE(N-1)
TGe (By ta) C(t, ((ty)
(t. (t) 2 2
96
A
90
Σ
of
o
xE [m]
j=k
(ly (x) (W)))()),, 22 (9)
2290 90
EE m
N
201y (4)
A 90 <
Σ
[C(t,, 21 (3)) using
incquality
Ti
mm(m]
j=k
j=k
N
N
2 90
Σ ||((t, 11
EE
j=k
j=n
N
N
22(2 R)
N
< A g0
Σ ||((t) (9)1
(1 e ))
vElm]
7
j=l
N
2 2
1---Xx
(I-E-
Σ m
> ||c(,, (2
using Lemma 13
(38)
1=1
Recall Bi,s, W.e as defined in Lemma 30 Applying these results along with the union bound we conclude with probability 1 - 8, the following holds every k simultancously:
40

---

max
sup
B,N V Wi Gill,
sup iElm ke[N-1]
3r / Weall WiallGGatill
sc|m]
+CVA(L+1)
d dsup & max
sup xopp (G |G,11|
i.k
+CVD(L+1)
dsup Wi,
((y-t)
sup
suproll<(te:... 2 1.6
(2) [|. using Holder's inequality
CC +1) 1V
dsup Wi,k i.k
1(5-11
sup IIC(tte (0)) i,
1-e-2ja
j=1
COL ()og() dsup Wi sup (Ct,, ( using Lemma i.k
We will specialize the setting in Lemma
17 with M, being given by H, the filtration being Fix
and the martingale decomposition given Lemma 20 Similarly, & corresponds to (Bi,))i, K; corresoonds to (Wa,)). given in Lemma
30
2/ corresponds to the upper bound E[R 1 Fi,e in
Lemma 29 Therefore, Ji corresponds to max(1, W.E log(
C
satisfies J4 S C'loog22) for
some constant C. In this case, the quantity > Gii1 M² G 12 as given in Lemma 17 corresponds to E E Fi and it can be bound using Lemma 31
Σ (E[M]..E[N]
E FaA-i] CL +1 +1) - (1--
Σ (1) (E(m) j=1
Σ
Similarly, we adapt Amiu- X be the random variables defined in Lemma 17 to our case for some arbitrary B E N, > 1. This lemma demonstrates the concentration of the quantity H conditioned on the event B = (mmin X E le-B ,eBB], It remains to deal with the following cases:
1. Inax(Amin X²) B
2. min(Amin; x²) <
First, consider the case max( \uiins X*) e Lemma 32. Assume "t- A, A co for some universal constant co. Then max maxx(Aii; implies
Xt) e
CNmm -2B
Σ
II((t, 11
A E
RET
Proof.
Using the fact that 1, we note that
max X²) > e
max( sup rElmi kE[N-1]
V -N |
sup
V < Cvae B for some universal constant C
iE|m]
(39)
By defining Gi, 0 and, note that o2y-24, el CNN Gi C(tN for l < N and o2, (G. - e G = 2t,, Using the fact that of < for some universal constant co. conclude that
(
41

---

max maxx(Amn:: 13) > E
sup 1s((t, 2, 5 emm..EE
A e
a
Σ x| ((1,, )12
CNma 22
A E
(40)
iE
We now consider the event min(X) Amiu) < <e-B.
Lemma 33. Assume "tt = A, = jA, A < for some universal constant a > 1.
min(X,, Amiu) < se- e-B implies:
Σ
2f )12 2B
md log (2d)(L 1)2 sup,, Wi,
MET
Proof. is easy show that min(X", Amin) < <e- implies:
eB
max(sup 2 (GG4+1ll. ||
log (og(2 m) W
i.k
This implies that there exists i, such that
IC(1,, (12 (8)
B
2 C
N (lgg(2d)(L + 1)V mdd WiLk
We then conclude the result using the fact that o², 2 co
Lemma 34. Assume NA A for universal constant co. Assume t; Aj and 7j A. Let a > and B E N. Ler TL(()) = Eie[m].ET [|5 x; )12 (C) = SuPre(m).tET 1I((t, x )l-- Let mmax log( ) l2g(2d) y dd sup,, W.k Then with probability (2B 1)e at least one of the following inequalities hold:
1.
L+1 -
+ Callooo (5)
2.
CNma -2B
L3(() <
A
3.
2B
LZ(() 2 cp mdN2 2 (2 (L + 1)2 sup,,k W.,
Proof. As considered in Lemma 17 define the event B = ( (Amin= X E BBB. Applying Lemmal 17 to our case with the martingale increments as defined in the discussion above, along with bounds for the quantities En= vz² |2 and sup, J.3 G as developed in Lemma 31 we conclude that:
1. Almost surely
Σ G < (T+22 Σ
I(((,,(())1
(E[m],ET
42

---

2. Almost surely
sup J.B. K [ 1) log log 3
/dl
dd
sup i.k
Wi. sup
1|s 22 (1)
|||
iE MET
((141 H L+I CVNNALL3( CaL (1) nB) S <2B + 1)e
(41)
Define the events B = {max(Amin )²) > e cB) B₂ == {min(Amin: 1²) < <e=
L+1
(V + Calloo (S)o
By Lemma 32
the event {LL(() CNma
A e 2B C BT. By
Lemma 33 the event:
Ae 2B
(L(() mdN² log (2d) L + 1)a sup;, Wi,
C B
Therefore consider complement of the event of interest in the statement of the lemma:
An(13C1 (3(() CNmm
2B In 13(1)
2
A
mdN2 (2 1)2 sup,,e W.R
CAnB nB
= (AnBBB n B.) u (An n BB n B3)
Clearly, PBB U Bi U B2) 1. This implies P( n B B9) 0. Therefore, using the above
inclusions along with Equation (4I)
we conclude:
P (AAN(L3CS 13(0)
CNmo 2B
n B
SP(A) < (2B 1)e=a
D Convergence of Empirical Risk Minimization
Lemma 35. For f E H. let ut of
(9)
and
7 (()))
(0) s(y,, ( ||
C(F) =
Σ
iE iE(M)
m
H E
Di (f (8) sttg, (1) ) Vi, - s st,,, (10))
(8)
[E(M]J[[N]
If E H then for f = arg inf sen [(f), have
C(f) < H²
(42)
where C is defined in (4).
Let Vi (1)
(6)
Proof.
We have, for any f E H.
og
7t (t (1) - st,),21)) s (t))
(0) Vi,
=()=((s) - +
Σ
(43)
m
JEIM)
43

---

7: 7:/0(bneef)) - "1 Since f is the minimizer, L (f) - Ls). There-
where [(8)= [iE[m]jjE[N] fore,
To (f(( (b)x()) v11)) (4.,
Σ
sE|m].JEMM
which completes our proof.
We will first demonstrate very crude bound, which will be of use later to derive finer bound based on Martingale concentration developed in previous sections.
Lemma 36. Fix å E (0, and let U): := = 4I E T, A <<L. 1. Furthermore, assume a linear
ai
discretization, i.e, tj Aj. For L, C as defined in Lemmal 35 and f fegmin we have almost surely:
2 (f) - (s)
we have with probability atleast 1 -,
(()) C(NA + log( 1 ) log( log("*) mi
Proof. Using Lemma 35 and the Cauchy-Schwarz inequality.
T (f (1..
(1,,a))) Ueg $ (t 15 ())
Σ
/ (f) (s))
[E[M]
which completes the first part of the proof. Next, we have
(t) x4
( Vi
Y
(8)
m
sE(m].JE[N
Clearly, since yi is marginally Gaussian we conclude that it is dyd norm subGaussian (see Definition 1. Using the fact that a(), is the conditional expectation of yt (1) Lemma F.3. in [4] shows that s(t, x2) is 4vd/o,-norm subGaussian. Therefore applying union bound over all ||s(t, xx (2) 11sb 11
/dlRR (m))
with probability at-least 6 the following holds:
Oe
ΣΣ REIM]&ET
8 t, x
(8)
Vi < Ad log( Na Σ
1
m
SET
Now, note the fact that o, 2 co (l, for some universal constant co. Therefore, ΣIET J/2 S
N log( 2 Plugging this into the equation above, conclude the result.
Lemma 37. Recall Vi (1)
( of for all E T. Let for f H.
(1) (3) yi, 74 ($ (t) (t),
H
m
[E(m].JE[M]
Then, for
(u' (
Uu (uw'2aNtenssEo))
p SP
JEF
where C, E, are defined in Lemma 35
44

---

Proof. From Lemma 36 we must have L(f) - ((s). Therefore:
P
H 26)= P
U HH' 2 20 M fis minimizer of 2
VEH
[H' 2 c) Nfcu)
U FEH
Lemma 38. Let E H. and suppose Assumption 7 holds. For any fixed To > 0, with probability
1 8, the following holds for every f H:
- Iet - LV dro) - - -2e
Li|l 211120,,40l
(f(t, - [1]
II+To - st+ T0 -00 dro) -2 L1 ||
Proof. Let g(1,,)) == [1, xl) Note that Tetro = 21,4+70-
By Assumption
g is
2L Lipschitz in x and with probability - 8 over Ietro and every f E H:
lla(t + To. Ts+r))ll II
2 (1) - llg(t To, T2+ro) c"h g(t
2 e (lg 21 gg[ T2tT)) eTh g(t eth re+Ta)ll 20 " x4400
xel
2 - (l. 21)l - 0 L dro log( 2c 20 1
(44)
We conclude the second inequality with a similar proof.
Lemma 39. Under Assumption 7 with probability 1- 6. for universal constant C 0 the following holds uniformly for every f E H:
( sup || (t), - (ty. (11. s SCA
Σ
Il (ty. - s (ty. 12 + CCLdA 3
log
Nm
(E(m) JE[N]
iE ml JE[N]
Proof. For the sake of clarity, we will denote g= f - s. Using Lemma 38 via the union bound [,]
for every ( = 1j. To = |6 - 4x. along with Gaussian concentration for =1,4+%0 we conclude that with probability 1 - 5 the following holds uniformly for every f E F, i E [m]] and j. E T with Ij - A < for some universal constant C.co > 0:
1 (,) (3,= 2 cal15 (ts, (11 11)
-CL k|A log( Nm)
Squaring both sides and using the AM-GM inequality,
| (t) s (t,,
cb ||5 (t2. ((1) tk 11(0 13 C² -c k| log( Nm)
(45)
Now, let (i+, k²) E argsupie m) ME[N] (ttt, (0) - s(tu, 2(tx, (1) )12. Now, for any j such that |0 A < 1, the Equation 445) implies:
Σ
|| (15,011)) (10)
Σ
|| (1,,11))) - (1,,a1"))1
kE[m]JE[N]
Σ
2
(
(Ix-, [ -C22)
C3 - k2 | Aoog( Nm
2
J:1 k |S/A
45

---

This implies the following inequality from which we can conclude the result.
Σ [t,,2!)) (b) l0= [e[m].JE[M]
241/3 (tw- o (t 1[ 20 log( (mm
of
Theorem 1 (Empirical L2 Bound), Let Assumption 1 hold. Fix E (0, 1). For all j E [N), let l := Aj and Y == A. Let = Cloog ((L + 1) dmnN log (+) / for an absolute constant C'
and ler log ( ( )d log2(2d) log (2 log B|H
I and NA I C'log( ). Then for
(L + 1)
B 5
log
NA
6
with probability al least
(3) (1 (5))a( s (1)2z()
S e
SEIm].JEIN]
Proof. Consider L(J) defined in Lemma 35
H$ as defined in Lemma 2 Let f be the empirical risk
minimizer. Then, by Lemma 35 we have: L(F) H¹ almost surely. Then, using Lemma 37
have: L(f) S [(s) almost surely.
As per Lemma 36 we pick UB = C(NA + log( à log(
((g" for some large enough constant C
and conclude that
I (C()) UB) -
(46)
Let f E FF be arbitrary. We consider the martingale H developed in Appendix C with { = 5-f
In this case we can identify H1 H. Considering the notation given in Lemma 34
have:
Lī(C) = - C(f). Let a log( 101H1(2B+1)). By Lemma 34 we conclude P(AI()) U Aa(f)
As(l)) 2 (2B 1)e-a where:
1.
Ai())
L L+1
HI
S SCV
aNAC(J)
Ot0 0.0max max
sup
[f(,, (8) s(t,
iTET
2.
:=ff)=(((f) & CNm2ae 2m
3.
2
Aa(f) = ((f) 2 co d.N2 log" (2d) 1)2 supi. Wip
Taking union bound over all f E H. we conclude that f satisfies:
PP F(A(())AA(CUAACC))) 1- (2B 1)
Since log( 10 (2B+1 ), we conclude:
8
21 8
(47)
4
46

---

By Lemma 30
we conclude that with probability 1- - sup;; Wi, I log( 6
Now, consider
(sup W., I l P(As(f) & P(As(f)
8 }}} + PP ssu W log( 8m
}}
8
i,k
i,k
8
s P(Aa(f) (sup W., S log( &Nm }})
<P (f 40
&Nm 2B A
))
+
dN² log (L + 1)a log(
s P ((c(f) UB}) 4'
(by using the definition of
8 2'
(by using Equation 46
(48)
Now, consider the event A2()) It is clear from our choice of B that following inclusion holds:
(c()) د s As(f)
(49)
Now, consider the event A A1). Define the following events for some large enough constant C.
C c= N1EF
sup
||ʃ (1,, (455
iElm]
jE[N]
S CA3
Σ (1,)) (1y, CLL log( Nm [m(m]
NEIN]
D = (= < C'loo( + log(2d) v dA log( Nm
Lemma 39
have P(C) 1- &. By Lemma
30 and union bound have sup,, W., log( (N
with probability 1 8. Therefore, P(D)
Under the event A1 (f) nen D we have:
1. c(f) < H (This holds almost surely by Lemma 35
2.
H$ = c(L+1))
aNAC(f)
+C(L+1)
at max
113 /m((f)++ + LVdA 1/0
Vlog( Nm
m
m
3.
Omax S Clog( ) (2d) v dA log(
Using the choice of A being small enough stated in the Theorem, as well as our choice of a, we conclude that under the event (i) Ci n D, for some large enough constant C':
oNAC(f)
+ C. (L+1)
c(f) cC((LI)
FF (L + 1)2 log (1/A) log(
((()) <
m
47

---

Therefore, under the events (Ai(f) O nDnc)uAA(f). the guarantee for L(f) stated in the theorem
holds. It now remains to show that ((410))nn))4A()) 2 ó. We begin with
Equation 47
1 4
8
=TAIDUAAA)++ +
by applying Equation (48)
P(CA))UAA()))C))))+P(((UUUU ((CCA((AA((()))CCCC))))))))))))) 8
(PCC))))AA()))))))))))))) P(DD)
6
2
38
(((A(()A(())CC)D)))) bound P(C),P(D) given above
35
38
(50)
This demonstrates the desired result.
E Generalization error bounds
Lemma 40. Let all ff (t, H. be parameterized (t. x; for 0 O R C that h (1,z;;;0 0.) = s (t, 21). Suppose 'Y2 μ 2 0 such that V0 O
and f2 be such
l (t, (1:)0))) 0) (t, Fr. 04) $ x2 ||0 0.1|*
and
llg (t, oz; 0) g (t, x. 0.)1
2 μ ||0 0_1
Then, all f H satisfy Assumption with A
Proof. The proof follows by squaring the second inequality and comparing with the first inequality.
Lemma 41. For timestep 1 2 O, let di be defined as in Consider function f IR Rd + Rd
such that 3x satisfying,
(Ex, (t, st. -(t(tt,))ss((())]]]] S (Bn, (t, (t.,a)))
Let X = {2) iE(mi be iid samples. Then, with probability atleast 1 - exp (- s there exists
(8) (1)
set 9 C [m] such that |G] BK
m and
| (t.x (1.2 1 Ez, [llf (t, (t, (t, 21))
W,
Proof.
Using the Payley-Zygmund inequality, for any i E [m], vo E 10, 1].
Exg Il (t, [t, (t,
(t, xx) 1
(11( - (1, 2 OE [15 (1, (1,2:)11)) 21 -02
Ex,
(51)
Define the iid indicator random variable (xilsejm) as,
Xi = (1)((1.))))
(1.2 - (1, 1|3 2 Er, (t, (t, a2,1)
2
48

---

Then, using (5T) (x: 1) 2 1 for Bernoulli random variables,
Let Σ
E
N
m Ax
Using standard chernoff bounds
Ve (0,1), P
Σ Cx
eexp
The result then follows by setting 6 = 2.
Theorem 2 (T22 Error Bound). Let Assumptions
hold. Fix 6 E (0, For all j [N]. let Aj and 7 == A. Let B == C' log ((L 1) N log (+) /A) for absolute constant C' > 0,
and 2
and let A log 3 ( dd logo (2d) log (2 log
B BH
< and NA S Cloo( ()
N
(L
1)²
N
BHH
m 2 R² max log
log
22
then with probability least 1 8,
Σ [IIf (1y, (Li )12 S²
75 Bay
JE[N]
Proof. Using Theorem
D we have with probability at least
6, 7i | (e,) s (c,, (L+
log
B|K!
(52)
JEIN
Using Lemma 40 and 41 if m Z x² log (*) then, using union-bound, for all particular timesteps (Li)ee(N with probability at least 1 - 8,
My (1)) -8 (1,,)
R22 Me But, [|| ((). - (1y,
Σ *E[m]
(53)
Adding over all timesteps (ts (tNNEENNI
nh (t,, (1, (t,,
Σ nc, Ess, [[((()))))) - (ty,, (1y, JEIN]
S xx
NE [E
(L + 1)
log
BHH
2A
The result then follows by setting the RHS smaller by e².
Theorem 5 (Accelerated Inference). Under the same assumptions Theorem 2 partition the timesteps {t, = AijjeiN) into k disjoint subsets S1, S2...., Sk, where each subset S, contains timesteps of the form t; = A(i + mk) for m E N. Define Y/ == k& for all j in any subset S.. Then, there exists at least one subset S, such that:
Σ En, [1((),00) s(tj, 11 JES;
S 2e,
with probability at least 1 1-66 8.
Proof. From Theorem 2 we have with probability 1 1 6:
Σ 7 Emy,
|| [() - s(1y, )11 se.
JEIN]
49

---

where 7/ = A. Partition the N timesteps into & disjoint subsets Si...., Si. as described. Each subset St contributes:
Σ jES.
7y Bai,
[|((0))00]) -o()))
slg. =l(),
[1((),)0)] 5l(,, Feey) [13
jES.
Summing over all k subsets gives the original total:
A
[| 12,) - s ((15; S6.
ABny
JES:
Now scale each subset's step size by ls (i.e., 7/$ kA). The contribution of subset S; becomes:
Σ Be
- s( k Σ AEEr,
[15C),,0,,] s(t),
jES.
JES:
Summing over all subsets with the scaled 7/y. we get:
[[(())))))))) s(t,, -
| s(t [2] $ ke²
Σ Beeg
Σ
A
i=1 JES.
JES.
We conclude that at least one subset S; must satisfy:
Σ C,,,,,, [[((ts,20,) - s(t,, 21, 11/ SC, jES:
since otherwise all & subsets would contribute more than e², leading to total exceeding ke?. which contradicts the scaled bound hc?.
F Dimension Free Experiments
In this section, we describe our experimental setup for the experiments conducted in Figure I We implement DSM samples drawn from (0, Σ) using Omstten-UUllebeed schedule with 5.0) and a two-layer MLP of hidden size
aj = exp(-20t)) (0 1.0,
1000 that
concatenates the noisy sample x E Rdd with a scalar time embedding // - 1) E [o, 1] to predict noise 2pred- A random covariance Σ = QAQ is generated from a GOE matrix with eigenvalues Ai Uniform(1,, 2). We train for E 200 epochs Mirain 1000 samples (batch size 1000, learning rate = 10 10-3) and evaluate on musst = 1000 held-out samples over N = 100 timesteps. For each dimension d E {10, 20, 30, 40, 75, 100, 125, 150, 175, 200) (each averaged over R runs) we compute the per-step MSE Ej = (1/mest) E average Es over j = N and runs to obtain a time-averaged error, define the scaled error E(d) (mean time-averaged error)/ (# (#params(()) (dl) loglog d), and plot E(d) versus d on log-log axis alongside a best-fit linear curve. Our experiments were performed on single Google Colab CPU.
Σ,, 21 / /I- āy
50

---

G
Bootstrapped Score Matching
Algorithm 1 BSM
((20) (e(m)
(0)
T,N, (HH :
(1)]
Input: Dataset D := 220 selm]
Initial Sample Size m, Number of discretized timesteps N < tN = Sequence of Function classes {H.) {HA)) Ko E N
labelled as to < t < <...
Output: Estimated Score Functions {st, JNE[N] to optimize Exy, [1s(te. s(t,, Ft, )l{
for k E [AV] do
Let Vi [m]]
(1)
so ( + 2(()
if le S ho then
8 + arg minseHa #h Eie(m)
((t,,21) (1)
(1)
> Denoising Score Matching (DSM)
end else
Nh f to tk-
akk + " 1_ 2ik-1
b Bootstrapped Score Matching (BSM)
1-c 21x
))
2/
9i
(1 ak)
oi
+ ak
o2
0ip-1
Bootstrapped
Targets
(13) [(tta
8ic arg E9H Eie(m)
Learning with biased targets
end
end
Lemma 42 (Bootstrap Consistency). For some a >, let
2t o
(1(()))))
2x
De
o
Then, [ stt, x²))-
Proof. Note that by Tweedie's formula.
(V', xx)
2z'
Fip'
Therefore, using the Markovian property, have
E
xx)
-z
[rt
= E
E
(1',
2z'
loir, Jt loce
07.
E
E
(t',,
-2
1o0e
0
Finally, the result follows using another application Tweedie's formula which shows that (t, ([-z//ollza)
Lemma 43 (Bootstrap Variance). For A t - t' and e o 2y oj
o7 ler
I (((2 (tt'
o
Then, under Assumption 7
E (Vr s(t, xx) s(t, xx)) [z] 11 =0 0 1)A
0f
51

---

Proof. Using Tweedie's 's formula,
St (2+) = E
2
21
21
8 (t', 2v) == E
2
2/'
2'
Using the Markov property,
E s 2x))
2x' Of
It
= E
E s (t', xz0
-24
Et
= E
E
s (t', xe)
-2
De'
It = 0
Therefore, E [ha,e [mr] = O. Let ua. == 81 (xx) as (t',zz) and Fe,e" == 0z a 54.
First consider ri. We have using 11, 2t e (1-11) z4 + 2n, where 2t,1" ~ ND( 03.0) Then,
21
Zx' a
- zn + 2.,""
2t'
e
a
2t,t'
Ta
of
of
a
0
-
dx
z
+
ot
(54)
Next, for va,er again using Tweedie's 's formula,
E
Ft
0.
(xe) = E
Jit
00
((',)))
o
E
2x
2t,0'
Ft
as (1', xerr
E
Tt
E
2t,
Ft
as (1', xx.)
of
of
oi
E
E
Ze
Te,,
F4
2
Tt
P 8 (t')
07
EE
E
of
Tt
E
41
008
(1', (1',)))) xe)),
using the Markov property
oE
E
0. (t',
E
Tt
+
a
e of
A
E
Tee [see]
o
o
0/
Z,,e"
e-
a (E [s ((,,)) [are]
8 (1,
-
Tt
E
|ze
[zre]
(55)
o?
a
o?
Therefore, using
55 and (4).
ÿr- s(t, = U1,e + Tt.
(a a
e-A)
= a (IE [s (t', (1", xx [ - - st',,x))) xx)) +
(2, - E [2 (x)) +
(Ev
EE [2v (x)))
07
of
-a a xr) [ar]] (t', xxr)
(2,,0 E3 |2 (zr)), using the value of p
(a s(t, - 8 (6', xx)xx))
+
z
(2,,1 + (t,, using Theorem from
o
Therefore,
E
(0:-
(t), - x(t, [3T]
20²E
e (t-(1-))) s(t, mi) st'', (t') (e (e-(e)))(tt, ((t, - (t', 20)) l
2
(nr + 2 o x()) (E + o(1, T [122]
+
20
(o-(t())((t))))) - (1' (o-10-))(t (t,, x4)) (t,,xx)) |
+
2
(0-
(o + r using Lemma 22
where he he = V² log(pe(zs))
of
52

---

which implies.
| (Dr- - stt, x() - s(t, T | llap
S
2a
1 (e xz) s s(((xx)) ((-1--))((, - s (t',
l0g
2
+
)o)())((11)) + o
oi
1AA2 +
0
+ +o2122)
using Assumption D and Corollary
of
(L2 [L'+ + 1)4
0
of
G.1 Experimental Details
In this section, we provide some preliminary experiments (Figure 3) with the Bootstrapped Score Matching algorithm described in Section[5] The formal pseudocode has been provided in Algorithm
Gaussian: : L2 error vs timesteps
GMM: Empirical vs True Density
DSM
0.004
ESM
3VM Density
0.003
0.20
0.002
0.15
0.001
0.000
200
400
500
800
2000
0.00
-10
10
15
Timesteps
Value
(a) L2 error for multivariate Gaussian density
(b) Empirical density for a mixture of
Gaussians
Figure 3: Experiments with Bootstrapped Score Matching. (a) represents the L. error at each timestep while performing score estimation for multivariate Gaussian density. In this case, since the score function is linear, (4) can be solved exactly without a neural network. We note that BSM significantly enhances the quality of the score function. (b) explores multimodal densities, specifically a mixture of Gaussians. Here, we use a 3-layer neural network to represent the score function and plot the empirical density learned by using (2) with different score estimation algorithms. We note that using score bootstrapping significantly enhances the proportional representation of the minor mode, leading to a fair output. We provide details of the experimental setup in the Appendix Section G
In the first experiment, we study the accuracy of different score estimation methods in the context of learning the score function of Gaussian distribution under the variance-reduced Bootstrapped Score Matching (BSM) objective. We compare BSM with DSM to evaluate their relative performance in estimating the true score function across different timesteps. Our target distribution is d- dimensional Gaussian distribution with covariance matrix Σ E dd constructed as Σ = 5MM 5 where M E Idd and E ddx1 are sampled from standard normal distribution. We generate m = 10000 samples from the target distribution. Note that since the target density is gaussian, the density all intermediate timesteps, Pt, also follows gaussian distribution. The time evolution follows an non-linear decay model, with N = 1000 discrete timesteps sampled as: f; = linspacee (0.001, mmax; 2 where tmax = v5. The noise covariance scaling factor follows o, = /1 e 2T_ The bootstrap ratio for BSM is adaptively chosen as 1 - (a:/(ot-r' + oz)), where t represents the previous timestep. The score function estimated using the standard least-squares regression solution on account of the simple target distribution which implies linear score function of the form st,, æ² ;= A₂ for some matrix A, We run 5 training epochs for the first few timesteps (1 S 3) and epoch thereafter. We plot the squared error of the learned score matrix, A, against the true score matrix, A, at all timesteps.
53

---

In the second experiment, we move away from the Gaussian density, which is unimodal, to Gaussian Mixture model (GMM), which is multimodal. We fix the dimensionality of the data as d 1 for ease of visualization, and generate a mixture of two gaussians with means +5 and mixture weights 0.7 and 0.3 respectively. We generate m 10000 samples from the GMM. The time evolution is linear with N = 1000 timesteps. We train a 3 layer neural network with hidden layer dimensions of 10 each, separately for DSM and BSM. We train the neural network for 100 epochs, with an initial learning rate of 0.05, using the AdamW optimizer, along with cosine scheduler to manage the learning rate schedule. The number of warmup steps of the scheduler are chosen to be 10% the total training steps. When training the BSM network, epochs. The bootstrap ratio is fixed at 0.9. Once training is completed, we sample 10000 points using the learned score functions to plot and compare the empirical density. Our experiments were performed on single Google Colab CPU.
start bootstrapping after ke 250 timesteps and 90
54


Reviews:
[{"review_id": "54v3RlY0Xq", "reviewer": "Reviewer_6emv", "summary": "This work obtains sample (and time) complexity bounds for estimating the score. Assuming that the score may be approximated in $L^2$ and that the score is both spatially and temporally Lipschitz with sufficiently nice parameters, they are able to show that the dependence in dimension is only doubly logarithmic. Namely, the best score estimator in a sufficiently regular and expressive class has $\\varepsilon^2$ error if the number of samples used is $O(\\log \\log d)$.", "questions": "**Major**\n\n- The step-size condition in Theorem 1 is unreadable. The factor $d^3$ appears to be outside the logarithm, but this is very unclear. Remark 2 appears to clarify that this does not affect the statistical rate.\n\n**Minor**\n\n- In related work, Markov should always be capitalized\n- subGaussian should be sub-Gaussian\n- Ito should be \\\\^Ito.\n- Equation (3) is strange, the $-$ sign should be outside the fraction.\n- L. 114: gaussian -> Gaussian\n- L. 115: datapoints -> data points\n- Figure 1 caption: atleast -> at least, similarly elsewhere.\n- L. 232: F.3. has an extra period.\n- L. 250: tweedie -> Tweedie. Also appears elsewhere.\n- L. 258: hessian -> Hessian\n- L. 265: proof Freedman -> proof of Freedman", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The work purports to obtain dimension-free statistical rates for learning a Lipschitz score under relatively standard hypotheses, \n- There are significant technical contributions: leveraging the temporal regularity via a martingale argument, which could prove useful in other domains.\n- The BSM algorithm is interesting as a method for variance reduction.\n\n**Weakness**\n\n- It seems that a large price ought to be paid in time complexity ($N \\sim d^{3}$) in training, compared to the standard analysis. Is this trade-off reasonable? It is not really clear to me how Theorem 3 fits into this picture in terms of the concrete guarantees.\n- The paper is very difficult to parse and should be thoroughly checked for typos. I have highlighted some in the main text below, but have not thoroughly checked the appendix.\n- Spatial Lipschitzness appears in a major way and also justifies the temporal regularity. However, a more reasonable hypothesis might be time-varying regularity (in both space and time).\n- The dependence on $\\log \\lvert{\\mathcal H}\\rvert$, while standard, means that it is difficult to achieve these dimension-free rates for practical classes.", "was_revised": true, "final_justification": "My primary concerns were addressed in the author response, although I still have reservations about how some of the details were communicated in the text.\n\nNonetheless, I think the paper is sufficiently novel to merit acceptance, although I would not be opposed to rejecting it.", "rebuttal": "We thank the reviewer for  acknowledging our technical contributions and providing helpful technical feedback to improve our work. We will thoroughly check for typos and improve the exposition as suggested. We address the main technical concerns below. \n\n## Training time computational complexity\n\nThe main concern raised by the reviewer is that setting $\\Delta = O(1/d^3)$ can make training inefficient. This is an important and subtle technical point. We explain why this does not affect training complexity with a short exposition on statistical error vs optimization error in diffusion models.\n\n**The Statistical Formulation**: The standard loss formulation in both theory and practice has time discretization $\\Delta =0$, corresponding to an integral/expectation over time. See Equation (17) in [Ref1] and Equation (7) in [Ref 2].\n\nWe consider a fine approximation of the integral with $\\Delta = O(1/d^3)$ due to purely technical reasons since a $\\log(\\log(1/\\Delta))$ term appears in the error bound. Note that $\\Delta$ can be made much smaller than $O(1/d^3)$ due to $\\log\\log$ dependence. \n\nIn fact, due to assumption 1, the difference between the integral (i.e, $\\Delta = 0$) and our loss is $O(\\sqrt{\\Delta})$. Therefore, we can consider the standard integral formulation of the loss as well with a few additional lines of proof.\n\n**The Optimization Question**: The integral or the large sum in the loss function is computationally intractable to optimize directly. Hence stochastic optimization algorithms such as SGD or Adam are used. Here random batches of datapoints $(x_0, x_t, t)$ are drawn to evaluate the stochastic gradients. When the times are sampled randomly, we obtain unbiased estimators for the gradients of this loss, even when $\\Delta = 0$ (or when it is very small). **Therefore, practical training of diffusion models can be performed efficiently even when $\\Delta = O(1/d^3)$.**\n\nConsider the widely used github repository in this field, corresponding to [Ref 2] (user:yang-song, project:score_sde in github):  In the file “losses . py”, the times during training are sampled uniformly from a continuous distribution when _training.continuous = True_ in config and they are sampled from discrete grid when it is set to _False_.\n\n**Our Contributions**: In learning theory, statistical convergence rates and optimization complexity are usually studied separately. In our work, we study how well the minimizer of this loss function behaves by **obtaining statistical error rates, and do not consider the optimization question** – which tries to understand how fast we can reach this minimizer. There are several theoretical works which show that stochastic optimization algorithms converge to the minimizers efficiently under certain conditions even when empirical/population risk cannot be efficiently evaluated.\n\n## Theorem 3 and faster inference\n\nWe now discuss the role of discretization error to further explain Remark 2 and its relationship to Theorem 3. Consider the sources of error in diffusion model sampling based on the results in [Theorem 1, Ref 3]. \n\nAs noted above, during training, the loss function is considered to be an integral (with $\\Delta = 0$) or a fine discretization as in our case with $\\Delta = O(1/d^3)$. For the sake of clarity, we specialize to the case where $\\Delta = O(1/d^3)$.  During inference, the neural network is queried at times $\\tau_1,\\dots,\\tau_A$ which can be a subset of the times $\\{t_1,t_2,..,t_N\\}$ with $A \\ll N$. \n\nReferring to [Theorem 1, Ref 3], there are two sources of error: \n\n1. Statistical error: $\\epsilon_{score}^2(\\tau_1,\\dots,\\tau_A) = \\sum_{i=1}^{A} (\\tau_{i}-\\tau_{i-1}) \\mathbb{E}[\\|\\|\\hat{f}(x_{\\tau_i},\\tau_i) - s(x_{\\tau_i}, \\tau_i)\\|\\|\\^2]$\n2. Discretization error: which is related to the quantity: $\\max_i |\\tau_i - \\tau_{i-1}|$\n\nTheorem 1 obtains the statistical error as defined above for the sequence of times $t_1,\\dots,t_N$ as $\\epsilon_{score}^2(t_1,\\dots,t_N) \\leq \\epsilon^2$. Theorem 3 shows shows that we can take a much coarser discretization with $\\tau_i - \\tau_{i-1} = k \\Delta$, and $A =\\lceil N/k \\rceil$ such that $\\epsilon_{score}^2(\\tau_1,\\dots,\\tau_A) \\leq \\epsilon^2$ is also true. Therefore, **using a coarser discretization during inference does not affect the statistical error**.\n\n## Time-varying Lipschitz constant\n\nThank you for the great suggestion on the assumption. This can be especially useful if the score function of the target distribution has a large Lipschitz constant which gets **smoothed out during the forward process**. We refer to our rebuttal to reviewer HNsM, where we point out that this question is more meaningful when explored with the question of understanding the best time discretization, which requires further technical work (For example, it might need to be finer when there is high Lipschitz constant).\n\nWe note that our proof techniques allow for time varying Lipschitz constant, but we chose to have a uniform upper bound for the sake of clarity. This assumption is standard in the Markov Chain Monte Carlo literature as well as analyses of iteration complexity of diffusion models (see [Ref 4]). We plan to explore time varying regularity in future work and sketch the primary modifications below. \n\nAll proofs remain intact when the drift satisfies the variable condition $ ||f(t,x) - f(t,y)|| \\leq L(t) ||x-y|| $  with a measurable $L(t)\\ge 0$. Wherever a fixed $L$ formerly appeared, we \n\n(i) replace the quadratic factor $(L+1)^{2}$ in martingale‐variance terms by the time-weighted average $ \\bar L_{2}^{\\,2}=\\frac{1}{N\\Delta}\\sum_{j=1}^{N}\\gamma_{j}\\bigl(L(t_{j})+1\\bigr)^{2}$,\n\n(iii) bound each sub-Gaussian tail parameter by the worst-case value $L_{\\infty}=\\sup_{t\\in[0,T]}L(t)$, which therefore enters only inside logarithmic terms.  \n\nWith these substitutions, the sample-complexity statement of Theorem 1 becomes $m \\gtrsim \\frac{\\bar L_{2}^{\\,2}}{\\varepsilon^{2}}\\log\\bigl(B|H|/\\delta\\bigr)$. Consequently, the dimension-free guarantees are robust to \\emph{time-varying smoothness}, depending chiefly on the _average_ $\\bar L_{2}^{\\,2}$ rather than the worst-case $L_{\\infty}$. This can be **especially useful if there is a considerable gap between the $\\sup_t L(t)$ and $\\sqrt{\\sum_t L(t)^2/T}$**.\n\n## $\\log(|H|)$ dependence\n\nAs noted by the reviewer, log(|H|) dependence is standard in learning theory (see for e.g. Corollary 4.6 [Ref 5], Section 4.4.3 [Ref 6]). Prior works on score matching analysis ([3] and [14] in the paper) also incur such factors. For instance [14] explicitly upper bounds this quantity with the number of parameters in the neural network. Therefore, in comparison **we bring down the complexity from $poly(d)\\log(|H|)$ to $\\log(|H|)$** which is meaningful in high dimensions, as emphasized in Remark 1. \n\n**Improvement over prior works**: To put our results in context (see line 190), prior work [12] shows that score matching suffers from exponential dependence on $d$ in the worst case. In contrast, we show that when the target distribution admits a suitable class of estimators with mild smoothness assumptions, score estimation becomes sample-efficient. This closes the gap between theoretical results and empirical findings in diffusion models, where global optimization reliably learns accurate score functions for natural images, despite the worst-case hardness of training neural networks.\n\n**Special cases for improving over** $\\log(|H|)$: Many deep learning theory papers study the high-dimensional loss landscape and implicit regularization, where optimization effectively operates over a smaller set of weights. This reduces the effective complexity from $\\log⁡|H|$ to $\\log⁡|H_0|$ where $|H_0| \\ll |H_1|$, leading to tighter bounds. Typically, $H_0$ still contains a local minimum nearly as good as the global one (see [Ref 7]).\n\nWe believe that further exploration on this topic is beyond the scope of our present work, since it involves deep unsolved problems in this field.\n\n_[Ref 1]: Denoising Diffusion Probabilistic Models, Ho et al, arxiv: 2006.11239_\n\n_[Ref 2]: Score-Based Generative Modeling Through Stochastic Differential Equations, Sohl-Dickstein et al, arxiv:2011.13456_\n\n_[Ref 3]: Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization, Benton et al,  arxiv:2308.03686_\n\n_[Ref 4]: Chen, S., Chewi, S., Li, J., Li, Y., Salim, A. and Zhang, A.R., 2022. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. ICLR 2023._ \n\n_[Ref 5]: Shalev-Shwartz, S. and Ben-David, S., 2014. Understanding machine learning: From theory to algorithms. Cambridge university press._\n\n_[Ref 6]: Bach, F., 2024. Learning theory from first principles. MIT press._\n\n_[Ref 7]: Why Do Local Methods Solve Nonconvex Problems? Tengyu Ma arxiv:2103.13462_"}, {"review_id": "Z4IYmUQSax", "reviewer": "Reviewer_Q2sL", "summary": "The paper studies the sampling error of the score function estimated by a score-matching objective in the context of a diffusion model. The  authors provide high-probability bounds for the error. The claimed contributions are 1) the bounds are nearly dimension-free, 2) the use of a novel martingale-based decomposition, and 3) a bootstrapped version of the score estimate with lower variance.", "questions": "Most of my questions have been asked in the weakness part of the above section.", "limitations": "Very restrictive limitations were provided in the Conclusion. I think there are technical limitations that are unclear from the current exposition, and I have included them in the Weakness section.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The bootstrapped score estimator looks interesting and I am slightly surprised by its performance.\n\n\nWeaknesses:\n\n- I am not convinced by the claim that the provided results are dimension-free:\n1) line 128 as well as subsequent theoretical results involve a condition that is very hard to intrepet, and notably has d^3 log^3(2d) dependence. As Remark 2 says, for this to be truly dimension free, this would require the discretisation step to be Delta = O(1/d^3), which is hard to reason about in practice. I'm not sure I understand why randomly sampled times, as argued in Remark 2, would address this theoretical issue.\n2) The log |H| dependence together with s in H feels prohibitively strong as to introduce in the conditions. One would expect H to also have dimension dependence (often exponential in d), unless a very informative class of H is chosen.  It would be helpful for the authors to provide a few concrete examples of score functions that satisfy Assumption 1 with concrete examples of H, to convince the readers that these are actually dimension-free results.\n\n- I am also not convinced that Theorem 3 provides a way to obtain faster inference, as I take that k is fixed in Theorem 3. Can the authors clarify whether k is allowed to grow, and whether the bound in Theorem 3 has hidden implicit dependence on k? In particular, I am not convinced about the claim in Remark 2 that Theorem 3 is a way to answer the Delta = O(1/d^3) requirement.\n\n- While I find the bootstrapped score matching section interesting, not enough details are given to illustrate why the bootstrapped version would be better. Both variance computations are upper bounds and not exact. Also, some limited experiments are included in the appendix but not in the main text. To illustrate the validity of this method, and also in view of the context of this paper, I think the authors need to perform experiments with a larger variety of settings, e.g. multimodal distributions beyond d=1 and non-Gaussian data.\n\n- Section 5: Can the authors clarify whether, the additional term in tilde y_t, should be interpreted as some sort of estimation of the noise? If so, some interpretation around this will be nice. There also seems to be a tradeoff in terms of decreasing Delta to improve the bound in Lemma 7 and the need to get good estimation of hat s in an earlier time step -- it would be great if some more interpretations can be given for this tradeoff. At the moment, the discussion mostly focuses on an explanation of how the method works but not really on why it works and what might be potential barriers for the method. I think a better illustration of the latter would enhance the message quite a lot.", "was_revised": true, "final_justification": "My main concern about the paper was that it claims to offer dimension-free bounds whereas there are unexplained dimension dependence in the results. During the rebuttal, the authors have clarified to me how the stated conditions were acceptable in view of the literature and some standard assumptions, which make the results \"dimension independent\" in view of the literature framework. In view of this, I am willing to raise my score to a weak accept and I lower my confidence score as I'm not as familiar with the literature context the authors mention. However, as the authors' responses have indicated, the \"dimension-free\" claim in the title and in the paper actually has quite a number of caveats that were not draft in the original draft. I think the authors should pay attention to not overclaiming this contribution and should try to include a proper discussion about these caveats in the revision. I also think that this limits the originally claimed novelty, which prevents me from raising the score up to an Accept.", "rebuttal": "We thank the reviewer for their detailed questions and address the main technical concerns below. \n\n## The condition $\\Delta = O(1/d^3)$ and dimension independence\n\nWe thank the reviewer for raising the subtle yet important point regarding the effect of setting $\\Delta = O(1/d^3))$ on the overall dimension-free rates claimed. Below we explain why this still results in dimension free rates. We begin with an explanation of statistical error and optimization error in standard formulations of diffusion models. \n\n**The Statistical Formulation**: The standard loss formulation in both theory and practice has time discretization $\\Delta =0$, corresponding to an integral/expectation over time. See Equation (17) in [Ref1] and Equation (7) in [Ref 2].\n\nWe consider a fine approximation of the integral with $\\Delta = O(1/d^3)$ due to purely technical reasons since a $\\log(\\log(1/\\Delta))$ term appears in the error bound. Note that Delta can be made much smaller than $O(1/d^3)$ due to $\\log\\log$ dependence. \n\nIn fact, due to assumption 1, the difference between the integral (i.e, $\\Delta = 0$) and our loss is $O(\\sqrt{\\Delta})$. Therefore, we can consider the standard integral formulation of the loss as well with a few additional lines of proof.\n\n**The Optimization Question**: The integral or the large sum in the loss function is computationally intractable to optimize directly. Hence stochastic optimization algorithms such as SGD or Adam are used. Here random batches of datapoints $(x_0, x_t, t)$ are drawn to evaluate the stochastic gradients. When the times are sampled randomly, we obtain unbiased estimators for the gradients of this loss, even when $\\Delta = 0$ (or when it is very small). **Therefore, practical training of diffusion models can be performed efficiently even when $\\Delta = O(1/\\Delta^3)$**.\n\nConsider the widely used github repository in this field, corresponding to [Ref 2] (user:yang-song, project:score_sde in github):  In the file “losses . py”, the times during training are sampled uniformly from a continuous distribution when _training.continuous = True_ in config and they are sampled from discrete grid when it is set to _False_.\n\n**Our Contributions**: In learning theory, statistical convergence rates and optimization complexity are usually studied separately. In our work, we study how well the minimizer of this loss function behaves by **obtaining statistical error rates**, and do not consider the optimization question – which tries to understand how fast we can reach this minimizer. There are several theoretical works which show that stochastic optimization algorithms converge to the minimizers efficiently under certain conditions even when empirical/population risk cannot be efficiently evaluated.\n\n## $\\log(|H|)$ dependence and its meaning\n\nThis requires an extended and subtle argument to interpret clearly. First, as noted by reviewer 6emV, log(|H|) dependence is standard in learning theory (see for e.g. Corollary 4.6 [Ref 3], Section 4.4.3 [Ref 4]). Prior works on score matching analysis ([3] and [14] in the paper) also incur such factors. For instance [14] explicitly upper bounds this quantity with the number of parameters in the neural network. Therefore, in comparison **we bring down the complexity from $poly(d)\\log(|H|)$ to $\\log(|H|)$ which is meaningful in high dimensions**, as emphasized in Remark 1. \n\n**Improvement over prior works**: To put our results in context (see line 190), prior work [12] shows that score matching suffers from exponential dependence on $d$ in the worst case. In contrast, we show that when the target distribution admits a suitable class of estimators with mild smoothness assumptions, score estimation becomes sample-efficient. This closes the gap between theoretical results and empirical findings in diffusion models, where global optimization reliably learns accurate score functions for natural images, despite the worst-case hardness of training neural networks.\n\n**Special cases for improving over** $\\log(|H|)$: Many deep learning theory papers study the high-dimensional loss landscape and implicit regularization, where optimization effectively operates over a smaller set of weights. This reduces the effective complexity from $\\log⁡|H|$ to $\\log⁡|H_0|$ where $|H_0| \\ll |H_1|$, leading to tighter bounds. Typically, $H_0$ still contains a local minimum nearly as good as the global one (see [Ref 5]).\n\nWe believe that further exploration on this topic is beyond the scope of our present work, since it involves deep unsolved problems in this field.\n\n## Theorem 3 and faster inference\n\nWe thank the reviewer for raising this important technical point. We first want to note that $k$ can be any integer smaller than $N$. We will make this clear in the statement of Theorem 3. **Theorem 3 has no implicit dependence on $k$**. The proof is a straightforward consequence of Markov’s inequality, which can be easily verified by the reviewer. In addition to the explanation of statistical rates vs optimization complexity above, we now discuss the role of discretization error to further explain Remark 2 and its relationship to Theorem 3. Consider the sources of error in diffusion model sampling based on the results in [Theorem 1, Ref 6]. \n\nAs noted above, during training, the loss function is considered to be an integral (with $\\Delta = 0$) or a fine discretization as in our case with $\\Delta = O(1/d^3)$. For the sake of clarity, we specialize to the case where $\\Delta = O(1/d^3)$.  During inference, the neural network is queried at times $\\tau_1,\\dots,\\tau_A$ which can be a subset of the times $\\{t_1,t_2,..,t_N\\}$ with $A \\ll N$. \n\nReferring to [Theorem 1, Ref 6], there are two sources of error: \n\n1. Statistical error: $\\epsilon_{score}^2(\\tau_1,\\dots,\\tau_A) = \\sum_{i=1}^{A} (\\tau_{i}-\\tau_{i-1}) \\mathbb{E}[\\|\\|\\hat{f}(x_{\\tau_i},\\tau_i) - s(x_{\\tau_i}, \\tau_i)\\|\\|\\^2]$\n2. Discretization error: which is related to the quantity: $\\max_i |\\tau_i - \\tau_{i-1}|$\n\nTheorem 1 in our work obtains the statistical error as defined above for the sequence of times $t_1,\\dots,t_N$ as $\\epsilon_{score}^2(t_1,\\dots,t_N) \\leq \\epsilon^2$. Theorem 3 shows that then shows that we can take a much coarser discretization with $\\tau_i - \\tau_{i-1} = k \\Delta$, and $A =\\lceil N/k \\rceil$ such that $\\epsilon_{score}^2(\\tau_1,\\dots,\\tau_A) \\leq \\epsilon^2$ is also true. Therefore, **using a coarser discretization during inference does not affect the statistical error**.\n\n## Questions regarding bootstrapped score matching\n\nThe reviewer is correct that the extra term in $\\hat{y}_t$ estimates the noise to reduce its variance. We want to note that the main contribution of our work are the theoretical results on score estimation with DSM. Bootstrapped score matching was inspired by some of the analysis techniques used in the process, and we believe this gives an interesting variance reduction paradigm. We present some upper bounds and basic empirical results as evidence of its efficacy, and hope to inspire extensive and rigorous future work on this topic. We state this explicitly in lines 330-331. \n\nLine 314 describes the target which has an unbiased but high variance component and a biased but low variance component where the bias is coming from the estimation of the score at the previous timestep. DSM considers $\\alpha_k = 0$ to obtain a completely unbiased estimate with high variance and our aim with BSM is to choose $\\alpha_k$ for the optimal bias-variance tradeoff and achieve overall lower sample complexity. \n\nWe are exploring this as part of ongoing work and will clarify some of these points in the revised manuscript. We included this in our paper because this is a clean algorithmic takeaway from our analysis which we feel will be interesting for the community to build upon. Therefore we request the reviewer to not consider this as a significant weakness of our work.\n\n_[Ref 1]: Denoising Diffusion Probabilistic Models, Ho et al, arxiv: 2006.11239_\n\n_[Ref 2]: Score-Based Generative Modeling Through Stochastic Differential Equations, Sohl-Dickstein et al, arxiv:2011.13456_\n\n_[Ref 3]: Shalev-Shwartz, S. and Ben-David, S., 2014. Understanding machine learning: From theory to algorithms. Cambridge university press._\n\n_[Ref 4]: Bach, F., 2024. Learning theory from first principles. MIT press._\n\n_[Ref 5]: Why Do Local Methods Solve Nonconvex Problems? Tengyu Ma arxiv:2103.13462_\n\n_[Ref 6]: Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization, Benton et al,  arxiv:2308.03686_"}, {"review_id": "nhXFRwoEsj", "reviewer": "Reviewer_HNsM", "summary": "This paper establishes dimension-free sample complexity bounds (modulo dependence due to the hypothesis class) for diffusion models. A single function approximator is used to jointly estimate the score for different noise levels. The proof techniques include marginal-based error decomposition and sharp variance bounds. Additionally, the paper proposes bootstrapped score matching with variance reduction techniques to improve the performance.", "questions": "In this paper, a uniform time discretization is considered. When $T$ is large enough, the marginal distribution $p_T$ approaches the Gaussian distribution $N(0,I)$, implying that the score function should have a simpler form. Could the authors clarify how this affects the sample efficiency? And how to optimize the time discretization?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\nThis paper achieves a double-exponential reduction in dimension dependence by leveraging a single function approximator to estimate the score across noise levels. The proposed martingale error decomposition is theoretically novel, offering a clear path toward tighter guarantees. Given the widespread adoption of diffusion models in modern generative modeling, addressing the issue of dimension dependence is impactful, especially for understanding and improving their performance on high-dimensional data.\n\n**Weaknesses**:\nI am not aware of significant weaknesses in the current version.", "was_revised": true, "final_justification": "Overall, I believe this paper provides a good contribution to the community. I skimmed through the other reviews and discussion, looks like the major concerns have been resolved. I will keep my current positive rating.", "rebuttal": "We thank the reviewer for the great review, showcasing the technical novelty in our work and the importance of our results. \n\n**Time-variation of the Score function**:  We considered uniform discretization for the sake of clarity of exposition and simpler calculations. We believe our techniques readily extend to non-uniform time discretization. \n\nThank you for your insightful question. We believe the question regarding the best time discretization is meaningful when the statistical learning error and the discretization error are considered together to analyze sample complexity. This requires additional non-trivial results as noted below, which we hope to pursue in future work.\n\na) We need to formalize the reviewer’s observation that the score functions at later times should be easier to estimate. This may involve rigorously characterizing the evolution of the smoothness of the score function, $L(t)$, from the target distribution to the Gaussian distribution. While this is intuitively clear, the details are not mathematically obvious. \n\nAll our proofs remain intact when the drift satisfies the variable condition $ ||f(t,x) - f(t,y)|| \\leq L(t) ||x-y|| $  with a measurable $L(t)\\ge 0$. Wherever a fixed $L$ formerly appeared, we \n\n(i) replace the quadratic factor $(L+1)^{2}$ in martingale‐variance terms by the time-weighted average $ \\bar L_{2}^{\\,2}=\\frac{1}{N\\Delta}\\sum_{j=1}^{N}\\gamma_{j}\\bigl(L(t_{j})+1\\bigr)^{2}$,\n\n(iii) bound each sub-Gaussian tail parameter by the worst-case value $L_{\\infty}=\\sup_{t\\in[0,T]}L(t)$, which therefore enters only inside logarithmic terms.  \n\nWith these substitutions, the sample-complexity statement of Theorem 1 becomes $m \\gtrsim \\frac{\\bar L_{2}^{\\,2}}{\\varepsilon^{2}}\\log\\bigl(B|H|/\\delta\\bigr)$. Consequently, the dimension-free guarantees are robust to \\emph{time-varying smoothness}, depending chiefly on the _average_ $\\bar L_{2}^{\\,2}$ rather than the worst-case $L_{\\infty}$. This can be **especially useful if there is a considerable gap between the $\\sup_t L(t)$ and $\\sqrt{\\sum_t L(t)^2/T}$**.\n\nb) Extend Theorem 1 in [Ref 1] to a fine-grained decomposition depending on the properties of the discretization. \n\n_[Ref 1]: Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization, Benton et al,  arxiv:2308.03686_"}, {"review_id": "527HflIPfB", "reviewer": "Reviewer_NwC3", "summary": "This paper investigates the sample complexity of score matching and establishes the first nearly dimension-free bounds under certain regularity conditions. Specifically, assuming Gaussian noise and a Lipschitz condition on the score function, the authors show that the number of samples required to achieve an $\\varepsilon$-accurate score estimate is $O(L^2 \\log(B|H|/\\delta)/ \\varepsilon^2)$. This bound holds for both empirical error and the expected $L_2$-norm error. The paper also introduces a bootstrapped score matching (BSM) method to improve empirical performance.", "questions": "1. Could the authors provide concrete application scenarios where the function class H is explicitly available?\n\n2. If the function class H is defined by a neural network class, what is the relationship between $\\log(H)$ and the number of network parameters?\n\n3. Even if the function class is parameterized by a one-dimensional contious parameter in $R$, will $\n\\log(H)$ tend to infinity?\n\n4. Do previous works [3] and [14] also rely on Assumption 2 to establish generalization bounds for score function learning?\n\n5. Definition 1 seems to be used only in the proof. The authors may consider moving it to Section 4.\n\n6. In Theorem 1, the bound is said to hold with high probability. Is the randomness here due to both the Gaussian noise in $x_t$ and the randomness in the samples $x^{(i)}$? Or conditioned on the data $x_t$?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\nThe primary contribution of this work lies in establishing a sample complexity bound for score matching that is almost independent of the data dimension. This may address a key challenge in high-dimensional generative modeling. The paper also verify the theory with numerical experiments, and demonstrate the performance of the proposed BSM method.\n\n**Weakness:**\n\n1. The analysis assumes optimization over a specific function class, which may not be available in practical settings.\n\n2. The analysis relies on a hypercontractivity assumption, which may not hold in real-world data distributions.\n\n3. The theoretical results are derived only for a fixed step size $t_j = \\Delta j$, which limits their generality.\n\n4. There is a minor typo in Remark 1: \"at least\" should replace \"atleast.\"", "was_revised": true, "final_justification": "I will keep my positive score for potential acceptance.", "rebuttal": "We thank the reviewer for the great review. The main concern raised by the reviewer is regarding the function class H, and the means to optimize over this function class and how large this can be. We clarify these points below. \n\n## The function class $H$ and the dependence on complexity\n\n**Motivation for function class in practice**: We follow a standard learning theoretic setup where optimization is considered over a general function class $H$ with suitable properties. The function class itself is characterized in practice by the type of optimization algorithm used. Our assumptions on the function class were motivated by the practical scenarios where both $t$ and $x_t$ are provided as input to neural networks for score learning, enabling smoothness across time and space. We would like to note that our work presents statistical sample complexity bounds for learning the score function, but to optimize the score learning objective, **explicit access to the function class is not needed in practice** since optimization constraints implicitly define a function class. \n\n**$\\log(|H|)$ and dependence on parameters**: Given a class of functions $H$, $\\log(|H|)$ is the standard dependency for statistical rates in learning theory (see for e.g. Corollary 4.6 [Ref 1], Section 4.4.3 [Ref 2], Theorem 19.5 [Ref 3]). This could be the set of neural networks with fp32 quantization and bounded weights, for instance. In general, a class of functions with M free parameters has $\\log(|H|) = \\Theta(M)$. We will clarify this aspect in the paper. Prior works on score matching analysis ([3] and [14] in the paper) also incur such factors, where [14] explicitly upper bounds this quantity with the number of parameters in the neural networks times the diameter.  In particular, for the class represented by fully connected neural network\nwith ReLU activations with $P$ parameters, each bounded by $R$ and depth $D$, they use $\\log(|H|) \\approx PD\\log(R)$ (see Setting 1.1 [14])\n\n**Improvements over**  $\\log(|H|)$: A large body of papers on Deep Learning Theory explore the high dimensional loss landscape and implicit regularization, a phenomenon where the optimization algorithm only effectively optimizes over a small class of weights, making the effective complexity $\\log(|H_0|)$ which is much smaller than $\\log(|H|)$, and the bounds should replace $\\log|H|$ with $\\log|H_0|$. However, this smaller class usually contains a local minimum which is almost as good as the global minimum. See [Ref 1] for a short survey. We believe that further exploration on this topic is beyond the score of our present work, since it involves deep unsolved problems in this field.\n\n## Assumption 2 and comparison to [3] and [14]\n\nIn short, assumption 2 is not exactly present in [3] and [14], these have a different setting allowing them to bypass this assumption. The setting can be more stringent than our setting (see Lines 174-185). We expound more on the differences below: \n \n[14] does not consider the $L^2$ error as we do, but a different “high probability” version which does not involve expectations. This can be bounded without using fourth moments. However, this also incurs a polynomial dependence in the high-probability parameters $\\delta$ instead of the logarithmic dependence in our case. \n\n[3] Corollary 9 assumes that the function class has bounded outputs almost surely, which can be more stringent than the control of  4th moments. This also considers the score function and its estimate to be dissipative (which roughly gives quadratic growth at infinity along with sub-Gaussianity as shown in Lemma 45), which allows sharper concentration results. \n\nWe want to note that Assumption 2 is very mild since we require control only over the $4^{th}$ moments. This holds for most popular distributions, including heavy tailed distributions which have finite fourth moments such as the pareto distribution. This assumption is also common in the robust statistics literature as shown in the literature review. \n\n## The randomness in Theorem 1\n\nThe randomness in theorem 1 arises from both the datapoints as well as the gaussian noise. \n\nWe show that this cannot hold uniformly for arbitrary datapoints $(x_0^{(i)})$ via contradiction because of the following LeCam’s 2 point method style argument below. \n\nAssume that the concentration in Theorem 1 holds uniformly for all choices of $(x_0^{(i)})$ over the support of $P$. Consider two probability densities $P,Q$ such that $P \\ll Q$ and $Q \\ll P$ (i.e, they are mutually absolutely continuous). Let the result in Theorem 1 holds uniformly for every $x_0^{(1)},\\dots, x_0^{(m)}$ over the support of P (and support of Q). Define the events $A_P$ and $A_Q$ as follows:\n\n$A_P (x):=\\\\{ \\frac{1}{m}\\sum_{i,j}\\gamma_j\\|\\hat{f}(t,x_{t}^{i})-\\nabla\\log P(t,x_t^{i})\\|^2\\leq\\epsilon^2 \\\\}$, $A_Q (x):= \\\\{ \\frac{1}{m}\\sum_{i,j}\\gamma_j\\|\\hat{f}(t,x_{t}^{i})-\\nabla\\log Q(t,x_t^{i})\\|^2\\leq\\epsilon^2\\\\}$\n\nBy theorem 1 and our assumption, this would imply that $\\mathbb{P}(A_P(x)) \\geq 1-\\delta$ and $\\mathbb{P}(A_Q(x)) \\geq 1-\\delta$. Therefore, with probability $1-2\\delta$, both $A_P(x)$ and $A_Q(x)$ must hold simultaneously which implies that $\\frac{1}{m} \\sum_{i,j}\\gamma_j\\|\\nabla \\log P(t,x_t^{(i)})-\\nabla\\log Q(t,x_t^{i})\\|^2 \\lesssim  \\epsilon^2$.\n\nThis leads to a contradiction when $P$ and $Q$ are different distributions (say Gaussians with same mean but different variance).\n\n_[Ref 1]: Why Do Local Methods Solve Nonconvex Problems? Tengyu Ma arxiv:2103.13462_"}]

Author rebuttal:

Meta-review: This work establishes a dimension independent bound for score-function learning. The key to achieve the improved statistical rate is to consider joint learning of score functions for all time steps with time regularity smoothness assumption on the hypothesis class. To study such learning problem with dependent data along the trajectory, the authors developed a technique based on Martingale decomposition of the error. Overall, the result presented in the paper improves the generalization analysis of score function learning in the current literature. The reviewers unanimously recommend acceptance, and the meta-review agrees with their assessment.
Decision: Accept (poster)