Reverse Diffusion Monte Carlo

Thank you for your review. For better discussion, we would like to clarify certain misunderstandings before presenting our formal rebuttal. Firstly, we acknowledge the concerns raised regarding the omission of parameterized sampling algorithms from our discussion. This was based on the fact that these algorithms primarily fall under the Variational Inference (VI) regime, while our algorithm is an improved version of MCMC. Nevertheless, we are grateful for your references and suggestions and will incorporate a discussion of these elements in our updated manuscript.

It is crucial to emphasize that our algorithm is non-parametric, focusing on the theoretical analysis and understanding of both asymptotic and non-asymptotic behaviors of discretized dynamics. Here, our rdMC demonstrates superior performance compared to Langevin-based algorithms, particularly for ill-behaved distributions.

A key aspect of our work is the exploration of log-Sobolev constant dependency of the gradient complexity, where we have found that rdMC outperform conventional methods. This distinction makes a direct comparison with parameterized models infeasible.

Our work does indeed share similarities with parameterized diffusion-based sampling algorithms. Some ideas might be embedded in your references, which will be discussed in our next version. However, the main algorithm and concentrations still differ. Once the parametric model is chosen, there is always an asymptotic error. In contrast, our method turns score-matching into a non-parametric mean estimation problem and is asymptotically exact, just like the traditional Monte Carlo methods. Our work represents a pioneering effort in examining non-parametric algorithms that leverage diffusion dynamics, backed by robust theoretical guarantees. We believe that our theoretical foundations distinctly support these algorithms.

We acknowledge your proposed works could be viewed as a parametric VI version of rdMC, analogous to the relationship between Black-Box Variational Inference and Langevin Dynamics in the VI-MCMC pair [1]. This perspective offers an intriguing angle, viewing diffusion models as a Parametric Approximation to rdMC. However, it is important to note that it's not entirely appropriate to directly compare a newly established, theoretically guaranteed MCMC work with VI models. Our algorithm can approximate the score with arbitrarily small error. Yet, the potential connections between these methodologies present an interesting avenue for discussion.

In light of your comments, we plan to have more discussion about connections between our algorithm and the ones you proposed. Additionally, we will extend our empirical results to more high-dimensional scenarios to further substantiate our claims.

We genuinely appreciate your constructive suggestions and look forward to incorporating these insights into our revised work.

[1] Black-Box Variational Inference as Distilled Langevin Dynamics

Dear reviewers,

The score 1 was not intended as dismissive of the work, but mostly to alert the strong concern of lacking evaluations and the very incomplete literature, in the current version of the manuscript. This score will very likely change as the revised version is uploaded, especially since I believe you understand some of the concerns I raised and at least part of them are not too difficult to address.

Notice that the open review platform allows for a score of 1, its part of the accepted scores / formal review process and is not intended to dismiss the nature of the contribution but in this case at least point to the current state of the paper, e.g. its presentation, literature review, numerics, claims, etc.

Anyway, let’s move forward and stop those emotional evaluations.

Agreed, let's stay focused. In that spirit, I want to revist some of your points in the rebuttal that I possibly missed / misinterpreted:

1. It is crucial to emphasize that our algorithm is non-parametric, focusing on the theoretical analysis and understanding of both asymptotic and non-asymptotic behaviors of discretized dynamics. ...

I think we have gone back and forth on this point a bit already. To summarise my views here:

• I agree the proposed schemes in this work is line with traditional MCMC works, thus comparisons to algorithms of this flavour such as ULA, SFS [1], and such seem more than reasonable.
• There is a "diffusion models for sampling" aspect to your algorithm, and whilst prior work is mostly (not entirely e.g. [1]) focused on VI approaches to estimate the score, the overal should be discussed and prior relevant formulations of the score should be credited appropiately.

2. A key aspect of our work is the exploration of log-Sobolev constant dependency of the gradient complexity, where we have found that rdMC outperform conventional methods. This distinction makes a direct comparison with parameterized models infeasible.

I agree mostly here and this is something that I missed in my initial review. I do think you are justified in not needing to compare empirically to these approaches, the comparison to ULA / MCMC schems here is sufficient.

However, as I mentioned before there is a significant overlap in that the discussed parametric approaches are trying to estimate the same score.

The existing works, after choosing the parametric (neural network) model, all suffer from an irremovable error.

This is true but notice that prior work [2] establishes quite detailed bounds on the error that these parametric estimators of the score can potentially achieve, and it may be interesting (yet not necessary) to discuss at a high level how the complexity of these bounds compares to the results on the inner loop you have provided.

Of course, in practice, these bounds are not realistic (whilst yours are) as the networks need to be trained via a non-convex objective that is not guaranteed to reach these errors.

Something I mentioned in my initial review, was that I found your log-Sobolev explorations quite exciting as they might also have something more to say in regards to expressiveness bounds when using NN parametrized estimators [2]. This is not directly relevant and you do not need to address this in the manuscript.

We believe that our theoretical foundations distinctly support these algorithms.

I do agree with this point, although as mentioned before this is not the first work that is entirely of this flavour (e.g. [1]) an important differentiating factor you offer however is a much more refined inner loop with finer guarantees compared to [1] ([1] simply does IS with no inner-loop and is thus very high variance).

I think the presentation of the work would be improved and made much more clear if this differentiating factor (in particular the complexity of the inner loop scheme) is emphasized as the main contribution / differentiating factor, which also renders the method more practical compared to [1].

This said more high dimensional numerics (and complex dists) are needed to truly verify the method empirically. In particular, such verifications must be done such that ULA and the new proposed algorithm have roughly the same computation budget (e.g. inner_loop_steps * outer_loo_steps = ula_steps).

P.S. I have updated my review a bit to reflect on some of this discussion.

[1] Huang, J., Jiao, et al Schrödinger-Föllmer sampler: sampling without ergodicity

[2] Vargas F. Et al Expressiveness Remarks for Denoising Diffusion Based Sampling.

Dear reviewer,

Thank you for your prompt response. Let me be straightforward about this. You have missed the main contribution of this paper.

Our method is not an approximate Bayesian inference method, like the ones you have cited. Our method is asymptotically exact, like the traditional MCMC methods. It leverages the reverse diffusion process, but does not really build a diffusion model. That is why we can obtain an overall convergence rate that decreases to zero as the computational complexity increases. The existing works, after choosing the parametric (neural network) model, all suffer from an irremovable error.

For [Huang et al.] you mentioned, the assumptions are much stronger than log-Sobolev assumptions, as they assume the Lipschitz continuity of the drift term, so they are unable to deal with general distributions and make a direct comparison with MCMC. Also, the drift term is estimated by importance sampling, which limits the usage as you mentioned.

We will have a separate paragraph citing these works and discussing the distinction.

Dear Author ,

It is not in your interest to be dismissive towards a reviewer. I am taking the time and effort to engage with you promptly and I am willing to reassess, however I do implore you to be respectful and not dismissive.

Firstly I am 100% aware that your method is asymptocally exact and more akin to mcmc I have not missed this focus and aspect of your contribution. My remarks are not taking this away so please stop trying to demerit my review and address the following individual points I have already made.

1 . I have citied a paper in my review which you have neither acknowledged nor responded too [1] this work is also asymptotically exact it is more MCMC alike and it is NOT approximate inference. 2. Both MCMC methods and approximate inference methods often target the same task . That is a sampling from unnormalized densities that can be evaluated pointwise . The point I am raising is the following

“ There are prior works that write down the exact same expectation formulations of the score to tackle the sampling task.”

Most of these prior works (not [1]) decide to learn an estimator for this score via a variational approach rather than an asymptotically exact approach. Please carefully read these other papers I agree the VI aspect is different but that is not my point be more thoughtful and read my feedback carefully.

In short please carefully address these points and stop dismissing them as non-relevant, this is very poor etiquette I am trying to work with you here and you are making my job much harder, let’s remain professional and on topic, please.

Please be mindful of my time and effort.

[1] Huang, J., Jiao, Y., Kang, L., Liao, X., Liu, J. and Liu, Y., 2021. Schrödinger-Föllmer sampler: sampling without ergodicity. arXiv preprint arXiv:2106.10880.

Thank you for your swift feedback.

We have incorporated experiments of Neal's Funnel into our Appendix F.5. It is shown that our algorithm can make a better balance between exploration and precision for Neal's Funnel sample.

More comprehensive empirical studies and bags of tricks could be a promising direction for future exploration. In this paper, our focus is on strengthening the theoretical underpinnings and enhancing our understanding of the rdMC algorithm (as well as the benefits of the diffusion-like dynamics) compared with MCMC.

If you have any further inquiries or suggestions, please do not hesitate to reach out to us.

Thank you for your helpful comments. We have highlighted the “lower isoperimetric dependency” in Section 4.1. Moreover, the parts related to Pinsker's inequality were rearranged for better reading experience.

For the Lipschitz continuity of the drift term, we add more explanations in our Appendix. We summarize it as below

The main reason is that the delta distribution side makes $p_t$ ill-behaved (when the variance is approaching 0, which makes $-\log p_t \approx \Vert x\Vert^2/(2\sigma^2)$ is exploding). They also provided a sufficient condition when both $p_*\cdot\exp(\Vert x\Vert^2)$ and its gradient are Lipschitz continuous, and the former is bounded below by a positive value. However, this condition may not be met when the variance of $p_*$ exceeds 1, limiting its general applicability of this condition. Thus, the generality of SFS remains an open question. On the other hand, due to the smoothness of $p_\infty$ in OU process, the smoothness of $\log p_t$ is widely accepted in diffusion analysis [1,2]. [3] also suggest that the smoothness of concave $\log p_0$ can imply the smoothness of $\log p_t$. In summary, the smoothness of $\log p_t$ in OU process is much weaker than a process towards to a delta distribution, which generalize the analysis to more distributions.

[1] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint, arXiv:2209.11215, 2022a.

[2] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pp. 4735–4763. PMLR, 2023.

[3] Holden Lee, Chirag Pabbaraju, Anish Sevekari, and Andrej Risteski. Universal approximation for log-concave distributions using well-conditioned normalizing flows. arXiv preprint arXiv:2107.02951, 2021a.

Thanks for your suggestions. In summary, we have added more experiments (Appendix F3 F4 F5) and highlight our complexity analysis. Our current one includes both inner, outer loop, and sample-size, which is still much more effient than Langevin-based ones. Both inner iterations and samples do not bring too much computation overhead compared with exponential log-Sobolev constant. We also verify that our algorithm is not sensitive to $\tilde{p}_0$.

If you have any further inquiries or suggestions, please do not hesitate to reach out to us. Detailed response are as below.

Lack of practical and experimental results for complex distributions

Thanks. We have added the experiments for high-dimensional setting in our Appendix F3. In general, as the leading factor of isolated multi-mode distribution is the log-Sobolev constant (exponential dependency), the dimension dependency (polynomial) is not the main challenge. Thus, our algorithm still has significant improvement.

Lack of complexity analysis. The combination of different sampling techniques (importance sampling, ULA) adds algorithmic complexity. Managing the interactions between these techniques and ensuring their proper integration can be challenging. Also, The method might demand significant computational resources, especially when dealing with large sample sizes and high-dimensional spaces. This could limit its practicality for resource-constrained applications. The sample size required for accurate estimation scales exponentially with the dimension due to the KL divergence between distributions. This exponential growth can make the method computationally infeasible for high-dimensional spaces. Could the authors please elaborate on these issues? The accuracy of the estimation relies heavily on the dimensionality of the problem. High-dimensional spaces exacerbate the sample size requirement, making it challenging to apply the method effectively in real-world applications.

Our paper provides a detailed complexity analysis in both Sections 4.1 and 4.2 under different assumptions. We incorporate both gradient complexity and sample complexity within our propositions, directly stemming from the log-Sobolev constant estimation and Theorem 1.

We highlight that our theory indicate that considering inner * outer loop, our algorithm is still much more efficient than Langevin-based algorithms. Our experimental results also verify this point.

Additionally, it is noteworthy that our algorithm's dependency on the dimension $d$ is polynomial, not exponential, further underscoring its efficiency. And our algorithm can reduce the exponential term induced by the log-Sobolev constant

Creating n Monte Carlo samples at each iteration can be computationally expensive, especially if n is large. This might limit the method's scalability and efficiency for high-dimensional or complex distributions.

Thanks for your suggestion. In our analysis, we have already considered the complexity of $n$ samples. The main point of our algorithm is that even with $n$ samples, the total complexity is still less than Langevin-based algorithm. Note that the complexity with respect to $n$ is linear and the needed accuracy is polynomial, but the complexity of the original problem is exponential. In addition, the computation of MC samples can be paralled, while exponetial iterations cannot be reduced.

The method uses random samples at each iteration. The quality of these random samples is crucial; if they are not truly random or are biased in some way, it can introduce errors in the sampled results. Furthermore, the way the samples are generated and combined in the update equation (step 6) could introduce bias if not done correctly. Biased estimators can lead to incorrect conclusions about the target distribution.

Thank you for you question. Indeed, the quality of these random samples is crucial, so we analysis the necessary accuracy of the inner loop to obtain the proper samples in our Theorem 1. When the error is controlled, we can guarantee the convergence of our algorithm. In real practice, the algorithm is even less sensitive to the inner loop error, as the theoretical bound considers the worst case.

The method's performance might degrade in high-dimensional spaces. Monte Carlo methods often face challenges in high-dimensional settings due to the curse of dimensionality, where the sampling space becomes sparse, making it harder to obtain representative samples.

We appreciate your feedback. In response, we have included high-dimensional experiments in Appendix F3. It is crucial to note that our approach maintains a polynomial dependency on dimensionality, ensuring the identification of representative samples within a finite timeframe.

How sensitive is this framework to initial distribution $p_0$

Thank you for your question. Are you referring $\tilde{p}_0$? If so, we have added a discussion in the current Appendix F4.

We are grateful once again for your invaluable review. In our revised manuscript and response, we have endeavored to thoroughly address all your concerns and questions.

We've enriched our work with new empirical results and an ablation study to demonstrate the effectiveness and robustness of our algorithm in high-dimensional scenarios. We also highlight our an in-depth complexity analysis, suggesting that our algorithm maintains higher efficiency than Langevin-based methods, considering inner, outer loops, and sample complexity. Furthermore, we have refined our writing to ensure clarity and prevent misunderstandings.

Could you please spare some time to review our updated response and verify if it satisfactorily answers your questions? We are eager to engage in further discussion and offer additional clarifications for any new inquiries you may have.

Dear Reviewer qHDx,

Thank you for your insightful feedback once again. We hope that our response addresses your concerns and questions.

As our author-reviewer discussion nears its end, we'd appreciate knowing if your concerns are resolved. We are open for any further discussion and would appreciate a reassessment of the rating in light of the manuscript's improvements.

Thank you for your helpful suggestions. We have significantly modified the proof for better reading experience and add more explanation for clarity. We also add a proof sketch for non-experts (Appendix B). We are trying our best to make our analysis user-friendly.

If you have any further inquiries or suggestions, please do not hesitate to reach out to us. Detailed response are as below.

Q1. Clarity and flow of the proofs.

Thank you for your suggestion. We have significantly rearranged the proof and lemmas for better reading experience. Moreover, we have added a proof sketch in Appendix B. Please take a look and feel free to tell us if you have any question.

Q2. Hyper-parameters.

We have included the hyperparameters in our appendix and added the hyperlink in the main context.

Q3. In D2 (proof of lemma 2 and 3): the paper refers to Proposition 2 in Ma et al. (2019). However, I cannot find the Proposition 2 in Ma et al. (2019). - Lemma 9: not an obvious mismatch between the statement of the lemma and the final line in the proof (RHS of inequality is d/mu for the former, 1/mu for the latter); - The proof of lemma 9 starts with “It is known that LSI implies Poincare inequality with the same constant,...”. Perhaps a reference would help.

For the Proposition 2 in Ma et al. (2019), Please refer to page 11 of the arXiv version (Appendix B.1), which is a formal version of Proposition 1. We also revised our content to reiterate the PNAS version proposition to make our paper self-contained.

For Lemma 9 (previous notation, current Lemma 22), sorry for the confusion. The previous version of last line is for a single dimension. We have also added the reference for LSI and PI.

We sincerely appreciate your insightful feedback once again. In response, we have diligently addressed each of your concerns and queries. Notably, we've incorporated a proof sketch and have significantly enhanced the clarity of our proof through thoughtful reorganization. Additionally, we've refined our writing to minimize any possible misunderstandings. Would you be able to spare some time to review our revised response and confirm if it adequately addresses your questions? We are eager to engage in further discussions and provide additional clarifications on any new queries you may have.

Thank you for your suggestion. We followed your points and try to make our claims more clear and rigorous. We also highlight our analysis of $q$'s log-Sobolev are in Sec 4.1 and 4.2. We try our best to revise our manuscript to address your concerns.

If you have any further inquiries or suggestions, please do not hesitate to reach out to us. Detailed response are as below.

Q1. The rigorousness of the claims.

Thank you for your suggestion. We have revised the claims as below:

1. Thus, we analyze the complexity to estimate the score by drawing samples from the posterior distribution and found that our proposed algorithm is much more efficient in certain cases when the log-Sobolev constant of the target distribution is small.

2. For any $t > 0$, we observe that $-\log q_{T-t}$ incorporates an additional quadratic term. In scenarios where $p_*$ adheres to a log-Sobolev condition, this term enhances $q_{T-t}$'s log-Sobolev constant, thereby accelerating convergence. Conversely, with heavy-tailed $p_*$ (where $f_*$'s growth is slower than a quadratic function), the extra term retains quadratic growth, yielding sub-Gaussian tails and log-Sobolev properties. Notably, as $t$ approaches $T$, the quadratic component becomes predominant, rendering $q_{T-t}$ strongly log-concave and facilitating sampling. In summary, every $q_{T-t}$ exhibits a larger log-Sobolev constant than $p_*$. As $t$ increases, this constant grows, ultimately leading $q_{T-t}$ towards strong convexity. Consequently, this provides a sequence of distributions with log-Sobolev constants surpassing those of $p_*$, enabling efficient score estimation for $\nabla\ln p_{T-t}$.

Q2. log-Sobolev constant of $q$.

Thank you for pointing out this. In fact, we are unable to whether $q_{T-k\eta}$ is log-Sobolev with A1 and A2. That is the reason why we add Section 4.1 and 4.2 to discuss the assumption of $p_*$ and log-Sobolev constant of $q_{T-k\eta}$. We have added more explanation before 4.1 to highlight this point:

Note that the log-Sobolev constants of $q_{T-k\eta}$ depend on the properties of $p_ \ast$, so we should add more assumptions to estimate the log-Sobolev constants for $q_{T-k\eta}$. Next, we will demonstrate the benefits of using $q_{T-k\eta}$ for ill-conditioned LSI or non-LSI $p_ \ast$.

Q3. Point out where the proof is in Appendix

Thank you for your suggestion. We have revised our manuscript.

Thank you sincerely for the time and effort you've invested in reviewing our work; your feedback is invaluable. We've aimed to address your questions clearly and concisely, minimizing misunderstandings for improved readability. Should you have any further concerns or need more information, we're more than willing to assist. If our responses meet your expectations, we would greatly appreciate your acknowledgment of our progress. Thank you once again for your crucial role in enhancing our work. We eagerly await your feedback.

Dear Reviewer UPK6,

Thank you for your insightful feedback once again. We hope that our response addresses your concerns and questions.

As our author-reviewer discussion nears its end, we'd appreciate knowing if your concerns are resolved. We are open for any further discussion and would appreciate a reassessment of the rating in light of the manuscript's improvements.

Thank you for your swift feedback.

We consider two cases as in Section 4.1 and 4.2 for more intuitive demonstrations.

(1) log-Sobolev constant of $p_*$ is exponential to radius $R$ as in [$A_3$], which is common for mixture models. Then due to the OU process, we have that the log-Sobolev constant of any $p_T$ is improved for any $T>0$. Once, the log-Sobolev constant for $q$ is NOT exponential wrt $R$, the reverse diffusion can save the computation:

As Lemma 2 suggest

Under [$A_1$], the log-Sobolev constant for $q_t$ in the forward OU process is $\frac{e^{-2t}}{2 \left(1-e^{-2t}\right)}$ when $0\leq t\leq\frac{1}{2} \ln\left(1+\frac{1}{2L}\right)$. This estimation indicate that when quadratic term dominate the log-density of $q_t$, the log-Sobolev property is well-guaranteed.

It means that the log-Sobolev constant within this interval is independent from $R$, and the endpoint of $p_T$ is smoother and more concentrated than $p_0$ that leads to a better log-Sobolev constant.

(2) $p_*$ is not log-Sobolev due to the heavy-tail property. We can assume the tail behavior of $p_*$, as [$A_4$],

For any $r>0$, we can find some $R(r)$ satisfying $f _ * (x)+r\left\|x\right\|^2$ is convex for $\left\|x\right\|\ge R(r)$. Without loss of generality, we suppose $R(r) = c _ R/r^n$ for some $n>0,c_R>0$ where $n$ defines the growth rate of the tail.

However, due to the additional quadratic of $q$, we can still keep $q$ is sub-Gaussian and log-Sobolev.

Under [$A_1$] and [$A_4$] the log-Sobolev constant for $q_t$ in the forward OU process is $\frac{e^{-2t}}{6(1-e^{-2t})}\cdot e^{-16\cdot 3L\cdot R^2\left(\frac{e^{-2t}}{6(1-e^{-2t})}\right)}$ for any $t\geq 0$.

It means for any $t>0$, we can get a log-Sobolev constant for $q$, but the original problem is non-log-Sobolev. Reverse diffusion provides a procedure that decompose the non-log-Sobolev sampling problem into log-Sobolev sampling subproblems.

Thank you for your insightful comments and encouragement. Your support fuels our motivation to further refine the manuscript.

A key aspect of our work involves providing a comprehensive theoretical analysis, particularly addressing questions like the complexity of score estimation at various time steps and the potential advantages of diffusion-based algorithms. We're eager to contribute ideas that may inspire other researchers and spark future innovations.

Recognizing the limitations of our current manuscript, we've dedicated ourselves to enhancing its quality. This includes incorporating additional empirical results and refining our writing for a better reading experience. We're hopeful that these updates will not only address your concerns but also provide valuable insights for the broader research community.