Shallow diffusion networks provably learn hidden low-dimensional structure
Authors: Nicholas Matthew Boffi
Arthur Jacot
Stephen Tu
Ingvar Ziemann
Venue: ICLR 2025 Poster (2025)
Keywords: Generative models
diffusion models
denoising score matching
low dimensional structure
Barron classes
Primary area: generative models

Abstract: Diffusion-based generative models provide a powerful framework for learning to sample from a complex target distribution. The remarkable empirical success of these models applied to high-dimensional signals, including images and video, stands in stark contrast to classical results highlighting the curse of dimensionality for distribution recovery. In this work, we take a step towards understanding this gap through a careful analysis of learning diffusion models over the Barron space of single hidden layer neural networks. In particular, we show that these shallow models provably adapt to simple forms of low-dimensional structure, such as an unknown linear subspace or hidden independence, thereby avoiding the curse of dimensionality. We combine our results with recent analyses of sampling with diffusions to provide an end-to-end sample complexity bound for learning to sample from structured distributions. Importantly, our results do not require specialized architectures tailored to particular latent structures, and instead rely on the low-index structure of the Barron space to adapt to the underlying distribution.

Published as a conference paper at ICLR 2025
SINGLE HIDDEN LAYER DIFFUSION MODELS PROVABLY LEARN SIMPLE LOW-DIMENSIONAL STRUCTURE
Nicholas M. Boffi Carnegie Mellon University nboff fi @anddew. cmu. edu
Arthur Jacot
New York University
arthur jaw.:recccoottyuuoooomm edu
Stephen Tu
Ingvar Ziemann
University of Southern California stephen. tu@usc.edu
University of Pennsylvania
ingvarz@seas upenn.
ABSTRACT
Diffusion-basee generative models provide powerful framework for learning to sample from a complex target distribution. The remarkable empirical success of these models applied to high-dimensional signals, including images and video, stands in stark contrast to classical results highlighting the curse of dimensionality for distribution recovery. In this work, we take step towards understanding this gap through a careful analysis of learning diffusion models over the Barron space of single hidden layer neural networks. In particular, show that these shallow models provably adapt to simple forms of low-dimensional structure, such unknown linear subspace hidden independence, thereby avoiding the curse of dimensionality. We combine our results with recent analyses of sampling with diffusions to provide an end-to-end sample complexity bound for learning to sample from structured distributions, Importantly, our results do not require specialized architectures tailored to particular latent structures, and instead rely on the low-index structure of the Barron space to adapt to the underlying distribution.
INTRODUCTION
Generative models learn to sample from a target probability distribution given dataset of examples. Applications are pervasive, and include language modeling (Li et al., 2022), high-fidelity image generation (Rombach et al., 2022), de-novo drug design (Watson et al., 2023), and molccular dynamics (Arts et al., 2023). Recent years have witnessed extremely rapid advancements in the field of generative modeling, particularly with the development of models based on dynamical transport of measure (Santambrogio, 2015), such as diffusion- based generative models (Ho et al., 2020; Song et al., 2021), stochastic interpolants (Albergo et al., 2023), flow matching (Lipman et al., 2023), and rectified flow (Liu al., 2023) approaches. Yet, despite their strong empirical performance and well gell-ggoondeed mathematical formulation, a theoretical understanding of how and why these large-scale generative models work is still in its infancy.
A promising line of recent research has shown that the problem of sampling from an arbitrarily complex distribution can be reduced to unsupervised learning: for diffusion models, if an accurate velocity or score field can be estimated from data, then high-quality samples can be generated via numerical simulation (Chen al., 2023d; Lee al., 2023). While deeply insightful, these works leave open the difficulty of statistical estimation, and therefore raise the possibility that the sampling problem's 's true difficulty hidden in the complexity of learning the score.
In this work, we address this fundamental challenge by presenting an end-to-end analysis of sampling with score-based diffusion models. To balance tractability of the analysis with empirical relevance, we study the Barron space of single hidden layer neural networks (E al., 2019; Bach, 2017). This space contains important features of models used practice most importantly, parametric nonlinearity while retaining well-studied theoretical properties that can adapt the generative modeling problem. As paradigmatic examples the widely- held belief that real-world datasets contain hidden low-dimensional structure (Tenenbaum al., 2000; Weinberger & Saul, 2006), focus two

---

Published as a conference paper at ICLR 2025
idealized settings in which the target data density is concentrated unknown low- din-dimesi linear manifold, or consists of groups of independent oww-dimesioonl variables. We show that for learning to sample from target distribution with either of these structures, diffusion models backed by Barron networks enjoy sample complexity bound that only depends exponentially on the intrinsic dimension of the structure rather than on the ambient dimension. Our results highlight that diffusion models based on one hidden layer networks without specific architectural modifications can adapt to hidden structure and sidestep the curse of dimensionality; in this way, they give insight into the empirical performance of more complex architectures on real-world high- high-dimensional datasets.
RELATED WORK
Sampling bounds for diffusion models. Much of the recent work on analyzing diffusson models has focused on the accuracy of sampling from discretized backwards diffusion process, assuming access to L2 accurate score functions. This includes work on discretized stochastic differential equations (Lee et al., 2022; Chen et al., 2023d; Lee et al., 2023; Chen et al., 2023a; Benton et al., 2024) and more recently, discretized probability flows (Chen et al., 2023e;c; Li et al., 2024; Liang et al., 2024; Gao & Zhu, 2024). Recent work by Li & Yan (2024) shows that the DDPM sampler (Ho et al., 2020) can be tuned so that in the presence of low dimensional structure, the discretization error only depends polynomially these works assume the existence of an e-accurate score function in L2, and thereby leave open the question of the sample complexity of learning such model.
the intrinsic dimension (in addition to the score error). However,
Sample complexity of score matching. Several works have considered the statistical complexity of learning score function. Block et al. (2020) and Koehler et al. (2023) use the standard Rademacher complexity framework to bound the error of empirical risk minimization (ERM) for learning the score, but leave open the question of which function class to learn over. Han et al. (2024) and Wang et al. (2024) consider optimizing the denoising score matching loss over neural network models, and show that gradient descent on overparameterized models finds quality ERM solutions. Wibisono et al. (2024), Zhang et al. (2024), Oko et al. (2023), and Dou et al. (2024) study the minimax optimality of diffusion modeling under various functional assumptions regarding the target density and its corresponding score function. While together these works show that diffusion modeling is both nearly optimal for learning to sample and also computationally efficient, they simultaneously highlight the curse of dimensionality that arises without more structure. To address this issue, both Oko et al. (2023) and Chen et al. (2023b) impose a latent subspace assumption on the data distribution, which they show avoids exponential dependence on the ambient dimension. Our work is directly inspired by these results, and we defer a detailed comparison to Section 3. Another related work is Bortoli (2022), which studies diffusion models under manifold hypothesis, proving bound that depends exponentially on the diameter of the manifold. Finally, Cole & Lu (2024) show that under the assumption that the target log-relative density (w.r.t. standard Gaussian) can be approximated by network with low path norm, score estimation can be performed with a sample complexity bound that does not depend explicitly on the ambient dimension.' However their absolute continuity assumption rules out examples such as target distributions supported on low dimensional manifolds.
Learning in Barron spaces. Even though the implicit bias of deep networks remains largely an open question, there is now strong consensus that the implicit bias of shallow networks with large width is accurately captured by the Barron norm (E et al., 2019) or variational Fi norm (Bach, 2017). Such networks can avoid the curse of dimensionality by capturing low-index structure (i.e., when the target f(x)= (Px) for low-dimensional projection P E dd ), leading to generalization bounds that depend on the intrinsic dimension d rather than the ambient dimension D (Bach, 2017). Several recent results have also studied the (sometimes modified) gradient descent dynamics of shallow networks, and how this low-index structure emerges in the network (Abbe et al., 2022; Bietti et al., 2022; Ben Arous et al., 2022; Glasgow, 2024; Lee al., 2024). While most of this literature focuses on supervised training problems, some work has shown that this type of analysis can be extended to the unsupervised case, particular to learn energy- based models (Domingo-Enrte Enniihh et al., 2021).
However, there are still 0(1)" frctorctors in the final rate.
2

---

Published as a conference paper at ICLR 2025
3 PROBLEM FORMULATION AND MAIN RESULTS
Our goal in this work is to study the statistical complexity of learning to sample from a target probability measure (2r defined on IR D given a dataset of n iid examples z/ ~ Po for 1,... ......... n. In particular, we consider the use of a diffusion model (Sohl-Dickstein et al., 2015; Song et al., 2021; Ho al., 2020) learn stochastic process that maps random noise to new sample from the data distribution. We assume that the target po contains hidden latent structure either Now-dimensions subspace or independent components and our primary goal will be to show that a single hidden layer network can learn this hidden structure efficiently, in the sense that the statistical rates are governed primarily by the underlying latent dimension d, as opposed the ambient dimension D > d.
Diffusion models. We consider ceffuusion-basee generative models based stochastic differential equations (Song et al., 2021). These models construct a path in the space of measures between the target Po and standard Gaussian N(O, /n) by defining a forward process that converges to Gaussian data over an infinite horizon. For simplicity, we consider the Ornstein-UUlenine
(OU) process,
dx. = -x,dl + v2dB., LE [0,
(3.1)
though our results straightforwardly generalize to the time-scaled OU processes commonly used in practice (Song al., 2021). In (3.1), (Bi)cso denotes a standard Brownian motion on R Due to the linear nature of the OU process, for w ~ N(O, ID) drawn independently of Zo, Ie is equivalent in distribution to the stochastic interpolant (Albergo et al., 2023)
T₁ m2 + o my = exp(-1), o :- - exp(-2)))
(3.2)
Let the marginal distributions of be denoted as (Pt) The reverse process is the process of ye == zr for t E [0, T]. A classic result (Anderson, 1982) shows that the reverse process satisfies
dy: (yt + 2V log pog v2dB,, yo ~ pp()), t E [0.
(3.3)
Thus, assuming knowledge of the time-dependent score function V loggt. Pt. sampling from po(-) can be accomplished by (a) setting large enough so that (.) is approximately an isotropic Gaussian, (b) sampling yo N(0, ID), and (c) rumning the reverse SDE (3.3) until time T.
To implement this scheme in practice, the score function must be learned, and the reverse process must be discretized. Assuming access to a learned score function & x V log p. we now consider discretizing (3.3). In this work we make use of the exponential integrator (EI), which fixes sequence (to be specified) of reverse process timesteps 0 To < TI <
TN = T and implements
dğ. (j+- + 28 (ū+))) )) + Vdd., E [m,, Tk41), E (0. (O. N 1).
(3.4)
Recently, building off of the works by Chen et al. (2023d) and Lee et al. (2023), Benton et al. (2024) showed that suffices to control the score approximation error in L2(pe) to guarantee that the process (3.4) yields high quality sample from po.
Score function estimation. To estimate the score function V log P. over the interval T), one would ideally minimize the least-squares objective over model s,
R(S)= = //' (e) dt, Ra().) = E,, (xx)) - V log (x:))
(3.5)
While direct minimization not possible because log is not observed, minimizing R(s) is equivalent to minimizing the following denoising score matching (DSM) loss (Vincent, 2011)
C(8) 10)= 1 C.(
L.(s.) = ((,,,)) (x, + w/o
(3.6)
as can be shown by Tweedie's identity V log (x) = - Blw xa = a] (Efron, 2011). In practice, (3.6) is typically approximated via Monte- Carlo by generating samples zi. my=z to w using the dataset of samples from Po. iid random draws of Gaussian noise wt, and random time points
Technically, Benton al. (2024) guarantees a high quality sample from Pr pT- (+) instead of po(-)-
3

---

Published as a conference paper at ICLR 2025
t' drawn from [0. J. This empirical risk can then be minimized to estimate time-dependent score function 8 [0. T] x R²' + R."
In this work. to simplify the mathematical amalysis, we consider stylized variant in which we fix sequence of timesteps < to < .... < f = 'I' and estimate N fime-independent score functions {&t, === of the form St, : IR" + R from a family of function classes F::
"
&e E arg ((ss,, (((s)) == 72 Σ (sx()²)) + w² loul?. E (t
(3.7)
&EE
In the sequel, we will let D, == {(1), wn) )i) denote the training data used in (3.7) for timestep t.
From Wibisono et al. (2024), we know that if the true score V logge Lipschitz continuous and p: is Sab-Gaussian, then the minimax rate for estimating V log Pt is given by n n-2/(D 22(()+4)) Unfortunately, this type of bound ignores all latent structure, raising the question of whether or not diffusion models can learn latent structure in a sample efficient way.
The Barron space Fj. Consider a single hidden layer network fm with mn neurons and mean-field scaling, (z) = 1
mi Ex= 140a(2z vt)). ). In the limit as m tends infinity, the summation may be replaced by integration foe (x) = wat(( ((z, u)) du((u, (u, v) against signed Radon measure μ over the neuron parameters (u. v). This leads to the Barron space Fi (Bach, 2017; Mhaskar, 2004; Rotskoff & Vanden -ijjden,,,, 2019; Mei et al., 2018; Sirignano & Spiliopoulos, 2020), which models single hidden layer networks in the infinite width limit and feature learning regime (Chizat et al., 2020).
Concretely, given a Radon measure j on a measurable space V, recall that the total variation norm (TV) is defined as ||.||tv == sup, Jy (v) du((), where the supremum is over continuous functions 0:V~ [-1,1] Given a basis function (x), the TV-norm induces the space of functions Fi == {S(z) = Jy (p()) || < ).). For a function f E F1, its Fi-rorm is the infimum over all TV-norms of measures that can represent f. i... |lffl == (ll f(x) = Jy (z() du(v)}.
In this work, we will consider the special case V = 1P-1 x for p E N+ and (x) = wo wo (z, v)). where (u, v) V and a(.) max + is the ReLU activation. Hence, the induced class Fi consists of vector-vale valued maps from R² + IR" that satisfy [x) < [[ ||=]|| In learning the score functions &c, via DSM (3.7), we will utilize norm-ball subsets of Fi model the true score functions V log Pt, (2)) This allows us to leverage the low-index structure of Fi (Bach, 2017 7) and obtain bounds for score estimation that scale with the intrinsic, rather than ambient, dimension of the problem.
Finally, while we consider Fi in this paper, we note that any f f Fi can be e-approximated in L2 by finite width fm with m & O(I /&, neurons (Bach, 2017, Section 2). Since we will show that we can approximate the underlying score function with F Fn-rrrm polynomial in D, our results easily extend to finite width one hidden layer networks with poly(D) width.
Flow matching and interpolant models. Flow matching models (Lipman et al., 2023; Liu et al., 2023) and stochastic interpolants (Albergo et al., 2023) have also been used recently in the context of generative modeling. In Appendix B, we relate the Barron norm of the drift vector field in these ODE based models with the Barron norm of the score function, which implies that our proof techniques can also be used to prove similar results for learning flow matching and interpolant drift terms.
Notation. We briefly review the (relatively standard) notation used in this work. For a d-dimensional vector x, the E, norm is denoted || : the notation || is reserved for the Euclidean (p- = 2) case. The (closed) ball of radius in d-dimension is denoted by B2(r, d); when r = 1, we use the shorthand B2 (d). The unit sphere in Rd is denoted sd The notation Oa(-) hides both universal constants and constants that depend arbitrarily on the variable d. Similarly, Oa(-) hides universal constants, constants that depend on d, and terms that may depend nolyllogarithmically on d, i.e., terms of the form log ((4) (.). The notation poly(-) indicates a polynomial dependence on the arguments, whereas poly <-)) indicates that the polynomial degrees are allowed to depend arbitrarily on d. The notation S (resp. 2 b) indicates that there exists a universal positive constant e such that cb (resp. a > cb), and a = b means that a S b and Z b. Finally, we use a V b to denote max (a, b}.
Interesttnngy, this rate is slower than the 2/(D+2) rate for learning Lipschitz functions (Tsybakov, 2008).
4

---

Published as a conference paper at ICLR 2025
3.1 LEARNING LATENT SUBSPACE STRUCTURE
We first consider a setting in which zo is supported on a d-dimensional (d < D) linear subspace:
zo U Zo
5g To(-), U E O(D,d) d),
(3.8)
where 20 is d-dimensional random vector and O d) == (U Rxd U Ta] denotes the d-dimensional orthogonal group in RDD Note that both the subspace dimension d and the embedding matrix U are unknown to the learner.
Recently, both Chen et al. (2023b) and Oko et al. (2023) consider learning diffusion models under the subspace structure (3.8). The main takeaway from both works is that the latent subspace dimension d, rather than the ambient dimension D, can govern the complexity of learning to sample from po the network used for learning satisfies various architectural assumptions. While insightful, these architectural assumption are difficult to satisfy in practice. Chen et al. (2023b) utilize function class that is specifically tailored to the linear structure (3.8), in the sense that a linear autoencoder with prior knowledge of the latent dimension d is used to reduce the learning problem to the latent space. The situation is improved in Oko et al. (2023), which considers fully-connected neural networks with bounded weight sparsity. Though closer to real-world architectures, optimizing networks with bounded sparsity constraints is computationally challenging in practice.
Our first result further closes the gap between theory and practice: we show that by optimizing over F1. the space of infinite-widhe single hidden layer networks, the latent subspace is adaptively learned without requiring prior latent dimension knowledge or difficult to impose sparsity constraints. We note that from computational perspective, sufficiently wide shallow networks trained with gradient descent (GD) and weight decay will converge to the minimal Fi-norm solution (Chizat & Bach, 2018). While control on the number of neurons required in the worst case is not available (optimizing over Fi is unfortunately NP-hard (Bach, 2017)), recent results have shown that under various assumptions
the data and task, this hardness can be avoided and GD can indeed learn low-index functions with a number of neurons that scales polynomially with an exponent that depends only on the intrinsic dimension (Abbe et al., 2022; Dandi et al., 2023; Lee et al., 2024). The fact that an exponential width might be required for GD to converge to the optimal solution is not in contradiction with the fact that polynomial width is sufficient approximate the optimal solution (cf. beginning of Section 3), since approximation is a weaker guarantee than convergence of GD.
Towards stating our first result, we begin with few standard regularity assumptions. Assumption 3.1. The latent variable zo =o(-) is L-sub-Gaussia (with 3 s 1), i.e.,
Eexp(A(I soll =l)) cxp(A?B²/2),
E.
Our next assumption concerns the regularity of the score function of the latent distribution ny, which denotes the marginal distribution of 2e == T'T..
Assumption 3.2. The latent score V log ग. is L-Lipschitz (with L 1) on Rd for all t > 0.
We emphasize that Assumption 3.2 concerns the Lipschitz regularity of the latent measure Te and not the ambient measure pæi due to the subspace structure (3.8), the Lipschitz constant of the ambient score diverges as L + O. Finally, we define some shorthand notation for L E [0,T],
,r. = po V VoVD,
Ht, := po V Vo,vd, L == + Vd + || log To (0))).
where Hg = [2 /22 and c > 1 is a universal constant. Since o; + as t - oo, these constants are uniformly bounded above. Hence, we define Hs := limy-poc Ht. and μı := lime- Pt,z-
Theorem 3.3. Suppose that po follows the latent structure (3.8), and that both Assumption 3.1 and Assumption 3.2 hold. Fix a >> 0 and define
:: P R
41l || & Re). RS == Ranadio +
D
(3.9)
0
where R₂ does not depend on n.5 Suppose that satisfies
n > no (t)) := polyyoy 1/ Pt,z V () poly a (T,, 14, V (9).
(3.10)
"This definition is also referred to as norm-sub- suussuus--aaannn in the literature (sec c.g. Jin et al., 2019).
'The explicit dependence of R, on the other problem parameters is detailed in the proof.
5

---

Published as a conference paper at ICLR 2025
Then, the empirical risk minimizer & E arg min (s) satisfies:
D2 o.n
D3 (Lij,, V VB))at (14 v 8)2 t + +1p0i
ED, (R)( < Ōd(1)
ofn (1e V 18)2.
Focusing on the factors n, d, D, Theorem 3.3 states that the score matching risk scales as Ep, (R.) & (p(l) (D))lly(())m))//())))))) demonstrating that exponential dependence enters only through the latent subspace dimension d and not the ambient dimension D. Some further remarks regarding Theorem 3.3 are in order. First, we can obtain a brgb-brobbiility bound with minor modifications to the proof; we omit these details in the interest of brevity. Second, our n (2((5)) rate nearly matches the minimax optimal rate of score matching from Wibisono et al. (2024), but with the subspace dimension d replacing the ambient dimension D; we leave showing n 2/(444)) rate to future work. Last, as noted before, Chen et al. (2023b, Theorem 2) proves a related result for learning score functions under the subspace structure (3.8). However, Theorem 3.3 substantially improves their result in the following ways. First, as already mentioned, our result does not require any specialized architectures, but instead applies to learning directly in the Barron space Fi of single hidden layer neural networks. Additionally, our result also provides several technical improvements: (a) our leading dependence on n improved to n -2/((++)) from n -2 (22-0(())/(d+)) 6 and (b) our dependence on o; is improved to oz
4/((++)) instead of or in the regime as t - 0.
We now use Theorem 3.3 to provide an end-to-end sample complexity bound for sampling from pu- Corollary 3.4. Fix E, (0,1). Suppose that po follows the latent structure (3.8), and that both Assumption 3.1 and Assumption 3.2 hold. Consider the exponential integrator (3.4) with:
T = co log
<VDV
=
C
DV
P0 E2
log²
VVV VDVMO
+ "logg
(T)]] (3.11)
and reverse process discretization timesteps { defined as:
[2
if (O..... (O.....NN2), if E (N/2 N...
T T 22/2
(3.12)
Next, define the forward process timesteps {4:) N-1 by L; = T TN-i- Suppose the exponential integration scheme is run with score functions {St, as defined in (3.9). Suppose furthermore that n. satisfies:
(ir 0 J.=-- where Sr, arg argmin...... Lee (5) with F
D2 (I(pz ()) B)) v 33 - (d45), D3 n 3 Ōa(1) max {
ς3
where n-(-) is defined in (3.10). With constant probability (over the randomness of the training datasets {D&, (N1)), ), we have that (L(p; || Law(fr-c)) < e?, where Law(Or-<) refers to the distribution of the random vector ÿr-ç.
Treating and B as constants, Corollary 3.4 prescribes a rate of n > Ōa(1) poly(D))- (after burn-in on n)) to obtain a sampler that satisfies KT || Law(rr-<)) < 62. To the best of knowledge, this is the first end-to-end sample complexity bound for learning a diffusion model over single hidden layer neural networks that adapts the intrinsic dimensionality of the problem. Note that as Corollary 3.4 controls the KL-divergence between the true data distribution pe and the distribution (a) of the final iterate of the exponential integrator (3.4), by Pinsker's 's inequality this also implies control on the TV-distance ||p: - Law(Or- (rr-r)llt tv- Furthermore, we can upgrade Corollary 3.4 high probability guarantee by utilizing a high probability variant of Theorem 3.3.
The parameter& Ç > 0 is the early stopping parameter often found in practical implementations of diffusion models (cf. Karras al. (2022)). Note that this is necessary since is supported on a nower-dimensional manifold and hence V log Po is not smooth on all of RDD We remark that bounds comparing the original po to Law(yr-C) are possible in Wasserstein distance by adopting the techniques from e.g. Chen et al. (2023d, Section 3.2); we omit these calculations.
'However, their logarithmic dependence is only through log 0(1) (m) terms instead of our log 0(4) (m).

---

Published as a conference paper at ICLR 2025
Compared to Chen al. (2023b, Theorem 3), who obtain > Ou(L)(E ((1) rate in the case of latent subspace-awe aware architecture, we see that our bound also improves the dependency on Ç. This is important, because ultimately will be chosen decay remark, however, that Chen et al. (2023b, Theorem 3) only depends polylogarihmmially on the ambient dimension D instead of polynomially. This can be traced back in their analysis imposing the constraint that their score functions are uniformly bounded, i.c., sup=, [ls(2, t)ll < K, which allows truncation arguments to avoid picking up extra PDly(D) factors. We choose to not impose such constraints our model class, as this adds another hyperparameter that must be tuned in practice. We leave open the question of whether or not these poly (D) pre-factors in the sample complexity can be removed without further modifications (e.g. clipping) of the F1 hypothesis class.
co. We do
Compared to Oko et al. (2023, Theorem 6.4), Corollary 3.4 also relaxes a few technical assump- tions, including uniformly lower bounded density To. and a requirement that xy be Coo0 near the boundary [-1, 11 On the other hand, their work obtains sharper rate on W1 (Po, Law(fr-s)) & (3--)/(d4+)) for any å >> 0. We also leave open the question of whether these extra assumptions can be used to strengthen our guarantees for learning over F1.
3.2 LEARNING LATENT INDEPENDENCE
We now consider different kind of latent structure here generated by independence opposed to the low-dimensional subspace setting just studied. Specifically, we suppose that for some E [D].
Io = U2u
20 ~ (=0
(K)),
(.).
(3.13)
where U E O(D) E UT -T ID). E Rd. with Σ d. = D, and where =66" is
independent of 2(()) for * This setting differs from the previous case in that the latent structure considered is probabilistic and not geometrie; it is possible for 2o to satisfy (3.13) but still be fully supported on R.P. Similar to the linear subspace setting, we assume that the orthonormal matrix U, the number of components K, and the dimensionality of each component {d, ) are all unknown to the learner, and we study the adaptive properties of Fi in the presence of this latent structure. We begin by imposing a similar set of assumptions as in the subspace case (cf. Section 3.1).
Assumption 3.5. For all i E [K]. we have that To is 3,-sub- Sab-Gaussian (for 3r > 1), ie..
Eexp(A(11))) E11000 I)) < exp()?3)/2),
A R.
Our next assumption again deals with the latent measure T., defined as the marginal distribution of
UZz, We decompose (2 (1) 24 (x)) into coordinate groups as for 2o, and we define
(5) ae as the marginal distribution of zi
Assumption 3.6. For all i [K]. V log (0) is L, Lipsschtttz (for L; > 1) on IR for all t t> 0.
As before, we define some shorthand notation for E [0, 7) and i [K]:
(4)
(5) Vorvd, : cLi(u!) V + | To (
(0))).
Ht, = 10
where 14 (8) = (EI 0 and > 1 is universal constant. Furthermore, we combine the = E and M4, == oá V a D.VD. D.
individual constants together as p4n == v (1
Finally, as before, we let pa == lim Pi,z and μ == lim, Mt,z. Mirroring Theorem 3.3, we first bound the eиror on the learned score functions under the latent independent structure (3.13).
(8)
Theorem 3.7. Suppose that follows the latent structure (3.13), and that both Assumption 3.5 and Assumption 3.6 hold. Fix a > O and define
K
F. := R
|| & Rc). RS :=
Σ
20.-5
(3.14)
1=1
where R(O) does not depend Suppose that satisfies
(t) poly(D,1/o,, Mr, V B) max poly (Li, Mi g(0).
(
(3.15)
sE[K]
7

---

Published as a conference paper at ICLR 2025
Then, the empirical risk minimizer B E arg E. (()s) satisfies:
DeK
D2 (Me V 3)).
Ep, (R.) < (1)
(Ls(pl,2 (9) V 8.)) (un v B)p + + of
ofn
Ignoring all parameters other than K and n, Theorem 3.7 states that the score matching risk (R,(R) scales as ED, [R.) S >>= (K/n)3/(d++5) which again captures the intrinsic dimensionality of the problem. To the best of our knowledge, this is the first result establishing score function error bound in the setting (3.13) that depends primarily on the latent d, 's. Our final result mirrors that of Corollary 3.4 and establishes an end-to-end sampling guarantee for this setting. Corollary 3.8. Fix e, C E (0, 1). Suppose that Po follows the latent structure (3.13), and that both Assumption 3.5 and Assumption 3.6 hold. Consider the exponential integrator (3.4) with (N, T) as in (3.11) and reverse process discretization timesteps {Ti)<=o N.N. defined as in (3.12). Next, define the forward process timesteps NN-11 by 14 == =T- -N-i- Suppose the exponential integration scheme is run with score functions {8t; J where St, E arg mi.. (s) with Fr as defined in (3.14). Suppose that n E mo(C) satisfies:
(1)D ((AAT)//(L(PP)) V 3))4:+3, E (0 Õ(1)D²
n > (mL V 3) max
max SE[K]
C²
where no(-) is defined in (3.15). With constant probability (over the randomness of the training datasets NN')), ). we have that KL(P; Law(ýr-s)) E
Corollary 3.8 states that n > poly( (D)/5 [[ poly (K)= (de++) samples (ignoring (zz, B, L:) suffice to ensure that KT,Ppc || LLa (ūr( & e². We note that, unlike the latent subspace setting of Section 3.1, given Assumption 3.6 is possible to prove a bound on KL[(po || Law(Or-c) directly, since V log Pt is uniformly Lipschitz for all > This can be done by using Chen al. (2023d, Theorem 2) to analyze the backwards exponential integrator process (3.4) instead of the results of Benton al. (2024). We elect to utilize the latter's analysis in the interest of consistency with Section 3.1 where it is required.
3.2.1 NON-ORTHOGONAL INDEPENDENT COMPONENTS
Section 3.2 shows that diffusion model based on a single hidden layer network can adapt to hidden independent component structure. A natural question is whether this extends to the non-orthogonal case, similar to independent component analysis (ICA) (Herault et al., 1985). Here, we explain why a direct extension of our argument works at t 0 case, but breaks whenever > 0 since the addition of noise breaks the independence structure. We then use data whitening to address the issue.
Recall from (3.13) that 20 ( ..... .0. (k)) where r(()) E Rdi for d1 +... dx = D, and where each of the K components are sampled independently. Now, let us assume that xo Azo. where A E DxD is invertible, but not necessarily orthonormal. Note that for t 0, the score A A- log TO 1ill (P.A-'a). where P. E Rddx x selects the d, coordinates that correspond the i-th variable group. Hence, the score function has the structure of sum of low-index functions, and the Fi norm of the score can be bounded in terms of the sum of Fi norms of each component. However, once isotropic noise is added, this structure is lost in general because the isotropy is not preserved in the latent space (z, = (m-ao + +,w) = m220 + --w).
function V log Po can be expressed as V lo
A possible fix for this issuc is to first whiten the data, and then to apply the results of Section 3.2 to the whitened data. Specifically, write Cov(2o) = AΣAT, where is a block diagonal matrix with K blocks _ (()) Now consider the transform To = Σー A-t which orthogonalizes the components and whitens each of them independently. Indeed, Fo follows the latent structure (3.13), and hence the results from Section 3.2 directly apply to Z.. However, one caveat with this approach is that the whitening factor 111 A- must be learned from the data samples 2/ ~ Po(.). Standard results in covariance estimation (see e.g., Wainwright, 2019, Chapter 6) allow us to learn 1/2 accuracy. It is an interesting question that we leave to future work to study how the associated estimation error propagates through both the learning and sampling procedures when obtaining final sample complexity bound.
Σ 1-1/2A-1 (modulo rotation) up -1122
8

---

Published as a conference paper at ICLR 2025
D 2
D
D-8
D 10
D 32
D 64
Figure 1: Hidden linear structure. Experimental results comparing the performance of a single hidden layer neural network. two hidden layer neural network, and random feature model in the presence of a hidden linear structure. The target is eight-mode
mode Gaussian mixture model in d = dimensions embedded into D dimensional space via an unknown orthogonal transformation; this transformation used to project generated samples down to R². The Barron model continues to perform well in moderately high dimension which is consistent with our theory, whereas the random feature model struggles to identify the orthogonal transform and performs significantly worse than the other two models.
4 EXPERIMENTAL RESULTS
In this section, present experimental results that verify our theoretical claims. To this end, compare the performance of a single hidden layer (Barron) neural network with a random feature network (Bach, 2015; Rahimi & Recht, 2007) and two hidden layer neural network as a function of the ambient dimension D on two synthetic tasks that isolate the hidden structures we analyzed. To make the comparison as fair as possible, all networks are trained with gradient descent for 2.5 x 10a steps. We use a cosine decay schedule that initializes the learning rate from 5 x 10-4 and ends at The single hidden layer neural network has a hidden layer width of 1024 neurons; to keep the number of parameters fixed, the corresponding random feature model has 2048 neurons. To avoid an unnatural reduction in width for the two hidden-layer neural network, we keep the width fixed at 1024 rather than fixing the number of parameters. We sample from each learned diffusion model using 1024 evenly-spaced timesteps on the horizon E [0, 5].
Hidden linear structure. We consider data points x RD given by = Uz where z e Rd with d = 2 drawn from the Gaussian mixture model = N Σi N(H,, Σ.) with N = 8. Here, U E RDxd is random orthogonal matrix that we keep fixed across all networks for constant D. We take Σ, 1 for all i and μ4 (cos (251) .sin (2x2 ) which leads to eight-mode, narrowly-spaced mixture evenly distributed on the circle of radius r = 5. We study the performance of each network architecture as a function of D ranging from D Results are shown in Figure 1, where we visualize 5 x 10s samples = UT T from each model. In each case, performance degrades as D increases, reflective of the increasing difficulty of the learning problem. Notably, performance degrades significantly more rapidly for the random feature model than for the Barron model despite the fact that both models have the same number of parameters; in particular, for D = 32 and D 64, samples do not lie within the visualized frame because the model becomes unstable. This is consistent with our theory, which predicts that sample complexity guarantees for Barron will depend exponentially on d = 2 rather than D, whereas the random feature model does not adapt to the latent structure Bach (2017). Unsurprisingly. given its extra parameters and additional nonlinear layer, the two-layer network maintains the highest performance for all T).
D 64 in powers of two.

---

Published as a conference paper at ICLR 2025
D 2
D=1
D D=8
0 16
D= 32
D 04
randon foature
barron
talp
Figure 2: Product of hidden independent components. Experimental results comparing the performance of a random feature model, a single hidden layer network, and two hidden layer network for dataset with hidden independence structure. The target product of K four mode Gaussian mixtures in R forming randomly rotated square, so that
2K: each mixture has different random rotation. Approximate samples are generated in R² and only the first mixture visualized. Similar to Figure I, the single hidden layer (and two hidden layer) network is able to detect the hidden independence structure, while the performance of the random feature model rapidly breaks down.
Hidden independent components. We now consider data points x (x1, T2, ,x xK) where D = K'd and each Σ₁ E Rd. We again take d = 2 for visualization, and we draw each from the Gaussian mixture model Pk - E N(uE, E;) with N = 4. Similar to the previous experiment, we take Σ, / for all and n4 (cos 2ná N" + Φu) sin (2 + dic) where 6% (n,f 2T) is fixed across all network architectures for fixed D. This construction ensures that each block 2y Ra is drawn from a Gaussian mixture with four modes placed on the corners of square of side length /2r that has been randomly rotated by an angle Φv in the plane. Results are shown in Figure 2, where we visualize 5 x 10 samples of d1 E IR2. Similar to the previous experiment, Barron networks significantly outperform random feature models, while the two hidden- layer network outperforms Barron.
R.
5 CONCLUSION
In this work, we showed that diffusion models based on single hidden layer neural networks applicd data from distributions that contain low dimensional structure specifically, linear subspace and hidden independent component structure exhibit favorable sample complexity bounds that primarily depend on the latent dimensionality of the problem, thereby avoiding the curse of dimensionality. We accomplish this by leveraging the low-index structure of the Barron space, which allows us to avoid specific latent-aware architectural modifications and computationally intractable sparsity constraints, both of which have been used to obtain similar results in earlier work.
Several exciting future research threads arise directly from our study. The most pertinent direction is to increase the scope of the latent structures covered by our analysis. to include, for example, non-linear manifolds. Another related question is whether or not favorable results that avoid the curse of dimensionality can be shown for latent diffusion models (Rombach et al., 2022), which first learn an autoencoder before learning a diffusion model in the autoencoder's latent space. On the algorithmic front, an interesting open question is whether or not gradient-based optimization algorithms can efficiently learn the low-index structure associated with the latent models studied in this paper. Finally, improving of Wibisono et al. (2024) with the latent dimension playing the role of the ambient dimension is another exciting area for future work.
rates to match the minimax optimal score estimation rates
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pp. 4782 4887. PMLR, 2022.
Michael S Albergo, Nicholas M Boffi, and Eric Vanden-Fijnden. Stochastic interpolants: A unifying framework for flows and diffusions. arXiv preprint arXiv:2303.08797, 2023.
Brian D.O. Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-328 1982. ISSN 0304-4149.
Marloes Arts, Victor Garcia Satorras, Chin-Wei Huang, Daniel Zugner, Marco Federici, Cecilia Clementi, Frank Noé, Robert Pinsler, and Rianne van den Berg. Two for one: Diffusion models and force fields for coarse-gar coarse-grained molecular dynamics. Journal of Chemical Theory and Computation. 19(18):6151-6155 2023.
Francis Bach. On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions. arXiv: 150.0060000 November 2015.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1-533 2017.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling. Advances in Neural Information Processing Systems, 35: 25349-25533 2022.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear con- vergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024.
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768-9788 99783, 2022.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and langevin sampling. arXiv preprint arXiv:2002.00107. 2020.
Valentin De Bortoli. Convergence denoising diffusion models under the manifold hypothesis. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative model- ing: user-friendly bounds under minimal smoothness assumptions. In Proceedings of the 40th International Conference on Machine Learning, 2023a.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 6672-4712 PMLR, 2023b.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. In Advances in Neural Information Processing Systems, volume 36, pp. 68552-68575. Curran Associates, Inc., 2023c.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023d.
Sitan Chen, Giannis Daras, and Alexandros G. Dimakis. Restoratioo-degraaatioo beyond linear diffu- sions: a non-asymptotic analysis for ddim-type samplers. Proceedings of the 40th International Conference on Machine Learning, 2023e.
Lénaïc Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Over- parameterized Models using Optimal Transport. In Advances in Neural Information Processing Systems 31, pp. 3040-3050. Curran Associates, Inc., 2018

---

Published as a conference paper at ICLR 2025
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. arXiv:1812.07956. January 2020.
Frank Cole and Yulong Lu. Score-based generative models break the curse of dimensionality in learning family of sub-gaussian distributions. In The Twelfth International Conference on Learning Representations, 2024.
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at time. arXiv preprint arXiv:2305. 18270, 2023.
Carles Domingo-Enrich, Alberto Bietti, Eric Vanden-Fijnden, and Joan Bruna. On energy-based models with overparametrizzd shallow neural networks. In International Conference on Machine Learning, pp. 2771-2 PMLR, 2021.
Zehao Dou, Subhodh Kotekal, Zhehao Xu, and Harrison H Zhou. From optimal score matching to optimal sampling. arXiv preprint arXiv:2409.07000 2024.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2826-2836 PMLR, 2021.
Weinan E, Chao Ma and Lei Wu. Barron spaces and the compositional function spaces for neural network models. arXiv preprint arXiv:1906.. 08039, 2019.
Bradley Efron. Tweedie's s formula and selection bias. Journal of the American Statistical Association, 106(496):600--6611 2011.
Xuefeng Gao and Lingjiong Zhu. Convergence analysis for general probability flow odes of diffusion models in wasserstein distances. arXiv preprint urXiv:2401.179555 2024.
Margalit Glasgow. SGD finds then tunes features in two-layer neural networks with near-optimal sample complexity: case study in the XOR problem. The Twelfth International Conference on Learning Representations, 2024.
Yinbin Han, Meisam Razaviyayn, and Renyuan Xu. Neural network-based score estimation in diffusion models: Optimization and generalization. In The Twelfth International Conference on Learning Representattinss, 2024.
Jeanny Herault, Christian Jutten, and Bernard Ans. Detection de grandeurs primitives dans message composite par une architeture de calcul neuromimetique en apprentissage non supervise. 10" Colloque sur traitement du signal des images, 1985 p. 1017-1022, 01 1985.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pp. 6850-6851. Curran Associates, Inc., 2020.
Arthur Jacot, Seok Hoan Choi, and Yuxiao Wen. How dnns break the curse of dimensionality: Compositionality and symmetry learning. arXiv preprint arXiv:2407.05666 2024.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. short note on concen- tration inequalities for random vectors with subgaussian norm. arXiv preprint (xXiv:1902.0372 2019.
Tero Karras, Miik Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. Advances in Neural Information Processing Systems, volume 35, pp. 26565-26577. Curran Associates, Inc., 2022.
Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score matching: The view from isoperimetry. In The Eleventh International Conference on Learning Representa- tions, 2023.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, volume 35, pp. 28870-22882 Curran Associates, Inc., 2022.
12

---

Published as a conference paper at ICLR 2025
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201, pp. 946-985. PMLR, 2023.
Jason Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polynomials with sgd near the information-theoreii limit. arXiv preprint arXiv:2406.01581, 2024.
Gen Li and Yuling Yan. Adapting unknown oow-dimesiional structures score- based diffusion models. arXiv preprint arXiv:2405. 2024.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprini arXiv:2408.0233 2024.
Xiang Li, John Thickstun, Ishaan Guirajani, Percy S Liang, and Tatsunori B Hashimoto. Diffusion-Im improves controllable text generation. Advances Neural Information Processing Systems, volume 35, pp. 4328 4343. Curran Associates, Inc., 2022.
Yuchen Liang, Peizhong Ju, Yingbin Liang, and Ness Shroff. Non-asymptotic convergence of discrete- time diffusion models: New approach and improved rate. arXiv preprint arXiv:2402.13900 2024.
Yaron Lipman, Ricky Q. Chen, Heli Ben-Hamu, Maximilian Nickel, and Matthew Le. Flow matching for generative modeling. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Xingchao Liu, Chengyue Gong, and Qiang Liu. Flow straight and fast: Learning to generate and transfer data with rectified flow. In The Eleventh International Conference on Learning Representations, 2023.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory, pp. 3-17. Springer, 2016.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-Layers Neural Networks. N0Niv:880000650 August 2018.
Shahar Mendelson. Learning without concentration. J. ACM, 62(3), June 2015.
H.N. Mhaskar. On the tractability of multivariate integration and approximation by neural networks. Journal of Complexity, 20(4):561-58) 2004.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribution
estimators. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 26517-26582. PMLR, 23-29 Jul 2023.
Ali Rahimi and Benjamin Recht. Random Features for Lcrge-Scale Kernel Machines. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition (CVPR), pp. 10684-10695, June 2022.
Grant M. Rotskoff and Eric Vanden Vanden-Fijnden. Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach. arXiv:180) 0005000955 July 2019.
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94, 2015.
Justin Sirignano and Konstantinos Spiliopoulos. Mean Field Analysis of Deep Neural Networks. arXiv: arXiv:1903.0m 044404 November 2020.
Jascha Sohl- Dicksteei, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Con- ference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp.
2256-2265. 2265. PMLR, 07-09 Jul 2015.
13

---

Published as a conference paper at ICLR 2025
Yang Song, Jascha Sohl-Dickstein Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. bosre-based generative modeling through stochastic differential equations. In International Conference Learning Representations, 2021.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, volume 23, Curran Associates, Inc., 2010.
Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500) 2323, 2000.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 1st edition, 2008.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Paseal Vincent. A connection between score matching and denoising autoencoders. Neural Computa- tion, 23(7):1611-1674, 2011.
Martin J Wainwright. High-ddmennsionl statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
Yuqing Wang, Ye He, and Molei Tao. Evaluating the design space of diffusion-based generative models. arXiv preprint arXh::2406. 2024.
Joseph L Watson, David Juergens, Nathaniel R Bennett, Brian L Trippe, Jason Yim, Helen E Eisenach, Woody Ahern, Andrew Borst, Robert J Ragotte, Lukas F Milles, et al. De novo design of protein structure and function with rfdiffusion. Nature, 620(7976):008--11
2023.
Kilian Q Weinberger and Lawrence Saul. Unsupervised learning of image manifolds by semidefinite programming. International journal of computer vision, 70:77-90, 2006.
Andre Wibisono, Yihong Wu, and Kaylee Yingxi Yang. Optimal score estimation via empirical bayes smoothing. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 4958-4991. PMLR, 2024.
Kaihong Zhang, Heqi Yin, Feng Liang, and Jingbo Liu. Minimax optimality of score-based diffusion models: Beyond the density lower bound assumptions. In Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 60134-60178. PMLR, 21-27 Jul 2024.
14

---

Published as a conference paper at ICLR 2025
A
PROOF IDEAS
Here, we outline the key proof ideas behind the results in Section 3.1 and Section 3.2. We focus discussion exclusively bounding the error of the score function estimate, as translating score error into sample quality bounds is already well-established
the literature (cf. Section 2). For this discussion, we fix specific value of O, noting from our discussion in Section (specifically Equation (3.7)) that we learn separate score models for a fixed sequence of forward process timesteps (1, (1)) N-1
A.1 BASIC INEQUALITY
Recall that 8, arg migginng..s.. (s( is the empirical risk minimizer (ERM) of the empirical denoising loss L, over the function class F = {s R2_ + RD || < Rt). where the norm bound Rd will be determined. Our first step uses the link between the L2(p)) score error Rs(s) and the DSM loss (s(s) in addition to standard arguments from the analysis of ERM to show the following basic inequality for all > O:
(R, & (1+E) inf Re(s) + ED, sup (Cr(s) - (1 =1+ - C.. SEF,
(A.1)
#EF
where C. Etr Cov (m, 24)) vx). The basic inequality (A.1) contains three key terms: an approximation-theeree theoretti term Ti := + E) infses, R&(s) which measures how well the Fi-norm bounded subset F approximates the true score, uniform convergence term T2 := Ep, supse.s, [s((s) (1 + [s)) over the function class F,, and a third offser term Tş := E C which trades off a fast rate for T3 (controlled via E) with the constant offset C2 between the score error and the DSM loss. In addition, the first two terms are in tension with each other, and must be carefully balanced to achieve the desired rate.
A.2 APPROXIMATION OF STRUCTURED MODELS WITH Fi
Our analysis based on careful control of the approximation error term Ti in (A.1) of the structured models consider in way such that the requisite Fi-norm R2 does not depend exponentially the ambient dimension D. This is accomplished by first understanding the low-dimensional structure present in the score functions V log Pt. and then arguing that this fow-dimensional structure can be approximated with a norm bound R3 that depends reasonably on D.
Subspace structure. We first consider the low dimensional subspace from Section 3.1. Under this model, we have the following expression relating the score V log pt to the score V log m of the latent 21.
Proposition A.1 (see e.g., Chen et al. (2023b, Lemma 1)). The following decomposition holds under the subspace model (3.8): v logpt(x) = UV log n. (UT
1 of
(T UU
(A.2)
Independent components. We next consider the independent structure from Section 3.2. Under this model, we have the following decomposition for the score.
Proposition A.2. The following holds under the independent components model (3.13):
V log = Σ UP ( (P.UTT).
(A.3)
where P; E R. selects the coordinates corresponding to the i-th variable group.
Note that the proof of Proposition A.2 follows directly from the standard change of variables formula, and the fact that the distribution of w is unchanged when pre- multipleee by UT.
The score function decompositions (A.2) and (A.3) both exhibit similar structure, where latent score functions are embedded into a score function the ambient space via linear encoding/decoding process. Fortunately, this embedding preserves the Fnomo of the underlying function.
15

---

Published as a conference paper at ICLR 2025
Fact A.3. Let f :R + Bd have bounded Fi-norm, and ler U O(D, Consider g: .R + R defined as g(x) = U(UTx)) We have that 1g = llffl
Hence, if the latent function f IR + R can be approximated well in Fi, then the embedded function is also approximated well with the same Fı norm. This is the key observation that enables results. Concretely, suppose that f R2 + Ied has bounded Fi norm and approximates f ; -Rd - Rd via sup: f f())]l E. Then, ((x) U f(UTx) approximates g(z) U f(U (T)T) via
(DDM) (l (xx) < e. and |l [l,
It remains to argue that F1 can approximate low dimensional functions well. Fortunately, the approximation properties of Fi functions over various function classes is well-understood (Bach, 2017: Jacot et al., 2024). In particular, utilize the following Fi approximation result for Lipschitz continuous functions, adopted from Bach (2017, Proposition 6).
Lemma A.4. Let f : R Rd be L-Lisschita and B-bounded on (z(d, M). Define K == LV. For any (0, K/2), there exists fe Fi such that supze B2 M)) (x) f=(x)] & and:
(d+1)/2
K
K
llfell, & Oa(1)K
log ld+11/2
A.3 UNIFORM CONVERGENCE OF THE DSM LOSS
With the approximation result in place, we turn to the analysis of uniform convergence term T2 in (A.1). Since the DSM loss is least-squares regression problem, for analyzing generalization error with smooth losses (Srebro et al., 2010). However, the main technical hurdle here is dealing with the fact that the data tuples (zr,, x7a) are uniformly bounded, which is a technical assumption needed in many of these arguments. While this can be handled straightforwardly for fixed time via standard truncation arguments, one challenge is ensuring that the resulting high probability bounds degrade nicely as t + O. The reason this is necessary is because the smallest timescale to used will ultimately scale with the number of datapoints n.
utilize existing results
To highlight the class of issues that arise in our truncation arguments, consider the latent score function V Voog πe arising from the subspace structure setting (3.8). In order to apply trunca- tion argument for analyzing T2, we need to argue that |/V log Tz(=)] is bounded uniformly over a high-probability truncation set z (2,d, M) By the continuity of V log Tr, we know that sup.eBI(d.M) V log <z(=)]l = A, co. However, we need to control the behavior of A, as f - O. By leveraging the perturbation analysis of Lee et al. (2023), we show that for all > O, under our assumptions, the inequality ||V log +=(2)] & L(1 + ||=|]) holds for all 2 E Rdd. Hence, we can bound
A, < L(1 + M) for all f 0.
B EXTENSION TO STOCHASTIC INTERPOLANTS
In this section, we describe how our approach can be extended to learning the drift field entering in flow matching models (Lipman et al., 2023; Liu et al., 2023), stochastic interpolants (Albergo et al., 2023), and probability flow ODE- samplers in diffusion models. To this end, we observe that every method can viewed as building a stochastic interpolant with linear coefficients
It = a(t)= + 8(t) (0)) a(1) 0,
(B.1)
((0) = 0, B(1) = 1,
where xp N(0, 1) and . p² drawn from the target data density, A common choice is given by att) = 1- and (() = f. In this section, we use the convention of interpolants and flow matching models, which exactly interpolate on [0, rather than doing so on [0, oo) like diffusions. Moreover, we fix the base density at = 0 and the target density at t = 1, which is opposite from the convention
7 As an alternative to boundedness, one could also rely on small-ball arguments (Mendelson, 2015). In the interest of keeping our assumptions minimal as possible, do pursue this approach.
16

---

Published as a conference paper at ICLR 2025
considered in the main text; (3.2) for how this construction works in the diffusion model setup. Given (B.1), the drift field entering the probability flow equation is given by
b(xr t) = E L æt = 2]
(B.2)
while the score field is given by
s(x, () ((1)
1E [20
1t 2]
(B.3)
The following argument is also given in Albergo et al. (2023). We first observe that é; - á((()x0 - ((t)z and then solve (B.1) for æ1 to find that
31
(xe - a(1)=o)) 3(1)
(B.4)
Hence, plugging in to (B.2), we find that
b(rr, 1) E a(()ar + 3()=z1 1t 1x =x]
E
((()zo + +()())
(x:: -a(()=0)
1xz x
B(1)
((1)) (((0)
((t)a(t)
3o + B(I)
]
E
It. = x
3(1)
B(1)
(B.5)
B(1)((1)
E [ro Ihe x² + B(1)
à(t))
B(t)
B(t)
((t)a(t) B(t)
B(t)
a(t)
a(t) s(x, t) + B(t)
so that b(r, can be entirely re-written in terms of the score s(x, t). This shows that the Fi-norm of b(x, t) the same as the Fi-norm of s(x, t) up to time-scaling and an additive O(D) term coming from the linear term. Hence, similar sample complexity bounds which we derive in Section 3 for learning score models can also be shown for learning the drift field b(x, l).
C PRELIMINARY RESULTS
We first make explicit the relation between the matching error R2 and the denoising loss Lt. In the sequel, we will make frequent use of Tweedie's formula (see e.g. Efron, 2011):
m.To Iz
log (z.)) [V log (z, mo) xx).
Vlog x0)
of
Fact C.1 (DSM loss minimizes score). We have for all sufficiently regular s R + R.:
R((s) L((s) - Ct.
(C.1)
where the offset constant Ce is given by:
MyKo
C = Etr Cov
I't
o
Furthermore, we can bound C, by:
C. < D/o
Proof. The standard proof for denoising score matching (see e.g. Vincent, 2011, Section 4.2) shows that for all
R+( Lx(J) E pt
V lo [0)
17

---

Published as a conference paper at ICLR 2025
Hence,
(z))
log ge (x
2
m4.00
m4200
E
of
of
m2
7,
-EE
I2
2t
0
MyJ0
Ft
- E tr Cov
It
07
-
To bound Ct, we observe:
C. = E tr Cov
my:00 - St
E tr Cov
w
at
< E B/lo// = Dio?.
of
We next state a result from Benton et al. (2024) regarding the quality of the samples generated via the exponential integrator scheme (3.4).
Lemma C.2 (Sampler quality from L2 score bounds (Benton et al., 2024, Theorem 2)). Fix a T > 1 and Ç (0, 1). Also fix N E N++ which is and satisfies N > llg((1/C). Define sequence of strictly increasing backwards process times (Ti (Ti)
[2 1)
i (O,..., N/2],
7:
T 22/N
if (N/2+ L,..,N.
(C.2)
Let 7/4 = T+41 Ti for E .O....,N 1}. Suppose we have N score functions še(x) for N-1 which satisfy:
t (T -1)e0
N-1
Σ
BB B. ST
V PogPT- PT
2 Scoore
(C.3)
Then, we have the following guarantee for the exponential integrator (3.4):
KL(Pę || Law(Dr-c) S eccore + x² DN + x(DT + mn) + (D + mo)e
where po are defined as:
= 2(T 1) + 4 (lg((1/C)
== E ro
N
Proof. In order to apply Benton et al. (2024, Theorem 2), we need to compute a & such that:
Y & k min (1, T 1.11), vk E (O....,--3 -1.
To do this, we follow the proof of Benton et al. (2024, Corollary 1). First, for l E (O...., N/2 1}. have that t++1 & T and hence T' + > (T' 1) 1. Hence, we can simply take >> 2(T 1)/N. Now, for k E [N/2,.... N - 1}. we have that fx+1 2 T 1, and therefore t++1 T (T 1) Hence we need K. such that 2h R( tk+1). We therefore
compute:
-200111- = < <(T (++) = 2((+1)//
From this that > Ç- 2/N -1 is required. A sufficient condition takes:
2/N 1 1=
exp log(1/E)
2 < 1 (e - 1)
log(1/() -1
since ex x1 (e- 1)x for r E [0,1]
N
4 1lg((1/C)
N
18

---

Published as a conference paper at ICLR 2025
Hence, in total we can set:
2(T - 1) + 4 logg(g/())
N
The result now follows from invoking Benton et al. (2024, Theorem 2).
Note that an immediate consequence of Lemma C.2 is the following observation: for any e E (0, 1). setting
VDV
DV po
VDV
loog ( 1
T co log
N
C1
log²
Mu
e2
for some universal positive constants co, C1, have that
KL(p< Law(Or-c) S
e
Next, we state a technical lemma regarding a perturbation result for Gaussian mollifications at small scale.
Lemma C.3 (Score function perturbation (Lee al., 2023, Lemma C.12)). Suppose that p(x) is a density on TRd such that v (ogp(x) is L-Lipschitz on IR. For a ž 1, define the corresponding density Pa (x) := p(az). Let 7 denote N(O, oa distribution. If L 1/(2a² then we have the following bound for all a E Rd:
V/ log - V VlogPa * (x)(1))
& 6a Lovdd (a + 20 La 1)L||=|| (a 1 Lo V Vlog
The previous mollification lemma is next used to bound the score functions uniformly over time.
Proposition C.4. Consider a forward diffusion process 2t m4z0 asw on IRd, Let denote the marginal distribution of 2t for all > Suppose that log ग. is L-Lipschitz (for > 1) on I&d for all 3 Defining L == cL(BB|20 zoll Vd + | log (o()))) where e 3 is an universal constant, we have that for all t and Rd.
Iolog & L(1 + ||=|]).
Proof. Define (2) = m, no ( which the density of the random variable m, Hence, have that ne R4 * 7op By Lemma C.3, whenever L & m² (2o we have that:
V log n. (0)l & 6m,² L (m, 1 + 2m, Lo || log (o]]-
We now compute the range of i's for which & m (2o?) holds. Using the specific form m,, dt.
< m
exp(-22
2T
log 1 + 2L
tu
cxp(-20 exp(2t) -
2
First, note that since we assume L >> 1, then we have that t, is bounded by universal constant. Hence, for & t..
V log n. (0)] $ L(Vā + | log (0)1))
Hence for any z,
I log (>)] < L||2|| V log (0)
< L| + ( loV (0)))
< ccL(Và V log (0)))) + |=|]).
On the other hand, when > L., more work is needed. When 2 L,, first bound:
0, 1 22L +1.
19

---

Published as a conference paper at ICLR 2025
Define two events:
: Billol/oa xr] 4Vd/orJ.
E2 = :1(ll 4(E]|2o0l + of vdd
By Markov's inequality we have that:
P., { < 1/4, P., (22) < 1/4.
Now suppose that Ei S &g. Then, we have a contradiction, since:
1 1/4 < P.. {ET) & (x)( & 1/4.
Hence, there must exists an w E Ef such that w & &g. Hence, there exists a & satisfying:
V log TH (=.)l < B||lw|//o, 2 2,] < 4vd/or, || & 4(Bl + o.Vd). Hence for any 2,
V log ni (2)]l
< L|2 2/| V log m (3))
< ||||||| 4L + + 4Vd/o,
< + vd) 4v l)d
< <
|=]l))
Next, we state Los approximation result for scalar-valued Lipschitz function from Bach (2017). Lemma C.5 (Lo approximation of scalar Lipschitz functions (Bach, 2017, Proposition 6)). Let f: d + R. Suppose that is L-Lipschitz and B-bounded on B2(d, M). Set := BV LM. For
any y > Oa(1) K there exists an fr. F1 such that 115l| < and:
2/(d+1)
K
[5(x) - [+(2) & Oa(1)K (d
sup
log
K
Our next result a simple technical fact which we will utilize in our truncation analysis. Proposition C.6. Let S, Š be two X-valued random variables over the same probability space. Let f X + be a measurable function. We have:
B[f(S)] & (VEI + + (E( P $3.
Note f is non-negative, then we have the simpler bound:
E[S(S) < E[S()) + + (
Proof. We have:
B(s(s)) = ( 5)1
= =E[S())1SS +])(s) $3
$1]
+ $11
< B[f()) V ESS + 5) + (I $3.
The next result is a simple algebraic fact which will be useful for solving for implicit inequalities involving logarithms.
Proposition C.7 (Log dominance rule, (see e.g. Du et al., 2021, Lemma E2)). Let b, v be positive scalars. Put == (1 + v) Then,
m va log" (vab) = m logo (bm).
20

---

Published as a conference paper at ICLR 2025
Next, have an intermediate result to bound the Rademacher complexity of F1 Fi-norm bounded functions. Proposition C.8. Let ||::|| for i [n]. We have:
D =
E (())))(( & <
(ec)
sup (.)
where the E {+1}d are independent Rademacher random vectors and > 0 is universal constans.
Proof.
Define Xu,v
Observe that for Wi, U4 B2(D) for E {1,2).
a 1 (0((1)) (app))))-(((()) (1122 Σ a((2,,))))u u2, 64)
Xuy.²1 Xug.22
Ti + T2
First, recall that a Rademacher random variable is 1-sub-Gaussinn Gaussian, and therefore (u, Ea) is also -ssub-aussian since ||u,|| || < 1. Using the fact that ReLU 1-Lipschitz followed by Cauchy-Sehhe Schwarz and the assumption that | <
(o((v1, x.)) o ((v2, z1)) < (01 U2 x.)1 & || -2/l-
Hence, (o((u), - ((022, (u), =,) is ||e1 U2 woyl-sub-Gaussee Suussaaaa Consequently, Ti is ||1 vell/ httl:///-uuu-Gusssiiii Similarly, since (002,, xx)i < 1, we also have that T2 is ||ul - u2 u2ll/ / sub-Gaussian, Hence, the sum Ti T- is sub-Gaussian with constant:
/ 2 - 22 + ||u - u2 /
Letting w = (u, v), we consider the following metric on = B2(D) x B2(D): d((u1, v1), (w2, 02)) v I| u2112
|00 U2 12
Hence for any w1,w2 E Ωt the difference Xws Xwz is 22/n d(w1, w2 ) --su---aussiae Therefore we can use Dudley's inequality (see e.g. Vershynin, 2018, Chapter 8) to bound:
TE sup X & en 1/2 /-- d1) = 112 f welt
Vlog (e: de
Next, fix and let {uz}, {wi} be e/ /2cooves of B2(D). Let [u] (resp. [v)) denote the closest point in the cover to u (resp. v). Given (u, v) E Ω we have:
d((u, v), ([u), [v])) = / ||u [u] ||0 [o| < Using the standard volume estimate the covering B2(D) (see e.g. Vershynin, 2018, Chapter 4),
log N(=; & 2Dlog(1 22/2/s).
Consequently,
V2 sup X & en 11/2/2D wel
V 2og(1+2V2/e)d) d' c'v
/ D/n.
Our final preliminary result translates the previous bound Proposition C.8 to a bound on the Rademacher complexity of Fi-morm balls.
Proposition C.9. Let F {s R + IRd |||||, & R). For any &s E B2(D, i E [n], we have:
(Ennf(E))) < cRM cRMV V
D
E (c.) sup n
where the e, E {+1]d are independent Rademacher random vectors and e is a universal constant.
That is, each coordinate of [=1]d is an independent Rademacher random variable.
21

---

Published as a conference paper at ICLR 2025
Proof. For any { and f I, observe that by the definition of F1:
n (e, f(+:))
T
Eis / uo (v) du(u,)))
71
Ee (() du(u,,)
1 n
R sup
Σ
(5x, ((),,
M
n
Hence,
(E sup n fE
Σ c f(+:))
& R- Bla
sup W
Σ len (),
Y2
from which the claim follows by Proposition C.8 and using homogeneity of ReLU to scale the data points &e to (D)
D Fi APPROXIMATION THEORY FOR LIPSCHITZ CONTINUOUS FUNCTIONS
Here we develop the necessary results to establish that F, functions can approximate structured score functions in an efficient way. Our first result a preliminary result that allows translate Lo approximation bounds to L2 bounds. For what follows, let the notation P(X) denote the set of subsets of X.
Proposition D.1. Let M: (0, + P(RD) be such that:
E (0, 1), Pzizp, (ar M()) > 1-166
Suppose that R(e, 8) satisfies the following condition: for any positive 0 and 5 E (0,1) there exists a function & RRD + DRD such that
|| R(E,5),
sup ||$(z) v Vlog < xEM(6)
(D.1)
Suppose there exists a 8 E (0, 1) satisfying:
(=/2,0) & coE /Bl/ 8 & (Eoo))/)//D
(D.2)
Above, both co, Ci universal positive constants. Then, there exists 8 RDD RD such that:
|| < R(s/2,6),
||s v log pel Iz(ps)
E.
(D.3)
Proof. Let Eg (x, E M()). By assumption, we have that PPEG)) > 1 5. Put 8, V log and let 9 RD + IR D be as guaranteed by the assumption such that:
||ا|| & R(E/2,5), zEM(8)
sup [|((z) - (x)) < E/2.
Hence,
Eg, || - = Ey,, ||$ $- s, 11(c) + E,, $ - (1
< sup =EM(6)
|[((x) (x))) + E.,, || s211 v6
(E/2)² + Ez, $ 111 Vo.
Consequently, by taking square root of both sides:
|| /11ppp))) < < || 5. (.1l2((0) 61/4
22

---

Published as a conference paper at ICLR 2025
Let us now control ||s s. s.llea(ma)- By triangle inequality and |((2)]| & || for all x::
|| (pl) || + I|s. (1a(()))))
|| || (o. 1|
R(ee/2, () 2al(p)) +
|| La(p))
To control (8xlLa((p))) we use Tweedie's formula:
70
Elwo xrl]
V (l = E
Ft
of
Hence by Jensen's inequality and the tower property.
1
3D² 07
8 (s po))) og
El|E[w
xx]]l*
< a0
B
B||w||
<
Combining these calculations.
31/1DD
|| sallea(re) < ( +
Tt
Hence,
| - sxl( + R(e/2,0)llzellaa00 + 31/aVD
84/1
Hence, we set such that:
32/4VD 82/1
R(s/2, 8)1 82/1 & E/4
E/4
01
then we conclude that || sx1lez(0)) E.
We next turn our main Los approximation result for Lipschitz functions. We proceed in steps. First, we extend Lemma C.5 to vector-valued Lipschitz functions in a straightforward way. Then, we use the log dominance rule invert the result. For the first step, we have the following result.
Proposition D.2. Let f Id + Rd. Suppose that f is L-Lipschitz and B- B-bounded B2(d, M). Ser Ka = d (BV LM). For any y 2 Oa(1). Ka. there exists an fyy Fi such that f & 7 and:
2/(d+1)
Ka
7 Kg
sup <E
- fa(()) & Oa(1)Ka -
log
(D.4)
Proof. For E [d], fi(x) == (e,, (x)), where 6, E IRd is the i-th standard basis vector. We will apply Lemma C.5 to each of the fi's. Note that each fi is also T--Lipschitz and B-bounded on B2 (2,d, Hence, for every i [d] there exists an fax E Fi with [1 & 7/d and:
Ka
Ka
2/(d+1)
sup 1f((z) - fa,(2a) & Oa(1) d (d
log
= C.
Ka
Choosing fn = (fr,,,..., Sa:a) yields:
sup (d
(1
sup (d.M)
Σ -
[f(()) fn,(1)) & Vaç.
sup BEBa(
To finish the claim, we bound the Fi norm of fz. Since
[~(1) Σ (af))()),
by triangle inequality ||lla & Ei & d. (7/d) =7.
23

---

Published as a conference paper at ICLR 2025
We now execute the second step, where we invert the RHS of Proposition D.2 and solve for 7 Lemma A.4. Let f R - Rd be L-Lipschitz and B B-bounded on (2 M). Define K == BV LM.
For any (0, (/2), there exists an fe E F1 such that supze Z Bald, M) I [x) f=(x)] < and:
(d+1)/2
lIfela. & Oa(1)K
K
log (d+1)/2
Proof. Setting the RHS (D.4) from Proposition D.2 to E and rearranging terms, we need the following condition to hold (recall Ka == d K):
(oa(1)Ka))
(d+1)/2
log (d+1)/2
Kd
Kd
Using Proposition C.7, sufficient condition is:
?
Oa(1)
(Qa(1)Ka))
(d+1)/2
log (d((21)/22
Oa(1)
(a(l)KKa
(d+1)/2
Kd
8
The claim now follows by simplifying these expressions with our assumptions.
E UNIFORM CONVERGENCE FOR THE DSM LOSS
Our first step is to establish the claimed basic inequality (A.1).
Proposition E.1 (Basic generalization inequality). Let F be any set of functions mapping I + R. Let fo E I denote the DSM empirical risk minimizer:
St E arg min L.)).
FET
Then, we have for any E 3
Ep. (R(fi] & =1+ inf R,(f) + Ep, sup [4((f) - -1++))(()))))))))))) C FeF
JE3
Proof. For any >/ 0 and any f f F.
ED. [R. ED, [f.( - Cc]
using Fact C.1
= ED, (f:) - (1 + + - G.
ED. (f)) (1 +=))(()++(+++)( C.]
since fr is an ERM
ED, (f) - (1 (=+=))((())((1=))((( - C.
since Ep, Ep,(((()) = L(()) using Fact C.I
ED, (C(()) - - -(+=)))(()==(11)))) +e. C.
& E.D sup [C.() (1 (1+)) (1 +e),.() + Ct. jE
The claim now follows by taking the infimum the RHS over f E F.
The rest of this section will focus on the uniform convergence term in the basic inequality (A.1). We first define some notation which we will use in our analysis. Let vz Z,) denote a distribution over pairs of truncated vectors, parameterized by 8 E (0, 1), defined as follows:
VB (aw v.)) (8)),, ((E) > 1-
(E.1)
Note that in the above definition, the event (8) lives in the joint probability space of (æo, 2x). The specifics of the event (5) are left unspecified for now, as they depend on the underlying details of our latent structure. However, we will require the following properties to hold almost surely for some (5) and (r.g(())
(0o, F4) vs = || & Pi.z (8) and || log (5. Bb0oll (o)
(E.2)
24

---

Published as a conference paper at ICLR 2025
Next, define the population denoising loss over Va
() = (E (Tt( log (e [i)
(E.3)
Furthermore, given a dataset D. = { x/) 1 the generalized empirical loss is defined as
(.(:D.)) = E (i v log gi ( =
(E.4)
Note that the above definitions are used only in our truncation argument, and do not appear in the actual learning procedure.
The main result of this section is the following bound on the uniform convergence term.
Lemma E.2. For R& 2 1, define F, = {s: R - R || < RaJ. For E (0, 1], we have:
E sup [C((f) (1 (1))
SEF.
R ae Della. + D/o?
(((I)(++ET)
+0(1)
n
n²
The proof of Lemma E.2 follows immediately from the following two results (invoking them both with 5 n-1). The first result applies truncation argument that it suffices prove uniform convergence over truncated data.
Proposition E.3. Fix 8 10. Define the truncated random pair (3o, Tt) ~ Vö/n (cf. (E.1)). Let on
the truncated dataset D: = {(06 =t){== be iid copies of Te), i.e. D. b/n" R2 > 1, define F, {s: D + RD || & Re). For all E [0, 1]. we have that:
For some
E sup [C((f) - (1+ (1+))(((f) SE3.
+((] (allaip + 2o,2D) - (1 < E sup [1 (1+ je
82/2
where e >> 0 is a universal constant.
Proof. Let Eg denote the event &g == (D; = Dí}. By union bound, P(Ea) > 1 - 8. Next we
define for dataset D, the random variable:
(D.) = sup [C,(f) - (1+ (1e))
(E.5)
fE3.
Applying Proposition C.6:
(D.) & [[v(D.)] + (v ((22 + (D.))(D.))) 81/2. 81/2
(E.6)
We next need to upper bound both:
E (De() Efv)(D,))
To do this, first derive few intermediate bounds. We start with:
L(()) = (x (x;)
V log x0)]1
< (x
2 log de (x;
=2
since (a b)² < 2(a² + 12)
& +
since |/ & R
-2R + +
25

---

Published as a conference paper at ICLR 2025
Next, we have:
2 2
E sup (2) = E. sup Se
1
Σ
n
[f()))
V log ge (a²) mb))?
71
2
2
11
|
11
|| | 11?
since llf & Rs
not
i=1
4R
4
B|
E| 11
IE|
Cauchy-Schward
not
1=1
1=1
< 1
+ 1212/00
Hence,
EDD) < E sup [C((f) - (1+ SE3:
S sup (f) + E sup 12(
SE3F
JE3,
S B1 || + D²
Now we move on to bounding (D.)) Defining & = (6/n),
कt - - = (z+ mczo) 1(Ex) = oww- 1(Ex)
and therefore:
BlI(E,
(1{,) < Elw//of1 < 3D3/0
Hence:
l[(())) - v log q: (5) =t>11ع) 2
1 n Σ
sup (f::))) = E sup
SE3.
SEF.
n
2
2R
n
2
n (3) mmbk)/
E
|
since ||ll| & Re
n
no?
4R4
4
||
B
Bl| 0000
Cauchy-Schwarz
no
1=1
4R4
B|
11
Bll - 0
no!
4R
n
E B1
/o:1"
n
no
1=1
4 1 + 12D2/O0
Therefore, we conclude that:
max [E| R Bw. & +
(E.7)
Plugging (E.7) into (E.6),
([v((D)) <
+0, 81/2
E sup
[L((f) - (1+)) D. c + t DD) 88/2
feF.
E sup (f; - (1+ 2) DJ] sup [L((f) - [.(5://]] JEF,
feF.
+ 12 + -.- 81/2
26

---

Published as a conference paper at ICLR 2025
Next, define:
Vy((, = [1( v lo x)]]
Observe by Jensen's 's inequality we can bound
E|V? ((zo, xz))] < E sup ((( S = + D²/0/.
SE.P
Therefore, by application of Proposition C.6,
E[V,((20, =1))] < ((o, &))] B ((ro v8/n
[[Vr +,)] c' (R) [ 1l + b vō/n.
Hence,
[2,() - (.188/11) FEF.
sup
= sup
B (()0)((0))))) x: (VVoV((VVV,, +.))
FE3,
< R Fz (px) + DD vō/n.
from which the claim follows.
L
The second result proves uniform convergence over truncated inputs. Proposition E.4. Fix E (0,1). Define the truncated random vectors (zo. .2) ~ Vojn (ef. (E.1)), and let Dr Von For some Rd 2 define F, {s R & E (0, 1), we have that:
+ RD ||s||s & Re)- For all
E sup (L((J:8/n) - (1+ SE9.
RR (5/n)D Ō(1)(+--)))
(8/m)
Te + D/o?
+ +
n
n²
Proof. Let fr,,= == -e, (5/n) and similarly Pe,g = ().(8//) We first observe that the following holds almost surely:
lI())) V log (#t, fo)ll < Rella, + V (e #1)1l
Reja, + Ptg =: By-
We consider the hypothesis of functions:
H = [(, [f( v log Iz)|| f E Fi).
defined over the support 2 == supp (z)) and coupled with the loss function d(2) =2. which 2-smooth. From Srebro al. (2010, Theorem 1), we have with probability at least 8 over D., for all h E Hi9
Blo(h(2o, < 8)
Σ
(his #t)) + (1 (1+ de log n R. +
B2 log(1/0)
(E.8)
where >> 0 is universal constant, and R, (H) denotes the Rademacher complexity of H::
1
RR (H) = sup E, sup kEH 1=1
Σ
h(2))e,
Zi:h C2
We now bound this Rademacher complexity term. Let G denote the shifted function class:
g = -(,,))) f(x)
V log q (7
x)) f E F.)
Note that ignore the labels y the setup of Srchro al. (2010, Theorem 1), they immaterial.
27

---

Published as a conference paper at ICLR 2025
Letting gu 9 and 2, (2), Z for i [n]] be arbitrary, we have:
Ee sup kEH
h(z))ez
= Eg sup gEg
++)1((>))11
< Eg sup aEG
Σ (((l((=))1 (=))) =
+ E
e (2))0(
LEg sup gEG
Σ ex ((1g((=)) [=00)))]1
190 (=:)
Jensen's 's inequality
Eg sup
(l9g(())) -
Σ (g0(22)) (2:)l?
since 9o
9.9 EG
Eg sup
-((0(=)))-11((()))) (z)())
(0o(2))
since is symmetric
9.9' g.g'E9
< 28, sup gEg 1=1
+())(=))|| + VnBu.
Next, we proceed with Maurer (2016, Corollary 4), which allows to bound, for Rademacher random vectors 7/ E (+1)
Eg sup JEG i=1
Σ e1]l((2))1 & V2E, sup gEG
(Tag g(x))
/2E, sup fe
(ra ((x))
S Roji, v Dn,
where the last inequality uses Proposition C.9. Putting the terms together,
1 S (Bejk, + jur.n) Vni
(H) S aR VD+ Bx) vn
From (E.8), with probability at least 1/n*, for all h E H:
R R2 D 22.
(())) < (1 + e) Σ ((M(5)) #()) + (1 + & "')lol"""
n
That is, with probability at least 1/n²
RG D p..
((1)(1+
sup - SE
Call this event 8'. We have that:
E sup (L.(f:0/)) - (1/ (1+)))())) SE3,
E sup (L fEf.
E sup (4 IE3,
RE D + i2.
(0(1)(++e=))
E sup (1(0:-0))- fEF.
n2
28

---

Published as a conference paper at ICLR 2025
To finish the proof, observe that:
Lr(J: R (1x)) (d) kn)l
< 2 log ( o0)l
< 2R 2E (
< 21/ (x+ m,
/ /0
2| + 2D/07.
On the other hand, from (E.7),
E sup (.) + SE
Hence, combining these bounds together,
E sup [L.(f:8/n) (1 + el FEL
RG D pig
R& Fr (L + D//0
2 ((1)(1+E7))
+
n2
Y1
F ANALYSIS OF SUBSPACE STRUCTURE (SECTION 3.1)
We now specialize the previous approximation and uniform convergence results to the subspace structure setting.
Proposition F.1. Fix an M > 1. For any E (0, LM/2), there exists fe Rd + Rd such that SuP (2( - V log (2)] < E, and
[e < Rin (c, M) (40))L))(43//24111
log log (d+1) (LM/e).
(F.I)
Proof. We will invoke Lemma A.4. To do this, we first observe for any E B2(d, M), using Proposition C.4,
V log (+))] < L(1 + [|=l]) < 2LM.
On the other hand, we know that V Vog na is L-Lipschitz. The claim now follows from Lemma A.4.
Our next task is to upgrade the previous result to an approximation result for the ambient score V loo Pt, using Proposition D.I. Proposition F.2. Fix an s E 10, There exists an 8 RR + RDD such that:
||ا| & Od(L)(L(p).= 8)))4433/22 + 2(D d)/o?, ||@ - V Vlogpillez()) E
(F2)
Proof. Define
M(6) = { x1 < As).
A5 colo. + /oog(11/))
We note that the condition (2, ( å holds for an appropriate choice of co.
Now, given e, (0, 1), from Proposition there exists h Rdd + Rd such that:
|Íاي < Rin As),
[i(()) V (e)) < e.
sup Ad
Embed h to a function : R + R by:
8(z) = Uh
-1-
oo
29

---

Published as a conference paper at ICLR 2025
and observe that (cf. Proposition A.1):
sup xcM(6)
[|((x))
(x)]
sup [[Uh(UTx) x) UV log (U x)]l xEM(6)
sup [lÁ(UTz)) x)) Vlog क. Tr(( (U x)
xEM(
sup [1h(2) =e,,(d
V log n. (2)ll
S.
Next, we bound the Fi-morm of s. To do this, we first bound the Fı-norm of (I UUT)2 by
representing it by the following sum of Dirac masses
D-d Σ
(()) + 6(--..-)))
and hence ||+ (U- )
)alll, < 2(D d). Next, recall by Fact A.3 that || + UA(UTz)]
[ Combining these results,
|| < |r + Uh(UTa >))l
of || (I UU-UU
< | + of
o d) & Run (e, A8) + of (D) d) =:e(s, 6).
(F33
That is, we have shown that for E > 0 and 8 E (0.1), 1). there exists s: RD 1 IR such that:
|||| < R),,
sup (EM(
||((x) v (z)] <
This verifies condition (D.1) of Proposition D.I. We now need to solve for a ó_ which satisfies the conditions listed (D.2). By several applications of Proposition C.7, the conditions listed (D.2) are satisfied with a 6, E (0, 1) satisfying:
LD
log(1/6.) & &O((1) log
Since we do not track the exact form of the leading Oa(1) constant, we skip the specific calculations. The result now follows from Proposition D.I after estimating R(E/2, 8.). First, we bound,
As. co(ur, + //log(1/))) = Ōa(1)(urs ().
Hence,
R(e/2,0, < (a(1)(L(mn, V1)1
Therefore, the result follows.
Now we have the tools in place to prove Theorem 3.3, our main score estimation result for this section.
Theorem 3.3. Suppose that po follows the latent structure (3.8), and that both Assumption 3. and
Assumption 3.2 hold. Fix a > O and define
D
x. R P |||||e < Re), R == Ryn 3[+t)
+
(3.9)
o,
where R2 does not depend on Suppose that satisfies
n n> no(t) == (,, 1/ar, Pt, V 3) poly aL,, ur, V 3).
(3.10)
Then, the empirical risk minimizer & E arg min (8) satisfies:
D2 (L(mr + v 8)
D3
Ep, (8)) < Ōo(1)
+ +oa(0l og (Me, V 8)2.
onn
The explicit dependence of R, the other problem parameters is detailed in the proof.
30

---

Published as a conference paper at ICLR 2025
Proof. First, by Proposition F.2, know if we set R₂ be
Rs ===
- 2(D-d)/of
then, have inf EE (s(s) E
Now we need to apply Lemma E.2. To do this, we need to define our auxiliary truncated random vectors (cf. (E.1)). We choose the definition:
(6) == [ & po + (o2/)))) ||m|| < VD + log((/00)
(F.4)
which by sub-Gaussial concentration followed by union bound satisfies ((E)(0)) > 1 8. Note that under this definition of & (6), we can take:
a (0) S Pt,z + lol/l/o011)) (r) S (VD+ Vlog(1/8).
(F.5)
By applying Lemma E.2, we obtain for (0,1),
sup [C((f) - (1 (1+)) (())())))))))))))))))))))()))))) + D [R v v3) + 1/0 fE3.
By the basic inequality Proposition E.
ED, (R+((i((i)) 28 +0((7-1) D ([. ( (14 v 3)
D2
+ -a( no, (Pt.z V 3)² +7 Ct.
We now optimize this expression over both E E (0, 1). We first optimize both expressions ignoring the constraint that E < 1. First, optimizing over y, set
7 7= )
1 C.
(a+ P (I(Me, v 3 v3 + no,
DD2 (Me,z V 332
and from this we obtain:
Voll))
C.D. (I(Me, ())dd3g-((++) vB) (d(1)) C,D2 not (Me B)?
ED, (R((f)) < 20 26
n
Now optimizing over e, we set
C.D (i(pe, V ()) (pe, v v32 1/(4+5)
E = Ōa(1)
and obtain:
C&D (I(u, V 4)) (Ma v 8)2
2/(d-3)
C.D2 not (Mea V 8)2.
Ep, (R, < Ōd(1)
+
+Oalll
The proof concludes by setting n large enough that both 6, 7 <
We now restate and prove Corollary 3.4, our main end-to-end bound for the latent subspace case.
Corollary 3.4. Fix E, (0,1). Suppose that po follows the latent structure (3.8). and that both Assumption 3.1 and Assumption 3.2 hold. Consider the exponential integrator (3.4) with:
VD <VDV
DV E²
m
(VDV!1)) E
(c] (3.11)
T log and reverse process discretization timesteps {T defined as:
=
ci
log?
+ log²
[ 1)
ii .......N/2.
T;
T 24/--
iiE (N/2 1,.... N).
(3.12)
31

---

Published as a conference paper at ICLR 2025
Next, define the forward process timesteps {ta):=0 N-1 by t, == T TN-i- Suppose the exponential integration scheme run with score functions {šr, - where Sr, arg se. Li, (s) with F as defined (3.9). Suppose
furtoeermm furthermore that n satisfies:
n 3 Óa(1) max {
D2
e (d+5), De (I(Mz (B)) ()))++((2 V vB g
where (-) is defined in (3.10). With constant probability (over the randomness of the training datasets {Dt;) > ), we have that KT(pe || Law(fr-c)) & E?, where Law(ÿr-() refers to the distribution of the random vector ÿr-c.
Proof. Using the bounds Mt.z. & fz and He, & Ma. from Theorem 3.3 we have that the following ERM bound holds for all & T]:
D² (L(us v 1)) v 83)
2/(445)
D3 (né v 82).
Ep, (R)( & Oa(1)
+
+dal1)
not
not
Furthermore, since e = < 1 x/2 for x [0, 1.59). then for E 0.795 we have
of = exp > t - 1/0 < 1/t.
On the other hand, for > 0.795, we have the bound
of = = 2t) > exp(-1.59) > 0.796 1/0 - 1. Combining these inequalities we have that 1/0 < 1/ S 1/f for all >
Hence, using the choice of T, N from (3.11) and { as specified in Lemma C.2, we have that:
BpBrr- 1
V loog lo
k=0
D2 Ōa(1)
2/((+5)
D3
2 T
(T(uz v 3)) (12 B3)
+ 02(1))
nc3 (n2 v (2)
nc
VDDVp na ) (oac))
D2 (I(me v3)++3 v 82)
2/(d+5)
D3
< log
+da(1)
nc3 (n v 82)
ng
Hence, in order to make 22 eocore conditions hold:
< E2 we need to take n large enough such that the following
log VDV V pO
D2 (I(uz v 3 v B32)
2/(d+5)
Oa(1)
S6²
nc
VDV nO
D3 ō,(1)
log
ne3 (u B2) $62
8
Hence, we need to take n satisfying:
Ōa(1) max (
D2 {2 (TAMs v 3)) (n2 v82)) 8 (d(3)
D3
C3 ( v
B2) --1)
o-1
On the other hand we also need to take n > no(C) (cf. (3.10)). The claim now follows.
G ANALYSIS OF INDEPENDENT COMPONENTS (SECTION 3.2)
We follow a very similar structure as in Appendix We first start with an approximation result.
Proposition G.I. For M and i E [K]. For any (0, M2M, there exists fe ; g4 + Rdd. such that sup (d. (I
log (1) (=)]l & e, and
log ||lll & Rii M) (4 (ogh//111(((0))))0 (4,
(G.1)
32

---

Published as a conference paper at ICLR 2025
Proof. The proof is nearly identical to Proposition F.I. and therefore omit the details.
Next, we upgrade the previous approximation result to approximation in (p(e). Proposition G.2. Fix , (0, 1). There exists an 8 : RDD RD safisfying:
K
K
|AlA <
Ou (1)(La( v 8)) Σ 1=1
1d++1)/2 (
|| V loggell<a(pe) &
Proof. Recall that P. E Rd D selects the coordinates corresponding to the i-th variable group (cf. Proposition A.2). Define the sets ())) as:
()) = (x ( ||P,Uxx|| < }. A!" = -- + B: (oVlog(1/)) i [K].
With appropriate choice co, we have that P PaIMpe for (8) > 1- 8. Given e (0, 1), from Proposition G.I, there exists h4 Rd + Rd for E [K] such that:
| < Rind (c, A sup (E
[lda(z) log t (=)] <
Now define &; := U.UPP...PPU z). Observe that:
[|; UP U log o. (1)
(P)UTz)]1 <
sup [[,((P,UTT)) v Vlog (P.U x)ll x
sup (B)
sup [1)(()) V lo (x)1
=EBydd
E..
Next, observe that ||& |lalle by Fact A.3. Invoking Proposition D.1 as is done in the proof of Proposition F.2, have that for all i E [K] |
UP. log n. (1) (llUT)) & e, and
|| Ōa (1)(( v (.)) (d+1)/2
Recall by Proposition A.2 have:
Log = UP.. V L (P.UT))
Hence, setting& Ex11= 8i, we have that
|| - V Poggee (.s(pr)
Σ ( (P. xx))
(huUP xx) - V Vlg (1) (P.U (x)))))))11
since P.P.T = for $
|| - UU..V (P.UT.)))
[=1
Furthermore,
|||||
|ا J1
Σ
33

---

Published as a conference paper at ICLR 2025
We now prove Theorem 3.7, our score estimation result for the independent components setting. Theorem 3.7. Suppose that follows the latent structure (3.13), and that both Assumption 3.5 and Assumption 3.6 hold. Fix >> O and define
K R
:: {s: Re:RR RRR | & Re),
(3.14)
i=1
where 12) does not depend on n.. Suppose that n satisfies
(t) pDly(D, 1/05, Me, V B) max poly (Lis ( V g()).
(3.15)
sE[K]
Then, the empirical risk minimizer & E arg min (s) satisfies:
K
DaK o7n
(Ia(pe V B:)) (M2 B)p -
D2 onn (Me, V B)2.
ED, (+)) < Σ Oa, (1)
+
Proof. Here we minic the proof of Theorem 3.3. First, by Proposition G.2, we know if we set RG as
K Ps Σ
(1)L (.))) (d4+1)/2 (d)21/1)
1=1
then, we have in (((s)
Our next step is to apply Lemma E.2. To do this we need to define auxiliary truncated random vectors (ef. (E. In this case, we use the definition:
(6)
n [1 11=0011 ||
+ t n [|lw| < vD /2
(G.2)
KE[K]
which satisfies (0)) > We have
(0) S 1t, (oog((/0)) (0) S 2 + vlo((1/)).
By applying Lemma E.2, we obtain for y (0,
E sup (f) (1 + +7)+((11 SEF,
< 1(1)-11 D (Me, v 8)² + 1/0?
DK <
Σ (4,(1) ( v (d1tt) vB) + Ô(1) D
yo!?
1=1
By the basic inequality Proposition E.I,
ED. (R((f)
+
DK
Vo v.)))..-33 -d:++11 (d (Me B)²
n
D
Ō() mou
+ 7 C₁.
We now need to optimize over both E;, E 10, We first set as:
DK K
D v) Ō(1) (d.4)((4 (d:+1)) (He (
(1)(La(1)))
1 Ci
no?
T=1
from which we obtain:
(1) (Ia(p ( V +.3,)) (dc+1) (ditt)( V 1882 + Vo()
C.DK
C.D. no?
Ep, [R)) &
34

---

Published as a conference paper at ICLR 2025
We now set E as:
CDDK (I,(u (1) V ( V 8)2
1/(4++))
= (1
and obtain:
CDDKK (Li(ku (6) V v.)) V 833
2/(d++3)
CDD no;
Ep, (R.(F) & Σ (1)
+ +101)
i=1
The proof concludes by setting n large enough that all of E < 1.
Finally, we conclude with Corollary 3.8, which provides an end-to-end sampling bound.
Corollary 3.8. Fix e, Ç E (0, 1). Suppose that po follows the latent structure (3.13), and that both Assumption 3.5 and Assumption 3.6 hold. Consider the exponential integrator (3.4) with (N, T) as in (3.11) and reverse process discretization timesteps {Ti) defined as (3.12). Next, define the forward process timesteps (--1 by t, == -N-i- Suppose the exponential integration scheme is run with score functions {&t, }N -1 where 8t, E arg min,es, (s) with F, as defined in (3.14).
Suppose that 2 no(() satisfies:
(aT(1)D2 ((4AT)//(L( V 3)) c
Ö(1)D2
(1L V 3)2 max
max iE[K]
C²
where (-)-) is defined in (3.15). With constant probability (over the randomness of the training NN11), ), we have that KL(pe Law((r-<))) & 6².
datasets {Dr, (1o,)
Proof. We follow the proof of Corollary 3.4. Using the bounds Pi.x
< piz and Me,r & Mas from
Theorem 3.7 we have that the following ERM bound holds for all [0,
D2K oi
D2 +1D
Ep, (()) <
(1)
(Li(1l) V B.)) (mz V v32
+
(mz B)².
onn
1=1
Recalling that 1/0, 6 1/5 for all > S, using the choice of T, N from (3.11) and ftz fm we have that:
Σ mh E pr 1 V log Pr 1|
VDV n10
K Ōa (1)
D2K (Li(nl) v 3.)) (uo v B)2
2,73
$ log
(n
VDV V 140
D2 Ō(L))
+ log
(2n (Mz 8)2.
Hence, in order to make 22 2ccore conditions hold:
& =², we need to take n large enough such that the following
VDV
K
D2K
log
Σ
(1(11)
(I,(11) ( V 3:)) (ux V 832 Gn
Sea
c
VDVNO po
D2 0(1g
log
(uz V v32 S
E
C2n
Hence, we need to take n satisfying:
(1 (d)+7))/2 (1 V 3)) . (di+3)
Ō(L)D²
n > (n) V 2 max
max
KE[K]
On the other hand we also need to take > no(C) (cf. (3.15)). The claim now follows.
35


Reviews:
[{"review_id": "G74fOg67WF", "reviewer": "Reviewer_iFA5", "summary": "This paper investigates why diffusion models, specifically those utilizing shallow neural networks within Barron spaces, can effectively learn and sample from high-dimensional data distributions that possess hidden low-dimensional structures. By focusing on Barron spaces—the function space of single-layer neural networks—the authors demonstrate that diffusion models can adapt to simple forms of low-dimensional structure without the need for specialized architectures. They provide theoretical results showing that the sample complexity for learning these models depends polynomially on the intrinsic latent dimensionality rather than exponentially on the ambient dimension. The analysis includes end-to-end sample complexity bounds for learning to sample from structured distributions, highlighting how shallow diffusion networks can circumvent the classical curse of dimensionality by leveraging the low-index structure of Barron classes.", "questions": "- To what extent can the assumptions of Lipschitz continuity and sub-Gaussianity be relaxed? Are there alternative conditions under which similar results could be obtained, possibly broadening the applicability of the theory?\n- Can the authors elaborate on the practical aspects of optimizing over Barron spaces?\n- In practical scenarios, data often contain noise and may deviate from idealized models. How robust is the proposed approach to such imperfections, and what modifications, if any, are needed to handle real-world datasets?\n- Given that non-linear manifolds are noted as future work, could you share any preliminary insights on how extending to non-linear latent structures might impact sample complexity or theoretical guarantees?\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper provides a rigorous theoretical framework that explains how diffusion models can overcome the curse of dimensionality by adapting to low-dimensional latent structures within high-dimensional data.\n- By leveraging Barron spaces to model shallow neural networks, the authors bridge the gap between theoretical tractability and practical relevance, as these spaces capture essential features of networks used in practice.\n- The work offers comprehensive sample complexity bounds that depend on the intrinsic latent dimensionality, providing valuable insights into the efficiency of learning diffusion models for structured distributions.\n- The results do not rely on specialized network architectures tailored to specific latent structures, emphasizing the general applicability of shallow diffusion networks in learning hidden low-dimensional structures.", "weaknesses": "- The analysis is restricted to shallow (single-layer) neural networks, which may not capture the complexities and representational power of deep neural networks commonly employed in state-of-the-art diffusion models.\n- The theoretical results are derived under idealized conditions, such as target distributions concentrated on low-dimensional linear manifolds or composed of independent components, which may not fully reflect real-world data complexities.\n- Optimizing over Barron spaces can be computationally challenging due to the infinite-dimensional nature of these function spaces, raising questions about the practicality of implementing the proposed methods.\n- Minor typo: Line 315 (difference -> different?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7kplMT8hT2", "reviewer": "Reviewer_NgbV", "summary": "The paper explores the effectiveness of shallow diffusion networks in learning distributions with low-dimensional structure, challenging the traditional belief that high-dimensional data inherently suffers from the curse of dimensionality. The study provides sample complexity bounds for these models, showing that they depend more on intrinsic latent dimensions rather than the ambient space, thus offering insights into the strengths of diffusion models for structured data generation.", "questions": "- Can the analysis be adopted to flow models/matching, which instead regresses a network onto the vector field of probability ODE (rather than the score)? \n- Can the authors give comments on how the analysis can be extended to discrete state spaces, for applications such as discrete diffusion models for language modeling?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The research presents a theoretically grounded approach to understanding the success of shallow diffusion networks, especially for low-dimensional structures in data.", "weaknesses": "The reliance on Barron spaces, while insightful, could pose challenges for scalability and model tuning in larger, more complex network architectures, which are crucial to modern success of diffusion-based generative models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y7bPIRCgPI", "reviewer": "Reviewer_USAA", "summary": "The paper shows that learning diffusion model in Barron spaces (spanned by single-layer neural networks) avoids curse of dimensionality by adapting to low dimensional subspace.", "questions": "Included in weakness.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Solid paper with concrete mathematical analysis. The results in the paper could be of general mathematical interests for related fields.\n\nThe paper makes a meaningful step towards understanding the gap between curse of dimensionality in theory and no curse in reality.\n\nThe paper has nice connection with recent progress in diffusion sampling process.", "weaknesses": "I have problems with calling results on \"single-layer neural networks\" by \"results on shallow networks\". Neural networks with a few layers are also shallow and the authors don't prove for them here. I'm not going to start a lecture on logic, but a paper should always try avoiding unnecessary confusions, especially those that make people think more favorably than it actually deserves.\n\nThe setting of single-layer networks is way too simple. The industry of deep learning scales to using 100k H100s, yet theories still are struggling with analyzing single-layer networks.\n\nThe formula in the theorems are complicated. If a simple setting leads to such convoluted formula, what would the more general cases be like?  Usually simpler things are more useful. It would benefit the presentation if a neat bound could be given the main body and a more detailed bound given in the appendix.\n\nLack of analysis of the gradient descent training process of neural networks.\n\nLack of direct usable implications. What could practitioners benefit from the theories? Or what future development of the theories could lead to some algorithmic innovations that is beyond imagination of practitioners? Machine learning is rather noisy compared with things like Physics. It's the best if we can get something useful from theoretical understandings.\n\nLack of experiments. The authors have proposed a set of assumptions which they believe is meaningful and proved results under these assumptions. It would be extremely beneficial to prove that these assumptions are relevant for the real world tasks and experiments on either simulation or real world data support the claim of the theorem. In theories, one inevitably chooses many simplification to make things elegant, which is quite understandable. However, experiments are needed to show that these simplification doesn't make the theoretical results irrelevant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y54mWbcrZe", "reviewer": "Reviewer_kfcb", "summary": "This theoretical work shows that for a neural network which is infinitely wide, and where neuron parameters come from the hypersphere, \nand there is one of two hidden latent structures in the data, then there is a bound on the emprical risk minimizer which only\ndepends on the dimension of the latent structure and not the dimension of the ambient space. \n\nIf we denote the ambient dimension as D, the two hidden structures considered are 1) a linear combination of lower dimensional \nvectors (of dimension d << D) and 2) a linear combination of independent components all of lower dimension than the ambient \nspace, but but where the sum of the dimensions of the components sum to D.", "questions": "**Questions:**\n\nQ1: On line 42-44 you write: \"these works leave open the difficulty of statistical estimation, and therefore raise \nthe possibility that the sampling problem’s true difficulty is hidden in the complexity of learning.\"\nCan you explain what you mean by this? \nEspecially, \"the difficulty of statistical estimation\", do you mean how close the estimation can get to the true distribution?\nAnd \"the sampling problem’s true difficulty is hidden in the complexity of learning.\", what do you mean by this?\n\n\nQ2: Line 165: W.r.t. risk for score function being asymptotic to $n^{-2/(D+4)}$. Do you mean asymptotic as $n \\to \\infty$? \n(If yes, this could also be written in words, then you could avoid introducing the extra notation.)\n\n\nQ3: Line 175-179: Can you give some intuition of the F_1-norm? Is it right that F_1 is the functions for which the integral is bounded \nfor all their basis functions? And does that mean the F_1-norm is the smallest integral for the \"largest\" basis function? \n\n\nQ4: In line 180, you say that you only consider neuron parameters from the hypersphere. Is there a reason why this \ngeneralizes to neuron parameters chosen over the entire space? If there is, I would like that argument added. \nIf there is not, I think you should add this assumption in the part of the introduction where you state your contribution.  \n \n\nQ5: In line 231: In your shorthand notation, you define $\\mu_{t,x} = \\mu_0 \\lor \\sigma_t\\sqrt{D}$. I am used to $\\lor$ being \nthe logical \"or\", but that cannot be what you mean in this context. So what does it mean here? \n\n\nQ6: In your remarks under theorem 3.3, you say that you leave showing a $n^{2/(d+4)}$ to future work, but in 3.3 you give an upper \nbound, and $n^{2/(d+5)} < n^{2/(d+4)}$ for $n > 1$. So how is $n^{2/(d+4)}$ a better bound? \n\n\nQ7: I don't recognize the denpendence on $\\sigma_t$ which you mention in the remarks after theorem 3.3. Where do you have something \nbounded by $\\sigma_t^{-4/(d+5)}$? \n\n\nQ8: In line 491 you mention your \"truncation arguments\", could you say what you mean by this? And maybe give a reference to where \nyou make these arguments? \n\n\n**Suggestions:**\n\nU1: Please make sure to use the full name and not an abbriviation the first time you mention a concept.\n\tFor example: DDPM in line 66, ERM in line 74, DNN in line 90 and GD in line 97. \n\n\nU2: Please make sure to explain all the notation you use before you use it. If you feel it would take up too much space \nin the main paper, you can make a list of used notation in the appendix. \nSpecific notation, where I cannot find an explanation in the paper: \n$\\mathcal{F}_t$ in equation 3.7 (I am guessing this is the space of score functions), $\\asymp$ in line 165, \ng cts in line 176 in the definition of the Total-Variation norm, the $\\lor$ in line 231 and equation 3.10 and\nLaw(.) in last line of corollary 3.4. \n  \n\nU3: I feel the title over-promises. \"SHALLOW DIFFUSION NETWORKS PROVABLY LEARN HIDDEN LOW-DIMENSIONAL STRUCTURE\"\nsounds like it is _all_ shallow networks and _all_ hidden low-dimensional structures. Of course I understand \nif you feel the title would get too long if you add all the assumptions, so I would suggest finding a new title \nwhich is as short or shorter, and which does not make the result sound more general than it is. \n\n\nU4: Typo in line 189: Should be $B_2(r, d)$", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: Diffusion models are videly used, so theoretical work on them is highly relevant. \n\nS2: Going from needing a specific architecture to \"only\" needing the network to be infinitely wide to get a bound, is a step forward. \n\nS3: Corollary 3.4 and 3.8 give bounds on the KL-divergence between the true data distribution and that of the diffusion model, \ngiven enough training samples (and the extra assumptions) which is interesting.", "weaknesses": "W1: I found this paper difficult to follow. I count this as a weakness, since I am a machine learning researcher who is interested in \nthe theory of machine learning, so I should be the target audience. See my questions and suggestions for places where clarification is \nneeded.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)