Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a theoretical analysis of SGMs that extends Chen et al. (2022c) and the bad set approach from (Lee et al., 2022a).

Compared to Chen et al. the analysis is much more general in a number of ways, and compared to Lee et al. the analysis relaxes an LSI assumption and is applicable to a larger class of generative models (CLD).

More concretely, the claimed contributions are:
- more general analysis without LSI assumption and applicable to CLDs
- particularly interesting special case for distributions with a bounded support (which remove the necessity for a restrictive assumption of Lipschitz score estimate)
- tight iteration complexity 
strength_and_weaknesses: Despite the strong claims, the paper seems to deliver on most aspects so everything listed in the summary of contribution should be considered as a core strength of the paper.

However each of the strong point presents some slight limitations that could be adressed more clearly.

1) Removing the LSI assumption is a strong result, but ends up introducing new assumptions of smoothness, bounded moment, and of accurate estimation of the score function
1.a) As the authors explain in the paper, this smoothness assumption is not satisfied when the input distribution lies on a manifold, which is probably the same regime where the accurate score function estimation is feasible at all. However most current SGM models also implicitely assume that q has full support, highlighting that this might be a limitation of the whole field. To make the analysis more relevant the failure modes of the theoretical analysis should shed some light on which modifications should be introduced in the models and training procedures to relax this assumption and be able to automatically detect the manifold and avoid this pitfall, but this would be an important contribution by itself. The authors instead give a good second choice by looking at a simplified but realistic model where the distribution lies in a ball around the origin. However the number of iterations grow quite quickly with the radius (e.g. ~R^8) making it vacuous.
1.b) The accurate estimation of the score function is the central point of the paper, but the authors spend very little time explaining how this quantity is computed. Beyond a quick description of score matching, they mostly refer the reader to Vincent 2011, but this source actually highlights how minimizing (13) is actually very hard even after the score matching rewriting, and the authors even mention hardness results at the end of page 2. It would be good to point out some more context on when this estimation problem can be solved in an efficient manner.
1.c) Unlike the other assumptions that are discussed mutliple times in the paper, the moment assumption receives very little attention. For example, the authors should try to justify why their proposed bound of m_2 < d in the discussion of Thm. 2 should hold, especially considering a bound e.g. m_2 < d^2 would result in different value for N and eps_score than the ones reported in the introduction.
clarity,_quality,_novelty_and_reproducibility: The paper is very clear, despite the complex subject. It goes at great lengths to highlight strengths of the contributions without downplaying the limitations. The appendix is very thorough.

Quality and reproducibility are both acceptable, but less obvious. In particular the quality (which usually for theoretical works corresponds to impact of the result and technical complexity of the novel tools) is made more confusing by the fact that the proof heravily rellies on Chen et al. (2022c) and the bad set approach from (Lee et al., 2022a). While the introduction makes an excellent work in describing how this paper improves over existing results in terms of generality, Sec. 4 could be streamlined to highlight better which novel technical contribution is introduced to improve over existing results. It seems to me that the core of the proof relies on a novel reduction from L_2 to L_infty which then allows to invoke results from (Lee et al., 2022a), but the authors do not clearly state if this reduction already existed in the literature. 

Regarding reproducibility, the paper includes a 15 page appendix that heavily relies on two extremely recent results in Chen et al. (2022c) and (Lee et al., 2022a). Chen et al. (2022c) has been peer-reviewed, but for (Lee et al., 2022a) I could not find a peer-reviewed evaluation at all, requiring me to take their results at face value or have to review another 42 page work. This is not an immediate issue with the reproducibility of the result, but it does make it slightly less suitable to a venue with a short publication cycle like ICLR. 
summary_of_the_review: Overall I think the paper introduces very strong, novel results that give a good foundation for the study of SGMs. Some limitations are present but they are to be expected due to the short format of the conference. Overall I think it's clearly above the bar for ICLR, but due to the close ties to several recent works it would be good to highlight more what separates the tools used in this paper with previous results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides convergence bounds for score-based models under the assumption that score estimate is $L^2$ accurate. Provided that, the paper derives some remarkable bounds for the score-based sampling methods under pretty weak assumptions.
strength_and_weaknesses: Strength: The results are pretty impressive given the state of the field.

Weakness: The results shown under the manifold hypothesis seem incomplete.
clarity,_quality,_novelty_and_reproducibility: Clearly written and novel results.
summary_of_the_review: The paper reads well and presents important results which provides clarity to the field. I have the following comments for the authors:

1) It looks like their rate matches the convergence of Langevin diffusions to the target measure under the LSI assumption - but without any stringent assumption on the target (just good score estimates). However, intuitively (or fundamentally), it was left unclear what actually enables this. Perhaps this is not so surprising, since the forward diffusion starts from actual samples from the target (rather than, like in a classical setting, from an arbitrary point in space) - and provided that the gradient is well estimated, sampling does not require any assumptions. Can authors comment clearly about the differences between their setup and a regular Langevin sampling setup where the initialisations are from arbitrary distributions? This can be perhaps done by assuming no gradient error (exact gradients) and discussing the difference between a Langevin diffusion sampler and a forward-backward score based sampler.

2) It would be also nice if the authors clarified the Remark after Corollary 4. As showed in multiple prior works, the real world data structure supports the manifold hypothesis -- therefore, the impressive convergence results presented in the first part may not apply, as authors pointed out (but still valuable). The remark states that a unified error bound can be obtained in the bounded Lipschitz metric but this was not completed. It would be nice if this is done.

3) Assumption 2 might be OK, assuming finite datasets, however, in a realistic setting where the data stream is observed, this may not hold. Can authors comment if this assumption can be relaxed and at what cost?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work provides a convergence guarantee for using a score-based diffusion model to sample from an arbitrary distribution. The method has significantly looser assumptions than previous work, and accounts for three sources of error: (1) L2 score estimation error, (2) discretization of the reverse SDE sampling algorithm, and (3) initializing the algorithm from noise rather than the true resulting distribution from the forward diffusion process. 


strength_and_weaknesses: Strengths:
- Well-written and presented clearly.
- Clearly discusses the relationship to other work in this area. While I am not an expert in the area, I thought this was especially well-done. 
- Bound is in terms of the L2 error of the score estimate.
- Bound does not assume log-concave data distribution.
- Assumptions and limitations of the results are described clearly.
- Explores the consequences of this result with respect to critically damped Langevin diffusion, a variant of the simpler diffusion process.
clarity,_quality,_novelty_and_reproducibility: This paper is exceptionally clear and well-written, considering that it is a theoretical analysis. I am not an expert in this field, so I am not the best judge of the novelty, but the author's take care to clearly explain the relationship to prior work. 
summary_of_the_review: While this is a very technical paper, there is immense interest in diffusion models. I expect this will be of high interest to the community.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper examines the convergence of SGMs under fairly general assumptions. The main novelty compared to existing works is the $L^2$ error assumption on the score estimates, as opposed to the more common $L^\infty$.The main conclusion is that one can basically reduce the difficulty of SGMs to estimating the scores since the sampling part afterward is relatively easy: the authors proved a convergence bound that scales polynomially with respect to the relevant parameters. Extention to CLD is discussed.
strength_and_weaknesses: Strength:

- The presentation is clear.

- The proof ideas are simple and fairly straightforward. As the authors mentioned, they seem robust enough to generalize to other settings beyond the OU process considered in the present work.

Weaknesses: 

- This paper does not really deal with DDPM in the sense of the cited (Song et al. 2021b). First, at least in (Song et al. 2021b), DDPM refers to a specific SDE with time-inhomogeneous diffusion. Although the authors briefly mention that the analysis can be extended to that case, I don't think it is such a straightforward matter. For instance,  the first step in Section 4 would break down, as $\tilde{p}_0 \neq \gamma^d$. How do we handle this? 

    Another major difference is, in (Song et al. 2021b), the sampling part is done by a predictor-corrector sampler; see Appendix G. Incorporating this source of error is quite important as it does reduce the variance of the sampling procedure significantly. Instead, the authors opted for an exact sampler by taking advantage of the time-inhomogeneous OU process, which, echoing the above, is not available for DDPM.



- One thing that is unclear to me is the scaling issue as follows. Since both TV and KL are invariant to scaling, instead of $q(x)$ one may consider a new measure $q(cx)$ for any $c >0$. Inspecting the bound in Theorem 2, it is clear that the first term is invariant, the second moment in the second term scales accordingly, whereas the $\varepsilon_{\text{score}}$ term is again left as constant. On the other hand, intuitively, as $c\rightarrow \infty$ the error in the score estimate might shrink (since this corresponds to shrinking the moments of $q$).

    To conclude, the bound in Theorem 2 doesn't seem to capture the scale invariance of TV/KL, suggesting that there might be some artifact in the proof. (That being said, I acknowledge that my argument above is no less vague than the authors', so this should not be taken as a major criticism.)

- I find the argument on the deficiency of underdamped Langevin fairly weak. On one hand, as the authors have noticed, no definitive statement is given. On the other hand, all of the bounds in this paper are either given by KL or TV, but these two are not really the "right" metric for underdamped Langevin (Desvillettes and Villani 2000).

- The comparison to (De Bortoli 2022) is not entirely fair since the convergence metric there is given in the Wasserstein distance, which makes sense under the manifold hypothesis. The Wasserstein distance is ideal for this setting as it does not rely on the measures being absolutely continuous to each other.

- As the authors acknowledged, a serious limitation is that the score estimate part is assumed away, whereas in practice estimating the score is the bottleneck.



Desvillettes and Villani 2000, On the trend to global equilibrium in spatially inhomogeneous entropy-dissipating systems: The linear Fokker-Planck equation.
clarity,_quality,_novelty_and_reproducibility: The presentation is clear except for a few minor issues below:
 
- The statement "LSI is slightly weaker than log-concavity" is misleading.

- Footnote on p.3: The error is fixed in the lastest version of (Block et al. 2020); see the new Proposition 21.

- I'm not sure why $\sigma_t$ is needed in Section 2.1. The authors never invoked $\sigma_t\neq \sqrt{2}$.

- The result of the overdamped Langevin process on p.5 is only for strongly log-concave distributions. The general implication is unclear.

summary_of_the_review: This paper provides several convergence results for diffusion models with OU process. I think this is a solid paper, but can be significantly improved if the authors can:

1. prove results on DDPM or other SDEs in (Song et al. 2021b).

2. provide more context on the related work, for instance (De Bortoli 2022).

3. figure out the scaling issue.

4. improve the section on CLD.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper derives theoretical convergence guarantees showing that diffusion models can sample from (almost) any data distribution with minimal assumptions on the underlying data distribution, and assuming that an L2-accurate score estimate is learned. Compared to prior works in this space, this submission removes restrictive assumptions that often don't apply to many real-world data distributions and it matches the complexity guarantees for the Langevin diffusion. The paper is extremely well written, making it more accessible to those less familiar with the theoretical analysis of diffusion models. The reviewers have uniformly recognized the significance of this work, and the AC is happy to recommend accept. 
justification_for_why_not_lower_score: The paper makes significant contributions to understanding diffusion models. All the reviewers have uniformly rated the paper as a good paper.
Decision: Accept: notable-top-5%