Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion
Authors: Ye He
Kevin Rojas
Molei Tao
Venue: NeurIPS 2024 poster (2024)
Keywords: Non-logconcave sampling
Monte Carlo sampling
Denoising Diffusion Model
Primary area: diffusion_based_models

Abstract: This paper considers the problem of sampling from non-logconcave distribution, based on queries of its unnormalized density. It first describes a framework, Denoising Diffusion Monte Carlo (DDMC), based on the simulation of a denoising diffusion process with its score function approximated by a generic Monte Carlo estimator. DDMC is an oracle-based meta-algorithm, where its oracle is the assumed access to samples that generate a Monte Carlo score estimator. Then we provide an implementation of this oracle, based on rejection sampling, and this turns DDMC into a true algorithm, termed Zeroth-Order Diffusion Monte Carlo (ZOD-MC). We provide convergence analyses by first constructing a general framework, i.e. a performance guarantee for DDMC, without assuming the target distribution to be log-concave or satisfying any isoperimetric inequality. Then we prove that ZOD-MC admits an inverse polynomial dependence on the desired sampling accuracy, albeit still suffering from the curse of dimensionality. Consequently, for low dimensional distributions, ZOD-MC is a very efficient sampler, with performance exceeding latest samplers, including also-denoising-diffusion-based RDMC and RSDMC. Last, we experimentally demonstrate the insensitivity of ZOD-MC to increasingly higher barriers between modes or discontinuity in non-convex potential.

Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion
Ye He Georgia Institute of Technology yhe3670gatech. edu
Kevin Rojas Georgia Institute of Technology kevin. as@gatech edu
Molei Tao
Georgia Institute of Technology mtao@gatech edu
Abstract
This paper considers the problem of sampling from non-logconcave distribution, based on queries of its unnormalized density. It first describes a framework, Denoising Diffusion Monte Carlo (DDMC), based on the simulation of a denoising diffusion process with its score function approximated by generic Monte Carlo estimator. DDMC an oracle-based meta-algorithm, where its oracle the assumed access to samples that generate Monte Carlo score estimator. Then we provide an implementation of this oracle, based on rejection sampling, and this turns DDMC into a true algorithm, termed Zeroth-Onn Order Diffusion Monte Carlo (ZOD- MC). We provide convergence analyses by first constructing general framework, i.e. performance guarantee for DDMC, without assuming the target distribution be log-concave or satisfying any isoperimetric inequality. Then we prove that ZOD-MC admits an inverse polynomial dependence on the desired sampling accuracy, albeit still suffering from the curse of dimensionality. Consequently, for low dimensional distributions, ZOD-MC is very efficient sampler, with performance exceeding latest samplers, including also-denoising-difuue diiiiiigdddffuso--baaae based RDMC and RSDMC. Last, experimentally demonstrate the insensitivity of ZOD-MC to increasingly higher barriers between modes or discontinuity in non- convex potential.
Introduction
The problem of drawing samples from a distribution based on unnormalized density oc exp(-V) (described by the potential V) is fundamental statistical and algorithmic problem. This classical problem nevertheless remains as a research frontier, providing pivotal tools to applications such as decision making, statistical inference estimation, uncertainty quantification, data assimilation, and molecular dynamics. Worth mentioning is that machine learning could benefit vastly from progress in sampling well, not only because of its connection to inference, optimization and approximation, but also through modern domains such as diffusion generative modeling & differential privacy.
Recent years have seen rapid developments of sampling algorithms with quantitative and non- asymptotic theoretical guarantees. Many of the results are either based on discretizations of diffusion processes [12, 13, 50, 16, 34, 33] or gradient flows [38, 10, 22]. In order to develop such guarantees, is necessary to make assumptions about the target distributions, for instance, that it satisfies an isoperimetric property, where standard requirements are log-concavity or functional inequalities
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

[12, 56, 21, 8, 48]. However, there is empirical evidence that the corresponding algorithms struggle to sample from targets that have high barriers between modes that create metastability. Overcoming such issues is highly nontrivial and researchers have continued to develop new methods to tackle these problems.
Diffusion models have lately shown remarkable ability in the generative modeling setting, with applications including image, video, audio, and macromolecule generations. This created a wave of theoretical work that showed the ability of diffusion models to sample from distributions under minimal assumptions [14, 5, 29, 4, 11, 3]. However, these works all started with the assumption that there is access to an approximation of the score function with some accuracy. This is reasonable assumption for the task of generative modeling when one spends enough efforts on the training of the score, but the task of sampling is different. A natural question is: can we leverage the insensitivity of diffusion models to multimodality to efficiently sample from unnormalized, con-log-concave density? This would require approximating the score, which is then used as an inner loop inside an outer loop that integrates reverse diffusion process to transport, e.g., Gaussian initial condition, to nearly the target distribution.
The seminal works by [26, 27, 20] try answer this question using Monte Carlo estimators of the score function and to provide theoretical guarantees. We also mention earlier work by [53] which learns parameterized scores and more work along the same line by [58, 44, 54, 55], whose theoretical guarantees are less clear but are based other interesting ideas. [26] proposed Reverse Diffusion Monte Carlo (RDMC), which estimates the score via LMC algorithm and relaxes the isoperimetric assumptions in the analysis of traditional sampling algorithms. [20] proposed a similar method, stochastic localization via iterative posterior sampling (SLIPS), which approximate the score via Metropolis-adjuste Langevin algorithm (MALA). However, both methods rely on the usage of a small time window where isoperimetric properties hold. This leaves the problem of finding a good initialization for the diffusion process. To alleviate this issue, [27] developed an acceleration of RDMC, the Recursive Score Diffusion- Monte Carlo (RSDMC), which improves the non- asymptotic complexity to be quasi-polynomial in both dimension and inverse accuracy and gets rid of any isoperimetric assumption. Such work provides strong theoretical guarantees, however it requires lot of computational power to get high accuracy sampler. Additionally, RDMC, SLIPS and RSDMC are all based on first-order queries (i.e. gradients of V), which brings extra computational and memory costs, in addition to requiring a continuous differentiable V. Motivated by these two observations, we create a sampler that only makes use of zeroth-order queries without assuming any isoperimetric conditions the target distribution. Our contributions can be summarized as follows.
We introduce oracle-based meta-algorithm DDMC (Denoising Diffusion Monte Carlo) and provide a non-asymptotic guarantee in KL-divergence in Theorem 1. Our result provides theoretical insight on the choice of optimal step-size in DDMC well as in denoising diffusion models (Sec. 3.2).
We develop novel algorithm ZOD-MC (Zeroth Order Diffusion-Montt Carlo) that uses zeroth-order queries and the global minimal value of the potential function to generate samples ap- proximating the target distribution. In Corollary 3. we establish zeroth-order query complexity upper bound for general target distributions satisfying mild smoothness and moment conditions. Our result is summarized and compared to other sampling algorithms in Table 5.
The advantages of our algorithm are experimentally verified for non- non-log-cones lon--ccccccvee target distribu- tions. We demonstrate the insensitivity of our algorithm to various high barriers between modes, and the ability of correctly account for discontinuities in the potential.
2 Preliminaries
2.1 Diffusion Model
Diffusion model generates samples that are similar to training data, by requiring the generated data to follow the same latent distribution p as the training data. To do so, it considers a forward noising
Asssmmtton [A4] in [26] is a soft version of strongly log-concave outside a ball.
"This criterion measures the KL-ddivereence from the oulput distribution distribution that is closed to the target distribution Wasserstein-2 2 distance. This criterion considered in analyzing denoising diffusion models with step-size that accommodates the early stopping technique, see [4, 3J. This criterion does not apply to RDMC/RSDMC since they don't 't use early stopping and instead assume the target distribution to be smooth and fully supported on Ied. See 3.c.3.3 for more discussions.

---

Algorithms
Queries
Assumptions
Criterion
Oracle Complexity
LMC
first-order
LSI
KL
Olde
RDMC
first order
soft log-concave'
TV
exp (logg() d) (
RSDMC
first-order
None
KL
exp(O(log" (ds 1))
Proximal Sampler zeroth-order
log-concave
KL
O(de (xp(O(d)O(lo((= 1))
ZOD-MC
zeroth-order
None
KL
W22
Table 1: Comparison of ZOD-MC to LMC, RDMC, RSDMC and the Proximal Sampler: Summary of isoperimetric assumptions and oracle complexities to generate s-accurate sample under different criterion. Ô hides (oyyloo(d=-)) factors. The zeroth-order oracle complexity of 7OD-MC is from Corollary 3.1 for achieving both KL and W2 errors. These theoretical results suggest that in the absense of isoperimetric assumptions, ZOD-MC excels in low-dimensions.
process that transforms a random variable into Gaussian noise. One most commonly used forward process is (a time reparameterization of) the Ornstein-Uhlenbert (OU) process, given by the SDE:
dX2 -X,dt + Vdd,, Xo ~ p.
where {B:) is the standard Brownian motion in Rdd The OU process that solves (1) is in distribution equivalent to sum of two independent random vectors: X, = x,=e-X, + v1- where (Xo, Z) ~ @ 7dd and yd is the standard Gaussian distribution in R. Denote ps = Law(X) for all 2 0. If we consider large, fixed terminal time T of (I), then pr is close to 7 Then, the denoising or backwards diffusion process, {X JoSOST, can be constructed by reversing the OU process from time T, meaning that Law(X,) = (Xw(Xx-r) for all E [0, By doing so we obtain the denoising diffusion process which solves the following SDE:
dx, = (X, + 2V (X.)d= + v2dB,, Xo PP~PT, OSIST,
(2)
where (Be) (Beoores is a Brownian motion in R4, independent of (Bi)osiST and V In pe is usually referred as the score function for Pt- Although the denoising process initializes at pr, we can't generate exact samples from pr- In practice, people consider the standard Gaussian initialization yd due to the fact that pr is close to 7d when T is large. The denosing process with the standard Gaussian initialization is given by
dX² (X, + 2V log (X.))t + V2dB,, ~
By simulating this denoising process (3), we can achieve the goal of generating new samples. However, the denoising process (3) can't 't be simulated directly due to the fact that the score function not explicitly known. A widely applied method to solve this issue is to learn the score function through denoising score matching [51, 24, 52]. Given learned score, denoted as s(,, one can simulate the denoising diffusion process using discretizations like the Fuler Maruyama or some exponential integrator. From theoretical perspective, assuming the learned score satisfies
(4) non-asymptotic convergence guarantees for diffusion models obtained in [5, 3, 11]. For instance, in [3], polynomial iteration complexities were proved without assuming any isoperimetric property of the data distribution and only assuming the data distribution has finite second moment and a score estimator satisfying (4) is available.
Ez-p, (1) 2) V In [x))]]] < Scoree vOAt<T.
In this work, consider instead the sampling setting, in which no existing samples from the target distribution available. Our sampling algorithm and thcoretical analysis are motivated from the denoising diffusion process given by (2) and its corresponding discretization through the exponential integrator in Algorithm 1. In particular, we first introduce an pracle-based meta-algorithm, DDMC, which integrates Algorithm and Algorithm 2, where the exponential integrator scheme of (2) is applied to generate samples and the score function is approximated by a Monte Carlo estimator assuming independent samples from a conditional distribution are available.
2.2 Rejection Sampling and Restricted Gaussian Oracle
Rejection sampling a popular Monte Carlo method for sampling a target distribution, p, based on the zeroth-order queries of the potential V. It requires that we have access to the potential function
3

---

Algorithm 1: Denoising Diffusion Sampling via Exponential Integrator
Input :N E Z+. 0 = to < < <N T - 8, score estimator {s(T tk. ) N-1
Output:220 :.N-
generate a sample zg ~ for = 0, 1, , do
generate & Tt such that & is independent to Eo. ... -k-11 2k+1 c 14411-10 ux + 2(clkt I)s(T tk) + Ve 11 16k.
end
Vn of some other distribution μ4, such that jr easy to sample from and exp(-V) V) I exp(-V,)) globally. Such distribution μ is typically called an envelope for the distribution p. With an envelope v, rejection sampling generates samples from p by running the following algorithm till acceptance:
1. Sample X ~ μ4,
2. Accept with probability exp(-V + (x)).
The rejection sampling is considered as high-accuracy algorithm as it outputs a unbiased sample from the target distribution. However, despite such a remarkable property, it has drawbacks. First, is nontrivial task to find an envelope for a general target distribution. Second, rejection sampling usually suffers from "curse of dimensionality". Even for strongly logconcave target distributions, the complexity of the rejection sampling increases exponentially fast with the dimension: in expectation it requires xd// many rejections before one acceptance, where x is the condition number for the potential V, see [9].
The Restricted Gaussian Oracle (RGO), which was first introduced in [31], assumes that an accurate sample from distribution (-1y) x exp v-) - ž || y/|²) can be generated for any y E gd, 7 > and any potential V. Implementing the RGO is challenging. is usually done by rejection sampling. However, most proposed methods [36, 18], only suitable for small 1).
Our proposed sampling algorithm, ZOD-MC applies the rejection sampling (Algorithm 3) imple- ment the RGO with large value of Details on ZOD-MC are introduced in Section 3.1.
3 Denoising Diffusion Monte Carlo Sampling
In this section, we first introduce DDMC and ZOD-MC in Section 3.1. Then we provide a convergence guarantee for DDMC in Section 3.2. Last, in Section 3.3, we establish the zeroth-order query complexity of ZOD-MC. Note DDMC is a meta-algorithm that still requires an implementation of its oracle, and ZOD-MC is actual algorithm that contains such an implementation. The theoretical guarantee of ZOD-MC (Sec. 3.3), therefore, is based on the analysis framework DDMC (Sec. 3.2).
3.1 Denoising Diffusion Monte Carlo and Keroth-Orden Diffusion Monte Carlo
Denoising Diffuusion Monte Carlo (DDMC). Let's start with known but helpful lemma on score representation, derivable from Tweedie's 's formula [45].
Lemma Let (Xth22 be the solution to the OU process (1) and p. LLa((X)). Then for all
t t>0 0.
V (l)p(x))= = Exa (o)(()12) (-12)
(5)
T-c"
" is the distribution of Xo conditioned on {X, x}.
where Po e(1x) & exp ( v()
_
This lemma was for example applied in [26] to do sampling based on the denoising diffusion process in (2). For the sake of completeness, we include its proof in Appendix C.5.
Due to (5), to approximate the score function V In ,, it suffices to generate samples that approxi-
mate (-ar(- [26, 27] proposed to use Langevin-based based algorithms to sample from (-lr)-) The first step of our work is to generalize this, with refined and more general theoretical analysis later
by considering oracle algorithm, DDMC, which assumes independent samples {2 that
((t)

---

Algorithm 2: Monte Carlo Score Estimation
Input :f E (0, T E IRd n(t) E Z4, 8(t) > 0. Out,
pi1 Oracle generate independent (=, such that W2 (o)) 8(1).
s(t, x) + Σn(t) x-e Rea
approximate Poje(-Izz are available. The Monte Carlo score estimator in Algorithm 2 is given by
n(t)
s(t,x)
(6)
where n(t) the number samples and 8(t) such that W2 WL((aa((2).)) (Laj (oje(-l=))] In Section 3.2, we will discuss how the performance of sampling depends nn(),, ((1).
S 8(t) for all i.
Zeroth-Order Diffusson Monte Carlo (ZOD-MC). Noticing that Lemma 1, the conditional distribution has structured potential function: summation of the target potential and quadratic function. Therefore, implementing the oracle in DDMC is equivalent to implementing RGO with y c'v: and 17 e2t 1. Based this, propose ZOD-MC, novel methodology based rejection sampling and DDMC. Rejection samping (Algorithm 3) can generate i.i.d. Monte Carlo samples required in Algorithm 2. Therefore, ZOD-MC, combination of rejection sampling and DDMC, can efficiently sample from non-logconeave distributions. See Appendix for more details.
Algorithm 3: Rejection Sampling: generating (2 in Algorithm 2
(n(t)
Input 2 E Rd zeroth-order queries of V. Output:2.
while TRUE do
Generate (E, u) ~ 7tt & [0, 1]: + e'x + e - L8;
return if S exp( V(2)+
end
Remark (Remark the optimization step) In theory, assume oracle access to the minimum value V... V. However, in practice we use Newton's 's method to find a local minimum. Throughout the sampling process we update the local minimum as we explore the search space.
Remark 2. (Parallelization) Notice that Algorithm can be run in parallel to generate all the n(t) samples required to compute the score. Contrary to methods like LMC that have sequential nature, this allows our method to be more computationally efficient and reduce the running time. This is feature that RDMC RSDMC doesn't 't benefit as much from.
3.2 Convergence DDMC
Our oracle-based meta-al meta-algonie algorithm, DDMC, provides framework for designing and analyzing pling algorithms that integrate the denoising diffusion model and the Monte Carlo score estimation. In this section, we first present error analysis to the Monte Carlo score estimation in Proposition 3.1, whose proof in Appendix C.3. After that, we leverage our result Proposition 3.1 and provide non-asymptotie convergence result for DDMC in Theorem 1, whose proof is in Appendix C.4.
Proposition 3.1. Let (Xe be the solution of the OU process (1) and pt Law(Xi) for all 0. mi(()
1 ((t) ---- with (r(D being sequence of independent random we define sl,, n( Di=l I-e-x
vectors such that W2(Law(z 13 (-)0(-1)) [ for all I > and x E Rd, then we have
E Inp. stt, xx1l (T- (ाP 8(t) n(( [1-e ay Covp(x).
(7)
Choice of (1) and n()). The error bound (7) helps choose the accuracy threshold 5(1) and the number of samples n(t) to control the score estimation error over different time. In fact, when
5

---

t increases, it requires less samples and allows larger sample errors to get a good Monte Carlo score estimator. If we assume Cov,(z) (dd for simplicity, then when small, the factor (I- ( and the choice of 8(L) = (ts) and n()) = 2 will lead to the - of order O( When i is large, the factor n----aa= ( and it only requires 5(t) = O(e'e) and ntt = S2(de =) to ensure the - is of order (=²)). In the latter case, the ((t is of larger order and nt) of a smaller order than the first case.
We now analyze the convergence of DDMC. Recall that Algorithm 1 is an exponential integrator discretization scheme of (2) with the time schedule 0 = Lo < (1 < ..... < lN = = for some > O. In each iteration, Fk++1 et*+1 xy + 2(ce4+1-fe 1)s((T tg 2..) v Ve2lfe11
Tεk, where &A 7d and s(T - f2. :) is the Monte Carlo score estimator generated by Algorithm 2. The trajectory of Algorithm can be wiicey characterized by the following SDEs: for all t [tx, fx+1).
dX,,, (X, + 2s tk X1, dt + Vdd,,, Xo
Xtx = 2k.
(8)
Therefore, the convergence of DDMC is equivalent to the convergence of the process (X, (XePosestN- which could be quantified under mild assumptions on the target distribution. Next, we present the moment assumption on the target distribution and our non-asymptotic convergence theorem.
Assumption 3.1. The distribution p has a finite second moment: Ex=
m oc.
Theorem 1. Assume that the target distribution satisfies Assumption 3.1. Let {Xe)e2o be the solution
of (1) with Pt = Law(Xe (Xt) and {X, 122 be the solution of (8) with qr. = Law(X.). For any be a time schedule such that 7h = 0()-2)) all l- = 0, 1, N 1. where "/k == tx+1 tg. Then
E 1) and T > 1, let = to < 1 < ... < IN =
N-
(L(psl9(N) S (d + mž)e 2T
me -(T--N)
5(T - tx)² + m(T-tta)
(1-e-2(2 2(7 227--
11
N-1
m m 30
(d+m))m
dy [1- 48 uyz
(9)
[I (T- 2773
(1-6 2(T 2(T- -o 20 12- 13
III
where 5(t), n(()) are parameters in Algorithm 2.
Remark 3. In Theorem 1, we characterize KL (tx)) instead of KL(pletx) due to the fact that kL(plq()) ) is not well-defined when the target distribution p is not smooth w.E.t the Lebesgue measure. turns out that ps is an alternative distribution to look at because ps is smooth for all 5 >> 0 and ps close to p when 8 is small (see Proposition C. This is standard treatment, referred to early stopping, in the score-based generative modeling literature [e.g.. 5, 3].
The terms II, III in (9) correspond to the three types of errors in Algorithm 1, the initialization error, the score estimation error and the discretization error, respectively. Such a decomposition is very common in analyses of diffusion models, see [5, 6, 3]. Since consider the sampling setting, the score estimation error is derived from the error analysis to the Monte Carlo score estimator, i.e., Proposition 3.1. A detailed discussion on these three types of errors provided in Appendix C.4.
Compared to existing analyses on diffuusion models, Theorem extends result in [3] from exponential- decay step-size to general choices of step-size, and recovers their sharp linear dimension dependence in the discretization error, with minimal assumptions on the target distribution. By assuming two consecutive step sizes of the same order, we perform asymptotic estimation the accumulated discretization errors and obtain a bound that depends on the step-size. Such kind of result helps to understand the optimal time schedule,
will discuss soon.
Discussion on the choices of time schedule. Under different choices of step-size, the discretization errors in the denoising diffusion model have the same linear dependence on d, but different dependence on The linear dimension dependence improves the results in [4], where (dd) discretization error bounds are proved for different choices of step-size. It is also a extension of the result in [3], where (d) discretization error is only proved for the exponential-decay step-size. In fact, Theorem implies that the exponential-decte constant in term of the inverse sarly-stopping time d Detailed discussions on different choices of time schedules is provided in Appendix C.5.
step-size induces an optimal discretization error up to some

---

3.3 Complexity of ZOD-MC
With the convergence result for DDMC in Theorem 1, we introduce the query complexity bound of ZOD-MC. Our analysis assumes a relaxation of the commonly used gradient-Lipschit condition on the potential. The formal statement is presented in Corollary 3.1, whose proof is provided in Appendix C.6.
Assumption 3.2. There exists constant L > 0 such that for any x² E arg argminyers Vyy) and x E 124 V satisfies V(x) - V(x*) S 1/2 || 10--"- x²1??.
Corollary 3.1. Under the assumptions in Theorem I and Assumption 3.2, if we set T 2 In( أ+يب
Exu
Tk min t2), 5 min( Fw $m2) ), e (T+))((6-))) then to obtain output (with distribution Qty) in ZOD-MC such that W2(p. p6) S EW2 and KL(ps. qex) S EKL, the zeroth-order query complexity is of order
mg
Õ(max
d+mī
d
KL.
2
22 d mm)
(d
2 1 12d
max OSKSN-1
exp (Z. 1|="==11 + || (10)
Exc.
where the Ô hides polylog( d+m2) factors. Eu2
Remark 4. If we assume WLOG that the minimizer of the potential is at the origin, i.e,, x² = 0, and further make reasonable assumptions that mžz, L and {1 ]12} } are all of order (d)) where { are the iterates in Algorithm I, then the query complexity of ZOD-MC is of order exp (O(d) log(s<r)) Even though this complexity bound has an exponential dimension dependence, it only depends polynomially on the inverse accuracy. Since it applies any target distribution satisfying Assumptions 3. and 3.2, this complexity bound suggests that with the same overall complexity, ZOD-MC can generate samples more accurate than other algorithms in Table 5, for large class of low-dimensiona non-logconcave target distributions.
Comparison to LMC, RDMC and RSDMC. When no isoperimetric condition is assumed, we compare convergence for ZOD-MC to convergence for LMC, RDMC and RSDMC.
In the absence of the isoperimetric condition, [1] demonstrated that LMC is capable of producing samples that are close to the target in Fl assuming the target potential is smooth. However, Fl is a weaker divergence than KI. divergence/ 2 distance. It has been observed that, in certain instances, the KL divergence/ divergence/Wassersteeeee Wasserstein-22 distance may still be significantly different from zero, despite a minimal FI value. This observation implies that the convergence criteria based on FI may not be as stringent as our result which is based on KL divergence/Wasserseenn that RDMC produces samples that are E-close to the target in KL divergence with high probability. Assuming the potential is smooth and a tail- gull-grothh condition, the first order oracle complexity is shown to be of order exp(e log d). [27] introduced RSDMC as an acceleration of RDMC. They were able to show that if the potential is smooth, RSDMC produces sample that is s-close to the target in KI. divergence with high probability. The first order oracle complexity is shown to be of order exp(log" (xp(l))"(d//)) Compared to RDMC and RSDMC, our result on ZOD-MC doesn't require the potential to be smooth as our Assumption 3.2 is only a growth condition of the potential. This indicates that our convergence result applies to targets with non-smooth, or even discontinuous potentials. Our result in Corollary 3.1 shows the zeroth-order oracle complexity for ZOD-MC is of order exp(dlog(e 1)), which achieves a better e-dependence compared to RDMC and RSDMC, at the price of worse dimension dependence. This suggests that, for any low-dimensional target, ZOD-MC produces more accurate sample than RDMC/RSDMC when the overall oracle complexity are the same. Last, zeroth-order queries cost less computationally than first-order queries in practice, which also makes ZOD-MC a more suitable sampling algorithm when the gradients of the potential are hard to compute.
distance. [26] proved
4 Experiments
We will demonstrate ZOD-MC on three examples, namely Gaussian mixtures, Gaussian mixtures plus discontinuities, and Müller-Brown which is highly-nonlinear, nonconvex test problem popular in computational chemistry and material sciences. Multiple Gaussian mixtures will be considered, for showeasing the robustness of our method under worsening isoperimetric properties. The baselines consider include RDMC [26], RSDMC [27], SLIPS [20], the proximal sampler [37], annealed
7

---

importance sample [42], sequential Monte Carlo [15], a parallel tempering approach with MALA proposals [30] and naive unadjusted Langevin Monte Carlo. All the experiments are conducted using NVIDIA GeForce RTX 4070 Laptop GPU with 8GB of VRAM and Pytorch.
4.1 Results for Gaussian Mixtures
Matched Oracle Complexity. We modify a 2D Gaussian mixture example frequently considered in the literature to make it more challenging, by making its modes unbalanced with non-isotropic variances, resulting in highly asymmetrical, multi-modal problem. We include the full details of the parameters in Appendix D. We fix the same oracle complexity (total number of 0th and 1st order V queries) for different methods, and show the generated samples in Figure 2. Note matching oracle complexity puts our method disadvantage, since other techniques require querying the gradient, which results in more function evaluations. Despite this, we see in Figure la that our method achieves both the lowest MMD and W2 using the least number of oracle complexity.
220-MC
ESOMC
ESSNIC
Z0D-FC
203
ROMC
1090
HSDNC
g
2000 4002
5005
5000
10000
2202
4200 5000 Crada Complenty
8008 10002
Ohudia Compledly
(a) Sampling accuracy against oracle complexity. For any fixed oracle complexity, ZOD-MC has the least error both in MMD and W2. Note diffusion based methods do not have an initialization. Thus curves
(b) Sampling accuracy against dimension We demon- strate that other diffusion based methods seale poorly with dimension. On the left we plot the error when evaluating statistics of the generated samples and on the right analyze the W22 metric.
don't 't start at the same y-value.
Figure 1: Accuracies of different methods for sampling Gaussian Mixture
Robustness Against Mode Separation. Now let's further separate the modes in the mixture to investigate the robustness of our method to increasing nonconvexiyymennstabiityy More precisely, we scale the means of each mode by constant factor to have mode located at (0, R); doing so increases the barriers between the modes and exponentially worsens the isoperimetric properties of the target distribution [49]. Figure 4a shows our method is the most insensitive to mode separation. Being the only one that can successfully sample from all modes, as observed in Figure 3, ZOD-MC suffers less from metastability. Note there is still some dependence on mode separation due to the dependence in the complexity bound in Corollary 3.1.
RION:
Figure 2: Sampling from asymmetric, unbalanced Gaussian Mixture. All iiffusion-based methods (ZOD-MC, RDMC, RSDMC) use 2200 oracles per evaluation. Langevin and the proximal sampler set to use the same total amount of oracles as diffusion based methods. While other methods suffer from metastability, ZOD-MC correctly samples all modes.
Dimension Dependence Against Other Diffusion Based Methods. One drawback of our method, is its bad dimension dependence when compared to diffusion based methods. For instance, RDMC and RSDMC have a dependence of (xog(()og())) ())((==))) and exp(O(log" (d) respectively. in comparison to our (IloO())((lo((e))))))) empirically that these methods don't scale well with dimension either. To demonstrate this we sample 5 points on the positive quadrant and use them means for GMM. We then evaluate statistics on the generated samples and W2 as a function of dimension. We observe Figure 1b that under fixed number of function evaluations our method results in the lowest Wz. More details are in Appendix D. Discontinuous Potentials. The use of zeroth-order queries allows ZOD-MC to solve problems that would be completely infeasible to first order methods. To demonstrate this, we modify the
Despite this theoretical disadvantage, we find
8

---

Figure 3: Gaussian Mixture with further separated modes (R 26). ZOD-MC can overcome strength- ened metastability and sample from every mode, while other methods are stuck at mode at origin, where every method is initialized.
potential in Figure 2. We consider V(z) + U(x) where is a discontinuous function given by U(x) [|| [s<[|==||<]1) This creates an annulus of much lower probability and strong potential barrier. the original problem, the mode centered at the origin was chosen have the smallest weight (0.1), but adding this discontinuity significantly changes the problem. As observed in Figure 5, our method still able correctly sample from the target distribution, while other methods not only continue to suffer from metastability but also fail to see the discontinuities. We quantitatively evaluate the sampling accuracy by using rejection sampling (slow but unbiased) to obtain ground truth samples, and then compute MMD and W2. See Appendix D.2 for details.
M30MC
2.8
AODME
9.9
20
203 MC
Largor
KDNC
35-
Siai
Langen
Tue
Kodks
(a) Sampling accuracy against how separated modes 70D-MC is (b) Average Score Error a func- the least sensitive mode separation. The oracle complexity is fixed, tion of time. Shaded is the stan- independent of how modes are separated.
dard deviation of the errors.
Figure 4: Accuracies of generated samples against dimension and Score Error. On the right, the result for SLIPS is not directly comparable as it has different forward process.
Score Approximation of Diffusion Based Methods. One explanation of our method's great success in comparison with RDMC and RSDMC is the ability approximate the score correctly. We select an unbalanced assymetrical 5d GMM and evaluate the average I,2 score error between methods. On Figure 4b show that the best approximations of the score are found by using ZODMC as an estimator as opposed to other methods. Even as ł increases and the approximation gets harder we are able to retain accuracy and therefore generate high quality samples.
Figure 5: Generated samples for discontinuous Gaussian Mixture. method can recover the target distribution even under the presence of discontinuities. The same oracle complexity is again used in each method, 3200 per score evaluation in Liffusion-based approaches.
4.2 Results of Müller Brown Potential
The Müller Brown potential is toy model for molecular dynamics. Its highly nonlinear potential has modes despite of being the sum of 4 exponentials. The original version has of its modes corresponding to negligible probabilities when compared to the 3rd, which is not good to visualization and comparison across different methods. Thus we consider balanced version [35] and further translate and dilate v and y so that one of the modes is centered near the origin. The details of the potential can be found in Appendix D.5. Our method the only one that can correctly sample from all 3 modes observed in Figure 6 (note they are leveled).

---

Figure 6: Generated samples for the Müller Brown potential. We overlay the generated samples on top of the level curves of V (x)) All methods use 1100 oracles.
Acknowledgments and Disclosure of Funding
The authors are grateful for the partially support by NSF DMS- DMS-1847802, Cullen-Peck Scholarship, and GT-Emory Humanity.Al AI Award. We thank the anonymous reviewers for their helpful comments.
10

---

References
[1] K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and S. Zhang. Towards theory of non-log-concayy sampling: first-order stationarity guarantees for langevin monte carlo. In Conference on Learning Theory, pages 2896-2923. PMLR, 2022.
[2] C. Bélisle, H. E. Romeijn, and R. I.. Smith. Hit-and-run algorithms for generating multivariate distributions. Mathematics of Operations Research, 18(2):255-26) 266, 1993.
[3] J. Benton, V. De Bortoli, A. Doucet, and G. Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. ICI.R, 2024.
[4] H. Chen, H. Lee, and Lu. Improved analysis of score-based generative modeling: User- friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages 4735 4763. PMLR, 2023.
[5] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. ICLR, 2022.
[6] Y. Chen, Chewi, A. Salim, and A. Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, pages 2984-3014. PMLR, 2022.
[7] Y. Chen and R. Eldan. Localization schemes: A framework for proving mixing bounds for markov chains. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 110-122. IEEE, 2022.
[8] Y. Chen and K. Gatmiry, A simple proof of the mixing of metropolii-adduuseed langevin algorithm under smoothness and isoperimetry. arXiv preprint arXiv:2304.04093 2023.
[9] S. Chewi. Log-concave sampling. 2023. Book draft available at https: chwwwsinho. github.ion io/.
[10] S. Chewi, T. Le Gouic, C. Lu, T. Maunu, and P. Rigollet. Svgd as kernelized wasserstein gradient flow of the chi-squared divergence. Advances in Neural Information Processing Systems, 11-2098-2109 2020.
[11] G. Conforti, A. Durmus, and M. G. Silveri. Score diffusion models without early stopping: finite fisher information is all you need. arXiv preprint arXiv:2308. 12240, 2023.
[12] A. S. Dalalyan and A. Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278-53) 2019.
[13] A. S. Dalalyan and L. Riou-Durand. On sampling from log-concan density using kinetic langevin diffusions. Bernoulli, 26(3):1956-199 1988, 2020.
[14] V. De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. TMLR, 2022.
[15] Del Moral, A. Doucet, and A. Jasra. Sequential monte carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(3):41 1--1666,,66 2006.
[16] R. Dwivedi, Y. Chen, M. Wainwright, and B. Yu. Log-concave sampling: Metropolis-hastings algorithms are fast. Journal of Machine Learning Research, 20(183):1 4-2, 2019.
[17] M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1-17, 1991.
[18] J. Fan, B. Yuan, and Y. Chen. Improved dimension dependence of a proximal algorithm for sampling. In The Thirty Sixth Annual Conference Learning Theory, pages 1473-1521. PMLR, 2023.
[19] A. Garbuno-Inigo, F. Hoffmann, W. Li, and A. M. Stuart. Interacting langevin diffusions: Gradient structure and ensemble kalman sampler. SIAM Journal on Applied Dynamical Systems, 19(1):412-441) 2020.

---

[20] L. Grenioux, M. Noble, M. Gabrié, and A. Oliviero Durmus. Stochastic localization via iterative posterior sampling. Proceedings of the 41st International Conference on Machine Learning. volume 235, pages 16337-16376. PMLR, 21-27 Jul 2024.
[21] Y. He, K. Balasubramanian, and M. A. Erdogdu. On the ergodicity, bias and asymptotic nor- mality of randomized midpoint sampling method. Advances in Neural Information Processing Systems, 33:7366-7376, 2020.
[22] Y. He, Balasubramanian, B. K. Sriperumbudur, and J. Lu. Regularized stein variational gradient flow. arXiv preprini wrXiv:2211.07885 2022.
[23] Y. He, T. Farghly, K. Balasubramanian, and M. A. Erdogdu. Mean-square analysis of discretized itó diffusions for heavy-tailed sampling. Journal of Machine Learning Research, 25(43):1 144, 2024.
[24] Ho, A. Jain, and Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-666 2020.
[25] D. Holzmüller and F. Bach. Convergence rates for non-log-coneave sampling and log-partition estimation. arXiv preprint arXiv:2303.03237, 2023.
[26] X. Huang, H. Dong, Y. Hao, Y. Ma, and T. Zhang. Reverse diffusion monte carlo. ICLR, 2024.
[27] X. Huang, D. Zou, H. Dong, Y. Ma, and T. Zhang. Faster sampling without isoperimetry via diffusion monte carlo. COLT, 2024.
[28] M. A. Iglesias, K. J. Law, and A. M. Stuart. Ensemble kalman methods for inverse problems. Inverse Problems, 2954)00 2013.
[29] H. Lee, J. Lu, and Y. Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[30] H. Lee and Z. Shen. Improved bound for mixing time of parallel tempering. arXiv preprint 33X1v:2304.01303, 2023.
[31] Y. T. Lee, R. Shen, and K. Tian. Structured logconcave sampling with a restricted gaussian oracle. In Conference on Learning Theory, pages 2993-3050. PMLR, 2021.
[32] G. Li, Y. Wei, Chen, and Y. Chi. Towards faster non-asymptotic convergence for diffusion- based generative models. ICLR, 2024.
[33] R. Li, M. Tao, S. S. Vempala, and A. Wibisono. The mirror Langevin algorithm converges with vanishing bias. In International Conference on Algorithmic Learning Theory, pages 718-742. PMLR, 2022.
[34] R. Li, H. Zha, and M. Tao. Sqrt(d) Dimension Dependence of Langevin Monte Carlo. In ICLR, 2021.
[35] X. H. Li and M. Tao. Automated construction of effective potential via algorithmic implicit bias. arXiv preprint arXiv:2401.03511, 2024.
[36] J. Liang and Y. Chen. A proximal algorithm for sampling, arXiv preprint arXiv: 22X.v:2202.13977 2022.
[37] Liang and Y. Chen, A proximal algorithm for sampling. arXiv preprint arXiv:2202.13975 2022.
[38] Q Liu. Stein variational gradient descent gradient flow. Advances in neural information processing systems, 30, 2017.
[39] L. Lovász and M. Simonovits. The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. Proceedings / [199]] 3 ss annual symposium on foundations of computer science, pages 346-354. IEEE, 1990.
12

---

[40] L. Lovász and S. Vempala. Hit-and-run from a corner. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 310-314, 2004.
[41] K. L. Mengersen and R. L. Tweedie, Rates of convergence the hastings and metropolis algorithms. The annals of Statistics, 2411)1011-12, 1996.
[42] R. M. Neal. Annealed importance sampling. Statistics and computing, 11:125-1383 2001.
[43] I.. Pardo. Statistical inference based divergence measures. CRC press, 2018.
[44] L. Richter, J. Berner, and G.-H. Liu. Improved sampling via learned diffusions. ICLR, 2024.
[45] H. E. Robbins. An empirical bayes approach to statistics. Breakthroughs Statistics: Foundations and basic theory, pages 388 1988.94. Springer, 1992.
[46] G. O. Roberts and R. L. Tweedie. Geometric convergence and central limit theorems for multidimensionall hastings and metropolis algorithms. Biometrika, 83(1):95-110, 1996.
[47] A. Roy, L. Shen, K. Balasubramanian, and S. Ghadimi. Stochastic zeroth-order discretizations of langevin diffusions for bayesian inference. Bernoulli, 28(3):1810-188 2022.
[48] A. Salim, L. Sun, and P. Richtarik. A convergence theory for svgd in the population limit under talagrand's 's inequality tl. In International Conference on Machine Learning, pages 19159-19152. PMLR, 2022.
[49] A. Schlichting. Poincaré and sob-soolev inequalities for mixtures. Entropy, 21(1):89, 2019.
[50] R. Shen and Y. T. Lec. The randomized midpoint method for log-concave sampling. Advances in Neural Information Processing Systems, 32, 2019.
[51] J. Sohl-Dickstein E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. ICMI, 2015.
[52] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representationss 2021.
[53] F. Vargas, W. Grathwohl, and A. Doucet. Denoising diffusion samplers. arXiv preprint arXiv:2302. 13834, 2023.
[54] Vargas, A. Ovsianas, D. Fernandes, M. Girolami, N. D. Lawrence, and N. Nüsken, Bayesian learning via neural schrödinger-föllmer flows. Statistics and Computing, 33(1):3, 2023.
[55] Vargas, S. Padhy, D. Blessing, and N. Nüsken. Transport meets variational inference: Controlled monte carlo diffusions. In The Twelfth International Conference on Learning Representations, 2024.
[56] S. Vempala and A. Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[57] K. Yingxi Yang and A. Wibisono. Convergence of the inexact langevin algorithm and score- based generative models in kl divergence. arXiv e-prints, pages arXiv-2211, 2022.
[58] Q. Zhang and Y. Chen, Path integral sampler: a stochastic control approach for sampling. ICLR, 2022.
13

---

A Related Works on Zeroth-Order Sampling
The zeroth-order sampling algorithms have been widely studied in the past decades. There is class of zeroth-order sampling algorithms, including the Ensemble Kalman Inversion [28] and the Ensemble Kalman Sampler [19], that are based on moving set of easy-to-sample particle according to certain dynamics. However, these methods require (noisy) observations from the target distribution rather than queries of the potential function. Within the zeroth-order sampling algorithms using queries of the potential function, one type of methods make use of the zeroth-order queries to approximate the gradient and apply some first-order sampling algorithm [12, 47, 23]. Since it based on the first-order methods, the analysis of this type of algorithms assumes the target distribution satisfies certain isoperimetric property in general. The other type of methods utilize the zeroth- queries directly without relating to the gradient. Such methods include the Rejection sampling algorithm, the Metropolized Random Walk (MRW) [41, 46], Ball Walk [39, 17]. Hit-and-Ruu algorithm [2, 40J. The rejection sampling algorithm requires to finding envelope function which is easy to sample from. This could be difficult. MRW requires sufficient smooth and light tail of the target distribution to mix fast. Ball walk and Hit-and- Run algorithms assume the target distribution is compactly supported. In this paper, we develop a zeroth-order sampling algorithm based on the reverse OU process. Our algorithm does not suffer from the difficulties in the rejection sampling and MRW, and our analysis does not assume isoperimetric property and compact support of the target distribution.
[25] also studies the complexity of a zeroth-order sampling algorithm that combines an approximation technique and rejection sampling. For target distributions that are m-diifereeniable with compact support, [2e][eh 12] implies a complexity of order Qa(e Qa(=-d/m) to reach an e-aceuracy in KL-divergence, where the dimension dependence is implicit. Compare to our result in Corollary 3.1, both complexities are polynomial in and exponential in d. Our complexity smaller for less smooth targets (m < 2) while their complexity is smaller for smoother targets (m >> 2). However, result [25] only applies to smooth targets (m > 0) with compact supports, while our Corollary applies to more general target distributions which can be with full support with even discontinuous potentials.
B More Details on ZOD-MC
In this section, provide more details on how rejection sampling (Algorithm 3) in ZOD-MC implements the oracle in DDMC, i.c., generating Monte Carlo samples required Algorithm 2. Construction of envelope. If we have V as minimum value of V, then by noting that:
x- --1- < <-V-
||=='=| o-
(2)
EEER Rd.
We are able to construct an envelope for rejection sampling. particular we propose a samples from N( (';e'z, e2t 1 1) and accept proposal with probability exp(-V(2)) + V*).
Sampling from the target distribution. Algorithm implements the oracle in Algorithm 2 with 5(1) = 0. When nt)) increases, Algorithm 2 outputs unbiased Monte Carlo score estimators with smaller variance, hence closer the true score. We will quantify the convergence DDMC next and consequently demonstrate that ZOD-MC can sample general non-logconcave distributions.
C Proofs
C.1 Properties of the OU-Process
In this section, we introduce and prove some useful properties of the OU-prcees. Throughout this section, we denote (Xilt20 as the solution of (1) with p. == Law(X,). For any s,t > 0, Pt. denotes the conditional probability measure of X, given the value of X..
Proposition C.1. (Decay along the OU-Process) Let {Xelezo be the solution of (1) with Pt = Law (X₂). Assume that the initial distribution p satisfies Assumption 3.1. Then we have
W2(po,)2 < (1 --- t)2mm + (1 (1-e- 22)d,
(11)
1 e 4
1 _ -
and k
<
2 e 21 d
(12)
14

---

Proof of Proposition C.I. The proof for (11) is based on the fact that the solution to (1) can be represented by
x -xo 11---221 4120. O.
(13)
We have
W2(2:.) p)2 s [ - xoll 2 B(xo,
+ v1-e
= =(1 - - + (1 2d)
Next, prove (12), have
f = p P
/
( =
where the inequality follows from the convexity of KL divergence. According to (13), Pejo(-lu) is Gaussian measure with mean e and covariance matrix (1 2- According to [43], we have
(L(pgo(-lv)l>> KL(N(e "v,, (1- -2)1 E (
2 dli(1 - -2) - e 26 d + e 22 [1/1
As result, we get
d 28 +
21 / (Ivll'(dv)) p(dv) S e
1
kL(phh") s - 1n(1 -
21
d
2t m22
2
2(1
20)
2
where the last inequality follows from the fact that In(1 + x) S x for all x > 0.
Proposition C.2. (Stochastic Dynamics along the OU-Process) Let {Xth120 be the solution of (1). Define mx())) = (xx and (X,) = (1x Exo=po.(1X0 me (X.(X))) Then we have for all
22-2t
[xi]] = e1-e 21)2
E (X)
dt
e
The above proposition is known in stochastic localization literature [7] and diffusion model litera- ture [3]. We present its proof for the sake of completeness.
Proof of Proposition C.2. For any T > 0, from (13), we have the conditional distribution
Poi(dr|(X,) & exp - 1 ||x - e 11112 'x
2 1 p(dxx)
where (Xcro PosesT is the solution of (1), Noticing that the solution of (2), {.rhosesT is the reverse process of JoJoeTT and it satisfies X, = XT in distribution for all E [0, [J. Therefore, suffices to study
1 || e xx]
Zfj (dx((d)|_x) = Z- exp (-
2 2(T )p(dr)
1 e ((T-1)
e (T-
= exp
||0||
1- e----(1-- 2(T-0) (z, x()r)
21
e
2(T
= Z exp(hx(z))p((d)))
(14)
where the normalization constant Z, Sau (xp(h)( (djr- x+- in distribution for all E [0, T] and
= We have [ojeddr
m, (X,) = x Rote (. (11 [Xo] Exx Nr. a [xo] my (XT
(15)
(X.)) == Cov Cov Xo ( (118,) (Xo)
= X (Xn) = En - (XT-
(16)
where the above two identities hold in distribution. For simplicity, we denote a, = v1 2- Then
hx(x) = - - 1| - oT= - 1(x, X,) is stochastic process linearly depending on
15

---

(Xire2o. The conditional measure ( (x) is teeasurevallued stochastic process, whose dynamics can be studied by applying Itö formula. First we have
dh+(x) =o- ||>|| dt (oT 1) '
+ or (x,, Xx)dt
+ tor 1) (z. dxx).
(17)
[1)()):(<))= = ( 1) ||>||| X]..
(18)
Since {XiJosest solves (2), according Lemma it satisfies that
(T (T- X 222 dd++++++ 22d
dx, = (X, + 2T (
= (- 1- Xx, + 2(1 o3 (X))) + v2dB..
(19)
Based on (17), (18) and (19), we have
dZt =
exp (z) (d)) + ([]((())))x)))))))(
Rd
3 Zydl
+ ( - 1) -
20 (0 Z.d
Z,dt
+ + (0 1) (m, (x)).
1
and dln 2, = Z, dz, - L, 2|
2
- + o 2 --- 1)) E 2o (118,) [1 [[=]|]]dt
+ (072, - 1) 1) / 20
(m) X,)
+ + 2 1)a2 (x.,
+ +07- 1) m| (xx) dt.
(20)
20 (del
If we define (x(X,)
Z exp(hı (x)), then apply Itô's formula again and we have p(dz)
(X,(X,) dexp (In (X.))
(I Re + R4 (X
( (x.), ((.(.)
(((()))))++))) Re (xXx)) Z, + (hx()) - In Z,, (x) Zz]. (21)
Now combine the results in (17), (18), (20) and (21), we can derive the differential equation of mi (X:):
(X,) d [ =R(((x))
JR'
[ (d)h+(x) dln Z4 + " (((h((x) In Z,, he(a)) In Z:)) 20 (o X.)
Raa
-T BBy (x,) ||=0|| x2]
+ + - 1)- $ 20 oT o. 2 - " (10)) (x X,dt
+ 1o,-1077" -1) 10) [XX,
-r 9.1 (1118)) ((1.)) ||,||| (X,)dtt
-077 - 1)- 1 20 - om) X,dl
07-1(07" 1)²s m. (x,)
- -072,0772 - 1) (Xx)) 1 mr (X.)dtt
+ + (07= - 11) (-188)) |||0 (X,))1 dt.
(22)
16

---

Utilize (19) and the definition of 0s all terms with factor dt in the above equation cancel and (22)
can be simplified
V2e- (T-
dm,(X;)= = 1- e -2((T-1) E (o)e(-1X,)
& (or m.(X.))dB.)
V2e (T-t)
-2(2-111 (x,
(23)
Last, we derive the differential equation that Ex,=p. [X,]] satisfies. Let f(t) = Ex.ep (X,)]
and g(t) = Ex.-o. [X,)² be two deterministic functions on [0, 27. According to (16) and (23),
we have
d dt
d Ex (Xx-)()
fT t)
d
ExiNpT Ex((X
dc
d
E Ex
[ (o) (x02] (x,
dt
d
Eeupl
[x 82
- Exempe (X,)
Ex
dt
dt
2e -(T-))
E Ex-ppr- (X,)
(1 - c e-2( 1))
2e -(T
(1 e 2(T 2(T- ( - 1).
where the last inequality follows from the Itô isometry. Proposition C.2 is then proved by reverse the time in f and g.
C.2 Proofs Section 3.1
Proof of Lemma 1. Based on (13), we have = (e-*) * (VI e 21 #yd where (e *p is the pushforward measure of p via map Rd + - and (vi e- 27 #y is the pushforward measure of 7d via map x E Rd + vI 2 Rdd The pushforward measures (e-*) #y and
(V1 e- 20 ) can be written as
(e ()) e p(e'(e"'a and
||
(V1 2-- ) ( (2 21) $ exp ( 2(1 20) )dr,
respectively. Therefore the score function V In (x() can be written
x 2 2|1
Vlnp(()) = pp(x)) ed
(2T -t
-21) V cxp
2(1 c 21) )p(eddz)
| e 2211
= -p(( (2T(1 c 21)) V
exp (
2(1 - E 20) )((2z)
/
1 1z
Pajo (x12))((2))
e 2f 2t
Pe (z)
e
1-c-2 21 Poje (dz(z))
where the last step follows from the Bayesian rule and
1 || - - 1
Poj(-11)) x p.o(xl))p() x exp (- V(.)
2
e
17

---

C.3 Proofs of Section 3.2
Proof of Proposition 3.1. With the score estimator given in Algorithm 2, we have
E| V (X):) - s(t, I
= Px
| pe)))
21,
(t()
1
c
21
n(()
(()
x
Σ
Zti 2t,1 [1]]
m(t) 2=1
21
n(t) 1=1
1 21
where {=1 sequence of i.dd samples following po that are chosen such that Ell 01, ze,i [x] (ssppj((-1z)), Law for all 0 and 1,2, n(t). Based on Lemma
1, I-c pun is sequence of unbiased i.d. Monte Carlo estimator of v Vlnp(()) for all > 0 and E R Therefore, we get
[[[VVlup - x()]
m(t)
Exmpi [[V]np(()) 1
Teii x +11 + +E|l (tt)
1
It, 24,
n(t)
1 e
((t)
F1,1 c-2
x
E Bxy
Poj (112)]
6 2イ, x |1
(1)
c-
e 21
n(C
21, 205il
e1- 21 n(t)²
The first term the above equation, Ni. related to the covariance poja (-)xt)), which is studied Proposition C.2. We have
21
(())
N1
Expop (oon
(1 e e-21 (t))
2t
Brop ftrace (Tace(E((1)) [I)]
e 2-22 (1())
-t
Bang trace Eoo (z))
22222 c 2t (1-e-20 ntt) Covp(x))
ntt)
1
where the inequality follows from Proposition C.2 indicating that Eespp (rrac(EE(<))) is increasing function.
The second term No characterize the bias from the Monte Carlo samples and the bias can be measured by the Wasserstein-2 2 distance:
26
((t)
B | z1.4 21. $ [|=re. zc,
N₂ S
(1 e 20 rt)²
21
n(()
Baape [2 Pojt (11)( (Wa(aa Poje (n<((=))))
(1 e e-22 2032 nx)))
6(t)
(4) follows from the estimation on N₂ and N2.
C.4 Proof of Theorem
In this section, we introduce the proof of our main convergence results, Theorem Recall that the convergence result in Theorem 1, three types of emrors appear in the upper bound: the initialization
18

---

error, the discretization error and the score estimation error. Our proof compares the trajectory of {Xi that solves (8) and the trajectory of [X, KoJosr that solves (2). We denote the path measures of (SI)T and { (orJoSisT by p and Q rrespectively. Next, we introduce a high level idea on how the three types of errors are handled.
1. Initialization error: the initialization error comes from the comparison between {Xi)osesy and "Xp""Jussss To characterize this error, introduce the intermediate process {XF" JoSIST
d dxp" = (X1" 2s(T la, X )dl v2dB,, Xo pr: L [kx, (++1),
(24)
in (24) and denote the path measure of { (X.T) rosisT by Q'r, Both processes are driven by the estimated scores and only the initial conditions are different. We factor out the initialization error from KL(ps qtx) by the following argument:
(L(pl)))x) = (L(psl9T-6)
- f In dpp"
dPr dQ dQ dp = f In dQer dQ dp
-II(PMr (QPT) / (L(PPTIQ"M) (L(p)l7"),
dQpr dppr
dQ
where the inequality follows from the data processing inequality and the last identity follows from the fact that dQFr
dQRr dor
which is true because the processes (XeJoSeST dyZ.
aQ aQp
and {XP"" Josisr have the same transition kernel function. KL(Prl>d) is the initialization error and is bounded based on (12) in Proposition C.I.
2. Discretization error: the dicretization error arises from the evaluations of the scores at the discrete times. We factor out the discretization error from the KL(PPr (Pr) via the Girsanov's Theorem.
KI. (PP QPT))
Eppr [Inr-- - s(T - 14, xx,)l
21
Eprr
V VImpr-(XX)) V Impr-4 (Xte)) (1
k=
discretization error
N
|| Pr (X,,, s(T tk, x1,
0=
score estimation error
We bound the discretization error term in the above equation by checking the dynamical properties of the process { IV P. (X,) JoSIST. Similar approach used in the analysis of denoising diffusion models, see [3]. For the sake of completeness, we include the proof in Appendix C.7.
3. Score estimation error: as discussed in the discretization error, the score estimation error is the accumulation of the - between the true score and score estimator at the time schedules {T - &x ) N-1 In the analysis of denoising diffusion models, [5, 4, 3], it usually assumed that such I score error is small. In this paper, we consider do sampling via the Reverse OU-process and score estimation. One of our main contribution is that we prove the 1,2 score error can guaranteed small for the class of Monte Carlo score estimators given in Algorithm 2. The 2 score error upper bound is stated in Proposition 3.1.
19

---

Proof of Theorem 1. First we can decompose (L(psl into summation of the three types of error.
KL(po = (
- fIm In dpp"
dQr dp = - -f
d dQ dQur dQr
)dper
dQPT KL(PP= /
dQ d dp
KL(PPT)QPT) -KI((pT1"))
sx+1
KL(prh +
Eppr Vinpr-((X)) - -s(T tky tg, x1x) 11)))3aa
tu+1
S kL(pTh
Eppr
(X)r- Impr-cn in (X,))l2
initialization error
discrctization error
N-1
EPT
[1]
impr- (X - tu
-t,, X )1
2=0
estimation
where the first inequality follows from the data processing inequality. The second inequality follows from Girsanov's 's theorem and [6, Section 3.1]. According to Proposition C.I and the assumption that 1, the initialization error satisfies
eT
KL(prh>*) -
2 - 27 d
_
2T m3 --_
S (d + mn)e 27
(25)
2
According to Lemma 2, the discretization enror satisfies
E Eper (Ipr--((()))) V Vlupr-4 (Xx))
1
%
d
1 e 2(T 2
kmD
2(T (x) yy
E [trace (rraaceETT-, (XT- [rrace (Er- (Xr (Xr-
(26)
2-2(T- y
Reordering the summation in the second term and we have
2T -((TTtt))
E trrac(Er u (Xr- }) (Iraco(Er- (Er (Xr (XT-
2(T 32
km0
N-1
c 2[T - +)) 74 20T 2CT 22)22
- -2-
E trace (Er-1, (Xr-
e
e- 2(T 2(T 2 1912
k=
23
El
trace Ex (Xr))
(1
22yy2
N-1
2T 4.) (1 w
R trace (X--x ))]
2(7 207- 401
2T
(1 27 tracc Ex (XT)]]
(27)
Recall that (X,) Cov(Xo X.) for all 0 S15T We have
E[trace (X.))) = E(Cov(Xo x.)] s [[ S m²
(28)
and E trace (X:)) = E Xx)] = Covo(oo e' X.
<E Xo e' x.I [x.]]
"e l)d.
(29)
20

---

where the last identity follows from (13). (29) and (28) implies that E trace (x..) & (1 + m²)
for all 0 & T. Therefore, from (26) and (27), the overall discretization can be bounded
1++1
Eppr |||
In pr (X
(xxx)) )l
N-1
dr
N-1
(d + 7 (1-e- (1 - 2 12-1))
mae -2r 70
(30)
2(7
12)
(1 e1-y2
k=0
k=
Last, according Proposition 3.1, the score estimation error satisfics
por
V Ia pr - (Xt,) s(T' Lk, Le, ]1
The 2(T--x)
mn
6(T -x)2
1x) n(T bx))
(31)
(1 e----ar--z2)
k=0
and (9) follows from (25), (30) and (31).
C.5 Discussion on the Step-size
In this section, we first state error bounds of DDMC under different choices of step-size. Then we provide the detailed calculations. Last we compare our results in Theorem existing results on convergence of denoising diffusion models.
In the following discussion, we assume ö(T - t2)² < drge? and n - -x) 2x 2(T (4)) for all & 0, 1......,.. .N- - 1. that the score estimation emrrr is dominated by the discretization error. For different choices of step-size, we discuss the parameter dependence of the error bound (9) under the assumptions d(t) and nt).
constant step-size: the constant step-size is widely considered in sampling algorithms and denoising diffusion generative models. It requires for all 0 < & < N - 1. Then
kL(pslaxx) ) S (d mī)e 27
(d+m3 N²
(T (T+ +
dI [T (T+8-)). N
2. linear step-size: the linear step-size is considered by [6] as an interpretation of the uniform discretization of diffusion model with non-constant diffusion coefficient [52]. It requires
tu T (8 (N k)))² with y vT- for all
N 1. Then
KL(pslqew) z (d + mē)e +
(d+m²)T YT N
(T 881 ar (T +8-))
3. exponential-decay step-size: the exponential-decay step-size considered to be optimal in SGMs [6, 3J. It requires 74 mmin(1 T (x) for some (0, 1). Then
KL(pslaww) S (d + mz)e
(d+m²) N (T + In)))) + $ (T + +nn
The purple terms are denoting the discretization errors. For all of the above choices of step-size, the error bounds have the same linear dimension dependence and different dependence on the early stopping parameter 8. Next, we provide detailed calculation of these error bounds and derivation of optimal 5-dependence.
1. constant step-size: when 7h = 7 for all k 1, ,,N, have T La 8 (N k)> and
(0())
if - 4/ > 1,
7
0 7
1 1- e 2(T
if - 44 < 1.
T tk
21

---

Therefore
(d + m²) 7k 7h-
N-1 1
2(T (4)
2(T 1211
- e1- bz
k=0
(d+ n
dy²
Σ
(d (d+ dh
Σ
(T --(+(( - 1(-1)
(T 1x)
1<T
5-T-
(d + m3)T
dT²
ddt dy f'' (2dt)
o
+ (d (d+m))+ mb
N
N
(d + m m
dT²
(d + m²)??
dI
N2
N
N282
N8
2. linear step-size: when T 1/- = (6 (N - k))))² with 7
vT-A N
we have 7/ (25+ + (2N
=
2k 1 = @(vT 7x and
( -
i - 4 > 1,
7kk
1 - ((T
0 VT tx
7
if - L/ < 1.
Therefore
N-1
(d + 7x
N-1
d 2 e 2(2 b2)
e 2(T-1x) (1 c 2(T 1)-
k=0
=0
Σ
(d m²y? TT (T 1k-1) + dr2 - tk-1)
+ mz))
+ dy2
+
Σ VT [T(T 1x-1)
T-
S<T-
I ldl + 7d S låde + 7all+22(1 + m2) / t 2d + +d S. f( (idd))
7d + m3)
=0 (d m3)
+ N + (d (d+ dT'
dT
N2
N28 N8.
3. exponential-decay step-size: when n = *min(1, T 1--t)) [x) with n: T+bm(1/5) N we have
7
[((k)
if t2 1,
(((k).
1 - e 222
if 1 < 1.
Therefore
N-1
(d + mZ) 7x 7/-
N-1
dr
2(T (2) (1
2(T 4 1)32
T 121
k=d
(d id+min mg) 3 + dx²
Σ
(d + m3) nx 222 mx (T (xx) -xx= + dRyye - (x) 11)
<T
6KT-4K11
0
(d+ di N + x² (d mž) (d))))) 1'
d'd + nd {- d'
= (d (d+mi) + d(T d(T + +I((/0(())))))
No
4. Optimality of the exponential step-size: assuming that 7 O(7e-1) for all l: 0, L.... .N - 1. the exponential step-size actually provides the optimal order estimation for the error terms. Noticing that the error terms all depend on the quantity
2 which is of order
(7x));
ifT t2 > 1,
7k
1- 2
7k
if t4 < 1.
T
th
22

---

Therefore
(d + m²) 1
dyR
13
(1
k=0
= Σ 1<T-4<77
(d m3nh du
E 6<T-4-51
(d + mē)7
dy
(T tx
(T x2
Noticing that x +> x² and I H x² are both convex functions on the domain I E oc). Since LieT-1s5 <T 7/6 7 = T - is fixed, according to Jensen's 's inequality, LisT -4- 74 and Σ -i<g-r<7 7 reach their minimum when "/o are constant-valued for all such that T - ts > 1. Similarly, let 3e In - E (0, 20). Then Ta_ = 1 - and Es<T-t,<t 3x lu(1/6) is fixed. Since x + (1 E and x ++ (1 e) are both convex functions on the domain x E (0, oo), according o
reach their minimum when Be the Jensen's inequality, Eeet- (7-44)2 and EEsT- (T-A))3 constant- valued for all & such that T tu
Comparison to convergence results in denoising diffusion models. (9) in Theorem bounds the error of DDMC by I, II, III, which reflect the initialization error, the discretization error and the score estimation error, respectively. Assuming the score estimation error is small, (9) reduces to the same type of results that study the error bound for the denoising diffusion models (Algorithm 1). In [5], the discretization error is proved to be of order (dd) assuming the score function is smooth along the trajectory and constant step-size. In [4], they get rid of the trajectory smoothness assumption and prove a (d²) discretization error bound with early-stopping. In [3], the discretization error bound is improved to (dd) with early-stopping and exponential-decae step-size, and without the trajectory smoothness assumption. Compared to these works, our result in Theorem I also implies a (dd discretization error without the trajectory smoothness assumption and it applies any choice of step-size with early stopping, as we discussed above. As shown in [3], the ((d) is the optimal for the discretization error. Therefore, our results indicates that with early-stopping, the denoising diffusion model achieves the optimal linear dimension dependent error bound.
C.6 Proofs of Section 3.3
To prove the query complexity of ZOD-MC, we first look query complexity of Algorithm 3.
Query complexity of Algorithm 3. The query complexity of Algorithm 3 essentially the number of proposals we need so that n(t) of them can be accepted. Intuitively, to get one sample accepted, the number of proposals we need geometrically distributed with certain acceptance probability [9]. We state this formally in the following proposition, for which it suffices to assume relaxation of the commonly used gradient- Lipschitz condition on the potential.
Proposition C.3. Under Assumption 3.2, the expected number of proposals for obtaining n(()) many exact samples from Pojel (-zr) defined in Lemma via Algorithm is
1 Lx" N(t) n(t) (I(62t $ exp L(e" ()))
Our complexity bound in Proposition C.3 exponentially depends on the dimension. This is due the curse of dimensionality phenomenon in the rejection sampling: the acceptance rate and algorithm efficiency decreases significantly when the dimension increases.
Remark 5.
Proof of Proposition C.3. For each t E [0, T). the expected number of iterations in the rejection
sampling to get one accepted sample
(1pz (OiHH(((NNNN;ee (6 -111aad))
-
(t)
< (Jee exp (-
L ||= x-1- 1²1 )W (622-1)Ta))
( 1 -
(L(e2t - 1)) 1)) exp
To get nt) many samples, the expected number of iterations we need is N(t (t).
23

---

Query complexity of ZOD-MC. The query complexity of ZOD-MC, denoted as N, is essentially the sum of query complexities in Proposition C.3 over the discretized time points, i.c. N En N(T lz).
2 EW2 ))), follows from Proposition C.I that Proof of Corollary 3.1. First, for = (min d (2(p, P6) I EW.
Next, under the exponential-decay step size, according Theorem 1, if we set n(T tx) 7i e 2(T then
KL(ps (oN) S (d + m²)e" -27
(d+m3) N² (T In())) N (T In(
In( (
+ max( (d+ à (r+1n(6-))))
a(T+In(6 and x
By choosing T = 2
N
CXL
CKL
O T+ 2) we have KL(pó qEN) S EKL. Last, it follows from Proposition C.3 that
N
Ñ
N-
(L(E21T-UN- + 1) $ exp 2
Lx -x-- ---=>=__ 1i ( w )
k=0
By plugging 6, T, t and N. (10) is proved.
C.7 Side Lemmas
Lemma 2. Let (XiJoseST be the solution to (2). Then for any 0 S A: S N 1, we have
te+1
In
Vnnpr-t (x
dr + - -))
(1 tw] 2x) [Irrce(ET--s (XT-22)) E [rrace (rraceEE--sae (XT-
where (o))ser is defined in Proposition C.2.
Proof of Lemma 2. For fixed s, consider the process (V In (X.) JoSIST, denoted as (LroseeT, and a function E,, == E[| L, I_,l is shown by Itô's formula in [3, Lemma 3] that
dL, Ledt + 2 (Xx)).(X))
(32)
and as result, (32) implies that
dE,,: = -2,,, 2E (L, Lg, L.) dt + 2E 2 In (X)))l
(33)
Apply (32) and Itô's formula again, we have
dE [E,,,, L.)] -E (L,, Lot
Lo)) (1-s) ((->))((
Therefore (33) can be rewritten as
Fg, = FF,e + 2(1 ((-ss-((-s) [1]] + 2E Inpp- (n
(34)
dt
Let {X,)osesT be the solution of (1). Since X, Xy ; in distribution for all t jo, T). E [1.11²]
and E [[|[V"In p (xx))
can both be represented by the covariance matrix defined in Proposition C.2. It is proved in [3, Lemma 6] that
E || LA 1 = E [
In (X.))l
e 2(T
E trace (Xr-,(Xr-)))
(35)
1
e
-8)
(1- 11-
24

---

and
d
2((-() 1)
B v2 Inpr
(1 e 2
2(1 - e 2(T
e-2(1 1)
2e -(T--)
E. trace Er (Xr-
(36)
E 2(T 22)
Now we choose 8 = in (34) and integrate from la to t. According to (35) and (36), we have
( 1 1-e-2(-- (1- w1
-² e
2"
21
2
(1 e 6-2((-(w))3 (race (ET (XT- (" c
e 22((--4))
6 222(7-0)+21
2(1 - - dE trace Er (r--)))]
22T
2
El E(tracef
(1 e (-2(T-W)3
d
e + 2t - 2
2¹ 2
2
e 2(T-(()
c 2(T 12) ( c (-2(T=1))
((T-4))
t (X &T 1)1 (0 + t 2e 21" [trace -r
(1 e- 21)33
(2
c -242-1)+2
(1 - ---2(T- B (rrace(Er (Tr (Xr (x
(1 e1-e 2((- trace ((rrac((on-(XTT-)) Brrannnep
L (1- 2 w) trace (Xr-
2 u
where the last identity follows from integration by parts. According to Proposition C.2, t H E trace (Xr- is positive and decreasing. Therefore, we have for all / E [4x,
1 +ee
(((--)))) 2((-1())
2c (c-tk)
1-e-2(t-(r) (x)
E I
(1 (1- - 2(T()))))
e 2(T
2
(() (2e (1-(4)) 1) E trace (EI- (Xr-
(1 0-2(T-1933 + 1/¹ c -21( 2(1 du E |race Er (Xx-<i)))))))
2e -((T-1)
(1 - e 2(1-
Integrate again from t to 1,+1, we get
1441
dx
2d
2(T--)
$
(1 6 2(T t2) +
c 2(T 11)-2 (2 -70 (1
(
2(T-
c ((T-
(1 - -e--2 2
(37x
2
| |racee (2r -ne (Xr (Xr-
3dy2
2e -2T -1x
+
nT [Trrcce(Err-a (Xr B fracece Er (Xr-
c 2(T 43)
2( 2))
25

---

ZOD-MC
RDMC
10a
RSDMC
slips
ais
smc
104
langevin
proximal
paraile!
10-1
0
2000
4000
6000
8000
10000
Gradient Complexity
Figure 7: Wall clock of different methods function of oracle complexity for the 2D GMM in the main paper
D More Experiments
D.1 Samples from 2D GMM different Oracle Complexities
We sample from Gaussian Mixture model with 4 modes, the following summarizes the parameters of the GMM.
Weights, w. [0.1
0.2
0.3
0.4].
0
9
11
Means, pA
0
[1
[9]
[
0.57
0.3
-0.2
1
0.3
1.2
-1
Covariances. Σạ
0.5 1
--2.2
0.2
0.3
0.3
-1
1.2
We display the generated samples at different oracle complexities in Figures 8, 9, 10. Notice that the mode located the origin holds less weight, and as the oracle complexity increases our method becomes better at sampling from other modes, as opposed to the corresponding baselines.
We detail the hyperparametens in Table 2 and the wall clock time of different methods in Figure 15.
Method
T
8
Step Size
N-MCMC
Num Steps
N- N-Chains
ZOD-MC
2
25
5e-3
K
RDMC
2
25
5e-2
0.01
1000
K/1000
RSDMC
2
25
5e-2
0.01
K1/1
K1/1
SLIPS
6.62e-3
Adaptive
1000
K/1000
AIS
Adaptive
M
512
SMC
Adaptive
M
512
Langevin
0.01
M
Proximal
1/5
M
Parallel
0.01
M
512
Table Hyperparameters for Various Methods for the 2D GMM experiment. K means the current
oracle complexity and M refers to a matched oracle complexity. For RSDMC we used recursions
per score evaluation.
26

---

(a) Generated samples at 200 oracle complexity per score evaluation
Graend
roa
(b) Generated samples at 1200 oracle complexity per score evaluation
Generated samples 2200 oracle complexity per score evaluation
Figure 8: Generated Samples for GMM at different oracle complexity
(a) Generated samples 3200 oracle complexity per score evaluation
Generated samples 4200 oracle complexity per evaluation
echer
(c) Generated samples at 5200 oracle complexity score evaluation
Crmend
roc
proweal
(d) Generated samples at 6200 oracle complexity per score evaluation
Figure 9: Generated Samples for GMM different oracle complexity
27

---

Generated samples 7200 oracle complexity per evaluation
soner
(b) Generated samples at 8200 oracle complexity score evaluation
Crand
rar
(c) Generated samples at 9200 oracle complexity per score evaluation
Figure 10: Generated Samples for GMM different oracle complexity
28

---

D.2 Samples from Discontinuous 2D GMM at different Oracle Complexities
We display the generated samples at different oracle complexities in Figures 11, ,12, 13. the end we show the W2 and MMD for this example in Figure 14.
We detail the hyperparameters in Table 3.
Method
T
Step Size
N-MCMC
Num Steps
N Chains
ZOD-MC
2
25
5e-3
K
RDMC
2
25
5e-2
0.01
1000
K/1000
RSDMC
2
25
5e-2
0.01
K171
K1/a
SLIPS
1
25
6.62e-3
Adaptive
1000
K/1000
AIS
Adaptive
M
512
SMC
Adaptive
M
512
Langevin
0.01
M
Proximal
1/5
M
Parallel
0.01
M
512
Table 3: Hyperparameters for Various Methods for the 2D Discontinuous GMM experiment. K
means the current oracle complexity and M refers to matched oracle complexity. For RSDMC we used 2 recursions per score evaluation.
(a) Generated samples 200 oracle complexity per score evaluation
baprc
ose
Porze
(b) Generated samples at 1200 oracle complexity per score evaluation
(c) Generated samples 2200 oracle complexity per score evaluation
Figure 11: Generated Samples for discontinuous GMM at different oracle complexity
29

---

Generated samples 3200 oracle complexity per evaluation
Boboaa (b) Generated samples at 4200 oracle complexity score evaluation
soper
Grann
rac
neter
(c) Generated samples at 5200 oracle complexity per score evaluation
e
Generated samples 6200 oracle complexity per score evaluation
Figure 12: Generated Samples for discontinuous GMM at different oracle complexity
(a) Generated samples 7200 oracle complexity score evaluation
Graed EXT
201
wase
(b) Generated samples at 8200 oracle complexity per score evaluation
(c) Generated samples 9200 oracle complexity per score evaluation
Figure 13: Generated Samples for discontinuous GMM at different oracle complexity
30

---

ZOD-MC
RDMC
12
RDMC
RSDMC
RSDMC
silps
MMO
ais
10
ais
langevin proximal parailel
langevin proximal
parallel
Oracle Complexity
Oracle Complexity
Figure 14: W2 and MMD at different oracle complexities for discontinuous potential
ZOD-MC
RDMC
RSDMC
slips
ais
104
langevin
Time
proximal
paralle!
10a
10-1
0
2000
4000
6000
8000
10000
Gradient Complexity
Figure 15: Wall clock of different methods as function of oracle complexity
D.3 Samples from different radius
We display the generated samples at different radius in Figures 16, 18 and the hyperparameters in Table
Method
T
N
8
Step Size
N-MCMC
Num Steps
N-Chains
ZOD-MC
10
50
5e-3
K
RDMC
2
50
5e-2
0.01
1000
K/1000
RSDMC
2
50
5c-2
0.01
KT/4
K1/4
SLIPS
1
50
6.62e-3
Adaptive
1000
K/ 1000
AIS
Adaptive
512
SMC
Adaptive
512
Langevin
0.01
M
Proximal
1/40
M
Parallel
0.01
M
512
Table 4: Hyperparameters for Various Methods for the 2D GMM experiment. K means the current oracle complexity and refers to a matched oracle complexity.
31

---

Generated samples
Vitec
(b) Generated samples at R 6
Figure 16: Generated samples at different radius
(a) Generated samples at R 11
(b) Generated samples at R = 16
(c) Generated samples 21
Figure 17: Generated samples at different radius
(a) Generated samples at I 26
Figure 18: Generated samples at different radius
D.4 Higher Dimensional Examples
Score Error Approximation Details. We use the following 5d Gaussian mixture to measure the error of the score approximation:
Coefficients, w [0.25
0.5
0.25]
- 47
44
4
Mcans, p4
3
4
-4
-4
-4
[
--
3
2
0
0
0
9 0
7
0
0
1
0.4
0
0
07
2
3
0.4
0
Variances, ΣΦ
0
0
4
2
0
0
0
0
4
3
0
0
0.4
0
3
4
0
0
0
0
0
0
1
0
0
0
0
1
32

---

Randomized Gaussian Mixtures To generate the results in Figure 1b we proceed as follows. For given dimension take:
12 |=|||
Where U|0, 1]3 additionally we sample o² U U1.3, 1.3). We then consider the Gaussian target N (H, I). We repeat this 5 times and create a Gaussian mixture with equally weighted modes. We plot the the 2d marginals of the target distribution as long as the generated samples.
D.5 Muller Brown Potential Details
The potential given by V(z,g) = (V, V,(,,)))
(2, v) - 170 exp ( 6.5(z + 0.5)* + 11(x 0.5) 6.56g 1.5)*)
100 exp ( - x² 100y 10:00yy0.33 0.5))) 15exp (0.7(x 0.6(2 + 1) 1) + 0.7(y - 1)²)
200 exp ( (- 1 11))
where VA corresponds to the original Müller Brown and (T, y) = 35.0133(x==2))+533 y²)² with (x2, y²) is approximately the minimizer at the center of the middle potential well, and V, a correction introduced that the depths of all three wells are.
D.6 Score error at ( = T
One natural concern is that the sampling problem T could be nearly hard sampling from the target distribution. Therefore, only a small number of samples could be accepted and the score error would be high. We display the score error at T show that this is not necessarily the case.
ZOD-IC
20C-MC
Oradk Compledy
(a) Score error at f = T = 4. for different diffusion samplers, used sz 1 for SLIPS. Results are for the 5d GMM in the main paper
(b) Score error at t T = 4. for different diffusion samplers, we used zs 1 for SLIPS. Results for
the 2d GMM in the main paper
Figure 19: Score error at f = T for different target distributions
D.7 Further details number of accepted samples
We present the number of accepted samples from our rejection sampler as a function of time. Specifically consider 1000 trajectories of the diffusion and for every intermediate step we sample 10K samples. We present the number of accepted samples in Table 5.
to
5.00
4.28
3.56
2.84
2.13
1.41
0.69
0.30
0.13
0.01
GMM
1.58
1.39
3.70
14.03
48.27
129.05
308.23
786.74
1299.30
2251.65 3129.97
Mueller
1.01
1.20
2.62
9.79
37.25
145.42
447.96
945.72
1598.99
Table 5: Comparison of GMM and Mueller values across different t values
33

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section 1, Table 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 3.3, Remark 5 and the discussion after
34

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Main results: Proposition 3.1, Theorem Corollary 3.1. Proofs included in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Code is provided with instructions to run it. Scripts provided so that one line script can reproduce all the plots found in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
35

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is provided with instructions to run Scripts are provided so that one line script can reproduce all the plots found in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /ttpsscccppbbpcc////eeccppcpppcp hwwbbliccguiieee guwdee/ /CodeSubmis ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
36

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Yes, the target distributions are well described, furthermore every hyperpa- rameter can be easily checked in the configuration files the corresponding script for each experiment.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Figure 4b we present the standard deviation of the errors in the score approximation. In other experiments we didn't find it insightful to add these statistics.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we give this information at the beginning of section
Guidelines:
The answer NA means that the paper does not include experiments.
37

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //terrip////is..../// cc cc/public//eeeee c
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://eeurrrr..coeo httpp/ppp....ppp.....ccccccceaad
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper studies the fundamental theory of sampling, with no specified applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
38

---

Answer: [NA]
Justification:
Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We didn't 't use any dataset or asset from another party during these experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
39

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "OlYyT9v3SO", "reviewer": "Reviewer_9Wcn", "summary": "This paper considers the problem of sampling from an unnormalized density by combining techniques developed from score-based generative modeling and non-log-concave sampling. Specifically, based on the Reverse Diffusion Monte Carlo (RDMC) framework proposed in [1], which is a meta-algorithm based on an oracle that estimates score function at any time, the authors proposed one way to implement such oracle via techniques developed for sampling non-log-concave distributions (Alternating Sampling Framework, where the Restricted Gaussian Oracle is implemented via Rejection Sampling) and arrived at an implementable and derivative-free version of RDMC.", "questions": "The reviewer's main concern is that when using rejection sampling to implement the Restricted Gaussian Oracle (RGO) in the Alternating Sampling Framework (ASF), one can only obtain the expected number of executions for rejection sampling (Proposition B.3). Therefore, it might be fair to compare the expected time complexity of this sampler with the exact time complexity of other samplers listed in Table 1?", "limitations": "It seems to be the reviewer that the name \"Diffusion Monte Carlo\" and its abbreviation \"DMC\" are not good choices for naming the sampling methodology here. They happen to coincide with the one of the quantum monte carlo methods developed in computational quantum physics. Maybe one possible way to resolve such issue is to use the name \"Diffusion-Based Monte Carlo (DBMC)\" or the name \"Score-Based Monte Carlo (SBMC)\" instead. \n\nReferences:\n\n[1] Huang, X., Dong, H., Yifan, H. A. O., Ma, Y., & Zhang, T. (2023, October). Reverse diffusion monte carlo. In The Twelfth International Conference on Learning Representations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a technically solid paper with rigorous proof. Also, a complete set of numerical experiments are included to justify the main claims. Furthermore, this paper is the first work turning RDMC into an implementable sampler, which might be useful for sampling real-world distributions. Moreover, for the theory part of this paper, no strong assumption like log-concavity or isoperimetric inequality are made in the proof.", "weaknesses": "1. One possible drawback of the proposed sampler, just as the authors stated in the paper, is that its iteration complexity depends linearly on the data dimension $d$. Hence, it will probably be appealing only for low-dimensional distributions. Therefore, it might be meaningful to do a numerical investigation to see how the sampler proposed in this paper behaves on high dimensional distributions. \n2. For the sake of completeness, it might be necessary for the authors to include a section of related work on derivative-free methods for optimization and sampling from unnormalized densities. Some classical examples include the Ensemble Kalman Filter (EnKF) and Ensemble Kalman Inversion (EKI).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation. \n\n> One possible drawback of the proposed sampler, just as the authors stated in the paper, is that its iteration complexity depends linearly on the data dimension. Hence, it will probably be appealing only for low-dimensional distributions. Therefore, it might be meaningful to do a numerical investigation to see how the sampler proposed in this paper behaves on high dimensional distributions.\n\nWe thank the reviewer for this suggestion. In Figure 1b of the main paper, numerically we've shown that the sample quality of ZOD-MC decreases a little as the dimension increases from 1 to 7. But ZOD-MC still generates relative high-quality samples and outperforms RDMC and RSDMC at a fixed number of function evaluations. \n\n>For the sake of completeness, it might be necessary for the authors to include a section of related work on derivative-free methods for optimization and sampling from unnormalized densities. Some classical examples include the Ensemble Kalman Filter (EnKF) and Ensemble Kalman Inversion (EKI).\n\nThanks for the suggestion. The Ensemble Kalman Filter (EnKF), Ensemble Kalman Inversion (EKI) and the Ensemble Kalman Sampler (EKS) are all derivative-free sampling algorithms that are based on moving a set of easy-to-sample particle according to certain dynamics. However, these methods seem to be mainly for data assimilation / Bayesian posterior sampling, which require (noisy) observations from the target distributions. That is different from our setting: sampling using queries on the target potential functions only. That's why we did not compare to them.\n\nHowever, we will add a discussion on these important related algorithms.\n\n\n>The reviewer's main concern is that when using rejection sampling to implement the Restricted Gaussian Oracle (RGO) in the Alternating Sampling Framework (ASF), one can only obtain the expected number of executions for rejection sampling (Proposition B.3). Therefore, it might be fair to compare the expected time complexity of this sampler with the exact time complexity of other samplers listed in Table 1?\n\nWe appreciate the question on the comparison in Table 1. We used zeroth-order oracle complexities in expectation for ZOD-MC in Table 1. We believe the comparison is fair due to the following two reasons:\n\n(1) lots of tasks, such as volume computing and Bayesian inference, require a large number of samples from the target distribution. Hence, we need to run the sampling algorithm many times. As the number of algorithm running gets large, the total oracle complexity will be approximately the total expected oracle complexity. From these perspective, the comparison in table 1 is fair. Similar comparison has been made in [1] to compare the complexity of the proximal sampler to the complexities of LMC and MALA.\n\n(2) it is worth mentioning the complexities of RDMC and RSDMC are not exact either. The complexties in RDMC (Theorem 1) and RSDMC (Theorem 4.1) are proved only to ensure an $\\varepsilon$-accurate sample with high probability, which means the complexities to obtain an $\\varepsilon$-accurate sample almost surely for RDMC and RSDMC should be larger than the corresponding complexities presented in table 1.\n\n[1] Chen, Yongxin, et al. \"Improved analysis for a proximal algorithm for sampling.\" Conference on Learning Theory. PMLR, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "571PpeL8gv", "reviewer": "Reviewer_8qyg", "summary": "This paper proposes a novel zero-order sampling algorithm (ZOD-MC) when the target distribution is beyond the log-concavity and even isoperimetry. Different from first-order diffusion-based Monte Carlo proposed previously, this paper only requires the zero-order information. Besides, this paper shows the good performance of ZOD-MC from both theoretical and practical perspectives.\nThis paper's key step is to introduce rejection sampling to implement the score estimation in a reverse OU process. Specifically, the authors note that the envelope for the rejection sampling is a Gaussian-type distribution when the minimum negative log density of the target distribution is given as $V_*$.", "questions": "- In Corollary 3.1, we can find the zeroth-order query complexity will depend on $\\epsilon_{\\mathrm{KL}}^{-d}$. But I would be curious to know if we can achieve a complexity whose order of $\\epsilon$ is independent with $d$?   What are the barriers to obtaining this complexity?", "limitations": "This is a theoretical paper. It can hardly find potential negative societal impact in their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is the first diffusion-based Monte Carlo method which only requires the bounded second moment and a relaxation of the commonly used gradient-Lipschitz condition. Such assumptions are even much weaker than the first-order diffusion-based Monte Carlo, e.g., RDMC and RSDMC.\n- Although zeroth-order sampling methods cannot circumvent the curse of dimensionality, this paper gets rid of the exponential dependence on error tolerance, i.e., $\\epsilon$. Combined with nearly no smoothness requirements in this paper, such complexity is acceptable.\n- This paper greatly simplifies the proof techniques used to estimate upper-bound score estimation errors, making them easy for readers to follow. Specifically, previous work introduces complicated concentration properties to provide the error bound. While this paper replace it with some monotonicity (Proposition B.2) used in stochastic localization.", "weaknesses": "- Some related work is missed in the authors’ survey, e.g., [1]. Theorem 7 of [1] provides a similar zeroth-order complexity ($\\exp(O(d)\\log \\epsilon^{-1})$) for achieving a minimal optimal error. I suggest the authors compare the theoretical results with [1].\n- The implementation of Algorithm 3 requires the minimum of $V$, which is denoted as $V_*$. How do we obtain this minimum? Since the function $V$ is highly irregular, calculating the minimum may also be difficult.\n- Although the experiments seem to be comprehensive, some details are not reported. For example, what is the meaning of oracle complexity? Does it include only zeroth-order oracle, first-order oracle, or both? If only counting the first-order oracle, is the comparison fair to first-order methods? What results are if the x-axis is set as the wall clock time? What are the hyper-parameters of ZOD-MC and baselines, and how do we choose these hyper-parameters? I hope these details will be included in the appendix.\n\n[1] Convergence Rates for Non-log-concave Sampling and Log-partition Estimation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments.\n> Some related work is missed in the authors’ survey, e.g., [1]. Theorem 7 of [1] provides a similar zeroth-order complexity O(exp(d)log(1/\\varepsilon)) for achieving a minimal optimal error. I suggest the authors compare the theoretical results with [1].\n\nThanks for mentioning this very interesting work. It is related to the zeroth-order sampling problem that we considered, and we will add the following discussion in our updated manuscript:\n\n[1] provides upper bounds on convergence rates for a zeroth-order sampling algorithm that combines an approximation technique and rejection sampling. We compare their results to ours from the following two perspectives:\n\n1) target distributions: the target distributions in [1] are restricted to have compact support and to be m-differentiable ($m>0$). Our considered target distributions are more general. For example, they can have full support and they can even have discontinuities as shown in our Section 4 Figure 5.  \n\n2) complexity bounds: we can compare our derived complexity upper bound to the results in [1] for target distributions in the restricted class considered in [1]. By using the fact that KL is smaller than $R_\\infty$, theorem 12 in [1] can be written as an upper bound on the complexity to reach $\\varepsilon$-accuracy in $R_\\infty$: the complexity is of order $\\Omega_{d}(\\varepsilon^{-d/m})$. The $d$-dependency is implicit, therefore we only compare the $\\varepsilon$-dependency. The $\\varepsilon$-dependency in both complexities is polynomial in $\\varepsilon$, with a linear d factor in the exponent. Since we consider a general class of targets, our result doesn't reflect the smoothness of the potential as their result does. Within the restricted class, if the target is differentiable up to an order greater than 2, their result is better than ours (in terms of $\\varepsilon$-dependency). Otherwise, our result is better.\n\n> The implementation of Algorithm 3 requires the minimum of $V$, which is denoted as $V_*$. How do we obtain this minimum? Since the function is highly irregular, calculating the minimum may also be difficult.\n\nThis is an oracle that ZOD-MC relies on. What we need can be relaxed to a global lower bound of $V$. Nevertheless, we agree this oracle can still be challenging to implement. Our practical implementation was mentioned in Remark 1, where we get an approximation using Newton's method (although other methods like Gradient Descent or the proximal bundle can also provide good approximations). As the sampling process explores the space more, the estimated minimum is updated as necessary. \n\n\n> Although the experiments seem to be comprehensive, some details are not reported. For example, what is the meaning of oracle complexity? Does it include only zeroth-order oracle, first-order oracle, or both? If only counting the first-order oracle, is the comparison fair to first-order methods? What results are if the x-axis is set as the wall clock time? What are the hyper-parameters of ZOD-MC and baselines, and how do we choose these hyper-parameters? I hope these details will be included in the appendix.\n\nThanks for a great question. Our claim is at least fair and in fact an understatement -- As mentioned in line 274 we count the total number of first and zeroth-order queries. We count each of them as being the same. This actually puts our method at a disadvantage since evaluating first-order queries is more expensive than zeroth-order queries. Despite this, we still see improved counts. The only exception to this is in the dimension experiment (Figure 1b in the main paper) where we matched number of function evaluations. For instance, a first-order query requires $d$ evaluations. We include a figure displaying the clock time as a function of the oracle complexity under the same set up as that of Figure 1a in the main paper. As introduced at the beginning of Section 4, the baselines we considered includes RDMC, RSDMC, Proximal sampler, Parallel Tempering and unadjusted Langevin Monte Carlo. The hyperparameters N,T and the step-size are analytically explored and we chose them according to Corollary 3.1. We will highlight these information in the updated manuscripts.\n\n>In Corollary 3.1, we can find the zeroth-order query complexity will depend on $\\varepsilon_{\\text{KL}}^{-d}$. But I would be curious to know if we can achieve a complexity whose order of $\\varepsilon$ is independent with $d$? What are the barriers to obtaining this complexity?\n\nThe exponent $d$ in the $\\varepsilon$-dependency is due to the curse of dimensionality in the rejection sampler: when we use the current version of rejection sampler to sampler $p_{0|t}$, we are only able to prove that the expected number of rejections is of order $O(\\exp(2dt))$. Since the largest $t$ in the denoising process is of order $\\log(d/\\varepsilon_{\\text{KL}})$, we end up with the $\\varepsilon_{\\text{KL}}^{-d}$ complexity. To improve the $\\varepsilon$-dependency requires a finer design of the rejection sampler with higher acceptance rate. We believe this is an interesting future work, and theoretically it could be done by considering non-logconcave targets with special structures.\n\nAll these scientific discussions are helpful and greatly appreciated. At this moment our method's strength still lies in being agnostic to multimodality in low (e.g., $\\lesssim$ 10) dimensions.\n    \n[1]: Holzmüller, David, and Francis Bach. \"Convergence rates for non-log-concave sampling and log-partition estimation.\" arXiv preprint arXiv:2303.03237 (2023).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ytNEZkkkL", "reviewer": "Reviewer_Q2x6", "summary": "In this paper, the authors are interested in the problem of sampling from an arbitrary non-logconcave probability distribution (namely, multi-modal distribution) with only access to its unnormalized density. While most of popular sampling methods rely on queries of the score of the target, i.e. the gradient of the log-density (1st-order methods), the proposed approach is a 0th-order sampling method, as it relies on queries of the unnormalized target density itself. Inspired by the performance of denoising diffusion models for generative tasks, they propose a sampling algorithm, Zeroth-Order Diffusion Monte Carlo (ZOD-MC), which simulates a discretized and approximate version of the time-reversal of the standard Ornstein-Uhlenbeck diffusion process (the ideal scheme being known to converge to the target). In this algorithm, rejection-sampling is used to provide a Monte Carlo estimate of the intractable scores of the process marginals that appear in the recursion. This is made possible by the Tweedie's formula, that links the score of the marginals to an expectation over the posteriors of the model. As rejection sampling is known to suffer from the curse of dimensionality, the authors acknowledge that ZOD-MC cannot address sampling problems with relatively high dimensions ($d\\geq10$). To support their algorithm, they provide a convergence analysis which requires a weak assumption on the target (bounded second order moment) and a control of the Monte Carlo estimation error for the posterior distributions at any time of the process. Under an extra-assumption on this control, they derive a readable oracle complexity of ZOD-MC that quantifies the number of queries of the target density in the whole sampling procedure. Finally, they conduct numerical experiments on low dimensional settings (mostly $d=2$), by considering multi-modal distributions which increasing higher energy barriers or with discontinuous potential. They compare ZOD-MC to recent approaches based on denoising approaches [1,2] and standard MCMC approaches such as Langevin or parallel tempering. In the considered settings, ZOD-MC exhibits the best performance at equivalent computational budget (namely, same oracle complexity)\n\n[1] Reverse Diffusion Monte Carlo. Huang et al. 2023.\n\n[2] Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo. Huang et al. 2024", "questions": "- I have a question about Algorithm 1: to obtain the sampling recursion with the MC estimator, you first discretize the SDE with exponential integration and then replace the score by its MC estimator. Would it bring less discretization error to first replace the score in the SDE by the term involving the conditional expectation and then apply exponential integration upon it ? It seems to me that exponential integration would still be tractable in this case. \n- To support my claim 2 in the 'Weaknesses' section, could the authors provide (i) the value of the average score error between the true score and the approximated score near $t=T$, while varying the number of queries to the target distribution (ie oracle complexity per score evaluation)  and (ii) results of rejection sampling directly applied on the target distribution with same oracle complexity as other methods ?", "limitations": "The main (and crucial) limitation of ZOD-MC is the fact that it can only be applied to small dimensional settings ($d\\leq 5$), as rejection sampling is notoriously known to suffer from the curse of dimensionality (which is the reason why it is not a popular sampling method in practice). Although the authors acknowledge this limitation in the abstract, it is not well highlighted at all in the main of the paper: this limitation appears explicitly in Remark 5 in Section 3.3 in the Appendix, but not in the main paper. As suggested by NeurIPS guidelines, a section/paragraph 'Limitations' should be given in the main.\n\nOn the other hand, ZOD-MC requires to know the location of local minima of the energy landscape, i.e., the location of the modes of the target distribution. As indicated by the authors, this can be done by applying Newton's method on the target potential (see Remark 1) before or while sampling; however, this is a 2nd-order method, which violates the framework chosen by the authors (0-th order method). Although it is a common assumption to have access to the location of the modes in realistic settings (which turns out to be another challenge of sampling procedures), this requirement should be much more highlighted. Otherwise the title of the paper is misleading.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The paper is didactic in the sense that the motivations and the bricks to build the algorithm ZOD-MC are exposed in a logical way.\n- The authors pay attention to bring intuition on their theoretical results.\n- The mathematical results are clear to understand, especially Theorem 1.\n- Although the numerical experiments are conducted on low dimensional settings, they consider interesting cases, i.e., sampling from multi-modal distributions where the modes are increasingly further from each other and Gibbs distributions with discontinuous potential.", "weaknesses": "In my opinion, this paper suffers from 3 main weaknesses, which explains my score.\n\n1. The comparison to the related work is incomplete. The authors do not cite the work [1] (although it was published approximately at the same time as [2]), where the authors propose a 1st-order sampling method, SLIPS, based on stochastic localization, that can be linked to a denoising diffusion model. In SLIPS, samples from the target distribution are obtained by following a diffusion process with intractable drift, which is nothing less than an expectation of a posterior distribution; in practice, the authors estimate this term by MCMC method (Langevin). In contrast to RDMC or ZOD-MC, SLIPS may exhibit multiple advantages:  (i) it can be applied to a flexible class of stochastic localization schemes, whereas RDMC and ZOD-MC only consider the standard Ornstein-Uhlenbeck diffusion process, (ii) it provides an exact finite-time setting for sampling (which is not the case for RDMC or ZOD-MC),  (iii) it is shown to scale well in dimension in their experiments (up to dimension 100), (iv) it has a small oracle complexity per score evaluation compared to the numerics presented here (32 vs 200 at least in the numerics of the current paper). Since the current approach has the same spirit as SLIPS (diffusion-based approach with MC estimation), it should be compared with it. Moreover, no numerical comparison with AIS or SMC (which are considered gold-standard to sample from low-dimensional multi-modal distributions) is provided. For me, this justifies why this paper does not meet the standards of NeurIPS. \n\n2. In my opinion, the proposed approach misses a fundamental point, which lies in the MC estimation of the denoiser (i.e. the conditional expectation over the posterior distribution): it is linked to the ability to be able to provide an accurate MC estimate near at $t_0=0$, equivalently $t=T$, namely when $p_t$ is fully noised. When $t\\approx T$, it is clear that the corresponding posterior distribution is approximately equal to the target distribution itself (since we have full noise, the quadratic term vanishes). Therefore, applying rejection sampling on the posterior distribution at the very beginning of the sampling process in ZOD-MC is equivalent to do rejection sampling on the target distribution itself ! Hence, in practice, **the whole diffusion-based approach presented in ZOD-MC to sample from the target distribution via an annealing scheme is actually as hard as directly sampling from the target distribution**, which hurts its usefulness. This remark is intimately linked to the notion of duality of log-concavity presented in [1], which explains that it is required to start the diffusion process further such that the posterior distribution is \"smoother\", and easier to sample from. On the theoretical side, I have a concerns that is linked to my point:  it seems to me that the authors make an assumption on the MC error $\\delta(t)$ to estimate the denoiser  (which is not explicited in the main) in order to derive the total complexity cost (hidden in Section B.5 in the appendix); as said above, this control is actually crucial in practice and it is not straightforward to verify an upper bound on it.\n\n3. The section on numerical experiments is incomplete for several reasons: no indication of tuning of the hyperparameters ($T$, $N$, step-size) either for ZOD-MC or other approaches, no ablation study on these hyperparameters to exhibit robustness, display of the estimation error of the true score for a large $t$ (where it becomes harder) and a variety of levels of oracle complexity, the plots in Figure 1 and Figure 4.a do not display any variance, missing related work as stated in my claim 1.\n\n[1] Stochastic Localization via Iterative Posterior sampling. Grenioux et al. 2024\n\n[2] Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo. Huang et al. 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments. \n\n> The comparison to the related work is incomplete. The authors do not cite the work [1] (although it was published approximately at the same time as [2]), where the authors propose a 1st-order sampling method, SLIPS, based on stochastic localization, that can be linked to a denoising diffusion model. In SLIPS, samples from the target distribution are obtained by following a diffusion process with intractable drift, which is nothing less than an expectation of a posterior distribution; in practice, the authors estimate this term by MCMC method (Langevin). In contrast to RDMC or ZOD-MC, SLIPS may exhibit multiple advantages: (i) it can be applied to a flexible class of stochastic localization schemes, whereas RDMC and ZOD-MC only consider the standard Ornstein-Uhlenbeck diffusion process, (ii) it provides an exact finite-time setting for sampling (which is not the case for RDMC or ZOD-MC), (iii) it is shown to scale well in dimension in their experiments (up to dimension 100), (iv) it has a small oracle complexity per score evaluation compared to the numerics presented here (32 vs 200 at least in the numerics of the current paper). Since the current approach has the same spirit as SLIPS (diffusion-based approach with MC estimation), it should be compared with it. Moreover, no numerical comparison with AIS or SMC (which are considered gold-standard to sample from low-dimensional multi-modal distributions) is provided. For me, this justifies why this paper does not meet the standards of NeurIPS.\n\nWe apologize for not having cited the very related work [1]. We were not aware of it at the time our manuscript was submitted.\n\nSimilar to ZOD-MC, SLIPS is also based on the denoising diffusion model and an MCMC score estimation. We have added a comparison between ZOD-MC and SLIPS in our updated manuscript. While SLIPS is great work, we hope to summarize three **major differences** between ZOD-MC and SLIPS: (1) SLIPS relies on MALA to approximate the score. As a result, to analytically establish convergence of SLIPS requires **log-concavity outside a ball assumption** due to the difficulty in analyzing MALA. The goal of our paper is to investigate a non-logconcave sampling algorithm **without any convexity-related assumption**. Therefore, we choose to approximate the score via rejection sampler, which can be analyzed under mild smoothness conditions. (2) SLIPS uses MALA to generate initial point: the denoising process is simulated from the middle of the observation process. This adds extra difficulty on initialization: **the initialization error is hard to control numerically and analytically in general**. In contrast, **the initialization error in ZOD-MC can be controlled** by starting at a large time $T$ in the forward process. (3) ZOD-MC can sample from non-differentiable and even **discontinuous** densities.\n\nNumerically, we have updated our experiments to include comparisons with SLIPS, AIS and SMC. We started by running these methods under the same set up as in the experiment in Figure 1. For SLIPS we used the same initialization as used in their code ($\\mathcal{N}(0,5)$ + LMC steps) and initialize AIS and SMC with $\\mathcal{N}(0,5)$. Under this set up we find that all of the methods perform  quite well, despite this ZOD-MC still has the best performance out of all methods. We further demonstrate that our method is less sensitive to the initial condition by initializing the methods with $\\mathcal{N}(0,1)$. We then show that these methods still suffer from metastability and are unable to sample from all modes even at different oracle complexities.\n\n>In my opinion, the proposed approach misses a fundamental point, which lies in the MC estimation of the denoiser (i.e. the conditional expectation over the posterior distribution): it is linked to the ability to be able to provide an accurate MC estimate near at $t_0=0$, equivalently $t=T$, namely when $p_t$ is fully noised. When $t\\approx T$ , it is clear that the corresponding posterior distribution is approximately equal to the target distribution itself (since we have full noise, the quadratic term vanishes). Therefore, applying rejection sampling on the posterior distribution at the very beginning of the sampling process in ZOD-MC is equivalent to do rejection sampling on the target distribution itself! Hence, in practice, **the whole diffusion-based approach presented in ZOD-MC to sample from the target distribution via an annealing scheme is actually as hard as directly sampling from the target distribution**, which hurts its usefulness. This remark is intimately linked to the notion of duality of log-concavity presented in [1], which explains that it is required to start the diffusion process further such that the posterior distribution is \"smoother\", and easier to sample from. On the theoretical side, I have a concerns that is linked to my point: it seems to me that the authors make an assumption on the MC error $\\delta(t)$ to estimate the denoiser (which is not explicited in the main) in order to derive the total complexity cost (hidden in Section B.5 in the appendix); as said above, this control is actually crucial in practice and it is not straightforward to verify an upper bound on it.\n\nApology for a serious misunderstanding of our main results (Proposition 3.1, Theorem 1 and Corollary 3.1), but we're afraid the comment \"the whole diffusion-based approach presented in ZOD-MC to sample from the target distribution via an annealing scheme is actually as hard as directly sampling from the target distribution\" is **not** true. \n\n---\nWe would like to kindly direct the reviewer to \"Comment\" for the response to the rest of the review. We sincerely apologize for exceeding the character limit but we eagerly hope to thoroughly address the reviewer's concerns.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lqpk0PrqNg", "reviewer": "Reviewer_HU9Z", "summary": "The authors investigate a popular reverse-diffusion sampling process, when the scores are estimated not from target samples but using the target's unnormalized density, which is the setup in energy-based modelling. Specifically, the authors consider a recent Monte-Carlo estimator of the scores which requires sampling from a possibly multimodal distribution (product of target and Gaussian densities). To do this, the authors use rejection sampling and obtain an upper bound on the convergence of their method. They also empirically validate their method in low dimensions with thorough experiments that monitor and benchmark against other methods:\n\n- **convergence** in MMD, W2, and generic statistics vs. **cost** in dimension or target queries) in Figure 1 \n- quantifying **mode coverage** in Figure 4\n\nas well as other visual diagnostics of convergence.", "questions": "-", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and the results are interesting. Their experiments are thorough, I appreciate the use of the $W2$ in Fig 1.a. as it is sensitive to mode coverage which is less the case of some other sampling metrics.", "weaknesses": "The authors are clear about the limitations of their method, for example the complexity in Corollary 3.1. is exponential not only in the dimension $d$ but also in the smoothness $L$ of the target (this holds even in one dimension).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>The authors are clear about the limitations of their method, for example the complexity in Corollary 3.1. is exponential not only in the dimension d but also in the smoothness L of the target (this holds even in one dimension).\n\nThat is right. Just to further remark about this fact: For general target distributions as considered in our paper, it was shown in [1] that the diffusion posterior sampling is computationally intractable in the worse case, and that worse case is among the distributions considered in our paper. Therefore, we feel if the theoretical complexity needs to be improved, one possibility is to restrict the target distributions to have more structures, while possibly adapting our algorithm to these structures to get better smoothness/dimension-dependence.\n\n[1] Gupta, Shivam, et al. \"Diffusion posterior sampling is computationally intractable.\" arXiv preprint arXiv:2402.12727 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for the helpful comments. Results of newly added experiments are included in the pdf file.

Meta-review: This paper proposes the framework of Diffusion Monte Carlo (DMC), which combines a discretized denoising process with a Monte Carlo score estimator, and proves its convergence under a weak bounded second moment condition. Subsequently, the paper introduces zeroth-order DMC, which implements the oracle required by the Monte Carlo score estimator using rejection sampling, and analyzes its zeroth-order oracle complexity under a condition slightly weaker than global smoothness. Numerical results demonstrate the competitiveness of the proposed zeroth-order DMC algorithm against existing sampling algorithms. Two limitations of this work are (1) its scalability in higher dimensions, and (2) its need for an optimization oracle that finds a global lower bound of the potential. Both have been clearly pointed out by the authors. 

To rigorously and efficiently implement the optimization oracle mentioned above might require additional assumptions on the target distribution. While it might be challenging to explicitly identify the necessary conditions, a discussion on this aspect would be beneficial.

The paper is well-written and provides both rigorous theory and persuasive experimental results. The proposed algorithm marks the first diffusion-based sampling algorithm that requires only a zeroth-order oracle and weak assumptions on the target distribution. Therefore, I recommend the acceptance of this paper.
Decision: Accept (poster)