We provide the first polynomial-time convergence guarantees for the probability flow ODE implementation (together with a corrector step) of score-based generative modeling. Our analysis is carried out in the wake of recent results obtaining such guarantees for the SDE-based implementation (i.e., denoising diffusion probabilistic modeling or DDPM), but requires the development of novel techniques for studying deterministic dynamics without contractivity. Through the use of a specially chosen corrector step based on the underdamped Langevin diffusion, we obtain better dimension dependence than prior works on DDPM ($O(\sqrt{d})$ vs. $O(d)$, assuming smoothness of the data distribution), highlighting potential advantages of the ODE framework.
Paper
References (54)
Scroll for more · 38 remaining
Similar papers
Peer review
Summary
In this work, authors propose improved solution scheme with the specially chosen corrector step for the the score-based generative models. Within the denoising diffusion probabilistic modeling (DDPM) and the underdamped Langevin diffusion approach authors obtain better dimension dependence within certain restrictions on the smoothness of data distribution (Algorithm DPUM) than prior works.
Strengths
1. Score-based generative models today are of great interest to the scientific community, while the theoretical establishment of their capabilities and limitations is a powerful impetus for the further development of new effective methods. The extensive analysis carried out in this work is certainly relevant and of direct interest to researchers. 2. The work is well structured, written in a great style and easy to read. 3. The provided approach with the polynomial-time convergence guarantees for the probability flow ODE seems to be essential if it will be successfully implemented in practice and applied to the real-world data.
Weaknesses
Given the high level of theoretical consideration carried out in the work, I am confused by such a weak study of the experimental part: 1. It seems that a (at least brief) description of the performed numerical experiments should be included as a section of the main text (in the presented text, numerical experiments are contained exclusively in the appendix). 2. I do not quite understand the conclusions that can be drawn from the only simple numerical experiment presented in the appendix for artificially generated data from a mixture of Gaussians. Does the proposed theoretical estimate of the convergence of the method hold in this case? How to interpret a word "approximately" in [Line 721, appendix]: "DPUM is able to provide samples (approximately) from the target distribution"? Can any quantitative conclusions be drawn from the experiment? Is it possible to do some form of convergence analysis and make a comparison with the baseline? 3. Can numerical experiments be done on real-world datasets using a neural network ([Line 130]: "the score estimates are produced via a deep neural network"; [Line 723, appendix]: "recall that we experiment without score error")?
Questions
Please see the section "Weaknesses" above. I have only one more minor comment: [Line 123] for clarity, it may be worthwhile, in addition to the dimension of the noise, to also indicate the dimension of the x variable.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The proposed approach is based on the assumption that the score functions along the forward process are Lipschitz continuous, and it does not cover non-smooth distributions. However, the authors note that this limitation can potentially be circumvented by using the early stopping technique.
Summary
This paper provides polynomial-time convergence guarantees for the probability flow ODE implementation. This paper obtains a better better dimension dependence than prior works on DDPM. However, there is no experiments to prove the effectiveness of the proposed methods.
Strengths
1. The paper is well written. 2. The theoretical results are solid.
Weaknesses
1. No experiments are performed to prove the proposed method. I think it is necessary to evaluate the method of diffusion models, such as Stable Diffusion or DeepFloyd. I admit that the theoretical results presented in this paper might be important, but that is not the reason of the lack of experiments. 2. The proposed method has an extra corrector step, which further introduces extra computational costs. 3. Some comparisons with previous sampling methods (DPM-Solver++, DEIS, etc) are missing.
Questions
Please see the weaknesses.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
The limitations have been fully discussed.
Summary
The authors proposed the convergence guarantees for the probability flow ODE implementation. Through the use of a specially chosen corrector step based on the underdamped Langevin diffusion, a better dimension dependence of $O(\sqrt{d})$ than DDPM $O(d)$ is achieved.
Strengths
1. the theoretical comparison between probability flow ODE and DDPM is less studied in the community. In this sense, analyzing the advantage of the ODE-based method brings new insight to the community. 2. solid and clean derivations.
Weaknesses
1. the term of fast looks a bit confusing to me. It is fast in inference or training? they have different meanings. As provided in the ranking: https://paperswithcode.com/sota/image-generation-on-cifar-10, **flow-based methods seem to perform quite mediocre in standard datasets**. So at least the claim of fast flow-ODE contradicts the fact of fast training in practice. Clarification is suggested. 2. Flow-based methods are known to work well in **low dimensions** and I am even suspecting it suffers from the curse of dimensionality. As such. I appreciate the authors' solid math techniques, but I personally believe that the advantage of the well-known smaller discretization error $O(\sqrt{d})$ v.s. $O(d)$ becomes **less interesting if it mainly adapts to low-dimensional problems** (see Q1 below). the authors can correct me if I am wrong. 3. The authors should point out the **limitations of probability-flow ODE methods** compared to DDPM so as not to confuse readers.
Questions
Q1. Do you know any popular real-world examples that probability-flow ODE works well in ultra-high dimensions in practice? Q2. Growall inequality does suffer from the exponential blowup. Q2.a) The authors propose to use the geometric contraction of the corrector (diffusion) step to control the exponential blowup. Is that right? Q2.b) Does it mean we can do lots of ODE steps but with only a few diffusion steps, the exponential blowup is still controlled in terms of complexity (ignore the constant) due to the contraction (closer to 1, e.g. alpha=0.999999999 also works, although the error / (1-alpha) is large)? Q2.c) Or do you need to maintain at least some amount of diffusion steps to make sure the bound hold? Minor: a relative work is missing and a short comment on this work would be appreciated: Provably Convergent Schrodinger Bridge with Applications to Probabilistic Time Series Imputation. ICML'23.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
NA
Summary
The current study offers a polynomial-time total variation convergence guarantee for score-based generative modeling, given that the generative process is a probabilistic Ordinary Differential Equation (ODE). This differs from previous work, which typically involves a reverse Stochastic Differential Equation (SDE). To the best of my knowledge, this is the first paper to present such results for an ODE-implemented score-based generative model targeting a general distribution without assuming log-concavity. The proof technique includes analyzing the discretization error of both the ODE and SDE, and employs the Score Perturbation Lemma to limit the error introduced by using estimated score functions. It's important to note that the convergence guarantee is provided for a modified version of the ODE-implemented score-based generative model. The authors have added an additional stochastic correction step to the deterministic dynamics, which is an unconventional approach.
Strengths
The results provided in the work is novel and important in my perspective. As mentioned in the summary, this is the first convergence guarantee for an ODE-based, score-based generative model for general target distributions that I am aware of (this could, of course, be due to my limited familiarity with the relevant literature). While some may contend that the additional stochastic correction step diminishes the impact of the work (given that the primary challenge of the proof is that the ODE transformation is purely deterministic, making Total Variation/Kullback-Leibler control nearly impossible), the theoretical framework employed remains significantly distinct from its SDE counterparts. The clarity of the writing and the structure of the proof are commendable. Despite the complexity of the paper, the proof is not difficult to follow, largely owing to a comprehensive preliminary introduction to the proof techniques. I particularly value the fact that the authors dedicated a significant portion of the text to discussing the limitations of some existing proof concepts, and made comparisons with similar intermediate results from the literature. This approach further underscores the contributions of this work.
Weaknesses
The inclusion of an additional stochastic corrector in the generative process is somewhat unsatisfying. To the best of my knowledge regarding score-based generative modeling via ODE, this correction step is not typically included in practice. One aspect that I believe is not clearly addressed in the current results is the comparison between the corrected and uncorrected generative processes. Ideally, there would be a result showing that the corrected process converges to the target faster. While it is mentioned in the paper that we cannot expect such a comparison in terms of Total Variation (TV) or Kullback-Leibler (KL) divergence - as without the stochastic correction, the TV/KL bound would be vacuous - could we not show such a comparison in terms of weak distance or even Wasserstein distance? (I've also raised some questions regarding the corrector in the Questions section.) Another minor shortcoming pertains to the toy numerical experiments presented in the study. It would have been more desirable if the authors had evaluated Algorithms 1 & 2 on actual image generation tasks and compared the performance of the corrected and uncorrected versions in these scenarios. While I admit it might seem somewhat unfair to expect this from a theory-oriented paper, such empirical evidence would undoubtedly render the study more comprehensive and impactful.
Questions
* Step 5 for Alg 1 and 2: Can authors provide some intuition on why geometric decreasing stepsize is needed for the prediction at the end given that correction step is used eventually? (I understand from the proof that when $t>1/L$, decreasing step size is required to control the ODE discretization error + approximated score error, but cannot form a practical intuition on this.) * In practice, which one of DPOM and DPUM is preferred? Or how does one choose the algorithm for practical applications? * Is it possible to get rid of the correction step for the convergence if the ODE discretization error is reduce by using more sphisticated numerical integrator (e.g., high order sympletic integrator)? Based on my superfluous understanding of the proof, the answer is probably NO since the key of the corrector is to obtain TV bounds based on Wasserstein bounds, intead of "correcting" the introduced error during the ODE simulation. This leads to my next question. * If intead of TV distance, all we care is just wasserstein distance, can we get rid of the correction step? Or is the correction step beneficial for a faster convergence?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
The author did note limitations or boundaries of the adopted techniques through out the proof (e.g., line 565 in Appendix C), and raised practical questions base on the theoretical framework.
Summary
In this article the authors propose polynomial-time convergence guarantees for probability flow ODEs related to score based generative models. Previous analyses on score based diffusion models have resorted to the use of SDEs and relied on properties of stochastic flows to alleviate error accumulation due to discretisation. Here the authors study the ODE counterparts of diffusion models. Since the deterministic dynamics are not contractive without log-concave assumptions on the data distribution, and thereby discretisation errors accumulate, the authors derive bounds for a modified process which requires interleaving deterministic integration steps (predictor) with stochastic (corrector) steps that smooths the reverse process, drawing inspiration from the purely stochastic framework of [4,9]. They propose two variants of the algorithm, one relying on overdamped Langevin dynamics with dimension dependence that scales as $\mathcal{O}(d)$ ,and one with underdamped Langevin dynamics that scales more favourably as $\mathcal{O}(\sqrt{d})$and thus has improved dimension dependence compared to previous approaches. The topic of the paper is interesting and relevant for the audience of NeurIPS for understanding denoising diffusion probabilistic models, however I find that the article could have been more accessible for the broader audience of NeurIPS, and importantly, I would expect that the authors would provide numerical evidence for their proposed guarantees.
Strengths
- the authors provide improved convergence guarantees compared to existing approaches. - they relax log-concavity assumptions existing in previous frameworks that are rather restrictive.
Weaknesses
- The work is purely theoretical and the authors do not provide numerical evidence for their claims excluding a simple experiment in the supplement. I find it a bit odd that they provide a convergence guarantee and propose a scaling with system dimension, but nevertheless they don't explore the said scaling numerically for increasing system dimension. The numerical example they present in the appendix concerns only a single experiment of dimension $d=5$. - the main theorem of the paper is formulated considering only linear dynamics (Ornstein-Uhlenbeck process). However according to the introduction of the paper a reader gets the impression that the provided results are relevant for general dynamics. I would propose to introduce this clarification both in the abstract and the introduction of the paper, otherwise the statements may be considered misleading. - the derivation of the probability flow ODE in Eq. 3 is a bit odd, and happens to be correct here because the considered dynamics is conservative. The whole point of [3] first introduced the formalism of ODE dynamics for diffusion that got later named prob. flow ODE by [4], was that there is no need for a stationary solution for the prob. flow ODE and no need to derive the dynamics wrt to the stationary solution. For general systems one can derive the dynamics of the deterministic process by rewriting the Fokker-Planck equation in the form of a Liouville equation as \begin{align} \partial_t p_t(\mathbf{x})& = - \nabla \cdot \left( f(\mathbf{x}) p_t(\mathbf{x}) - \frac{\sigma^2}{2} \nabla p_t(\mathbf{x}) \right) \\\\ &=- \nabla \cdot \left[p_t(\mathbf{x}) \left( f(\mathbf{x}) - \frac{\sigma^2}{2} \nabla \log p_t(\mathbf{x}) \right) \right] \end{align} From this formulation one can apply the divergence theorem and obtain the deterministic dynamics similar to [5]. The explanation used in the paper uses the Wasserstein gradient flow structure. - Poorly written and limited conclusion without discussing the limitations and possible outcomes of the provided guarantees. Minor: - The notation of the stationary distribution of the overdamped Langevin dynamics is rather unfortunate, especially considering that then it is used in the same sentences/equations with the parameter $\gamma$ indicating the damping of the underdamped process. I recommend adapting the notation to avoid confusing the readers unnecessarily.
Questions
- How does the proposed approach relate to the flow matching methods, i.e. [8]? - How does the method compare with concurrent approaches [7] , [9] and [10]?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
3 good
Limitations
- The authors do not provide numerical experiments to support their claims. - They do not provide comparisons with already proposed bounds on either stochastic or deterministic implementations of diffusion based generative models. - They do not discuss limitations of their approach. --- **References:** [1] Chen, Sitan, et al. "Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions." arXiv preprint arXiv:2209.11215 (2022). [2] Lee, Holden, Jianfeng Lu, and Yixin Tan. "Convergence of score-based generative modeling for general data distributions." International Conference on Algorithmic Learning Theory. PMLR, 2023. [3] Maoutsa, D., Reich, S., & Opper, M. (2020). Interacting particle solutions of Fokker–Planck equations through gradient–log–density estimation. Entropy, 22(8), 802. [4] Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., & Poole, B. (2020). Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456. [5] Hermoso, A., Homar, V., & Yano, J. I. (2020). Exploring the limits of ensemble forecasting via solutions of the Liouville equation for realistic geophysical models. Atmospheric Research, 246, 105127. [6] Albergo, Michael S., and Eric Vanden-Eijnden. "Building normalizing flows with stochastic interpolants." arXiv preprint arXiv:2209.15571 (2022). [7] Li, Gen, et al. "Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models." arXiv preprint arXiv:2306.09251 (2023). [8] Benton, Joe, George Deligiannidis, and Arnaud Doucet. "Error Bounds for Flow Matching Methods." arXiv preprint arXiv:2305.16860 (2023). [9] Lee, Holden, Jianfeng Lu, and Yixin Tan. "Convergence of score-based generative modeling for general data distributions." International Conference on Algorithmic Learning Theory. PMLR, 2023. [10] Albergo, Michael S., Nicholas M. Boffi, and Eric Vanden-Eijnden. "Stochastic interpolants: A unifying framework for flows and diffusions." arXiv preprint arXiv:2303.08797 (2023). [9] Jain, Ajay, and Ben Poole. "Journey to the BAOAB-limit: finding effective MCMC samplers for score-based models." NeurIPS 2022 Workshop on Score-Based Methods. 2022.
Thank you for your response. First of all, I would like to clarify the following point. In your response you stated: `We experimented DPUM on a toy model so the only conclusion one can draw is that DPUM works on this toy model. But this experiment is not our main contribution.` However, in section "1.1 Our contributions" you specify: ... - We propose an algorithm based on the probability flow ODE with underdamped Langevin corrector (DPUM.. - We provide the first convergence guarantees for DPUM. These convergence guarantees show improvement over (i) the complexity of DPOM ... - We provide preliminary numerical experiments in a toy example showing that DPUM can sample from a highly non log-concave distribution (see Appendix)... It seems to me that the reader may get the feeling that your numerical experiment confirms your theoretical estimates for convergence. In this context, I would like to clarify whether it is possible to see confirmation of your main result from the experiment you conducted? If not, why not? [By baseline in my review, I meant DPOM].
Thanks for engaging with us
Thanks for your reply. Exactly. The experiment does NOT illustrate the theory because our theorems holds for large dimension, whereas the experiment is done in low dimension. In particular, we did not see a difference between DPOM and DPUM in our low dimensional experiment (and we did not expect to see a difference). Therefore, the experiment and the theory are somehow orthogonal. So, one may ask why to include the experiment. The reason is simply because DPUM is a new algorithm that we propose. So, we thought that it would be interesting to try it on the simplest relevant case, which is in our opinion a low dimensional mixture of Gaussian. We will clarify that the experiment is not our main contribution and that it does not illustrate our theory (which holds when d is large). Finally, the reason why we do not increase the dimension in the experiment is because we run into instability and memory issues (one can try by setting a large d in the code we provided in the Supplementary).
Thank you. 1. Statements `DPUM is a new algorithm that we propose` and `we run into instability and memory issues` in your answer make me agree with Reviewer L7v8 ("I think for a paper about diffusion models, theoretical results and convincing experiments are both very important. Otherwise, there would be too many papers with beautiful theories that can hardly be used in real applications"). On the other hand, indeed, there is a significant number of successful works on this topic that contain only theoretical constructions, and your request to evaluate only your theoretical results, in general, sounds (to my regret) logical. 2. You chose a somewhat aggressive style of responding to the comments of the Reviewers, and it seems to me that this is slightly inappropriate, including, for example, such a phrase for one of the Reviewers as "...you rated your confidence level very low compared to the other reviewers. We kindly ask you to raise your confidence level...". On the other hand, you actively and purposefully defend your creation, and this, in general, causes respect. Since the comments in my original review were specifically about the experimental part, taking into account the above, I raise my final score from 4 to 5. I wish you good luck and further scientific success!
Thanks for raising the score.
Thank you for your positive comments. We are sorry if you find our style aggressive. To be honest we wondered if we should write the sentence you refer to. But we believe that the low confidence level of the review you refer to does not match the level of details in the comments and questions of that review *regarding our theorems*, which are our main contributions. Anyways, we also wish you good luck and scientific success in the future.
Last clarification
We want to clarify a last point: The instability issue we ran into in high dimension **are not specific to DPUM**, we ran into the same issues with DPOM, without corrector, and with SDE based diffusion model (see the code in the Supplementary where all these methods are implemented). We believe that this is because we have to fine-tune the hyperparameters for each of these methods. Best
Simulation in higher dimension
**We resolved the instability issue.** It was due to the calculation of the score of the mixture of Gaussian: the density of the mixture of Gaussian in high dimension can be so low that it was treated by zero by Python. The score is needed by DPUM and other concurrent methods, that's why we could not experiment in dimension 500 for example. We resolved the instability by multiplying the density by a large constant (which corresponds to the exponential of the entropy of the Gaussian components of the mixture). That does not change the value of the score (since the score involves calculating the gradient). The code is given at the end of this Comment. **Observation**: Our paper contains simulations of 500 particles in dimension 5 along 300 iterations. We see that in dimension 180, our algorithm's output at iteration 1800 is equivalent to the iteration 300 in dimension 5. In other words, by multiplying the dimension by 36, the algorithm is 6 times slower. Since $6 = \sqrt{36}$, this simulation suggests the scaling $O(\sqrt{d})$ for DPUM, which is mathematically proven in the paper. *We hope that this improves your opinion of our paper.* **Code**: in the Python file in the supplementary, replace the line densities[:, i] = torch.distributions.MultivariateNormal(mean, cov).log_prob(X).exp().to(X.device) by the lines dim = cov.shape[0] determinant = torch.det(cov) constant_term = torch.tensor(2 * torch.pi * torch.e, dtype=torch.float) entropy = 0.5 * (dim * torch.log(constant_term) + torch.log(determinant)) A = torch.distributions.MultivariateNormal(mean, cov).log_prob(X) + entropy densities[:, i] = A.exp().to(X.device)
Thanks for the authors' response. I think for a paper about diffusion models, theoretical results and convincing experiments are both very important. Otherwise, there would be too many papers with beautiful theories that can hardly be used in real applications. Since the authors have addressed most of my concerns, I would raise my score to borderline reject.
Thanks for raising the score.
We respect your opinion but we still believe that diffusion model is a field where there is a disequilibrium between the amount of applied works compared to the amount of theory works. The field is lacking theory papers that provides mathematical understanding. **Expecting from a theory paper like ours to provide large scale experiments fuels this imbalance between theory and practice in the field by setting the bar too high for theoretical papers.** Recall that we do not expect applied papers to provide extensive theory (and that's the right thing to do!) so it feels unfair to expect from us extensive experiments. Thanks for your consideration.
I personally agree.
A theoretical paper should be mainly evaluated by the theoretical novelty, application potential, and soundness.
Simulation in higher dimension
We scaled our toy experiment to higher dimension. We know this is not exactly what you were looking for, but we still hope that this improves your opinion of our paper. Recall that our paper contains simulations of 500 particles in dimension 5 along 300 iterations. We have modified the code to run simulations in higher dimension (e.g., d = 500). In particular, we observe that in dimension 180, our algorithm's output at iteration 1800 is equivalent to the iteration 300 in dimension 5. In other words, by multiplying the dimension by 36, the algorithm is 6 times slower. Since $6 = \sqrt{36}$, this simulation suggests the scaling $O(\sqrt{d})$ for DPUM, which is mathematically proven in the paper.
About the experiments
Please stop saying the reviewers are requiring _**extensive**_ experiments! First, evaluating your sampler on pre-trained diffusion models **is not difficult** at all and there are no extra training costs. Besides, there are so many available pre-trained diffusion models on different datasets you can use, such as on CIFAR10, FFHQ, LSUN-Bedroom, CelebA, etc. These models are not too big and I believe it is very convenient to use them to evaluate your method. I think just a simple experiment on **any of the above datasets** would be enough for a theoretical paper like yours. However, only a toy example is provided in the supplementary, which makes it questionable whether the proposed method is effective. I highly encourage you to add an experiment using just one model I mentioned above and compare your method to existing methods.
I can understand why reviewers are pushing for more experiments, especially when the authors claimed their algorithms as one of the main contribution. This can potentially be misleading. I would recommend the authors to clarify their message in the paper. The experiments suggested by L7v8 will clearly be a nice addition to this paper (as mentioned in my first round comments as well). However, I'd like to argue for the authors that adding more experiments or the existence of ANY empirical result is not central to the contribution of this specific work. In fact, I would suggest the authors to just remove the toy experiments; these illustrations do not seem to be representative enough. The key contribution of this paper is theoretical in nature and the evaluation of this work should purely be based on whether the results or proof techniques are mathematically interesting (or maybe the clarity of the writing as well). To me, this work clearly improved existing results and provided a fairly novel techinique of achieving polynomial TV convergence, with a high quality writing as well. (Please see my comments and discussions with the authors for justifications of the above points; but I also respect that if other reviewers hold different opinions.) As for the expectation of empirical verifications in theory papers in this domain, I see it as a philosophical question instead of a strictly scientific one. While the community rightly values methodologies that show promising empirical outcomes, works that make attempts to understand and interpret of existing methods should also be appreciated -- even if even if these theoretical probes sometimes operate in constrained or potentially impractical settings. Supporting and encouraging these ``impractical'' but rigorous scientific investigations are crucial to fostering a healthy and diversed research community.
ask some details
1. I probably missed something in the literature. Could you share some standard references on when Langevin leads a linearly-increased error in TV? 2. Could you show me in your proof where we require enough diffusion steps to yield this linear property?
Thanks for the questions
Thanks again for commenting and questioning our theorems. 1. The analysis in TV which leads to error growing linearly in time is not found in the literature; rather it is a **novelty of our work**. Intuitively this stems from different ways of measuring distances between probability distributions. The Wasserstein distance measures distances between random variables, and since our dynamics are not contractive, then a naive coupling of the algorithm iterates with the ground truth lead to errors being compounded over time, leading to an exponential blow-up. But when we work in total variation distance, we work with probabilities of certain events. At each iteration, there is some probability of the "bad event" occurring, in which the algorithm iterate has strayed away from the ground truth. But by the union bound we can sum up the probabilities of these bad events across the iterations, leading to an error bound that only grows linearly with the number of iterations. This is the main reason why we develop our framework in which the added stochasticity of the diffusion leads to a Wasserstein-to-TV regularization effect, and then we carry out our analysis in TV. 2. As mentioned above, the key property of the diffusion is Wasserstein-to-TV regularization, which is captured in Thms. 4 and 5 in the Appendix. These theorems show that after running the corrector, we can bound the TV error in terms of the Wasserstein error. However, the bounds depend on the amount of continuous time for which we run the corrector. For our analysis, we run the corrector for sufficiently long in order for these bounds to give good results. **To see the linear accumulation of error in TV, see the proof of Thms. 2 and 3 in the Appendix; in particular, in the second display equation, the error terms scale linearly with T, the total time that we run the process.**
Thanks for the response
I think the authors have addressed my concerns on the theoretical side. Their response has bolstered my confidence, and I genuinely appreciate their efforts. In terms of practical experimentation, I hold the view that real-world experiments, such as CIFAR-10, might not be essential for this solid theoretical diffusion paper. Nonetheless, considering the paper's emphasis on exhibiting enhanced dimension dependence, it would be prudent to consider employing clever high-dimensional synthetic simulations (which would help increase my current score). Drawing inspiration from [1], where a sampler was employed with a dimensionality of 1000, could serve as an apt illustration of the paper's strengths. With these thoughts in mind, I am inclined to maintain my current score of 6. [1] Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo.
Simulation in higher dimension
Thanks for the suggestion and for your support. Our paper contains simulations of 500 particles in dimension 5 along 300 iterations. We have modified the code to run simulations in higher dimension (e.g., d = 500). In particular, we observe that in dimension 180, our algorithm's output at iteration 1800 is equivalent to the iteration 300 in dimension 5. In other words, by multiplying the dimension by 36, the algorithm is 6 times slower. Since $6 = \sqrt{36}$, this simulation suggests the scaling $O(\sqrt{d})$ for DPUM, which is mathematically proven in the paper. **We hope that this improves your opinion of our paper.**
Response to authors rebuttal
Thank you for answering my questions; I think your response has addressed my questions and clarifies further the key novelty of the presented proof technique. However, I decided to keep the score 8 for this work, which clearly means it's a strong theory paper. To merit a score above 9 in my evaluation criteria, a paper should excel both theoretically and empirically. Regarding my initial confidence score, I wish to clarify that it was not due to my lack of ability to understand the content, but to from my unfamiliarity with the current literatures on theories for ODE based diffussion models. So I felt less confident to assess the significance of the current results. Now after reading up some literature in this line of work, I'm more confident to my evaluation. In this regards, I raised my confidence score from 2 to 3.
Simulation in higher dimension
Thanks for your support and for updating the confidence level. FYI, we performed simulations in higher dimension. Our paper contains simulations of 500 particles in dimension 5 along 300 iterations. We have modified the code to run simulations in higher dimension (e.g., d = 500). In particular, we observe that in dimension 180, our algorithm's output at iteration 1800 is equivalent to the iteration 300 in dimension 5. In other words, by multiplying the dimension by 36, the algorithm is 6 times slower. Since $6 = \sqrt{36},$ this simulation suggests the scaling $O(\sqrt{d})$ for DPUM, which is mathematically proven in the paper.
Simulations in higher dimension
An update on our simulations: Our paper contains simulations of 500 particles in dimension 5 along 300 iterations. We have modified the code to run simulations in higher dimension (e.g., d = 500). In particular, we observe that in dimension 180, our algorithm's output at iteration 1800 is equivalent to the iteration 300 in dimension 5. In other words, by multiplying the dimension by 36, the algorithm is 6 times slower. Since $6 = \sqrt{36}$, this simulation suggests the scaling $O(\sqrt{d})$ for DPUM, which is mathematically proven in the paper. **We hope that this answers your concern on the toy experiments.**
Decision
Accept (poster)