Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
Authors: Adrien Vacher
Omar Chehab
Anna Korba
Venue: NeurIPS 2025 poster ()
Keywords: Diffusion
Sampling
Multi-modal
Complexity
Primary area: theory

Abstract: Even in low dimensions, sampling from multi-modal distributions is challenging. We provide the first sampling algorithm for a broad class of distributions --- including all Gaussian mixtures --- with a query complexity that is polynomial in the parameters governing multi-modality, assuming fixed dimension. Our sampling algorithm simulates a time-reversed diffusion process, using a self-normalized Monte Carlo estimator of the intermediate score functions. Unlike previous works, it avoids metastability, requires no prior knowledge of the mode locations, and relaxes the well-known log-smoothness assumption which excluded general Gaussian mixtures so far.

fr Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
Adrien Vacher CREST, ENSAE
Omar Chehab CREST, ENSAE
Institut Polytechnique de Paris adrien. www.eraaessssaeeee. fr
Institut Polytechnique de Paris
omar. www.hhhenssssee....o fr
Anna Korba CREST, ENSAE Institut Polytechnique de Paris anna.
Abstract
Even low dimensions, sampling from multi-modal distributions challenging. We provide the first sampling algorithm for a broad class of distributions - includ- ing all Gaussian mixtures - with query complexity that is polynomial the parameters governing multi-modality assuming fixed dimension. Our sampling algorithm simulates a time-reversed diffusion process, using a self-normal self-normalized Monte Carlo estimator of the intermediate score functions. Unlike previous works, it avoids metastability, requires no prior knowledge of the mode locations, and re- laxes the well-known log-smoothness assumption which excluded general Gaus- sian mixtures so far.
Introduction
Sampling from distribution whose density is only known up to normalization constant is fundamental problem statistics. Formally, given some potential V Rd - such that (e=V(#) dæ oo, the sampling problem consists obtaining a sample from some distribution p such that p c-close to the target μ e with respect to some divergence while maintaining the complexity, i.e., the number of queries to V and possibly to its derivatives, as low as possible. Depending on the shape of the distribution, the typical complexity of existing sampling algorithms can significantly differ.
Log-coneave and "PL-like" distributions As in Euclidean optimization, a common assumption in the sampling literature is to assume that y is log- log-concave and smooth or equivalently, that V convex and smooth. Specifically, when the potential V is assumed be a-strongly convex and to have an L-Lipschitz gradient, the popular Unajusted Langevin Algorithm (ULA) is known to achieve fast convergence [[Durmus and Moulnes. 20TA Dalalyan and Karagulyan, 20 Because strong- log concavity implies uni-modality, thus excluding many distributions of interest, this assumption was further relaxed μ verifying an -----ooSobooo Sobolev inequality, later interpreted as Polyak- Eojasiewicz type condition on KL(-Ip) for the Wasserstein geometry [Blanchet and Bolte, 2018]. Under these conditions, ULA was shown to achieve e-error Kullback-Leible (KL) divergence in Ó - queries to VV |Vempala and Wibisong, 2019) While these polynomial guarantees
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

do go beyond the modal setting, we show in the next paragraph that most existing algorithms still fail sample from truly multi-modal distributions.
Multi-modal distributions Designing sampling algorithms for multi-modal distributions is an active area of research. However, most existing sampling algorithms are limited in at least two of the following ways:
The query complexity is exponential in the parameters the problem. For instance, when the global c-strong convexity of V is relaxed with a-strong convexity outside ball of radius R. the log-Sobolev constant of μ. degrades to O MM 2012 Prop.
2]. In practice, this does not simply translate to poor worst case bounds: practitioners are well aware that when dealing with multi-modal distributions, ULA-based algorithms suffer from metastability, where they get stuck in local modes, leading to slow convergence [Deng at 20201.
2. Guarantees are obtained under a log-smoothness assumption; we show in Sec. 3.2 that even for Gaussian Mixtures, which is arguably the most basic multi-modal model, this assumption may not be verified.
3. Explicit a priori knowledge the target distribution is required for the algorithm to con- verge. For instance, importance sampling requires a proposal distribution whose "effective" support must cover sufficiently well the one of the target; however, since V can only be evaluated point-wise, the access to such a support is unclear. In fact, this limitation goes beyond the multi-modal setting in some cases: matter the tog-Sobolev constant of the target, similarly to euclidean gradient descent, ULA still requires an priori bound on the inverse smoothness constant of V and sufficiently small step size in comparison in order to converge.
Generally speaking, finding a sampling algorithm that addresses even the first limitation is not pos- sible. Recent results provide lower-bounds the complexity of sampling from multi-modal dis- tribution: they are exponential in the dimension, as shown in Lee et all [2018, Th K. Chaki [2024, Th 3.3] and He and Zhang [2025, Th. 3]. However, when the dimensionality of whether the three limitations can be addressed remains. In fixed dimension, can we sample from a broad class of multi-modal distributions with polynomial number of queries in the parameters of the problem, (e.g. L, R, or) and without prior knowledge on these parameters?
fixed, the question
Our contributions Our work answers this question positively. We provide sampling algorithm that addresses the three limitations outlined above. First, we show that our algorithm has polyno- mial complexity in all the problem parameters but the dimension, thus enabling to efficiently sample from highly multi-modal distributions in fixed dimension. Second, we show that unlike most exist- ing results, our guarantees hold under relaxed regularity assumptions that cover general Gaussian mixtures. Third, our algorithm yield guarantees without prior knowledge on the parameters of the distribution.
The workhorse of our algorithm is made of two key ingredients: the reverse diffusion scheme, that transfers the sampling problem into a score estimation problem with different levels of noise, and self-normalized importance sampling, to estimate these noisy scores using only query access to V and additional Gaussian samples. Both reverse diffusion [Huang et all 2024 He et all 2024] and norf-normalized importance sampling [Huang et al, 2025, Tra et all 21241 Ruzayqat et all sample in a Bayesian setting, where only the log-density of the target available. However, these works either offer no theoretical guarantees or fail to improve upon existing results. In this article, we combine both reverse diffusion and self- normalzzdd importance sampling in a single algorithm, allowing us to recover the first polynomial time guarantees to sample from highly multi-modal distributions in fixed dimension.
2023, Ding et al, 2013,, Saremi al, 2012 were already used separately
This paper is structured as follows. First, we survey related work on multi-modal sampling in Sec- tion @ and present our main result Section B. Then, we detail our sampling algorithm in Section and provide the key ingredients for the proof in Section E.

---

2
Related work
Before detailing our sampling algorithm in Section EL we review the main alternatives to ULA when sampling from multi-modal distribution and the guarantees they offer. We show that existing approaches suffer from at least two of three drawbacks outlined in the introduction: exponential query complexity, restrictive smoothness assumption that excludes general Gaussian mixtures (as shown later in Sec. (.2), and unavailable prior knowledge of the distribution.
Proposal-bas -ased algorithms At a high level, proposal-base algorithms use proposal distribution that is easy to sample from and that can either be directly used as proxy for the target, alter- natively, whose samples will be rejected (respectively re-weighted) to obtain approximate samples from the target, the corresponding algorithm for the latter case is the well-known rejection sampling (respectively importance sampling) scheme. Guarantees for these methods typically assume that the target distribution is log-smooth. Furthermore, they must use carefully designed proposals that require prior knowledge of the target distribution that is often unavailable in practice.
For instance, when the target is L-log-smooth and with finite second moment m2, one can design and sample from proxy distribution that is c-close in TV to the target using O((Lmge yoid) queries to the potential function V and its gradient VV [[e and Zhang. 2025]. While this bound is indeed polynomial in fixed dimension, the design of the proxy requires an e-approximation of the global minimum of V which can only be achieved if m2, therefore the location of the mass, is explicitly available; this is rarely the case in practice.
Similarly, if we further assume that the target is a-strongly log-concave outside of ball of radius R. one can achieve an 6- e-precise approximation of the target distribution in TV with polynomial number of queries to VV when d is fixed via an importance sampling scheme [Chak,, 20221. Th. 2.3]. this case, the proposal is such that it coincides with the target when the potential of the target is above some cutoff, and is flat elsewhere. While there exists a cutoff value ensuring the log-concavity of the proposal, thus allowing its efficient sampling, this value depends on the unknown constants L, R and a [CCaa,, 2024,, Prop. 5.
Tempering- algorithms Instead of directly sampling from μ x eV these algorithms start by sampling from a flattened version of μ given by 1º x e -V for small B, and gradually increase 1, strategy sometimes also referred to as annealing. When μ is assumed to finite mixture of the same shifted a-strongly log log-concave and L-log-smootl distribution. Lee et all [2018] proved that for well-chosen (stochastic) sequence of flattened distributions μ sampling up to precision in KL can be achieved in poly(L, a wmin: d, -1 It) queries VV, where It is the location of the furthest mode and Wmin the minimum weight in the mixture. However, this setting is quite restrictive: for Gaussian mixtures for instance, it only handles the case where the covariance matrices are identical for all components, Furthermore, the algorithm requires explicit knowledge of R which unavailable.
Föllmer Flows Instead of directly sampling from the target distribution μ x eV Föllmer Flows start from a simple (e.g. Gaussian or Dirac mass) distribution that is progressively interpolated to the target using Schrödinger bridge. When the initial distribution is a Dirac mass at 0, this bridge solves a closed-from SDE [Wang et all, 2021, Theorem 3] which can thus be discretized to generate samples from the target. In the context of Bayesian inference, where one only has access to the unnormalized density, (argas et al. [2022] estimated the drift of the resulting SDE via neural methods; in particular no guarantees on the sampling quality are provided. In Huang et all [2025]] Uiao et all [2021]] Ruzaygat et al. [2023], Ding et all [2023], the drift is estimated via a Monte-Car method. While appearance, these works provide strong polynomial guarantees, a closer look shows that these guarantees only hold if the function fxx = e [[x)))[a==))) is Lipschitz, smooth and bounded from below; we show in Appendix B that this assumption is quite restrictive.
Diffusion-based methods Over the past few years, diffusion-based algorithms, and especially reverse diffusion, that we shall review details in Sec. EL have emerged as solid candidates for multi-modal sampling. In essence, they allow to transfer the sampling problem into the problem of estimating the scores of intermediate distributions that are given by the convolution of the initial distribution with increasing levels of Gaussian noise. Under an c-oracle of these intermediate scores,
3

---

it has been shown that Liffusiio-basse methods could yield an e-approximate sample of the target in poly(e 1) time under milder and milder assumptions [Chen et all m023B Benton et all. 2024, and Ocelld, 2025, Cordero-Encinar et all, 2025]. This framework has been applied with tremendous empirical success in generative modeling, where numerous samples of the target are already available and one seeks to produce new samples from the target, for several years now [Song and Ermon, 20T9, Hol. 2020. Hortol all, 20211 Chen [ However, it was only quite recently that this framework has been applied in Bayesian context, where only an unnormalized density of the target, instead of samples, is avail-
Lt all 2024, Conforti et all R025, Gentiloni
able [Huang et all, 2024al6 Heltaal 2024. Grenioux et all, 2022,, Akhound -Saeghh et all 2022 In
a work closely related to ours, Huang et all [2022]]] showed that if the intermediate scores remain L-log-smooth for any noise level, which in particular implies that the target itself is E-log-smooth, their algorithm could reach complexity of O(e ((d((t)))) with m2 the second order mo- ment of the target. In He et all [20241] the smoothness assumption is relaxed with a sub-quadratic growth assumption (zz) - V(x*) S LIaa -x= ="113. where x" is any global minimizer of V. yet at the price of an oracle access to V V(="); ); under these assumptions, the authors manage to obtain a complexity that is at best ( c ==l[ll=" where EN is the final output sample. Under the reasonable (and desirable) assumption that E[| = m2, Jensen's inequality yields an over- all -_ +l*+))) complexity. In particular, both these works suffer at least two of the limitations mentioned in the introduction, making them ill-suited for multi-modal sampling.
3 Presentation of the main result and application to Gaussian Mixtures
3.1 Main result
As in the works mentioned above, we rely on the recent advances on reverse diffusion and focus on the task of estimating the intermediate scores. Using an estimator that is described in Sec. Al we recover polynomial sampling guarantees for densities verifying the assumptions described hereafter. Assumption (Semi-log-conventt
We assume that μ. ix e V is such that log(11) is C2 and verifies 2 (1)(()) = -IIa or equivalently A = BIa some 3 2 O.
This assumption shall be referred to as cemi-log-corvexity, by analogy with the functional analysis literature [Mikulincer and Shenteld, 2023, Theorem 3]. Note that is has also been referred to as I-sided Lipschitzness for VV [Genttlom=SSiverr and Ocelld, 202S]. It relaxes the classical log- smoothness assumption which implies the additional lower bound V2V t -BIa- In particular, unlike the latter, mixture of semi-log-convex densities remains semi-log-convex [Marshall et all 1979, Chap. 16.B]; we provide a quantitative version of this statement in Sec. 3.2 in the case of Gaussian mixtures.
Assumption 2 (Dissipativity) We assume that μ X V is such that there exists a > 0,b 2 0 for which its potential satisfies (VV()), 2 a||=||2-
for all x E Rd.
This assumption is referred to as dissipativity as common in the sampling and optimization liter- ature [Raginsky et all, 2017. Zhang et all, 2017 Erdogdu and Hossemnzadel, 2021]. Note that this assumption relaxes strong convexity outside of a ball which can be equivalently re-written as (VV(x) - (2), x y) allx y/!² - b for all pairs (x, y) E Rdd also referred to as strong dis- sipativity [Eberle, 20TK Brdogdu et anl 2022]. We show in Sec. 1 that unlike strong-dissipatinn mixture of dissipative distributions remain dissipative.
Theorem [Main result, informal) Suppose that Assumption W and holld Then, for all c > O, there exists a stochastic algorithm whose parameters only depend on (and not on the parameters of the problem), that outputs a sample ~ such that E[KL(H, p)] S e3d+3(b (b+ d)/a² in O(poly(e queries to V. where E hides universul constant as well as log quantities in d, a, b.
In particular, when d is fixed, this algorithm can output a sample from a distribution that is e-close to y in expected KL in poly((b + 1)/a, 3, running time.
Our algorithm addresses the three limitations outlined in the sections above. When the dimension d fixed, we obtain polynomial query complexity. This guarantee does not assume log-smoothness and applies to general Gaussian mixtures, as will be shown in the next subsection. Moreover, this guarantee does not require running the algorithm with any explicit knowledge of the target distribu- tion's 's constants b, 3.

---

Algurilam
Assmmptons
Oracle
Complesity (Toial Vanation)
ULA MareE
Co- Da L. (VViia 3 Lh
VV.L
Proposal-basc based
Zhing
[V Hi
M.V.M.L
OILLM (jrre))
RD + ULA Friing
[V logip:l m,mg
PV
0013" (1altma/)))
RD Rejection Sumpling et 102z
V(z] Vix") Llle x
V.V*
RD + Self normalized IS (ours)
VVV 3 Blg, (VV()) 2012
Olydstor) /b afoc (1)))
Table 1: Complexity of sampling algorithms. We denote by x* a global minimizer of V, by V = V(x*) the global minimum of V. by m2 the second moment of the target, by Pt the density of the forward process (see Sec. BD and || the operator norm for matrices. In RD + ULA, RD refers Reverse Diffusion algorithm and ULA to how the intermediate scores are estimated. Even though originally stated in KL for our work and the one of He et all [2024]], all the complexities are w.r.t. the Total Variation distance (obtained via the Pinsker inequality).
Overall comparison We summarize in Table II how our algorithm compares to previous ap- proaches in terms of assumptions, oracles required to run the algorithm and resulting complexity. Along with the work of He and Zhang [2025], our algorithm is the only one that is polynomial in the parameters of the distribution when d is fixed. Furthermore, while our dissipativity assumption is stronger than finite second moment, we relax the log-smoothness assumption by semi-log-convexing which notably covers general Gaussian mixtures. Finally, as mentioned above, because their algo- rithm requires an e-approximation of the global minimum of V. they require explicit upper-bound on the second order moment of which may not be available in practice.
Numerical illustration In Figure 2 we consider a standard task in the literature: sampling from mixture of 16 equally weighted Gaussians with unit variance and centers uniformly distributed in [-40, 40 [Midgley et al, 2023). We compare our algorithm against Unadjusted Langevin Al- gorithm (ULA) and to the reverse diffusion algorithm of Huang et all [2024a] (RDMC). We also implemented the zeroth-order method of He etal [2024], but it failed to converge. ULA was initial- ized from (0, (2) and run for 5 x 10a steps. All three methods used the same discretization step size h = 0.01. Our reverse diffusion algorithm and RDMC were both run with 500 reverse diffusion steps and both used 100 samples to estimate the intermediate scores. As discussed in Sec. EL while our samples are simply drawn from a Gaussian distribution, the samples used in RDMC are drawn from auxiliary, multi-modal distribution generated via inner ULA step. In this experiment, this inner ULA was initialzed with a standard Gaussian and was run for 100 steps; in particular, we emphasize that while ULA and our algorithm were roughly given the same computational budget, the one given to RDMC was a hundred times superior. As a result, ULA and our algorithm took approximately one minute to run a computer locally and the RDMC method required over an hour. We observe that unlike the two others, our algorithm successfully recovers all the modes.
In Figure M. monitor the convergence of the same three algorithms as a func- tion of the problem difficulty, measured by the distance between the modes. Here, the target distribution is mixture of three
Convergence vs. Between mode distance
30
Wassersteln error
ULA
RDMC
Gaussians in two dimensions. It has equal weights 1/3, equidistant modes located a distance R from the origin, and different
20
Our algorithm
10-
covariances (I, T T/2, 1/4.. The final error is measured in Wasserstein distance, be- cause can be easily approximated using samples: we use 500 samples generated by the sampling algorithm and 500 sam- ples from the true target distribution. We allowed each of the three algorithms 106 queries to the potential V or to its gradient: we performed 10 iterations for ULA, we used 100 steps of reverse diffusion for our algorithm and RDMC. We used 100 inner steps of ULA for RDMC that was initialized with a standard Gaussian. We used 100 particles for score estimation for RDMC and 10000 for our algorithm. As expected, as the between-mode distance grows with R, our algorithm yields the lowest error.
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Belween-mode distance
Figure 1: Error in Wasserstein distance as a function of the between- mode distance.
5

---

3.2 Application to Gaussian mixtures
We now apply our results to derive provable sampling guarantees for general Gaussian mixtures. Apart from the very recent exception of Lytras and Mertukopoulos [2025]] that we discuss below, note that despite their wide popularity, no sampling guarantees were yet derived for general Gaus- sian mixtures. Indeed, unless they verify some specific assumptions such as identical covariance matrices among components (Cordero-Eneinar et all 2025, Lemma B.1], general Gaussian mix- tures do not satisfy the log-smoothness assumption, thus they do not fit the framework of many previously discussed works. In fact, their gradient may not even be Hölder continuous: consider the simple counter-example of a two-dimensional mixture
0.5 Σ1) + 00,A 22) with covariances Σ1 = diag 1, 0.5) and Σg d0ag(0.5, 1). On the diagonal x = y, the score is V log(()) (x, x)
/3/2(z,, .). while near the diagonal, right above it for instance, the score be- haves asymptotically as log( ~2++00 - -2xx, z); we provide a rigorous analysis in Ap- next show. Proposition 2 Let μ Ei=1 wyN(ps, Σd) and denote Amin > (resp. Amaz) the minimum (resp. maximum) eigenvalue of the covariance matrices Ex. holds that -V² log(m) 3 Ia/ Ja/Xmin and that for all I E R (-V Log(()))))) 2
pendix B. Fortunately though, Gaussian mixtures do verify Assumptions M-
Amaz max; Amin)
The proof is deferred to Appendix
B. Combined with Theorem I1 Proposition 2 shows that we can sample any Gaussian mixture with average precision e in KL in (pooly R, d, Xmii+ e Ed) queries to V where Rt = max; || and к \mar/ Amin There exists relatively recent literature seeking to relax the log-smoothness assumption. For instance, Chatterji et all [20] Erdogdu and Hossemnzadeh [202]]] Nguyen all [202]] work under weak smoothness, i.e. a-Hölder continuous gradient of the potential for a in (0, 1 (recall that a=1 recovers the smooth case). However, as shown above, this relaxation is not sufficient yet cover general Gaussian mixtures. The only reference we know of that does is the work of Lytras and Mertikopoulos [2025]], who used a regularized version of Langevin relax the global smoothness condition with local Lipschitz smoothness and polynomial growth of the Lipschitz constant. Yet crucially, their complexity bound scales as polynomial of the Poincaré constant of μ. We prove in Appendix B4l that for the mixture μ 0.5. (,R,,, Amax + (..N(--Ru, Amin with any unit vector and 0 < Amin I Amax, this constant is at least (R2e (2Amma))/2 In particular, this method still degrades exponentially with the multi-modality parameter R.
Our sampling algorithm
In this section, we introduce the reverse diffusion framework and explain how reduces the sampling problem to that of estimating the scores along the forward Ornstein-Ullenheck (OU) process.
4.1 Reverse diffusion: from sampling to score estimation
Reverse diffusion methods emerged as an alternative to Langevin-based samplers in order to over- come metastability and were first introduced to the ML community in (Song et al. [2021]] They rely on the so-called forward process
dX; -xdtt + V2dB. Xo ~ n,,
(1)
-30
20
20 40
Figure 2: From left to right: our algorithm vs. ULA vs. Huang et al. [024a]] The color scheme indicates the probability density value of the distribution we want to sample from (dark low prob- ability density, bright is high probability). The blue dots are the samples produced by the algorithm.

---

which corresponds to the standard OU process initialized at μ. that is specific case of Langevin diffusion targeting standard Gaussian, that we will denote я. Note that since the target of this process, the standard Gaussian, is 1-strongly log-concave, the resulting process converges expo- nentially fast to the equilibrium. In order to sample from jr, reverse diffusion algorithms rely on the semi-discretized backward process: given horizon T that we discretize as 0 = to s 4 -N- S i 'T, the latter writes
dy, = Y,dt + 2V log (P) + V2dB, t tElT - -N - IN 1x-(+
(2)
with Yo- Pr and where Pt is the distribution of the forward process Eq. at time t. Note that this reverse process cannot be readily implemented for two reasons: first, requires the knowledge of the intermediate scores V log(pt,) which from the distribution pr. Nevertheless, if one can access a proxy St,, of the scores V log(pt,). and considering T' large enough that pr n. can implement instead
available in closed form. Second, it requires sampling
dY;- Yjdt + 2st, (Yx) + V2dB,, t E|T -N, -, (N-((t1))
with Yo- ~ and where all iterations can be solved in closed form. Because the forward process Eq. converges exponentially fast, we can expect the initialization error Yú ~ π instead of Y. pr to be small after short time T. Furthermore, if the proxies St, are sufficiently accurate, one can expect that the process output by the approximate scheme Eq. 3 has distribution that is close the target μ.. Over the past three years, several works provided quantitative bounds of the error induced by the discretization, the use of an approximate score and the initialization error with respect to different divergences and under various assumptions [Bortoli et all, 20211. Lee et all, 2022,, Chen aLa 202 Contort atall 2025). Yet, we shall rely exclusively on the following theorem as is the most suited to our framework.
Theorem (Contorti et all (2025]) Assume that i x e has finite Fisher-information w.r. π the standard gaussian density in Rd:
/ VV==VV(()))dd(a < t00.
I(
Then, for the constant step-size discretization to KT/N, denoting p the distribution of the sample Y1 output by Eq. B. holds that
N
Kl(up) S (d m2)e
+
1
Σ
V log(pre) Sc,
T Pe.1i (iEP()))) + N I(u,))
N
k=1
where ma is the second order moment of μ and where S hides a universal constant.
The previous theorem shows that under mild assumptions that notably allow for multi-modality. the problem of sampling from μ can be transferred into score approximation problem along the forward process. In the next subsection, we present an estimator for these intermediate scores that tractable given the knowledge of the unnormalized density μ ee-V.
4.2 Derivation of estimator
The key observation to derive an estimator the intermediate scores is that the forward process Eq. M is nearly available in closed form. However, this closed form may be written in different manners.
Different expressions of the scores Consider Eq. II integrates to X, XxX + VI- where X; = e- 2t, Z a standard d-dimensional Gaussian, and X, is random variable simulating the target distribution. The corresponding density convolves the target density with Gaussian, as
1
p (x) -
VX.
where æ is standard Gaussian and yn()) (p)) the target distribution. From this expres- sion, we can obtain different formulas for the scores. We retain
1. v loggy (z)
Di, Eylı
V log
u/ ~X μ1
1- x NN (1 - Ax)
Vxe
7

---

=- --viーー
=- =-vA-A1
Ex log
2. V loggl (x)
v/a
v/a
y~ ~rr000
vx.
Bylu
v/a
3. V Vlogrl (x)
1-2i (Eylall) - x),
1
5120 1 (vxta)
x N -x)T)
By m *tV /TV1-
4. V loggy (z) VI-At By
V
y y~N(r
Derivations can be found in Appendix Al The second [Akhond-SSadegh et al, 2024]. third [Huang etall M0ZE, He et all, 2024) Grenioux et atl 2024] and fourth [Saremi all 2022| identities have been used to build Monte Carlo estimators of the score. Hence, one natural way to group these identities is by how difficult it to draw the samples y. The second and fourth identities sample from a Gaussian distribution, whereas the first and third identities sample from an auxiliary multi-modal distribution from generating y lr. As gets closer zero, this auxiliary distribution resembles the original target, so sampling from it progressively becomes as difficult as sampling from the original
target density. This observation explains why, unsurprisingly. Huang et all [20225], He et [2024] do not improve upon existing results. Another way to group these identities is whether or not they require evaluating the score of the target distribution: identities one and two do and are referred to as
TSI estimators, referring to the Target Score Identity (TSI) used to obtain them [Bortoli al. 20224]; identities three and four not and are referred to as DSI estimators, referring to Denoising Score Identity (DSI) used to obtain them [e et all (22 Combinations of TSI and DSI estimators have
also been considered [Phullps et al. 2074
Hc al 2025
We now focus on the estimator of the scores that we use. It is rewrite of the fourth identity and a ratio of expectations under Gaussians
A self-normalized estimator
-1 E VV(c'(=-xx) 1-
V logg(p)) - Ee V(ee(=
with Y ~ (1- which is easy to simulate. While conventional statistical wisdom may suggest using independent samples estimate both the numerator and the denominator, we voluntarily choose to correlate them and implement instead
D the V(el(=-vi)
-1
8t.m (z)
e E. V(e
where the y4 are independent Gaussians such that Yo c1 2l we refer to this estimator as self-normalized as common in the sampling literature [Agapiou et all 2012]. The key property of self-normalized estimators that they remain nearly bounded: in our case, holds uniformly in that
(1
E E/max, 11 II
dlog(n) e--i
E S2,n (z)]II
1 e-
This boundedness will allow us to derive a non-asymptotical control on the quadratic error that we present in the next section.
We now explain how this differs from previous work. While this estimator was already considered in [Saremi et all MIRZIJ, the authors did not use it within the reverse diffusion pipeline and more importantly, we are the first work to derive quantitative guarantees for this estimator, which is one of our core contributions. Similarly, an estimator close to this one was considered in the context of Föllmer Flows [Maa et all 2021. Ruzayqat et all 2023. Ding et all 2023| in order to approximate the shift in the corresponding Schrödinger bridge. We show in Appendix B.I.I that while this shift itself close to the intermediate scores that we seek to approximate, the resulting self-normalized estimator is more degenerate. Namely, as discussed above, their guarantees are significantly weaker.
5 Sketch of proof of the main result
The proof is decomposed in three steps: (i) we derive a non-asymptotic bound on the quadratic error of the estimator presented in Eq. B (ii) we show that under Assumptions M-Z, the integrated error of
8

---

this estimator (that appears in the bound of Theorem B) can be fully controlled by the zeroth and second order moments of the ratio b. = p /pY where p." (respectively p.") is the density of the forward process defined in Eq. M initialized at μr (respectively j)) (iii) we provide a quantitative bound on these moments as well as other relevant quantities and we conclude with Theorem B.
Proposition& 4 (Non-asymptotic bound on the quadratic error) For all E R2, and I. >> 0, denoting pf" (respectively p. ) the density of the forward process defined in Eq. 0 initialized at 2² x e-2V -2V (respectively js e-V). Zzv (respectively Zv) ) the normalizing constant of μ² (respectively μo) and t the density of the standard Gaussian, it holds that
32c² (d + +og(n))
P2 (2)
E (1)) Vlog(p))
S
1 1 (1)
M(1--22)
(p) (z)
with (z(2) A log (z) A Alog(m)(s) 21
V Log (pl (=) + lo (2) 112 +1.
The complete proof is left to Appendix Q yet we briefly sketch the main arguments. We split the expectation on the event A where the empirical denominator D of Eq. 5l (respectively the empirical numerator Ñ) is not too small (respectively not too large) with respect to its expectation D (respec- tively []) and on the complementary Á. Over A, we use a second-order Taylor expansion to make the variances of both the numerator and the denominator appear, and compute them explicitly, Conversely, the quadratic error of the estimator remains almost bounded on A. We use Chebyshev's 's inequality to upper-bound (AA) and make the variances of the numerator and of the denominator appear again, which concludes the proof.
Remark 5 Generic bounds on self-normalized estimators were derived in Agapiou al [207
Theorem 2.3]. Yet, we show in Appendix B.5 that if used in our context, they would involve at least an V.) factor which can cause the integrated error f E [[] (2) V log((p) (px) (z) [?a] dp. (2)
extra 1/(p)) to diverge.
Then, we need to control the Laplacian of the forward processes well their gradient appearing in 8, in the former proposition. As mentioned in the previous section, the intermediate scores can be re- re-written as
V log (z) z M
1-e-2 2
with (x) x e e-v(=)e 1=-fa-112
201---2) Now we note that if x e is dissipative, so is 9t.s in particular we can quantitatively bound its second order moment and a fortiori, upper-bound ||V log(r (=)l?²
Proposition 6 (Regularity bounds on the forward process) Suppose that Assumption D holds. Then, for all 2 E Rd and L > 0, it holds that
Io - (1-e 20y2
||
+ a(l-e
2t
+
2e (2(6+
a(1 - 21
A Alog(p\) S 25-
1=l|
+ 26+d
Ba(1-e-21j
-
The complete proof is left in Appendix b This result implies that the 0r term defined in Proposi- tion is at most of order of order (z(2) ~ (1 + [|2]]²) w.r.t. z. In particular, the average integrated error E E (2) V log (p) ( can be upper-bounder with respect to the zeroth and the sec-
ond order moments of the ratio p, pi /p/". In the next proposition, we show that these moments are bounded under the semi-log-convexity assumption. By a slight abuse of notation, we shall denote m, (T.) [ (2))) the i-th moment of h..
Lemma 7 (Bounds on the moments of the ratio) Assume that μ x - has finite second moment m2 and that Assumption 0 holds. Then,
m)( S ( cd -e c 2222 + e e-2dd ZAy
m2( < 2t
1zzr (3(1 e e- c2) ) + e 2-2dd m2 + d(3 + 11) + 2d log (Bu(0) 2/d
Zav
2
where Z (respectively Zx) is the normalization constant of -2V (respectively e e and where π in the right-hand-side -ide refers to the constant π se 3.14.

---

The proof of this lemma is deferred to Appendix E. It relies on key result in Mikulmner and Shenteld [2023, Lemma 5] where is shown that for 3-semi-log convex distributions, the following bound holds:
(3 - 1)e 1)e
2 log(T)) V log(p!)
(1-E-21)(B 1) La.
In particular, the right-hand-side remains bounded w.r.t. & whenever > O, which allows to avoid an exponential dependence in B in final bounds. It suffices now to control I(U, R), m2 and (0( in order to apply Theorem E and conclude.
Lemma 8 Assume that μ x e- such that Assumption D and hold: V 1 (VV(x), 2 a||ar|12 b for some a > 0,b, B 2 0. Then,
BIa and
m2 S (b (b+2d)/a,
I(u, T) - 2(b + 2d)/a- + 28d, log (p((0)))21) 4/3b/ (db)/(da) + 2 1og(2/o).
Here again, the π. in the right-hand-side refers to the constant = 3.14.
The proof is left to Appendix D We can now state our main result.
Theorem 9 Under Assumptions W and A if we run the algoritiu of Eq. G with T = log(1/c), N = 1/c, lx = KT/NN and with the stochastic score estimators 8ugds, defined Eg. Bl with vs de (2d+3), then, denoting p the stochastic distribution of the output YN. it holds that
EIKL(H, D)] e.a43 d)/a²,
where 2 hides a universal constant as well as log factors with respect to d, 1 a, b, B. In particular, the error above is achieved in Ex= n2. = de- 2(d+2) queries to V.
The proof is deferred to Appendix B Bandin is mainly application of the results collected above.
6 Conclusion
In this article, we successfully applied the reduction from sampling to intermediate score estimation, initiated over the past three years by Ct [2023Bal] Contorti et [2025] Benton et all [00ey)
to the problem of low dimensional multi-modal sampling. Using the self-normalized estimator of the scores, our results provide polynomial query complexity guarantees in fixed dimension, apply to general Gaussian mixtures, and do not require prior knowledge of the target distribution's 's constants. Interesting future directions include extending theoretical guarantees to more general multi-modal distributions with heavy tails for instance.
We note that our sampling algorithm is based time-reversed diffusions, which have recently gained traction for sampling from unnormalized densities. Our method stands out by offering rigor- ous, non-asymptotic theoretical guarantees on query complexity, especially in the presence of score estimation error that we precisely quantify. Such theoretical guarantees are scarce and we believe our results are therefore meaningful and timely contribution the field.
7 Acknowledgements
This work was supported by the Agence Nationale de la Recherche (ANR) through the JCJC WOS project and the PEPR PDE-AI project (ANR-23-PEIA-0004) We thank Pierre Monmarché for his help in proving Lemma
References
Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and Andrew M Stuart. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, 2017.
Tara Akhound-Sades -Sddehh Jarrid Rector-Brooks, Avishek Joey Bose, Sarthak Mittal, Pablo Lemos, Cheng-Hao Liu, Marcin Sendera, Siamak Ravanbakhsh, Gauthier Gidel, Yoshua Bengio, al. Iterated denoising energy matching for sampling from Boltzmann densities. In ICML, 2024.
10

---

Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-Linear con- vergence bounds for diffusion models via stochastic localization. ICLR, 2024.
Adrien Blanchet and Jérôme Bolte. A family of functional inequalities: Lojasiewicz inequalities and displacement convex functions. Journal of Functional Analysis, 2018.
Valentin De Bortoli, James Thornton, Jeremy Heng, and A. Doucet. Diffusion Schrödinger Bridge with applications to score-based generative modeling, In NeurIPS, 2021.
Valentin De Bortoli, Michael Hutchinson, Peter Wimsherger, and Amaud Doucet. Target score
matching, arXiv preprint arXiv:2402.0866) 2024.
Martin Chak. On theoretical guarantees and a blessing of dimensionality for nonconvex sampling. arXiv preprint arXiv:2411.07770 2024.
Niladri S. Chatterji, Jelena Diakonikolas, Michael I. Jordan, and Peter L. Bartlett. Langevin monte
carlo without smoothness. In AISTATS, 2019.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In ICML, 2023a.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li. Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In ICLR, 2023b.
Sitan Chen, Vasilis Kontonis, and Kulin Shah. Learning general Gaussian mixtures with efficient score matching. In COLT, 2024.
Giovanni Conforti, Alain Durmus, and Marta Gentiloni Silveri. Score diffusion models without early stopping: finite Fisher information is all you need. SIAM Journal on Mathematics of Data Science (SIMODS), 2025.
Paula Cordero-Encee Encinar, O Deniz Akyildiz, and Andrew B Duncan. Non-asymptotic analysis of diffu- sion annealed Langevin Monte Carlo for generative modelling. arXiv preprint arXiv:2502.09300 093006 2025.
Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 2019.
Wei Deng, Guang Lin, and Faming Liang. A contour stochastic gradient Langevin dynamics algo- rithm for simulations of multi-modal distributions. In NeurlPS, 2020.
Zhao Ding, Yuling Jiao, Xiliang Lu, Zhijian Yang, and Cheng Yuan. Sampling via Föllmer Flow. arXiv preprint arX1v:2111.03660, 2023.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 2017.
Andreas Eberle. Reflection couplings and contraction rates for diffusions. Probability Theory and Related Fields, 2013.
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of Langevin Monte Carlo: The interplay between tail growth and smoothness. In COLT, 2021.
Murat A. Erdogdu, Rasa Hosseinzadeh, and Shunshi Zhang. Convergence of Langevin Monte Carlo in chi-squared and Rényi divergence. In AISTATS, 2022.
Marta Gentiloni-Silveri and Antonio Ocello. Beyond log-concavity and score regularity: Improved convergence bounds for score-based generative models W2-distance. In ICML, 2025.
Louis Grenioux, Maxence Noble, Marylou Gabrié, and Alain Oliviero Durmus. Stochastic localiza- tion via iterative posterior sampling. In ICML, 2024.
Jiajun He, Wenlin Chen, Mingtian Zhang, David Barber, and José Miguel Hernández-Loobtto Train- ing neural samplers with reverse diffusive KL divergence. In AISTATS, 2025.
11

---

Ye He, Kevin Rojas, and Molei Tao. Zeroth-orde order sampling methods for non-log- non-log-concave concave distribu- tions: Alleviating metastability by denoising diffusion. In NeurIPS, 2024.
Yuchen He and Chihao Zhang. On the query complexity of sampling from non-log-concave distri-
butions. In COLT, 2025.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In NeurIPS, 2020.
Jian Huang, Yuling Jiao, Lican Kang, Xu Liao, Jin Liu, and Yanyan Liu. Schrödinger-Flllmer sampler. IEEE Transactions on Information Theory, 2025.
Xunpeng Huang, Hanze Dong, Hao Yifan, Yi-An Ma, and Tong Zhang. Reverse diffusion Monte Carlo. In ICLR, 2024a.
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, and Tong Zhang. Faster sampling without isoperimetry via diffusion-based Monte Carlo. In COLT, 2024b.
Yuling Jiao, Lican Kang, Yanyan Liu, and Youzhou Zhou. Convergence analysis of Schrödinger- Föllmer sampler without convexity. arXiv preprint 1rXiv:2107.04766, 2021.
Holden Lee, Andrej Risteski, and Rong Ge. Beyond Log-concavity: Provable Guarantees for Sam- pling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo. In NeurlPS, 2018.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. In NeurlPS, 2022.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards non-asymptotic convergence for diffusion-based generative models. In ICLR, 2024.
Iosif Lytras and Panayotis Mertikopoulos. Tamed Langevin sampling under weaker conditions. In AISTATS, 2025.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 2019.
Albert W Marshall, Ingram Olkin, and Barry C Amold. Inequalities: theory of majorization and its applications. Springer, 1979.
Laurence Illing Midgley, Vincent Stimper. Gregor N.C. Simm, Bernard Schölkopf, and José Miguel Hernández-Lobato. Flow annealed importance sampling bootstrap. ICLR, 2023.
Dan Mikulincer and Yair Shenfeld. On the Lipschitz Springer International Publishing, 2023.
Properties of ('Tansporrtation Along Heat Flows.
Dao Nguyen, Xin Dang, and Yixin Chen. Unadjusted langevin algorithm for non-convex weakly smooth potentials. Communications in Mathematics and Statistics, 2021.
Angus Phillips, Hai-Dang Dau, Michael John Hutchinson, Valentin De Bortoli, George Deligianni- dis, and Arnaud Doucet. Particle denoising diffusion sampler. In ICML, 2024.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In COLTT 2017.
Hamza Ruzayqat, Alexandros Beskos, Dan Crisan, Ajay Jasra, and Nikolas Kantas. Unbiased esti- mation using a class of diffusion processes. Journal of Computational Physics, 2023.
Saeed Saremi, Ji Won Park, and F. Bach. Chain of log-concave Markov chains. In ICLR, 2024.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In NewriPS, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In ICLR, 2021.
12

---

Francisco Vargas, Andrius Ovsianas, David Fernandes, Mark Girolami, Neil D. Lawrence, and Niko- las Nüsken. Bayesian learning via neural Schrödinge-FFöllme flows. In AABI, 2022.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In NeurIPS, 2019.
Gefei Wang, Yuling Jiao, Qian Xu, Yang Wang, and Can Yang. Deep generative learning via Schrödinger bridge. In ICLR, 2021.
Yuchen Zhang, Perey Liang, and Moses Charikar. A hitting time analysis of stochastic gradient Langevin dynamics, In COLT, 2017.
13

---

Appendix Table of contents
Expressions the infermediate scores
15
Additional discussions
17
Föllmer Flows
17
32 Detais on the non-smooth example
17
B Proof of Proposition 2
18
B.4 Discussion Lytras and Mertikopoulos 2025
19
Discussion on Agapiou al. 2017
20
Prool of Proposition 4
22
Proof of Proposition and Lemma
26
DJ Proof of Lemma
27
D.2 Prool of Proposition
27
Proof of Lemma
28
Proof of Theerem
34
14

---

A Expressions the intermediate scores
We next provide derivations of the Monte Carlo estimators of the intermediate scores discussed in section 2
The probability law along the reverse diffusion path has density
py (x) VI- π
14
(6)
Vx
where ı is standard Gaussian and ju(-) x exp(-V(()) is the target distribution
Case 1: write the convolution an integral against the proposal distribution
We have
p
y
dy 1
1
f(2,))dg
(7)
Zx, yERR
Vx
Znne
where we denoted the integrand by f(, y). We can compute the score
Vlogr = (x) [V (x, y)dy Vxe / log
/
x 2 Vxe
f(z. v) f(xx,
dy
(8)
Pe (I) f(x, y)dy
From this, we can either define Monte Carlo estimator
v log T (x)
B
V log
x
g/ ~ox f(x
where f(x,y) is smoothened version of the target distribution distribution. Replacing with standard Gaussian. Or by unpacking f (ar, y) and using the proposal as the sampling distribution the integration variable y appears in it,
1 By V Vlog
V log pt (x)
Vxr
By ju
7~T
VI-x
VI
y
Xe
(10)
Case 2: write the convolution as an integral against the target distribution
We now have
pY (z)
Zn. yEER (/,,) α
VI- dy
I x-
1 I |sle.uddyy
(11)
Zx.
where we now denote the integrand by f(x, y). We can compute the score
Vpl (x)
f y)dy
V VlogpY (x)
(12)
pY (x)
f( y)dy
/
Viogg क (x==²)
[(a, v)
[ v)dy dy
(13)
From this, we can either define a Monte Carlo estimator as
v loggy (x)
Eylz
V log
( u/æ ~ox f(x,y)
(14)
vI
where fæx y) is smoothened version of the target distribution distribution. Or else, by upacking f(x, y) and using the target as the sampling distribution as the integration variable y appears it,
Ey
log π
a-y VI
v Vlogp (x) -
y ~ P
y VX
(15)
Ey
which is not very useful given that sampling the target hard the first place. However, we can use the proposal distribution the sampling distribution the integration variable appears in it as well. To see this, recall that
ạ D
= . x -0 VV XoN (o 01 >t)
(16)
/1 X
--
N,N (y:
Aa)
(17)
15

---

This leads to
By
[y
xM
y
V loggi (z)
y~~ - (1-)))1a
(18)
1 Xt
y By |a
1 Eg 2/
x - Are
vi
~~~(zz00,aa)
(19)
Xe Eg
xtvT-Xis
Vdi
Using a change variables, we obtain
E exp
-V
V loog(p))
-1
VA
(20)
1- B exp
-V(
with Y, ~NO -a))
16

---

B
Additional discussions
B.1
Föllmer Flows
B.1.1
Comparison with our work
Instead of implementing a reverse diffusion process, Föllmer Flows Huang et al. [2025]] [iao et all 20211
Ruzayqat et all [2023] seek to implement the following Schrödinger bridge:
dX,- b(X,, t) + dW,, Xo
with b(x, V log Ez Wi-t)] and where f is given by du
(a) with μ the target density; for such a process, we have that X1 We refer the reader to the notations Proposition 14 observe that the shift 6(x, t) is given by
b(x, t) = log 10g00/2/(////
1
V logp log()/((2//V3 (og)())),
with ı is the density of the standard Gaussian. Hence, up to the Gaussian term and a time-rescaling, the shift exactly given by the intermediate scores the reverse diffusion. However, because the Gaussian correction, extra exponential term appears in the associated self-normalized estimator of the shift: Huang et all [2025]], Iiao at [2021], Ruzayqat et all [202]] the authors implement
b(I,t) Σi= (x + V 1z - VV + v (2))e - VeooVV/------- (z)+ Iir+ (|tt///a.//l//
6 E (it-VV=+vv---a) [tv1)
with 2, n-i.id. samples from the standard Gaussian distribution. We suspect that because of the extra exponential terms el ell=+vi-fs as discussed below, their estimator provide appealing guarantees only under very stringent assumptions.
B.1.2 Theoretical guarantees
The theoretical complexity bounds derived in the works of Huang et al. [2025]. Diao et all [2021]]
du Ruzayqat et al. [|23]] quantitatively rely the assumptions that dA((0, is Lipschitz, has
Lipschitz gradient and is bounded from below. In particular, assume for instance that ye a standard
Gaussian centered at some point E Rd. In this case, the ratio ff reads
f(x) 22 c+|lel
which verifies none of the assumptions above if + O. More broadly, even if verifies these assump- tions, the resulting quantities degrade exponentially with the mismatch between & + - log (x) and x || As noted in Vargas et al] [2022], this limitation is not only theoretical artifact; in practice, these methods are very unstable and fail to convergence on simple examples.
B.2 Details on the non-smooth example
Consider the mixture 005. En) + 0,, Eg) with Σ₁ = diag(1,0.5) and Σ1 = diag(0.5, 1). For (a, v) 122 it holds that
(x. 2y) 2 -² 12/1 + (2x. y) 22--222
v log(H)(z,))
0-12/2-13 -0² -==--1 -12/2
Hence, when x = have -V log(()) (x, v) 3/2( 3/2(xz x). Now for
17, the score reads
+)) (x,2x 2x + 2nje 12-222 2n x + (2x, + n)e-- 22- 12 12- -
x- - 2n n7
- x² x² 1/ -
(x. 2x + 2n) n0 pp- 2 12 (2x, x 17)
n2 92 +1
2ootoo (2r, x))
In particular, - -V log(u) is not Hölder.
17

---

B.3 Proof of Proposition 2
Recall we denote Aegn = Ian,dran(Zi),
Amax max; Amax (Ei). We write:
(- (x m²) T x (2: - m.)) = Σ (x)
1
m(x)=
Wy exp
with ú; = w; w2T 2/2 det(E;) (Ix) -1/2
Bound on the Hessian.
The Hessian of μ writes:
1
1
2 logu(z))
V u(x)
mxx) (a(z)Va(x)
11(x)
Since
Vo.(2) = 2 14) (1(2))
V Vo(( [0 (xr (1) us) En) x dx(2)
We have
Vu(a)= Σ W: Vol(()) Σ (idi(() E (x -1:)
v²u(2)= Σ V.V2) = Σ (x))(x) | (x u.) un) 2T -T-1
==1
Denoting (x(x): = (x) ((x)
and s;(x) -Ep (x pi) we get
- - Σ (ocooaloo) (Irccossto)
2 ((x) = E ((x) -
= (s) - -
where the first term is covariance matrix of the vectors (a()) under the weights (x()), hence which a positive semi-de cemi-definite matrix. Therefore:
-22 log p(x) Σ (mxx)T 3 Ent)) 1a- Ia-
Atan
Alan
Bound on the drift. For the (negative) score of the mixture we have:
V(o = Σ En(())) (x m4)
Hence
P Σ (E) (x 2)))
logg(<))
(x) (x 2 x n 2 2)
Σ
m())
Xmax u 21
la for the first term. Now for the second term, using Cauchy- where we have used D 2 Amax Schwartz and Young's inequality:
||l|||
1 (1|=]|2 + |1
n. T - ||mll 1|5 xl1 <
Aian
2213m
18

---

Hence, using that Σ; 7s(2) = 1 and that E, 7xxx)]l I max; || we have:
(logu(x); 2
7x(x)
||0112
1
(1|z=11 (1121133)
Amax
2A1an
1
1
p
||0112
Amax
2d10n
2ALan
1
|0]|
max ||:
Amax
2d1mn
2A1
|
|peal|
2
Amax
max
2Amax
Aaan
B.4 Discussion on Lytras and Mertikopoulos 2025
To justify claims at the end of Section 57 first need some preliminary background Poincaré constants. Let E (RR() We say that satisfies the Poincaré inequality with constant Cp 2 if for all f E W) (functions with zero-mean with respect to and whose gradient is squared integrable with respect q):
f (())dg(x) & CpIlVfllia
(21)
and let Cr(() be the best constant in Eq. 21 or +00 if it does not exist. We show that in the Joll case where μ 1/2N(c, Amar) (-/N((C,, Amin) the Poincaré constant is at least 2e ZAmaz /||c||
therefore the resulting sampling complexity in Lytras and Mertikopoulos [2025, Theorem 3] is at |ell
least ((poly((cc]) 2hmus ( ())
Proposition 10 Let 1/2N(c, Aman + 1/2N Amin la) with Amaz 2 Amin > 0 and ||c|| > It holds that
1012
Cp(M)
2
Proof.
Denoting u = c/|lcll and defining g IR + R as
{
s(() -1 < -1|c|1/2,
g(t) 2t/[|c| if - ||cl1/2 <t |c|1/2.
((() if t ||cl//2,
consider the function fx) g(x uu). Denoting μ1 W(xxAmaxta) p2 = NC-c, Aminta). we start to upper-bound the Dirichlet energy 1 = f
2 ||||2
||||| 2
|c|l
||l||
s xxtus (illl)) 2
[ (Px~ai
< x
us
+ P
2
2
Now remark that for X μis the random variable X T u is also a one dimensional gaussian: X Mr, it holds that X Tu ~V[[lll),, Amaz) ) and if X ~ n2, it holds that x (-|||c|| Amin). In particular, the Dirichlet energy re-writes as
|||||
3|||||| 2 Amma
||llll
-//|c||
1 |c|2 ④
+
2/Ames
2//min
2 Vemin
where is the cumulative density function of the standard Gaussian. In particular, I is upper- bounded as
4Φ Jel
2e 2
Te| (1 erf( |||||
27/mas
I 15
|cl
122maz
||c||2
Now there remains to lower-bound the variance term. The variance reads
(fr = f pdu= 1f + (x))))
19

---

The first term can be lower-bounded as
||||
[x2() 2 P Px [XT 1 2
2
|c|l
( 2 Amax
2 1/2.
Conversely, it holds that 1,, 2 1/2 and fortiori Var, (f) 2 1. Hence we recover that
Jel2
(ff
||||
ZAmaz
which concludes the proof.
B.5
Discussion on Agapiou et al. [
In Agapiou et all 201 for dominated by r,, denoting g the unnormalised density ratio
dv (u) = J g())dT(u))
g(u)
dm
the authors derived error bounds for self-normalised estimators: for any test function Rd - R. the expectation of & under denoted v(Φ). is estimated via
v" (Φ) = Σ o(x:)g(x,)
Di=1 g(2,)
with (a:) n-iid samples drawn from In Theorem 2.3, they provide the following quadratic emor bound:
B[(v(0) n"' (0)) 3 2/
(22)
(g(
with (h) = x((((-) (hi)l') and d, too such that 1/d + 1/E 1. Now recall that, denoting Y, ~ (/,,N - (2)) the score along the forward is given by
-1 B
Vlog(p!)
1 1- 2t Ele (x]]]]
1n12
-1 J ye ((ee w)) 2:--- dy
e 2t
1x1l Eznu(Z],
J ee-V(ot(=- (of((=-v))) wille - dy
2t
ui=1
where v(x) x e-(()) error of the self-normalized estimator reads
2---- In particular, denoting ((x) x e 24-6-25
the quadratic
1
Σn Mag(y))
(z) Vlog 2
EZ
(1 c 2092
Σ g(1.)
1
i= ou (1:)g(())) Σm ((v))
EZ lox (2)
(1 - e 2122
with g dv/dm, (ys) n-iid samples drawn from and Φx Fd + R the projector on the k-th coordinate. Hence, the bound Eq. M of Agapiou et al, [ provides the following upper-bound
3 3
(x) Vlogpl (2)12 <
nT(g)
20

---

We show in the next paragraph that, when integrated against p this upper-bound is vacuous. By Jensen's inequality, it holds that
(2e 2 m2 (((ong|2d) (((@ug/3)11
Hence, the previous right-hand side of lower-bounded as
d
3 22) (00)
(m((6) 3m2(g) d (g(g)*
Σ ((oxg]=)) n
(g)²
We now compute explicitly each of the quantities in the right-hand-side above using Proposition First we have
1=12 (g) = (2i(1 - 22)1)) -d/2 / cVVeelt--all 20-6 dz
= = (z).
Then, the variance term reads
- mz(g) (2 - c --22)))-111 / (o-Vielte=2)) - (2)) 201-- dæ
1=-1
ed Z2vPt 2V (z) 22-22 Zzv Zvpl (2)pt 2 (2) (vp)(2)p? (e /p (2)² (2)
Finally, the second order moment term reads
क () = (2 - c 2-211) -//2 2)) / (101(2e-21e0(-=0)) 201- 25 dx
= 2V (z)0(=),
where we denoted
((2) = Z2v - e 20)2 log (pt (=) + V log log (=))1 + d/(1 - e c-21)
Hence, once integrated against p lower bound reads
(g) not (1)
d Σ (lovol ( (=)d== 2nd Z2v 7 / O 22 (2) Pf (2)3
de 22 Z2y 733
/
22 (x) 0())
dz
pt (2)²
A=1
+ ed Zav
/
pi (z)
O(2)
dz.
ZF
P (2)
Combining Proposition E and Lemma M we have that the third term is always finite. For the specific case V(x) ||]|" we show that the second term also remains finite while the first diverges thus making the overall lower bound diverge. First, we recall that for this choice of potential, we have
{
(2) xe D2 (2) 20 21/3
from what we obtain
((2) = Zzv (| + d(1-e-21) -e -20--ee--
+e +
2-0-2
(z)2
16-
PY [z)z x 21-- 2/
2 (2)
20
of (2js X e 201--21/3)
In particular, we obtain that the second term bounded and that the first term diverges to infinity making the overall bound of Agapiou et all [017 vacuous.
21

---

C Proof of Proposition g
Before starting the proof, we recall the following identities. Proposition 11 (Tweedie's ss formulas) Denoting PY the density of the forward process X, initialized at u H and Yt (0,, (1 =-²()a), it holds for all E Rd that
edd Lsle (ee-V((e-X)))
p. (z)
(23)
Zv
that
E Y,e Vi( (())))))e))
Vlog(p))
(24)
(1 e1-e-2))1 2 1 V((= v((=- x()et]]
and that
E|Y,Y, e
V(((=-))))
Ia
(1 - - =
2 log(p))
(1
212
(25)
(V log (p) (z) (z))) log (p) (2))
Proof.
Recall that p the law of the variable
= Xo B1-e-2t
with Xo pu and Bg the standard Brownian motion evaluated at time Hence, using Bayes formula, we have
1
Ils-ze- 212 20 21 V(rr)
(2) - pc(2(=)dpo(=)- E
dx.
After taking the logarithm and differentiating with respect to we obtain
1s-ze 21-0 e dr
(p)((p)))) Jgr - (2 xc ')e
so 42 21-e-21 e dx
(1- fax
To obtain the Hessian, we differentiate the formula above. The Jacobian of the numerator given by
- Is / E 20 2) e -V(x) dx + 1- 1-e-2t 2- Jgd
1a-ne-ty
1
/ (a (3- xe () xe 1)
-1a- 1a= 20 c 222 e vx, dx,
from which we can deduce
le-se-t12
(1 ---e- e-2 + Ska xe 2)2 De "T 211 2t c v dr
Is
2 log
11s-0e 20-1- 21
112
(1 (1- Jax
e v(x
21-12
12-
(gga(z xe ")e 20-0-2 e V(a) do) xe t)
201-0-21 e e-V(x)
(1-e (1)2-2 12-10-112
21- 21) e
12-
Ia
Ska(s - xe ((= - xe- TT 20-0 25 e
(ix) dr
(1 e 2-2
lee se t1e
(1 2222 fax 20-0 26 e- v(x)
log (=)) (o))
In order to rewrite the quantities above as expectations, we make the change of variable 2e2e so that x = (z y)e* and we obtain for the density p\
pa (z) = Rdd
Ele v((=-X))e))]
Zy
22

---

where Y, ~ Ia(1 - 2)). Conversely, the score rewrites as
LB|-Y,e Y,e
V (((=
(()=)))))f)
(z) - 21
V(1 ((e-v x
and the Hessian rewrites as
E| (((2 (()))))))
la
2 (x)
-(V (=))
(1 (1-6- 21) e ([(2 (2-Y\)eet)
Ye)et)]
(1 2-2
For the rest of the proof we shall drop the dependence in and write S,,n (2)
N with the empirical
D
numerator Ñ Di-i vie (a-o))) and denominator D Σ c- (=e((=)))) where recall 1-e-2e
(0, (1 e In the following proposition, we explicitly compute the variances of N and D using the formulas above. In what follows, we shall denote N E[N] and D E[D] Proposition 12 (Variance of estimators) Let yI,..., -y ii.d. distributed as NO, (1 - e Denote by a standard normal density, and by (2) and (22) the numerator and denominator of the estimator defined Eq. D We have:
B[J N11]] < vi Zove-ta td
(ol A (log(T)(=)
e-2 + (ooo(pp
n
DI1D-D1111 P.V (2)
7
Proof. For the numerator, we have
N 1 y:C V((=-0:)ee)
e-e-2t +N,
hence, since the ye, == 1, ......
i.dd distributed as Y NOO - (a)))
1 E
Yec V((a=Y)ee)
|
| 2V2
E[Jl NIP
N(2))
S E
c-e
(1 2022
Taking in the trace in the log hessian identity in Proposition I yields
E
Yell 2e 2V((==
= (Alog(p?")
A log( π
1 e + V log log 24
Pi 2V Zove td
(1 20)2
Similarly, we have
D D-D= V((=-9))e') D,
1=1
hence we get using again Proposition I
(zvz (26)
=((D-)) (Ble 2V((=-X)oo) - E(e -2((==>\)o))pp)
n
We can now prove Proposition
Proof. Define the event A - 2 n) ( S <||]] to be chosen later. We start to decompose the quadratic error as:
where 7) S 1, 2
are positive scalars
2
2
N
N
N
Ñ
N
E
=
+A
E
1
D
D
D
D
D
23

---

We now separately analyze the first and the second term. For the first term, define
0: R x R +
R _ 2v H
(z.p)
p D
The gradient and Hessian of 0 are given by
v0(z.p) -2
N
1 2
(g
D
p2
- )T
v20(c,p)=
7 nd
22z
D
N
-3
+ 2 1
We thus make a Taylor expansion of order of 0(N, D) around (N, D): there exists (a random)
E [0, 1] such that
O - D) D)T - -,,
- N, - T)T('((NN D,(NN - -N, -D.
where we denoted N₂ = iÑ + (1 - N) and Dj = id + (1 - (1- The two first terms in the expansion are null and we are left with
O(N, D) = D
- -112 2 2( Dj
D.N. - NN)N D))
+
3
2 N
)
N
( (k-D)²
Di
N;
N
N
| 1)
(6- (b-D)}
<
| - 21I2 + 2112
-D -NII- - +
3
+ 2
D3
Dj
D3
Dj
Hence, almost surely over A
N
N
< 1
+ 6x N (IN-
I - - NIII +
K n7
(D D)²
D
D
D2
"
D
D
Hence, after taking the expectation and applying Cauchy-Schward we obtain
Ñ
N
6x
N
E
LA S D2
(EIIL N +
D
D
7
D
NNN
2
+5
E(( D)?1)
D
Now recall that D = p. Zye-td td and that N
V log which, combined with Proposition P
yields for the first term:
E 1 [1
V. Zoveld
(Alo((??))
A log(TT)
1 20 + 1|I (11)
D2
(7 (2
for the second term:
IN-IDD---
I
<
6kpty 2V Zzv cld
V Vlog(bb') !11
A (oog(1??)) 2
A Alog(T))
e-2r + |/V log log(2?") ( 11) 1/2
3 D
D
1p" (p) )2 Zz 1m
and for the last term:
2
2
5x²p?y Zeve"d
5
D
2 D
K
(D- 1D)
<
) )2(2v) 1
1 log(p)))
24

---

Hence we finally obtain
Ñ
N
2
Pt T naf Zr) (0 (Vlo((())))) || Aog
A log(TT)
1/2
LA
+ | log 2 1|?]
D
- e--2
A log(T))
(0()) | log(
+ A llgg(p?")
+6
1 e-e
(27)
Let us now handle the quadratic error of the estimator on the complementary A. We have, using Young's inequality aa
b1l 2(1|a|| + [[6]1)),
N D
N D
max; |1//: 1 a (1 - (1-e-21j3 21)2
1 A
S 2
P(A) + 2E
D
Now, recall that X; = 11:::12(1 - 2 -1 are n independent variables such that for all i, X; (d). Using Hölder inequality for some 2 1, the second term can be upper-bounded as
max; |13: 1|2
E
1
E E/max (PPp)PP(A))
(1 - 11----213
e 2t
1
<
(PP(
2 n (d ( 2A)
where we used in the penultimate inequality that the max is smaller than the sum, and in the last one that [[[X]] II. (d + 2i) when X₁ ~ (d) combined with the fact that the geometric mean is lower than the arithmetic mean.
We now upper bound the probability of the event À = (D < <nD) > Nl( By Cheby- shev's 's inequality, using 17 < 1, it holds that
E D - D 2 1)2
pt Zzveld
P(D < DD) -
S
n(p) ) 1)2 = n(n 1)2
Similarly, recalling that ||A1|| = D V log (p) 1l, we have
E|J 2 1)2
P[[| || > x||
U
A log(T) 2 + | log (og(p)) (13)
A log(p?")
V log (p) [1=( - 1)2
We now make disjunction of cases: if V log 2 1, we pick r 1/2 and n. 3/2 so we recover
SU
A Alog(T)
E
1 A
A log (pg 2
1 e-2 + 2/ log ) 11?
D
D
71
+
n
1/(pd + 2p)
TSU (llg(o?"))
A log(())
- e e--2 + | lo
+1) 1-1/p (1)
1 1-
80
A log((T)
$
A A (
+ + log (p.
) )12
2-22
n
n 1/p + 2p)
8U Aolo(
A log(T))
+ IV 112 +1) +
1 --
1 - ----2 2t
We thus pick = log(n) (n) to get
2
Ñ
N
16e² (d + 2 log(n))
(Alog(p?")
A log(T))
+ V log )12 +1) +1
1
D
D
n(1
e 21
e e-21
25

---

Combining this with the bound Eq. 27 eventually yields
8² S n11 - e
32c² 11-+2logg ll)(n))
(Alog(pf")
A (og
+ V log((p)) VVV )12 +1) +
1 e e-2 26
where we used the inequality
A log(TT)
+ | log (pt ( [12 1/2
I log Alog(p?")
e e-2
1 | log( log(())) A log (pg
A (T)
2r + V log log(pt (1)
In the case where
/ log(p:))l
< 1, we instead pick 1 = 1/2 and A: = 1 + 2 (ox())()
We obtain
that
P(A) v
4U
A lpg
A Alog(T)
+ 1/V )p 112 +1)
and as previously, for = log(n) we get
2 16 (d + (1)((n))
U (Alog(u7")
A log((T)
+ | log(p))) 112 11)
1 A
+
D
n( 2-22)
e-22 2
For this choice of K. the bound on A becomes
N
N
AU (6 log
A log(T)
1/2
A log(m)) (T)
A
V log 2V )
+
log
1 - c 2 +
D
n
e 21
4U (7(Alog(p3")
A log(T)
(P )12 ((+1))
+ 66166[11og) log
n
2
Thus, we obtain as previously
83 32c d + 2 log((n)
U (Alog(E?")
A log(m))
V log(p!)) log(( 112 11 +1
n11 21)
D Proof of Proposition 6 and Lemma 8
Before starting the proofs, we recall the following usefull lemma that bounds the second order moment of dissipative distributions.
Lemma 13 Let V be such that (VV(z), x) 2 a||z||2 b. Then for μ e V denoting m2 the
second moment of μ, it holds that m2
bid
Proof. Define the Laplacian of μ as L(f) = - (VV, Vf) for sufficiently smooth. By integra- tion by parts, it holds that
I (()())d)(x)) = 0.
In particular, for f(x) ||=|2, we recover ((VV(a), vf(x))du(z) 2d. For V dissipative, implies
af [lllddu())) < 2d
equivalently m2 < (b+ 2d)/a.
26

---

D.1
Proof of Lemma 8
Proof. The first inequality was shown in the Lemma above. For the Fisher information, it holds that
I(u, m) / -VV(z) - =l12d)(xx)
2 /
+ 2m2,
2 AVdu(z) 2m2
- 23d + 2m2
There remains to lower-bound (0).. Denote x² global minimizer of V. By dissipativity, it must hold that || 2|2 S b/a. Now observe that
V(x*) v(0) L.' (x (=') )x"" S $||==1|3
Combined with the fact that for all E Rd, it holds that V(x) V(a*) 2 0, be recover that V(x) - V(0) 2 - |x1 112 2 - Bbba. a. Furthermore, for < 5 < 1, we have
-xx)-v(0) ! (VV(tz),
(VV(Lz), + V(6x) - V(O),
2 (vV(tz), ta) tdt -b/a.
at||>|1 - b/tdt - 3b/aa
=a| a||x|13/2 ad² |>||| /2 + blog(o) -Bb/a.
In particular, for d = 1/v2, we obtain
V(z) - (0) 2 a||=|1 6B/a + 22g(2)/2))
Hence, we have
-v((
m00)=
e V(zldr
] Te- V(-
a a|xl (1
Since 3/a 2 and log(2)/2 1, we recover that log (0) < 43b/ ad + 2 log(2/a).
D.2 Proof of Proposition
Recall that the intermediate scores read
pr. [Y] (pg (2) e e
2 In particular, if V is dissipative with constant a, b then it holds
with We.s (x) x (oo) 20-c that
21 xx) (-Vlo((g:>) = + (e feexx== x 2)
2 a|| b+ -2 (E (|101 (2,x)))
27

---

Now recall that e -=||==1| - (2,x) 2 -2211 which yields
V (og(((.))())) 2 |||=| 2 (b + ||=1 - -)))-
Hence, using Lemma R it holds that
2b + / - c 2) +d
B [|
Hence we recover that
2||2112
2e 2e-2(E, 4t. |||1
V (ogg()))
5 (1 e- 2-2
e 2012
2 2|
e. e-21 21
22(2 + d)
||=11
$ (1 e 21y2
(1 c 2122
a
(1 e 21 20
|
c 2-2
2e 21 22b d)
2 +
(1 2222
a(1
e 21)
a(1 e 2-12
Similarly, recall that
2-2
Covqr. (X) It
(olg(p)) V2 (0g((T)(2)
1 e e- 21
e
from which we can deduce A log(
-I-c-211²
2-
By
|||]
which yields again
-2
|| 1
2b d
A log(p?
2a(1 (1 (1-e 2-22
212 a
E Proof of Lemma 7
Before starting the proof, we recall the result of Mikulmeer and Shenteld [2025]]
Proposition 14 Let μ be 3-semi-log -osmi-log--oovex probability distribution. Then, denoting P the distri- bution of the forward process in Eq. 0 and x the density of the standard Gaussian, holds for all z E IRd that
(3 - 1)e
V lo)(T)())) V log(p)) 1 (1-e-21) 1) +
la.
(28)
Proof. Define the Ornstein- Uhlenbeck semi-group Qt as
Qc(9)(z)= / g(ze + + VI- e-- 1u12 (2T) dd/2 ddydd
1
/
1u- gluje
20---211 (2 d/2 du. d/udus
for all function g integrable w.r.t. the standard Gaussian measure. Taking 9 as f = standard Gaussian, we obtain that
du
with the
de
1
f V(w)e 1n12 lu-e 2 2010 25 du
Qr(((=)= Zv ZvV1 22
7vV1-e"
-
1
c
v(m) L 1- - 1u]
241 21
du
1
V(u)
- - 111
2(1 211---11 du
Zvv1 - -
1012
/
c Vv(i
20- du.
ZvVI-e-
In particular, we remark that V Vlog(Q.())
(p
V log(#). Now, the quantity
V (og((:(()) was studied in Mikulincer and Shenteld [2023]] and they prove in Lemma 5 that for all
(1- -3)---1 -1
2 log(Ce(()()))
(1- 1) + La
28

---

which is equivalent to
(3 1)E (1 (1- 1) + La
V (z)( - v² log(p!)
Before proving Lemma introduce this preliminary result on the evolution of dz..
Lemma 15 (Evolution of the ratio) Let I. >> O, it holds that
0 2, 2x) (V (),: V log(m)) + + 2(V log(p!)) V Vlog(
Proof. Recall that the log-density (p evolves as
O, log())) A log(p!) + | log(p) ) Vlog(=)) Alg((T).
Hence, we deduce that log( (b) evolves as
a log( = A log +.) (V (.), V log(T)) + log (1 Vogg (p!
The difference of quadratic terms can be expressed as
V log (pt 2V I|( || log (pl ||2 = V log (b,) + V (pg -
| 1 )12
V log hb,) || 2( log lo
V log +.))
which allows recover 0 log( = A log(2,) - (V ()), V Vlg((T)) + V llg((,))11 + log(p)) V (g)()))).
We now provide the proof of Lemma
M
Proof. Until the rest of the proof, the dependence on of the integrand shall be implied unless expressed explicitly. We start by differentiating mo mo())) with respect to l:
0ymo(4)) = / 0, 0,
/ Φ (A logg( (.) WVog((F)) (F.); V log(m)) | (1)) 2(V log(p!)) llog(:))) dz,
where we used Lemma to compute Pr Using integration by parts, the first term reads
f L log( dz - (v V (o)(()))dz= = - del V loo((())))
hence the first and the third terms cancel and we recover
log(r))) Vor)dz / (V log(T)) V0,)d2. Using integration by parts again, we recover
Dano (+.)
/ A Alog(T) - / log 2,dz
O ):)
= 2 / (Alog(()) - A log ) - / log(
dmp( + 2 (Alog(T) Aog )
Using Proposition 14, since is 3-seem--oo---cooeee the term (A log(T)) - A Alog(p!)) can be upper-
bounded uniformly by [I-e [1-e-*)3--FF we eventually get
d(g d(8-1)e-24
(1
2(3 - 1)e 2t
2t
0m))(4)) < d
(1 (1-e-21) 1 +
29

---

Hence we can use Gronwall's 's lemma which yields
m) I mo (Po) exp ( ( (1
2(3 1)c 20
(1-6-2))(6 - -1) ds
Denoting by Zv (resp. Zzv) the normalizing constant of ee (resp. e -2 the term mo (o) reads
mo ( = /
Po Pd
v
Zv
/
e-V(=) de (Zv)²
2V(x)
Zzv
Zzv
Finally, let us compute the integral above. Making the change of variable u = = 1) we have du -2 1)e ds which yields
2/8 1)c-2
(8- (0-1)e-21
1
ds
du
(1 1 (1- - 1) +
B - u
9-1
[log(3 - w)) (8-1)e 1)c
11-1
log (3 (3 1)e 21)
log log( e c2) e-20)
Hence recover
edd (Zv)² Zzv
mo (+.) S
(8(1 - 2- + 2-2ad
In order to recover a bound on the second moment of t; we need several intermediate results. We first prove that the maximum of the ratio decreases through time.
Lemma 16 (Decrease of the maximum of b) The maximum of the ratio c; decreases with t.
Proof. Let 2t be a point where i; attains its maximum and denote Mr log(Dr)(z1). By implicit function theorem, 2 is differentiable hence
compute M,M,
0, M = 0 log(( (z)) + (0.z,, v Vlog(4))(z.))
A log( (2))
Since z is a maximum, we have in particular A log (2x) < which implies that M, decreases.
We then derive an upper-bound on the maximum of log-smooth distribution. Proposition 17 (Upper-bound of the maximum) If i is 9-semi-log-convex then holds that du
as
8
2
Proof. Recall that the density of μ can re-written as
dp (V(())) dz I (V(=)
where V. the minimum of V attained for some 2.. By definition e (V(=)-V)) < for z. Further- more, since V verifies V2V BTa, we ensured that
v(z) V. < 2
2
which implies in particular that
1
(v
v.)
2
Using the previous result, we can derive upper-boute bouud- the integrated squared gradient 0.
30

---

Lemma 18 (Upper-bound integrated gradient) Let & e-V be 3-semi-log-comer convex measure. De- noting (0) the density of μ with respect the Lebesgue measure at 0, holds that
L. (ooo(()))))(0))) S llog (m(00) + log
3 2T
Proof. Denoting x the density of the standard d dimensional Gaussian, recall that the density p.
evolves
a.py =V (El log xx) ))
which can also be re- ce-written as
App
O, log(p!)
(V (ogg(p)) ) V Vlog(T)) - A log(T)
pi
A log (pl) + log || (V ) v Vlog(=)) A Alog(T).
In particular, for = 0 this yields
O log (p) (0) A log(r))) + | |V -o)
which implies
L | log logg ( -ogg())))))) / log( (0) A log(p) ( (0)ds.
Using the uniform upper-bound of Proposition 44, the second term can upper-bounded as
! A (0) A log (p. (0)ds (ogg
(3 - 1)e 1)e-2s
< d
/
ds
2x 1)
(3 - 1) f'
1
Ja B - u(B du
log ((1 21 + 21)
Furthermore, Proposition 14 shows that - 2 log (p,))
3[1 311---2 ---2- Thus, using Proposition 3
I7. recover that log (p)) s _ log
(311---23te-2
d log log((T)) ). In partieular, recover
du dr
d
d 2 log(2x).
|
- loog
(0)
log(
We can now bound the first order moment of 4 Lemma 19 Let be a B-semi-log-come convex measure with finite second moment m2. holds that
(Zv)² ((++1) (B(1-e -e 20d (vm / -og (m(0)) d
mi mi(4)) (2.) s
+ 22
Zav
Proof. We differentiate m1 (D,) and we recover
0,m1 (#.) = / de (Alog( 2b) (V log(#)), V log(TT) VVog( +2()))))222)))) (VVoo(p)) V /log(4;))) ||
Integration by parts of the first term yields
/ - log( 2 [[)
- / /
(V4,, |||||
dz
hence the squared gradients terms cancel and we recover
@m,)(1)) / (2V (o - log(z), v /
|>|| dz.
31

---

Let us denote by A the first term above. Integration by parts yields:
1 (T) 24 log (p. (p! + / 8 (V)g((T) - 2V log log(p!) 2
A =
|| )dz
/ d.A 2 / (0)(()) - A (og ||==|d=
/ Dr (,.VVog((T)
|= dz + 2 f @ - v (og( ) ||| ydz
2
2
= (d + 1)m1 (b)) + $.(A log(z) log
||==]|d ) + 2 / T, (.(VVlo((T) - -Vlo(=))))))((())
2 dzz
||]||
Using the upper bound given in Proposition I we get 2 f th A log(T) A log (1l 5
(B-1)e 20
2d ()-- 2041 m1 m1(1)). (L.). Similarly, we re-write the second term as
2 3 ( log(TT) - (olg( 2 ydz = 2 / t (Vlog log
π (z) - V log
π
(0),
2
dz
||2||
v
|||||
P
Pt
+ 2 ʃ 1e( V log
π
(0): ||=||
dz
(3 1)e 21
< 2m (+.)
(3 1)(1 c 21) +1 + + log (0)) (m) (
Let us now handle the term B - -- J[V
T In one dimension, B = -0) S max( (b,)
and for d 2 2, we have
l1 -
1) dz
B
||||
1)
(,(d - 1) ||:||
dz +
dz
||
Bn
Bn
d
< max(
de
+
ma ( (1))
BR
||:||
R
d/2
d -
max($.))
Rd-1
mo (Pp)
T(d/2)
R
Using Lemma 1A and Proposition 17, we have that max( S max (0)) = [2v]² (Zv)² Zov
max dz <
-Zav
8 d/22 Hence, if we pick R (Zaymo(2:) 1/d g 8-1/221/2-1/6 we get as an upper-bound for B:
27
B 3 d
2 (
Zzv
27
<
Zev
In particular, we recover that
0. (..) S (d+ 1) (1 (1+2 2 (8- 1)e- 2t
(8- 1)( e 222 +1 mi (4.)
22%
+ 2//VVlog ( (0))lmm (F.) +
v //dlmmo (B)(m(()))22//23)) (29)
Zzv
hence using Gronwall lemma, we have that mi (b))= $ ((d+1) (3(1 -e -e- --22 + e 22 -22dd+1 d+1 f (F))
+2 %/ | (1Vlog(22) x ) (0) (Φ.) +
c((+t)) - 21 + 221dd4 ds.
c3(4t) 20) + e-23jo+1
32

---

Using Lemma we have that mo( S
Rz Zzv
edd (3(1 -e 22) + te- 20yd hence the first term of the
integral is upper-bounded as:
(p.) (0)1
Z
!
(3(1- + e 20)ddt ds I
[Vlog(p')
ds
Z2v
3(1 - E 20) + 22
By Cauchy-Schwarr it holds that
V log( (og()) L(1 - 20 ds V V.
J.
e-2s (3(1 - 20) + e e-23 ds.
[Vlogo
V
The integral term is given by
L'
2s (8(1 e 25) + 2-202
1
ds
du
2 e-
(3(1 u) + u)²
1
2(1 3)
8(1 1) +
+ c 1)
2(1 B) 3(1 e 21)
1 c 21
2 21) + 20-
Similarly,
L. mo(())) 111
(8(1 e 20) + 20 ds 1 /// (3(1 E 20
e ((( 1)
e c-2s
+ 2-00 2003 ds
1 e 21
2(3(1 - E 22) + c 21)
Hence, we obtain
Zzv
B
mi (.,) < e (dd-1)
7zv
20gdt1
?
m1 m1 (8n) + V
2 2log(u(0)) + dloog
2T
+
d3
Finally, my (+)))
(Zv)²
[|1|2||
c vv
dz
(Zv)² Zav
Vmz((u).
Zzv
vas
We can now derive our upper-bound on m2 (2.).
Proof. We start by differentiating m2(
0,mz (b.)=
/ ||=]P(div - (Vo,, Vlo((T)) + +(VVlog()))) VD.,)
/ 2(2, vo,jd2 / (Alog(m) 24 log 2 2 / (V Vog((m) - 2log(p)) )) h1de
2 / Alog(T) - / (lgg(T)]ll|/ - / (V 2)
+2 / (Alog(T) A log (pl ())")))))) ||| 22 + 4 / (V log(T) v log(p!) 2) 2,
= 2dmo + (2)) + (4.)
+ / (Alog(T) A log ( ||1=11 + / (Vlog(T) Vlog(p)) 2)) 2,dz.
33

---

The first term (o)))(()) A log )|===| is upper-bounded by (I-e 20(3-110 1)+1 dmy (b,) and for the second term we have
(B-1)e
f V log(<)) Vlog(p))) 2)
VVlog
π (2) V Vlog
π
2),,
p/
p
V log
π
(0), 2) 0,d=
(1 - c 21 (B 1) 1 D,dz + || logg(p")) / 112l
(L 1)e 2t
(3 - 1)e-2
(1 c (B 1) m2( + V (og())))
Hence we recover
2(3 1)e 22
(.))( S (d+2)
1+
(1 (1-63 21 - 11
We now use the Gronwall lemma to obtain
m2( v (3(1- + - m2( + /-2 e=-ldd=2) (2m (0x ( log + dmo((
ds
(8(1 2 20) + 2x)((++))
Recalling the upper-bound m1 (0((9) (b)) I ( - 2-2) + e e-21jd+1 C where C' is defined in
Lemma 19 we upper-bound the integral term as
e =( (2.)l (p))
ds S C
V Log(p") (0)]lds
(8(1 - 20) + 20)(42))
3(1 20 + 20) J0
e 2-2
<c/
V lolo (pl (0))
(3(1 - 2-2) + 2
1 1-e-21
CV
| log (p. (0)]/2d.
2
Similarly,
e (dd(2)
e 2s
(3(1 e 20) 20) mo )ds <
Jo (8(1 25) + e 20
- c
Hence we recover that
3
m2( - (3d+)) - -21d0+ m2((0) + 20,
-2 log (u((0) + d dlog
+ d
2x
Using the expression of C, we recover eventually that
m2(4))) < 2c zz 22) m2(()) + d(3 + 1) 4log (n(0)) + 2d log
B
Zzv
2T
F
Proof of Theorem g
Proof. As Proposition G shows, the average error of the estimator can be upper- bounded as
dlog(n)e Zev 2V
(2) ||
+ d
E (1, (z)(2
+
na(Zv) (2 ( (z))²
(1 10-e-21p4
(1 - E 20
34

---

Hence, the average integrated error reads
Blʃ [1 log( (z)
dB6+2 log (o na - 2-
mz (0,)2())))))) (. (dd+)) (Zv)²
Zov + d)mo (
(30)
(Zv)²
We then apply the upper-bounds in Lemma and in Lemma and we recover
BI 5 [|).a(2) V (oog(p)) x
d3d+3 log(n)e2(44)))) (b++)
na 2-21)4
We thus (og(1/c) that
d
,--)) 22(+11)) and we eventually get for $ 1 S
B f |1 (z) - log (=)l S
eBd+3
a²
Hence, plugging again the bounds of Lemma R in Theorem recover the desired result.
35

---

NeurIPS Paper Checklist
The checklist designed to encourage best practices for responsible machine learning research, ad- dressing 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 is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (12 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 it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to the checklist one of the factors in their evalu- ation. While "[Yes] generally preferable to "[No] is perfectly acceptable to answer "[No] provided 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 "[No]" "[NA] not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification elaborate, All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point 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 Check- list",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: the abstract and introduction list our contributions, i.e. novel complexity guarantees for sampling algorithm that simulates a time-reversed diffusion with a specific estimator of the intermediate scores.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be 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 to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
36

---

Answer: [Yes]
Justification: we discuss the limitations of our theoretical results in the Related Work sec- tion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed the paper.
The authors are encouraged to create a separate "Limitations" section 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 au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to 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 their approach ad- dress problems of privacy and fairness.
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 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 thcoretical result, does the paper provide the full set of asssmmptioss and complete (and correct) proof?
Answer: (Yss]
For each theoretical result, we worked with justified assumptions, making all the dependencies of the problem clear. We provide clear and detailed proofs in the appendix.
Justification:
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 or referenced in the statement of any theo- rems.
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 to provide intuition.
Inversely, any informal proof provided the core of the paper should comple- mented by formal proofs provided in appendix 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 experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
37

---

Answer: [Yes]
Justification: Our experiments are simple and illustrative of our theory. We provide details how reproduce them.
Guidelines:
The answer NA means that the paper does not include experiments.
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 a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 it 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, other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing 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: [NA]
Justification:
our experiments are illustrative, we do not use specific datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.com cc/
Pub ic/ qui des. CooeSuumm ssi oonooliccccc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.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 NeurIPS code and data submission guidelines (ittps: //ipss.cm cc/
cttp:///ui..ees/ooeeubbmm..m isi oonoolicy 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.
38

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
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]
Justification: our experiments are simple and detail their setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: our experiments illustrate a theoretical result on the convergence rate of an algorithm. The goal not investigate the stochasticity of results across different runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, 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
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.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If 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 to reproduce the experiments?
Question:
Answer: [Yes]
39

---

Justification: Our experiments are simple. We detail how long they take to run on local computer.
Guidelines:
The answer NA means that the paper does not include experiments.
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 of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://s//aaarpp...o///raaataate
Answer: [Yes]
Justification: In opinion, this paper does not address societal impact directly, and con- siders the generic problem of sampling from a distribution.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a 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: In opinion the paper does not have direct positive or negative social im- pact.
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 (c.g., deployment of technologies that could make decisions that unfairly impact spe- cific 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 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 mitiga- tion 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).
40

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not present such risks.
Guidelines:
The answer NA means that the paper poses 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 re- quiring that users adhere usage guidelines restrictions 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 not 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 (e.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 coded our our own experiments that are illustrative of our theoretical result.
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 or dataset.
The authors should state which version of the asset is used and, if 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 use in the package should provided. For popular datasets, paperswithcomm com/ datasetaa has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
we document the setup of our experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
41

---

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 anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per 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 experiments not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contri- bution 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, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe 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 institution) were obtained?
Answer: [NA]
Justification: our study does not involve risk for participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) 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 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not part of this research project.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy ftttps://neurs /ttp://s////eeeaoeo.o/////ottter wwt..c/nneeenece//220..... 2025/ (.T)) for what should should not be described.
42


Reviews:
[{"review_id": "mFOdNKVzZ5", "reviewer": "Reviewer_sQu7", "summary": "This paper tackles the problem of (approximate) sampling from high-dimensional multi-modal distributions. Multi modality is a common feature of most real-world distributions. In general the problem is known to be computationally intractable, and there are various techniques to speed up sampling that exploit some or the other regularity in the problem description. For multi-modal distributions, polynomial time algorithms are not yet known for situations where there are many unknown modes, and the distribution does not follow extremely stringent smoothness conditions, and if the parameters are not explicitly known. \n\nThis paper presents the first algorithm that is able to sample from a class of high-dim. multi-modal distributions that includes Gaussian mixtures, among others. The key idea lies in the use of semi-log-convexity, a relaxation of log-convexity that has some desirable properties. One of which is that a mixture of semi-log-convex densities remains so. \n\nThe algorithm uses this for estimating the intermediate score functions required in a reverse diffusion process. Previous methods for score estimation required sampling from a complex distribution, and this paper presents a new way to estimate using ratio of expectations, where both expectations are taken with respect to a simple Gaussian distribution, and are bounded. This combination allows for a polynomial runtime in fixed dimensions. The runtime is exponential in the number of dimensions.", "questions": "NA", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:-\n1) The paper is generally well written, and the extensive background material is very helpful to understand the paper. \n\n2) The proposed method seems to be novel, and the insights might extend to the broader field of sampling. \n\nWeakness:-\n1) Although the paper is mostly of theoretical interest, there are a few illustrative experimental results. I notice that the proposed algorithm, which takes ~1 minute, is significantly faster than the state-of-the-art for the chosen problem. It would have been interesting to see what the algorithm is NOT able to deal with. This might be useful for future research, and also for practitioners when they implement a sampler.", "was_revised": true, "final_justification": "I think the rating is appropriate for the paper.", "rebuttal": "**Contributions and future work** --- We appreciate the reviewer’s positive assessment. Time-reversed diffusions have significantly impacted sample generation from multi-modal distributions, and we believe this work offers a timely contribution by providing a strong theoretical foundation for their use to sampling from unnormalized densities. In response to the reviewer’s comment, interesting future directions include developing theoretical guarantees for multi-modal distributions with non-Gaussian tails."}, {"review_id": "IHEvrv2YgA", "reviewer": "Reviewer_uDVT", "summary": "This paper proposes a novel sampling algorithm specifically designed to operate efficiently in scenarios involving multi-modal distributions, which are typically challenging for standard sampling methods. In addition to the algorithmic contribution, the paper provides rigorous theoretical analysis, offering formal guarantees on the performance and convergence of the proposed method.", "questions": "Besides the questions mentioned in **Weakness**, there are also several issues.\n\n1. Are there some extension methods which can remove the constrain on dimension? \n2. And also, are there some numerical experiments or real world applications to verify the performance of the proposed algorithm?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**\n1. The paper provides a clear motivation and presents a well-articulated problem statement that effectively frames the research contribution.\n2. The theoretical analysis is thorough, with detailed interpretations and carefully explained assumptions that support the proposed methodology.\n3. The proof sketches are clearly written, making the key steps of the theoretical development easy to follow.\n\n**Weakness**\n1. The information presented in Figure 1 is somewhat confusing. It would be helpful if the authors could provide additional explanation. Specifically, the meaning of the \"dark regime\" and \"bright regime\" should be clarified to enhance the reader's understanding.\n2. The experimental validation is lacked. It would strengthen the paper to include experiments that directly verify the theoretical results and further demonstrate the practical applicability of the proposed method.\n3. The organization of the paper could be improved. Currently, the introduction presents complex notations that are not fully explained until later, which makes it difficult to follow the story. It may be beneficial to provide some preliminary definitions, notations, or a notation table before Section 3, so that readers can better grasp the main theorem and the subsequent technical content.", "was_revised": true, "final_justification": "They addressed my questions, especially on both empirical validation and data dimension constrain, and I have no further questions. So I prefer to keep the positive score 4.", "rebuttal": "We thank the reviewer for his careful review and positive comments on our paper.\n\n**Clarifications in the text** --- thank you for picking up on these. We will clarify the caption of Figure 1 with the following explanation. The color scheme indicates the probability density value of the distribution we want to sample from (dark is low probability density, bright is high probability). The blue dots are the samples produced by our algorithm. We will also regroup notations in a paragraph of table as suggested by the reviewer. \n\n**Experimental validation** --- our paper aims to provide strong theoretical guarantees for sampling using time-reversed diffusions. Related works have been published at this venue and similar venues without experimental results [1,2,3,4], as the primary contribution is theoretical. Figure 1 is intended as a visual aid to support the theory. That being said, we ran an experiment that was suggested by reviewer 29WY. The distribution to sample is a 2D mixture of three Gaussians with equal weights $1/3$, equidistant modes  located at a distance $R$ from the origin, and different covariances $(\\mathrm{Id}, \\mathrm{Id}/2, \\mathrm{Id}/4)$. We compare convergence in Wasserstein distance between ULA, RDMC, and our algorithm. As expected, \nas the between-mode distance grows with $R$, our algorithm yields much lower error than ULA and RDMC. \n\n|  Between-mode distance R    |  Error of ULA  | Error of RDMC | Error of our algorithm |\n|:------:|:-----:|:-----:|:-------------:|\n|  1.00  | 0.26  | 1.04  |     0.35      |\n|  3.11  | 0.42  | 3.17  |     0.64      |\n|  5.22  | 4.89  | 6.39  |     0.97      |\n|  7.33  | 8.69  | 9.70  |     1.26      |\n|  9.44  | 12.36 | 12.92 |     2.25      |\n| 11.56  | 16.09 | 16.68 |     3.63      |\n| 13.67  | 18.59 | 19.13 |     5.57      |\n| 15.78  | 21.58 | 22.08 |     3.36      |\n| 17.89  | 23.86 | 24.36 |     3.29      |\n| 20.00  | 28.19 | 28.63 |     4.74      |\n\n**Removing the constraint on the dimension** --- As was stated in our introduction, the exponential dependence in the dimension *cannot* be avoided under our hypotheses because of existing lower-bounds [5,6]. Intuitively, this is because finding the modes of the target distribution would require exploring the entire space, and that search problem grows exponentially with the dimensionality. Our results surprisingly show that, unlike many sampling algorithms, the exponential complexity is *only in the dimension, not in the other parameters* (e.g. smoothness) of the distribution. \n\n[1] Chen et al., *Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions*, ICLR 2023. \n\n[2] Lee et al., *Convergence for score-based generative modeling with polynomial complexity*, NeurIPS 2022. \n\n[3] Conforti et al., *KL Convergence Guarantees for Score Diffusion Models under Minimal Data Assumptions*, SIAM 2025. \n\n[4] Chen et al., *Learning general Gaussian mixtures with efficient score matching*, Arxiv 2024 \n\n[5] Lee et al., *Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo*, NeurIPS 2018 \n\n[6] Chak, *On theoretical guarantees and a blessing of dimensionality for nonconvex sampling*, Arxiv 2024"}, {"review_id": "7CEexUwQOT", "reviewer": "Reviewer_29WY", "summary": "This paper proposes an approach to sampling from unnormalised density functions.\nIn a nutshell, the sampler starts from a Gaussian initialisation, and denoises along the time-reverse SDE. \nTo estimate the score, the author proposed to use self-normalised importance sampler using a Gaussian as the proposal.\nIt shows that this approach has polynomial time complexity in target parameters and can address some limitations that previous works have.", "questions": "1. Regarding Fig 1. How do you initialise the Langevin for RDMC? How many steps you use? It is very surprising to me that RDMC failed at this simple 2D problem. I have played around with similar ideas and algorithms before, but they work very well for simple GMMs in a reasonably high dimension.\n\n2. Regarding mode weight.\nAccording to my experience and also discussed in [1], the RDMC-style algorithm (no matter using Langevin or SNIS) has a problem in that it cannot estimate the mode weights accurately. This can be corrected by adding an MH corrector, as done by DiGS [1]. Can the theory reflect this?\n\n\n\n[4] Grenioux, Louis, Maxence Noble, and Marylou Gabrié. \"Improving the evaluation of samplers on multi-modal targets.\" FPI workshop @ ICLR 2025.", "limitations": "Please see Weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strength\n\n1. The motivation is clear. This paper found limitations in previous works, and addresses them by SNIS.\n\n2. The theory is solid. I did not check the correctness of all of the proof, but it looks correct to me.\n\n### Weakness\n\n1. **The proposed algorithm is a simple combination of previous works**. Using SNIS to estimate the score is not novel, leveraging the reverse-diffusion with estimated score also exists. In my opinion, the main contribution of this paper is **proving the theorical benefit of using SNIS+DSI for the score**, instead of **proposing a new sampler**.\n\n2. **There are some missing references**. For example, DiGS [1] who use the same Gaussian proposal but with MH instead of SNIS, and  they are not estimating the score, but to re-localise the particles. \nAlso, while the author cited iDEM, it does not highlight the similarity of the proposed estimator to iDEM's. In short, one can calculate the score by Denoising Score Identity or Target Score Identity, with any estimator, including SNIS, Langevin, etc. Then:\n\nDSI + SNIS -> this paper;\n\nDSI + Langevin -> RDMC;\n\nTSI + SNIS -> iDEM; \n\nTSI with DSI + SNIS -> PDDS [2];\n\nTSI with DSI + Langevin -> DiKL [3].\n\nWhile most of these papers do not analyse the complexity, they should be discussed as they use very similar estimators.\n\n\n3. **The experiments are quite toy.** I must first clarify that my primary experience and focus are on the practical side, which may not be directly relevant to this paper's main contribution. The weakness in experiments might be okay for a theoretical paper. But I still have a few concerns.\n\n - This paper only verifies the results on 2D. It is surprising to me to see RDMC fail on this simple 2D problem. I have a concern that this comparison is not fair. Please see my questions for more on this.\n\n - I feel it is helpful to change the target parameter (It's fine to do it even in 2D!) and see how the KL / TVD / or any metrics scale with this parameter, given a fixed number of energy evaluations. Or the eval number w.r.t the parameters to achieve a certain KL/TVD/any metrics.\nThis is much more convincing than just visualising one case.\n\n\n[1] Chen, Wenlin, et al. \"Diffusive gibbs sampling.\" ICML 2024.\n\n[2] Phillips, Angus, et al. \"Particle Denoising Diffusion Sampler.\" ICML 2024.\n\n[3] He, Jiajun, et al. \"Training Neural Samplers with Reverse Diffusive KL Divergence.\" AISTATS 2025.", "was_revised": true, "final_justification": "My concern has been addressed. \n\n- Why not higher:\nI feel the proposed algorithm is not strong enough on its own as a simple combination of SNIS and reverse diffusion. \n\n- Why not lower:\nMy concern has been addressed and I agree with the author the contribution of the theory is significant on its own.", "rebuttal": "**Simple combination of previous works** --- Indeed, our algorithm simply combines reverse diffusion + a self normalized estimator of the score. However, that combination having never been explored before, that makes it a new algorithm in its own right. Furthermore, we must insist that our contribution is not the algorithm in itself, which is not very hard to come up with, but rather to study its error and most importantly quantitatively prove that, in terms of query complexity, it is state-of-the-art compared to previous works as it is robust to multi-modality. \n\n**Additional references** --- we have read through the additional references and agree that they are relevant. We appreciate the reviewer's clear summary and DSI / TSI classification. We will add these references and discuss them, especially as they use estimators of the scores which is a central part of our analysis. \n\n**Toy experiment** --- The Figure 1. should not be seen as an experiment but rather as a visual illustration of the performance of our algorithm in comparison with previous works. We highlight the fact that related works have been published at this venue and similar venues without experimental results [1,2,3,4], as the primary contribution is theoretical. That being said, we ran an experiment that was suggested by the reviewer. The distribution to sample is a 2D mixture of three Gaussians with equal weights $1/3$, equidistant modes located at a distance $R$ from the origin, and different covariances $(\\mathrm{Id}, \\mathrm{Id}/2, \\mathrm{Id}/4)$. We allowed each three algorithms $10^6$ queries to the potential $V$ or to its gradient: we performed $10^6$ iterations for ULA, we used $100$ steps of reverse diffusion for our algorithm and RDMC. We used $100$ inner steps of ULA for RDMC that was initialized with a standard gaussian. We used $100$ particles for score estimation for RDMC and $10000$ for our algorithm. Finally, we generated $500$ samples for each three algorithms that we compared in Wasserstein distance to $500$ samples generated from ground truth. As expected, as the between-mode distance grows with $R$, our algorithm yields the lowest error. \n\n|   Between-mode distance R    |  Error of ULA  | Error of RDMC  | Error of our algorithm |\n|:------:|:-----:|:-----:|:-------------:|\n|  1.00  | 0.26  | 1.04  |     0.35      |\n|  3.11  | 0.42  | 3.17  |     0.64      |\n|  5.22  | 4.89  | 6.39  |     0.97      |\n|  7.33  | 8.69  | 9.70  |     1.26      |\n|  9.44  | 12.36 | 12.92 |     2.25      |\n| 11.56  | 16.09 | 16.68 |     3.63      |\n| 13.67  | 18.59 | 19.13 |     5.57      |\n| 15.78  | 21.58 | 22.08 |     3.36      |\n| 17.89  | 23.86 | 24.36 |     3.29      |\n| 20.00  | 28.19 | 28.63 |     4.74      | \n\n**Doubts on poor performance of RDMC on 2D illustration** -- It is not surprising that RDMC fails on this 2D experiment as the dimension *is not* the relevant parameter for RDMC, but rather the isoperimetric constants (Log-Sobolev and/or Poincaré) of the target. Indeed, as we explicitly state in Section 3, RDMC uses ULA to sample from $q_{t, z}(x) \\propto e^{-V(x)} e^{- \\| x e^{-t} - z \\|^2/(2 (1-e^{-2t}))}$ which is almost as hard as sampling from the target $e^{-V}$ as $t$ grows. In particular, in our example, since the target is highly multi-modal, we expect this inner step to fail when $t = O(1)$ and as a consequence, the intermediate scores $\\nabla \\log(p_t)$ will be poorly estimated. \n\n**Initialization of Langevin for RDMC** --- For RDMC, the inner Langevin step is initialized with a standard gaussian $\\mathcal{N}(0, I_2)$. While some improvements are possible [5, 6], they may require unknown parameters of the target distribution (e.g. its smoothness) and the task of sampling from a multi-modal distribution with an inner ULA step remains fundamentally difficult.\n\n**Why our illustration is in 2D** --- Our theory shows that time-reversed diffusion, when combined with a suitable SNIS score estimator, achieves polynomial query complexity *only in low dimensions*. This motivates our choice of a 2D illustration. We emphasize that the target distribution is not a \"simple 2D problem\": in the absence of prior knowledge of the mode locations, sampling is highly nontrivial. In fact, even in 1D, sampling from this unnormalized density using ULA, for instance, typically incurs exponential query complexity in its parameters (e.g. smoothness), whereas our method retains polynomial complexity.\n\n**Ability to recover mode weights** ---  as is typical in theoretical work, our guarantees are stated in terms of distributional closeness in KL divergence. Explicitly assessing the recovery of mode weights would require a different statistical divergence that is specifically sensitive to mode weights. This is unfortunately beyond the scope of our analysis as well as most of the theoretical literature, to the best of our knowledge. Nevertheless, this is an interesting question for future research. \n\n**Positioning our contribution** --- given their success, time-reversed diffusions have recently gained traction for sampling from unnormalized densities. The reviewer lists many algorithms that are \"simple combinations of previous works\" yet are still noteworthy. Our method fits this category but stands out by offering rigorous, non-asymptotic theoretical guarantees on query complexity, especially in the presence of score estimation error that we precisely quantify. Such theoretical guarantees are scarce and we believe our results are therefore a meaningful and timely contribution to the field. We hope our responses have addressed the reviewer’s concerns and that they will consider revising their score. \n\n[1] Chen et al., *Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions*, ICLR 2023. \n\n[2] Lee et al., *Convergence for score-based generative modeling with polynomial complexity*, NeurIPS 2022. \n\n[3] Conforti et al., *KL Convergence Guarantees for Score Diffusion Models under Minimal Data Assumptions*, SIAM 2025. \n\n[4] Chen et al., *Learning general Gaussian mixtures with efficient score matching*, Arxiv 2024 \n\n[5] Grenioux et al., *Stochastic Localization via Iterative Posterior Sampling*, ICML 2024 \n\n[6] Huang et al., *Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo*, COLT 2024"}, {"review_id": "mhI3898s7d", "reviewer": "Reviewer_zc68", "summary": "This paper investigates the problem of sampling from a multi-modal target distribution. Specifically, utilizing the diffusion framework, this paper investigates the problem of estimating the diffusion scores when only the potential of the target is known. The paper provides theoretical score-estimation guarantees for those potentials that satisfy certain smoothness and dissipativity assumptions. Building upon the previous result in (Conforti et al., 2025), this results in an end-to-end sampling guarantee.", "questions": "Some questions are in the \"Weaknesses\" section. Other than those, I have the following questions.\n\n1. In the paper the score estimator is frequently called \"our estimator\" (even listed as the third contribution). However, the paper also claims that it has been considered in (Saremi et al., 2024). My question is: Is there any algorithmic modification from (Saremi et al., 2024)? If not, my concern is that the third contribution might sound as overclaimed.\n\n2. Is there some other distributional example (which is hard to sample when only the potential is given) that satisfies dissipativity beyond Gaussian mixtures?\n\n3. How are the obtained results related to the sample complexity of estimating the vanilla score-matching objective, in particular for Gaussian mixtures?\n\nI am happy to raise my score if these questions are properly addressed.", "limitations": "This is a theoretical paper. There is hardly any negative societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. Combines diffusion-sampling and unnormalized targets\n2. New theoretical guarantees that apply to different target distributions for which the potential is known\n3. Polynomial complexity except the dimension\n\nWeaknesses:\n1. The contribution on Gaussian mixture seems to be confusing. In particular, it is claimed that \"no sampling guarantees were yet derived for general Gaussian mixtures\" (line 199). However, this is only true when restricted to the case where the potential function rather than the samples are given. Indeed, there have been many recent attempts to characterize estimation guarantees for Gaussian mixtures under this vanilla objective (e.g., [1]), but none of these is included as related works.\n\n2. Continuing the previous point, the Gaussian mixtures seem to be a special focus both in the motivation and in presenting the results. It is not clear why Gaussian mixtures are important for unnormalized models, as once we know the potential, it is easy to obtain samples and perform vanilla score matching.\n\n3. The presentation of the paper is quite confusing. \"Our algorithm\" is mentioned in Theorem 1 even before it is proposed. This quite hinders readability.\n\n[1] Sitan Chen, Vasilis Kontonis, Kulin Shah, Learning general Gaussian mixtures with efficient score matching.", "was_revised": true, "final_justification": "The theory part is quite strong. I did not score it higher because I feel that the 2d illustration is still simple, and the dependence on dimension is important (which is not polynomial in the paper).", "rebuttal": "**Related work on Gaussian Mixtures** -- As noted by the reviewer, the authors of [1] assume that samples of the mixture are available, whereas we assume query access to the potential $V$. While these are two very different settings (Generative modeling vs classical sampling), we will include [1] as a reference in our paragraph on Generative Modeling. \n\n**Sampling from a Gaussian Mixture is easy when $V$ is known** -- We would like to clarify that we do not assume that $V$ is known analytically, only that we can evaluate $V(x)$ at any given point $x \\in \\mathbb{R}^d$. In particular, even if $V$ is the potential of a Gaussian Mixture, we do not know the corresponding weights, the means and the covariance matrices. \n\n**Result presented before algorithm** -- We followed a standard way of presenting results in TCS (theoretical computer science) [1, 5], where the emphasis is put on the consequences (in this case, polynomial complexity for sampling from a multimodal distribution) rather than on the algorithm itself, which is just a means to an end. However, we fully recognize that clarity is important and when introducing a concept early, we will explicitly state in which later section of the paper it will be elaborated. \n\n**Comparison with Saremi et al., 2024** -- Even though we use the same estimator of the score, note that we do not use it within the same pipeline: in Saremi et al., 2024 the scores are used in a chain of MCMC at a single noise level. In our work, we use this estimator within the reverse diffusion framework, with multiple noise levels. Hence, our overall algorithms differ. Furthermore, note that unlike Saremi et al., 2024, we provide a non-asymptotic error for this estimator (Proposition 4) and we fully control the overall error of our algorithm which is, in our opinion, the main contribution of our work.\n\n**Third contribution is an overclaim** -- We are unsure of the link between the SNIS estimator of the score and our \"third contribution\": in our introduction, we stated our third contribution as the fact that our algorithm does not require prior knowledge on the target to provably work. Is this what you had in mind? \n\n**Dissipativity beyond Gaussian Mixtures** -- First, we emphasize that our work being the first one to handle Gaussian Mixtures, this seemingly toy case is not an easy one. Furthermore, dissipativity is a quite broad setting: any distribution that is strongly log-concave outside a compact is dissipative and so are all distributions of the form $p(x) \\propto e^{- \\| x \\|^m}$ with $m \\geq 2$ (and by stability of dissipativity by mixtures, so are all mixtures of the two previous kinds). \n\n**Comparison with vanilla score matching** -- The asymptotic sample complexity of vanilla score matching scales with the square of the Poincaré constant of the target density (Theorem 2 in [3]). For multi-modal distributions such as Gaussian mixtures, this constant increases exponentially with the between-mode distance (Section 4.1 in [4]). In contrast, our result shows polynomial scaling with respect to the between-mode distance (see our Section 3), which we believe is a key theoretical strength of our work. \n\nWe hope we addressed all of your questions and hope you will consider revising your score. Please let us know if any further clarifications are needed. \n\n[1] Chen et al., *Learning general Gaussian mixtures with efficient score matching*, Arxiv 2024 \n\n[2] Saremi et al. *Chain of log-concave markov chains*, ICLR 2024 \n\n[3] Koehler et al., *Statistical Efficiency of Score Matching: The View from Isoperimetry*, ICLR 2023 \n\n[4] Schitling, *Poincare and Log–Sobolev Inequalities for Mixtures*, Entropy 2019 \n\n[5] Jason Altschuler and Sinho Chewi, *Faster high-accuracy log-concave sampling via algorithmic warm starts*, Journal of the ACM 2024."}]

Author rebuttal:

Meta-review: All reviewers praised the novel theoretical contribution of this work, to an important problem relevant to the NeurIPS community.

There is a consensus to accept, but the paper is still borderline; three of four reviewers mark this as only borderline accept. In general, there is concern that the experimental validation is minimal (though this is fine for a theory-oriented paper) and also that the proposed method largely combines existing approaches. Reviewers had mixed opinions regarding the overall clarity of the paper and presentation. There were also some concerns as to the exponential dependency on the dimension, as the polynomial complexity is only for a fixed dimension. However, all reviewers felt on-balance that the theory represents a strong enough contribution on its own for acceptance.
Decision: Accept (poster)