Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian distributions
Authors: Frank Cole
Yulong Lu
Venue: ICLR 2024 poster (2024)
Keywords: score-based generative models
Barron space
curse of dimensionality
Primary area: generative models
TL;DR: Score-based generative models can estimate an exponential tilting of the Gaussian distribution without the curse of dimensionality.

Abstract: While score-based generative models (SGMs) have achieved remarkable successes in enormous image generation tasks, their mathematical foundations are still limited. In this paper, we analyze the approximation and generalization of SGMs in learning a family of sub-Gaussian probability distributions. We introduce a measure of complexity for probability distributions in terms of their relative density with respect to the standard Gaussian measure. We prove that if the log-relative density can be locally approximated by a neural network whose parameters can be suitably bounded, then the distribution generated by empirical score matching approximates the target distribution in total variation with a dimension-independent rate. We illustrate our theory through examples, which include certain mixtures of Gaussians. An essential ingredient of our proof is to derive a dimension-free deep network approximation rate for the true score function associated to the forward process, which is interesting in its own right.

SCORE-BASED GENERATIVE MODELS BREAK THE CURSE OF DIMENSIONALITY IN LEARNING A FAMILY OF SUB- SUB-GAUSSIAN PROBABILITY DISTRIBUTIONS
Frank Cole
Yulong Lu
Department of Mathematics University of Minnesota Minneapolis, MN, 55414, USA {cole093 922e09322 32 @mm. edu
Department of Mathematics University Minnesota Minncapolis, MN, 55414, USA {yulonglu] umn edu
ABSTRACT
While score-based generative models (SGMs) have achieved remarkable suc- cesses enormous image generation tasks, their mathematical foundations are still limited. In this paper, we analyze the approximation and generalization of SGMs learning a family of sub-Gaussian probability distributions. We intro- duce notion of complexity for probability distributions in terms of their rel- ative density with respect to the standard Gaussian measure. We prove that if the log-relative density can be locally approximated by neural network whose parameters can suitably bounded, then the distribution generated by empiri- cal score matching approximates the target distribution in total variation with dimension-independeni rate. We illustrate our theory through examples, which include certain mixtures of Gaussians. An essential ingredient of our proof is derive dimension-fre -free deep neural network approximation rate for the true score function associated to the forward process, which interesting in its own right.
INTRODUCTION
Generative modeling is central task in modern machine learning, where the goal is to learn high dimensional probability distribution given a finite number of samples. Score-based generative models (SGMs)
et al. (2015); Song et al. (2021) recently arise novel family of generative models achieving remarkable empirical success in the generation of audio and images outperforming state-of-the-art generative models such as generative adversarial networks [Dhriwal and Nichol (2021). More recently, SGMs have proven effective in variety of applications such as natural language processing Austin al. (2021);
Yang al. (2022); Croitoru et al. (2023),
Savinov et al. (2021), computational physics Lee et al. (2023a); Jing et al. (2022), computer vision Amit al. (2021): Baranchuk al. (202T): Brempong al. (2022), and medical imaging Chung and Ye (2022). In addition to their own expressive power, SGMs can also help to understand and
improve other existing generative models, such as variational autoencoders Huang al. (2021) Luo
(022) and normalizing flows Gong and Li (202T))
SGMs are often implemented by a pair of diffusion processes, known as forward and backward pro- cesses. The forward process transforms given data into pure Gaussian noise, while the backward process turns the noises into approximate samples from the target distribution, thereby accomplish- ing generative modeling. The analytical form of the reverse process is unknown, since its parameters depend on the target distribution, which is only accessible through data; hence, the reverse process must be learned. This is made possible by the remarkable fact that the time reversal of diffusion process is again a diffusion process whose coefficients depend only on the target distribution via the score function, time-dependent vector field given by the gradient of the log-density of the forward

---

process. There exist well-studied techniques cast the estimation of the score function from data as a supervised learning problem Hyvärinen and Dayan (2055): Vincent (2011). which is crucial to the practical implementation of SGMs.
While SGMs have received significant attention from thcoretical viewpoints, there are still several barriers complete theoretical understanding. Recent results Chen et al. (2023a b): Benton et al. 2023) have shown that the distribution recovery error SGMs is essentially controlled by the estimation error of the score function, which is typically parameterized by neural network. While neural networks are known to be universal approximators for many classes of functions Cybenko [1899 Yarotsky (2017). the number of parameters of the neural network needed to approximate function to eπror é often scales like e where d is the dimension of the data. Such rates are of little practical significance for high dimensional problems, and thus the ability of neural networks to express the score function of a general probability distribution remains a mystery.
Nonetheless, SGMs have still exhibited great success in generating high-qualits samples from com- plex, high-dimensional data distributions. One salient reason for this is that, while the data itself may very high-dimensional, the score function of the noising process often possesses some in- trinsic structure that can be exploited by neural networks. The purpose of this article is to justify this intuition rigorously for a broad class of probability distributions. Specifically, we study the genera- tive power of SGMs for probability distributions which absolutely continuous with respect the standard Gaussian distribution. Such distributions admit a probability density function of the form
|=11² + [(x))
p(x) exp
where exp(f) Rd + R+ is the Radon-Nikodym derivative of with respect to the Gaussian distribution and Z is the normalization constant. This representation of the density has proven par- ticularly elucidating in the context of statistical learning and Bayesian inference, where the Gaussian component can model our subjective beliefs on the data. In this paper, we show that the expression for the density in Equation [ is also relevant SGMs, because the score function is related to the function / by tractable composition of functions. A central theme of this work is that if belongs low-complyxity function class, then the score function inherits similar low-complexity struc- ture. This enables deep neural networks to learn the score function of diffusion processes without the curse of dimensionality in some concrete cases.
1.1
OUR CONTRIBUTIONS
We summarize our contributions as follows.
We prove that if the log-relative density of the data distribution with respect to the standard Gaussian can be locally approximated without the curse of dimensionality, then the score function at any fixed time can be approximated in the Tp² norm, where Pt denotes the marginal density of the forward process at time without the curse of dimensionality.
2. We show that the empirical score matching estimator within prescribed class neural net- works can estimate the score at any fixed time without the curse of dimensionality. The error is decomposed into the approximation error of the score and the Rademacher com- plexity of the neural network class.
3. We combine our results with existing discretization error bounds (c.g.. in Chen al. (2023b)) to obtain explicit error estimates for SGMs in terms of the number of training samples. As an application, we prove that SGMs can sample from certain Gaussian mix- ture distributions with dimension -inisioon-deeeedeentt sample complexity.
1.2 RELATED WORK
A majority of the recent theoretical analysis of SGMs De Bortoli et al. (2021): Lee et al. (2022) 2023b); Chen et al. (2023a c): Benton et al. (023) focuses obtaining convergence guarantees for SGMs under minimal assumptions on the target distribution but, crucially, under the assumption that the score estimator is accurate in the sense of L L The common message shared among these works that learning the distribution is as easy (or hard) as learning the score function. More precisely, the estimation error of the target density is mainly controlled by the estimation error of
2

---

the score function and the discretization error of the diffusion processes (as another error source) scales at most polynomially in the data dimension. However, there has been relatively little work to address the problem of score estimation error.
More recently, was proven in Oko et al. (2023) that SGMs can estimate Besov densities with a minimax optimal rate under the total variation distance. However, the obtained sample complexity of density estimation over a Besov space suffers from the curse of dimensionality. The paper et al. (2023) further proved that the estimation rate can be substantially improved under the additional assumption that the data distribution is supported on a low-dimensional linear subspace, in which case the resulting rate only depends on the intrinsic dimension. Distributions with the same low- dimensional structure was also studied by [Chen et al. (2023d) in the Lipschitz continuous setting. The paper De Bortoli (022) obtained convergence bounds in the Wasserstein distance for SGMs under more general manifold hypothesis on the target distributions (including empirical measures).
Our work differs from the work above that we do not make low-dimensional assumption on the data distribution. Instead, we assume that the target is absolutely continuous with respect Gaus- sian and that the log-relative-density belongs to the Barron space [Barron] (1993). Barron functions have recently received much attention due to the fact that shallow networks can approximation them without curse of dimensionality; see, e.g., Klusowski and Barron (2018); Siegel and Xu (2022); Ma et al. (2022). In the context of generative modeling, the recent work Domingo-Enrich Enrich et al. (2021a b) investigated the statistical guarantees of energy-based models under the assumption that the underlying energy function lie in Barron space (or the Fi space therein). The work [ee et al. (217)) obtained expressive bounds for normalizing flows in representing distributions that are push- forwards of base distribution through compositions of Barron functions. This work shares the same spirit as Domingo-Enrien et al. (2021a a b); Lee et al. (2017) and demonstrates the statistical benefits of SGMs when target distribution exhibits low-complexity structures.
We note that in an carlier version of this work, the log-relative density f was assumed to be bounded. After discussions with an anonymous reviewer, we were inspired to strengthen the results to allow f to grow at infinity. In more detail, the reviewer pointed out that when is bounded, the data distribution satisfies log-Sobolev inequality (LSI) with constant e ell/llss which implies that the distribution can be sampled via Langevin dynamics with an estimator for the vanilla score. Our current results extend beyond the LSI case.
1.3 NOTATION
Throughout this article, we study functions and probability distributions on a Euclidean space Rd of a fixed dimension d. We let -| denote the Euclidean norm on Rd. For vector function, || oloo denotes the supremum norm, and || ILsp denotes the Lipschitz seminorm of metric space- valued function. We let ra(dz) denote the standard Gaussian measure on IRd, i.e., f f=))na(d)) = 4/2
(2m)-4/2 Jgu f(x)e- [|=])//2 The indicator of set S denoted Ils. We denote by (+) the ReLU activation function, defined by (c)+ max(0, e) for R. For a vector x, (x)+ + is interpreted componentwise. For No Rd and t > 0, we define (-(-XXX)) as the Gaussian density function with mean ex, and variance e 2t, For non-negative functions g(x),, h(x) defined on Rd we write s(x) X h(x) (resp. X) g(x) = O(h(z)) (resp. ((h(z)) if there exists a constant C. > 0 which depends at most polynomially on the dimension such that g(x) & Cah(a) (resp. 2). We write g(z) @(h(z)) if g(x) & h(x) & g(z). For B E (0, 10,1 and g L (Taa) define ( (1225)
M3(g) = Ja. 9
na(du).
BACKGROUND
In this section, give brief overview of the mathematical preliminaries required to understand our main result.
2.1 A PRIMER ON SGMS
In a score-based generative model (SGM), data is first transformed to noise via a forward process; work with Orastein-Ullenbee process (Xx)osesT, which solves the stochastic differential
3

---

equation
= V2dW,, Xo ~ Po-
Here, Po is some initial data distribution on R2 and We denotes d-dimensional Brownian motion. In the limit + oc, the law pt of the process Xy quickly approaches that of the standard Gaussian measure 7di in particular, we have pt - aa exponentially fast in in the KL divergence, total variation metric and 2- Wasserstein metric Bakry et al. (2014); Villani (2021). The SDE can be solved explicitly and, at each fixed time t, the solution coincides in law with the random variable
-Xo + VI- 21, Xo ~ Pos &~ (O, 12).
In particular, X, conditioned on Xo is a Gaussian random variable with mean e e "Xg and variance 1 By averaging Xo, obtain simple expression for the density pa in terms of po:
(x-e-'y)² 2(1 ((1-e-21)
pe(x) Zz²
exp
dyo(u)
where 2, = (2 e- 2) 2 is the time-dependent normalization constant.
The reverse process, X, Xr- is also a diffusion process Anderson
1982
Haussmann and
Pardoux 1986), solving the SDE (for S t
X, (X, 2V log ( + V2dW,, X, Pt.
where W, denotes time-reversed Brownian motion on Rd In order to implement SGMs in practice, one must discretize the OU process, and a canonical algorithm is the exponential integrator scheme
(EIS). In order to implement the EIS, one samples Xo die tv I and simulates the SDE
pr. picks time steps 0 = to t <
d. (X,ii + 2V logpr-t, pr (X.)) dt d..
each interval [La, 1..1.. J. Also, the reverse process typically initialized at X, ~ 7/ in practice, because pr is unknown. However, the eπror accrued by this choice is small, evidenced by the exponential convergence of pr to Ya as T + oo. The process one samples is then obtained by replacing the score function at time T t with score estimate sg:
[dY, = (Y₁ + 2s (Yr))) dt + dBi, E [tk, tx+1] You ~ Id).
(5)
Loss function:
To learn the score function at time f, a natural objective to minimize is the following least-squares risk, namely,
s, (t, + Exeop [||s(t, X,) V (x.))(
for given estimator S; : Rd Rdd However, this risk functional is intractable since, in the genera- tive modeling setting, one does not have access to pointwise data of the score function. However, it can be shown Vincent (201T) that for any St.
E Ex, [X. V. log (X.) Exp=po Ex Xx [|sse Xt), V (x((x(X)))11]] E,
where is constant independent of st. Here, V.(X,(Xo) tion of the forward process conditioned on the initial distribution. Note that the integral the right-hand side can be approximated on the basis of samples of po. since the trajectories (X₂ Xo) easy to generate. This motivates definition of the population risk at time t:
Xo denotes the score func- 1-
(s.) Exo-ro [Ex,<p,,x LXo (t), V. (. (x)
(6)
If we define the individual loss function at time & by
( x)) = Ex,1x== [X,s V.(Xx
(7)
then the population risk can be written as
R(,ss) Exnpo E (((
4

---

We also define the empirical risk associated to the i..d. samples x by
R (Sc)
Xi)
(8)
We then to solve the optimization problem
N min R (st)
where FF is an appropriately defined class of vector fields on IR (e.g., a class neural networks). The of the risk functional in 6 learn the score has been termed denoising score matching, because the function (Xx(Xo)) is the noise added to the sample Xo along the forward process.
2.2 NEURAL NETWORKS
fully connected feeefoowaar ReLU neural network is a function of the form
I -+ W++ WL-1 (..--(...WW (W1 (W1x + b1) + b2. b2...)" + bs.11)
+ bL.
where Wz. Rd x Rdc are matrices, by E Rdc are vectors, and, when r is a vector, (z)+ interpreted as componentwise mapping. The parameters (W:) and (b:) are called the weights and biases of the neural network respectively. The number of columns of W. is called the width of the ith layer. When I. 2, neural network called shallow, and, when they take values in I. such networks admit representation
m
a((,, b,)+
where x, wi E Rd and a,, b, E R. Neural networks have achieved remarkable success learn- ing complex, high-dimensional functions. In this work, study their ability to express the score function the diffusion process defined in Equation In order to control the generalization error incurred by empirical risk minimization, must introduce notion of 'complexity" for neural net- works, and a natural notion is the path norm, defined for real-valued shallow ReLU neural networks by
| path
lasl (1wwll + (b,1), ((x) Σ (w x + b,)
and extended natural way to vector valued/deep ReLU neural networks. has been shown that the collection of I-fold compositions of shallow networks of uniformly bounded path seminorm enjoys good generalization properties in terms of Rademacher complexity.
PROBLEM AND MAIN RESULTS
We outline our main assumptions on the data distribution.
Assumption 1. The data distribution po is absolutely continuous with respect to the standard Gaus- sian distribution. Throughout the paper, we let po denote both the probability distribution and the PDF of the data, and we write f(x)= == | /2 + log po(x) for the log-relative density of po with respect to the standard Gaussian distribution, so that
| 2
po(x) Z exp
+ f(x))
We further assume that
1. There exist positive constants Tf, B with B < such that -a||>|12 & f(x) s B11x11 whenever | 2 rf. and a. 3 satisfy c(a,, (3) = 1(a+8)
[1-B) 1;
2. f is continuously differentiable;
5

---

3. sup | f grows most polynomialty a function of R:
4. the normalization constant Z satisfies (2x) C, where C is constant depending most polynomially on dimension.
Assumption T roughly states that the tail of the data distribution should decay almost as quickly standard Gaussian. As illustrating example, consider the Gaussian mixture model q(x) oc
1x-21112
2-
10-02 2x max
If we write f(x) - ||~11 /2 log ((x)), then for any >> O, there exists r.
such that
(1- 20 min
1 o +e
d -1+
||=|| f(x) S
||3 ||
20 20
whenever ||=||| 2 rc- This shows that Assumption applies to Gaussian mixtures, as long as the bandwidths are suitably constrained.
The benefit of expressing the data distribution in terms of the log-relative density is that it leads to nice explicit calculation of the score function. In particular, Lemma states that the j component of the score function of the diffusion process is given by
(22 (-03 (x) Gx(x))
(V Po)) 1 c-2
(9)
where (z) faa(e VI-
naldu) and Gz(z)
S (efle-aovI-e-uui (d(duu) The linear growth assumption ensures that the tail Po has similar de- cay properties that of Gaussian, of which we make frequent use. The other assumptions on f and the normalization constant are stated for convenience.
In order to obtain tractable bounds the estimation error of SGMs for learning such distributions, it is necessary to impose additional regularity assumptions on the function f.
Assumption 2. [Learnability of the log-relative density] For every > 0 and R > 0, there exists an L-layer ReLU neural network of which satisfies
| SR sup If(x)
(f(=) -10)-007
R. (())))((((<))) (x)) Rc.
We denote by n/e,, R) = |10b Ipak the path norm of the approximating network as a function of and R.
We will generally abbreviate of to o mild abuse of notation. Assumption is weak because any continuous function can approximated by neural networks to arbitrary precision on a compact set [Cybenko (1989). However, we are mainly interested in cases where Φy generalizes well to unseen data; this corresponds to 17(E, R) growing mildly as e -
3.1 GENERAL RESULTS
the score function can be approximated effi- ciently by neural network, even in high dimensions. Our result helps to understand the massive suc- cess of deep learning-bast based implementations of SGMs used in large-scale applications. We denote by NN L,K the set of neural networks from Rdd to Rdd with depth L and path that for class of vector fields F. denote by Jacoret (x + -- (-x e f())) F).
Our first result shows that, under Assumptions D and 2
most K. Recall
Proposition 1 (Approximation error for score function). Suppose assumptions there exists class of neural networks NN with low complexity such that
hold. Then
[ [[δ(x) V (zg
inf dENNNOO
Jdd
=0 max (1 (1-c) 2- (1 + 20 2d,01 (1-)(1)))))) -(a,9))
(1 - e-2233 x223(11))

---

The class of neural networks is defined precisely in the appendix. A high-level idea of the proof is to show that the map from f to the score function v log Pt has low-complexity a suitable sense. The next result concerns the generalization enror of learning the score function via empirical risk minimization.
Proposition 2. /Generalization error for score function] Set R. /d+ i-c(aro) log (1=
and R. (og( The empirical risk minimizer's s in NN of the empirical risk R satisfies the population risk bound
R' (5) = =({)), provided the number of training samples N 2 Ne,t, where Ne,t satisfies
Ne. = max
221, & (1 20d 6 411 (Res (1 + 2a) 20120-220000 (0)22(a,8))
21 + 20) 12) -2220.,0) - -4-10, - (Te,, 166)
The next result describes how the learned score can be used to produce efficient samples from Po- with explicit sample complexity rates.
Proposition 3. [Distribution estimation error of SGMs] Let $ denote the empirical risk mini- mizer in N of the empirical risk Re. let P denote the distribution obtained by simulat- ing the reverse process defined in Equation [ over the time interval [to, T] with St, in place of the true score for each discretization point, using the exponential integrator discretization scheme outlined in Section 2. with maximum step size and number of steps M. Then, with T (log(1/d) (d) + 2d Bollog(1 + 2a) + +(1(1- 2c(,, ()) log(1/c)), M 2 dTc, K S M' to S Ma(f)-22?
and N 2 Ne,to (where Ne.oo is defined in Proposition] 2 we have
TV (c)
with probability > - poly(1/N).
The proof of the above result has three essential ingredients: Prop 2] which controls the score esti- mation еπгоr for any fixed f, an application of Theorem in Benton et al. (202)). which bounds the KL divergence between Pt, and p along the exponential integrator scheme terms of k, M, T and the score estimation error, and Lemma 10 which proves that the KL. divergence between po and Pto can be bounded by Mf(
3.2 EXAMPLES
We now discuss several concrete examples to which our general theory can be applied.
Infinite-width networks: Suppose that x e +(x)) where f(x) is an infinite-width ReLU network of bounded total variation, i.e., [(xx) = Sgata a(w"> + b)(+) du(a, b,)),, where c >> 0 and is a probability measure on Rd+2 For such an f. the Barron norm is defined as
[ gge |a[([[]]|+ + (6)))(da, dw, db).
| == =innf inf
where the infimum is over all μ such that the integral representation holds. The space of all such functions is sometimes referred to as the Barron space or variation space associated to the ReLU acti- vation function. The Barron space has been identified as the 'correct' function space associated with approximation theory for shallow ReLU neural networks, since direct and inverse approximation theorems hold. Namely, for any f in the Barron space and any O, there exists a shallow ReLU neural network JNN such that suP||=||<R parameters and || JNNNNl Ipah ||. Conversely, any function which can be approximated to curacy e by a network with path norm uniformly bounded in e belongs to the Barron space. A comprehensive study of Barron spaces can be found in Ma et al. (2022).
[f(x)) [NN(#)) < Re, where JNN has I -2)
Under the Barron space assumption on f. we can leverage the linear growth and fast approximation rate of Barron spaces to obtain dimeeniooninndeenden sample complexity rates for SGMs.

---

Proposition 4. [Distribution estimation under Barron space assumption] Suppose that po(z) o --11=11/24+(00)) where f belongs to the Barron space. Let I| denote the Barron norm and let Cy = > 0: 1f()) - c||>||> & llf Given ő E (0, 1), let e(6) be small enough that Sej where Rt = /d d log( [/) Then for all S co, the distribution p learned by the diffusion model satisfies
Rt. I 8,
TV O(E))
provided the number of samples N satisfies.
N 9 222,,11 (1
20g
12d
M
145/4
R2
When is small, we essentially require -10 samples to learn Po to accuracy (up to the prefactors) this is significant improvement to classical sample complexity bounds in high dimensions, wherein the rate typically tends to zero as - oo. We emphasize that the significance of our contribution is that the rafe of the sample complexity is independent of dimension, and we leave it open direction whether all prefactors can be improved to depend only polynomially on d.
Gaussian mixtures: Distributions that describe real-world data are often highly multimodal, and natural model for such distributions is the Gaussian mixture model; we assume the initial density to be of the form
1 Z1
| x1 |
1 exp Zz
(- || -| 22112 σ max
Po
exp
20
min
where 0 < min < d are the bandwidths and I1, 22 E Idd are the modes the distribution. The results that follow can easily be adapted mixtures with more than two components and with arbitrary weights, but we keep the setting as simple as possible to illustrate the results. Due to the growth condition imposed in Assumption our theory cannot be applied Gaussian mixtures with arbitrarily small bandwidths; this is discussed further in Appendix distribution estimation result for Gaussian mixtures.
We prove the following
Proposition
5. [Distribution estimation for Gaussian mixture]
Given
0,
Re
V d + 1- log
(L+22))) and R.
ldglog((t
Let Po(x)
lim-xill 2e man
11?
In-p21?? max
be mixture of two Gaussians, and fix 8 < 1. Assume that
Z.
Zz
the bandwidths min Jaax satisfy c(a, 3) Ma+3) 1, where a and are as defined in Assump- 1-23
tion] 7 Then there exists an to (depending on 6) such that for any e S eg. the distribution π learned by the SGM satisfies
TV 0 (
=0(11 (1+ 2a) '
provided the number of samples N satisfies N 2 max(Ne.1, Ne.2). where
No.1 St 12L,-10
10x) 2cx 12d 12d_-1 sup Po (x)
[ SR.
and
No2 Ω 22 2cx) 12d, () -4- (84-88c(a,8)
sup Po (x0) | R.
As an example, if oiin =0 1, then we have
TV 0(E)
provided the number of samples satisfies
N = 222 + 3)22d d/2 11122-244--0 268-7686
8

---

The details of the proof presented in Appendix E One technical detail is that need to be able to approximate the log density by a ReLU neural network so that Assumption 2is satisfied. Unlike in the previous example, the log- log-likeldhood is not Barron function. However, can be shown that for any R. the restriction of the log-likelihood to Bn can be represented by a composition of two Barron functions, and from this it follows that the log-likelihood can be locally approximated by ReLU network with two hidden layers.
4 CONCLUSION
In this paper, derived distribution estimation bounds for SGMs, applied to family of sub- Gaussian densities parameterized by Barron functions. The highlight of our main result is that the sample complexity independent of the dimension. An important message of this work is that, for a data distribution of the form in Assumption I low-complexity structure of the log-likelihood induces a similar low-complexity structure the score function. particular, the score function can be approximated in I,² by neural network without the curse of dimensionality. Some recent works (Oko et al. 2023; Chen et al., 2023d) have derived distribution estimation bounds under assumptions of low-dimensionality on the data; we chose to investigate an approximation-theoree notion of lowwccmplexity"" and thus our results are a complement to these existing works.
We conclude by mentioning similar results could be achieved if we relax some of our assumptions on the data distribution; for instance, would like to extend the results to the case where the log-likelihood is allowed to decay arbitrarily quickly. Second, is not clear whether our estimation rate for the class of densities con- sidered is sharp, and thus obtaining lower bounds for sampling from such densities is interesting open problem. We conjecture that our generalization error bound can be improved using more re- fined techniques such local Rademacher complexities. Finally, obtaining training guarantees of score-based generative models remains an important open problem, and another natural direction for future work would be to study the gradient flow/gradient descent dynamics of score matching under similar assumptions on the target distribution.
potential directions for future research. First, we wonder whether
ACKNOWESDS
Frank Cole and Yulong Lu thank the support from the National Science Foundation through the award DMS-2N2 MMS-2333335.
REFERENCES
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learn- ing. pages 2256-2265. PMLR, 2015.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, PMLR, 2021.
Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. Diffusion models: A comprehensive survey of methods and applications. arXiv preprint 20X.v22209.00796, 2022.
Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah. Diffusion models in vision: A survey. IEEE Transactions on Patlern Analysis and Machine Intelligence, 2023.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-179993 2021.

---

Nikolay Savinov, Junyoung Chung, Mikolaj Binkowski, Erich Elsen, and Aaron van den Oord. Step- unrolled denoising autoencoders for text generation. arXiv preprint arXiv:2112.06749, 2021.
Jin Sub Lee, Jisun Kim, and Philip M Kim. Score-based generative modeling for de novo protein design. Nature Computational Science, pages 1-11, 2023a.
Bowen Jing, Gabriele Corso, Jeffrey Chang, Regina Barzilay, and Tommi Jaakkola. Torsional dif- fusion for molecular conformer generation. Advances in Neural Information Processing Systems, 35:24240 24253, 2022.
Tomer Amit, Tal Shaharbany, Eliya Nachmani, and Lior Wolf. Segdiff: Image segmentation with diffusion probabilistic models. arXiv preprint 1rXiv:2112.00390, 2021.
Dmitry Baranchuk, Ivan Rubachev, Andrey Voynov, Valentin Khrulkov, and Artem Babenko. Label- efficient semantic segmentation with diffusion models. arXiv preprint arXiv:2112.03/26, 2021.
Emmanuel Asiedu Brempong, Simon Korblith, Ting Chen, Niki Parmar, Matthias Minderer, and Mohammad Norouzi. Denoising pretraining for semantic segmentation. Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 4175 2022.
Hyungjin Chung and Jong Chul Ye. Score-based diffusion models for accelerated mri. Medical image analysis, 80:102479 2022.
Chin-Wei Wei Huang, Jae Hyun Lim, and Aaron C Courville. A variational perspective on diffusion- based generative models and score matching. Advances in Neural Information Processing Sys- tems, 34:22863-22222 22876, 2021.
Calvin Luo. Understanding diffusion models: A unified perspective. arXiv:2208. 11970, 2022.
arXiv preprint
Wenbo Gong and Yingzhen Li. Interpreting diffusion score matching using normalizing flow, arXiv preprint
2021.
Aapo Hyvärinen and Peter Dayan, Estimation of non-normalized statistical models by score match- ing. Journal of Machine Learning Research, 6(4), 2005.
Pascal Vincent. connection between score matching and denoising autoencoders. Neural compu- lation, 166)::16611177, 2011.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friente friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages 4735-4763, PMLR, 2023a.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Score approx- imation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Learning Representations. PMLR, 2023b.
Joe Benton, Valentin De Bortoli, Amnud Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXiv preprint 0336623008..3666, 2023.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematccs of control, signals and systems, 2(4):303-314, 1989.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Nenworks, 94: 103-114, 2017.
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695-17709, 2021.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances Neural Information Processing Systems, 35:22870-2222 2022.
10

---

Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023b.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast, arXiv preprint 2xXi::3355.1199: 2023c.
Kazusato Oko, Shunta Akiyama, and Taiji Suzuki. Diffusion models are minimax optimal distribu- tion estimators. International Conference of Machine Learning, 2023.
Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Conference on Machine Learning. PMLR, 2023d.
Valentin De Bortoli. Convergence denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information theory, 39(3):930-99) 1993.
Jason M Klusowski and Andrew Barron. Approximation by combinations of relu and squared relu ridge functions with el and e controls. IEEE Transactions on Information Theory, 64(12):
7649-7656, 2018
Jonathan W Siegel and Jinchao Xu. Sharp bounds on the approximation rates, metric entropy, and n-widths of shallow neural networks. Foundations of Computational Mathematics, pages 1-57, 2022.
Chao Ma, Lei Wu, al. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369-406, 2022.
Carles Domingo-Enriche Alberto Bietti, Eric Vanden-Eijnden, and Joan Bruna. On energy based models with overparametrized shallow neural networks. In International Conference on Machine Learning, pages 17712 PMLR, 2021a.
Carles Domingo-Enrich, Alberto Bietti, Marylou Gabrié, Joan Bruna, and Eric Vanden-Eijnden. Dual training of eergy-basse models with overparametriieed shallow neural networks. arXiv preprint arXiv:2107.05// 2021b.
Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. On the ability of neural nets to express distributions. In Conference on Learning Theory, pages 1271-1296. PMLR, 2017.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Ap- plications, 12(3):313-326, 1982.
Ulrich G Haussmann and Etienne Pardoux. Time reversal of diffusions. The Annals of Probubility, pages 1188-1205, 1986.
Stephan Wojtowytsch et al. On the banach spaces associated with multi-layer relu networks: Function representation, approximation theory and gradient descent dynamics. arXiv preprint 1rXiv.2007.15663, 2020a.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Chao Ma, Stephan Wojtowytsch, Lei Wu, al. Towards mathematical understanding of neural network-basse machine learning: what we know and what we don't. arXiv preprint arXiv:2009. 10713, 2020.
11

---

Stephan Wojtowytsch al. Representation formulas and pointwise properties for barron functions. arXiv preprint arXiv:2006.05982, 2020b.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
12


Reviews:
[{"review_id": "IG8oZpiH8D", "reviewer": "Reviewer_bdyJ", "summary": "The authors prove a bound on the sampling error of score based modeling under the assumption that the target density has the form $p_0(x) \\\\propto e^{f(x)} \\\\gamma_d(dx)$, where $f$ has $\\\\|f\\\\|_\\\\infty < \\\\infty$ and $\\\\|f\\\\|\\_{\\\\mathcal{B}} < \\\\infty$. The latter norm is the spectral Barron norm, which is known to define a function class $\\\\mathcal{B} = \\\\{f : \\\\mathbb{R}^d \\\\to \\\\mathbb{R}, \\\\|f\\\\|\\_{\\\\mathcal{B}} < \\\\infty\\\\}$ that can be well approximated in sup-norm by shallow neural networks with bounded path norm. Under these assumptions, the authors bound on the total variation $\\\\text{TV}(p_0, \\\\hat{p}_{t_0})$, where $\\\\hat{p}_{t_0}$ is the output of an early-stopped SGM. The sample complexity of this bound is $\\\\text{TV}(p_0, \\\\hat{p}_{t_0}) \\\\lesssim N^{-\\\\alpha}$ where $\\\\alpha > 0$ is independent of the dimension. \n\n It has been shown in previous works that the SGM sampling error is controlled by the approximation error of the learned score model, $\\\\hat{s}(t, X) \\\\approx \\\\nabla_x \\\\log p_t(x)$, where $(p_t)_{t \\\\geq 0}$ is the law of an Ornstein-Uhlenbeck Process with initial condition $p_0$ given by the data distribution. Using integration by parts, the score can be rewritten as $$\n    \\\\nabla_x \\\\log p_t(x)  = \\\\frac{1}{1-e^{-2t}}\\\\left( -x + e^{-t} \\\\mathbb{E}[ e^{-t} x + \\\\sqrt{1-e^{-2t}} U \\\\mid X_t = x] \\\\right)$$\n where the expectation is taken with respect to $\\\\text{Law}(U \\\\mid X_t = x) \\\\propto e^{f(e^{-t}x + \\\\sqrt{1-e^{-2t}}U)} \\\\gamma_d(dU)$. The key insight of the paper is that the conditional expectation in this expression inherits the smoothness properties of $p_0$, and in particular, it can be approximated by a composition of shallow neural networks. In Theorem 3, the authors prove an approximation error bound on the score network by an appropriate class of neural networks. In Theorem 2, using standard techniques from empirical process theory, the authors use this bound to prove the TV bound on SGM sampling error.", "questions": "What is the minimax rate of estimation for functions from $\\\\mathcal{F}\\_{\\\\text{score}}(\\\\{K_i\\\\}_{i=1}^L)$? How does it compare to estimation rates proven in this paper? What should one takeaway from the rates in this paper, and/or what do they say about the relationship between this problem and vanilla density estimation?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Clarity: while there are some minor typos, the results in this paper are clear and well-explained. They are correct to the best of my knowledge. \n- Dimension free sample complexity: it is interesting and potentially valuable to prove generalization bounds that depend on instance-specific complexity measures, like the Barron norm of $f$, in place of a dependence on the ambient dimension.", "weaknesses": "- Exponential dependence on $\\\\|f\\\\|\\_{\\\\infty}$. The assumption that $\\\\|f\\\\|\\_\\\\infty < \\\\infty$ seems extremely strong and the constants in this bound depend exponentially on $\\\\|f\\\\|\\_{\\\\infty}$. As a thought experiment, suppose $p_0(x) = \\\\prod_{i=1}^d p_0^{(i)}(x_i)$ is the tensor product of 1-d distributions $p_0^{(i)}(x_i) \\\\propto e^{g(x_i)} \\\\gamma_1(dx_i)$. Then it is reasonable to expect $f(x) = \\\\sum_{i=1}^d g(x_i)$ can have $\\\\|f\\\\|\\_{\\\\infty} = \\\\Omega(d) \\\\|g\\\\|_{\\\\infty}$ if the support is not restricted to a low-dimensional subspace. Because of this, it's not clear to me that the stated bounds can actually 'escape the curse of dimensionalty' or be 'dimension free' in non-trivial cases. \n- Likely suboptimal bounds. There are many techniques in the literature on empirical process theory that could be used to improve the stated bounds (notably localization methods). I am not an expert on these techniques, but it would at least be worth commenting on ways the bounds in this work could be improved.\n- No lower bound. It would also be helpful to prove (or at least discuss) lower bounds for this estimation problem. For example, do you know a minimax lower bound for estimating a generic function in $\\\\mathcal{F}\\_{\\\\text{score}}(\\\\{K_i\\\\}_{i=1}^L)$? How does it compare to the generalization error of $\\\\hat{s}$? It is difficult make any takeaways from this work given that the upper bound is likely suboptimal and there is no lower bound to compare against. \n\nAlso, here are some minor typos:\n- Statement of Theorem 2: please define $\\hat{p}_t$. The theorem statement includes $\\text{TV}(\\hat{p}\\_0, p\\_{t\\_0})$, but based on the proof (pages 31, 32) it seems like it should be $\\text{TV}(\\hat{p}\\_{t\\_0}, p\\_{0})$. \n- Page 7, \"Proposition 3 guarantees that, by choosing $K$ ...\" should be Theorem 3\n- Page 7, display following \"Girsanov's theorem, combined with the data processing inequality\" shouldn't this be an inequality instead of an equality? Also, there seems to be inconsistent notation regarding $\\hat{p}\\_{t_0}$, $\\hat{p}\\_{t\\_0, T}$, etc -- please make the notation consistent and define it. \n- Page 9, first paragraph, \"as the multiplication of $a_i(t)$ and $b_i(t)$ induces a nonlinearity.\" What is $b_i(t)$? I was not able to find any reference of it. \n- Lemma 2 in the appendix is missing parenthesis in the big $O$ notation in both line items. \n- Lemma 2 proof, line two of the series of inequalities (begins with $\\lesssim$), this line seems to be missing a factor of $\\\\|f\\\\|\\_{\\mathcal{B}}$ which appears in following lines. \n- Lemma 3 statement uses functions $F\\_1, F\\_2$ instead of $F, G$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7QeD5QN23B", "reviewer": "Reviewer_r8Sf", "summary": "Recent progress in theoretically understanding score-based diffusion models has shown that sampling (i.e., training a generative model) often reduces to L^2 (or L^\\infty) score estimation [Lee et al., 2023; Chen et al., 2023; Benton et al. 2023]. In light of these results, the logical next step is to understand when neural networks can efficiently learn score functions.\n\nThis work represents a significant step in this direction. The authors restrict their attention to distributions that can be represented as exponentially tilted Gaussian distributions. Then, they show that if the tilting function, which characterizes the target distribution, is of “low-complexity”, then neural networks can *efficiently* approximate the corresponding score function at a rate that is independent of the data dimension. Building on this approximation-theoretic result for the score function, the paper then establishes a sample complexity upper bound for approximating the target distribution in TV distance. Notably, this upper bound avoids the cursed exponential-in-d rate.\n\nThese results are distinct from other recent results which achieve dimension-independent rates by assuming that the target distribution is supported on a low-dimensional manifold.\n\n**References**\n- Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. *NeurIPS* 2022.\n- Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. *ICLR,* 2023.\n- Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. *arXiv:2308.03686*, 2023.", "questions": "- Aside from the Barron space assumption, what conditions must the tilting function satisfy to ensure that corresponding function is a probability density? An immediate one seems to be subquadratic growth, but are there other conditions that one needs to or would want to assume?\n- What are some well-known distributions which are Gaussians exponentially tilted by a “low-complexity” function from Barron space?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is a very well-executed paper. The question addressed in this work is a natural continuation of the recent research effort devoted to understanding theoretical aspects of score-based diffusion models. The main results are timely and significant, and the authors draw ideas (tilted Gaussians, Barron space, path norms) from diverse research areas, and combine them in an elegant manner.\n\nMoreover, the paper is exceptionally well-written, especially considering the technicality of the topic. Ideas are presented clearly and concisely, and intuition behind the proofs are communicated effectively.", "weaknesses": "I only have minor editorial comments.\n\n- It would help motivate the setting better if examples of non-trivial target distributions that satisfy the assumptions were provided. What are some well-known distributions which are Gaussians exponentially tilted by a “low-complexity” function from Barron space?\n- The sudden appearance of L=8 in Theorem 2 is unnecessarily surprising and mysterious. It would be helpful if this was explained prior to Theorem 2. For example, one can mention that the score function is a composition of the tilting function, which can be approximated by a shallow network, and basic function/arithmetic primitives like exponentiation and multiplication, which can be implemented by stacking more layers.\n- Typo in p.9: “allowed to be grow”\n- I would suggest simply adding a table of contents to the Appendix (there is a latex package for this) instead of Section B.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "COuzBWC2KW", "reviewer": "Reviewer_2C1B", "summary": "This paper introduces a theoretical setting in which a deep network which minimizes the empirical score matching loss produces approximate samples from a high-dimensional data distribution. The curse of dimensionality is broken by assuming that the data distribution is a small perturbation from the Gaussian distribution. The asymptotic sample complexity exponent is independent of the dimension, with a constant that depends polynomially on the dimension and the Barron norm of the perturbation (but exponentially in its $L^\\infty$ norm).", "questions": "I have some minor remarks and questions:\n- Since $f$ is defined up to a constant, the $L^\\infty$ norm of $f$ can be replaced with the \"oscillation\" of $f$ $(\\sup f - \\inf f)/2$, which makes the invariance of $p(x)$ on addition of constants to $f$ explicit\n- The specification of the function class for neural networks makes no mention of the intermediate widths. In general, I was initially confused whether they were assumed to be one or not, as the previous paragraph talks about real-valued shallow networks.\n- The equation (9) seems related to the Miyasawa/Tweedie relationship for the structure of the score (see e.g. equation (4) in [5]), as is commonly used in denoising score matching [6]. I think it would make the paper clearer to state that the network has to approximate the conditional expectation $\\mathbb E[x_0 | x_t]$, which is essentially the ratio of the functions $F_t$ and $G_t$.\n- In section 4.2, it would help the reader to state that the approximations of the intermediate functions (product, exponential, etc) are in the $L^\\infty$ norm restricted to balls.\n\nTypos:\n- Lemma 4, \"K0\"\n- Lemma 12, extra $|\\ell_{R,S}$\n\n[5] Raphan, Martin, and Eero P. Simoncelli. “Least Squares Estimation Without Priors or Supervision.” Neural Computation 23, no. 2 (February 2011): 374–420.\n\n[6] Vincent, Pascal. “A Connection Between Score Matching and Denoising Autoencoders.” Neural Computation 23, no. 7 (July 2011): 1661–74.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "While sampling guarantees of diffusion models are now rather well-understood, learning guarantees are much less explored, especially in high dimensions. This paper thus studies a central topic, and is the first (to the best of my knowledge) to obtain results on a truly high-dimensional distribution. The paper is also very clearly written and is enjoyable to read: I commend the authors for managing to give intuition about the several steps of the proof despite its technical difficulty.", "weaknesses": "The results have a very big limitation, which is the exponential dependence of the error bound on the $L^\\infty$ norm of the perturbation $f$. To avoid the curse of dimensionality, this norm thus needs to be $O(1)$ in the dimension. However, in this setting, diffusion models are unnecessary, as much simpler classical techniques are sufficient. Indeed, the Holley-Stroock perturbation lemma [1] implies that the distribution $p(x)$ satisfies a logarithmic Sobolev inequality with a constant that is $\\Omega(1)$ in the dimension. The score matching loss at time $t=0$ then controls the error in KL divergence [2], and knowing the score at time $t=0$ is sufficient to obtain sampling guarantees with Langevin/MALA algorithms [3,4]. Therefore, it is not necessary to approximate the scores at all times with a neural network. After a quick assessment of the proof technique, it seems hard to remove this exponential dependence in this norm as the variance of the Monte-Carlo approximation of the integrals depends exponentially on the $L^\\infty$ norm of $f$.\n\nI still think the paper should be accepted, because the paper is the first (to the best of my knowledge) to study the sampling complexity of score approximation in high dimensions, and the proof technique might be useful for further research which extends the results in a more interesting setting. But the authors should acknowledge and properly discuss the limitation mentioned above.\n\n[1] Holley, R., and Stroock, D. Logarithmic Sobolev inequalities and stochastic Ising models. J. Stat. Phys. 46, 5–6 (1987), 1159–1194.\n\n[2] Koehler, Frederic, Alexander Heckett, and Andrej Risteski. “Statistical Efficiency of Score Matching: The View from Isoperimetry.” arXiv, October 3, 2022. http://arxiv.org/abs/2210.00726.\n\n[3] Chewi, Sinho. Log-Concave Sampling. https://chewisinho.github.io/main.pdf.\n\n[4] Altschuler, Jason M., and Sinho Chewi. “Faster High-Accuracy Log-Concave Sampling via Algorithmic Warm Starts.” arXiv, February 20, 2023. http://arxiv.org/abs/2302.10249.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XHtFlqyM5X", "reviewer": "Reviewer_wRd7", "summary": "An exciting result that studies the generalization of the score-based generative modeling under finite sample & shallow neural networks under assumptions of actual sampling density being in the Baron class of functions.", "questions": "Assume the function is say, just Lipshitz-smooth. Can we upper bound the Baron constant with a dimensionally dependent constant? \nWhy asking -- in constants in proofs there are terms that have said Baron constant in the exponent. \nSo if for densities that are highly non-convex -- we should expect curse of dimensionality to re-appear?\n\nWhat is connection of densities that are $-||x||^2$+Baron class perturbation to $(\\alpha, \\beta)-$dissipative distributions? (convex outside of region)? It seems that this is sub-class of such, and if so, can authors elaborate what obstacles there is to generalise results on such class? (that are common in say analysing Langevin Dynamics generalization). \n\nBaron class assumption needed only for universal approximation results about shallow network, right?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Rigorous theoretical analysis of population and empirical losses of score-based diffusion models with explicit bounds.\n2. The work is well-written and structured.\n3. The work answers an intriguing question if there is a class of functions for which score-based diffusion models break the curse of dimensionality, which by itself is not obvious.", "weaknesses": "Limited to shallow networks and Baron class (later I don't consider it as something concerning, just some discussion of potential extensions to other classes/other architectures will be appreciated with potential caveats, e.g., in Appendix authors discuss about extending to deep networks -- won't there be any issues with dimension dependency in Lipshitz constants?).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)