Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models

Thank you for your review. We address your comments below.

Bounded assumption on the target distribution. Thank you for raising this point!

• We agree that the bounded support assumption is stronger than, for example, the bounded second moment assumption, and it excludes Gaussian distributions. However, we argue that this condition is satisfied in most practical scenarios. Arguably, the most important applications of diffusion models are to generate new images from a target distribution, where image data is naturally bounded. For instance, the CIFAR and ImageNet datasets consist of images with pixel values ranging from 0 to 255 or $[0, 1]$, and it is common to normalize them to the range $[-1, 1]$. Then the $\ell_2$ norm of an image from, e.g., the CIFAR dataset, is typically below $60$. Moreover, for DDPM in image generative tasks, $T$ is typically around $100$. Hence, we believe it is reasonable to assume in theoretical analysis that the radius of the data distribution is bounded by $T^{c_R}$, where $c_R$ is any given fixed constant that can be very large.
• We acknowledge that it is unfortunate not to cover common distributions like the Gaussian. Although we believe the bounded support assumption is not essential, it greatly facilitates our analysis, especially since we use a novel set of analytical tools that characterize the dynamics of DDPM in a more deterministic manner to establish convergence guarantees in the presence of low-dimensional structure. While we can relax this assumption in some specific cases (e.g., for Gaussian distribution, as illustrated in the next paragraph), we find it challenging to achieve a clean and concise result that holds generally for any distribution with a finite second moment. We leave this to future investigation.

We will incorporate these discussions in our next revision.

Regarding the gap between our lower bound and the TV error. Thank you for your suggestion! We conduct an experiment to examine whether our coefficient design (3.2) is indeed the unique coefficient design that leads to dimension-independent TV error $\mathsf{TV}(q_1,p_1)$, described as follows.

Using the degenerated Gaussian distribution considered in Theorem 2 as a tractable example, we ran the DDPM sampler with exact score functions (so that the error only comes from discretization) and plotted the error curves of $\mathsf{TV}(q_1,p_1)$ versus the ambient dimension $d$ under several different choices of $T$. We implemented both our coefficient design (2.4) and another widely-used design $\eta_t = \sigma_t = 1-\alpha_t$. The results demonstrate that the TV error $\mathsf{TV}(q_1,p_1)$ is independent of the ambient dimension $d$ under our coefficient design (2.4), while it grows with $d$ when using the other design. Please refer to the figures in the attached PDF in the response to all reviewers. This supports our key message that (3.2) represents a unique coefficient design for DDPM in achieving dimension-independent error.

Dependency on $\log d$. Thank you for raising this point! The polylogarithmic dependency w.r.t.~the ambient dimension $d$ arises from the analysis tools that allows us to characterize the algorithmic dynamics in a more deterministic manner. This analysis framework is crucial for tackling the convergence of DDPM in the presence of low-dimensional structure.

In the proof, we identified a "typical" high-probability set where we are able to characterize the evolution of conditional density precisely (see our discussion at the beginning of Section 4). However, the algorithmic dynamic outside this set is difficult to track, and we have to bound some quantities related to the dynamics outside the typical set at the order of $d$. As a result, we have to set the radius of the "typical" high-probability set to be large enough (larger than some logarithmic factor of $d$), such that the exceptional probability is small (e.g., smaller than $O(1/\mathsf{poly}(d))$ in order to offset the impact of these terms. We think it might be possible to improve the polylogarithmic dependency on $d$ via more refined analysis, and we leave it to future investigation.

Discussion on coefficient design. Thank you for the suggestion! We have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions. Please see our response to all reviewers for this general lower bound, as well as an outline of the proof. We believe that this general result can help us understand the role of our coefficient design (2.4), as well as why earlier designs get the dimension-dependent error. To facilitate discussion, we copy the lower bound here: \\mathbb{E}_{x\_{t}\sim q\_{t}}[\\mathsf{KL}(p\_{X\_{t-1}|X\_{t}}(\\cdot| x\_{t})\\parallel p\_{Y\_{t-1}|Y\_{t}}(\\cdot| x\_{t}))] \\geq \\bigg(\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} + 2\\log\\frac{\\sigma\_t}{\\sigma\_t^\\star}- 1\\bigg)\\frac{d}{2} + \\frac{c\_0(\\eta\_{t}-\\eta\_{t}^{\\star})^2d}{2\\sigma\_{t}^{2}(1-\\overline{\\alpha}\_t)} - C\_{5}^2\\frac{k^{4}\\log^{6}T}{T^2}\\bigg(3+\\frac{\\sigma\_{t}^{\\star2}}{\\sigma_t^2}\\bigg) - C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\bigg|\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} - 1\\bigg|\\sqrt{d} - \\exp(-c\_1k\\log T) This bound is achieved by a novel set of analysis tools that characterize the algorithmic dynamics in a more deterministic manner, which together with our analysis in Theorem 1 provide a sharp characterization of the impact of coefficient design (i.e., $\eta_t$ and $\sigma_t$) in determining the error induced in each denoising step. It can be seen that, unless we take $\eta_t=\eta_t^\star$ and $\sigma_t=\sigma_t^\star$ as suggested in (2.4), there will be inevitable error that scales at least linear in $d$ incurred in each denoising step.

I thank the authors for providing the detailed rebuttal and also providing the additional experiment for the uniqueness of the coefficient.

• I understand some of the explanations provided by the authors but as authors mentioned, each pixel is normalized between 0 to 1 or -1 to 1. If we think of each pixel as a coordinate in the input, then the norm of the input is typically $O(\sqrt{d})$ but the result is proven under the assumption that norm of the input is $poly(T) = poly(k, log(d))$.
• The experiments on the synthetic data are interesting. Can you provide more details on the baseline choices for $\eta_t$ and $\sigma_t$? The original DDPM paper [1] uses different $\alpha_t$ and $\sigma_t^2 = \sqrt{\alpha}_t \beta_t$ (note that the definition of $\sigma_t$ differs in this work and the original work). The follow-up work [2] also seems to have different choices than $\eta_t$ and $\sigma_t$ than the one used in the above experiment so can you provide some of the references that use the choices ($\eta_t = \sigma_t = 1-\alpha_t$)?

[1] Denoising Diffusion Probabilistic Models

[2] Improved Denoising Diffusion Probabilistic Models

Thank you for your reply!

On the $d$-dependence. Thanks for the insightful comment. We agree that the norm of the input image $X_0$ is typically $\sqrt{d}$. However this won't affect our main message, and the reason is as follows:

• Our paper requires that, for some fixed (arbitrary) constant $c_R$, the norm of $X_0$ is bounded by $T^{c_R}$. This means that we need $T \geq d^{1/(2c_R)}$. Since $c_R$ can be chosen arbitrarily, this is weaker than any polynomial dependence on $d$.
• In fact, we can see that the $d$-dependence in this requirement can be removed at the price of an additional $\log d$ factor in the final error bound. Although we treat $c_R$ as a universal constant in the current paper and hide its dependence in Theorem 1, the final upper bound in Theorem 1 actually depends polynomially on $c_R$ as follows: $\\mathsf{TV}\\left(q\_{1},p\_{1}\\right)\\lesssim c\_R^2\\frac{\\left(k+\\log d\\right)^{2}\\log^{3}T}{\\sqrt{T}}+\\varepsilon\_{\\mathsf{score}}\\log T.$ We will make this dependence explicit in the next revision. If we take $c_R \asymp \log d$, then our error bound becomes larger by a factor of $\log^2 d$, which is still nearly as good as the current one. However, notice that $d^{1/\Omega(\log d)} = O(1)$, the requirement $T \geq d^{1/(2c_R)} = O(1)$ is independent of $d$.

On the choices of $\eta_t$ and $\sigma_t$. Thanks for raising this point. We use the same $\eta_t$ as [1] and [2], and we agree that the choices of $\sigma_t$ in [1] and [2] are different with our choices in the experiment. Here, [1] chose $\sigma_t^2 = \alpha_t\beta_t$, while our choice is $\sigma_t^2 = \beta_t$. We use this type of $\sigma_t^2$ as our baseline, since it is commonly adopted in the theoretical literature (e.g., [3]) and has been shown to achieve $\mathsf{poly}(d)/T$ convergence. In addition, we have also implemented the choice $\sigma_t^2 = \alpha_t\beta_t$ in [1] in the numerical experiments, and the performance is very similar to using $\sigma_t^2 = \beta_t$. We will include this result in our next revision. Our lower bound based on the degenerated Gaussian distribution also show that this choice $\sigma_t^2 = \alpha_t\beta_t$ will incur some error that is linear in $d$.

Note that $\sigma_t^2$ in [2] is learned from the dataset in the hope of achieving optimal performance, which takes a different approach from our current work, where we intend to identify the coefficients based on the learning rates of the forward process (i.e., $\alpha_t$'s) in a non-data-driven way. will discuss this point more clearly in the next revision.

[3] Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models, G. Li, Y. Wei, Y. Chen and Y. Chi, ICLR 2024.

Thank you for your review. We address your comments below.

Intuition for our coefficient design. Thanks for raising this point. We have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions. Please see our response to all reviewers for this general lower bound, as well as an outline of the proof. We believe that this general result can help us understand the role of our coefficient design (2.4). To facilitate discussion, we copy the lower bound here: \\mathbb{E}_{x\_{t}\sim q\_{t}}[\\mathsf{KL}(p\_{X\_{t-1}|X\_{t}}(\\cdot| x\_{t})\\parallel p\_{Y\_{t-1}|Y\_{t}}(\\cdot| x\_{t}))] \\geq \\bigg(\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} + 2\\log\\frac{\\sigma\_t}{\\sigma\_t^\\star}- 1\\bigg)\\frac{d}{2} + \\frac{c\_0(\\eta\_{t}-\\eta\_{t}^{\\star})^2d}{2\\sigma\_{t}^{2}(1-\\overline{\\alpha}\_t)} - C\_{5}^2\\frac{k^{4}\\log^{6}T}{T^2}\\bigg(3+\\frac{\\sigma\_{t}^{\\star2}}{\\sigma_t^2}\\bigg) - C\_{5}\\frac{k^{2}\\log^{3}T}{T}\\bigg|\\frac{\\sigma\_{t}^{\\star2}}{\\sigma\_t^2} - 1\\bigg|\\sqrt{d} - \\exp(-c\_1k\\log T) This bound is achieved by a novel set of analysis tools that characterize the algorithmic dynamics in a more deterministic manner, which together with our analysis in Theorem 1 provide a sharp characterization of the impact of coefficient design (i.e., $\eta_t$ and $\sigma_t$) in determining the error induced in each denoising step. It can be seen that, unless we take $\eta_t=\eta_t^\star$ and $\sigma_t=\sigma_t^\star$ as suggested in (2.4), there will be inevitable error that scales at least linear in $d$ incurred in each denoising step.

Comparison with other coefficient designs. Thank you for raising this point. In the prior work [3], the marginal distribution of the forward process is $X_{t_k} \sim e^{-t_k}X_0 + \sqrt{1-e^{-2t_k}}\,\overline{W}$ where $\overline{W}\sim\mathcal{N}(0,I_d)$. This means that $e^{-2t_k}$ plays the role of $\\overline{\\alpha}\_t$ in our paper. By examining their discretization rule (see Eq.~(4) therein), we find that they use the following update rule:

where $\Delta_t = \frac{1}{2}\log\frac{1}{\alpha_t}$. By applying a similar calculation as in Theorem 2, we can show that:

Hence, the coefficient design in [3] will also incur dimension-dependent error in each denoising step. We will incorporate these discussions in our next revision.

Approximately low-dimensional structure. Thank you for raising this point. We first would like to clarify that we are not assuming that the data distribution is exactly low dimensional. Our characterization of low-dimensionality is based on the covering number of the support, as defined in Section 2, which accommodates approximately low-dimensional structure. For example, our setup includes the case that $\mathsf{supp}(p_\mathsf{data}) \in \cup_{i \le N_{\varepsilon}} \mathbb{B}(c_i, \varepsilon)$, the balls centered at $c_i$ with $\varepsilon$ radius, whose dimension is $d$ instead of $k$. Therefore even if the support of the data distribution is not exactly low-dimenaional, our results can still be applied. (We apologies if we misunderstood your question.)

It is an interesting question whether our result is stable against adding an $\varepsilon$-mass outside the cover. This setting is beyond our current result, since this mass can be spread out in the full space (thus having large covering number that depends on $d$). We conjecture that our result will be stable to this perturbation, namely it is possible to show an error bound similar to Theorem 1, but has an additional term proportional to $\varepsilon$ (or $\varepsilon d$). Currently, we don't know how to prove this result, and we leave this for future investigation.

Improving the quartic dependency on $k$. Thank you for raising this point. Currently, we don't know how to improve this dependency, which we believe requires new analysis frameworks and tools. We leave this for future investigation.

Thank you for your review. We address your comments below.

Bounded assumption on the target distribution.

• We agree that the bounded support assumption is stronger than, for example, the bounded second moment assumption, and it excludes Gaussian distributions. However, we argue that this condition is satisfied in most practical scenarios. Arguably, the most important applications of diffusion models are to generate new images from a target distribution, where image data is naturally bounded. For instance, the CIFAR and ImageNet datasets consist of images with pixel values ranging from 0 to 255 or $[0, 1]$, and it is common to normalize them to the range $[-1, 1]$. Then the $\ell_2$ norm of an image from, e.g., the CIFAR dataset, is typically below $60$. Moreover, for DDPM in image generative tasks, $T$ is typically around $100$. Hence, we believe it is reasonable to assume in theoretical analysis that the radius of the data distribution is bounded by $T^{c_R}$, where $c_R$ is any given fixed constant that can be very large.
• We acknowledge that it is unfortunate not to cover common distributions like the Gaussian. Although we believe the bounded support assumption is not essential, it greatly facilitates our analysis, especially since we use a novel set of analytical tools that characterize the dynamics of DDPM in a more deterministic manner to establish convergence guarantees in the presence of low-dimensional structure. While we can relax this assumption in some specific cases (e.g., for Gaussian distribution, as illustrated in the next paragraph), we find it challenging to achieve a clean and concise result that holds generally for any distribution with a finite second moment. We leave this to future investigation.

We will incorporate these discussions in our next revision.

Truncating Gaussian distribution in the lower bound. We agree that the degenerated Gaussian distribution considered in Theorem 2 is not a good example because it is unbounded. As we mentioned in footnote 2 on page 5, this lower bound can be extended to the truncated Gauss distribution. We have changed the result to truncated Gaussian in the following.

Before presenting the details, we also want to highlight that we have extended Theorem 2 to a general lower bound that works for arbitrary low-dimensional data distributions, which we believe also helps addressing this comment. Please see our response to all reviewers for this general lower bound, as well as an outline of the proof. Now we continue presenting results for the truncated Gaussian.

Let $X_0 \sim \mathcal{N}(0,I_k)$, and define its truncated counterpart $\\widetilde{X}\_0$ as

Define $\\widetilde{X}\_t = \\sqrt{\\alpha\_t}\\widetilde{X}\_{t-1} + \\sqrt{1-\\alpha\_t}Z\_t$, and construct the reverse process $\\widetilde{Y}\_t$ with score estimation of $\\widetilde{X}\_t$. Then we can establish exactly the same lower bounds for $\\widetilde{X}\_t$ and $\\widetilde{Y}\_t$. Notice that $\\widetilde{X}\_t$ and $\\widetilde{Y}\_t$ have independent entries, hence it suffices to studying each entry separately (we use $\\widetilde{X}\_{t, i}$ and $\\widetilde{Y}\_{t, i}$ to denote their $i$-th entry), i.e.,

The right hand side of the above inequality obeys

where the first relation holds since the truncation does not affect the entries with zero variance, and the second relation is proved in Line 550-552 in Appendix B.

Empirical demonstration. Thank you for raising this point. We have conducted a numerical experiment using the data distribution considered in Theorem 2. The results demonstrate that the TV error and KL divergence are independent of the ambient dimension $d$ under our coefficient design (2.4), while they grow with $d$ under other widely-used designs. Please refer to the figures in the attached PDF in the response to all reviewers, where we plot the error curves of $\mathsf{KL}(q_1\parallel p_1)$ and $\mathsf{TV}(q_1,p_1)$ versus $d$, with all other setups fixed. This supports the conjecture that (2.4) represents a unique coefficient design for achieving dimension-independent error.

While the lack of GPUs prevents us from examining this design in more complex, large-scale tasks, we believe that our theoretical findings and empirical observations are already meaningful and interesting.

Our use of $\varepsilon$-covering. Thanks for raising this point! While we believe that it's a good idea to use covering number for characterizing low-dimensional structure in our problem, we are not aware of other existing literature that does the same. We choose to use $\varepsilon$-net and covering number to define approximate low-dimensional structure because we believe that this is less stringent and more general than assuming an exact low-dimensional structure (e.g., by assuming that the support of the data distribution lives in a low-dimensional subspace). As a sanity check, we showed in Section 2 that when the support of the data distribution lives in an $r$-dimensional subspace, our intrinsic dimension $k$ defined through covering number is of order $r$, confirming that our definition is indeed more general. We will incorporate these discussions in our next revision.

Thank you for your review. We address your comments below.

Comparison with prior works. Thank you for the reference. These two works and the current paper approach the diffusion model from different perspectives, making direct comparison challenging. Specifically, the two prior works establish error bounds for estimating density under the assumption that the true target density meets certain smoothness conditions. Their results rely on a score-matching procedure designed based on the level of smoothness, situating their findings within the context of nonparametric statistics.

In contrast, our paper approaches the problem from an applied mathematics perspective, decoupling the error of DDPM into discretization error and score matching error, and characterizing them separately, akin to prior works [3, 4, 6, 13]. Our results assume minimal conditions on the target distribution, avoiding smoothness assumptions, and accommodating arbitrary score-matching procedures. Therefore, our results cannot be directly compared with these prior works.

Our paper does not require knowledge or estimation of the manifold, and our error bound is expressed as the sum of discretization error and score matching error:

When a subspace is given a priori, we believe it will not help in improving the discretization error bound, as it already adapts to the low-dimensional structure automatically. While there might still be room for improvement (e.g., reducing the polynomial dependency on $k$), we believe this requires new analytical tools rather than assuming access to the low-dimensional structure. However, knowing the subspace can aid in improving the score-matching error, as it is possible to exploit the subspace information to design an efficient score-matching procedure that achieves a smaller $\varepsilon_{\mathsf{score}}$. This, however, is not the main focus of our paper, as our result accommodates any score-matching procedure, which we believe is more general. We leave this for future investigation.

We will incorporate and discuss these references in our next revision.

Extending the lower bound to arbitrary data distribution. Thank you for raising this point. As far as we know, it is quite general to use the worst-case error (or risk) to characterize the inherent difficulty of a problem in areas like statistics (e.g., minimax lower bound) and optimization (e.g., algorithmic lower bound). We believe that establishing a lower bound for the (degenerated) standard Gaussian distribution effectively illustrates our point: if the algorithm cannot perform well without using the proposed coefficient design in probably the simplest case, we can hardly expect it to work well in more complicated examples. However, the good news is that for this problem, we can actually show a similar lower bound for arbitrary low-dimensional data distributions. Please see our response to all reviewers for this general lower bound, as well as an outline of the proof. We will include this result in our next revision.

Regarding the gap between our lower bound and the TV error. Thank you for raising this point. First, we would like to point out that we actually have an upper bound for the KL divergence between $q_1$ and $p_1$. In the analysis, we control $\mathsf{TV}(q_1, p_1)$ by bounding $\mathsf{KL}(q_1\parallel p_1)$ (see Eq.~(3.2)). Then the established KL lower bound in Theorem 2 is meaningful. We will added the KL divergence bound in our main result.

In addition, the lower bound for KL divergence can also be extended to TV distance. According to the calculation in Appendix B (see Line 545 and 547), we know $p_{X_{t-1}|X_t}$ and $p_{Y_{t-1}|Y_t}$ are two gaussian distributions. Then with basic calculations, it can also be shown that

We will also include this result in the next revision.

Finally, due to the lack of GPUs, we conducted a numerical experiment using the data distribution considered in Theorem 2. The results demonstrate that the TV error and KL divergence are independent of the ambient dimension $d$ under our coefficient design (2.4), while they grow with $d$ under other widely-used designs. Please refer to the figures in the attached PDF in the response to all reviewers, where we plot the error curves of $\mathsf{KL}(q_1\parallel p_1)$ and $\mathsf{TV}(q_1,p_1)$ versus $d$, with all other setups fixed. This supports the conjecture that (2.4) represents a unique coefficient design for achieving dimension-independent error.

Thank you for the reply! We are not sure whether we understand the "prior distribution" in your comment correctly. Please let us know if we misunderstood anything.

• First, we would like to clarify that the only assumption we imposed on the target distribution $p_{\mathsf{data}}$ is that it has bounded support. We do not need any further assumption, e.g., absolute continuousness, in order to establish our results. In what follows, we will explain why we don't need to worry about the explosion or error, both in the upper bound (Theorem 1) and lower bound (Theorem 2).
• Regarding the upper bound in Theorem 1, our error metric is the TV distance between the distribution of $X_1$ and $Y_1$ (i.e., $q_1$ and $p_1$), which are both absolutely continuous w.r.t.~the Lebesgue measure (i.e., they both have densities). This circumvents any potential issue when the data distribution $p_{\mathsf{data}}$ of $X_0$ is not continuous. Since $X_0$ and $X_1$ are exceedingly close (since $\beta_1=T^{-c_0}$ is vanishingly small), this error metric also reflects the closeness of the generator distribution and the target distribution.
• The generalized lower bound stated in the rebuttal is established for the error incurred in each denoising step, which is defined as the expected KL divergence between two conditional distributions $p_{X_{t-1} | X_t}$ and $p_{Y_{t-1} | Y_t}$, for $2\leq t \leq T$ (again, it does not concern $t=1$ to circumvent the case when the data distribution is not absolutely continuous). These two distributions are both absolutely continuous w.r.t.~the Lebesgue measure (i.e., they both have densities), regardless of whether the target distribution $p_{\mathsf{data}}$ of $X_0$ is absolutely continuous or not.
• To further support our claim above, we would like to mention that prior works [3,4,6,13] showed that even without using our coefficient design (2.4), other reasonable coefficient designs also lead to convergence rates $\mathsf{poly}(d)/T^2$ for the error incurred in each of the denoising steps (and they sum up to an overall error $\mathsf{poly}(d)/T$). This also suggests that the error in the denoising steps will not explode even if $p_{\mathsf{data}}$ is not continuous -- they just suffer from dependence on the ambient dimension $d$.
• While our upper bound is established under the specific time schedule (i.e., $\beta_t$'s) in Section 2, the lower bound, including the one for degenerated Gaussian as well as the generalized one, holds for a reasonably large class of time schedules (only with the exception of some corner cases). We will specify this in our next revision.

We are happy to discuss more details with you in case you have concern on the generalized lower bound. Nevertheless, as we discussed in the rebuttal, we believe that our original lower bound established for a simple example (degenerated Gaussian) already effectively illustrates our point. We present the generalized lower bound in the rebuttal just because we think it is a beautiful, concise, yet powerful result that can make the paper better.