Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian distributions

We are very grateful to the reviewer for their encouraging feedback and insightful questions. We address your remarks as follows.

• Note that the only exponential dependence in our constants is on the $L^{\infty}$ norm of $f$, not the Barron norm of $f$. The only dependence on the Barron norm of $f$ in our main result (Theorem 2) is linear.
• As we understand it, a measure $p = \frac{1}{Z} e^{-V(x)}$ is considered $(\alpha,\beta)$ dissipative if $\langle \nabla V(x), x \rangle \geq a\|x\|^{\alpha} - b$ for some $a,b \geq 0$, and $\nabla V$ is $\beta$-Holder continuous. In the case that the potential $V$ satisfies $V(x) = \|x\|^2/2 + f(x)$ where $f$ is a spectral Barron function, you are correct that the density is $(\alpha,\beta)$-dissipative: since $|\nabla f|_{\infty} < \infty$

for Barron functions, we find that $\langle \nabla V(x), x \rangle \geq \frac{1}{2}\|x\|^2 - \frac{\|\nabla f\|_{\infty}}{2}$

and similarly $V$ is Lipschitz with Lipschitz constant at most $(1+\|\nabla f\|_{\infty})$. Hence $\frac{1}{Z}e^{-\|x\|^2/2+f(x)}$ is $(\alpha,\beta)$-dissipative with $\alpha = 2$ and $\beta = 1$. However, our main assumption on the distribution is a low-complexity assumption, which general $(\alpha,\beta)$-dissipative distributions need not satisfy. Those SGMs for learning $(\alpha,\beta)$-dissipative distributions would in general suffer from curse of dimensionality without further low-dimension or low-complexity assumption.

• Yes, the Barron assumption is needed for the approximation properties of neural networks.

Note that any changes that we have made to the submitted version of the paper are colored in blue. In order to get under the page limit with the changes, we have commented out some less-important remarks, which we plan to add back in the final version.

We thank the reviewer for their detailed and insightful comments. We would like to address them as follow.

• We do recognize that the $L^{\infty}$ norm of $f$ may depend on the dimension in many contexts. However, as we mentioned in our response to reviewer 1, such exponential dependence on dimension in the prefactors is generally unavoidable.
• It is a sharp observation that, since the density we study satisfies LSI, it would be enough to learn the score at time 0 and run a Langevin process with the empirical score. To show that distributions which do not satisfy functional inequalities can be learned by SGMs without the curse of dimensionality is therefore an interesting open problem. However, we feel that our bounds are still meaningful because, in practice, one cannot use such structural information about the data to design the generative model, as it is unknown to the learner.
• About intermediate widths, the proof of Theorem 3 shows that for approximation, it is enough to assume the intermediate widths are all 1, since we're really just approximating a bunch of single-variable functions. However, this is obviously not done in practice, and it does not hurt our generalization argument to assume that intermediate widths are arbitrarily large, as long as the path norm at each layer is bounded independently of the width. We have added a statement about this in the paper (in order to keep under the page limit, we have made this comment in the appendix, specifically at the end of Appendix C).
• We have added a remark after the statement of Theorem 2 to mention that, without loss of generality, the $L^{\infty}$ norm of $f$ can be replaced with oscillation of $f$, i.e., that the $L^{\infty}$ norm of $f$ can be assumed minimal over all translates. Thank you very much for pointing this out to us.
• We have stated in Section 3 that the network is estimating the conditional expectation $\mathbb{E}[x_0|x_t]$, which is basically just $F_t/G_t$ under our assumptions. We have also made clearer in Section 4.2 that the intermediate function approximation is only done locally, i.e., that the metric is the $L^{\infty}$ norm restricted to a ball.
• Thank you for pointing out the typos; we have corrected them.
• We have added the references you listed to our bibliography.

Note that any changes that we have made to the submitted version of the paper are colored in blue. In order to get under the page limit with the changes, we have commented out some less-important remarks, which we plan to add back in the final version.

We are very grateful for the positive feedback and helpful suggestions from the reviewer. We have addressed the remarks below:

• We would first like to mention that, upon further inspection of the proofs, the approximation and generalization proofs can be adapted to the case that the function $f$ is allowed to grow linearly at infinity, say, if $|f(x)| \leq C_f \|x\|$ whenever $\|x\|$ is sufficiently large. Under this change, the main results can be extended to a larger class of distributions, where the function $f$ need not be globally bounded, at the expense of a slightly slower estimation rate. We will update the changes in the final revised version of the paper accordingly.

A motivating example that falls into the linear growth framework for $f$ is the case where the initial density is a Gaussian mixture. Suppose that $p(x) = \frac{1}{Z} \left( e^{-\|x-x_1\|^2/2} + e^{-\|x-x_2\|^2/2} \right), x_1, x_2 \in \mathbb{R}^d,.$ Then the log-relative density with respect to the standard normal distribution is $f(x) = \log(1/Z) + \log \left( e^{-\|x-x_1\|^2/2} + e^{-\|x-x_2\|^2/2} \right) + \frac{\|x\|^2}{2}.$

• The depth of the network constructed in Theorem 2 actually should be $L = 7$, and it is explained further in the proof of Theorem 3 in the paper; in essence, it arises from the compositional structure of the score function under our assumption, and the fact that every elementary function that we approximate (e.g., the exponential or product function) corresponds to a single layer in the final network. We are glad that you made us aware that this sudden introduction of depth appears unnatural to the reader, so we have added a brief explanation of where it comes from after the statement of the theorem.
• Thank you for pointing out the typo, and for suggesting the inclusion of a table of contents for the appendix in place of an extra section. We have edited the paper accordingly.
• As you point out, for $\frac{1}{Z}e^{-\|x\|^2/2 + f(x)}$ to be a density, we really just need $\|x\|^2/2 - f(x)$ to grow fast enough that $e^{-\|x\|^2/2 + f(x)}$ is integrable. The Barron assumption on $f$ immediately implies that $f$ is bounded hence leading to the function $e^{-|x|^2/2+f}$ being integrable.

Note that any changes that we have made to the submitted version of the paper are colored in blue. In order to get under the page limit with the changes, we have commented out some less-important remarks, which we plan to add back in the final version.

We thank the reviewer for their detailed and insightful feedback. In response to the great points made, we have a few remarks:

• It is true that the $L^{\infty}$ norm of $f$ may depend on the dimension for certain distributions. However, since the function $f$ is only defined up to an additive constant, we can replace the dependence on $\|f\|_{\infty}$ with the quantity $\frac{1}{2} \textrm{osc}(f)$, where $\textrm{osc}(f) := \sup f - \inf f$.
• In addition, it is generally difficult to obtain sample complexity bounds where the prefactors do not depend exponentially on the dimension of the problem. In fact, in the classical nonparametric estimation of Sobolev densities, the $L^2$ error scales like $O(\|p\|_{H^s}) n^{-\frac{s}{2s+d}}$

where the Sobolev norm can grow exponentially in $d$. For example, in the example pointed out by the reviewer where $p_0(x) = \Pi_{i=1}^d p_0^{(1)}(x_i)$, the $H^s$ norm of $p_0$ on the unit cube $[0,1]^d$ would be $O(C^d)$ where $C \sim \|p_0^{(1)}\|_{H^s([0,1])}$, leading to an exponential dependence of $d$ when $C>1$.

We stress here that our goal is to prove that, in the presence of low-complexity structure of the function $f$ defined in our paper, the rate of convergence with respect to the growing sample size is independent of the dimension $d$. Nonetheless, it is worth discussing the potential limitation of the constant factor $e^{\|f\|_{\infty}}$ in our bound and its comparison to classical density estimation, and we have added a remark to this end in the conclusion paper.

• It is true that, specifically, our bound on the generalization gap (denoted $\mathcal{R}_R(\hat{**s**}) - \mathcal{R}_R(**s**^{\ast})$ in Section 4.1 the paper) is likely sub-optimal, because we bound it by the Rademacher complexity directly. We believe that a faster generalization rate can be achieved through the use of more refined techniques from empirical process theory (localization, as you point out, would probably work quite well). We have added a discussion on this in the conclusion of the paper.
• We thank the reviewer for pointing out the very interesting question on the minimax lower bound. First we would like to clarify that $\mathcal F_{score}(\{K_i\}_{i=1}^{L})$ is class of estimators, not the target function class of the score function. Right now, we do not have a minimax lower bound for estimating densities of the form $e^{-\|x\|^2/2 + f(x)}$ with $f$ Barron, nor do we have a lower bound for estimating score functions of such distributions. Our focus here is to derive generalization error bound for the sample quality of score-based generative models instead of the estimation error of the density function itself. The main takeaway message is that the rate of the generalization error between the generated distribution and the target data distribution is dimension-free when the target density has certain low-complexity structure whereas the estimation rate of density estimation under the standard Sobolev and Holder assumptions suffers from the curse of dimensionality.

We admit that the problem of obtaining a minimax lower bound of the generalization error for SGMs under our low-complexity assumption is very important and that understanding it would make the upper bound more meaningful, but it is highly non-trivial and requires deeper understanding of the approximation of the relevant multi-layer function space for the score function. We think investigation of this question is beyond the scope of the paper. We have noted this question as an interesting future direction in updated the conclusion section.

• We thank the reviewer for catching several typos and, in response to the helpful comments on notation, we decided to begin the proof of Theorem 2 with a list of all relevant distributions and their explicit definitions. Right now, this addition is in the proof of Theorem 2 in the appendix, not the main text, due to the page limit.

Note that any changes that we have made to the submitted version of the paper are colored in blue. In order to get under the page limit with the changes, we have commented out some less-important remarks, which we plan to add back in the final version.