Shallow diffusion networks provably learn hidden low-dimensional structure

## Abstract

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 layer neural networks.
In particular, we show that these shallow models provably adapt to simple forms of low dimensional structure, thereby avoiding the curse of dimensionality.
We combine our results with recent analyses of sampling with diffusion models 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.

## 1 Introduction

Generative models learn to sample from a target probability distribution given a dataset of examples.
Applications are pervasive, and include language modeling (Li et al., ), high-fidelity image generation (Rombach et al., ), de-novo drug design (Watson et al., ), and molecular dynamics (Arts et al., ).
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, ), such as diffusion-based generative models (Ho et al., ; Song et al., ), stochastic interpolants (Albergo et al., ), flow matching (Lipman et al., ), and rectified flow (Liu et al., ) approaches.
Yet, despite their strong empirical performance and well-grounded 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 et al., ; Lee et al., ).
While deeply insightful, these works leave open the difficulty of statistical estimation, and therefore raise the possibility that the sampling problem’s true difficulty is hidden in the complexity of learning.

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-layer neural networks (E et al., ; Bach, ).
This space contains important features of models used in practice – most importantly, parametric nonlinearity – while retaining well-studied theoretical properties that we can adapt to the generative modeling problem.
As a paradigmatic example of the widely-held belief that real-world datasets contain hidden low-dimensional structure (Tenenbaum et al., ; Weinberger and Saul, ), we focus on an idealized setting in which the target data density is concentrated on an unknown low-dimensional linear manifold.
We show that for learning to sample from a target distribution supported on a low-dimensional subspace,
diffusion models backed by single layer neural networks – which we refer to as *shallow diffusion networks* – enjoy a sample complexity bound that only depends exponentially on the dimension of the subspace rather than on the ambient dimension.
In addition, we extend our framework to the setting of target distributions constructed by composing independent components.
Our results highlight that diffusion models based on shallow neural 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 network architectures on real-world high-dimensional datasets.

## 2 Related Work

##### Sampling bounds for diffusion models.

Many recent analyses of diffusion models have focused on
the accuracy of sampling from a discretized process assuming
access to
an $L_{2}$ accurate score function.
In this direction, both discretized SDEs (Lee et al., ; Chen et al., ; Lee et al., ; Chen et al., ; Benton et al., ) and probability flow ODEs (Chen et al., , ; Li et al., ; Liang et al., ; Gao and Zhu, ) have been studied.
Recent work by Li and Yan () shows that the DDPM sampler (Ho et al., ) can be tuned so that in the presence of low-dimensional structure, the discretization error only depends polynomially on the intrinsic dimension (in addition to the score error).
However, because these works assume the existence of an $\varepsilon$-accurate score function in $L_{2}$, they leave open the question of the sample complexity of obtaining such a model, which is precisely what we tackle here.

##### Sample complexity of score matching.

Block et al. () and Koehler et al. () employ the standard Rademacher complexity framework to bound the error of empirical risk minimization for learning a score function with the implicit score matching objective, but leave open the question of which function class to learn over.
Han et al. () and Wang et al. () consider optimizing the denoising score matching loss over neural network models, and show that gradient descent on overparameterized models finds high-quality solutions.
Wibisono et al. (), Zhang et al. (), Oko et al. (), and Dou et al. () study the minimax optimality of diffusion models for distribution estimation under various functional assumptions on the target density and its score.
Taken together, these works show that diffusion modeling is both statistically nearly-optimal and computationally efficient for learning to sample.
Yet, simultaneously, they highlight the presence of the curse of dimensionality in the absence of structured data.

To address this issue,
both Oko et al. () and Chen et al. ()
study a setting in which the data lives on a low-dimensional subspace, and show that this latent structure avoids exponential dependencies on the ambient dimension.
However, both works require assumptions about the low-dimensional subspace (i.e., knowledge of the dimension) and/or constraints on the network architecture (i.e., bounded weight sparsity) which are usually not available in practice and/or computationally challenging to implement.
Our work can be seen as further bridging the gap between theory and practice in this setting by showing that the same dependence on the latent dimension also holds for shallow Barron networks which
are closer to the architectures used in practice; we defer a detailed comparison to Section 3.
Concurrent with our work, Azangulov et al. ()
show that the network architecture studied in
Oko et al. () can also be used to learn diffusion models
for data residing on general compact smooth manifolds.
Earlier work from Bortoli () also studies a similar setting as Azangulov et al. (),
and proves a bound that
depends exponentially on the diameter of the manifold.
Finally, Cole and Lu () show that under the assumption that the target log-relative density (w.r.t. a standard Gaussian) can be approximated by a NN with low path norm, score estimation can be performed with a sample complexity bound that does not depend explicitly on the ambient dimension.(^1^11However, there are still $O(1)^{D}$ pre-factors in the final rate.) 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 DNNs remains a largely open question, there is now strong consensus that the implicit bias of shallow networks with large width is accurately captured by the so-called Barron norm (E et al., ) or the (total variation) $\mathcal{F}_{1}$ norm (Bach, ).
These networks have also been analyzed using statistical physics-based techniques in the mean-field limit (Rotskoff and Vanden-Eijnden, ; Mei et al., ; Sirignano and Spiliopoulos, ).
Such networks can avoid the curse of dimensionality when the target function has *low-index* structure, i.e., when $f(x)=f(Px)$ for a low-dimensional projection $P$, leading to generalization bounds that depend on the intrinsic dimension $d$ of $Px$ rather than the ambient dimension $D$ of $x$ (Bach, ).
A number of 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., ; Bietti et al., ; Ben Arous et al., ; Glasgow, ; Lee et al., ). 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, in particular to learn energy-based models (Domingo-Enrich et al., ).

## 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 $p_{0}(x_{0})$ defined on $\mathbb{R}^{D}$ given a dataset of $n$ iid examples $x_{0}^{i}\sim p_{0}$ for $i=1,\ldots,n$.
In particular, we consider the use of a diffusion model (Sohl-Dickstein et al., ; Song et al., ; Ho et al., ) to learn a stochastic process that maps random noise to a new sample from the data distribution.
We assume that the target $p_{0}$ contains hidden latent structure – either a low-dimensional subspace or independent components – and our primary goal will be to show that a shallow 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 to the ambient dimension $D\gg d$.

##### Diffusion models.

We consider diffusion-based generative models based on stochastic differential equations (Song et al., ).
These models construct a path in the space of measures between the target $p_{0}$ and a standard Gaussian $\mathsf{N}(0,I_{D})$ by defining a simple forward process that converges to Gaussian data over an infinite horizon.
For simplicity, we study the simple Ornstein-Uhlenbeck (OU) process,

$$ $\displaystyle\mathrm{d}x_{t}=-x_{t}\mathrm{d}t+\sqrt{2}\mathrm{d}B_{t},\quad t \in[0,T],$ (3.1) $$

though our results straightforwardly generalize to the time-scaled OU processes commonly used in practice (Song et al., ).
In (3.1), $(B_{t})_{t\geqslant 0}$ denotes a standard Brownian motion on $\mathbb{R}^{D}$.
Due to the linear nature of the OU process, for $w\sim\mathsf{N}(0,I_{D})$ drawn independently of $x_{0}$, $x_{t}$ is equivalent in distribution to the stochastic interpolant (Albergo et al., )

$$ $\displaystyle x_{t}\overset{\mathsf{d}}{=}m_{t}x_{0}+\sigma_{t}w,\quad m_{t}:= \exp(-t),\quad\sigma_{t}:=\sqrt{1-\exp(-2t)}.$ (3.2) $$

Let the marginal distributions of $x_{t}$ be denoted as $(p_{t})_{t\in[0,T]}$.
The *reverse process* is the process of $y_{t}:=x_{T-t}$ for $t\in[0,T]$.
A classic result (Anderson, ) shows that the reverse process satisfies

$$ $\displaystyle\mathrm{d}y_{t}=(y_{t}+2\nabla\log p_{T-t}(y_{t}))\mathrm{d}t+ \sqrt{2}\mathrm{d}B_{t},\quad y_{0}\sim p_{T}(\cdot),\quad t\in[0,T].$ (3.3) $$

Thus, assuming knowledge of the time-dependent score function $\nabla\log p_{t}$, sampling from $p_{0}(\cdot)$ can be accomplished by (a) setting $T$ large enough so that
$p_{T}(\cdot)$ is approximately an isotropic Gaussian, (b) sampling $y_{0}\sim\mathsf{N}(0,I_{D})$,
and (c) running 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 $\hat{s}\approx\nabla\log p$, we now consider
discretizing (3.3).
In this work we make use of the *exponential integrator* (EI),
which fixes a sequence (to be specified) of reverse process timesteps
$0=\tau_{0}<\tau_{1}<\dots<\tau_{N}=T$
and implements

$$ $\displaystyle\mathrm{d}\tilde{y}_{t}=(\tilde{y}_{t}+2\nabla\log\hat{s}_{T-\tau _{k}}(\tilde{y}_{\tau_{k}}))\mathrm{d}t+\sqrt{2}\mathrm{d}B_{t},\quad t\in[ \tau_{k},\tau_{k+1}],\quad k\in\{0,\dots,N-1\}.$ (3.4) $$

Recently, building off of the works by Chen et al. () and Lee et al. (), Benton et al. () showed that it suffices to control the score approximation error in $L_{2}(p_{t})$ to guarantee that
the process (3.4) yields a high quality sample from $p_{0}$.(^2^22Technically, Benton et al. () guarantees a high quality sample from $p_{T-\tau_{N-1}}(\cdot)$ instead of $p_{0}(\cdot)$.)

##### Score function estimation.

To estimate the score function $\nabla\log p_{t}$ over the interval $[0,T]$, one would ideally minimize the least-squares objective over a model $\hat{s}$,

$$ $\displaystyle\mathcal{R}(\hat{s}):=\int_{0}^{T}\mathcal{R}_{t}(\hat{s}_{t})\, \mathrm{d}t,\qquad\mathcal{R}_{t}(\hat{s}_{t}):=\mathbb{E}_{x_{t}}\lVert\hat{s }_{t}(x_{t})-\nabla\log p_{t}(x_{t})\rVert^{2}.$ (3.5) $$

While direct minimization is not possible because $\nabla\log p_{t}$ is not observed, minimizing $\mathcal{R}(s)$ is equivalent (up to a constant) to minimizing the following
denoising score matching (DSM) loss (Vincent, )

$$ $\displaystyle\mathcal{L}(\hat{s}):=\int_{0}^{T}\mathcal{L}_{t}(\hat{s}_{t})\, \mathrm{d}t,\qquad\mathcal{L}_{t}(\hat{s}_{t}):=\mathbb{E}_{(w,x_{t})}\lVert \hat{s}_{t}(x_{t})+w/\sigma_{t}\rVert^{2},$ (3.6) $$

as can be shown by observing that Tweedie’s identity (Efron, ) implies

$$ $\nabla\log p_{t}(x)=-\frac{1}{\sigma_{t}}\mathbb{E}[w\mid x_{t}=x].$ (3.7) $$

In practice, (3.6) is typically approximated via Monte-Carlo by generating samples $x_{t^{i}}^{i}=m_{t^{i}}x_{0}^{i}+\sigma_{t^{i}}w^{i}$ using the dataset of samples from $p_{0}$, iid random draws of Gaussian noise $w^{i}$, and random time points $t^{i}$ drawn from $[0,T]$.
This empirical risk can then be minimized to estimate a time-dependent score function $\hat{s}:[0,T]\times\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$.

In this work, to simplify the mathematical analysis, we consider a stylized variant in which we fix
a sequence of timesteps
$0<t_{0}<\dots<t_{N-1}=T$
and estimate $N$ time-independent score functions $\{\hat{s}_{t_{i}}\}_{i=0}^{N-1}$ of the form $\hat{s}_{t_{i}}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$.

$$ $\displaystyle\hat{s}_{t}\in\operatorname*{arg\,min}_{s_{t}\in\mathscr{F}_{t}} \hat{\mathcal{L}}_{t}(s_{t}),\quad\hat{\mathcal{L}}_{t}(s_{t}):=\frac{1}{n} \sum_{i=1}^{n}\lVert s_{t}(x_{t}^{i})+w^{i}/\sigma_{t^{i}}\rVert^{2},\quad t \in\{t_{i}\}_{i=0}^{N-1}.$ (3.8) $$

In the sequel, we will let $\mathcal{D}_{t}:=\{(x_{0}^{i},x_{t}^{i})\}_{i=1}^{n}$ denote the training data used in (3.8)
for timestep $t$.

From Wibisono et al. (),
we know that if the true score $\nabla\log p_{t}$ is Lipschitz continuous and $p_{t}$ is sub-Gaussian,
then the minimax rate for estimating $\nabla\log p_{t}$ is
given by $n^{-2/(D+4)}$.(^3^33Interestingly, this rate is slower than the $n^{-2/(D+2)}$ rate for learning Lipschitz functions (Tsybakov, ).)
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 ℱ 1 subscript ℱ 1 \mathcal{F}_{1} caligraphic_F start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT .

Consider a shallow neural network $f_{m}$ with $m$ neurons and mean-field scaling, $f_{m}(x)=\frac{1}{m}\sum_{i=1}^{m}u_{i}\sigma(\langle x,v_{i}\rangle)$.
In the limit as $m$ tends to infinity, the summation may be replaced by integration $f_{\infty}(x)=\int u\sigma(\langle x,v\rangle)\,\mathrm{d}\mu(u,v)$ against a signed Radon measure $\mu$ over the neuron parameters $(u,v)$.
This leads to the Barron space $\mathcal{F}_{1}$ (Bach, ; Mhaskar, ; Rotskoff and Vanden-Eijnden, ; Mei et al., ; Sirignano and Spiliopoulos, ), which models shallow neural networks in the infinite width limit and in the feature learning regime (Chizat et al., ).

Concretely, given a Radon measure $\mu$ on a measurable space $\mathcal{V}$, recall that the *total variation norm* (TV) is defined as $\lVert\mu\rVert_{\mathrm{tv}}:=\sup_{g:\mathcal{V}\mapsto[-1,1],\,\textrm{$g$
cts}}\int_{\mathcal{V}}g(v)\,\mathrm{d}\mu(v)$.
Given a basis function $\varphi_{v}(x)$, the TV-norm induces the space of functions $\mathcal{F}_{1}:=\{f(x)=\int_{\mathcal{V}}\varphi_{v}(x)\,\mathrm{d}\mu(v)\mid
\lVert\mu\rVert_{\mathrm{tv}}<\infty\}$.
For a function $f\in\mathcal{F}_{1}$, its $\mathcal{F}_{1}$-norm is the infimum over all TV-norms of measures that can represent $f$, i.e., $\lVert f\rVert_{\mathcal{F}_{1}}:=\inf\{\lVert\mu\rVert_{\mathrm{tv}}\mid f(x)
=\int_{\mathcal{V}}\varphi_{v}(x)\,\mathrm{d}\mu(v)\}$.

In this work, we will consider the special case $\mathcal{V}=\mathbb{S}^{p-1}\times\mathbb{S}^{p-1}$ for $p\in\mathbb{N}_{+}$ and $\varphi_{v}(x)=u\sigma(\langle x,v\rangle)$, where $(u,v)\in\mathcal{V}$ and $\sigma(\cdot)=\max\{0,\cdot\}$ is the ReLU activation.
Hence, the induced class $\mathcal{F}_{1}$ consists of vector-valued maps from $\mathbb{R}^{p}\to\mathbb{R}^{p}$,
which satisfy $\lVert f(x)\rVert\leqslant\lVert f\rVert_{\mathcal{F}_{1}}\lVert x\rVert$.
In learning the score functions $\hat{s}_{t_{i}}$
via DSM (3.8), we will utilize norm-ball subsets of $\mathcal{F}_{1}$ to model the true score functions $\nabla\log p_{t_{i}}(x)$.
This allows us to leverage the low-index structure of $\mathcal{F}_{1}$ (Bach, ) and obtain bounds for score estimation that scale with the *intrisic*, rather than ambient, dimension of the problem.

##### Notation:

We briefly review the (relatively standard) notation used in this work.
For a $d$-dimensional vector $x$, the $\ell_{p}$ norm is denoted $\lVert x\rVert_{p}$; the notation $\lVert x\rVert$ is reserved for the Euclidean ($p=2$) case.
The (closed) $\ell_{2}$-ball of radius $r$ in $d$-dimension is denoted by $B_{2}(r,d)$; when $r=1$, we use the shorthand $B_{2}(d)$.
The unit sphere in $\mathbb{R}^{d}$ is denoted $\mathbb{S}^{d-1}$.
The notation $O_{d}(\cdot)$ hides both universal constants and constants that depend arbitrarily on the variable $d$.
Similarly, $\tilde{O}_{d}(\cdot)$
hides universal constants, constants that depend on $d$, and terms that may depend poly-logarithmically on $d$, i.e., terms of the form $\log^{O(d)}(\cdot)$.
The notation $\mathrm{poly}(\cdot)$ indicates a polynomial dependence on the arguments, whereas $\mathrm{poly}_{d}(\cdot)$ indicates that the polynomial degrees are allowed to depend arbitrarily on $d$.
Finally, the notation $a\lesssim b$ (resp. $a\gtrsim b$) indicates that there exists a universal positive constant $c$ such that $a\leqslant cb$ (resp. $a\geqslant cb$).

### 3.1 Learning latent subspace structure

We first consider a setting in which $x_{0}$ is supported on a $d$-dimensional ($d\ll D$) linear subspace.
Specifically, we study

$$ $\displaystyle x_{0}=Uz_{0},\quad z_{0}\sim\pi_{0}(\cdot),\quad U\in O(D,d),$ (3.9) $$

where $z_{0}$ is a $d$-dimensional random vector
and $O(D,d):=\{U\in\mathbb{R}^{D\times d}\mid U^{\mathsf{T}}U=I_{d}\}$ denotes the $d$-dimensional orthogonal group in $\mathbb{R}^{D}$.
Note that both the subspace dimension $d$ and the embedding matrix $U$ are unknown to the learner.

Recently, both Chen et al. () and Oko et al. ()
consider learning diffusion models under the subspace structure
(3.9).
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 $p_{0}$ if the network used for learning satisfies various architectural assumptions.
While insightful, these architectural assumption are difficult to satisfy in practice.
Chen et al. ()
utilize a function class that is specifically tailored to the linear structure (3.9), 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. (), 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 $\mathcal{F}_{1}$, the space of infinite-width shallow networks, the latent subspace is adaptively learned without requiring prior latent dimension knowledge or difficult to impose sparsity constraints.
We note that from a computational perspective, sufficiently wide shallow networks trained with gradient descent (GD) and weight decay will converge to the minimal $\mathcal{F}_{1}$-norm solution (Chizat and Bach, ).
While control on the number of neurons required in the worst case is not
available (optimizing over $\mathcal{F}_{1}$ is unfortunately NP-hard (Bach, )),
recent results have shown that
under various assumptions on 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., ; Dandi et al., ; Lee et al., ).

Towards stating our first result, we begin with a few standard regularity assumptions.

###### Assumption 3.1 .

The latent variable $z_{0}\sim\pi_{0}(\cdot)$ is $\beta$-sub-Gaussian(^4^44This definition is also referred to as *norm-*sub-Gaussian in the literature (see e.g. Jin et al., ).) (with $\beta\geqslant 1$),
i.e.,

$$ $\mathbb{E}\exp(\lambda(\lVert z_{0}\rVert-\mathbb{E}\lVert z_{0}\rVert)) \leqslant\exp(\lambda^{2}\beta^{2}/2),\quad\forall\lambda\in\mathbb{R}.$ $$

Our next assumption concerns the regularity of the
score function of the latent distribution $\pi_{t}$, which denotes the marginal distribution of $z_{t}:=U^{\mathsf{T}}x_{t}$.

###### Assumption 3.2 .

The latent score $\nabla\log\pi_{t}$ is $L$-Lipschitz (with $L\geqslant 1$) on $\mathbb{R}^{d}$ for all $t\geqslant 0$.

We emphasize that 3.2 concerns the Lipschitz regularity of the latent measure $\pi_{t}$ and *not* the ambient measure $p_{t}$; due to the subspace structure (3.9), the Lipschitz constant of the ambient score diverges as $t\to 0$.
Finally, we define some shorthand notation for $t\in[0,T]$,

$$ $\displaystyle\mu_{t,x}:=\mu_{0}\vee\sigma_{t}\sqrt{D},\quad\mu_{t,z}:=\mu_{0} \vee\sigma_{t}\sqrt{d},\quad\bar{L}:=cL(\mu_{0}+\sqrt{d}+\lVert\nabla\log\pi_{ 0}(0)\rVert),$ $$

where $\mu_{0}:=(\mathbb{E}\lVert z_{0}\rVert^{2})^{1/2}$ and $c\geqslant 1$ is a universal constant.
Since $\sigma_{t}\to 1$ as $t\to\infty$,
these constants are uniformly bounded above.
Hence, we define
$\mu_{x}:=\lim_{t\rightarrow\infty}\mu_{t,x}$ and
$\mu_{z}:=\lim_{t\rightarrow\infty}\mu_{t,z}$.

###### Theorem 3.3 .

Suppose that $p_{0}$ follows the latent structure
(3.9), and that both 3.1 and 3.2 hold.
Fix a $t>0$ and define

$$ $\displaystyle\mathscr{F}_{t}:=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid \lVert s\rVert_{\mathcal{F}_{1}}\leqslant R_{t}\},\quad R_{t}:=\bar{R}_{t}n^{ \frac{d+1}{2(d+5)}}+\frac{D}{\sigma_{t}^{2}},$ (3.10) $$

where $\bar{R}_{t}$ does not depend on $n$.(^5^55The explicit dependence of $\bar{R}_{t}$ on the other problem parameters is detailed in the proof.)
Suppose that $n$ satisfies

$$ $\displaystyle n\geqslant n_{0}(t):=\mathrm{poly}(D,1/\sigma_{t},\mu_{t,x}\vee \beta)\cdot\mathrm{poly}_{d}(\bar{L},\mu_{t,z}\vee\beta).$ (3.11) $$

Then, the empirical risk minimizer $\hat{s}_{t}\in\operatorname*{arg\,min}_{s\in\mathscr{F}_{t}}\hat{\mathcal{L}}_
{t}(s)$ satisfies:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{s}_{t})] \leqslant\tilde{O}_{d}(1)\left[\frac{D^{2}}{\sigma_{t}^{2}n}(\bar{L}(\mu_{t,z} \vee\beta))^{d+3}(\mu_{t,x}\vee\beta)^{2}\right]^{\frac{2}{d+5}}+\tilde{O}_{d} (1)\sqrt{\frac{D^{3}}{\sigma_{t}^{6}n}(\mu_{t,x}\vee\beta)^{2}}.$ (3.12) $$

Some remarks regarding 3.3
are in order.
First, we can upgrade 3.3 to a high-probability bound with minor modifications to the proof; we omit these
details in the interest of brevity.
Second, we note that our $n^{2/(d+5)}$ rate nearly matches the minimax optimal rate of score matching from Wibisono et al. (), but with the subspace dimension $d$ replacing the ambient dimension $D$; we leave showing a $n^{2/(d+4)}$ rate to future work.
Last, as noted before, Chen et al. (, Theorem 2) proves a related result for learning score functions
under the subspace structure (3.9).
However, our result in 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 $\mathcal{F}_{1}$ of shallow neural networks.
Additionally, our result also provides several technical improvements:
(a) our leading dependence on $n$ is improved to $n^{2/(d+5)}$ from
$n^{(2-o(1))/(d+5)}$,(^6^66However, their logarithmic dependence on $n$ is only through $\log^{O(1)}(n)$ terms instead of our $\log^{O(d)}(n)$.)
and (b) our dependence on $\sigma_{t}$ is improved to
$\sigma_{t}^{-4/(d+5)}$ instead of $\sigma_{t}^{-2}$; as $t\to 0$ the former degrades slower than the latter.

We now use 3.3
to provide an end-to-end sample complexity bound for sampling from $p_{0}$.

###### Corollary 3.4 .

Fix $\varepsilon,\zeta\in(0,1)$.
Suppose that $p_{0}$ follows the latent structure
(3.9), and that both 3.1 and 3.2 hold.
Consider the exponential integrator (3.4) with:

$$ $\displaystyle T=c_{0}\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right), \quad N=2\left\lceil c_{1}\frac{D\vee\mu_{0}^{2}}{\varepsilon^{2}}\left[\log^{ 2}\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)+\log^{2}\left(\frac{1}{ \zeta}\right)\right]\right\rceil,$ (3.13) $$

and reverse process discretization timesteps $\{\tau_{i}\}_{i=0}^{N}$ defined as:

$$ $\displaystyle\tau_{i}=\begin{cases}2(T-1)\frac{i}{N}&\text{if }i\in\{0,\dots,N /2\},\\ T-\zeta^{2i/N-1}&\text{if }i\in\{N/2+1,\dots,N\}.\end{cases}$ (3.14) $$

Next, define the forward process
timesteps $\{t_{i}\}_{i=0}^{N-1}$ by $t_{i}:=T-\tau_{N-i}$.
Suppose the exponential integration scheme is run with score functions $\{\hat{s}_{t_{i}}\}_{i=0}^{N-1}$,
where $\hat{s}_{t_{i}}\in\operatorname*{arg\,min}_{s\in\mathscr{F}_{t_{i}}}\hat{
\mathcal{L}}_{t_{i}}(s)$ with
$\mathscr{F}_{t}$ as defined in (3.10).
Suppose furthermore that $n$ satisfies:

$$ $\displaystyle n\geqslant\tilde{O}_{d}(1)\max\left\{\frac{D^{2}}{\zeta}(\bar{L} (\mu_{z}\vee\beta))^{d+3}(\mu_{x}\vee\beta)^{2}\cdot\varepsilon^{-(d+5)},\frac {D^{3}}{\zeta^{3}}(\mu_{x}\vee\beta)^{2}\cdot\varepsilon^{-4},n_{0}(\zeta) \right\},$ $$

where $n_{0}(\cdot)$ is defined in (3.11).
With constant probability (over the randomness of the training datasets $\{\mathcal{D}_{t_{i}}\}_{i=0}^{N-1}$), we have that
$\mathrm{KL}(p_{\zeta}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta}))\leqslant
\varepsilon^{2}$.

Treating $\bar{L}$ and $\beta$ as constants,
3.4 prescribes a rate of $n\geqslant\tilde{O}_{d}(1)\frac{\mathrm{poly}(D)}{\zeta}\varepsilon^{-(d+5)}$ (after a burn-in on $n$) to obtain a sampler that satisfies $\mathrm{KL}(p_{\zeta}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta}))\leqslant
\varepsilon^{2}$.
To the best of our knowledge, this is the first end-to-end sample complexity bound for learning a diffusion model over shallow neural networks that adapts to the intrinsic dimensionality of the problem.
Note that as 3.4 controls the
KL-divergence between the true data distribution $p_{\zeta}$
and the distribution $\mathrm{Law}(\hat{y}_{T-\zeta})$
of the final iterate of the exponential integrator (3.4),
by Pinsker’s inequality this also implies control on the TV-distance
$\lVert p_{\zeta}-\mathrm{Law}(\hat{y}_{T-\zeta})\rVert_{\mathrm{tv}}$.
Furthermore, we can upgrade 3.4
to a high probability guarantee by utilizing a high probability variant of 3.3.

The parameter $\zeta>0$ is the early stopping parameter which is found
in practical implementations of diffusion models (cf. Karras et al. ()).
Note that this is necessary since $p_{0}$ is supported on a lower-dimensional manifold and hence
$\nabla\log p_{0}$ is not smooth on all of $\mathbb{R}^{D}$.
We remark that bounds comparing the original $p_{0}$ to $\mathrm{Law}(\hat{y}_{T-\zeta})$ are possible in Wasserstein distance
by adopting the techniques from e.g. Chen et al. (, Section 3.2); we omit these calculations.

Compared to Chen et al. (, Theorem 3), who obtain a
$n\geqslant\tilde{O}_{d}(1)(\varepsilon\sqrt{\zeta})^{-(d+5)/(1-o(1))}$ rate
in the case of a latent subspace-aware architecture, we see that our bound also improves the dependency on $\zeta$.
This is important, because ultimately $\zeta$ will be chosen to decay to zero as $n\to\infty$.
We do remark, however, that Chen et al. (, Theorem 3) only
depends polylogarithmically on the ambient dimension $D$ instead of polynomially. This can be traced back in their analysis to imposing the constraint that their score functions are uniformly bounded,
i.e., $\sup_{z,t}\lVert s(z,t)\rVert\leqslant K$, which allows truncation arguments to avoid picking up extra $\mathrm{poly}(D)$ factors.
We choose to not impose such constraints in our model class, as this adds another hyperparameter that must be tuned in practice.
We leave open the question of whether or not these $\mathrm{poly}(D)$ pre-factors in the sample complexity can be removed without further modifications (e.g., clipping) of the $\mathcal{F}_{1}$ hypothesis class.

Compared to Oko et al. (, Theorem 6.4),
3.4 also relaxes a few technical assumptions,
including a uniformly lower bounded density $\pi_{0}$, and a requirement that $\pi_{0}$ be $C^{\infty}$ near the boundary $[-1,1]^{d}$.
On the other hand, their work obtains
a sharper rate on $W_{1}(p_{0},\mathrm{Law}(\hat{y}_{T-\zeta}))\lesssim n^{-(3-\delta)/(d+4)}$ for any $\delta>0$.
We also leave open the question of whether these extra assumptions can be used to strengthen our guarantees for learning over $\mathcal{F}_{1}$.

###### Assumption 3.1 .

###### Assumption 3.2 .

###### Theorem 3.3 .

###### Corollary 3.4 .

### 3.2 Extensions to independent component structure

We now consider a different type of latent structure – here generated by independence – as opposed to the low-dimensional subspace setting just studied.
Specifically, we suppose that for some $K\in[D]$,

$$ $\displaystyle x_{0}=Uz_{0},\quad z_{0}\sim(z_{0}^{(1)},\dots,z_{0}^{(K)}), \quad z_{0}^{(i)}\sim\pi_{0}^{(i)}(\cdot),$ (3.15) $$

where $U\in O(D):=\{U\in\mathbb{R}^{D\times D}\mid U^{\mathsf{T}}U=I_{D}\}$,
$z_{0}^{(i)}\in\mathbb{R}^{d_{i}}$ with $\sum_{i=1}^{K}d_{i}=D$,
and where $z_{0}^{(i)}$ is independent of $z_{0}^{(j)}$ for $i\neq j$.
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_{i}\}_{i=1}^{K}$ are all unknown to the learner, and we study the adaptive properties of $\mathcal{F}_{1}$ 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\in[K]$, we have that $\pi_{0}^{(i)}$ is $\beta_{i}$-sub-Gaussian (for $\beta_{i}\geqslant 1$), i.e.,

$$ $\mathbb{E}\exp(\lambda(\lVert z_{0}^{(i)}\rVert-\mathbb{E}\lVert z_{0}^{(i)} \rVert))\leqslant\exp(\lambda^{2}\beta_{i}^{2}/2),\quad\lambda\in\mathbb{R}.$ $$

Our next assumption again deals with the latent measure $\pi_{t}$, defined as the marginal distribution of $z_{t}:=U^{\mathsf{T}}x_{t}$.
We decompose $z_{t}=(z_{t}^{(1)},\dots,z_{t}^{(K)})$ into coordinate groups as for $z_{0}$, and we define $\pi_{t}^{(i)}$ as the marginal distribution of $z_{t}^{(i)}$.

###### Assumption 3.6 .

For all $i\in[K]$,
$\nabla\log\pi_{t}^{(i)}$ is $L_{i}$-Lipschitz (for $L_{i}\geqslant 1$) on $\mathbb{R}^{d_{i}}$ for all $t\geqslant 0$.

As before, we define some shorthand notation for $t\in[0,T]$ and $i\in[K]$:

$$ $\displaystyle\mu_{t,x}^{(i)}:=\mu_{0}^{(i)}\vee\sigma_{t}\sqrt{d_{i}},\quad \bar{L}_{i}:=cL_{i}(\mu_{0}^{(i)}+\sqrt{d_{i}}+\lVert\nabla\log\pi_{0}^{(i)}(0 )\rVert),$ $$

where $\mu_{0}^{(i)}:=(\mathbb{E}\lVert z_{0}^{(i)}\rVert^{2})^{1/2}$ and $c\geqslant 1$ is a universal constant.
Furthermore, we combine the individual constants together as
$\mu_{0}:=\sqrt{\sum_{i=1}^{K}(\mu_{0}^{(i)})^{2}}$,
$\beta:=\sqrt{\sum_{i=1}^{K}\beta_{i}^{2}}$, and
$\mu_{t,x}:=\mu_{0}\vee\sigma_{t}\sqrt{D}$.
Finally, as before, we let $\mu_{x}^{(i)}:=\lim_{t\to\infty}\mu_{t,x}^{(i)}$
and $\mu_{x}:=\lim_{t\to\infty}\mu_{t,x}$.
Our first result mirrors that of 3.3, and
provides an error bound on the learned score functions
under the latent independent structure (3.15).

###### Theorem 3.7 .

Suppose that $p_{0}$ follows the latent structure
(3.15), and that both 3.5 and 3.6 hold.
Fix a $t>0$ and define

$$ $\displaystyle\mathscr{F}_{t}:=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid \lVert s\rVert_{\mathcal{F}_{1}}\leqslant R_{t}\},\quad R_{t}:=\sum_{i=1}^{K} \bar{R}_{t}^{(i)}n^{\frac{d_{i}+1}{2(d_{i}+5)}},$ (3.16) $$

where $\bar{R}_{t}^{(i)}$ does not depend on $n$.
Suppose that $n$ satisfies

$$ $\displaystyle n\geqslant n_{0}(t):=\mathrm{poly}(D,1/\sigma_{t},\mu_{t,x}\vee \beta)\cdot\max_{i\in[K]}\mathrm{poly}_{d_{i}}(\bar{L}_{i},\mu_{t,x}^{(i)}\vee \beta^{(i)}).$ (3.17) $$

Then, the empirical risk minimizer $\hat{s}_{t}\in\operatorname*{arg\,min}_{s\in\mathscr{F}_{t}}\hat{\mathcal{L}}_
{t}(s)$ satisfies:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{s}_{t})] \leqslant\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)\left[\frac{D^{2}K}{\sigma_{t}^{2}n }(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3}(\mu_{t,x}\vee\beta)^{2} \right]^{\frac{2}{d_{i}+5}}+\tilde{O}(1)\sqrt{\frac{D^{2}}{\sigma_{t}^{4}n}( \mu_{t,x}\vee\beta)^{2}}.$ (3.18) $$

Ignoring all parameters other than $K$ and $n$, we have that the risk scales as $\sum_{i=1}^{K}(K/n)^{2/(d_{i}+5)}$,
which again captures the intrinsic dimensionality of the problem.
To the best of our knowledge, this is the first result establishing
a score function error bound in the setting (3.15)
which depends primarily on the latent $d_{i}$’s.
Our final result mirrors that of 3.4 and establishes an end-to-end sampling guarantee for this setting.

###### Corollary 3.8 .

Fix $\varepsilon,\zeta\in(0,1)$.
Suppose that $p_{0}$ follows the latent structure
(3.15), and that both 3.5 and 3.6 hold.
Consider the exponential integrator (3.4) with
$(N,T)$ as in (3.13) and reverse process discretization timesteps $\{\tau_{i}\}_{i=0}^{N}$ defined as in (3.14).
Next, define the forward process
timesteps $\{t_{i}\}_{i=0}^{N-1}$ by $t_{i}:=T-\tau_{N-i}$.
Suppose the exponential integration scheme is run with score functions $\{\hat{s}_{t_{i}}\}_{i=0}^{N-1}$,
where $\hat{s}_{t_{i}}\in\operatorname*{arg\,min}_{s\in\mathscr{F}_{t_{i}}}\hat{
\mathcal{L}}_{t_{i}}(s)$ with
$\mathscr{F}_{t}$ as defined in (3.16).
Suppose that $n\geqslant n_{0}(\zeta)$ satisfies:

$$ $\displaystyle n\geqslant(\mu_{x}\vee\beta)^{2}\max\left\{\max_{i\in[K]}\left\{ \frac{\tilde{O}_{d_{i}}(1)D^{2}}{\zeta}K^{(d_{i}+7)/2}(\bar{L}_{i}(\mu_{x}^{(i )}\vee\beta))^{d_{i}+3}\cdot\varepsilon^{-(d_{i}+5)}\right\},\frac{\tilde{O}(1 )D^{2}}{\zeta^{2}}\cdot\varepsilon^{-4}\right\}.$ $$

where $n_{0}(\cdot)$ is defined in (3.17).
With constant probability (over the randomness of the training datasets $\{\mathcal{D}_{t_{i}}\}_{i=0}^{N-1}$), we have that
$\mathrm{KL}(p_{\zeta}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta}))\leqslant
\varepsilon^{2}$.

We note that, unlike the latent subspace setting of Section 3.1,
given 3.6 it is possible to prove a bound on $\mathrm{KL}(p_{0}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta}))$ directly, since $\nabla\log p_{t}$ is uniformly Lipschitz for all $t\geqslant 0$. This can be done by using
Chen et al. (, Theorem 2) to analyze the backwards exponential integrator process (3.4) instead of
the results of Benton et al. (). We elect to utilize the latter’s analysis in the interest of consistency with Section 3.1 where it is required.

###### Assumption 3.5 .

###### Assumption 3.6 .

###### Theorem 3.7 .

###### Corollary 3.8 .

#### 3.2.1 Non-orthogonal independent components

Section 3.2 shows that a diffusion model based on a shallow neural 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., ).
Here, we explain why a direct extension of our argument works at $t=0$ case, but breaks whenever $t>0$ since the addition of noise breaks the independence structure.
We then use data whitening to address the issue.

Recall from (3.15) that $z_{0}=(z_{0}^{(1)},\dots,z_{0}^{(K)})$ where $x^{(i)}\in\mathbb{R}^{d_{i}}$
for $d_{1}+\dots+d_{K}=D$, and where each of the $K$ components are
sampled independently.
Now, let us assume that $x_{0}=Az_{0}$, where $A\in\mathbb{R}^{D\times D}$ is invertible, but not necessarily orthonormal.
Note that for $t=0$, the score function $\nabla\log p_{0}$ can be expressed as
$\nabla\log p_{0}(x)=\sum_{i=1}^{K}A^{-\mathsf{T}}P_{i}^{\mathsf{T}}\nabla\log
\pi_{0}^{(i)}(P_{i}A^{-1}x)$,
where $P_{i}\in\mathbb{R}^{d_{i}\times D}$ selects the $d_{i}$ coordinates that correspond to the $i$-th variable group.
Hence, the score function has the structure of a sum of low-index functions, and the $\mathcal{F}_{1}$ norm of the score can be bounded in terms of the sum of $\mathcal{F}_{1}$ 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.
That is, $z_{t}=A^{-1}(m_{t}x_{0}+\sigma_{t}w)=m_{t}z_{0}+\sigma_{t}A^{-1}w$.
In this case, the sum of low-index
functions structure is not preserved.

A possible fix for this issue is to first whiten the data, and then to apply the results of Section 3.2 to the whitened data.
Specifically, write $\mathrm{Cov}(x_{0})=A\Sigma A^{\mathsf{T}}$, where $\Sigma$ is a block diagonal matrix with $K$ blocks $\Sigma^{(1)},\dots,\Sigma^{(K)}$.
Now consider the transform $\bar{x}_{0}:=\Sigma^{-\frac{1}{2}}A^{-1}x_{0}$, which
orthogonalizes the components and whitens
each of them independently. Indeed, $\bar{x}_{0}$ follows the latent structure (3.15), and hence the results from Section 3.2 directly apply to $\bar{x}_{0}$.
However, one caveat with this approach is that the whitening factor $\Sigma^{-1/2}A^{-1}$ must be learned from the data samples $x_{0}^{i}\sim p_{0}(\cdot)$.
Standard results in covariance estimation (see e.g., Wainwright, , Chapter 6) allow us to learn $\Sigma^{-1/2}A^{-1}$ (modulo rotation) up to $n^{-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 a final sample complexity bound.

## 4 Proof Ideas

Here, we outline the key proof ideas behind the results in
Section 3.1 and
Section 3.2.
We focus our discussion exclusively on bounding the
error of the score function estimate, as translating score error
into sample quality bounds is already well-established in the literature (cf. Section 2).
For this discussion, we fix a specific value of $t>0$, noting from our discussion in Section 3 (specifically Equation 3.8) that we learn separate score models for a fixed sequence of
forward process timesteps $\{t_{i}\}_{i=0}^{N-1}$.

### 4.1 Basic inequality

Recall that $s_{t}\in\operatorname*{arg\,min}_{s\in\mathscr{F}_{t}}\hat{\mathcal{L}}_{t}(s)$
is the empirical risk minimizer (ERM) of the empirical denoising loss
$\hat{\mathcal{L}}_{t}$ over the function class $\mathscr{F}_{t}=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid\lVert s\rVert_{
\mathcal{F}_{1}}\leqslant R_{t}\}$, where the norm bound $R_{t}$ will be determined.
Our first step uses the link between the
$L_{2}(p_{t})$ score error $\mathcal{R}_{t}(s)$ and the DSM loss $\mathcal{L}_{t}(s)$
in addition to standard arguments from the analysis of ERM to show
the following basic inequality
for all $\varepsilon\geqslant 0$:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{s}_{t})] \leqslant(1+\varepsilon)\inf_{s\in\mathscr{F}_{t}}\mathcal{R}_{t}(s)+\mathbb{E }_{\mathcal{D}_{t}}\sup_{s\in\mathscr{F}_{t}}[\mathcal{L}_{t}(s)-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(s)]+\varepsilon\cdot C_{t},$ (4.1) $$

where $C_{t}:=\mathbb{E}\operatorname*{\mathrm{tr}}\mathrm{Cov}(\sigma_{t}^{-2}(m_{t}
x_{0}-x_{t})\mid x_{t})$.
The basic inequality (4.1)
contains three key terms:
an *approximation-theoretic* term $T_{1}:=(1+\varepsilon)\inf_{s\in\mathscr{F}_{t}}\mathcal{R}_{t}(s)$ which measures how well the $\mathcal{F}_{1}$-norm bounded subset $\mathscr{F}_{t}$ approximates the true score,
a *uniform convergence* term $T_{2}:=\mathbb{E}_{\mathcal{D}_{t}}\sup_{s\in\mathscr{F}_{t}}[\mathcal{L}_{t}(
s)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(s)]$
over the function class $\mathscr{F}_{t}$, and
a third *offset* term $T_{3}:=\varepsilon\cdot C_{t}$ which
trades off a fast rate for $T_{2}$ (controlled via $\varepsilon$) with
the constant offset $C_{t}$ 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.

### 4.2 Approximation of structured models with ℱ 1 subscript ℱ 1 \mathcal{F}_{1} caligraphic_F start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT

Our analysis is based on careful control of the approximation error term $T_{1}$ in (4.1) of the structured models we consider in a way such that the requisite $\mathcal{F}_{1}$-norm $R_{t}$ does not depend exponentially on the ambient dimension $D$.
This is accomplished by first understanding the low-dimensional structure present in the score functions $\nabla\log p_{t}$, and then arguing that this low-dimensional structure
can be approximated with a norm bound $R_{t}$ 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 $\nabla\log p_{t}$ to the score $\nabla\log\pi_{t}$ of the latent $z_{t}$.

###### Proposition 4.1 (see e.g., Chen et al. ( 2023e , Lemma 1) ) .

The following decomposition holds under the subspace model (3.9):

$$ $\displaystyle\nabla\log p_{t}(x)=U\nabla\log\pi_{t}(U^{\mathsf{T}}x)-\frac{1}{ \sigma_{t}^{2}}(I-UU^{\mathsf{T}})x.$ (4.2) $$

###### Proposition 4.1 (see e.g., Chen et al. ( 2023e , Lemma 1) ) .

##### Independent components.

We next consider the independent structure
from Section 3.2.
Under this model, we have the following decomposition for the score.

###### Proposition 4.2 .

The following holds under the independent components model (3.15):

$$ $\displaystyle\nabla\log p_{t}(x)=\sum_{i=1}^{K}UP_{i}^{\mathsf{T}}\nabla\log \pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x),$ (4.3) $$

where $P_{i}\in\mathbb{R}^{d_{i}\times D}$
selects the coordinates corresponding to the $i$-th variable group.

Note that the proof of
4.2 follows directly from the standard
change of variables formula, and the fact that the distribution of $w$ is unchanged when pre-multiplied by $U^{\mathsf{T}}$.

The score function decompositions
(4.2)
and (4.3) both exhibit similar structure, where
latent score functions are embedded into
a score function in the ambient space via a linear encoding/decoding process.
Fortunately, this embedding preserves the $\mathcal{F}_{1}$-norm of the underlying function.

###### Fact 4.3 .

Let $f:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ have bounded $\mathcal{F}_{1}$-norm, and let $U\in O(D,k)$.
Consider $g:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ defined as $g(x)=Uf(U^{\mathsf{T}}x)$. We have that
$\lVert g\rVert_{\mathcal{F}_{1}}=\lVert f\rVert_{\mathcal{F}_{1}}$.

Hence, if the latent function $f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ can be approximated well in $\mathcal{F}_{1}$, then the embedded function is also approximated well with the *same* $\mathcal{F}_{1}$ norm.
This is the key observation that enables our results.
Concretely, suppose that
$\hat{f}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ has bounded $\mathcal{F}_{1}$ norm and approximates
$f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ via
$\sup_{z\in B_{2}(d,M)}\lVert f(z)-\hat{f}(z)\rVert\leqslant\varepsilon$.
Then, $\hat{g}(x)=U\hat{f}(U^{\mathsf{T}}x)$ approximates $g(x)=Uf(U^{\mathsf{T}}x)$ via
$\sup_{x\in B_{2}(D,M)}\lVert g(x)-\hat{g}(x)\rVert\leqslant\varepsilon$, and $\lVert\hat{g}\rVert_{\mathcal{F}_{1}}=\lVert\hat{f}\rVert_{\mathcal{F}_{1}}$.

It remains to argue that $\mathcal{F}_{1}$ can approximate low dimensional functions well.
Fortunately, the approximation properties of $\mathcal{F}_{1}$ functions over various function classes is well-understood (Bach, ; Jacot et al., ).
In particular, we utilize the following $\mathcal{F}_{1}$ approximation result for Lipschitz continuous functions, adopted from Bach (, Proposition 6).

###### Lemma 4.4 .

Let $f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be $L$-Lipschitz and $B$-bounded on $B_{2}(d,M)$.
Define $K:=B\vee LM$.
For any $\varepsilon\in(0,K/2)$, there exists an $f_{\varepsilon}\in\mathcal{F}_{1}$ such that
$\sup_{x\in B_{2}(d,M)}\lVert f(x)-f_{\varepsilon}(x)\rVert\leqslant\varepsilon$ and:

$$ $\displaystyle\lVert f_{\varepsilon}\rVert_{\mathcal{F}_{1}}\leqslant O_{d}(1)K \left(\frac{K}{\varepsilon}\right)^{(d+1)/2}\log^{(d+1)/2}\left(\frac{K}{ \varepsilon}\right).$ $$

###### Proposition 4.2 .

###### Fact 4.3 .

###### Lemma 4.4 .

### 4.3 Uniform convergence of the DSM loss

With the approximation result in place, we turn to the analysis of uniform convergence term $T_{2}$ in (4.1).
Since the DSM loss is a least-squares regression problem, we can utilize existing results for analyzing generalization error with smooth losses (Srebro et al., ).
However, the main technical hurdle here is dealing with the fact that the data tuples $(x_{0},x_{t})$ are not uniformly bounded, which is a technical assumption needed in many of these arguments.(^7^77As an alternative to boundedness, one could also rely on small-ball arguments (Mendelson, ). In the interest of keeping our assumptions minimal as possible, we do not pursue this approach.)
While this can be handled straightforwardly for a fixed time $t$ via standard truncation arguments, one challenge is ensuring that the resulting high probability bounds degrade nicely as $t\to 0$.
The reason this is necessary is because the smallest timescale $t_{0}$ used will ultimately scale with the number of datapoints $n$.

To highlight the class of issues that arise in our truncation arguments,
consider the latent score function $\nabla\log\pi_{t}$ arising from the subspace structure setting (3.9).
In order to apply a truncation argument for analyzing $T_{2}$,
we need to argue that $\lVert\nabla\log\pi_{t}(z)\rVert$ is bounded uniformly over a high-probability truncation set $z\in B_{2}(d,M)$.
By the continuity of $\nabla\log\pi_{t}$, we know that $\sup_{z\in B_{2}(d,M)}\lVert\nabla\log\pi_{t}(z)\rVert=A_{t}<\infty$.
However, we need to control the behavior of $A_{t}$ as $t\to 0$.
By leveraging the perturbation analysis of Lee et al. (), we show that for all $t\geqslant 0$, under our assumptions, the inequality
$\lVert\nabla\log\pi_{t}(z)\rVert\leqslant\bar{L}(1+\lVert z\rVert)$ holds for all $z\in\mathbb{R}^{d}$.
Hence, we can bound $A_{t}\leqslant\bar{L}(1+M)$ for all $t\geqslant 0$.

## 5 Conclusion

In this work, we showed that diffusion models based on shallow neural networks
applied to 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., ), 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 our rates to match the minimax optimal score estimation rates of Wibisono et al. () – with the latent dimension playing the role of the ambient dimension – is another exciting area for future work.

#### Acknowledgments

Ingvar Ziemann acknowledges support by a Swedish Research Council international postdoc grant.

## Appendix A Preliminary results

We first make explicit the relation between the
score matching error $\mathcal{R}_{t}$ and the denoising loss $\mathcal{L}_{t}$.
In the sequel, we will make frequent use of
Tweedie’s formula [see e.g. Efron, ]:

$$ $\displaystyle\nabla\log p_{t}(x_{t})=\mathbb{E}\left[\nabla\log q_{t}(x_{t} \mid x_{0})\mid x_{t}\right],\quad\nabla\log q_{t}(x_{t}\mid x_{0}):=\frac{m_{ t}x_{0}-x_{t}}{\sigma_{t}^{2}}.$ $$

###### Fact A.1 (DSM loss minimizes score) .

We have that for all sufficiently regular $s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$:

$$ $\displaystyle\mathcal{R}_{t}(s)=\mathcal{L}_{t}(s)-C_{t},$ (A.1) $$

where the offset constant $C_{t}$ is given by:

$$ $C_{t}:=\mathbb{E}\operatorname*{\mathrm{tr}}\mathrm{Cov}\left(\frac{m_{t}x_{0} -x_{t}}{\sigma_{t}^{2}}\mid x_{t}\right).$ $$

Furthermore, we can bound $C_{t}$ by:

$$ $C_{t}\leqslant D/\sigma_{t}^{2}.$ $$

###### Proof.

The standard proof for denoising score matching [see e.g. Vincent, , Section 4.2]
shows that for all $s$:

$$ $\mathcal{R}_{t}(f)=\mathcal{L}_{t}(f)+\mathbb{E}_{(x_{0},x_{t})}[\lVert\nabla \log p_{t}(x_{t})\rVert^{2}-\lVert\nabla\log q_{t}(x_{t}\mid x_{0})\rVert^{2}].$ $$

Hence,

$$ $\displaystyle\mathbb{E}_{(x_{0},x_{t})}[\lVert\nabla\log p_{t}(x_{t})\rVert^{2 }-\lVert\nabla\log q_{t}(x_{t}\mid x_{0})\rVert^{2}]$ $\displaystyle=\mathbb{E}_{(x_{0},x_{t})}\left[\left\lVert\mathbb{E}\left[\frac {m_{t}x_{0}-x_{t}}{\sigma_{t}^{2}}\mid x_{t}\right]\right\rVert^{2}-\left \lVert\frac{m_{t}x_{0}-x_{t}}{\sigma_{t}^{2}}\right\rVert^{2}\right]$ $\displaystyle=-\mathbb{E}\mathbb{E}\left[\left\lVert\frac{m_{t}x_{0}-x_{t}}{ \sigma_{t}^{2}}\right\rVert^{2}-\left\lVert\mathbb{E}\left[\frac{m_{t}x_{0}-x_ {t}}{\sigma_{t}^{2}}\mid x_{t}\right]\right\rVert^{2}\mid x_{t}\right]$ $\displaystyle=-\mathbb{E}\operatorname*{\mathrm{tr}}\mathrm{Cov}\left(\frac{m_ {t}x_{0}-x_{t}}{\sigma_{t}^{2}}\mid x_{t}\right)$ $\displaystyle=-C_{t}.$ $$

To bound $C_{t}$, we observe:

$$ $\displaystyle C_{t}=\mathbb{E}\operatorname*{\mathrm{tr}}\mathrm{Cov}\left( \frac{m_{t}x_{0}-x_{t}}{\sigma_{t}^{2}}\mid x_{t}\right)$ $\displaystyle=\mathbb{E}\operatorname*{\mathrm{tr}}\mathrm{Cov}\left(\frac{w}{ \sigma_{t}}\mid x_{t}\right)\leqslant\mathbb{E}\lVert w/\sigma_{t}\rVert^{2}=D /\sigma_{t}^{2}.$ $$

∎

We next state a result from Benton et al. []
regarding the quality of the samples generated via the exponential integrator
scheme (3.4).

###### Lemma A.2 (Sampler quality from $L_{2}$ score bounds [Benton et al., 2024 , Theorem 2] ) .

Fix a $T\geqslant 1$ and $\zeta\in(0,1)$.
Also fix an $N\in\mathbb{N}_{+}$ which is even and satisfies $N\geqslant 2\log(1/\zeta)$.
Define a sequence of strictly increasing backwards process times $\{\tau_{i}\}_{i=0}^{N}$:

$$ $\displaystyle\tau_{i}=\begin{cases}2(T-1)\frac{i}{N}&\text{if }i\in\{0,\dots,N /2\},\\ T-\zeta^{2i/N-1}&\text{if }i\in\{N/2+1,\dots,N\}.\end{cases}$ (A.2) $$

Let $\gamma_{i}:=\tau_{i+1}-\tau_{i}$ for $i\in\{0,\dots,N-1\}$.
Suppose we have $N$ score functions $\hat{s}_{t}(x)$
for $t\in\{T-\tau_{i}\}_{i=0}^{N-1}$
which satisfy:

$$ $\displaystyle\sum_{i=0}^{N-1}\gamma_{i}\mathbb{E}_{p_{T-\tau_{i}}}\lVert\hat{s }_{T-\tau_{i}}-\nabla\log p_{T-\tau_{i}}\rVert^{2}\leqslant\varepsilon^{2}_{ \mathrm{score}}.$ (A.3) $$

Then, we have the following guarantee
for the exponential integrator (3.4):

$$ $\displaystyle\mathrm{KL}(p_{\zeta}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta})) \lesssim\varepsilon^{2}_{\mathrm{score}}+\kappa^{2}DN+\kappa(DT+\mu_{0}^{2})+( D+\mu_{0}^{2})e^{-2T},$ $$

where $\kappa,\mu_{0}$ are defined as:

$$ $\displaystyle\kappa:=\frac{2(T-1)+4\log(1/\zeta)}{N},\quad\mu_{0}:=\mathbb{E} \lVert x_{0}\rVert^{2}.$ $$

###### Proof.

In order to apply Benton et al. [, Theorem 2],
we need to compute a $\kappa$ such that:

$$ $\gamma_{k}\leqslant\kappa\min\{1,T-t_{k+1}\},\quad\forall k\in\{0,\dots,N-1\}.$ $$

To do this, we follow the proof of
Benton et al. [, Corollary 1].
First, for $k\in\{0,\dots,N/2-1\}$, we have that
$t_{k+1}\leqslant T-1$, and hence $T-t_{k+1}\geqslant T-(T-1)=1$.
Hence, we can simply take $\kappa\geqslant 2(T-1)/N$.
Now, for $k\in\{N/2,\dots,N-1\}$,
we have that $t_{k+1}\geqslant T-1$, and therefore
$T-t_{k+1}\leqslant T-(T-1)=1$.
Hence we need a $\kappa$ such that
$\gamma_{k}\leqslant\kappa(T-t_{k+1})$.
We therefore compute:

$$ $\displaystyle\zeta^{2k/N-1}-\zeta^{2(k+1)/N-1}=\gamma_{k}\leqslant\kappa(T-t_{ k+1})=\kappa\zeta^{2(k+1)/N-1}.$ $$

From this we see that $\kappa\geqslant\zeta^{-2/N}-1$ is required.
A sufficient condition takes:

$$ $\displaystyle\zeta^{-2/N}-1$ $\displaystyle=\exp\left(\frac{2}{N}\log(1/\zeta)\right)-1$ $\displaystyle\leqslant 1+(e-1)\frac{2}{N}\log(1/\zeta)-1$ $\displaystyle\text{since }e^{x}\leqslant 1+(e-1)x\text{ for }x\in[0,1]$ $\displaystyle\leqslant\frac{4\log(1/\zeta)}{N}.$ $$

Hence, in total we can set:

$$ $\displaystyle\kappa=\frac{2(T-1)+4\log(1/\zeta)}{N}.$ $$

The result now follows from invoking Benton et al. [, Theorem 2].
∎

Note that an immediate consequence of A.2 is the following observation: for any $\varepsilon\in(0,1)$, setting

$$ $\displaystyle T=c_{0}\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right), \quad N=2\left\lceil c_{1}\frac{D\vee\mu_{0}^{2}}{\varepsilon^{2}}\left[\log^{ 2}\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)+\log^{2}\left(\frac{1}{ \zeta}\right)\right]\right\rceil,$ $$

for some universal positive constants $c_{0},c_{1}$,
we have that

$$ $\displaystyle\mathrm{KL}(p_{\zeta}\;\|\;\mathrm{Law}(\hat{y}_{T-\zeta})) \lesssim\varepsilon^{2}_{\mathrm{score}}+\varepsilon^{2}.$ $$

Next, we state a technical lemma regarding a perturbation result for
Gaussian mollifications at small scale.

###### Lemma A.3 (Score function perturbation [Lee et al., 2023 , Lemma C.12] ) .

Suppose that $p(x)$ is a density on $\mathbb{R}^{d}$ such that $\nabla\log p(x)$ is $L$-Lipschitz on $\mathbb{R}^{d}$.
For $\alpha\geqslant 1$, define
the corresponding density $p_{\alpha}(x):=\alpha^{d}p(\alpha x)$. Let $\gamma_{\sigma^{2}}$ denote an ${\mathsf{N}}(0,\sigma^{2}I_{d})$ distribution. If $L\leqslant 1/(2\alpha^{2}\sigma^{2})$, then we have the following bound for all $x\in\mathbb{R}^{d}$:

$$ $\displaystyle\lVert\nabla\log p(x)-\nabla\log p_{\alpha}\ast\gamma_{\sigma^{2} }(x)\rVert$ $\displaystyle\qquad\leqslant 6\alpha^{2}L\sigma\sqrt{d}+(\alpha+2\alpha^{3}L \sigma^{2})(\alpha-1)L\lVert x\rVert+(\alpha-1+2\alpha^{3}L\sigma^{2})\lVert \nabla\log p(x)\rVert.$ $$

The previous mollification lemma is next used to bound the
score functions uniformly over time.

###### Proposition A.4 .

Consider a forward diffusion process $z_{t}\overset{\mathsf{d}}{=}m_{t}z_{0}+\sigma_{t}w$ on $\mathbb{R}^{d}$. Let $\pi_{t}$ denote the marginal distribution of $z_{t}$ for all $t\geqslant 0$. Suppose that $\nabla\log\pi_{t}$ is $L$-Lipschitz (for $L\geqslant 1$) on $\mathbb{R}^{d}$ for all $t\geqslant 0$.
Defining $\bar{L}:=cL(\mathbb{E}\lVert z_{0}\rVert+\sqrt{d}+\lVert\nabla\log\pi_{0}(0)\rVert)$ where $c\geqslant 1$ is an universal constant,
we have that for all $t\geqslant 0$ and $z\in\mathbb{R}^{d}$,

$$ $\displaystyle\lVert\nabla\log\pi_{t}(z)\rVert\leqslant\bar{L}(1+\lVert z\rVert).$ $$

###### Proof.

Define $\bar{\pi}_{t}(z):=m_{t}^{-d}\pi_{0}(m_{t}^{-1}z)$,
which is the density of the random variable $m_{t}z_{0}$.
Hence, we have that $\pi_{t}=\bar{\pi}_{t}\ast\gamma_{\sigma_{t}^{2}}$.
By A.3,
whenever $L\leqslant m_{t}^{2}/(2\sigma_{t}^{2})$, we have that:

$$ $\displaystyle\lVert\nabla\log\pi_{t}(0)\rVert\leqslant 6m_{t}^{-2}L\sigma_{t} \sqrt{d}+(m_{t}^{-1}+2m_{t}^{-3}L\sigma_{t}^{2})\lVert\nabla\log\pi_{0}(0)\rVert.$ $$

We now compute the range of $t$’s for which
$L\leqslant m_{t}^{2}/(2\sigma_{t}^{2})$ holds.
Using the specific form of $m_{t},\sigma_{t}$,

$$ $\displaystyle 2L\leqslant\frac{m_{t}^{2}}{\sigma_{t}^{2}}=\frac{\exp(-2t)}{1- \exp(-2t)}=\frac{1}{\exp(2t)-1}\Longleftrightarrow t\leqslant\frac{1}{2}\log \left(1+\frac{1}{2L}\right)=:t_{\star}.$ $$

First, note that since we assume $L\geqslant 1$,
then we have that $t_{\star}$ is bounded by a universal constant.
Hence, for $t\leqslant t_{\star}$,

$$ $\displaystyle\lVert\nabla\log\pi_{t}(0)\rVert\lesssim L(\sqrt{d}+\lVert\nabla \log\pi_{0}(0)\rVert).$ $$

Hence for any $z$,

$$ $\displaystyle\lVert\nabla\log\pi_{t}(z)\rVert$ $\displaystyle\leqslant L\lVert z\rVert+\lVert\nabla\log\pi_{t}(0)\rVert$ $\displaystyle\leqslant L\lVert z\rVert+cL(\sqrt{d}+\lVert\nabla\log\pi_{0}(0)\rVert)$ $\displaystyle\leqslant cL(\sqrt{d}+\lVert\nabla\log\pi_{0}(0)\rVert)(1+\lVert z \rVert).$ $$

On the other hand, when $t\geqslant t_{\star}$,
more work is needed.
When $t\geqslant t_{\star}$, we first bound:

$$ $\displaystyle\sigma_{t}^{-1}\leqslant\sigma_{t_{\star}}^{-1}=\sqrt{2L+1}.$ $$

Define two events:

$$ $\displaystyle\mathcal{E}_{1}:=\left\{\mathbb{E}[\lVert w\rVert/\sigma_{t}\mid z _{t}]\geqslant 4\sqrt{d}/\sigma_{t}\right\},\quad\mathcal{E}_{2}:=\left\{ \lVert z_{t}\rVert\geqslant 4(\mathbb{E}\lVert z_{0}\rVert+\sigma_{t}\sqrt{d})\right\}$ $$

By Markov’s inequality we have that:

$$ $\displaystyle\mathbb{P}_{z_{t}}\left\{\mathcal{E}_{1}\right\}\leqslant 1/4, \quad\mathbb{P}_{z_{t}}\left\{\mathcal{E}_{2}\right\}\leqslant 1/4.$ $$

Now suppose that $\mathcal{E}_{1}^{c}\subseteq\mathcal{E}_{2}$. Then, we have a contradiction, since:

$$ $\displaystyle 1-1/4\leqslant\mathbb{P}_{z_{t}}\{\mathcal{E}_{1}^{c}\}\leqslant \mathbb{P}_{z_{t}}\{\mathcal{E}_{2}\}\leqslant 1/4.$ $$

Hence, there must exists an $\omega\in\mathcal{E}_{1}^{c}$ such that $\omega\not\in\mathcal{E}_{2}$.
Hence, there exists a $\bar{z}_{t}$ satisfying:

$$ $\displaystyle\lVert\nabla\log\pi_{t}(\bar{z}_{t})\rVert\leqslant\mathbb{E}[ \lVert w\rVert/\sigma_{t}\mid z_{t}=\bar{z}_{t}]\leqslant 4\sqrt{d}/\sigma_{t} ,\quad\lVert\bar{z}_{t}\rVert\leqslant 4(\mathbb{E}\lVert z_{0}\rVert+\sigma_{ t}\sqrt{d}).$ $$

Hence for any $z$,

$$ $\displaystyle\lVert\nabla\log\pi_{t}(z)\rVert$ $\displaystyle\leqslant L\lVert z-\bar{z}_{t}\rVert+\lVert\nabla\log\pi_{t}( \bar{z}_{t})\rVert$ $\displaystyle\leqslant L\lVert z\rVert+4L(\mathbb{E}\lVert z_{0}\rVert+\sigma_ {t}\sqrt{d})+4\sqrt{d}/\sigma_{t}$ $\displaystyle\leqslant L\lVert z\rVert+4L(\mathbb{E}\lVert z_{0}\rVert+\sqrt{d })+4\sqrt{(2L+1)d}$ $\displaystyle\leqslant c^{\prime}L(\mathbb{E}\lVert z_{0}\rVert+\sqrt{d})(1+ \lVert z\rVert).$ $$

∎

Next, we state a $L_{\infty}$ approximation result for scalar-valued Lipschitz function from Bach [].

###### Lemma A.5 ( $L_{\infty}$ approximation of scalar Lipschitz functions [Bach, 2017 , Proposition 6] ) .

Let $f:\mathbb{R}^{d}\mapsto\mathbb{R}$.
Suppose that $f$ is $L$-Lipschitz and $B$-bounded on $B_{2}(d,M)$.
Set $K:=B\vee LM$.
For any $\gamma\geqslant O_{d}(1)\cdot K$ there exists an $f_{\gamma}\in\mathcal{F}_{1}$ such that $\lVert f_{\gamma}\rVert_{\mathcal{F}_{1}}\leqslant\gamma$ and:

$$ $\displaystyle\sup_{x\in B_{2}(d,M)}|f(x)-f_{\gamma}(x)|\leqslant O_{d}(1)K \left(\frac{K}{\gamma}\right)^{2/(d+1)}\log\left(\frac{\gamma}{K}\right).$ $$

Our next result is a simple technical fact which we will utilize in our
truncation analysis.

###### Proposition A.6 .

Let $S,\check{S}$ be two $\mathsf{X}$-valued random
variables over the same probability space.
Let $f:\mathsf{X}\mapsto\mathbb{R}$ be a measurable function.
We have:

$$ $\displaystyle\mathbb{E}[f(S)]\leqslant\mathbb{E}[f(\check{S})]+(\sqrt{\mathbb{ E}[f^{2}(S)]}+\sqrt{\mathbb{E}[f^{2}(\check{S})]})\sqrt{\mathbb{P}\{S\neq \check{S}\}}.$ $$

Note if $f$ is non-negative, then we have the simpler bound:

$$ $\displaystyle\mathbb{E}[f(S)]\leqslant\mathbb{E}[f(\check{S})]+\sqrt{\mathbb{E }[f^{2}(S)]\mathbb{P}\{S\neq\check{S}\}}.$ $$

###### Proof.

We have:

$$ $\displaystyle\mathbb{E}[f(S)]$ $\displaystyle=\mathbb{E}[f(S)\mathbf{1}\{S=\check{S}\}]+\mathbb{E}[f(S)\mathbf {1}\{S\neq\check{S}\}]$ $\displaystyle=\mathbb{E}[f(\check{S})\mathbf{1}\{S=\check{S}\}]+\mathbb{E}[f(S )\mathbf{1}\{S\neq\check{S}\}]$ $\displaystyle=\mathbb{E}[f(\check{S})]+\mathbb{E}[f(S)\mathbf{1}\{S\neq\check{ S}\}]-\mathbb{E}[f(\check{S})\mathbf{1}\{S\neq\check{S}\}]$ $\displaystyle\leqslant\mathbb{E}[f(\check{S})]+\sqrt{\mathbb{E}[f^{2}(S)] \mathbb{P}\{S\neq\check{S}\}}+\sqrt{\mathbb{E}[f^{2}(\check{S})]\mathbb{P}\{S \neq\check{S}\}}.$ $$

∎

The next result is a simple algebraic fact which will be useful for solving for implicit inequalities involving logarithms.

###### Proposition A.7 (Log dominance rule, [see e.g. Du et al., 2021 , Lemma F.2] ) .

Let $a,b,\nu$ be positive scalars.
Put $\bar{\nu}:=(1+\nu)^{\nu}$.
Then,

$$ $\displaystyle m\geqslant\bar{\nu}a\log^{\nu}(\bar{\nu}ab)\Longrightarrow m \geqslant a\log^{\nu}(bm).$ $$

Next, we have an intermediate result to bound the Rademacher
complexity of $\mathcal{F}_{1}$-norm bounded functions.

###### Proposition A.8 .

Let $\lVert x_{i}\rVert\leqslant 1$ for $i\in[n]$. We have:

$$ $\displaystyle\mathbb{E}_{\{\varepsilon_{i}\}}\sup_{u,v\in B_{2}(D)}\left|\frac {1}{n}\sum_{i=1}^{n}\langle u,\varepsilon_{i}\rangle\sigma(\langle v,x\rangle) \right|\leqslant c\sqrt{\frac{D}{n}},$ $$

where the $\varepsilon_{i}\in\{\pm 1\}^{d}$ are independent Rademacher random vectors(^8^88That is, each coordinate of $\varepsilon_{i}\in\{\pm 1\}^{d}$ is an independent Rademacher random variable.)
and $c>0$ is a universal constant.

###### Proof.

Define $X_{u,v}:=\frac{1}{n}\sum_{i=1}^{n}\langle u,\varepsilon_{i}\rangle\sigma(
\langle v,x\rangle)$.
Observe that for $u_{i},v_{i}\in B_{2}(D)$ for $i\in\{1,2\}$,

$$ $\displaystyle X_{u_{1},v_{1}}-X_{u_{2},v_{2}}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}[\sigma(\langle v_{1},x_{i}\rangle)- \sigma(\langle v_{2},x_{i}\rangle)]\langle u_{1},\varepsilon_{i}\rangle+\frac{ 1}{n}\sum_{i=1}^{n}\sigma(\langle v_{2},x_{i}\rangle)\langle u_{1}-u_{2}, \varepsilon_{i}\rangle$ $\displaystyle=:T_{1}+T_{2}.$ $$

First, we recall that a Rademacher random variable is $1$-sub-Gaussian, and therefore $\langle u_{i},\varepsilon_{i}\rangle$ is also $1$-sub-Gaussian since $\lVert u_{i}\rVert\leqslant 1$.
Using the fact that ReLU is $1$-Lipschitz followed by Cauchy-Schwarz
and the assumption that $\lVert x_{i}\rVert\leqslant 1$,

$$ $\displaystyle|\sigma(\langle v_{1},x_{i}\rangle)-\sigma(\langle v_{2},x_{i} \rangle)|\leqslant|\langle v_{1}-v_{2},x_{i}\rangle|\leqslant\lVert v_{1}-v_{2 }\rVert.$ $$

Hence, $[\sigma(\langle v_{1},x_{i}\rangle)-\sigma(\langle v_{2},x_{i}\rangle)]\langle
u
_{1},\varepsilon_{i}\rangle$ is $\lVert v_{1}-v_{2}\rVert$-sub-Gaussian.
Consequently, $T_{1}$ is $\lVert v_{1}-v_{2}\rVert/\sqrt{n}$-sub-Gaussian.
Similarly, since $|\sigma(\langle v_{2},x_{i}\rangle)|\leqslant 1$, we also have that
$T_{2}$ is $\lVert u_{1}-u_{2}\rVert/\sqrt{n}$-sub-Gaussian.
Hence, the sum $T_{1}+T_{2}$ is sub-Gaussian with constant:

$$ $\sqrt{2(\lVert v_{1}-v_{2}\rVert^{2}+\lVert u_{1}-u_{2}\rVert^{2})}/\sqrt{n}.$ $$

Letting $\omega=(u,v)$, we consider the following metric on
$\Omega:=B_{2}(D)\times B_{2}(D)$:

$$ $d((u_{1},v_{1}),(u_{2},v_{2}))=\sqrt{\lVert u_{1}-u_{2}\rVert^{2}+\lVert v_{1} -v_{2}\rVert^{2}}.$ $$

Hence for any $\omega_{1},\omega_{2}\in\Omega$,
the difference $X_{\omega_{1}}-X_{\omega_{2}}$ is $\sqrt{2/n}\cdot d(\omega_{1},\omega_{2})$-sub-Gaussian.
Therefore we can use Dudley’s inequality [see e.g. Vershynin, , Chapter 8] to bound:

$$ $\displaystyle\mathbb{E}\sup_{\omega\in\Omega}X_{\omega}$ $\displaystyle\leqslant cn^{-1/2}\int_{0}^{\infty}\sqrt{\log N(\varepsilon; \Omega,d)}\,\mathrm{d}\varepsilon=cn^{-1/2}\int_{0}^{\sqrt{2}}\sqrt{\log N( \varepsilon;\Omega,d)}\,\mathrm{d}\varepsilon.$ $$

Next, fix an $\varepsilon>0$ and let $\{u_{i}\},\{v_{i}\}$ be $\varepsilon/\sqrt{2}$-covers of $B_{2}(D)$.
Let $[u]$ (resp. $[v]$) denote the closest point in the cover to $u$ (resp. $v$).
Given $(u,v)\in\Omega$, we have:

$$ $\displaystyle d((u,v),([u],[v]))=\sqrt{\lVert u-[u]\rVert^{2}+\lVert v-[v]^{2} \rVert}\leqslant\varepsilon.$ $$

Using the standard volume estimate of the covering of $B_{2}(D)$ [see e.g. Vershynin, , Chapter 4],

$$ $\displaystyle\log N(\varepsilon;\Omega,d)\leqslant 2D\log(1+2\sqrt{2}/ \varepsilon).$ $$

Consequently,

$$ $\displaystyle\mathbb{E}\sup_{\omega\in\Omega}X_{w}\leqslant cn^{-1/2}\sqrt{2D} \int_{0}^{\sqrt{2}}\sqrt{\log(1+2\sqrt{2}/\varepsilon)}\,\mathrm{d}\varepsilon =c^{\prime}\sqrt{D/n}.$ $$

∎

Our final preliminary result translates the previous bound
A.8 to a bound on
the Rademacher complexity of $\mathcal{F}_{1}$-norm balls.

###### Proposition A.9 .

Let $\mathscr{F}=\{s:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\mid\lVert s\rVert_{
\mathcal{F}_{1}}\leqslant R\}$.
For any $\check{x}_{i}\in B_{2}(D,M)$, $i\in[n]$, we have:

$$ $\displaystyle\mathbb{E}_{\{\varepsilon_{i}\}}\sup_{f\in\mathscr{F}}n^{-1}\left |\sum_{i=1}^{n}\langle\varepsilon_{i},f(\check{x}_{i})\rangle\right|\leqslant cRM \sqrt{\frac{D}{n}},$ $$

where the $\varepsilon_{i}\in\{\pm 1\}^{d}$ are independent Rademacher random vectors
and $c>0$ is a universal constant.

###### Proof.

For any $\{\varepsilon_{i}\}$ and $f\in\mathscr{F}$, observe that by the definition of $\mathcal{F}_{1}$:

$$ $\displaystyle n^{-1}\left|\sum_{i=1}^{n}\langle\varepsilon_{i},f(\check{x}_{i} )\rangle\right|$ $\displaystyle=n^{-1}\left|\sum_{i=1}^{n}\left\langle\varepsilon_{i},\int u \sigma(\langle v,\check{x}_{i}\rangle)\,\mathrm{d}\mu(u,v)\right\rangle\right|$ $\displaystyle=\left|\int\left[\frac{1}{n}\sum_{i=1}^{n}\langle\varepsilon_{i}, u\rangle\sigma(\langle v,\check{x}_{i}\rangle)\right]\mathrm{d}\mu(u,v)\right|$ $\displaystyle\leqslant R\sup_{u,v\in\mathbb{S}^{D-1}}\left|\frac{1}{n}\sum_{i= 1}^{n}\langle\varepsilon_{i},u\rangle\sigma(\langle v,\check{x}_{i}\rangle) \right|.$ $$

Hence,

$$ $\displaystyle\mathbb{E}_{\{\varepsilon_{i}\}}\sup_{f\in\mathscr{F}}n^{-1}\left |\sum_{i=1}^{n}\langle\varepsilon_{i},f(\check{x}_{i})\rangle\right|\leqslant R \cdot\mathbb{E}_{\{\varepsilon_{i}\}}\sup_{u,v\in\mathbb{S}^{D-1}}\left|\frac{ 1}{n}\sum_{i=1}^{n}\langle\varepsilon_{i},u\rangle\sigma(\langle v,\check{x}_{ i}\rangle)\right|,$ $$

from which the claim follows by
A.8
and using homogeneity of ReLU to scale the data points $\check{x}_{i}$ to $B_{2}(D)$.
∎

###### Fact A.1 (DSM loss minimizes score) .

###### Proof.

###### Lemma A.2 (Sampler quality from L 2 subscript 𝐿 2 L_{2} italic_L start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT score bounds [Benton et al., 2024 , Theorem 2] ) .

###### Proof.

###### Lemma A.3 (Score function perturbation [Lee et al., 2023 , Lemma C.12] ) .

###### Proposition A.4 .

###### Proof.

###### Lemma A.5 ( L ∞ subscript 𝐿 L_{\infty} italic_L start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT approximation of scalar Lipschitz functions [Bach, 2017 , Proposition 6] ) .

###### Proposition A.6 .

###### Proof.

###### Proposition A.7 (Log dominance rule, [see e.g. Du et al., 2021 , Lemma F.2] ) .

###### Proposition A.8 .

###### Proof.

###### Proposition A.9 .

###### Proof.

## Appendix B ℱ 1 subscript ℱ 1 \mathcal{F}_{1} caligraphic_F start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT approximation theory for Lipschitz continuous functions

Here we develop the necessary results to establish that $\mathcal{F}_{1}$ functions can approximate structured score functions in an efficient way.
Our first result is a preliminary result that allows us to translate $L_{\infty}$ approximation bounds to $L_{2}$ bounds.
For what follows, let the notation $\mathcal{P}(\mathsf{X})$ denote the set of subsets of $\mathsf{X}$.

###### Proposition B.1 .

Let $M:(0,1)\mapsto\mathcal{P}(\mathbb{R}^{D})$ be such that:

$$ $\forall\,\delta\in(0,1),\quad\mathbb{P}_{x_{t}\sim p_{t}}\{x_{t}\in M(\delta) \}\geqslant 1-\delta.$ $$

Suppose that $R(\varepsilon,\delta)$ satisfies the following condition: for any positive $\varepsilon>0$ and $\delta\in(0,1)$ there exists a function $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ such that

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant R(\varepsilon, \delta),\quad\sup_{x\in M(\delta)}\lVert\hat{s}(x)-\nabla\log p_{t}(x)\rVert \leqslant\varepsilon.$ (B.1) $$

Suppose there exists a $\delta\in(0,1)$ satisfying:

$$ $\displaystyle R^{4}(\varepsilon/2,\delta)\cdot\delta\leqslant c_{0}\varepsilon ^{4}/\mathbb{E}\lVert x_{t}\rVert^{4},\quad\delta\leqslant c_{1}(\varepsilon \sigma_{t})^{4}/D^{2}.$ (B.2) $$

Above, both $c_{0},c_{1}$ are universal positive constants.
Then, there exists an $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ such that:

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant R(\varepsilon/2, \delta),\quad\lVert\hat{s}-\nabla\log p_{t}\rVert_{L_{2}(p_{t})}\leqslant\varepsilon.$ (B.3) $$

###### Proof.

Let $\mathcal{E}_{G}:=\{x_{t}\in M(\delta)\}$.
By assumption, we have that $\mathbb{P}(\mathcal{E}_{G})\geqslant 1-\delta$.
Put $s_{\star}:=\nabla\log p_{t}$
and let $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ be as guaranteed by the assumption such that:

$$ $\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant R(\varepsilon/2,\delta),\quad \sup_{x\in M(\delta)}\lVert\hat{s}(x)-s_{\star}(x)\rVert\leqslant\varepsilon/2.$ $$

Hence,

$$ $\displaystyle\mathbb{E}_{x_{t}}\lVert\hat{s}-s_{\star}\rVert^{2}$ $\displaystyle=\mathbb{E}_{x_{t}}\lVert\hat{s}-s_{\star}\rVert^{2}\mathbf{1}\{ \mathcal{E}_{G}\}+\mathbb{E}_{x_{t}}\lVert\hat{s}-s_{\star}\rVert^{2}\mathbf{1 }\{\mathcal{E}_{G}^{c}\}$ $\displaystyle\leqslant\sup_{x\in M(\delta)}\lVert\hat{s}(x)-s_{\star}(x)\rVert ^{2}+\sqrt{\mathbb{E}_{x_{t}}\lVert\hat{s}-s_{\star}\rVert^{4}}\cdot\sqrt{\delta}$ $\displaystyle\leqslant(\varepsilon/2)^{2}+\sqrt{\mathbb{E}_{x_{t}}\lVert\hat{s }-s_{\star}\rVert^{4}}\cdot\sqrt{\delta}.$ $$

Consequently, by taking square root of both sides:

$$ $\displaystyle\lVert\hat{s}-s_{\star}\rVert_{L_{2}(p_{t})}\leqslant\varepsilon/ 2+\lVert\hat{s}-s_{\star}\rVert_{L_{4}(p_{t})}\cdot\delta^{1/4}.$ $$

Let us now control $\lVert\hat{s}-s_{\star}\rVert_{L_{4}(p_{t})}$.
By triangle inequality and $\lVert\hat{s}(x)\rVert\leqslant\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\lVert x\rVert$ for all $x$:

$$ $\displaystyle\lVert\hat{s}-s_{\star}\rVert_{L_{4}(p_{t})}$ $\displaystyle\leqslant\lVert\hat{s}\rVert_{L_{4}(p_{t})}+\lVert s_{\star} \rVert_{L_{4}(p_{t})}$ $\displaystyle\leqslant\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\lVert x_{t}\rVert_ {L_{4}(p_{t})}+\lVert s_{\star}\rVert_{L_{4}(p_{t})}$ $\displaystyle\leqslant R(\varepsilon/2,\delta)\lVert x_{t}\rVert_{L_{4}(p_{t}) }+\lVert s_{\star}\rVert_{L_{4}(p_{t})}.$ $$

To control $\lVert s_{\star}\rVert_{L_{4}(p_{t})}$, we use Tweedie’s formula:

$$ $\displaystyle\nabla\log p_{t}(x_{t})=\mathbb{E}\left[\frac{m_{t}x_{0}-x_{t}}{ \sigma_{t}^{2}}\,\bigg{|}\,x_{t}\right]=-\frac{\mathbb{E}[w\mid x_{t}]}{\sigma _{t}}.$ $$

Hence by Jensen’s inequality and the tower property,

$$ $\displaystyle\lVert s_{\star}\rVert_{L_{4}(p_{t})}^{4}=\mathbb{E}\lVert\nabla \log p_{t}(x_{t})\rVert^{4}=\frac{1}{\sigma_{t}^{4}}\mathbb{E}\lVert\mathbb{E} [w\mid x_{t}]\rVert^{4}\leqslant\frac{1}{\sigma_{t}^{4}}\mathbb{E}\lVert w \rVert^{4}\leqslant\frac{3D^{2}}{\sigma_{t}^{4}}.$ $$

Combining these calculations,

$$ $\displaystyle\lVert\hat{s}-s_{\star}\rVert_{L_{4}(p_{t})}$ $\displaystyle\leqslant R(\varepsilon/2,\delta)\lVert x_{t}\rVert_{L_{4}(p_{t}) }+\frac{3^{1/4}\sqrt{D}}{\sigma_{t}}.$ $$

Hence,

$$ $\displaystyle\lVert\hat{s}-s_{\star}\rVert_{L_{2}(p_{t})}\leqslant\varepsilon/ 2+\left[R(\varepsilon/2,\delta)\lVert x_{t}\rVert_{L_{4}(p_{t})}+\frac{3^{1/4} \sqrt{D}}{\sigma_{t}}\right]\cdot\delta^{1/4}$ $$

Hence, if we set $\delta$ such that:

$$ $\displaystyle R(\varepsilon/2,\delta)\lVert x_{t}\rVert_{L_{4}(p_{t})}\cdot \delta^{1/4}\leqslant\varepsilon/4,\quad\frac{3^{1/4}\sqrt{D}}{\sigma_{t}} \cdot\delta^{1/4}\leqslant\varepsilon/4,$ $$

then we conclude that $\lVert\hat{s}-s_{\star}\rVert_{L_{2}(p_{t})}\leqslant\varepsilon$.
∎

We next turn to our main $L_{\infty}$ approximation result for Lipschitz functions.
We proceed in two steps.
First, we extend A.5
to vector-valued Lipschitz functions in a straightforward way. Then, we use the log dominance rule
to invert the result.
For the first step, we have the following result.

###### Proposition B.2 .

Let $f:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$.
Suppose that $f$ is $L$-Lipschitz and $B$-bounded on $B_{2}(d,M)$. Set $K_{d}:=d\cdot(B\vee LM)$.
For any $\gamma\geqslant O_{d}(1)\cdot K_{d}$, there exists an $f_{\gamma}\in\mathcal{F}_{1}$ such that $\lVert f_{\gamma}\rVert_{\mathcal{F}_{1}}\leqslant\gamma$ and:

$$ $\displaystyle\sup_{x\in B_{2}(d,M)}\lVert f(x)-f_{\gamma}(x)\rVert\leqslant O_ {d}(1)K_{d}\left(\frac{K_{d}}{\gamma}\right)^{2/(d+1)}\log\left(\frac{\gamma}{ K_{d}}\right).$ (B.4) $$

###### Proof.

For $i\in[d]$, let $f_{i}(x):=\langle e_{i},f(x)\rangle$, where $e_{i}\in\mathbb{R}^{d}$ is the $i$-th standard basis vector.
We will apply A.5 to each of the $f_{i}$’s.
Note that each $f_{i}$ is also $L$-Lipschitz and $B$-bounded on $B_{2}(d,M)$.
Hence, for every $i\in[d]$ there exists an $f_{\gamma,i}\in\mathcal{F}_{1}$ with
$\lVert f_{\gamma,i}\rVert_{\mathcal{F}_{1}}\leqslant\gamma/d$ and:

$$ $\sup_{x\in B_{2}(d,M)}|f_{i}(x)-f_{\gamma,i}(x)|\leqslant O_{d}(1)\frac{K_{d}} {d}\left(\frac{K_{d}}{\gamma}\right)^{2/(d+1)}\log\left(\frac{\gamma}{K_{d}} \right)=:\zeta.$ $$

Choosing $f_{\gamma}:=(f_{\gamma,1},\dots,f_{\gamma,d})$ yields:

$$ $\displaystyle\sup_{x\in B_{2}(d,M)}\lVert f(x)-f_{\gamma}(x)\rVert$ $\displaystyle=\sup_{x\in B_{2}(d,M)}\sqrt{\sum_{i=1}^{d}|f_{i}(x)-f_{\gamma,i} (x)|^{2}}$ $\displaystyle\leqslant\sqrt{\sum_{i=1}^{d}\sup_{x\in B_{2}(d,M)}|f_{i}(x)-f_{ \gamma,i}(x)|^{2}}\leqslant\sqrt{d}\zeta.$ $$

To finish the claim, we bound the $\mathcal{F}_{1}$ norm of $f_{\gamma}$. Since

$$ $\displaystyle f_{\gamma}(x)=\sum_{i=1}^{d}e_{i}f_{\gamma,i}(x),$ $$

by triangle inequality $\lVert f_{\gamma}\rVert_{\mathcal{F}_{1}}\leqslant\sum_{i=1}^{d}\lVert f_{
\gamma,i}\rVert_{\mathcal{F}_{1}}\leqslant d\cdot(\gamma/d)=\gamma$.
∎

We now execute the second step,
where we invert the RHS of B.2
and solve for $\gamma$.
See 4.4

###### Proof.

Setting the RHS of (B.4)
from B.2 to $\varepsilon$ and rearranging terms,
we need the following condition to hold (recall $K_{d}:=d\cdot K$):

$$ $\displaystyle\frac{\gamma}{K_{d}}\geqslant\left(\frac{O_{d}(1)K_{d}}{ \varepsilon}\right)^{(d+1)/2}\log^{(d+1)/2}\left(\frac{\gamma}{K_{d}}\right).$ $$

Using A.7,
a sufficient condition is:

$$ $\displaystyle\frac{\gamma}{K_{d}}\geqslant O_{d}(1)\left(\frac{O_{d}(1)K_{d}}{ \varepsilon}\right)^{(d+1)/2}\log^{(d+1)/2}\left(O_{d}(1)\left(\frac{O_{d}(1)K _{d}}{\varepsilon}\right)^{(d+1)/2}\right).$ $$

The claim now follows by simplifying these expressions
with our assumptions.
∎

###### Proposition B.1 .

###### Proof.

###### Proposition B.2 .

###### Proof.

###### Proof.

## Appendix C Uniform convergence for the DSM loss

Our first step is to establish the claimed
basic inequality (4.1).

###### Proposition C.1 (Basic generalization inequality) .

Let $\mathscr{F}$ be any set of functions mapping $\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$.
Let $\hat{f}_{t}\in\mathscr{F}$ denote the DSM empirical risk minimizer:

$$ $\displaystyle\hat{f}_{t}\in\arg\min_{f\in\mathscr{F}}\hat{\mathcal{L}}_{t}(f).$ $$

Then, we have for any $\varepsilon\geqslant 0$:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})]$ $\displaystyle\leqslant(1+\varepsilon)\inf_{f\in\mathscr{F}}\mathcal{R}_{t}(f)+ \mathbb{E}_{\mathcal{D}_{t}}\sup_{f\in\mathscr{F}}[\mathcal{L}_{t}(f)-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(f)]+\varepsilon\cdot C_{t}.$ $$

###### Proof.

For any $\varepsilon\geqslant 0$ and any $f\in\mathscr{F}$,

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})]$ $\displaystyle=\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{L}_{t}(\hat{f}_{t})-C_{t}]$ using A.1 $\displaystyle=\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{L}_{t}(\hat{f}_{t})-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(\hat{f}_{t})+(1+\varepsilon)\hat{\mathcal{L} }_{t}(\hat{f}_{t})-C_{t}]$ $\displaystyle\leqslant\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{L}_{t}(\hat{f}_{t} )-(1+\varepsilon)\hat{\mathcal{L}}_{t}(\hat{f}_{t})+(1+\varepsilon)\hat{ \mathcal{L}}_{t}(f)-C_{t}]$ since $\hat{f}_{t}$ is an ERM $\displaystyle=\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{L}_{t}(\hat{f}_{t})-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(\hat{f}_{t})]+(1+\varepsilon)\mathcal{L}_{t} (f)-C_{t}$ since $\mathbb{E}_{\mathcal{D}_{t}}[\hat{\mathcal{L}}_{t}(f)]=\mathcal{L}_{t}(f)$ $\displaystyle=\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{L}_{t}(\hat{f}_{t})-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(\hat{f}_{t})]+(1+\varepsilon)\mathcal{R}_{t} (f)+\varepsilon\cdot C_{t}$ using A.1 $\displaystyle\leqslant\mathbb{E}_{\mathcal{D}_{t}}\sup_{f\in\mathscr{F}}[ \mathcal{L}_{t}(f)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f)]+(1+\varepsilon) \mathcal{R}_{t}(f)+\varepsilon\cdot C_{t}.$ $$

The claim now follows by taking the infimum of the RHS over $f\in\mathscr{F}$.
∎

The rest of this section will focus
on the uniform convergence term
in the basic inequality (4.1).
We first define some notation which we will use in our analysis.
Let $\nu_{\delta}(\check{x}_{0},\check{x}_{t})$ denote a distribution over
pairs of *truncated* vectors, parameterized by $\delta\in(0,1)$, defined as follows:

$$ $\displaystyle\nu_{\delta}:=\mathrm{Law}((x_{0},x_{t})\cdot\mathbf{1}\{\mathcal {E}_{x}(\delta)\}),\quad\mathbb{P}\{\mathcal{E}_{x}(\delta)\}\geqslant 1-\delta.$ (C.1) $$

Note that in the above definition, the event $\mathcal{E}_{x}(\delta)$ lives in the *joint* probability space of $(x_{0},x_{t})$.
The specifics of the event $\mathcal{E}_{x}(\delta)$
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 $\check{\mu}_{t,x}(\delta)$ and $\check{\mu}_{t,q}(\delta)$:

$$ $\displaystyle(\check{x}_{0},\check{x}_{t})\sim\nu_{\delta}\Longrightarrow \lVert\check{x}_{t}\rVert\leqslant\check{\mu}_{t,x}(\delta)\textrm{ and } \lVert\nabla\log q_{t}(\check{x}_{t}\mid\check{x}_{0})\rVert\leqslant\check{ \mu}_{t,q}(\delta).$ (C.2) $$

Next, define the population denoising loss over $\nu_{\delta}$ as:

$$ $\displaystyle\check{\mathcal{L}}_{t}(f;\delta):=\mathbb{E}_{(\check{x}_{0}, \check{x}_{t})\sim\nu_{\delta}}\lVert f(\check{x}_{t})-\nabla\log q_{t}(\check {x}_{t}\mid\check{x}_{0})\rVert^{2}.$ (C.3) $$

Furthermore,
given a dataset $\bar{\mathcal{D}}_{t}=\{(\bar{x}_{0}^{i},\bar{x}_{t}^{i})\}_{i=1}^{n}$,
the *generalized empirical loss* is defined as

$$ $\displaystyle\hat{\mathcal{L}}_{t}(f;\bar{\mathcal{D}}_{t}):=\frac{1}{n}\sum_{ i=1}^{n}\lVert f(\bar{x}_{t}^{i})-\nabla\log q_{t}(\bar{x}_{t}^{i}\mid\bar{x}_ {0}^{i})\rVert^{2}.$ (C.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 C.2 .

For $R_{t}\geqslant 1$, define
$\mathscr{F}_{t}:=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid\lVert s\rVert_{
\mathcal{F}_{1}}\leqslant R_{t}\}$.
For $\varepsilon\in(0,1]$, we have:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(f)]$ $\displaystyle\leqslant\tilde{O}(1)(1+\varepsilon^{-1})\left[\frac{R_{t}^{2} \check{\mu}_{t,x}^{2}(n^{-5})D+\check{\mu}_{t,q}^{2}(n^{-5})}{n}\right]+O(1) \frac{R_{t}^{2}\lVert x_{t}\rVert^{2}_{L_{4}(p_{t})}+D/\sigma_{t}^{2}}{n^{2}}.$ $$

The proof of C.2 follows immediately
from the following two results (invoking them both with $\delta=n^{-4}$).
The first result applies a truncation argument so that it suffices
to prove uniform convergence over truncated data.

###### Proposition C.3 .

Fix a $\delta\in(0,1)$.
Define the truncated random pair $(\check{x}_{0},\check{x}_{t})\sim\nu_{\delta/n}$ (cf. (C.1)).
Let the truncated dataset $\check{\mathcal{D}}_{t}:=\{(\check{x}_{0}^{i},\check{x}_{t}^{i})\}_{i=1}^{n}$ be $n$ iid copies of $(\check{x}_{0},\check{x}_{t})$, i.e., $\check{\mathcal{D}}_{t}\sim\nu_{\delta/n}^{\otimes n}$.
For some $R_{t}\geqslant 1$, define $\mathscr{F}_{t}:=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid\lVert s\rVert_{
\mathcal{F}_{1}}\leqslant R_{t}\}$.
For all $\varepsilon\in[0,1]$, we have that:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(f)]$ $\displaystyle\leqslant\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}} _{t}(f;\delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t })]+c(R_{t}^{2}\lVert x_{t}\rVert_{L_{4}(p_{t})}^{2}+\sigma_{t}^{-2}D)\cdot \delta^{1/2},$ $$

where $c>0$ is a universal constant.

###### Proof.

Let $\mathcal{E}_{G}$ denote the event $\mathcal{E}_{G}:=\{\mathcal{D}_{t}=\check{\mathcal{D}}_{t}\}$.
By a union bound, $\mathbb{P}(\mathcal{E}_{G})\geqslant 1-\delta$.
Next we define for a dataset $\bar{\mathcal{D}}_{t}$ the random variable:

$$ $\displaystyle\psi(\bar{\mathcal{D}}_{t}):=\sup_{f\in\mathscr{F}_{t}}[\mathcal{ L}_{t}(f)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\bar{\mathcal{D}}_{t})].$ (C.5) $$

Applying A.6:

$$ $\displaystyle\mathbb{E}[\psi(\mathcal{D}_{t})]\leqslant\mathbb{E}[\psi(\check{ \mathcal{D}}_{n})]+(\sqrt{\mathbb{E}[\psi^{2}(\mathcal{D}_{t})]}+\sqrt{\mathbb {E}[\psi^{2}(\check{\mathcal{D}}_{n})]})\cdot\delta^{1/2}.$ (C.6) $$

We next need to upper bound both:

$$ $\displaystyle\mathbb{E}[\psi^{2}(\mathcal{D}_{t})],\quad\mathbb{E}[\psi^{2}( \check{\mathcal{D}}_{n})].$ $$

To do this, we first derive a few intermediate bounds.
We start with:

$$ $\displaystyle\mathcal{L}_{t}(f)$ $\displaystyle=\mathbb{E}_{(x_{0},x_{t})}\lVert f(x_{t})-\nabla\log q_{t}(x_{t} \mid x_{0})\rVert^{2}$ $\displaystyle\leqslant 2\mathbb{E}\lVert f(x_{t})\rVert^{2}+2\mathbb{E}\lVert \nabla\log q_{t}(x_{t}\mid x_{0})\rVert^{2}$ since $(a+b)^{2}\leqslant 2(a^{2}+b^{2})$ $\displaystyle\leqslant 2R_{t}^{2}\mathbb{E}\lVert x_{t}\rVert^{2}+2\mathbb{E} \lVert(x_{t}-m_{t}x_{0})/\sigma_{t}^{2}\rVert^{2}$ since $\lVert f\rVert_{\mathcal{F}_{1}}\leqslant R_{t}$ $\displaystyle=2R_{t}^{2}\mathbb{E}\lVert x_{t}\rVert^{2}+2\mathbb{E}\lVert w/ \sigma_{t}\rVert^{2}$ $\displaystyle=2R_{t}^{2}\mathbb{E}\lVert x_{t}\rVert^{2}+2D/\sigma_{t}^{2}.$ $$

Next, we have:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}\hat{\mathcal{L}}_{t}^{2}(f)$ $\displaystyle=\mathbb{E}\sup_{f\in\mathscr{F}_{t}}\left(\frac{1}{n}\sum_{i=1}^ {n}\lVert f(x_{t}^{i})-\nabla\log q_{t}(x_{t}^{i}\mid x_{0}^{i})\rVert^{2} \right)^{2}$ $\displaystyle\leqslant\mathbb{E}\left(\frac{2R_{t}^{2}}{n}\sum_{i=1}^{n}\lVert x _{t}^{i}\rVert^{2}+\frac{2}{n\sigma_{t}^{2}}\sum_{i=1}^{n}\lVert w^{i}\rVert^{ 2}\right)^{2}$ since $\lVert f\rVert_{\mathcal{F}_{1}}\leqslant R_{t}$ $\displaystyle\leqslant\frac{4R_{t}^{4}}{n}\sum_{i=1}^{n}\mathbb{E}\lVert x_{t} ^{i}\rVert^{4}+\frac{4}{n\sigma_{t}^{4}}\sum_{i=1}^{n}\mathbb{E}\lVert w^{i} \rVert^{4}$ Cauchy-Schwarz $\displaystyle\leqslant 4R_{t}^{4}\mathbb{E}\lVert x_{t}\rVert^{4}+12D^{2}/ \sigma_{t}^{4}.$ $$

Hence,

$$ $\displaystyle\mathbb{E}[\psi^{2}(\mathcal{D}_{t})]$ $\displaystyle\leqslant\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)- (1+\varepsilon)\hat{\mathcal{L}}_{t}(f)]^{2}$ $\displaystyle\lesssim\sup_{f\in\mathscr{F}_{t}}\mathcal{L}_{t}^{2}(f)+\mathbb{ E}\sup_{f\in\mathscr{F}_{t}}\hat{\mathcal{L}}^{2}_{t}(f)$ $\displaystyle\lesssim R_{t}^{4}\mathbb{E}\lVert x_{t}\rVert^{4}+D^{2}/\sigma_{ t}^{4}.$ $$

Now we move on to bounding $\mathbb{E}[\psi^{2}(\check{\mathcal{D}}_{n})]$.
Defining $\mathcal{E}_{x}:=\mathcal{E}_{x}(\delta/n)$,

$$ $\displaystyle\check{x}_{t}-m_{t}\check{x}_{0}=(x_{t}-m_{t}x_{0})\cdot\mathbf{1 }\{\mathcal{E}_{x}\}=\sigma_{t}w\cdot\mathbf{1}\{\mathcal{E}_{x}\},$ $$

and therefore:

$$ $\displaystyle\mathbb{E}\lVert(\check{x}_{t}-m_{t}\check{x}_{0})/\sigma_{t}^{2} \rVert^{4}$ $\displaystyle=\mathbb{E}\lVert w/\sigma_{t}\rVert^{4}\mathbf{1}\{\mathcal{E}_{ x}\}\leqslant\mathbb{E}\lVert w/\sigma_{t}^{4}\rVert\leqslant 3D^{2}/\sigma_{t }^{4}.$ $$

Hence:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}\hat{\mathcal{L}}_{t}^{2}(f; \check{\mathcal{D}}_{t})$ $\displaystyle=\mathbb{E}\sup_{f\in\mathscr{F}_{t}}\left(\frac{1}{n}\sum_{i=1}^ {n}\lVert f(\check{x}_{t}^{i})-\nabla\log q_{t}(\check{x}_{t}^{i}\mid\check{x} _{0}^{i})\rVert^{2}\right)^{2}$ $\displaystyle\leqslant\mathbb{E}\left(\frac{2R_{t}^{2}}{n}\sum_{i=1}^{n}\lVert \check{x}_{t}^{i}\rVert^{2}+\frac{2}{n\sigma_{t}^{2}}\sum_{i=1}^{n}\lVert( \check{x}_{t}^{i}-m_{t}\check{x}_{0}^{i})/\sigma_{t}^{2}\rVert^{2}\right)^{2}$ since $\lVert f\rVert_{\mathcal{F}_{1}}\leqslant R_{t}$ $\displaystyle\leqslant\frac{4R_{t}^{4}}{n}\sum_{i=1}^{n}\mathbb{E}\lVert\check {x}_{t}^{i}\rVert^{4}+\frac{4}{n\sigma_{t}^{4}}\sum_{i=1}^{n}\mathbb{E}\lVert( \check{x}_{t}^{i}-m_{t}\check{x}_{0}^{i})/\sigma_{t}^{2}\rVert^{4}$ Cauchy-Schwarz $\displaystyle\leqslant\frac{4R_{t}^{4}}{n}\sum_{i=1}^{n}\mathbb{E}\lVert{x}_{t }^{i}\rVert^{4}+\frac{4}{n\sigma_{t}^{4}}\sum_{i=1}^{n}\mathbb{E}\lVert({x}_{t }^{i}-m_{t}{x}_{0}^{i})/\sigma_{t}^{2}\rVert^{4}$ $\displaystyle=\frac{4R_{t}^{4}}{n}\sum_{i=1}^{n}\mathbb{E}\lVert{x}_{t}^{i} \rVert^{4}+\frac{4}{n\sigma_{t}^{4}}\sum_{i=1}^{n}\mathbb{E}\lVert w^{i}/ \sigma_{t}\rVert^{4}$ $\displaystyle\leqslant 4R_{t}^{4}\mathbb{E}\lVert x_{t}\rVert^{4}+12D^{2}/ \sigma_{t}^{4}.$ $$

Therefore, we conclude that:

$$ $\displaystyle\max\{\mathbb{E}[\psi^{2}(\mathcal{D}_{t})],\mathbb{E}[\psi^{2}( \check{\mathcal{D}}_{t})]\}\lesssim R_{t}^{4}\mathbb{E}\lVert x_{t}\rVert^{4}+ \sigma_{t}^{-4}D^{2}.$ (C.7) $$

Plugging (C.7) into
(C.6),

$$ $\displaystyle\mathbb{E}[\psi(\mathcal{D}_{t})]$ $\displaystyle\leqslant\mathbb{E}[\psi(\check{\mathcal{D}}_{t})]+c(R_{t}^{2} \lVert x_{t}\rVert_{L_{4}(p_{t})}^{2}+\sigma_{t}^{-2}D)\cdot\delta^{1/2}$ $\displaystyle\leqslant\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)- (1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]+c(R_{t}^{2} \lVert x_{t}\rVert_{L_{4}(p_{t})}^{2}+\sigma_{t}^{-2}D)\cdot\delta^{1/2}$ $\displaystyle\leqslant\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}} _{t}(f;\delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t })]+\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-\check{\mathcal{L}}_{t}(f; \delta/n)]$ $\displaystyle\qquad+c(R_{t}^{2}\lVert x_{t}\rVert_{L_{4}(p_{t})}^{2}+\sigma_{t }^{-2}D)\cdot\delta^{1/2}.$ $$

Next, define:

$$ $\displaystyle V_{f}((x,\bar{x})):=\lVert f(\bar{x})-\nabla\log q_{t}(\bar{x} \mid x)\rVert^{2}.$ $$

Observe by Jensen’s inequality we can bound

$$ $\displaystyle\mathbb{E}[V_{f}^{2}((x_{0},x_{t}))]\leqslant\mathbb{E}\sup_{f\in \mathscr{F}_{t}}\hat{\mathcal{L}}_{t}^{2}(f)\lesssim R_{t}^{4}\mathbb{E}\lVert x _{t}\rVert^{4}+D^{2}/\sigma_{t}^{4}.$ $$

Therefore, by application of A.6,

$$ $\displaystyle\mathbb{E}[V_{f}((x_{0},x_{t}))]$ $\displaystyle\leqslant\mathbb{E}[V_{f}((\check{x}_{0},\check{x}_{t}))]+\sqrt{ \mathbb{E}[V_{f}^{2}((x_{0},x_{t}))]}\cdot\sqrt{\delta/n}$ $\displaystyle\leqslant\mathbb{E}[V_{f}((\check{x}_{0},\check{x}_{t}))]+c^{ \prime}(R_{t}^{2}\lVert x_{t}\rVert_{L_{4}(p_{t})}^{2}+\sigma_{t}^{-2}D)\cdot \sqrt{\delta/n}.$ $$

Hence,

$$ $\displaystyle\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-\check{\mathcal{L}} _{t}(f;\delta/n)]$ $\displaystyle=\sup_{f\in\mathscr{F}_{t}}[\mathbb{E}[V_{f}((x_{0},x_{t}))]- \mathbb{E}[V_{f}((\check{x}_{0},\check{x}_{t}))]]$ $\displaystyle\leqslant c^{\prime}(R_{t}^{2}\lVert x_{t}\rVert_{L_{4}(p_{t})}^{ 2}+\sigma_{t}^{-2}D)\cdot\sqrt{\delta/n},$ $$

from which the claim follows.
∎

The second result proves uniform convergence over truncated
inputs.

###### Proposition C.4 .

Fix $\delta\in(0,1)$.
Define the truncated random vectors
$(\check{x}_{0},\check{x}_{t})\sim\nu_{\delta/n}$ (cf. (C.1)),
and let $\check{D}_{t}\sim\nu_{\delta/n}^{\otimes n}$.
For some $R_{t}\geqslant 1$, define $\mathscr{F}_{t}:=\{s:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}\mid\lVert s\rVert_{
\mathcal{F}_{1}}\leqslant R_{t}\}$.
For all $\varepsilon\in(0,1]$, we have that:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f; \delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]$ $\displaystyle\leqslant\tilde{O}(1)(1+\varepsilon^{-1})\left[\frac{R_{t}^{2} \check{\mu}_{t,x}^{2}(\delta/n)D+\check{\mu}_{t,q}^{2}(\delta/n)}{n}\right]+O( 1)\frac{R_{t}^{2}\lVert x_{t}\rVert^{2}_{L_{4}(p_{t})}+D/\sigma_{t}^{2}}{n^{2}}.$ $$

###### Proof.

Let $\check{\mu}_{t,x}:=\check{\mu}_{t,x}(\delta/n)$
and similarly $\check{\mu}_{t,q}:=\check{\mu}_{t,q}(\delta/n)$.
We first observe that the following holds almost surely:

$$ $\displaystyle\lVert f(\check{x}_{t})-\nabla\log q_{t}(\check{x}_{t}\mid\check{ x}_{0})\rVert$ $\displaystyle\leqslant R_{t}\lVert\check{x}_{t}\rVert+\lVert\nabla\log q_{t}( \check{x}_{t}\mid\check{x}_{0})\rVert$ $\displaystyle\leqslant R_{t}\check{\mu}_{t,x}+\check{\mu}_{t,q}=:B_{\mathcal{H }}.$ $$

We consider the hypothesis of functions:

$$ $\displaystyle\mathcal{H}:=\{(x,\bar{x})\mapsto\lVert f(\bar{x})-\nabla\log q_{ t}(\bar{x}\mid x)\rVert\mid f\in\mathscr{F}_{t}\},$ $$

defined over the support $\check{\mathcal{Z}}:=\mathrm{supp}((\check{x}_{0},\check{x}_{t}))$, and
coupled with the loss function $\phi(z)=z^{2}$, which is $2$-smooth.
From Srebro et al. [, Theorem 1],
we have with probability at least $1-\delta$ over $\check{D}_{t}$,
for all $h\in\mathcal{H}$:(^9^99Note that we ignore the labels $y$ in the setup of Srebro et al. [, Theorem 1], as they are immaterial.)

$$ $\displaystyle\mathbb{E}[\phi(h(\check{x}_{0},\check{x}_{t}))]\leqslant(1+ \varepsilon)\frac{1}{n}\sum_{i=1}^{n}\phi(h(\check{x}_{0}^{i},\check{x}_{t}^{i }))+(1+\varepsilon^{-1})c\left[\log^{3}{n}\cdot\mathfrak{R}^{2}_{n}(\mathcal{H })+\frac{B^{2}_{\mathcal{H}}\log(1/\delta)}{n}\right],$ (C.8) $$

where $c>0$ is a universal constant, and
$\mathfrak{R}_{n}(\mathcal{H})$ denotes the Rademacher complexity of $\mathcal{H}$:

$$ $\displaystyle\mathfrak{R}_{n}(\mathcal{H}):=\sup_{z_{1:n}\subset\check{ \mathcal{Z}}}\mathbb{E}_{\varepsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\left| \sum_{i=1}^{n}h(z_{i})\varepsilon_{i}\right|.$ $$

We now bound this Rademacher complexity term.
Let $\mathcal{G}$ denote the shifted function class:

$$ $\displaystyle\mathcal{G}:=\{(x,\bar{x})\mapsto f(\bar{x})-\nabla\log q_{t}( \bar{x}\mid x)\mid f\in\mathscr{F}_{t}\}.$ $$

Letting $g_{0}\in\mathcal{G}$ and $z_{i}=(x_{i},\bar{x}_{i})\in\check{Z}$ for $i\in[n]$ be arbitrary, we have:

$$ $\displaystyle\mathbb{E}_{\varepsilon}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n }h(z_{i})\varepsilon_{i}\right|$ $\displaystyle=\mathbb{E}_{\varepsilon}\sup_{g\in\mathcal{G}}\left|\sum_{i=1}^{ n}\varepsilon_{i}\lVert g(z_{i})\rVert\right|$ $\displaystyle\leqslant\mathbb{E}_{\varepsilon}\sup_{g\in\mathcal{G}}\left|\sum _{i=1}^{n}\varepsilon_{i}(\lVert g(z_{i})\rVert-\lVert g_{0}(z_{i})\rVert) \right|+\mathbb{E}\left|\sum_{i=1}^{n}\varepsilon_{i}\lVert g_{0}(z_{i})\rVert\right|$ $\displaystyle\leqslant\mathbb{E}_{\varepsilon}\sup_{g\in\mathcal{G}}\left|\sum _{i=1}^{n}\varepsilon_{i}(\lVert g(z_{i})\rVert-\lVert g_{0}(z_{i})\rVert) \right|+\sqrt{\sum_{i=1}^{n}\lVert g_{0}(z_{i})\rVert^{2}}$ Jensen’s inequality $\displaystyle\leqslant\mathbb{E}_{\varepsilon}\sup_{g,g^{\prime}\in\mathcal{G} }\left|\sum_{i=1}^{n}\varepsilon_{i}(\lVert g(z_{i})\rVert-\lVert g^{\prime}(z _{i})\rVert)\right|+\sqrt{\sum_{i=1}^{n}\lVert g_{0}(z_{i})\rVert^{2}}$ since $g_{0}\in\mathcal{G}$ $\displaystyle=\mathbb{E}_{\varepsilon}\sup_{g,g^{\prime}\in\mathcal{G}}\sum_{i =1}^{n}\varepsilon_{i}(\lVert g(z_{i})\rVert-\lVert g^{\prime}(z_{i})\rVert)+ \sqrt{\sum_{i=1}^{n}\lVert g_{0}(z_{i})\rVert^{2}}$ since $\mathcal{G}-\mathcal{G}$ is symmetric $\displaystyle\leqslant 2\mathbb{E}_{\varepsilon}\sup_{g\in\mathcal{G}}\sum_{i= 1}^{n}\varepsilon_{i}\lVert g(z_{i})\rVert+\sqrt{n}B_{\mathcal{H}}.$ $$

Next, we proceed with Maurer [, Corollary 4],
which allows to bound, for Rademacher random *vectors* $\gamma_{i}\in\{\pm 1\}^{D}$,

$$ $\displaystyle\mathbb{E}_{\varepsilon}\sup_{g\in\mathcal{G}}\sum_{i=1}^{n} \varepsilon_{i}\lVert g(z_{i})\rVert$ $\displaystyle\leqslant\sqrt{2}\mathbb{E}_{\gamma}\sup_{g\in\mathcal{G}}\sum_{i =1}^{n}\langle\gamma_{i},g(z_{i})\rangle$ $\displaystyle=\sqrt{2}\mathbb{E}_{\gamma}\sup_{f\in\mathscr{F}_{t}}\sum_{i=1}^ {n}\langle\gamma_{i},f(\bar{x_{i}})\rangle$ $\displaystyle\lesssim R_{t}\check{\mu}_{t,x}\sqrt{Dn},$ $$

where the last inequality uses A.9.
Putting the terms together,

$$ $\displaystyle\mathfrak{R}_{n}(\mathcal{H})\lesssim(R_{t}\check{\mu}_{t,x}\sqrt {D}+B_{\mathcal{H}})\frac{1}{\sqrt{n}}\lesssim(R_{t}\check{\mu}_{t,x}\sqrt{D}+ \check{\mu}_{t,q})\frac{1}{\sqrt{n}}.$ $$

From (C.8),
with probability at least $1-1/n^{4}$,
for all $h\in\mathcal{H}$:

$$ $\displaystyle\mathbb{E}[\phi(h(\check{x}_{0},\check{x}_{t}))]$ $\displaystyle\leqslant(1+\varepsilon)\frac{1}{n}\sum_{i=1}^{n}\phi(h(\check{x} _{0}^{i},\check{x}_{t}^{i}))+(1+\varepsilon^{-1})c\log^{3}{n}\left[\frac{R_{t} ^{2}\check{\mu}_{t,x}^{2}D+\check{\mu}_{t,q}^{2}}{n}\right].$ $$

That is, with probability at least $1-1/n^{4}$,

$$ $\displaystyle\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f;\delta/n)-(1 +\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]\leqslant\tilde{ O}(1)(1+\varepsilon^{-1})\left[\frac{R_{t}^{2}\check{\mu}_{t,x}^{2}D+\check{ \mu}_{t,q}^{2}}{n}\right].$ $$

Call this event $\mathcal{E}^{\prime}$.
We have that:

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f; \delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]$ $\displaystyle=\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f; \delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})] \mathbf{1}\{\mathcal{E}^{\prime}\}+\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check {\mathcal{L}}_{t}(f;\delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{ \mathcal{D}}_{t})]\mathbf{1}\{(\mathcal{E}^{\prime})^{c}\}$ $\displaystyle\lesssim\tilde{O}(1)(1+\varepsilon^{-1})\left[\frac{R_{t}^{2} \check{\mu}_{t,x}^{2}D+\check{\mu}_{t,q}^{2}}{n}\right]+\frac{1}{n^{2}}\sqrt{ \mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f;\delta/n)-(1+ \varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]^{2}}.$ $$

To finish the proof, we observe that:

$$ $\displaystyle\check{\mathcal{L}}_{t}(f;\delta/n)$ $\displaystyle=\mathbb{E}_{(\check{x}_{0},\check{x}_{t})\sim\nu_{\delta/n}} \lVert f(\check{x}_{t})-\nabla\log q_{t}(\check{x}_{t}\mid\check{x}_{0})\rVert ^{2}$ $\displaystyle\leqslant 2\mathbb{E}\lVert f(\check{x}_{t})\rVert^{2}+2\mathbb{E }\lVert\nabla\log q_{t}(\check{x}_{t}\mid\check{x}_{0})\rVert^{2}$ $\displaystyle\leqslant 2R_{t}^{2}\mathbb{E}\lVert\check{x}_{t}\rVert^{2}+2 \mathbb{E}\lVert(\check{x}_{t}-m_{t}\check{x}_{0})/\sigma_{t}^{2}\rVert^{2}$ $\displaystyle\leqslant 2R_{t}^{2}\mathbb{E}\lVert x_{t}\rVert^{2}+2\mathbb{E} \lVert(x_{t}-m_{t}x_{0})/\sigma_{t}^{2}\rVert^{2}$ $\displaystyle=2R_{t}^{2}\mathbb{E}\lVert x_{t}\rVert^{2}+2D/\sigma_{t}^{2}.$ $$

On the other hand, from (C.7),

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}\check{\mathcal{L}}_{t}^{2}(f ;\check{\mathcal{D}}_{t})\lesssim R_{t}^{4}\mathbb{E}\lVert x_{t}\rVert^{4}+ \sigma_{t}^{-4}D^{2}.$ $$

Hence, combining these bounds together,

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\check{\mathcal{L}}_{t}(f; \delta/n)-(1+\varepsilon)\hat{\mathcal{L}}_{t}(f;\check{\mathcal{D}}_{t})]$ $\displaystyle\lesssim\tilde{O}(1)(1+\varepsilon^{-1})\left[\frac{R_{t}^{2} \check{\mu}_{t,x}^{2}D+\check{\mu}_{t,q}^{2}}{n}\right]+\frac{R_{t}^{2}\lVert x _{t}\rVert^{2}_{L_{4}(p_{t})}+D/\sigma_{t}^{2}}{n^{2}}.$ $$

∎

###### Proposition C.1 (Basic generalization inequality) .

###### Proof.

###### Lemma C.2 .

###### Proposition C.3 .

###### Proof.

###### Proposition C.4 .

###### Proof.

## Appendix D Analysis of subspace structure ( Section 3.1 )

We now specialize the previous approximation and uniform convergence results to the subspace structure setting.

###### Proposition D.1 .

Fix an $M\geqslant 1$.
For any $\varepsilon\in(0,\bar{L}M/2)$, there exists an $f_{\varepsilon}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ such that
$\sup_{z\in B_{2}(d,M)}\lVert f_{\varepsilon}(z)-\nabla\log\pi_{t}(z)\rVert\leqslant\varepsilon$,
and

$$ $\displaystyle\lVert f_{\varepsilon}\rVert_{\mathcal{F}_{1}}\leqslant R_{ \mathrm{lin}}(\varepsilon,M):=O_{d}(1)(\bar{L}M)^{(d+3)/2}\varepsilon^{-(d+1)/ 2}\log^{(d+1)/2}(\bar{L}M/\varepsilon).$ (D.1) $$

###### Proof.

We will invoke 4.4.
To do this, we first observe for any $z\in B_{2}(d,M)$,
using A.4,

$$ $\displaystyle\lVert\nabla\log\pi_{t}(z)\rVert\leqslant\bar{L}(1+\lVert z\rVert )\leqslant 2\bar{L}M.$ $$

On the other hand, we know that $\nabla\log\pi_{t}$ is $L$-Lipschitz.
The claim now follows from 4.4.
∎

Our next task is to upgrade the previous result to an approximation result for the ambient score $\nabla\log p_{t}$, using B.1.

###### Proposition D.2 .

Fix an $\varepsilon\in(0,1)$.
There exists an $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ such that:

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant\tilde{O}_{d}(1)( \bar{L}(\mu_{t,z}\vee\beta))^{(d+3)/2}\varepsilon^{-(d+1)/2}+2(D-d)/\sigma_{t} ^{2},\quad\lVert\hat{s}-\nabla\log p_{t}\rVert_{L_{2}(p_{t})}\leqslant\varepsilon.$ (D.2) $$

###### Proof.

Define

$$ $\displaystyle M(\delta):=\left\{\lVert U^{\mathsf{T}}x_{t}\rVert\leqslant A_{ \delta}\right\},\quad A_{\delta}:=c_{0}(\mu_{t,z}+\beta\sqrt{\log(1/\delta)}).$ $$

We note that the condition
$\mathbb{P}\{x_{t}\in M(\delta)\}\geqslant 1-\delta$ holds
for an appropriate choice of $c_{0}$.

Now, given $\varepsilon,\delta\in(0,1)$,
from D.1
there exists $\hat{h}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ such that:

$$ $\lVert\hat{h}\rVert_{\mathcal{F}_{1}}\leqslant R_{\mathrm{lin}}(\varepsilon,A_ {\delta}),\quad\sup_{z\in B_{2}(d,A_{\delta})}\lVert\hat{h}(z)-\nabla\log\pi_{ t}(z)\rVert\leqslant\varepsilon.$ $$

Embed $\hat{h}$ to a function $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ by:

$$ $\hat{s}(x)=U\hat{h}(U^{\mathsf{T}}x)-\frac{1}{\sigma_{t}^{2}}(I-UU^{\mathsf{T} })x,$ $$

and observe that (cf. 4.1):

$$ $\displaystyle\sup_{x\in M(\delta)}\lVert\hat{s}(x)-s_{\star}(x)\rVert$ $\displaystyle=\sup_{x\in M(\delta)}\lVert U\hat{h}(U^{\mathsf{T}}x)-U\nabla \log\pi_{t}(U^{\mathsf{T}}x)\rVert$ $\displaystyle\leqslant\sup_{x\in M(\delta)}\lVert\hat{h}(U^{\mathsf{T}}x)- \nabla\log\pi_{t}(U^{\mathsf{T}}x)\rVert$ $\displaystyle\leqslant\sup_{z\in B_{2}(d,A_{\delta})}\lVert\hat{h}(z)-\nabla \log\pi_{t}(z)\rVert$ $\displaystyle\leqslant\varepsilon.$ $$

Next, we bound the $\mathcal{F}_{1}$-norm of $\hat{s}$.
To do this, we first bound the $\mathcal{F}_{1}$-norm of
$x\mapsto(I-UU^{\mathsf{T}})x$ by
representing it by the following
sum of Dirac masses

$$ $\sum_{i=1}^{D-d}\delta_{(u_{i},u_{i})}+\delta_{(-u_{i},-u_{i})},$ $$

and hence
$\lVert x\mapsto(I-UU^{\mathsf{T}})x\rVert_{\mathcal{F}_{1}}\leqslant 2(D-d)$.
Next, recall by 4.3 that
$\lVert x\mapsto U\hat{h}(U^{\mathsf{T}}x)\rVert_{\mathcal{F}_{1}}=\lVert h
\rVert_{\mathcal{F}_{1}}$.
Combining these results,

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}$ $\displaystyle\leqslant\lVert x\mapsto U\hat{h}(U^{\mathsf{T}}x)\rVert_{ \mathcal{F}_{1}}+\frac{1}{\sigma_{t}^{2}}\lVert x\mapsto(I-UU^{\mathsf{T}})x \rVert_{\mathcal{F}_{1}}$ $\displaystyle\leqslant\lVert\hat{h}\rVert_{\mathcal{F}_{1}}+\frac{2}{\sigma_{t }^{2}}(D-d)\leqslant R_{\mathrm{lin}}(\varepsilon,A_{\delta})+\frac{2}{\sigma_ {t}^{2}}(D-d)=:R(\varepsilon,\delta).$ (D.3) $$

That is, we have shown that
for $\varepsilon>0$ and $\delta\in(0,1)$,
there exists a $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ such that:

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant R(\varepsilon, \delta),\quad\sup_{x\in M(\delta)}\lVert\hat{s}(x)-\nabla\log p_{t}(x)\rVert \leqslant\varepsilon.$ $$

This verifies condition (B.1) of B.1.
We now need to solve for a $\delta_{\star}$ which satisfies the conditions listed in (B.2).
By several applications of A.7,
the conditions listed (B.2) are
satisfied with a $\delta_{\star}\in(0,1)$ satisfying:

$$ $\log(1/\delta_{\star})\leqslant O_{d}(1)\log\left(\frac{\bar{L}D\mu_{t,x}\beta }{\varepsilon\sigma_{t}}\right).$ $$

Since we do not track the exact form of the leading $O_{d}(1)$ constant, we skip the specific calculations.
The result now follows from
B.1 after estimating $R(\varepsilon/2,\delta_{\star})$. First, we bound,

$$ $\displaystyle A_{\delta_{\star}}=c_{0}(\mu_{t,z}+\beta\sqrt{\log(1/\delta_{ \star})})=\tilde{O}_{d}(1)(\mu_{t,z}\vee\beta).$ $$

Hence,

$$ $\displaystyle R(\varepsilon/2,\delta_{\star})\leqslant\tilde{O}_{d}(1)(\bar{L} (\mu_{t,z}\vee\beta))^{(d+3)/2}\varepsilon^{-(d+1)/2}.$ $$

Therefore, the result follows.
∎

Now we have the tools in place to prove 3.3,
our main score estimation result for this section.
See 3.3

###### Proof.

First, by D.2,
we know if we set $R_{t}$ to be

$$ $R_{t}=\tilde{O}_{d}(1)(\bar{L}(\mu_{t,z}\vee\beta))^{(d+3)/2}\varepsilon^{-(d+ 1)/2}+2(D-d)/\sigma_{t}^{2},$ $$

then, we have $\inf_{s\in\mathscr{F}_{t}}\mathcal{L}_{t}(s)\leqslant\varepsilon^{2}$.

Now we need to apply C.2.
To do this, we need to define our auxiliary truncated
random vectors (cf. (C.1)).
We choose the definition:

$$ $\displaystyle\mathcal{E}_{x}(\delta):=\{\lVert z_{0}\rVert\leqslant\mu_{0}+ \beta\sqrt{2\log(2/\delta)},\,\,\lVert w\rVert\leqslant\sqrt{D}+\sqrt{2\log(2/ \delta)}\},$ (D.4) $$

which by sub-Gaussian concentration followed by a union bound satisfies $\mathbb{P}\{\mathcal{E}_{x}(\delta)\}\geqslant 1-\delta$.
Note that under this definition of $\mathcal{E}_{x}(\delta)$, we can take:

$$ $\displaystyle\check{\mu}_{t,x}(\delta)\lesssim\mu_{t,x}+\beta\sqrt{\log(1/ \delta)},\quad\check{\mu}_{t,q}(\delta)\lesssim\sigma_{t}^{-1}(\sqrt{D}+\sqrt{ \log(1/\delta)}).$ (D.5) $$

By applying C.2, we obtain for $\gamma\in(0,1)$,

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-(1+\gamma )\hat{\mathcal{L}}_{t}(f)]\leqslant\tilde{O}(1)(1+\gamma^{-1})\frac{D}{n}\left [R_{t}^{2}(\mu_{t,x}\vee\beta)^{2}+1/\sigma_{t}^{2}\right].$ $$

By the basic inequality C.1,

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})]$ $\displaystyle\leqslant 2\varepsilon^{2}+\tilde{O}_{d}(\gamma^{-1})\frac{D}{n}( \bar{L}(\mu_{t,z}\vee\beta))^{d+3}\varepsilon^{-(d+1)}(\mu_{t,x}\vee\beta)^{2}$ $\displaystyle\qquad+\tilde{O}_{d}(\gamma^{-1})\frac{D^{2}}{n\sigma_{t}^{4}}( \mu_{t,x}\vee\beta)^{2}+\gamma\cdot C_{t}.$ $$

We now optimize this expression over both $\varepsilon,\gamma\in(0,1)$.
We first optimize both expressions ignoring the constraint that $\varepsilon,\gamma<1$.
First, optimizing over $\gamma$, we set

$$ $\displaystyle\gamma=\tilde{O}_{d}(1)\sqrt{\frac{1}{C_{t}}\left[\frac{D}{n}( \bar{L}(\mu_{t,z}\vee\beta))^{d+3}\varepsilon^{-(d+1)}(\mu_{t,x}\vee\beta)^{2} +\frac{D^{2}}{n\sigma_{t}^{4}}(\mu_{t,x}\vee\beta)^{2}\right]},$ $$

and from this we obtain:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})]$ $\displaystyle\leqslant 2\varepsilon^{2}+\sqrt{\tilde{O}_{d}(1)\frac{C_{t}D}{n} (\bar{L}(\mu_{t,z}\vee\beta))^{d+3}\varepsilon^{-(d+1)}(\mu_{t,x}\vee\beta)^{2 }}+\sqrt{\tilde{O}_{d}(1)\frac{C_{t}D^{2}}{n\sigma_{t}^{4}}(\mu_{t,x}\vee\beta )^{2}}.$ $$

Now optimizing over $\varepsilon$, we set

$$ $\displaystyle\varepsilon=\tilde{O}_{d}(1)\left[\frac{C_{t}D}{n}(\bar{L}(\mu_{t ,z}\vee\beta))^{d+3}(\mu_{t,x}\vee\beta)^{2}\right]^{1/(d+5)},$ $$

and obtain:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})] \leqslant\tilde{O}_{d}(1)\left[\frac{C_{t}D}{n}(\bar{L}(\mu_{t,z}\vee\beta))^{ d+3}(\mu_{t,x}\vee\beta)^{2}\right]^{2/(d+5)}+\tilde{O}_{d}(1)\sqrt{\frac{C_{t }D^{2}}{n\sigma_{t}^{4}}(\mu_{t,x}\vee\beta)^{2}}.$ $$

The proof concludes by setting $n$ large enough so that both $\varepsilon,\gamma<1$.
∎

We now restate and prove 3.4,
our main end-to-end bound for the latent subspace case.
See 3.4

###### Proof.

Using the bounds
$\mu_{t,z}\leqslant\mu_{z}$ and
$\mu_{t,x}\leqslant\mu_{x}$,
from 3.3
we have that the following ERM bound holds for all $t\in[0,T]$:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})] \leqslant\tilde{O}_{d}(1)\left[\frac{D^{2}}{n\sigma_{t}^{2}}(\bar{L}(\mu_{z} \vee\beta))^{d+3}(\mu_{x}^{2}\vee\beta^{2})\right]^{2/(d+5)}+\tilde{O}_{d}(1) \sqrt{\frac{D^{3}}{n\sigma_{t}^{6}}(\mu_{x}^{2}\vee\beta^{2})}.$ $$

Furthermore, since $e^{-x}\leqslant 1-x/2$ for $x\in[0,1.59]$,
then
for $t\leqslant 0.795$ we have

$$ $\sigma_{t}^{2}=1-\exp(-2t)\geqslant t\Longrightarrow 1/\sigma_{t}^{2}\leqslant 1 /t.$ $$

On the other hand, for
$t>0.795$, we have the bound

$$ $\displaystyle\sigma_{t}^{2}=1-\exp(-2t)\geqslant 1-\exp(-1.59)\geqslant 0.796 \Longrightarrow 1/\sigma_{t}^{2}\lesssim 1.$ $$

Combining these inequalities we have that $1/\sigma_{t}^{2}\leqslant 1/\sigma_{\zeta}^{2}\lesssim 1/\zeta$ for all $t\geqslant\zeta$.

Hence, using the
choice of $T$, $N$ from (3.13) and $\{t_{i}\}_{i=0}^{N}$ as
specified in A.2,
we have that:

$$ $\displaystyle\sum_{k=0}^{N-1}\gamma_{k}\mathbb{E}_{p_{T-t_{k}}}\lVert\hat{f}_{ T-t_{k}}-\nabla\log p_{T-t_{k}}\rVert^{2}$ $\displaystyle\lesssim T\left[\tilde{O}_{d}(1)\left[\frac{D^{2}}{n\zeta}(\bar{L }(\mu_{z}\vee\beta))^{d+3}(\mu_{x}^{2}\vee\beta^{2})\right]^{2/(d+5)}+\tilde{O }_{d}(1)\sqrt{\frac{D^{3}}{n\zeta^{3}}(\mu_{x}^{2}\vee\beta^{2})}\right]$ $\displaystyle\lesssim\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right) \left[\tilde{O}_{d}(1)\left[\frac{D^{2}}{n\zeta}(\bar{L}(\mu_{z}\vee\beta))^{d +3}(\mu_{x}^{2}\vee\beta^{2})\right]^{2/(d+5)}+\tilde{O}_{d}(1)\sqrt{\frac{D^{ 3}}{n\zeta^{3}}(\mu_{x}^{2}\vee\beta^{2})}\right].$ $$

Hence, in order to make $\varepsilon_{\mathrm{score}}^{2}\leqslant\varepsilon^{2}$, we need to take $n$ large enough such that
the following conditions hold:

$$ $\displaystyle\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)\tilde{O} _{d}(1)\left[\frac{D^{2}}{n\zeta}(\bar{L}(\mu_{z}\vee\beta))^{d+3}(\mu_{x}^{2} \vee\beta^{2})\right]^{2/(d+5)}$ $\displaystyle\lesssim\varepsilon^{2},$ $\displaystyle\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)\tilde{O} _{d}(1)\sqrt{\frac{D^{3}}{n\zeta^{3}}(\mu_{x}^{2}\vee\beta^{2})}$ $\displaystyle\lesssim\varepsilon^{2}.$ $$

Hence, we need to take $n$ satisfying:

$$ $\displaystyle n\geqslant\tilde{O}_{d}(1)\max\left\{\frac{D^{2}}{\zeta}(\bar{L} (\mu_{z}\vee\beta))^{d+3}(\mu_{x}^{2}\vee\beta^{2})\cdot\varepsilon^{-(d+5)}, \frac{D^{3}}{\zeta^{3}}(\mu_{x}^{2}\vee\beta^{2})\cdot\varepsilon^{-4}\right\}.$ $$

On the other hand we also need to take $n\geqslant n_{0}(\zeta)$
(cf. (3.11)).
The claim now follows.
∎

###### Proposition D.1 .

###### Proof.

###### Proposition D.2 .

###### Proof.

###### Proof.

###### Proof.

## Appendix E Analysis of independent components ( Section 3.2 )

We follow a very similar structure as in Appendix D.
We first start with an approximation result.

###### Proposition E.1 .

For an $M\geqslant 1$ and $i\in[K]$. For any $\varepsilon\in(0,\bar{L}_{i}M/2)$, there exists an $f_{\varepsilon}:\mathbb{R}^{d_{i}}\mapsto\mathbb{R}^{d_{i}}$ such that
$\sup_{z\in B_{2}(d_{i},M)}\lVert f_{\varepsilon}(z)-\nabla\log\pi_{t}^{(i)}(z)
\rVert\leqslant\varepsilon$, and

$$ $\displaystyle\lVert f_{\varepsilon}\rVert_{\mathcal{F}_{1}}\leqslant R_{ \mathrm{ind}}^{(i)}(\varepsilon,M):=O_{d}(1)(\bar{L}_{i}M)^{(d+3)/2} \varepsilon^{-(d+1)/2}\log^{(d+1)/2}(\bar{L}_{i}M/\varepsilon).$ (E.1) $$

###### Proof.

The proof is nearly identical to D.1,
and therefore we omit the details.
∎

Next, we upgrade the previous approximation result
to approximation in $L_{2}(p_{t})$.

###### Proposition E.2 .

Fix $\varepsilon_{1},\dots,\varepsilon_{K}\in(0,1)$.
There exists
an $\hat{s}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ satisfying:

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant\sum_{i=1}^{K} \tilde{O}_{d_{i}}(1)(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta))^{(d_{i}+3)/2} \varepsilon_{i}^{-(d_{i}+1)/2},\quad\lVert\hat{s}-\nabla\log p_{t}\rVert_{L_{2 }(p_{t})}\leqslant\sqrt{\sum_{i=1}^{K}\varepsilon_{i}^{2}}.$ $$

###### Proof.

Recall that $P_{i}\in\mathbb{R}^{d_{i}\times D}$ selects the coordinates
corresponding to the $i$-th variable group (cf. 4.2).
Define the sets $M^{(i)}(\delta)$ as:

$$ $\displaystyle M^{(i)}(\delta):=\left\{x\in\mathbb{R}^{D}\mid\lVert P_{i}U^{ \mathsf{T}}x\rVert\leqslant A_{\delta}^{(i)}\right\},\quad A_{\delta}^{(i)}:=c _{0}(\mu_{t,x}^{(i)}+\beta_{i}\sqrt{\log(1/\delta)}),\quad i\in[K].$ $$

With appropriate choice of $c_{0}$, we have that
$\mathbb{P}_{x_{t}\sim p_{t}}\{x_{t}\in M^{(i)}(\delta)\}\geqslant 1-\delta$.

Given $\varepsilon,\delta\in(0,1)$,
from E.1,
there exists $\hat{h}_{i}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ for $i\in[K]$ such that:

$$ $\lVert\hat{h}_{i}\rVert_{\mathcal{F}_{1}}\leqslant R_{\mathrm{ind}}^{(i)}( \varepsilon,A_{\delta}^{(i)}),\quad\sup_{z\in B_{2}(d,A_{\delta}^{(i)})}\lVert \hat{h}_{i}(z)-\nabla\log\pi_{t}^{(i)}(z)\rVert\leqslant\varepsilon.$ $$

Now define $\hat{s}_{i}:=UP_{i}^{\mathsf{T}}\hat{h}_{i}(P_{i}U^{\mathsf{T}}x)$.
Observe that:

$$ $\displaystyle\sup_{x\in M^{(i)}(\delta)}\lVert\hat{s}_{i}(x)-UP_{i}^{\mathsf{T }}\nabla\log\pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x)\rVert$ $\displaystyle\leqslant\sup_{x\in M^{(i)}(\delta)}\lVert\hat{h}_{i}(P_{i}U^{ \mathsf{T}}x)-\nabla\log\pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x)\rVert$ $\displaystyle\leqslant\sup_{z\in B_{2}(d_{i},A_{\delta}^{(i)})}\lVert\hat{h}_{ i}(z)-\nabla\log\pi_{t}^{(i)}(z)\rVert$ $\displaystyle\leqslant\varepsilon.$ $$

Next, observe that $\lVert\hat{s}_{i}\rVert_{\mathcal{F}_{1}}=\lVert\hat{h}_{i}\rVert_{\mathcal{F}
_{1}}$ by 4.3.
Invoking B.1
as is done in the proof of D.2,
we have that for all $i\in[K]$,
$\lVert\hat{s}_{i}-UP_{i}^{\mathsf{T}}\nabla\log\pi_{t}^{(i)}(P_{i}U^{\mathsf{T
}}\cdot)\rVert_{L_{2}(p_{t})}\leqslant\varepsilon_{i}$ and

$$ $\displaystyle\lVert\hat{s}_{i}\rVert_{\mathcal{F}_{1}}\leqslant\tilde{O}_{d_{i }}(1)(\bar{L}_{i}(\mu_{t,z}^{(i)}\vee\beta_{i}))^{(d_{i}+3)/2}\varepsilon_{i}^ {-(d+1)/2}.$ $$

Recall by 4.2 we have:

$$ $\displaystyle\nabla\log p_{t}(x)=\sum_{i=1}^{K}UP_{i}^{\mathsf{T}}\nabla\log \pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x).$ $$

Hence, setting $\hat{s}=\sum_{i=1}^{K}\hat{s}_{i}$, we have that

$$ $\displaystyle\lVert\hat{s}-\nabla\log p_{t}\rVert_{L_{2}(p_{t})}^{2}$ $\displaystyle=\mathbb{E}\left\lVert\sum_{i=1}^{K}UP_{i}^{\mathsf{T}}(\hat{h}_{ i}(P_{i}U^{\mathsf{T}}x_{t})-\nabla\log\pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x_{t}) )\right\rVert^{2}$ $\displaystyle=\sum_{i=1}^{K}\mathbb{E}\lVert UP_{i}^{\mathsf{T}}(\hat{h}_{i}(P _{i}U^{\mathsf{T}}x_{t})-\nabla\log\pi_{t}^{(i)}(P_{i}U^{\mathsf{T}}x_{t})) \rVert^{2}$ since $P_{j}P_{i}^{\mathsf{T}}=0$ for $i\neq j$ $\displaystyle=\sum_{i=1}^{K}\lVert\hat{s}_{i}-UP_{i}^{\mathsf{T}}\nabla\log\pi _{t}^{(i)}(P_{i}U^{\mathsf{T}}\cdot)\rVert_{L_{2}(p_{t})}^{2}$ $\displaystyle\leqslant\sum_{i=1}^{K}\varepsilon_{i}^{2}.$ $$

Furthermore,

$$ $\displaystyle\lVert\hat{s}\rVert_{\mathcal{F}_{1}}\leqslant\sum_{i=1}^{K} \lVert\hat{s}_{i}\rVert_{\mathcal{F}_{1}}\leqslant\sum_{i=1}^{K}\tilde{O}_{d_{ i}}(1)(\bar{L}_{i}(\mu_{t,z}^{(i)}\vee\beta_{i}))^{(d_{i}+3)/2}\varepsilon_{i} ^{-(d+1)/2}.$ $$

∎

We now prove 3.7, our
score estimation result for the independent components setting.
See 3.7

###### Proof.

Here we minic the proof of 3.3.
First, by E.2,
we know if we set $R_{t}$ as

$$ $R_{t}=\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_ {i}))^{(d_{i}+3)/2}\varepsilon_{i}^{-(d_{i}+1)/2},$ $$

then, we have $\inf_{s\in\mathscr{F}_{t}}\mathcal{L}_{t}(s)\leqslant\sum_{i=1}^{K}\varepsilon
_{i}^{2}$.

Our next step is to apply C.2.
To do this we need to define auxiliary truncated random vectors
(cf. (C.1)). In this case, we use the definition:

$$ $\displaystyle\mathcal{E}_{x}(\delta):=\bigcap_{i\in[K]}\{\lVert z_{0}^{(i)} \rVert\leqslant\mu_{0}^{(i)}+\beta_{i}\sqrt{2\log(2K/\delta)}\}\cap\{\lVert w \rVert\leqslant\sqrt{D}+\sqrt{2\log(2/\delta)}\},$ (E.2) $$

which satisfies $\mathbb{P}\{\mathcal{E}_{x}(\delta)\}\geqslant 1-\delta$.
We have

$$ $\displaystyle\check{\mu}_{t,x}(\delta)\lesssim\mu_{t,x}+\beta\sqrt{\log(K/ \delta)},\quad\check{\mu}_{t,q}(\delta)\lesssim\sigma_{t}^{-1}(\sqrt{D}+\sqrt{ \log(1/\delta)}).$ $$

By applying C.2, we obtain for $\gamma\in(0,1)$,

$$ $\displaystyle\mathbb{E}\sup_{f\in\mathscr{F}_{t}}[\mathcal{L}_{t}(f)-(1+\gamma )\hat{\mathcal{L}}_{t}(f)]$ $\displaystyle\leqslant\tilde{O}(1)\gamma^{-1}\frac{D}{n}\left[R_{t}^{2}(\mu_{t ,x}\vee\beta)^{2}+1/\sigma_{t}^{2}\right]$ $\displaystyle\leqslant\gamma^{-1}\frac{DK}{n}\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1 )(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3}\varepsilon_{i}^{-(d_{i} +1)}(\mu_{t,x}\vee\beta)^{2}+\tilde{O}(1)\frac{D}{\gamma n\sigma_{t}^{2}}$ $$

By the basic inequality C.1,

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})]$ $\displaystyle\leqslant 2\sum_{i=1}^{K}\varepsilon_{i}^{2}+\gamma^{-1}\frac{DK} {n}\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i} ))^{d_{i}+3}\varepsilon_{i}^{-(d_{i}+1)}(\mu_{t,x}\vee\beta)^{2}$ $\displaystyle\qquad+\tilde{O}(1)\frac{D}{\gamma n\sigma_{t}^{2}}+\gamma\cdot C _{t}.$ $$

We now need to optimize over both $\varepsilon_{i},\gamma\in(0,1)$.
We first set $\gamma$ as:

$$ $\displaystyle\gamma=\sqrt{\frac{1}{C_{t}}\cdot\left[\frac{DK}{n}\sum_{i=1}^{K} \tilde{O}_{d_{i}}(1)(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3} \varepsilon_{i}^{-(d_{i}+1)}(\mu_{t,x}\vee\beta)^{2}+\tilde{O}(1)\frac{D}{n \sigma_{t}^{2}}\right]},$ $$

from which we obtain:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})] \leqslant 2\sum_{i=1}^{K}\varepsilon_{i}^{2}+\sum_{i=1}^{K}\sqrt{\tilde{O}_{d_ {i}}(1)\frac{C_{t}DK}{n}(\bar{L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3} \varepsilon_{i}^{-(d_{i}+1)}(\mu_{t,x}\vee\beta)^{2}}+\sqrt{\tilde{O}(1)\frac{ C_{t}D}{n\sigma_{t}^{2}}}.$ $$

We now set $\varepsilon_{i}$ as:

$$ $\displaystyle\varepsilon_{i}=\tilde{O}_{d_{i}}(1)\left[\frac{C_{t}DK}{n}(\bar{ L}_{i}(\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3}(\mu_{t,x}\vee\beta)^{2}\right] ^{1/(d_{i}+5)},$ $$

and obtain:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{f}_{t})] \leqslant\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)\left[\frac{C_{t}DK}{n}(\bar{L}_{i} (\mu_{t,x}^{(i)}\vee\beta_{i}))^{d_{i}+3}(\mu_{t,x}\vee\beta)^{2}\right]^{2/(d _{i}+5)}+\sqrt{\tilde{O}(1)\frac{C_{t}D}{n\sigma_{t}^{2}}}.$ $$

The proof concludes by setting $n$ large enough so that all of $\varepsilon_{i},\gamma<1$.
∎

Finally, we conclude with 3.8,
which provides an end-to-end sampling bound.
See 3.8

###### Proof.

We follow the proof of 3.4.
Using the bounds
$\mu_{t,x}^{(i)}\leqslant\mu_{x}^{(i)}$ and
$\mu_{t,x}\leqslant\mu_{x}$,
from 3.7
we have that the following ERM bound holds for all $t\in[0,T]$:

$$ $\displaystyle\mathbb{E}_{\mathcal{D}_{t}}[\mathcal{R}_{t}(\hat{s}_{t})] \leqslant\sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)\left[\frac{D^{2}K}{\sigma_{t}^{2}n }(\bar{L}_{i}(\mu_{x}^{(i)}\vee\beta_{i}))^{d_{i}+3}(\mu_{x}\vee\beta)^{2} \right]^{\frac{2}{d_{i}+5}}+\tilde{O}(1)\sqrt{\frac{D^{2}}{\sigma_{t}^{4}n}( \mu_{x}\vee\beta)^{2}}.$ $$

Recalling that $1/\sigma_{t}^{-2}\lesssim 1/\zeta$ for all $t\geqslant\zeta$, using the
choice of $T$, $N$ from (3.13) and $\{t_{i}\}_{i=0}^{N}$
we have that:

$$ $\displaystyle\sum_{k=0}^{N-1}\gamma_{k}\mathbb{E}_{p_{T-t_{k}}}\lVert\hat{f}_{ T-t_{k}}-\nabla\log p_{T-t_{k}}\rVert^{2}$ $\displaystyle\lesssim\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right) \sum_{i=1}^{K}\tilde{O}_{d_{i}}(1)\left[\frac{D^{2}K}{\zeta n}(\bar{L}_{i}(\mu _{x}^{(i)}\vee\beta_{i}))^{d_{i}+3}(\mu_{x}\vee\beta)^{2}\right]^{\frac{2}{d_{ i}+5}}$ $\displaystyle\qquad+\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right) \tilde{O}(1)\sqrt{\frac{D^{2}}{\zeta^{2}n}(\mu_{x}\vee\beta)^{2}}.$ $$

Hence, in order to make $\varepsilon_{\mathrm{score}}^{2}\leqslant\varepsilon^{2}$, we need to take $n$ large enough such that
the following conditions hold:

$$ $\displaystyle\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)\sum_{i=1 }^{K}\tilde{O}_{d_{i}}(1)\left[\frac{D^{2}K}{\zeta n}(\bar{L}_{i}(\mu_{x}^{(i) }\vee\beta_{i}))^{d_{i}+3}(\mu_{x}\vee\beta)^{2}\right]^{\frac{2}{d_{i}+5}}$ $\displaystyle\lesssim\varepsilon^{2},$ $\displaystyle\log\left(\frac{\sqrt{D}\vee\mu_{0}}{\varepsilon}\right)\tilde{O} (1)\sqrt{\frac{D^{2}}{\zeta^{2}n}(\mu_{x}\vee\beta)^{2}}$ $\displaystyle\lesssim\varepsilon^{2}.$ $$

Hence, we need to take $n$ satisfying:

$$ $\displaystyle n\geqslant(\mu_{x}\vee\beta)^{2}\max\left\{\max_{i\in[K]}\left\{ \frac{\tilde{O}_{d_{i}}(1)D^{2}}{\zeta}K^{(d_{i}+7)/2}(\bar{L}_{i}(\mu_{x}^{(i )}\vee\beta))^{d_{i}+3}\cdot\varepsilon^{-(d_{i}+5)}\right\},\frac{\tilde{O}(1 )D^{2}}{\zeta^{2}}\cdot\varepsilon^{-4}\right\}.$ $$

On the other hand we also need to take $n\geqslant n_{0}(\zeta)$
(cf. (3.17)).
The claim now follows.
∎

###### Proposition E.1 .

###### Proof.

###### Proposition E.2 .

###### Proof.

###### Proof.

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
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?
- Can the authors elaborate on the practical aspects of optimizing over Barron spaces?
- 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?
- 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?"
soundness: 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.
- 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.
- 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.
- 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.
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.
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.
- 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.
- 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.
- Minor typo: Line 315 (difference -> different?)

---

confidence: 1
contribution: 2
initial_rating: 6
presentation: 2
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)? 
- 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?
soundness: 2
strengths: The research presents a theoretically grounded approach to understanding the success of shallow diffusion networks, especially for low-dimensional structures in data.
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.
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.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Included in weakness.
soundness: 4
strengths: Solid paper with concrete mathematical analysis. The results in the paper could be of general mathematical interests for related fields.

The paper makes a meaningful step towards understanding the gap between curse of dimensionality in theory and no curse in reality.

The paper has nice connection with recent progress in diffusion sampling process.
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.
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.

The 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.

The 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.

Lack of analysis of the gradient descent training process of neural networks.

Lack 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.

Lack 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.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: **Questions:**

Q1: On line 42-44 you write: "these works leave open the difficulty of statistical estimation, and therefore raise 
the possibility that the sampling problem’s true difficulty is hidden in the complexity of learning."
Can you explain what you mean by this? 
Especially, "the difficulty of statistical estimation", do you mean how close the estimation can get to the true distribution?
And "the sampling problem’s true difficulty is hidden in the complexity of learning.", what do you mean by this?


Q2: Line 165: W.r.t. risk for score function being asymptotic to $n^{-2/(D+4)}$. Do you mean asymptotic as $n \to \infty$? 
(If yes, this could also be written in words, then you could avoid introducing the extra notation.)


Q3: 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 
for all their basis functions? And does that mean the F_1-norm is the smallest integral for the "largest" basis function? 


Q4: In line 180, you say that you only consider neuron parameters from the hypersphere. Is there a reason why this 
generalizes to neuron parameters chosen over the entire space? If there is, I would like that argument added. 
If there is not, I think you should add this assumption in the part of the introduction where you state your contribution.  
 

Q5: 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 
the logical "or", but that cannot be what you mean in this context. So what does it mean here? 


Q6: 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 
bound, and $n^{2/(d+5)} < n^{2/(d+4)}$ for $n > 1$. So how is $n^{2/(d+4)}$ a better bound? 


Q7: I don't recognize the denpendence on $\sigma_t$ which you mention in the remarks after theorem 3.3. Where do you have something 
bounded by $\sigma_t^{-4/(d+5)}$? 


Q8: In line 491 you mention your "truncation arguments", could you say what you mean by this? And maybe give a reference to where 
you make these arguments? 


**Suggestions:**

U1: Please make sure to use the full name and not an abbriviation the first time you mention a concept.
	For example: DDPM in line 66, ERM in line 74, DNN in line 90 and GD in line 97. 


U2: Please make sure to explain all the notation you use before you use it. If you feel it would take up too much space 
in the main paper, you can make a list of used notation in the appendix. 
Specific notation, where I cannot find an explanation in the paper: 
$\mathcal{F}_t$ in equation 3.7 (I am guessing this is the space of score functions), $\asymp$ in line 165, 
g cts in line 176 in the definition of the Total-Variation norm, the $\lor$ in line 231 and equation 3.10 and
Law(.) in last line of corollary 3.4. 
  

U3: I feel the title over-promises. "SHALLOW DIFFUSION NETWORKS PROVABLY LEARN HIDDEN LOW-DIMENSIONAL STRUCTURE"
sounds like it is _all_ shallow networks and _all_ hidden low-dimensional structures. Of course I understand 
if you feel the title would get too long if you add all the assumptions, so I would suggest finding a new title 
which is as short or shorter, and which does not make the result sound more general than it is. 


U4: Typo in line 189: Should be $B_2(r, d)$
soundness: 3
strengths: S1: Diffusion models are videly used, so theoretical work on them is highly relevant. 

S2: Going from needing a specific architecture to "only" needing the network to be infinitely wide to get a bound, is a step forward. 

S3: Corollary 3.4 and 3.8 give bounds on the KL-divergence between the true data distribution and that of the diffusion model, 
given enough training samples (and the extra assumptions) which is interesting.
summary: This theoretical work shows that for a neural network which is infinitely wide, and where neuron parameters come from the hypersphere, 
and there is one of two hidden latent structures in the data, then there is a bound on the emprical risk minimizer which only
depends on the dimension of the latent structure and not the dimension of the ambient space. 

If we denote the ambient dimension as D, the two hidden structures considered are 1) a linear combination of lower dimensional 
vectors (of dimension d << D) and 2) a linear combination of independent components all of lower dimension than the ambient 
space, but but where the sum of the dimensions of the components sum to D.
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 
the theory of machine learning, so I should be the target audience. See my questions and suggestions for places where clarification is 
needed.

Meta-review: The paper is a solid mathematical analysis of an interesting phenomenon and will be of interest to much of the community. Some complexities, such as very deep models and algorithmic aspects, have been simplified for the sake of theoretical results, but even without them, the contribution is well recognized. In addition, clarifications of the presentation made in the rebuttal should be appropriately reflected in order to appeal to a wider audience of the machine learning community.

Decision: Accept (Poster)