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

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

Thank you for your response! **Uniform distribution over sphere.** Yes, our proof and result can be applied to a uniform distribution over sphere, since the only assumption we imposed on the data distribution $p_{\mathsf{data}}$ is boundedness. However, the intrinsic dimension $k$ of, e.g., the unit sphere $\mathbb{S}^{d-1}$ in $\mathbb{R}^d$ is $d-1$, which is not a typical low-dimensional structure. Although our theory holds for general $k$, the most interesting regime is $k\ll d$, where our results significantly improve the convergence rate that has polynomial dependence on $d$. **Using covering number to characterize intrinsic dimension.** Thank you for asking this. Here we provide some related literature and discussion on this issue. * In fact, our definition of the intrinsic dimension $k$ is actually the metric entropy of $\mathcal{X}$, the support of $p_{\mathsf{data}}$. Metric entropy is defined using covering number, and is widely used in statistics and learning theory to characterize the complexity of a set/class in a metric space, which is useful in proving sample complexity and generalization bounds for algorithms; see e.g., Sections 5 and 14 in [1] for the reference. The low-dimensionality is also a concept of complexity, therefore we believe it is very natural to use covering number, or metric entropy to characterize the intrinsic dimension. * Prior literature [2], which studied diffusion model on low-dimensional data, assumes that the data is supported on a low-dimensional linear subspace. More generally, another work [3] assumes that the distribution is supported on a union of low-dimensional linear subspace. As we discussed in Section 2 and in the rebuttal, our intrinsic dimension $k$ defined through covering number is of order $k$ for a $k$-dimensional linear subspace, and we can also easily seen that $\sum_{i=1}^{m} k_i$ for the union of $m$ linear subspace (each with dimension $k_i$). Therefore using covering number to characterize intrinsic dimension actually admits the setup in these prior literature as special examples, and is more general and robust. The discussion phase is due to conclude in 20 hours, and we would like to know whether our response has appropriately addressed your questions and concerns about our paper. If we have addressed your concerns, we would appreciate it if you consider increasing your score for our paper. Please let us know if you have further comments or concerns about our paper. Thank you! [1] High-Dimensional Statistics: A Non-Asymptotics Viewpoint, M. J. Wainwright, Cambridge University Press, 2019. [2] Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data, M. Chen, K. Huang, T. Zhao, M. Wang, ICML 2023. [3] Robust Subspace Clustering, M. Soltanolkotabi, E. Elhamifar, E. J. Candes, Annals of Statistics, 2014.