Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization
Authors: Frederic Koehler
Thuy-Duong Vuong
Venue: ICLR 2024 poster (2024)
Keywords: sampling
score matching
contrastive divergence
langevin dynamics
Primary area: learning theory
TL;DR: We show that sampling multimodal distributions with the vanilla score is provably fixed by data-based initialization.

Abstract: There is a long history, as well as a recent explosion of interest, in statistical and generative modeling approaches based on \emph{score functions} --- derivatives of the log-likelihood of a distribution. In seminal works, Hyv\"arinen proposed vanilla score matching as a way to learn distributions from data by computing an estimate of the score function of the underlying ground truth, and established connections between this method and established techniques like Contrastive Divergence and Pseudolikelihood estimation. It is by now well-known that vanilla score matching has significant difficulties learning multimodal distributions. Although there are various ways to overcome this difficulty, the following question has remained unanswered --- is there a natural way to sample multimodal distributions using just the vanilla score? Inspired by a long line of related experimental works, we prove that the Langevin diffusion with early stopping, initialized at the empirical distribution, and run on a score function estimated from data successfully generates natural multimodal distributions (mixtures of log-concave distributions).

Published as a conference paper at ICLR 2024
SAMPLING MULTIMODAL DISTRIBUTIONS WITH THE INITIAL-
VANILLA SCORE: BENEFITS OF IZATION
Frederic Koehler
Thuy-Duong Vuong
Department of Statistics and Data Science Institute
Department of Computer Science Stanford University Stanford, CA 94305 tdvuonge stannngsssaffrr.eee.o..
University of Chicago
Chicago, IL 60637
ABSTRACT
There is a long history, as well as recent explosion of interest, in statistical and generative modeling approaches based on score functions - derivatives of the log-likelihood of distribution. In seminal works, Hyvärinen proposed vanilla score matching as a way to learn distributions from data by computing an estimate of the score function of the underlying ground truth. and established connections between this method and established techniques like Contrastive Divergence and Pseudolikelihood estimation. It is by now well-known that vanilla score matching has significant difficulties learning multimodal distributions. A Although there are various ways to overcome this difficulty, the following question has remained unanswered - is there natural way to sample multimodal distributions using just the vanilla score? Inspired by a long line related experimental works, we prove that the Langevin diffusion with early stopping, initialized at the empirical distribution, and run on a score function estimated from data successfully generates natural multimodal distributions (mixtures of log-concave distributions).
INTRODUCTION
Score matching is a fundamental approach to generative modeling which proceeds by attempting to learn the gradient of the log- ligelikel of the ground truth distribution from samples ("score function")) [yyvärinen (2005). This is an elegant approach to learning energy-based models from data, since it circumvents the need to compute the (potentially intractable) partition function which arises in Maximum Likelihood Estimation (MLE). Besides the original version of the score matching method (often referred as vanilla score matching). many variants have been proposed and have seen dramatic experimental success in generative modeling, especially in the visual domain (see e.g. Song & Ermon 2019) [ong al. 2020b); Rombach al. (2022)).
In this work, we revisit the vanilla score matching approach. It is known that learning a distribution via vamilla score matching generally fails in the multimodal setting (Wenliang al.) 20199; Song Ermon 2019. Koehler et al. 2022). However, there are also many positive aspects of modeling distribution with the vanilla score. To name a few:
1. Simplicity to fit: computing the best estimate to the vanilla score is easy in many situations. For example, there simple closed form solution the class of models being fit is an exponential family (Hyvärinen, 2007b). and this in turn lets us compute the best fit in kernel exponential family (see e.g. /Sriperumbudur al. (2017); Wenhang et al. (2019))
2. Compatibility with energy-based models: for distribution p(z) & exp( exp(E(x:)) the vanilla score function is E((r)) so is straightforward to go between the energy and the score function. This is related to the previous point (why exponential families are simple to score match), and also why is easy to implement the Langevin chain for sampling an energy-based model.
3. Statistical inference: in cases where vanilla score matching does work well, it comes with attractive statistical features like Vn-consistency, asymptotic normality, relative efficiency

---

Published as a conference paper at ICLR 2024
guarantees compared to the MLE, etc. e.g. Barp et al. (2019); Forbes & Lauritzen 2015); Koehler et al. (2022): Song et al. (2020a).
In addition, score matching is also closely related to other celebrated methods for fitting distributions which have been successfully used for a long time in statistics and machine learning pseudo- likelihood estimation (Besag, [975) and contrastive divergence training (Hinton 2002). (See e.g.
Hyvärinen (2007a): Koehler et al. (2022))
For these reasons, we would like to better understand the apparent failure of score matching in the multimodal setting. In this work, we study score matching in the context of the most canonical family of multimodal distributions - mmiturrs of log-concave distributions. (As a reminder, any distribution can be approximated by sufficiently large mixture, see e.g. [Wasserman] (2006).) While vanilla score matching itself does not correctly estimate these distributions, we show that the trick of using "data-based initialization" when sampling. which is well-know in the context of CD/MLE training of energy based models (see e.g. |Hinton (2012); 2): Xie et al. (2016) and further references below), provably corrects the bias of any model which accurately score matches the ground truth distribution.
1.1 OUR RESULTS
We now state our results in full detail. We are interested in the question of generative modeling using the vanilla score function. Generally speaking. there is some ground truth distribution μs, which for us we will assume is a mixture of log-concave distributions, and we are interested in outputing good estimate á of We show that this possible provided access to:
1. A good estimate of the score function of V log μ.. (In many applications, this would be learned from data using a procedure like score matching.)
2. A small number of additional samples from μ4, which are used for data-based initialization.
To make the above points precise, the following is our model assumption on μ:: Assumption 1. We assume probability distribution p. is mixture of K log-concave components: explicitly, μ = = PiPt, for some weights . PPK S.I. P; 0 and E, Pt 1. Furthermore, suppose the density of each component μ4 is crronglyllog-ooneee and 3-smooth with B 2 i....
al 1 -V log [4(x)= N 31 for all x. We define the notation p- min; Pę and k = a//x 2 1.
Remark 1. The assumption that p4 is a-strongly log-concave and 3-smooth is the most standard setting where the Langevin dynamics are guaranteed to mix rapidly (see e.g. Dalalyan (2017).
and the following captures formally what we mean by a "good estimate" of the score function: Definition 1. For p. a probability distribution with smooth density p(z)). an Escore Escore acccurate estimate of the score in L2(p) is a function s such that
E (e>p]]]>((>) - V log [o))(())11] S Sccoe.
(1)
As discussed in the below remark, this the standard and appropriate assumption to make when score functions are learned from data. There are also other settings of interest where the ground truth score function is known exactly (e.g. a is an explicit energy- based model which we have access to, and we want to generate more samples from i in which case we can simply take éxcore O.
Remark 2. Assumption ① says that on average over freresh sample from the distribution, s(x) a good estimate of the true score function V log u(z).. This the right assumption when score functions are estimated from data, because it is generally impossible to learn the score function far from the support of the true distribution. See the previous work e.g. Chen et al. (2023); Lee et al. 2022abb) b): Block et al. (2020) where the same distinction is discussed in more detail.
Given a class of functions which contains a good model for the true score function and has small Rademacher complexity compared to the number of samples, the function output by vanilla score matching will achieve small L2 error (see proof of Theorem of Koehler et al. (2022)). In
We can always re-scale the domain so that , 1 1.
For example, one case of generative modeling is when we have the ground truth and want to accelerate an existing sampler which expensive run, e.g. Alhergo (20T)) Lawrence & Yamauchi (202))
2

---

Published as a conference paper at ICLR 2024
particular, this can be straightforwardly applied to parametric families of distributions like mixtures of Gaussians. We would also generally expect this assumption to be satisfied when the distribution is successfully learned via other learning procedures, such as MLE/contrastive divergence. (See related simulation in Appendix !
We show the distribution output by Langevin dynamics on an approximate score function will be close to the ground truth provided (1) we initialize the Langevin diffusion from the empirical distribution of samples, and (2) we perform early stopping of the diffusion, so that does not reach its stationary distribution. Formally, let the Langevin Monte Carlo (LMC, a.k.a. discrete-time Langevin dynamics) chain with initial state Xo, score function 8, and step size h > 0 be defined by the recursion
X((+1) = Xns + (X() + 2h Ani
where each noise variable Ans ~ (0, 1) is independent of the previous ones. Our main result gives guarantee for samplling with LMC started from small set of samples and for time T:
Theorem 1.
Let ETV E (0, 1/2). Suppose μ is a mixture of strongly log-concave measures in Assumption and s is a function which estimates the score of μ within L2 error Eyoore in the sense of Let
Definition
T= ((((
(exp((K)d
(x(1))
GvV
h h= (BK2K exp(K))Addp
PaETV
Let Usampic be set of M i.i.d. samples from μ and V sample be the uniform distribution over U sample- Suppose that M (Mpp2epp Ka log (K/ (/EEv) log( (/T),, and that
12 1/2 V/VTTee =
p2 GTV
Cycore
7T
(Bx2K (xp(())Pd8227p)
Let (X"mmook nh OnEN be the LMC chain with score s and step size h initialized at Vsampte Then with probability at least 1 - over the randomness of samples the conditional law = L(X ( satisfies
U (ssappe)
drv (p. (p, S cTV.
We now make few comments discuss the meaning of the result. Conclusion 2 says that we have successfully found an -cy-e approximation of the ground truth distribution Unpacking the definitions, says that with high probability over the sample set: (1) picking a uniform sample from the training set, and (2) rumning the Langevin chain for time T will generate an approximaee sample from the distribution jr. Note in particular that we can draw as many samples as we like from the distribution without needing new training data. The fact that this is conditional on the dataset is key distinction: the marginal law of any element of the training set would be p. but its conditional law is a generative modeling (being able to draw new samples from the right distribution). See also Figure for simulation which helps illustrate this distinction.
at that training sample, and the conditional law is what is relevant for
Provided the number of components in the mixture is O(1), Le. upper bounded by constant, the dependence on all other parameters polynomial or logarithmic. It is possible to remove the dependence on the minimum weight p- completely
Remark 3.
Corollary i Appendix 77
Remark 4. It turns out Theorem 7 is new result even in the very special case that the ground truth unimodal. The closest prior work is Theorem 2.1 Lee al. (2022a), where il was proved that the Langevin diffusion computed using an approximate score function succeeds to approximately sample from the correct distribution given (polynomially- jwarm start in the x2 d-vveergence. However, while the empirical distribution of samples is a natural candidate for a warm start, in high dimensions it will not anywhere close to the ground truth distribution unless we have an exponentially large (in the dimension) number of samples, due to the "curse of dimensionality" see e.g. Wasserman (2006).
1.2 FURTHER DISCUSSION
One motivation: computing score functions at substantial noise levels can be computationally difficult. In some cases, computing/leaming the vanilla score may be substantially easier task than
3

---

Published as a conference paper at ICLR 2024
alternatives; for example, compared to learning the score function for all noised versions of the ground truth (as used in diffusion models like [Song & Ermon (2019)). As a reminder, denoising diffusion models are based the observation that the score function of noised distribution N N0,0021) +p exactly corresponds to a Bayesian denoising problem: computing the posterior mean on X ~ P given noisy observation Y ~ Nxx o² T) Vincent (201T): Block et al. (2020), via the equation
y + o log(N I21) * ()) = E| Y = y]-
Unlike the vanilla score function this will not be closed form for most energy-based models; the optimal denoiser might be complex when the signal is immersed in substantive amount of noise.
For example, results in the area of camputaaiinal-ssatistiiin gaps tell us that for certain values of the noise level a and relatively simple distributions p. approximate denoising can be average-case computationally hard under widely- believed conjectures. For example, let p be a distribution over matrices of the form N(rr" ,²") with r random sparse vector and e > 0 small. Then the denoising problem for this distribution will be "estimation in the sparse spiked Wigner model". In this model, for a certain range of noise levels performing optimal denoising is as hard as the (conjecturally intractible) "Planted Clique" problem (Brennan et al., (0188; in fact, even distinguishing this model from a pure noise model with r is computationally hard despite the fact it is statistically possible
see the reference for details. So unless the Planted Clique conjecture is false, there is no hope of approximately computing the score function of p * (O, o²) for these values of o. On the other hand, there is no computational obstacle to computing the score of itself provided e >> 0 is small denoising is only tricky once the noise level becomes sufficiently large.
Related Experimental Work. As mentioned before, many experimental works have found success generating samples, especially of images, by running the Langevin diffusion (or other Markov chain) for small amount of time. One aspect which varies in these works is how the diffusion is initialized. To use the terminology of Nijkamp et al. (2020), the method we study uses an informative/data- based initializattin similar to contrastive divergence |Hinton (2012); Gao et al.] (2018); Xie al. (016)) While in CD the early stopping of the dynamics is usually motivated as a way to save computational resources, the idea that stopping the sampler early can improve the quality of samples is consistent with experimental findings in the literature on energy-based models. As the authors of Nijkamp al. (2020) say, "it is much harder to train a ConvNet potential learn steady-state over realistic images. To our knowledge, long-run MCMC samples of all previous models lose the realism of short-run samples." One possible intuition for the benefit of early stopping. consistent with our analysis and simulations, is that it reduces the risk of stepping into low-probar coooobbbyylltty regions where the score function may be poorly estimated. Some works have also found success using random/uninformative initializations with appropriate tweaks (Nijkamp et al.) 2019 2020), although they still found informative initialization to have some advantages - for example in terms of output quality after larger numbers of MCMC steps. Finally, recall that the success of many recent experimental works which fit score functions with neural networks (e.g. [Song & Ermon (2019): Song et al. 22220b) Rombach et al. (2022); Ho et al. (2020)).
The works Block et al. (2020) : Lee et al. (2022a) established results for learning unimodal distributions (in the sense of being strongly log-concave or satisfying log-Sobolev inequality) via score matching, provided the score functions are estimated in an L2 sense. The work Kochler et al. (2022) showed that the sample complexity of vanilla score matching related the size of a restricted version of the log-Sobolev constant of the distribution, and in particular proved negative results for vanilla score matching in many multimodal settings. The works Lee et al. (2022b); Chen et al. (2023) proved that even for multimodal distributions, annealed score matching will successfully learn the distribution provided all of the annealed score functions can be successfully estimated in L2 In our work we only assume access to a good estimate of the vanilla score function, but still successfully learn the ground truth distribution in a multimodal setting.
Related Theoretical Work.
In the sampling literature, our result can be thought of establishing a type of metastability statement, where the dynamics become trapped in local minima for moderate amounts of time- - see e.g. Tzen et al. (2018) for further background. Also in the sampling context, the works Lee et al. 2018 Ge et al. 2018) studied a related problem, where the goal is to sample a mixture of isotropic Gaussians given black-box access to the score function (which they do via simulated tempering). This problem ends up to be different to the ones arising in score matching: they need exact knowledge of the true score function (far away from the support of the distribution), but they do not have access training
4

---

Published as a conference paper at ICLR 2024
data from the true distribution. As a consequence of the differing setup, they prove impossibility result (Ge et al. 2018 Theorem F. for mixture two Gaussians with covariances I and 2/ (it will not be possible to find both components), but our result proves this is not issue in our setting.
Questions for future work. In our result, we proved the first bound for sampling with the vanilla score, estimated from data, which succeeds in the multimodal setting, but it an open question if the dependence on the number of components is optimal; it seems likely that the dependence can be improved, least in many cases. Finally, distributions our result can generalize to with data-based initialization, multimodality itself is no longer an obstruction to sampling with Langevin from estimated gradients, but are there other possible obstructions?
interesting to ask what the largest class of
2 TECHNICAL OVERVIEW
We first review some background and notation which is helpful for discussing the proof sketch. We leave complete proofs of all results the appendices.
Notation. We use standard big-Oh notation and use tildes, e.g. Ö(.). to denote inequality up to log factors and Oz(-) to denote an inequality with constant allowed to depend on B. We let drv( v) = supA (μ(AA) - m[A] be the usual total variation distance between probability measures and defined the same space, where the supremum ranges over measurable sets. Given random variable X, we write (XX) to denote its law.
Log-Sobolev inequality. We say probability distribution satisfies log-Sobolev inequality (LSI) with constant CLS if for all smooth functions f. [og < [ Due the Bakry-Emery criterion, if is a-strongly log-concave then  satisfies LSI with constant CL.S 1/a. LSI is equivalent to a statement about mixing of the Langevin dynamics - if we let T denote the law of the diffusion time then an LSI is equivalent to the inequality
DKL [-) & exp(-2t/1 222ttt/Os (et//Cs))KK(Tolll (Tol
holding for an arbitrary initial distribution To- Here DKL (P.() = Ep dP is the Kullback- Liebler divergence. See Bakry et al. 2014)
aQ
Van Handel (2014) for more background.
Stochastic calculus. We will need use stochastic calculus compare the behavior of similar diffusion processes see Karatzas & Shreve (199]) for formal background. Let (X.) and (Yi) be two Ito processes defined by SDEs: d.X, $1 (Xx))dt + dB, and dY, s2(X)) + dB,. Let Pr, Qr be the laws of the paths (X,) and (Y))tejo,7) respectively. The following follows by Girsanov's theorem (see (Chen et al. 2023 Eq. (5.5) and Theorem 9))
1 (Yv,Yr,)))) drv Pr) Bar [."
s1 sY))l -1x1sxxx)==xxxx1111)
In particular, this is useful to compare continuous and discrete time Langevin diffusions. If (Y;) be the continuous Langevin diffusion with score function s, and (X,) is linearly interpolated version of the discrete-time Langevin dynamics defined by d.X, = s(X (1/m]a)dt dBe,, then
1 Bar 1/" [|s(X) s(Y) (1(1))))))
Xx)²
(3)
2.1 PROOF SKETCH
High-level discussion. At a high level, our argument proceeds by (1) grouping the components of the mixture into larger "well-connected" pieces, and (2) showing that the process mixes well within each these pieces, while preserving the correct relative weight of each piece. One of the challenges in proving our result is that, contrary to the usual situation in the analysis of Markov chains (as in e.g. Bakkry et al. (2014); Levin & Peres (2017). we do not want to run the Langevin diffusion until mixes to its stationary distributions. If we ran the process until mixing, then would be performing
5

---

Published as a conference paper at ICLR 2024
the vanilla score matching procedure which provably fails in most multimodal settings because it incorrectly weights the different components (Koehler et al. (022). So what we want to do is prove the process succeeds at some intermediate time T (See Figure for simulation illustrating this.)
To build intuition, consider the special case where all of the components in the mixture distributions very far from each other. In this case, one might guess that taking T to be the maximum of the mixing times of each of the individual components will work. Provided there are enough samples in the dataset, the initialization distribution will accurately model the relative weights of the different clusters in the data, and running the process up to time T will approximately sample from the cluster that the initialization is drawn from. We could hope to prove the result by arguing that the dynamics on the mixture is close to the dynamics on one of the mixture components.
Some challenges to overcome in the analysis. This is the right intuition, but for the general case the behavior of the dynamics is more complicated. When components are close, the score function of the mixture distribution may not be close to the score function of either component in the region of overlap; relatedly, particles may cross over between components. Also, the following remark shows that natural variants of our main theorem are actually false.
We might think that initializing from the center of each mixture component would work just as well as initializing from samples. This is fine if the clusters are all very far from each other, but wrong in general. If the underlying mixture distribution is 5N(00, Ia) + (0, 21a) and the dimension d is large, then the first component will have almost all of its mass within distance ((1) of a sphere of radius vd and the second component will similarly concentrate about a sphere of radius V2d. (See Theorem 1.1 of Vershynin (018).) )) As consequence, the dynamics initialized at the origin will mix within the shell of radius / d but take (xp(S((d)) time to cross the larger v2d shell. (This can be proved by observing that the gap between the two spheres forms a "bottleneck" for the dynamics, see Levin & Peres (2017))) In contrast, if we initialize from samples then approximately half of them will lie on the outer shell and, as we prove, the dynamics mix correctly.
Remark 5.
We now proceed to explain in more detail how we prove our result. We start with the analysis of an idealized diffusion process, and then through several comparison arguments establish the result for the real LMC algorithm.
Analysis of idealized diffusion. To start out, we analyze an idealized process in which:
1. The score function V log μ is known exactly. (Our result is still new in this case.)
2. The dynamics is the continous-time Langevin diffusion given by the Ito process
dxx = V log u ((x,) dt + vdd...
This is the scaling limit of the discrete-time LMC chain as we take the step size h + O. where dB, is the differential of Brownian motion B,.
3. For purposes of exposition, tion μ is supported in a ball of radius R. This will not be literally true, but for sufficiently large R μ will be almost entirely contained within radius R ball. (In the supplement, handle this rigorously using concentration, see e.g. proof of Lemma 11 of Appendix FF)
make the fictitious assumption that the ground truth distribu-
Additionally, for the purpose of illustration, in this proof sketch we assume the target distance in TV is 0.01 and consider the case where there are two atsonongly log concave and f-smooth components fi and μ2z and μ = Ž + 122 After we complete the proof sketch for this setting, we will go back and explain how to generalize the analysis to arbitrary mixtures, handle the error induced by discretization, and finally make the analysis work with an L2 estimate of the true score function.
Overlap parameter. We define
512 = 1 - dry (M1, =
quantitative measure of how much components and overlap; for example, 612 1 iff μr and He are identical. The analysis splits into cases depending on whether 812 is large; we let > be a parameter which determines this split and which will be optimized at the end.

---

Published as a conference paper at ICLR 2024
High overlap case (Appendix C If di and μ2 has high overlap, in the sense that 812 2 8, then show that μ satisfies a log Sobolev inequality with constant at most O(1/(a5)), by applying our Theorem 2 an important technical ingredient which is discussed in more detail below. Thus for typical sample x from J4, the continuous Langevin diffusion (X?") )ez0 with score function V log J initialized at x converges to p i.e. drv(L(X;) p) S for T 2 22( 1 ad log(de 1)
Low overlap case (Appendix) F Lemma 17). When μl and have small overlap i.c. 812 S 6, we will show that for x ~ 14, with high probability, the gradient of the log-likelihood of the mixture distribution μ at z is close to that of one of the components P1, (Appendix F.P.. supposing that ||=||| < R, for i E 2] we can upper bound
This is because,
V log 14: (x)]1 S 2,3R (1
11(x)) (1(x) + +2((z)
V log ((x)
and low overlap implies that min;
(1r is small for rypical x ~ μ..
Consider the continuous Langevin diffusion (x²²) initialized at 62 i.c. Xo = Observe that the marginal law of X where a is exactly μu, since is the stationary distribution of the Langevin diffusion. Let H > 0 be a parameter to be tuned later. The above discussion and Markov's 's inequality allows us to argue that for a typical sample v, the gradient of the log-likelihood of μ at X is close to that of either components (A1 /22 with high probability.
HH
Next, we perform a union bound over n E fo..... .N - 1} and bound the drift V log (u(x) v log (x)]] in each small time interval inH, (n+ By doing so, we can argue that for typical over the randomness of the Brownian motion
sample x ~ with probability at least 1 -3-
driving the Langevin diffusion, the gradient of the log-likelihood at X for E O. N H is close to
that of the component distribution μ4 closest the initial point x (see Proposition 26 of Appendix [
In other words, assuming that the initial point x satisfies M1 (3) 2 (2(2) and letting T = N H, we can show that with high probability,
V (o) V (oog (E[O.T]
sup
S 1.le.
This allows us, using 3 to compare our Langevin diffusion with the one with score function V log μn and show the output at time T is approximately a sample from μ4l
In a typical set ssmmll of i.i.d. samples from μt, roughly 50% of the samples E Usmple satisfy Ui (z) 2 (2) and the other 50% samples satisfy μ2(x) 2 (I(),, thus the Langevin dynamics (X, "annte J:20 initialized at the uniform distribution l/sample over Usapple will be close to M1- = f after time T provided we set H,,T,e, E, appropriately.
Concluding the idealized analysís. Either 812 2 8 in which case the high-overlap analysis above based on the log- Sobolev constant succeeds, d12 8 in which case the low-overlap analysis succeeds. Optimizing over we find that in either case, with high probability over the set Usamplo of
samples from μu, for 2 Ō2 (BR)3 4572
we have
drv(C(X) Sorpp |Usampte); p) S 0.01
as desired.
Generalizing idcalized analysis arbitrary mixtures. (Appendix Theorem 5 When there are more than two components, we can generalize this analysis - tthe key technical difficulty, alluded to earlier, is analyzing the overlap between different mixture components. We do this by defining, for each 5 > 0, graph G where there is an edge between i, E [K] when d.j := 1 - drv (Hi. < 8. As long as the minimum of the weights p. == min, P; is not too small, each connected component C of G is associated with a probability distribution PC = Eize Pips that has log Sobolev constant on Liec
the order of OO,O, Kpp (1/a6).
'This follows as LSI yields exponential convergence in KL-divergence. While the KL-divergence of the initialization 5- with respect ş unbounded, we can hound the KI. -lvdeieeeeeeee of X-6x for some small h.
7

---

Published as a conference paper at ICLR 2024
Suppose for moment that the connected components well separated compared to the magnitude of 6. More precisely, suppose that for i.j in different connected components and some >> we have
(a5)&//2
6. S f(6) : (3R)3
Then, a direct generalization of the argument for two components shows that for a typical set Usumple of i..dd samples from μs, the continuous Langevin diffusion (X, (XPhomp ")20 initialized at the uniform distribution over Usmple converges to ju after time Ta =aad)=
remains to discuss how we select so that 4 is satisfied. We consider a decreasing sequence 1 - do > 61 > > ōK-1 where 6 [(,) as in Eq. {4). Let C G If any two vertices from different connected components of G" have overlap at most 6,41, then the above argument applies. Otherwise, G must have one less connected component than G², and since G has at most K connected components, G R-1 must have connected component and the above argument applies it. Thus, all cases, the distribution of "
is close to ju in total variation distance.
Tok-1
Discretization analysis. (Appendix G Lemma 14 We move from continuous-tine to discrete-time process. Let (x and (x)) be respectively the LMC with step size and the continuous Langevin diffusion. Both are with score function V log μ and have the same initialization. By an explicit calculation, we can bound || V log μи())lop along the trajectory of the continuous process. This combined with the consequence of Girsanov's theorem (3) allows us bound the total variation distance between the continuous (X,) and discretized (Xna) processes. For appropriate choices of step size and time Nh, using triangle inequality and the bound drv drv(Xx, p1). we conclude that the discretized process X NA is close to μl.
Sampling with an Lz-approximate score function. (Appendix G In many cases, score functions only have access an Lz-estimate of the score such that E [s() v log [33] < - We now describe how to make the analysis work in this setting. Using Girsanov's ' theorem, we can bound the total variation distance between the LMC (Xa meN initialized at y with score estimate and the continuous Langevin diffusion (Zth)ee with true score function V log μt, thus we can bound the probability that the LMC (x=)))==(u... )n=(u,....N-1 hits the bad set
learned from data,
Bscore {x: ||((z) log [(x)]| Escore,
(The idea of defining a "bad set" is inspired by the analysis of Lee et al. (2022a).) Similar to the argument for the continuous process, let S. denote the LMC with score function s and step size h initialized at the empirical distribution Psample- Since we know that X avoids the bad set and that L(X*))) = BU ammaa [C[ (x(",,, (xsnkt)))))) ))] we have by Markov's inequality that for typical U sample> with high probability over the randomness of the Brownian motion, 5 also avoids the bad set < N. Thus, we can compare Xah X with the LMC with true score function log μ1, and conclude that L(X (. is close to μ in total variation distance.
Bucure for all
2.2 TECUNICAL INGREDIENT: LOG-SOBOLEV CONSTANT OF WELL-CONNECTED MIXTURES
The following theorem, which prove in the appendix, is used in the above argument to bound the log-Sobi log-Sobolev constant of mixture distributions where the components have significant overlap.
Theorem Let I be a set, and consider probability measures {prtien, nonnegative weights (px)ier summing to one, and mixture distribution = Ex Piu.. Let G be the graph on vertex set I where there is an edge between i. if (es Hy have high overlap i.e.
Bij = min(( 2
Suppose G is connected and let p. min p.. The mixture distribution μ EiEr Pitti has log- Sobolev constant
CLS(H) < CHi.. max CIS(HI
where C1I1.p. = 4/7 + 1)),, only depends on [T] and p.-
8

---

Published as a conference paper at ICLR 2024
140
0.5
033
030
045
6.03
0.1
000
0.3
(a) T 0
(b) T 200
(c) T & truth (orange)
Figure I: Visualization of the distribution of the Langevin dynamics after T iterations when initialized the empirical distribution and with approximate score function estimated from data. Orange density (rightmost figure) is the ground truth mixture of two Gaussians; the empirical distribution (leftmost figure. T 0) consists of 40 iid samples from the ground truth. Langevin dynamics with step size 0.01 is run with an estimated score function, which was fit using vanilla score matching with one hidden-layer neural network trained on fresh samples; densities (blue) are visualized using Gaussian Kernel Density Estimate (KDE). Matching theory, we see that the ground truth is accurately estimated at time 200 even though it is not at 0 or co.
A version of Theorem which bounds the (weaker) Poincaré constant instead appeared before as Theorem 1.2 of Madras & Randall| (2002), but the result for the log-Sobolev constant is new to the best of our knowledge. Compared to Chen et al. (20TT), ), our assumption is milder than their assumption that the chi-square divergence between any two components is bounded. (For example. two non-isotropic Gaussians might have infinite chi-square divergence (see e.g. (Schlichting 2019 Section 4.3)). so in that case their result doesn't 't imply a finite bound on the LSI of their mixture.) Schlichting (2019) bounds LSI of μ P/1 + (1 p) when either x² (21l122) or x ((22l11)) are bounded; our bound applies to mixtures of more than two components.
3 SIMULATIONS
In Figure we simulated the behavior of the Langevin dynamics with step size 0.01 and an estimated score function initialized at the ground truth distribution on simple 1-dimensional example, mixture of two Gaussians. If the Langevin dynamics are run until mixing, this corresponds to exactly performing the standard vanilla score matching procedure and this will fail to estimate the ground truth distribution well, which we see in the rightmost subfigure. The empirical distribution (time zero for the dynamics) also not good fit the ground truth, but as our theory predicts the early-stopped Langevin diffusion (subfigure (b)) is indeed good estimate for the ground truth.
In Figure we simulated the trajectories of Langevin dynamics with step size 0.001, again with initialization from samples and learned score function, in a 32-dimensional mixture of Gaussians. Similar to the mie-dimensional example, we can see that at moderate times the trajectories have mixed well within their component, and large times the trajectories sometimes pass through the region in between the components where the true density is very small. Additional simulations (including an experiment with Contrastive Divergence training) and information in Appendix [
ACKNOWLEDGMENNSS
F.K. supported in part by NSF award CCF1704417, NSF award IIS1908774, and N. Anari's Sloan Research Fellowship.
REFERENCES
Michael S Albergo, Denis Boyda, Daniel Hackett, Gurtej Kanwar, Kyle Cranmer, Sébastien Racaniere, Danilo Jimenez Rezende, and Phiala E Shanahan. Introduction normalizing flows for

---

Published as a conference paper at ICLR 2024
-1
(a) -300
(b) 12000
(c) T 120000
Figure 2: 2D projected trajectories of Langevin dynamics up T iterations with step size 0.001 in 32-dimensional mixture of Gaussians / (- 1.57) + 3 (6e1, 1.5/). The projection is the first two coordinates and the direction of separation of the components the first axis direction. Langevin is initialized from the empirical distribution (15 iid samples) and run with an approximate score function learned from samples using a one hidden-layer neural network.
lattice field theory. arXiv preprint arXiv:2101.081777 2021.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Alessandro Barp, Francois-Xavier Briol, Andrew Duncan, Mark Girolami, and Lester Mackey. Minimum stein discrepancy estimators, Advances in Neural Information Processing Systems, 32, 2019.
Julian Besag, Statistical analysis of non-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), 24(3):179-195, 1975.
Adam Block, Youssef Mroueh, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and langevin sampling. arXiv preprint urXiv:2002.00107 2020.
Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory, pp. 48-166. PMLR, 2018.
Hong-Bin Chen, Sinho Chewi, and Jonathan Niles-Weed Dimension-free log-sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281 2021.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R. Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions, 2023.
Sinho Chewi, Murat A. Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of langevin monte carlo from poincaré log- sobolev. 2021.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society. Series B (Statistical Methodology), pp. 651-676. 2017.
Persi Diaconis and Laurent Saloff-Coste. Logarithmic sobolev inequalities for finite markov chains. The Annals of Applied Probability, 6(3):695-750) 1996.
Peter GM Forbes and Steffen Lauritzen. Linear estimating equations for exponential families with application to gaussian linear concentration models. Linear Algebra and its Applications, 473: 261-283, 2015.
Ruiqi Gao, Yang Lu, Junpei Zhou, Song-Chun Zhu, and Ying Nian Wu. Learning generative convnets via multi-grid modeling and sampling. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 9155-9164, 2018
Rong Ge, Holden Lee, and Andrej Risteski. Simulated tempering langevin monte carlo ii: An improved proof using soft markov chain decomposition. arXiv preprint arXiv: /8/2,00799 2018.
10

---

Published as a conference paper at ICLR 2024
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800, 2002.
Geoffrey E Hinton. A practical guide to training restricted boltzmann machines, Neural Networks: Tricks of the Trade: Second Edition, pp. 599-619, 2012.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-68541 2020.
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Aapo Hyvärinen. Connections between score matching, contrastive divergence, and pseudolikelihood for continuous-valued variables. IEEE Transactions neural networks, 18(5):1529-155 1531, 2007a.
Aapo Hyvärinen. Some extensions of score matching. Computaaional statistics data analysis, 51 (5):2499-2512, 2007b.
Ioannis Karatzas and Steven Shreve. Brownian motion and stochastic calculus, volume 113. Springer Science & Business Media, 1991.
Frederic Koehler, Alexander Heckett, and Andrej Risteski. Statistical efficiency of score matching: The view from isoperimetry. arXiv preprint arXiv:2210.00726, 2022.
Scott Lawrence and Yukari Yamauchi. Normalizing flows and the real-time sign problem. Physical Review D. (0((1)):14509) 2021.
Holden Lee, Andrej Risteski, and Rong Ge. Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering langevin monte carlo. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31, Curran Asso- ciates, Inc., 2018. URL https: httttp:://prooeed.ngg.... neurips htt.er/wps..ccppppp////////////. c6ede20e6r59 oagia//266tttttaoooofooeeaaeeeee
4b3
pdf
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. arXiv preprint 2rXiv:2200..0627,, 2022a.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. arXiv preprint arXiv:2209. 12381, 2022b.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, 12:581 1-661 2002.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer foundaation symposium (CSF), pp. 263-275 IEEE, 2017.
Erik Nijkamp. Mitch Hill, Song-Chun Chun Zhu, and Ying Nian Wu. Learning non-convergent non- persistent short-run meme toward energy-based model. Advances in Neural Information Processing Systems, 32, 2019.
Erik Nijkamp, Mitch Hill, Tian Han, Song-Chun Zhu, and Ying Nian Wu. On the anatomy of meme-based maximum likelihood learning energy-based models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp- 5272-5280, 2020.
Phillippe Rigollet and Jan-Christian Hütter. High dimensional statistics. Lecture notes for course 18S997, 2017.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.

---

Published as a conference paper at ICLR 2024
André Schlichting. Poincaré and log sobolev inequalities for mixtures. Entropy, (1)))8 2019, doi: 10.3390/e21010089. 2tt.:///0.......................
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Yang Song. Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pp. 574-584. PMLR, 2020a.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13455, 2020b.
Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Aapo Hyvärinen, and Revant Kumar. Density estimation in infinite dimensional exponential families. Journal of Machine Learning Research, 18, 2017.
Belinda Tzen, Tengyuan Liang, and Maxim Raginsky. Local optimality and generalization guarantees for the langevin algorithm via empirical metastability. In Conference On Learning Theory, pp- 857-875. PMLR, 2018.
Ramon Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Pascal Vincent. A connection between score matching and denoising autocncoders. Neural computa- fion, 2367)116 2011.
Larry Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
Li Wenliang, Danica J Sutherland, Heiko Strathmann, and Arthur Gretton. Learning deep kernels for exponential family densities. In International Conference on Machine Learning, pp. 6737-6746. PMLR, 2019.
Jianwen Xie, Yang Lu, Song-Chun Zhu, and Yingnian Wu. A theory of generative convnet. In International Conference Machine Learning, pp. 2635 2644. PMLR, 2016.
12

---

Published as a conference paper at ICLR 2024
A ORGANIZATION OF APPENDIX
In Appendix we review some basic mathematical preliminaries and notation, such as the definition of log-Sobolev and Poincaré inequalities. In Appendix [ we prove Theorem 4 (Theorem of the main text), which shows that when clusters have significant overlap that the Langevin dynamics for the mixture distribution will successfully mix. Appendix (aaandiixaannd and Appendix D contain intermediate results which are used in the following sections: diffusion starting from a point, and Appendix E shows how to bound the drift of the continuous Langevin diffusion over a short period of time. In Appendix[Fiw we prove Theorem [ which shows that the continuous Langevin diffusion with score function VV converges to μ. after suitable time 7. In Appendix G we prove our main results Theorem and Corollary [ which show that the discrete LMC with score function s with appropriately chosen step size close to μl in total variation distance suitable time. Corollary [ corresponds to Theorem I of the main text. In Appendix H remove the dependency of the runtime and number of samples on the minimum weight of the components Le. P. min p; (see Theorem and Corollary for the analogy of Theorem and Corollary T respectively that has no dependency on p.). Appendix contains some additional simulations.
Drrendixxsshowee how to analyze the Langevin
B PRELIMINARIES
In the preliminaries, we review in more detail the needed background on divergences between probability measures, functional inequalities, log-concave distributions, etc. in order to prove our main results.
Notation. We use standard big-Oh notation and use tildes, e.g. Ö(-), to denote inequality up to log factors. We similarly use the notation S to denote inequality up to a universal constant. We let v) = s [m{AA) v(A) be the usual total variation distance between probability measures and v defined on the same space, where the supremum ranges over measurable sets. Given a random variable X, write L(X) to denote its law. In general,
the same notation for measure and its probability density function as long as there is no ambiguity. For random variables X, Z. we will write drv (X, Z) denote the total variation distance between their laws L(X) and ((Z).
B. RENYI DIVERGENCE
The Renyi divergence, which generalizes the more well-known KI. divergence, is useful technical tool in the analysis of the Langevin diffusion divergence order & E (1, oc) of μ from æ is defined to be
c.g. Vempala & Wibisono (2019). The Renyi
du(x=)
)
1 In /
dd((z) do (x(
In E,
dm d
dm (x)
9-1
In /
du(xx) (d((T)
8-1
1
du((x)
dp(x)
In By,
q
9-1
di dx())
The limit R2 as q + is the Kullback-Leible divergence DKL (M|( p(x) log ((x)) x(z) dx, thus we
write R.(-)) (.).()) Renyi divergence increases as q increases i.e. R. S R.y for S S d'
Lemma (Weak triangle inequality, (Vempala & Wibisono, 2019 Lemma 7), Mironov (017)). For
q >> 1 and any measure absolutely continuous with respect measure p.
1/2
Ru(()ln) < R2, (2,(1/))))
(21-1(1/11))
q 9-1
Lemma 2 (Weak convexity of Renyi entropy). For q > 1. if is convex combination of p4 i.e. u(x) = Σ (z)) then
dv((x)
( (dv(a) (du(())
E,
$ Σ prE,
du(x))
Consequently, (el()) max; (1lss) and (ull() max; Re
13

---

Published as a conference paper at ICLR 2024
Proof. By Holder's inequality
E (c)((=))0-11
Σ
Pj
E p.) =1
Mc(z))-1
thus
vxx)
9-1
vxz)
9-1
Pi
m(x))
Taking expectation in v gives the first statement. Similarly, since > 1 > 0,
( (W(2))
o
[
[1(z))
Ev
S Σ P.E.
(H((z))
For the second statement
In E dr(z) a- du(z))
In(xxx; E, KK dr(x) )o-1)) 11
dia(()))
max R.g (vlla))
q
and
In E2 [[ (e(()) )9]
In (max, B
dv(z) )²)
Ro(u|lu)=
(a)((a)
max (vslll)))
q
B.2 LOG-CONCALE DISTRIBUTIONS
Consider a density function Rd R2 where Txx) = exp(-V(x)) Throughout the paper, we will assume V is a twice continuously differentiable function. We say a is 3-smooth if V has bounded Hessian for all Rd:
-31 v²V 31.
We say is a-strongly log-concave if
0 0< v\V
for all x E IRd.
B.3 FUNCTIONAL INEQUALITIES
For nonnegative smooth f Rd + R20, let the entropy of ff with respect to probability distribution
be
Ent [ʃ] = [f(f
We say satisfies a Sobolov inequality (LSI) with constant CLS if for all smooth functions f.
F < (n
and π satisfies a Poincare inequality (PI) with constant Cpy if Var, < 2Cp The log-Soboley inequality implies Poincare inequality: Cp1 I CL.s Due to the Bakry-Emery criterion, if क is a-strongly log-concave then и satisfies LSI with constant CLs 1/a.
LSI and Pl are equivalent to statements about exponential ergodicity of the continuous-tin time Langevin diffusion, which is defined by the Stochastic Differential Equation
dx V log パ (Xt' dt v2dB
Specifically, let n, denote the law of the diffusion at time initialized from mo then LSI equivalent to the inequality
(KL(T)l(=) < exp(-2t (2--2//sC)P)LmmE
holding for arbitrary initial distribution mp- Similarly, PI is equivalent ( ||T) < dPr (1//Crr) Here DRz Q) Ey aq is the Kullback-Liebler divergence and (P Q) = Eo[(dP/dQ - 1) is the x2 -ivvergeence. See Bakry et al. (2014); Van Handel
(2014) for more background.
14

---

Published as a conference paper at ICLR 2024
B.4 CONCENTRATION
Proposition 1 (Concentration of Brownian motion, (Chewi et al. 2021 be a standard Brownian motion in RRd. Then, if X 2 and h S 1/ (2),
Lemma 32)). Let (B:)
(x
sup ||B.112] ] BE(U,h)
E
exp
exp(6dhh))
In particular, for all 1)
(- 1/?
sup telo,h]
|Bl| 20 S cxp
6dh
Proposition 2. Suppose random non-negative real variable Z satisfies
Vt: P 2 D + s 2exp(->t²)
for some D 2 0, 0. Then there exists numerical constant C s.t.
B[2g] S CyP/2 -
Proof. For some R D be chosen later
E =
1 2 x dr
11"
/ P|ZZ 2 z/dr RP
IP 2 x/dr
000
$
1d
+
P 2 y)d(vP)
R
R 2p
8 exp( -7 d
x-1 exp( ( DP-1 / exp(->22 (s2(-))))dz)
Rp p29(
S R 28 2-- p/2 (7-1/ pp2(p/2) pDP-1 120--1-1/3 1/2 TT)
+pD
where in the last inequality, we make change of variable u 722 and note 7 pPpl 2/2-1 exp(-u)du
that 2p ʃ 28 exp(p exp(-72²)dz Jo exp(->22)dz = 11/2/m1/ Take R = gives the desired result.
l(p/2) I (p/2)p/2 and
Proposition (Bakry al. 2014 5.4.2), restated in (Lee al. 2022al Lemma E.2) ). Suppose T: R R20 satisfies LSI with constant 1/a. Let f Rd + R be L-Lipschitz function then
at2
Pawe [[(x) [=()(])]] 2 1) S exp
2L
Proposition 4 (Sub-Gaussian concentration norm for strongly log concave measures). Let V Rd + R. be a-strongly convex and 3-smooth function. Let 3/a. Let n be the probability
measure with T(x) exp(-V(x))) Let x, arg ming V(x) then for D 5 In(10k) we have
Pawa ||| x.ll 2 D + t] exp(-att/4
thus by Proposition 2 for p 2 1.
Ex [||| -= 11 O(1)p In(10))
Proof. By (Lee al. 2022a Lemma E.3), let F [x]] then || -x'l // In(0s).. By Proposition for any unit vector Rdd the function (v, 5) is 1-Lipschitz, since (V,
15

---

Published as a conference paper at ICLR 2024
|| yll2. Thus, by Proposition 3 (u. σ) has mean 0 and sub- Gaussian concentration for unit vector v, thus x - 2) is a sub Gau-saasi random vector. From sub- uub-Gaussianity standard argument (see e.g. Theorem 1.19 of Rigollet & Hütter (2017) shows that
(,,y)1 I V| 2 ج|ا2
d a
P
||
xll
2 4V
+
s
thus by triangle inequality, using that ||8 -
- V
(100,,,
we have
4V d a
| - x111 2 (4 1/2 Pa
+
S x ||
xll
2
+t S exxp(-aff /4)
Proposition 5 (Normalization factor bound). Let V 1 IR be c-strongly conver and B-smooth function. Let π. be the probability measure defined by x x(x) x
and = Zx
J exp( (xx) )d be its normalization factor For any Rd
IIV( (2 s 235 exp
-V(y) + IIVV())1I))
(V(y) +
11//2
exp
25
2a
Let y = x² arg min (z) and assume w.l.o.g. Vyy) gives
d
1
d
2 In S In 7T In In(2 s In
Proof. Since al 3 (z)(x) 3 3I,
x + + 5 V(y) (VV(y),x V) +111 u113/2
7 2 /
exp( exp(-V(()) -v() (VV x - -allx /112/2ddr
exp (V(2) + |VV(2))1
all(x - y) + a - vV
exp
dr
2a
2
(2)
exp
-V(())
(2TTa 1/d/22
2a
The lower bound follows similarly. The second statement follows from the first since VV(x") = 0.
B.5 GIRSANOV'S THEOREM
Theorem 3 (Girsanov's Theorem Karatzas & Shreve
1991 Chapter 3.5)). Let (Xi) be stochastic
processes adapted to the same filiration. Let Pr and Qr be probability measure on the path space C(O,T]: ;R; X, evolved according
dX,, = b," dt + Vdd. under Pr
dX, b9 dt + v2dB, under QT
Assume that Novikov's 's condition
1 I exp (4 1b6," - 69 b2112dt) ]
Eqr
< 00
(5)
holds. Then
dPr dQT
exp (1,"
108
1 (bp
18 dB
4 {" 1b6 -b9
(6)
V2"
16

---

Published as a conference paper at ICLR 2024
Lemma 3 (Application of Girsanov with approximation argument (Chen al. 2023 Equation 5.5, Proof of Theorem 9)). Let (Xt) be stochastic processes adapted to the same filtration. Let Pr and Qr be probability measure on the path space C(O,,T T); s.t. Xt evolved according to
dX,- = bi. dt + /2dB, under Pr
dX,, bidt dt + V2dB under Qr
Suppose Eer 1So la6l 6, oo then
!
Bdrv(Q1) (QT|| Pr) S DKL (QTlI
Eor
116
11112
Lemma 4 (Corollary of Theorem tions in Theorem For any event E,
Chewi al. 2021
Corollary 20)). With the setup and precondi-
dPr dQ1
9
q² / l1b - b2112tt 18
Eqr
18 S
EQr
exp
B.6 MIXTURE POTENTIAL
Notation for indexing components. Let /= = [K] be the set of indices i for the components f4 of the mixture distribution p.. We will need to work with subsets S of I and the mixture distribution forms by components μi for i E S.
Definition 2. For S S 1, let ps = Eies Ps: and μs = Eses Pitl: Let Vs log Ms.
S we omit the subscript S.
Derivative computations. For future use, compute the derivatives of V.
Proposition 6 (Gradient of V).
VV(x) = VV((()
(7)
m(x)
Consequently, [[V(())]| & max [V((=)]
Proof. The statement follows from
VV(x) = Vlogm(z)= Vp(x)
(xx)
and
Vμ(x) [ V P.Z," (vp(-))(z)) ()n()))V(()))
Proposition 7 (Hessian of V).
V'V(x)- (=P u(x)
PaDjU(()),, -V) -V
VV)(
4p²(x)
(8)
hence VV BT for all E T then V2V(x) 1 BT.
Proof. Let Z, exp( -Vi(x))) be the normalization factor of μ.. Note that
v(nx(z)VV((z))
-
7. + v2V(())
17

---

Published as a conference paper at ICLR 2024
and Vu(z)= = [pin(())V(()))) thus
V2x(2)
PIH (V
1(x)
1x(x)
-WV D m())
11((z)
Next,
Σ { P(LL)VV(()) - E (L PiHA)
2 EaRppeNN VV VV(E)VVV VV2(2)VV,))
2 Σ
VVC))) -VV(=))
thus the first statement follows. The second statement follows from noticing that (VV(()) (VVV())) VV}(x)) ž
B.7 PROPERTIES OF SMOOTH AND STRONGLY LOG-CONCAVE DISTRIBUTION
We record the consequences of a-strongly log- log-concave and 8-smooth that will use.
Lemma 5. Suppose μ4 is a-strongly log-concave and 3-smooth then for B/a, u;
arg min (z);,; D 5 In(10x), and c₂ a lu,, we have
1. For all V s 3 and [V)|)) B||= uill
2. al|x 611x- < V((a) 8|| 2.112.
Consequently, for 2, = J (dxx,, there exists 24 S z_ with 24 = -- - C2 s.t.
exp(-0llı u.1 =-) S (x)) = 2 expl - Vv(x)) S exp(-cal will? z+)
3. Sub- bub-ggassian concentration:
P[[ will 2 D t) < exp(-att
By Proposition this implies that for all
Fulll1 - uz [P] Ex DP.
4. satisfies LSI with constant CLs = 1.
Proof. This is due to Proposition and Proposition 2 and the fact that VVi(u,) = for 24 arg min (z).
B.8 BASIC MATHEMATICAL FACTS
Proposition 8. For any constant a > 0,b,p E Nzo f(x) exp( b)x is decreasing on [p/a, +20)
Proof. Let g()) logg f(x) -ax b log and observe that
g'(x) - p/x 1 0
when x 2 p/a, the claim follows by integrating.
18

---

Published as a conference paper at ICLR 2024
Proposition 9. Let PI...., Pk. QI...., Qs be distributions dIv & c. Let
a1 ag. 81, .. By be s.t. as 3, 2 OVi and E, 04 -, Then
drv Σ a.P. Σ (. s =Σ ais
and
drv d Eailin E B.Qi) - 2
Σ ass Bd
Proof. By triangle inequality
2d CaavlEail a. (uri)= J.Sn EaiP((t) Σ (
Σ
-aj1P(())-Q(i0))) Qi(z))dr = =2 E Ladrrv(P, Qi)
ZE
Similarly,
2dTv E a, E 3.Q
JEEn EΣ [a((())) Σ (ll(
Jas - (x)) Σ la; 3,1 Σ
-
ZEN
C LOG-SOBOLEV INEQUALITY FOR WELL--CONEECTED MIXTURES
In this section, we show that the mixture Σ Pitt, has a good log-Sobolev constant component distributions p4 have high overlap. The below Theorem corresponds Theorem of of the main text. Definition 3. For distributions Let dij denote 8(14, (2)). Note that
let 5(v, x) min(v(r), xx)) be the overlap of v and x.
1 5 5(v, TT) )²= f|v/[ssa (v(x)
(x)))
J (v(x) (x))ddr drv(u, T).
Theorem 4. Let G be the graph on I where (i.g) E E(G) iff Pt, 1b have high overlap i.e.
f {
dij =
min((s(())
2 6.
Suppose G is connected. Let M S |1| be the diameter of G. The mixture distribution Σiel Pip has
1. Poincare constant (Madras & Randall 2002
Theorem 1.2)
4M
Cpr(ua)
Cri(k) < 8
max EEY
Pi
2. Log Sobolev constant
Cis(H) < 4MCLs(p)
CLs(M)
8 max
Pi
where for p. = min; ps, CLS(p) = + +og(p= ) is the log Sobolev constant of the instant mixing chain for p. Hence
Ci.((H) S C1t.pp mmax
max Cr.s(ps)
where Cpp,. 417 + )),, only depends on [T] and pa
19

---

Published as a conference paper at ICLR 2024
Below fix a test function f s.t. Eulfa I co. Let
Ct. = - - (z)
(9)
Lemma (Triangle inequality).
2-1
Cio se
0
Proof. Without loss of generality, assume i, j for all j. Then
Cio.se = | (f(on) - ((0)
= Jh... / (f(2o) - f(1z) + ... f(ze-1) f(xe)) III jm0
(f(z0)-
Mey (21 )roydd ... .x.
me
6-1 -
HI ... dxt
e
= e " J (f(zz) 1) dd,, = l Σ
Cjs+1
j= 23
5=0
where the inequality Holder's inequality.
The following comes from (Madras & Randall, 2002 Proof of Theorem 1.2)
Lemma 7. If ( dx 2 5 then
Ct. S 2(2 2(2 8)
(Var,: (f) + Var,y (f)).
Proposition 10 (Variance decomposition).
J. [ (())))
2 Var (f)
Σ
Cip
Σ
p Var (f) +2 Σ EpppyC.s
Proof.
Var,()) = / ((x) ([messsooaa
= [.] 1 (())at))wW)ddd - 1.1,
(V) dady
2 [.]. (()) P dxdy
1 / / ((z))(b)(((>)) f(v)) dzzyy
2
20

---

Published as a conference paper at ICLR 2024
Since (xx)= = (ipsss(IE, further rewrite
2 (ar = (190) (((())
Σ Ppsulco)) (Emurlor) drdy
-
Σ (1PP)((()))(()) dady 1.
EPDD PiP; (((56))
Σ Cip,Cij
Σ p.Ca + [(ii Cji)
2 > of Var p [f] + 2
Σ i
Cip
where the last equality is because Cip = Czi-
Lemma 8. For j let "is be the shortest path in G from j and let hispl be its length i.e. the number of edges in that path. For u, u, let uo denote the edge {u, oj of G if it is in E(G). Let M max,, |7tp be the diameter of G. Then
ΣPiP, S
Σ
Cuv
Σ
pipsitaol
15
MVE B(G)
isjurEns
M(2 8)
Σ
Var (f)
8
u
M(2 8)
Σ EE [/|
5
Proof.
Σ Pip,Ciys <
Σ (Cuv Σ
pepyltus)ss M Σ (Cuv Σ
PsPp)
(VEE(G)
QvE
iejawENy
By Lemma 7 and the definition of G, Cun <
2(2-8) 0
(Var (f) + Varp, (f)), thus
2M(2
Σ Pip,Cis <
Σ
(Var + Var,, (f))
Σ
PiPj
MVEEIG)
i<javEnu
2M 8)
Varp, (f)
Σ
PiPj
CaPEE(Q)
2M(2 8) Σ
Var (f)
Σ
PiPj
M(2 8)
Var (f)
6
M(2 8)
Σ
Cpr(Mu) EE. [1
21

---

Published as a conference paper at ICLR 2024
Proposition 11. For C2. be in Eq. (
C = 2 (Varm, (f) + Var (f) + (Bn,1f) - (B,1(1)3)
Proof. Let = 2/14 + 211- We write Var(v) in two ways. First, [x (E [f] + Ep, [f]) thus
Varx(f) = Ex - (Eu(f))² 2 [E Ep, (f9) 4 (E Eu, (f))
1 Σ [Epx[f?] (Bng [f]) + 1 (5 [f] + E Myl - 2E, [f
2 (E()))
1 4 (Bn, [f] - Bng [fl)
2 (Var,, [f] Var,, (fI)
On the other hand, by Proposition 10
Var, (f) (Var (f) Var (f)) 1 Cis
Rearranging terms gives the desired equation.
Proposition 12, Let = f². Let the projection of g on I be defined by g(i) = F. Then
Ent[
Σ
Ps Ent n. [ Entplg]
iE!
Proof.
Ent[f = /
bog
= / Σ (1 [og
Em pi (f (n(o))())) (((o))(()))ogg())dd logg(r)dr Ep [s(x)))
Σ logg() Ex(g(x) log((
where in the last equality, we use the definition of g()). Note that
Bamplo(1)]= = Σ p:g(1) Σ E(;: / / =
pilki g(x) (I
-F)((()))
thus
Ent[f Σee Ent [f + Ent,, [0(1)
Proposition 13. Let be defined in Proposition 12 then
vo(i)² (V0(1 ()())) < Var,, [ + Var [ + (E,, [f] Ey,, [/]) = 201r
Proof. The first inequality comes from (Schlichting 2019 Proof of Lemma 3) and the second part from Proposition
Proposition 14 (Log Sobolev inequality for the instant mixing chain, (Diaconis & Saloff-Coste 1996
Theorem A.1)). Let p be the distribution over I where the probability of sampling T is Pt. For
function h : 1 + R20
Ent, [h] < Cp Var [
with Cp 1n(4p=1) with p. min: P.-
22

---

Published as a conference paper at ICLR 2024
Lemma 9.
With defined in Proposition 12
Var v
Σ
p:p,(vo())- = Σ Pip,Cij
Proof of Theorem part We can rewrite
Ent =
Σ
Ps Eut [52] Entplg]
VEI
S())
EnCLs(W)EE + CLS(p) VarplVū)
2C2s(p) I + Σ Cip
S(2)
icj
2M 8)CLs(p)
Σ S(z)
Σ Cp,( [1|
8
4MCLs(P)
max CLs(HH)
S(4)
4M)
CLS(HL) EE [1
maxt
8
Pi
where (1) is due to definition of CLS(H)) and Proposition 14 (2) is due to Lemma 9 (3) is due to Lemma 8 and (4) is due to Cri(s) S CLS(RR and CLS(p), M 2 1.
D INITIALIZATION ANALYSIS
For the continuous Langevin diffusion (X2)c20 initialized at a bounded support distribution vos we bound R. (C(xx,) for some small h. Consequently, for μ being the stationary distribu- tion of the Langevin diffusion and satisfying a LSI with constant CLS, we can use the fact that (cL(C(X))llu) exp(- CLe (ec()K((XX))) (C(X,)) (4) to show that X, converges to μ..
Lemma 10 (Initialization bound). Let = Eier Pips be a mixture of distributions μ4 o exp(-Vi(z)) which are a-stroonly log concave and 3-smooth. Let V(x) = - In u(x). Let (Pr)eeto,n) (Vi)teto,M be respectively the distribution of the continuous Langevin diffusion and the LMC with step size h and score function VV initialized at 8z. Let G(x) max; [VVV( Suppose 1/(303) then for q E (2, TomN):
(T,lW/) S (2)
Ry-1(Pallm) S d 1I((2ah)-))
and
(a/2(Dhllm) S (( + 32 dh)) + 2
+ --
If we replace 8n with any Vy then by weak convexity of Renyi divergence (Lemma 2) the claim holds when we replace G(x) with G, supzempp(vo) G(xr).
Proposition 15. Let v = N(y, 22 x(x) x exp(-W(x)) is a-strongly log concave and B- Lipschitz and o < 1/2 then
(x((T) < II(ao))+ (W
Proof. Since aT = V2 3T,
(VW()) (v), x y) a||x / /2 < W(x) - w(y) (VW y) + B| x /112/2
By Proposition
5 we can upper bound the normalization factor 2 = [f exp (WW()) + [w)11 (2//-1
by
2a
23

---

Published as a conference paper at ICLR 2024
For R", using the upper bound on Z
4/2 Z exp (-11)) -11=~y] v11
v(x)/T(x)) (2TO²) (o00))ad12200
+ W(())
20²
W(x) W(v) (v)1
| n/1
(ao²² 4/2
(000))a12000) exp
2a
20
2 )2)
= = 4/2 exp
[[W(8)] 2(1-5045) exp
2(1 201-80 A
(3 a1 )0)
$ (aoo)) 4/2 exp
[|)
20(1 - -
S (ao7)) 4/2 exp (V)))/)))))))
where the last inequality follows from 1/2 1 -30 1 1 1.
Proof of Lemma 10 We apply Theorem
3 with T = h, Pr = (De)eE(o,N) and Qr = (o.))) Note
that, b."
(VV(X)) and b. (z)). We first check that Novikov's condition Eq. 5 holds.
]
1 4 % -
Eqr
exp
|69 1f
E exp
with (Xe)aeju. be the solution of the interpolated Langevin process i.e.
- - + v2B.
By 3-Lipschitzness of VV,
VX, - s ByllX, =|1 +
|[V] -
thus
VV S (G())) = max [X)] < G(x) + BIG(()) + 3V2 sup
|
jel
tE(0..)
1.1G(()) + 3V2 sup
||
(E
and
L// h [[VV(X.) v=(2)] 22 22 / (IVVV(X)I|++IVVV 13)
s < 448 sup 3E[D,A]
|B + G(x)
(10)
< (z) + h88h sup rE(o,))
||
We first prove the following.
Proposition 16. For any < 53
For exp A 1" 11b b811pat) ]
1 (1+ 11822222 s exp((4\h(P(1))
1-888822
Proof.
By Proposition
for A 5 1634p2
E exp / IVV((X))-V<<))l)
(F())
< E exp 4h>G²(a) + 4
sup ||B&| rE[O.A]
S exp(4\hG (x)) (x226632
24

---

Published as a conference paper at ICLR 2024
Apply Proposition 16 with À 1/4 gives
T
1 // [IVV(X)) -VVV(x))vV(<)))))
Eqr
exp
E exp
exp (hG² (x)) exp(11 <0
Next, let
H2 S/"
1
1 1 116 b
v2 16g 69. dB
then
exp(HI; and aQ.
dP
dH, = -VV()
1
By Ito's formula.
d dexp(gH,)
q² -xpp)//)lVV(Xx))-vvoc))) gexp(((11)) 1 -VV))) vV(X)),
/2
Thus
(exp(gH()) - g² --9 9 1/" )xp((H)))\V((X)))))))))))))))))) - -VV
4
q² hh
//'²'' VElexp(2qHHa) VEI]VV((())) (V())]14jdt
4
We bound each term under the square root.
VV|V), = B[(1.1((z) + BV2 sup
|B, + G(z))
rE(0,)]
$ 40G (x) + 3 sup
|| ||
LE(0,h]
s 400*(x) (z) + 0(342h2)
By Lemma 4 and Proposition 16 if q²
1 then
10082
4n² [" [VV(X.) -VV(X))-VV<>)))))) ]
(Elexp(2(H..))
exp
(x:) (xx) < (x + 72
Substitute back in gives
Eq, (exp(((T)r)) By the data processing inequality
- -1
4
In En, (x,p(qqq
(Tnla)) S (r(Pr ((r)
9-1
-2h
In
+
4
1+ 9h
< In
4
2h
In
1+
4
<
(3++)
25

---

Published as a conference paper at ICLR 2024
Now, note that Vn .V(y, 1 with y x (VV(2) and 0² 2h. Note that [vV
[[VV[(z)]I+ + Blyy z|| = [z)] - /h| (z))l - (z)) By Lemma 2 and Proposition 15
R2g-i(unllp) (1m) S max
5 In((2al)) -1) + max VV
2
1
In((2ah) + 2a - (x(
The final statement follows from the weak triangle inequality (Lemma
E PERTURBATION ANALYSIS
In this section, bound the drift ||X; - X fort E [kh, (k + 1)h] of the continuous Langevin diffusion X,. These bounds will be used to bound the mixing time of the continuous Langevin diffusion and compare the discrete LMC with the continuous process via Girsanov's theorem.
We will consider subset S of such that the components 14; for i E S have modes that are close together. We record the properties of the mixture distribution μs (see Definition 2 for definition) and and its log density function Vs - log μs in Assumption 2 To be clear, we are defining this assumption as it shared between multiple lemmas (and will be satisfied when we apply the lemmas), it is not new assumption for the final result.
Assumption 2 (Cluster assumption), We say subset S of I satisfies the cluster assumption if there exists Ug E R,,, 1 Atten,,, Agrad,1 Agrud, S.I.
1. (VVs(=)llop S minnes A uzl1 AHess,
2. VVs())]l Agrad, ||2 - usl Agrad.-
Proposition 17. Suppose for all S. ps satisfies item [ of Lemma 5 Let u, and D be as in
Lemma 5 and suppose I|u (ok-uj) uyll < L i,j E S with L Z 10D. Then μs satisfies Assumption with us Ps Eies pell, Agrad,
Agrad, BL, Attes,1 = 2,3 Atten 23
In addition, if μ4 satisfies item of Lemma Jthnn
PMs |r -usl 2 1.1L + 4 S expp-ca??/4))
Proof. First, Vi S: ||u; usll Ps Ejes 1 uzl - S L. By Proposition 6
VvV(s( = Σ VVV(() S Σ p. x -ull
iES
iES
Σ
PaB(11 usl
+ ||u usll) S ps(B|<æ usll + L)
i
We replace 1 with S and use the formula from Proposition
7
By Holder's inequality
[[VV;(x) V=)(>)11 & 4 max
[V
4.3²
max
uu 12
<
8,8 min(l uxl1 + 1.2)
KES
kES
keS
Next, for p. = -P/Ps, we have
2 ( = Σ Emnul(t) = (C)
Σ IJS
VES
thus
BT VV 2 0 7 max
[V((2) VV -2T
min([1= mall2 + 1.2).
iJES
RES
For D D I 1.1L and = 2.2
P 11 usl| > D +
vnln(1/n)
= Ps
Σ (2 1| usll 2 D + / In(nn))
iES
$ Ps
Σ
Pij4(Z
(Z:
1| w/ll 2 D + VzIn(1/n)
iES
< Ps
P:7)
26

---

Published as a conference paper at ICLR 2024
where first inequality is due to l|u us|l L for all i S.
Proposition 18. Suppose S C I satisfies item and item of Assumption 2 Let (Zz) be the continuous Langevin diffuusion with score VV initialized at Zo ~ 1o then for E [kh, (k + 1)h)
E||l V (ZMA) VV(22)11
$ V B[A Hess, 21 us|l + 11 us||s) + A Aess,ol
(t kh)a [" (n F usl| A gnd o) d2(t-kh)
Proof. By the mean value inequality
VVVs VVs(2))1 1uh
Zell
||>Vl
max
y=nZen +1-1111111) me.o...
By item of Assumption
2 the fact that - 2 + (1 - 2) and Holder's inequality
V & A usl12 + AHess, S AHess, (1) - us us 11 - us|l²) + AHess,
and
B(IVVs((Zk)) - -Vs
<B
(AHess.1 (11Zkk us|1² 12 || usll?) + AHess 300 2
VVs(Z.)ds + V2B:-An11
khh
E (AHess,1 (II - -usl us|12 + |X usl + AHoss,0)*
E|
VVs(Z))ds + 2B..-a
khh
By item 2 of Assumption| and Holder's inequality, for p O(1)
E||l
VVs(Z,)ds + V2B. [P]
[[ kh) 2-
[V,s( Pd B [0s]]
(4A22 (A2rd, usl 2p
S (I - kh) 2p-1
2p a ds + (d(( - kh))
The desired result follows from 4.
Proposition 19. Suppose S C I satisfies item of Assumptioo 2 Let (Zi)22 be the continuous
Langevin diffusion ps initialized at vn- Suppose 2Agut,11 and suPkejo.N || 1L usll S D then
6N
12 Zen < 22(AArod. + Agradt 1// us|l) + 48ch In
sup kE(O,N 1E
thus with probability 2 1-
1| - usll < 2hA grad, + 2D + 48dh 6N
sup kejo.N--TJN.eejo..i
1
27

---

Published as a conference paper at ICLR 2024
Proof. The proof is identical to (Chewi et al. 2021 Lemma 24). By triangle inequality,
1|Zhh+ Z
[VVs( /2 Bkn+ BEAll
hAgaad + Agrua,1 S/ [|Zxhtr usl|dr +
BEAll
(Nl/Zzn - -ulll + L. 1 Zen Banlldr) / - Buall
- hAgrado + Agrad,1
where we use item 2 of Assumption Zin in the second inequality. Gronwall's inequality then implies
[kzzttz Zkmll
h h(Agrad.0 Agrad, [k usll) + V2 sup [E[0,A]
Bkkh-t BuAl || exp(hAgrad.1)
$ 2h(Agrd,. +
usll) + /8 sup
|| Bkull
(6(0.))
as long as h < 2Agui.
Thus by triangle inequality,
1eh+t ug| - 1E - -usll + 1xh++ -t - 7kh
2h.Agad, / us|| Agadd 1) + v8 sup <E(o.A]
BBatt BEk
By union bounds and concentration for Brownian motion (see (Chewi et al. probability 1 ?):
2021
Lemma 32)), with
6NV
sup Bah+r BRall s 6dh In
6dhhlm
kE kEJU.N-1//N.EEOO..
thus
6N
sup -
|| - usll S 2h.ggadd + -2D
48dh In
ANALYSIS OF CONTINUOUS-TIMG DIFFUSION
In this section, analyze idealized version of the final LMC chain: assume knowledge of the exact score function and run the continuous time Langevin diffusion. First in Lemmal below, we prove that when the diffusion is initialized from a point, converges in a certain amount of time to sample from a mixture distribution corresponding to the clusters near the initialization. Then in Theorem 5 we deduce the analogue of our main result for the idealized process: the diffusion started from samples converges to the true distribution.
Definition 4. For S C I and x E Rd. let imax.s(()) arg maxtes p=(x). We break ties in lexicographic order of i.e. we let imax,s(22 s(x) be the maximum index among all indices i s.t. (x()) maxjes (z(x).
Lemma 11. Fix erV. T E (0,1/2),8 E (0.1). Fix S SCI. Let P.
P.PS' and recall that ps Eies Pitts. Papu. Let p. minges Ps. Note that p. 2 minjer Pi. Recall that |] K.
Suppose for E S, μ4 are a-strongly log-concave and 3-smooth with 2 1. Let u; = arg miny V₁(x) and D 2 /v/ d be defined in Lemma 5 Suppose there exists L 2 10D such that for any i, S, ||u, - u,ll S L.
Let G = (S, 5, E) be the graph on S with an edge between i,j iff 8.g S Let
2Cp..K
('n
B
T
+ Inlnn r 22
da
a
28

---

Published as a conference paper at ICLR 2024
Suppose for all i.j S which are not in the same connected component of G., deg S 8' with
33/2 p= CT
8' 105 (0 8/2 8 Le I-
In
16d(A))
For I E Rd, let (X,- 120 denote the continuous Langevin diffusion with score VVs initial- ized at da, and let mmxx(a) (2) be the unique connected component of G containing Smax,s(x) arg maxies (i(x) as defined in Definition 4 Then
P Pamps [drv (C(X)) (z), (C S ETV] 21-
From the above lemma, we can deduce the following theorem. (The proof of the lemma is deferred until after the proof of the theorem.) In this result, the reader can consider simply the case S the flexibility to pick a subset of indices is allowed for convenience later.
Theorem 5. Fix CrV, T E (0, 1/2). Fix S Let p: P.Ps'* and recall that ps = Eies Pipt- Let p. mints Pt. Note that p. 2 minge1 1 Pt. Recall that [[
= K.
Suppose for E S. #4 are atstrrngly log- log-concave and 3-smooth with 3 2 1. Let us = arg min, Va(x)) and D 2 /// au be defined in Lemma 5 Suppose there exists I, 2 10D such that for any i. S 1151- S L. Let Usomll be set of M ii.dd samples from μıg and ssampe be the uniform distribution over U sample. Let (Xg (o )220 be the continuous Langevin diffusion with score Vss initialized at Vsamplc Let
7/2 2 0//2
Pa
10dd(3L)exppAAs In (n3 1 In 16d(81))
If M 2 600()) -2² log (17 and
T2 1 (a 12 (f
then
Uu (drv (C(X ( (Usappt)) (1s) S <rv|21-9
Remark 6. Note that after fixing U Urample. pg Unmpii == L (Unample) is a function of Unmple and Brownian motions (Be)eEoOTT Each run of the Langevin diffusion produces sample from j'g by choosing/sampling value for the Brownian motions, thus we can produce as many samples as desired from f variation distance for a rypical set of samples U Usappte.
Unmone is approximately close to ps in total Unseis while Theorem 5 guaranttes that Ps
Proof of Theorem 5
Let P. = PPPS' then ps = Eies Pipt, For C S S, let Pc = Eiec Pi.
Let ěrV =
<rV. 9K' and 7 Paerv 9K
& min CTV .P/33. Define the sequence 1 = 6o > 61 > ... > 8k
inductively as follow:
8//2 3/2 5/2
G7
8.t1
10 10<K>d(3L)3mn 3/2
In 3/2 ST 1n
In 2.51 16d(GL)
3/2
3/2 7/2 TTV
10a ( (p=1) 3/2
3/2
LeTv
In 2.51 16d(
ervô,a
Let G* = G' E3) be the graph on S with edge between j iff d.j 2 d.. Fix one such s.t. K - 2. Suppose d,j < 8.41 for all i. not in the same connected component of G* then Lemmal I] applies. Let the connected components of Go be Ci...., Cs For x E Idd let C=ax(() (x) be the unique connected component of G* containing (max,,(2)) and let (X. )ez0 denote the continuous Langevin diffusion with score VV initialized at dz, then for T3
2C Sea
(In 9 + In + 2 knv),,
P Parps [drv (88. MC (+)) I εrv] 2
29

---

Published as a conference paper at ICLR 2024
and by Proposition 21
P Pawus ( E C.1 2 (1 - 6s+1)Pc;-
It is easy to see that d.+1 S Erv /3. By Proposition 23 as long as M 600(c7yp.)~ - K2 "2olog K +
log 11)
Uumnte (dTV(C((X) (i (aampi
us)) I eTV] 21-7
Since Ms is the stationary distribution of the continuous Langevin with score function VVs, for any "//ani (Usample); .u)) thus
2 Tk-1 2 Te, drv (C(( "oaok sUsample), ps) S drv (CV((C(XT) (C()),
Ueampe (C(X7,
"empk Usample) ps) S <evv 2 1-T.
On the other hand, suppose for all s E 10, - 2] N, there exists i.j not in the same connected component of G* s.t. dij > 6 then G has one fewer connected components than G Thus GK is connected then f has LSI constant x 6K-1 thus Lemma 11 apply with d = ōx-1 and Proposition 21 apply with 8' = For T 2 TK-1,
PU Ueepe ddv (C(x, Usample), ps) S eTVl 2 --
Let 2 e 8/2 If we ignore log terms, then 6,-1 2 thus d₂ 4(32)
(31)s
(2((3/2)-1) To get the correct bound for 6g and T,, we can let
p. 7/2 2/ 2/223/2
I1
8000d()L))expp( K) In 3/2 (p. (ppp:)nnn In 16d(81)2 S
eryTa
then we can inductively prove 6, 2 r2[ (11122)) and thus get the bound on T, i.e.
1k -1 In(10p |n 3 LeTV )T T 2((3/2)-
T, s 0 K2p,
ap. K
(0aa-kk3 (n
2/ 2/
with r 10=d((3L)Pexp(AA (p. 'nnn
18
*TVT
Proof of Lemmall 11 Let (X,) denote the continuous Langevin with score VVs initialized at us.
Since μs is the stationary distribution of continuous the Langevin with score VVs, the law L(X;) of X, is jss at all time t. Let = /22 and N T/h. Let h > 0. E (0, 1) to be chosen later. Let C be the partition of consisting of connected components of the graph G and Bsc be defined in Definition
5 Suppose 8', 7 satisfies -28 x T T/h S n/2,, then by Lemma 12 Mss (Bs,,,,)) N < Kk2 8 x T/h n/2
Since the law of Ngh is uas, we can bound || - us| using sub- Gaussian concentration of jas (due to Proposition 177. By the union bound, with probability 1 77, the event Edisertte happens where
Ediscrete is defined by: Vk E [O - I]NN: N: || usll || s 2L + 64 In 16N and X & Bs.C,v- " Since μs E Ex [8x]] and μs and 5, are the initial distribution of X, and X respectively, so (() = Exzus [(X [x)] where L(X) denote the law of the random variable X. Thus, let = 2L +
I6N and Go is the event
1| where the probability is taken over the randomness of the Brownian motions, then P [Gx] 2 1-7/2
Pr lvk - IjoN:
usll < L X & Bs.c,)) 2 1-e1111
Fix æ, let C Cmax (x) and suppose Gr holds. Suppose h satisties the precondition of Proposition 26
then with probability 2 - eTv/5,
[IVVs(X.*) [E[o,]]
sup
(e)
(ccore, := 36pp 1,,
thus X. & B for all t E [0, T7, where B is the "bad" set defined by B == E [[VVs(2)- Rd
VVe(=)]| > ( ) Let un be the distribution of X5, for some hi' < 1/(33)). Let Ginit be the event
30

---

Published as a conference paper at ICLR 2024
that || usll 1 L1 2L - log(10/7) then P. Paraulliii [9mit 2 1 T/10. Suppose Guit, happens.
Then Gs(z) maxies [[V](x))] 1L1. Set h min
{
BT. 3d then by Lemma 10
D DkL. (vol Mc) 2 dln BBL
Pick T P. be a
(In 3L In then h' 2 T process
Cu..I ān
(In DKL((ollus) + In eTV))
Let )220 be the continuous Langevin initialized at vo with score Soo defined by
(2) = (f (V
then sup |15 (z) VVc(=)]l S S E
Note that if Go holds then X BVt E [0, - h4]
and 2 X Vt E [0, ht] thus
dTv(X;; 2T- S ETV/5
Proposition 20 gives
drv ( - h/ (2)); [x),MC)) S Excore 1 T/2 + erV
Set
P.Cry then Excore,1 = 18p, 7 S VT then by triangle inequality 180LvT
drv (Tv(, xx), HC) S crv-
This holds conditioned on Gr and Fmnr. both happen, thus by union bound
P Pa>uldTv (C(x (x), (C))a(a)) S crvl 2 1 --
Plug in y and set
2000d(3L)2 2 16d(BL)PT
CTVT
then h In(1/h) S 200) and h hnn2 1000 /a) and S 100 (0(3%/a)ln (166T/v)) Hence
satisfies the precondition of Proposition 26
Finally, since < L
In
16T hm
< 22
In(3Lent- IT), thus with
83/2 3/2 5/2 77 In 3/2 8² Le In--1
P. P
8' < 10 10*K3d In(p
In
2.51 16
10s 133
eTVTda
TTV
the precondition
K28 x T/h= K28', x 183LVT
x TT/h
P.TTV
36K23LT3/2 In(3LeTtr-17)
< x
Parryh
1/2
CrVT/4
holds, so we are done.
Proposition 20 (Continuous chain with score estimation with Low enror bound). Fix C C I. Let (Zx) 1:20 and X, be the continuous Langevin diffussion with score functions VV and respectively and both (Zi) and (X.) are initialized at vo. Suppose supzers [|s(x) VVc(=)]1 < E then
2drv 2drv < DKL < E [ [|s(Z,) - (Vc(2)) < 2 T
Suppose μs has log Sobolev constant CLS and T 2 CLs KL ( + 22 ( v drv(((X)))Ne)) dry dx 7r) + (Lv+)( (1c) S (com, VT/2 + eTV
31

---

Published as a conference paper at ICLR 2024
Proof. Clearly, by the assumption on 8, E [|s( - vVc(())) - So0 S.rre dl sccure
The first statement thus follows from Girsanov and the approximation argument in (Chen et al. 2023 Lemma 9) and Pinsker's inequality. Next, since μ.c' has LSI constant CLS, with this choice of 7;
DRI(C(ZT)lIu)) - Dxz exp(- T
CL.
and the second statement follows from Pinsker's inequality and triangle inequality for TV distance.
We need these propositions to go from Lemma 1 to Theorem 5
Proposition 21. Suppose = =iiss Pipty Fix a set C _ 1. If the overlap between pas for E C and j & C is S 8' for all such i, then
p({x (mxx(()) E CJ) 2 pc 0'11))
To remove dependency on px, we will use the following modified version of Proposition 21 Proposition 22. Fix C, C. S I s.l. Cnc. 0. Let I' = I\ C. If E C,j E I' C' the overlap between μ4 and Py is S then fmax = arg max,e1' (,(x)
pr((æ: i (x) E C)) 2 pc 8114))
Proof of Propositions 27 aadd 22
We first prove Proposition 21 For E CC,j C
[ (mm)()))ss()) (z(x)dz
pi(to: (x)x) s (z(z)))
(1
$ f
s
By union bound, for i E C
(1x 3j C: [z())) 8
Let A {o : (max(() E C}. vj & C (.()))) > (x) then imax(x) E C. Thus A₃ == (x
(=(x)= > (í(2)b & CC and (A.A,) = -1-Mi(x & C: cx(( S 15(2)) 2 1 - T.. Since
u(x)= 2 LiecPalli
f u(x)dx
m(fx Xmax(() [C)
Σ pipt(x)dr- Σ (A))(A)
ZEEA
JSEA I5C
1EC
2 Σ (A,) 2
Σ Pi(1 81) -p((1-8(7))
The proof of Proposition 22 is identical. except we will consider C.j E I' \ C and argue
that u;(x: : [x(x)= I (z(x)) < 8'. Then [a] E 1')
\ C' pı(I) S <m,(z)) I 811 For i E C, T and A C fx 1maxx, ( (4) E C).
A; = (xl(4(z) > My (z)v Finally,
I' CJ then (A,,
u((x: F (2) E CJ) 2 Σ p.P((A)) 2 Ppp1-8'11 81(
iEC
Proposition 23. Consider distributions P4 for i E T. Suppose = Eier Pitki for P; > 0 and
Eier P. 1. Suppose have partition of into Ci...., Cm. For x E Rd let C = Cmnx (x) be the unique part of the partition C containing (xax(z)= arg maxiel (x)).. Let p. mingel Pi. For Rd. let (xxx) ) be process initialized 8z. Suppose for any ērv (0, 1/10), 7 (0.p./3),
there exists Tirv. 5 such that the following holds:
P Eecyldrr (C(XT 1), (Cmaala) S ērvl > 21 1-
32

---

Published as a conference paper at ICLR 2024
In addition, there exists 8' E (0, s.t. for C [CI....,,Cm Cm3 IP Pu-ulCmax( = C| Pc
Let Usample be set of M i..dd samples from i and Vsample be the uniform distribution over U Usmple. Let (Xi be the process with score estimate s initialized at 1/ Drample- If M z 6 x 10217]=67p12 =2 (og(Kr=)), with probubility 2 1 - over Usample, let T T TTx mint Ery p./3)
and P ( ( sampl))) then Uuinte (drv (L(Xx soople (Urample) p)) S cTv]
To remove the dependency on p. = minge1 Pts we will use this modified version of Proposition 23 Proposition 24. Consider distributions Ps for i E I. Suppose = EvE Pitti for pi > 0 and
EiEr Ps 1. For Fd let (xf*), be process initialized at dz. Let I' {i :i: TF3 I'.
and C. C I. Suppose we have partition C of I' into CI,'.., C, For x E IRd, lel Cmax (x) be the unique part of the partition C containing 'max, (x) = arg maxie1 [4(x))
Suppose for any ēTV (0,1/10), (0, 1). there exists Terv.7 such that the following holds:
Pawul drr (C(X [x), (Cmax(()) S ērv] 2
In addition, there exists 8' E (0,ēTv) s.1. for C (CI,..., Cm P m = CI 2 pc(1-8),
Let Usample be a set of M i.i.d. samples from μ and Vsample be the uniform distribution over )120 ):20 be the process with score estimate initialized at Vsample- If M Z 2 x 10a 1 TT log( ([T(( then for êTV
U Usample. Let (X, (Xmmmine
STV 7 9ा
97 and T Terv.F
PP Ununpe (drv(L(X( Naapppe [U (uampll)) 11) S <Tv] 21-7
(L(X)
Proof of Proposition 23 and Proposition 24 tion 23 is similar.
We will prove Proposition 24 The proof of Proposi-
For e I', let Q, = fx Cmax (x) = C, drv drv (X+r (C)maa))) S erv}. Clearly, Qp are disjoint, and by union bound ((2+r) 2 Pc, = =11 (1 821-8')pe 8')pc. - 7 2
erv
10/l1
Let Up 22 n Usaple then Chernoff bound gives
33 M7 PI|U11 2 Mrc, (1 -Tv)] 2 -eVo, 2 exp(
20]7]
28 Let & be the event Vr: : |U,| 2 MPc, (1 E. By union bound, P(E) 2 1 1- /1 exp(
20
Suppose & happens. Let Up sammlle Urer Ur then
Uo v M MM11 - =rv)
Σ
(Pc. (1- ērV
rEl'
< M (Tv - 81)(1 (TV) - -rvv]
< M (3érv + 8') < 4MeTy
where the second inequality is due to Erer PC, 2 21 E--ErgJPe PC, 2 |1| x ēTV [I).
Note that C(X² (uampp)))
M ExeUmm
c(Xf=12)) Thus, let Erer Unamte NC, and
|tel = Ever
[Ual n. we can apply part 1 of Proposition 9 drv (C(X Kompin ( ,, ())
M HC, + M
< - 1
Σ Σ
drv (rv( + Σ drv drv(CC(X)) (C(X++
drv
rEJ TEU,
zEti
< M (ērv(M - (lb)) + (Uo))
< črv + 4èrv 5êrv
33

---

Published as a conference paper at ICLR 2024
Next, note that /
Erer PC,HC, + pC, and Erer PC,MC, with pc, We bound ppc, Pc,|.
[Ua]
(1
M
10
[t
Muagte
M [Upl
10'1
UU
M(1 - -TV ((L 8', - Ery
M iUØl
M
ÊTV
1 PC, (2
2 Pc, (1 ÊrV 8') [
[1]
We upper bound [U,]. Since U,'s are disjoint,
U S M
Σ
U. M M Σ
Pc. -11 - -8") êTV
seP
sef'
I M(c. + 3eTv + 8) S MPc. + 48rv)
where the first inequality is due to the lower bound of [U,1 above and the second inequality is due to 1 -E PC. S PC, + ETV and ss PC, (ÊTV + 8') S (ēTV + 8'). Thus
|U~| M - Uel - Pc, < M(pc, + 4êTv) Pc, S 1 - -érév
48rv (pc, +1) I 162rv
M(1 - 4ērv)
where in the last inequality, use the bounds εrv 1/10 and pc. 1. thus 1 ) Ic. - -p.l max + [T|
Part 2 of Proposition gives
2d (n. (b) $ D Iic. - -Pc,1 Pc.
pc. $ ma (2 | }} + |7| x T
s (16) 1)ēr
Thus by triangle inequality,
drv (C(X |U (,mppt))) 1) S drv (("/aani [Usample); [1) + drv (u, ()) S 9
Let M 2 2 x 1101 log(1 / 11 2 20 / log(([(7~] gives the desired result.
In the proof of Proposition 23 l' 1, and we will set F min Ery p-/33 which implies
((2+)) 2 /3/3 and the event happens with probability / exp( (exp(_P-ijp P ). The rest of the argument follows through, and we need to set M 6 x 10pp, 17/2 log((T[r~1) to ensure & happens with probability 1-T. T.
F.1 GRADIENT ERROR BOUND FOR CONTINUOUS PROCESS
Definition (Bad set for partition). Let C = (Ci...., Cm) be a partition of S i.e. UC, S and Cr O Cr. = if & r'. For Rd, let pmax,s( = maxies [r(x), s(m)),(()) =
arg maxiss (x(x) T and Cuax((r) (I) is the unique part of the partition containing ((r) For (0, 1) lei
Bs,c, {x 3j E S
Cunax Muuas, (uuax,s(x)) S --- (15(m)
If these are clear from context, we omit S, C in the subscript.
Lemma 12. Fix S C I, C is partition of S, and define B,, = Bs.c.y y. as in Definition 5 of S
for i,j not being in the same part of the partition then pl ((,)) S - 6
*If there ties, break ties according to the lexicographic order of T.
34

---

Published as a conference paper at ICLR 2024
Proposition 25 (Absolute gradient difference bound). Fix S C I. For S, let p. P.Ps and recall that pz( Eies (S) Let == ( = arg maxyes' (z) Suppose C S and for all E \ C, p4(x) 2 (z))
Let (z( s [[V(( then
4y Gs(
In Appendix H we will state generalized versions of Definition Lemma 12 and Proposition 25 For proof' of Lemma 12 and Proposition 25 refers to proof of Lemma and and Proposition 32 respectively.
The following proposition shows that if the continuous Langevin process (Ze-) initialized at doesn't I hit the bad Cs,,,y, then the gradient (V,(2,) will be close to the gradient VVc(Z)) where C is the unique part of the partition C containing smax,s(x)).
Proposition 26. Fix
S. Suppose we have a partition C of S as in Definition Suppose for i E S. 14 satisfies item 1 of Lemma with B 2 and ||4 uyll S LVi,j E S. Let pt = Ps Ps, and recall that μs = -Eies Pit4.. Let (Zg") ):20 be the continuous Langevin diffusion with score function Vg initialized at dy. Fix E (0, 1/2). Suppose for any E (0, 1), with probability 1 - 7/2, the event Edierrte, happens where Edieentee is defined by: for all [0, N 1] N.
64
16N In
1 usll S -= =:: L+
n
and
7 & Bgc
Let T = Nh and C = (m) C be the unique part of the partition C containing i (xx).
Fix 1) E (0, 1). Suppose T 1.
h < min(
(8/a) (2/a) 40(BL)2 20000(3))3
h1n(1/h) (0 and h2l22(1/)) I 1030
Then with probability 1-1)
18y30
EE [0, (V=(2 - VVo N
min.er Pi
Proof. By Proposition
17 S satisfies item 2 of Assumption with Agrad, BL and Agmd,1 B.
From Proposition
19 with probability 2 - 2 the following event Edhn.n/2 happens
(64(3h)2 + 48dh In S $1/(208L)
16N
Zial1 S 4.hL + 2/ |
sup kEJo.N keJ..N-IIjN..Eo..i
a
Here we use the fact that In(16N/m) = In(16T/(mh) = (n616 + In(1/h) thus
64
16T
64
((L)) < h(3L)² + 2
ln
+ 2L(BL)8
In(1/))
7
< h(31)² + 16
1 h
82
h(31)2
167
+ 16
82
l1(3)))n((1/)
a
160
35

---

Published as a conference paper at ICLR 2024
and
64(
16N
+ 48dh
In
x (3I)
7
16T
64
167
64
< 10vdh(y In
+ vIn(1/h) [BL+20
In
+ 2/
In(1/h)
"
"
(10()
<10
16T [na(s1y
7 + (1)(31))
48
h
(In?
16T
(1/h))
7
80
Suppose both events /n and Edrit.n/2 happen. By union bound, this occurs with probability 77. We have, by triangle inequality
1 - usl s L + 1/(10 z 1.1
sup kE 1J0.NN-i
and for i E S, by item of Lemma 5 and ||u; - -usll S L
VVV Mh++ll & B(1 usll L.) S 2.2
(11)
For any i.j E and t E [0,
My My(ZZhh+
14 (Thh)
log
log
Mi Mr (Z8r1e))
Pi (28x)
v2((it) - -V (Z() - V.(Z
(12)
S (I (2 (i01l -ZZill 311 2h Zxh 11
S - 1/2
where we use the assumption 8 2 1.
Below we write mmax instead of i since is clear from context. We first argue by induction on that fmax (Z E C. The base case ko = 0 holds trivially. Let be a realization of 2 Z = y. we argue that ámax / 1)+ E Cmax(y). Since Cmax(y) (v) C by the inductive hypothesis for k. the inductive hypothesis for le follows. Apply Eq. 12 for h, == imax (y) and j & (y) gives
Ah Condition on
(1((( 11 (k+1jh) log
(3,(2hh) (2(2)))
+ 1/2 log Mg(3) Vyax(()
< log
+ 1/2 S log + + 1/2 < 0
Ms (1+1j))
where the penultimate inequality follows from Zeh & B, and j & (y), and the final inequality from 7 1/2. Thus, for all; j & Cmax(y), Mi (z( 138)) > p2 (z(Z(i+ thus innax (28- ((( E Crnax C.na Finally, we argue for [0, N 1] N and (0, h0, kmax (Z E C and kh & B2y Condition on Z v. apply Eq. 12 for = h i == imax (v) and & Cmax(y) C gives
Mt (Z log
+1/2 log (1)(V)
log
+ 1/2 < log 1/2 log(27)
1i (2(
1: (Z)1)
Mmaa (y)
thus Vj & C. Mmaxx (2 2 H. (Z
> (27)- H4 (1,( (2) Combine this with the bound on 25 gives the desired result. Indeed,
VVa 12,, kk)++) in Eq. 11 and using Proposition
4 (27) 25-))
1831.
(2V* VVc(2 )|
Pi
Pt
36

---

Published as a conference paper at ICLR 2024
G ANALYSIS OF LMC WITH APPROXIMATE SCORE
In this section, we prove the main result (Corollary Definition 6. Let HH the graph where there is an edge between i,j iff ||u - -uyll S T. Proposition 27. Suppose a connected component of H then for any i, C, 11ui-uuull S KL.
Proof. For any i.j E there exists path i := Po. Pi. :. Pm = J s.t. l| - up S L. The
statement then follows from triangle inequality.
G.1 EXPECTED SCORE ERROR BOUND
Lemma 13. Suppose μl, satisfies the conditions stated Lemma Let us be as defined Lemmal Fix R C Sn S.R. R = 0. Letp- maXJER Pj. Suppose for j T (SUR), 1|u, unll 2 Lvi S,
with L 2 30 max / 2. kVV) (n(1k)) If score estimate s satisfies E [x]l((()) VV S Excore then
L
Byg [VV Vvs(x)]1 <
3pp ( + 8,3 K exx(
+ 10K2p-B21.)
80k
Proof. Since VVs(2) - p Eies VVi(z), we can write
[VV(2) VVs(2)]] (u(z)ps(s(z))-
E (=)1))))(((/IVVV(
VESJES
(())pSU((()
188. uyllec
VK(+I
Σ
+
M(x)
EES 1E 1
If l| - -usll I L then [vv
VVy(2)]I & 3([1= will + - - S B(2 u,ll + L) thus
the first term can be bounded by
(PsH)(()))-
Σ
(AP)HAH)(()
3(2 x -ull+++11
((x)
1 (x) uyll + L)
iES
I 3
u(z)
SP Sp
where in the last inequality we use the fact that if |/u - -uyl S for some E S then j R and
Pj S p_. Hence, by Holder's inequality
Eps VV(x) - VVs(2) S ([[pp(llss()) - VV())| A A2)
(13)
with Ag = Eys (2 DiEs,jeT ( (z) and
27
(x) uzll + 1.)
A Eys B2
M(x)
JESip, Sp_
(Pams(a)) (1|x uzl1² + Ldd
< 553KK K
us(x))
JES:p,
Pj I pg(x)((1x uzl1² L)dr
5588 Kp
Σ
JES:p,
<
37

---

Published as a conference paper at ICLR 2024
Now bound the term A2. Let T22
S.p, 2p-}.
Σ
Bus
(sPs(E))u())
VES,JET
E (V (EiesJeT, (IPS)r()))s(()))
Eys
(P)))()))(z)²
(z)) VV)( VV) de
Ps
1(xx)
iES.jTT
(=))(()
Ps
Prlp pa
[VV[(z))
VVV
m(xx)
1ES.JTT
L
$ 8ps K K33 exp(
40k
where in the last inequality we use Proposition 29 Plug these inequalities back into Eq. 13 and use Proposition 28 gives the desired results.
L
Proposition 28. Suppose 8 satisfies Definition)
then
E [plllls(>)
VV())l Ps Score
Proof.
PsRpsllle VVV())] = ps (s(x))l(()) VV(x))
/ (psus(x) pss VV
= Ep]lls(>) - [V(x)11 I 20o
Proposition 29 (Pairwise gradient difference for large 11 Ut []) Suppose pix Mý satisfies items
and 3 in Lemma then
Let ui, Uj be defined in Lemma
5 and r ||u -uyl- 1f ar" arraaa222200 /2+es
> 4D
17/16a+3
(x))(x) p(x)
ar cz
Eneus
[VV(()) - VV2(=)11 -V))))- S 83
1 exp (-17a + 16,3
17a
Consequently, suppose Pis Hij are a-strongly log concave and 3-smooth with B 2 and = B/a, and Ilu4 -uyl 2 T. with 2 30 max V.. (n(0m))))))
(p)py()) u(xx)
< 8 exp (-
I,2
P.E
[VV((x) VV((z)11
80k
Proof. By Lemma
5. item 2
[x(
exp (-0l|z w/ll z_ alI= 22y12 24)
M, (x)
exp u - (a + B) u + Cz
where the second inequality follows from ||u, - 12112/2 & (|(x - uill + || uill2 +
Ug 11)2/2 s 1|
||
12 thus
(r))(r)
Pjp (x)
H(|lz-us
((x)
Pip (x) + (ppu(x)
(z)
(2)
38

---

Published as a conference paper at ICLR 2024
where
H(y) = 1 + Ps exp( ( uyll (a Bby + c2)
Let A = Ex (11 - uzl uz]1²]] and B = Ba ||| / - uzll Using the fact that
[[V]((x) - (x) - 5B
- -u.l - = 24 -uil + llu - uy 1|²),
can bound
E En-ss
(2) u(x))
[VV(xx) - vV5(E)11 S (r
First we bound A. We have
E, (112 uy [0]13)]
H(I uil (x))) //E-uullee H(I uzll pxll))
P aun 2 uill 2/ R + H
- (B) + exp( 2
a (a
where the second inequality follows from H being an increasing function bounded above by 1, and ar2 /2+c, at.3+a/16
the third inequality follows from (y) S P, exp(=arr + (a B)y c2). Set 18t
then 2 2D thus exp(-o R - /)3 I exp(-aR (R((-R exp(-or2/2 /2- + (a + 3) c2). Hence, the rhs is bounded by 2p, exp( or /2+cs
T7c+1633
Now we bound B. By Holder's inequality
B, [| 4/| 1 H[| vull3)]
B,, ||| - 2111 / Ep,, [H2([|= 13
$ D2 V P PaNmill ||| - will 2 Rl + H2(
< D2 exp(-a -)33/4) + p; exp(-200 2ar + 2(a + R) 2c²)
where we use the sub-Gaussian moment assumption to bound E,,, - uu|l=] and the same argu- ment as in the bound for A to bound E,,, [ will3), noting that (+) is also an increasing function bounded above by 1. Set R²2 ar /2t then R 2D thus exp( exp(-a(Ri D)2 s
a+b+a/32
exp(-aR2/10) /16)- exp(-2(ar2 (a R3 cz)). Hence,
or 12 Cz B < 2D' 1 exp(- R2 /2/32) 2D2 p; exp (- 33a + 323
For the second statement, plug in D 5 _. In(10x) and c₂ - In(n), and use the fact that B 2 1, we have
0.45ar
3d
2 80 x In 110x)) = 4D²
17a + 163
333
a
Thus by Proposition
and the fact that 2 > 2n. p2 expl
ar² /2tcs 170+10 163
S 1 expl 80w
L exp( L2
80K
Theorem 6. Suppose each μ; is a strongly-log-concave and 3-smooth for all i E with B 2 1. Recall that |/| K. Let i, arg min Vi(x),, p. miniel pi, K = 3/aa. Set
Lo = θ 2 KV (dd[([() + exp(K) In(p, ((()) = 0(k2 K (xp(K))V)
Let S be connected component of IH', where there is an edge between i, j if llue u,ll < : Lo/ (R.). Let U sample be a set of M i..dd samples from ps and Usompte be the uniform distribution over U Unmplee. Let (X nh
mEE 2 be the LMC with score s and step size h. initialized at Vsample. Set
2((3/2) 1-1)
(0dd(3L))exp((A In 3/2 (/3/(pp1))
In 16d(3Lo)
T = 0
a - K22 mmm00pp))))
eTyTa
pt 2 a3/2
7/2
39

---

Published as a conference paper at ICLR 2024
Let the step size h =
Gr (3Lo]
=
cry [BK [xp(())4dd7
Suppose s satisfies Definition with
Ecome
1/2
Gv
P+
7T
1/2
-
TTV
(BLO)2TT/
Pa
1/2 1/2
cTV
(BnRK exp( )))(K)))33/270777
3(3322)
p²c4va332 3/2 K3 I3 (3Lo)2 (exp(( K) In 3/2 (p2 (f=²)
p²
CTV 3/22
3
=0
16d(Ht))
TT
Suppose the number of samples M satisfies M 2 40000p CTV TiykK K22 log K (KTV)) log(T-)) then
Pu drv (C(X) suampte); ps)) <rv] 2 -
Corollary 1. Suppose 14 is strongly-Ior brooggl-log-coneee log-ccnvvee and 3-smooth for all i with 3 2 1. Let
p- = minker Pi- Suppose s satisfies Definition 7 Let Usample be a set of M i.id samples from and Veample be the uniform distribution over Usaplte With T, h, ewore as in Theorem 6 and
M 2 20000p,"<7t log( K KTVV) log(Kr=1). Let (X")nmi)
Ynek be the LMC with score 8 and step nh
size h initialized Vsampie: then
Pu ( "i
U Unmppte): 1)) S
Proof. This a consequence of Theorem and Proposition 31
Here we apply Proposition with
Mo 4000p. GV K2 log( K GTV log(r-)).
Proof of Theorem 6 Let u; arg min, Vz(x) then VVi(u,) O. W.L.ogg.
assume (.(),)
By Proposition
27 ||u, u,ll L KL Lo/K for i,j S. By Proposition 17 with
Ug = Ps Eies P,u; S satisfies Assumption 2 with Agndd, = 3, Agrad = 3L, AHess11 = 2,3 and
Atess, 2.
We first show the statement for M Mo 600p- K2 (log ()) where we set r CrV, then Proposition 30 obtain the result for M 2 1000p--e.p Kdd log K KeTz)) log(T-1) 2 6. log(E
From this point onward set T = erV and M = MM as defined above. Let (X nh )eN be the LMC
with score estimate and step size h initialized at μs and (X!") be the continuous Langevin diffusion with score VVs initialized at ps. Let QT and QT denote the distribution of the paths (XAR) (o,T//jjj and (X("))eE(or)) )te(o,T)- Note that 2 5lk.ddn((00k) 2 10D, Lemma 15 gives
2drv (Qr. ) S 2 L + 2hT L +T
with L 3p's (c + + K exp( 1,2 )). Let e2 ccore
Sx and B -s(
Se
Escore,1) then by Markov's inequality BBB) <
Spar
Tv
Let n = ETVT. Suppose Te < 1//100 and s (100)- -1 mint (B (3L)+aT drv(QT, QT) S 11/4, thus
n
then
PPnn E [0, N N
8 nh
E B P(nn E -
X
Rus nn
E B] + drv (Qr, Qr)
T
<
A
+ ETVT/4
h
40

---

Published as a conference paper at ICLR 2024
Since Bninptte [/sampte] JAs; (i) Unaute [L ( (usmple)) )] and
Ussuse F Bn N - N "omple B]] = P[ O IJNN: X E BJ S A
By Markov's inequality, let Eg be the event Py, An [0, N - X
B - 2A1/T then
Puamp [Eu occurs] 2 - T/2
Suppose En occurs. Let := Paample- Let (Z OIEN be the LMC initialized at with score estimate 8xc defined by
if
500 (2)
(Vs(2)ifrEB
then SuR (1) VVs(=)112 2000e.1-
Note that Xnh & Byn E NO - 1]nN then Zu X"Manok E [0, N thus conditioned on Eg occurs, drv (ZNE (ouno Xumne
.NN 2 2A1/T. Let (Z (uuuuee) )r be the continuous Langevin with score VVs initialized at v. We want to bound drv (ZNr "oann Zy ). By sub-Gau Gaussian concentration of
H4 and union bound over M samples, we have with probability 2 1 r/3, the following event E happens:
sup max || u,ll S = :0:==224
+
Va
4
In(
8M
S 3
any
since for 2
1,
In
SM
& 3/2
v /I((ETV) L.
Let & be the event
drv (Tv(L(Zzg oo Usample); ps) S <TV /4 M. 2 60 -2k
By Lemma 11
K2 log( 11- then Grane {&g] 2 1 -T/6.
Suppose Eo, & & all hold; by union bound, this happens with probability for
By Lemma 14
Lo = - + V In((2(h)-))+ + v (16/a + 200dh) In
8T
h
we have
drv "rance Zn $113333 4 hTd3 + 1/22 e/v /64
if 100h
< (3Lo) dT
(
By triangle inequality
drv(C(X Xh U sample)): ps)
< drv Naano Z
drv Vampi 2"ammee drv (LTV( 1 pS)
167 2 2
+
+ 5 <eTV
hepp
1 Eaxes h
S ET.
Our choice of parameters satisfies all the conditions mentioned above. Since h < 1/0100d,, , 2 1 and i. 2 / á In(10n) 2 Va In(a-1). bound Lo by
17
8T
Lo < 2Îx + V In((22))-11) +
In
h
17 In(87) +21n(11h)
d+1
< 3i. V
a
= 3în exp(K) Vvd(K)Vkdln(pp) de Lork)
41

---

Published as a conference paper at ICLR 2024
where we use the bound on T and h to bound In( and In(1/h). Set I. (0kv0Il(10ss) + Vnd In (nnddp/ddprpa Since 3x Lo S 5kL,
Lu = O (((n(O)()) + cxp(K) In dp_ (100%/c)))) (V))). ))).
cvv but this is true due to the choice of h. Next, we need to check
We need to check that h S (BLo) dr
167 Saree. I CTV /8 and T Geore. S 10 /70/10. We note that the former implies the latter,
and the latter is true since
1/2
7v Vh
Ps
Cecore I
7T
and
L?
1/2 BV exp(
YT S /
Ps
160k
which in turn is implied by
L/ cxp(K) In(dkp. GVv 2 5ln (Th 1annThh13K cv)
which is true for choice of L, h and T.
5 suppose ||u: - uuyll S LVi,j E with 2 10D. Let Vo be a distribution s.t. suP maxies ||e well S L.. Let (z2)) the continuous Langevin with score VVs initialized at My. Let (Zhh)et be the LMC with step size and score 8xx. s.l. SupZER= [|s(x) VVs(+)] S e Suppose S 1/(303) then for δ :=
Lemma 14. Fix S C I. For un and D as defined in Lemma
(0 IL + v _ In((2ah)))1) +
69 0
16 + 200dh) In(NN) we have
div ) s D -hTd D +
+ Soom, T/2
Proof. To simplify notations, we omit the superscript vn and write Zun and Ze in the proof instead of 2e and Z Let Ti be the distribution of Zn, First, we bound (2 (s)). (1)))))s)) By Lemma 10
R2(Pxllus) < ((a "(si= + d(In((2h))))
By Proposition 17 let us Ps LiES pru; then μs satisfies Assumption 2 80
Pusllx - usll 2 1.11 + t] S exp(-at? /4).
Let T/h. By the change of measure argument in (Chewi al. probability n
2021
Lemma 24), with
|| 1uth usll S 1.1L + V Ro((ullus) + 1
2 2
8N 17
max kE[1,N 1|
in
8N n
< 1.1L + kL. (aalnn(((2)))1) + V
By Proposition 19 this implies that with probability 2 - v), for 7 a
16
200dh
t [0 1| usll < D \n/n(11n)
sup
with D = 6L + O + Va- (a-Iddn((2ah)]1 + v/ In()). By Proposition this implies, for p O()
El||Z, usl
u 1'| < ( vT)² S D
where we use the fact that VTS V 11 < D/50.
42

---

Published as a conference paper at ICLR 2024
By Proposition 18 for E [kh, (A: + 1)h].
B VV Zan) - (2()
- E
[[A Hess, 2KA - us|| + 2| - 1s|18) + A Hess,u
x xV(L (1 kh)s (" (A B1|1 - us|1a] + A grad + d2 khi)
kh
(A 03 + H) (A .32 Agna,o) dh)
2 (Tx + 322) + 1.2) + dh) ~ 8 (12 dh)
where in the second inequality, we use the moment bounds for 1|2, - -usll. in the third inequality, we use Proposition 17 to substitute in the parameters 1 AHess 0. Agrad, 1, Agrad. and in the final bound, we use D 61. Then by Girsanov's 's theorem (see Lemma
2drv ( ZT. 2
1B/
1| [10(Z(e/n))) -
VV(2))
S 2 1 T + E1 (Z1//Z))) - (V(2))
$ 2or,, T + 36 T6 + hT
Lemma 15. Suppose the score estimate s satisfies Definition 7 Let and D be defined as in Lemma 5
Let S be a connected component of H with L > 10D. Let (X menN be the LMC with score estimate s and step size initialized at μss and (X )120 be the continuous Langevin diffusion with score VVs initialized at us. Let Nh, Qr and Qr denote the distribution of the paths of (XPS) ( (eto,T/Mi and (X!$) ) Then for I, L.K,
2drv(Qr, Qr)² < E 1/-0 [1s(S (tAAj)) VX
2h 80 + 2hTTB+ T score00
with ".core = 3p5² (5200m + 1, exp(
La 10x ))
Proof. By Proposition 27
|lu u < i for i,j E S and ||u; - uالس > L for i E S, & S. Note that since ps is the stationary distribution of the continuous Langevin diffusion with score Vss, the law of X is ps at all time t. Thus, for t E [kh, (k + 1)h]
[[Il=(( VVs(XX
S 2(EIIlss VVs < 2 + 3 (h? + dh))
(Vs(X (X.")())
(14)
where in the second inequality, tion 19 and Proposition to bound the second term. The argument is similar to the one in the proof
Lemmal 13 with R @ to bound the first term and Proposi-
of Lemma 14 Let ug = Ps Eies pru; then ||u -usll < LVi e S. For D = D + L < 1.1L and
7 4 since the law of X is us, by Proposition 17
P|| usll > ò + / ln(1n)11))) In
43

---

Published as a conference paper at ICLR 2024
thus by Proposition 2 and D 2 1100/a, for p= O -sllp 2 DP. By Proposition 19
E V (Vs(X (1)
L2) + dh)
S 8 +dh)
The statement follows from integrating Eq. (14) from 0 to T2 and Girsanov's theorem (see Lemma 3
This proposition is used Theorem to go from a set of samples of fixed size Mo to a set of samples with size M that can be arbitrarily large.
Proposition 30. Fix distributions Usamples μ.. For set U sample S Rd let (X, be process initialized at V Vsample: the uniform distribution over Usmple.. Suppose there exists T O, crv E (0.1) s.t. with probability 1 erV /10 over the choice of U sample consisting of My i.i.d. samples from I Haumlee; drv ( L X [Usmaill (Usample) 11) S eTv/ /00. Then, for M 2 BeTV Mo log(r-)), with probability T over the choice of U Sample consisting of M i.id samples from Psample
drv ( (ara
1 (sample):: ) 11) eTV
Proof. Let Usample be a set of M i..d. samples ,z(1), ,... " (M) from Muample- For r E
{1..... M//Mo] Let U, = fx(1) (r- - 1) + I rMob} and Ug = U sample \ U. Ur. Let
V, be the uniform distribution over U, and vy be the uniform distribution over Ug. For [M/Mol
Mo Σ
M - Mom
Mr
V0
M
M
Let Ω be the set of U E Mo s.t. drv (X% 1) S crv / with v being the uniform distribution over U.
Similar to the proof of Proposition 23 if we choose M/ GC log(r-)), ) then with probability
T, lt: U, E QH Z m(1 <Tv/5). By Proposition
Mo drv (C(X))
M Mam(1 - 5TV/5)
drv (C(X"
"ampi (e (usmple) H²)
Σ
M
M
ER
I e e/v - crv cTv/2
where in the penultimate inequality, we use the definition of Ω Mom < M and M - mo S Mo S M/6.
The following proposition combined with Theorem Glimplies Corollary !
Proposition 31. For Usampic C Rdd let (X"nooh) ) be process initialized at the uniform distribution over U sample- Consider distributions PC for C E C. Let μ = -E PCPC with Pe > O 0,e
Let Ps min PC- Suppose there exists ability 2 TO over the choice of UC, sappeee consisting of M 2 Mo i.i.d. samples from H.,, drv (C(X" (mp ( sample))) Hc)= S ETV where VC, is the uniform distribution over Uampeee Then, for M Z minp. [Mo, 20cTy log([Cr--1) with probability 2 - T over the choice of U Usmppe consisting of M i..dd samples from p.,
and Σ pC
(0,1) s.t. with prob-
drv (Tv( Usampte)..)) S eTV.
Proof of Proposition 37 Since μ = Ec PCHC, sample (() from μ can be drawn by first sampling ((0) E C from the distribution defined by the weights {po}cec. then sample from Pots. Consider M i.i.d. samples (6) using this procedure, and let Uc {z(() C00 CJ. Since M 20p. ETV> and E||Uc|] = M,, by Chernoff's s inequality and union bound, with probability - 7/2 over the randomness of sample: the following event ε holds
lUcl M
YC:
pcl S PC
44

---

Published as a conference paper at ICLR 2024
Suppose ε holds. Then, Wel pc(1-crv/ c2v/2)M 2 Mo. Thus by union bound, with probability 1 1 Erv 10 over the randomness of samplee the following event &g holds with ve the uniform distribution over Uc
AC (r::dv(((()) (C). & erv/10
then let it = Eo
[Te M MC: by part of Proposition 9
drv (f
(1) = drv
Σ
[icl c(xx91Vo))
Licl M eTv
and drv p)) S Ec probability T, We have
Lcll Pol & c2v/2. Condition on E and &g both hold, which happens with
drv (( (
(Uample): ): p1) s (C(x) (Usample)) ),1b) i3) + drv (ir,
S 6TV <Tvv 10 + <TV 2 5 CTV
H REMOVING THE DEPENDENCY ON p. minger Pi-
In this section, we remove the dependency on the minimum weight p. minger Pt- The idea is
to consider only the components μ4: with significant weight p; i.e. Pt 2 Ptreshold for some chosen threshold Pthreshold- In Lemma 17 Theorems and g and Corollary 2 prove analogs of Lemmal
Theorems and and Corollary resppettvvely with no dependency on p..
We will need modified versions of Lemmal 12 and Proposition 25 which are Lemma and and Proposi-
tion 32 respectively.
Definition 7 (Bad set for partition (modified)). Fix SCI,C, S S,S = S \ C.. Suppose we have partition C (CI,.... Cm) of S'. For x E Rd, let imix, = arg maxies pi(a)) and Mmax, (x) = (s)) = maxies' pa(x) as in Definition 4 Let Cmax, (x) is the unique part of the partition C containing (x)). For E (0, > Olet
Bs.c..Cmm
= { E S' S umax, (: (x) S S > or 3j E C. Mmmx, (x) S n. (z))3
Note that if C. then Bs,C. context, we omit S, C.,C in the subscript.
Bs.c.r as defined in Definition
If they are clear from
C be partition of S' S C.. Let ps Eies Pi and p: P:P's Recall that μs Eies Pille For y, E (0, 1),
Lemma 16 (Bad set bound (generalized version of Lemma 12) Fix
define B., = Bs.c..C.v as in Definition with 7- = > 18/8. Suppose
1. If E C. then p. 5/8
2. 6i < 8 forri which are in S' and are not in the same part of the partition C. of S!
then us us(B)) 28K2
Proof of Lemmas 12 and 16 C. 9 in Definition
We prove Lemma 16 then Lemma 12 follows immediately by setting
Consider x E B., s.t. (x) = For E S", let C(j) denote the unique part of the partition
C containing j. Let lo mmx 2, (x) arg maxxess (z). If C(i) then by definition of
i (2) - (x) < (x).
If E S" C(i), then by definition of k, (1(x)) I po(x). Let
By = {x Bj E S' C (x) Mmaax (x) S x ~,111;
and
B, (x Aj E C. S S v5 3 (z))
45

---

Published as a conference paper at ICLR 2024
Let pj PyP''' for E S. I I. E 2 and for
ps(x)) [pl((()== = E Piu((z)+
+
E P)p((1)+
+
Σ
Ps)((()
JEC(i)
JESNI())
JEC.
< Σ (yUa(z)+ +
E PsUe(T)
+ Σ 1)1((x)
SEC(()
jESMO()
jEC.
x Σ Poy (x(x)) + Σ (s))(x)
JES'
jEC.
S px(x)+ + Σ (zH((0)
jEC.
Let Pc. := Ejec. Dj then Pc. K x 8/8 v 7 since 7 > 1. For i, E S" let S2 be
the set of x s.t. ( = and max 2.5 (x) = k. Since {Ri,ll k E S", c()) & C(k) forms partition of Rdd, we have
Ps(BB²)
Σ
us(a)dx
Σ
(x()+ + Σ (z))
(k:C())((()) NEB
jEC.
=7- E
(LEE
px(x)dx + /
1e (x)
+ Σ
Pj
Σ
EB
jEC.
i.k
=
Σ
(in( +
Σ P3
(C(()
JOE ((PAAU))))
JEC.
S--1
Σ
8 8 18K88
(K(0000(())
SS
5K/8
where in the penultimate inequality, we use the fact that dis < for i, k which are not in C. and not the same part of the partition, and p5 S 8K/2 S 7 18K/2 for j E C..
For i E C.,, let 92 be the set of x s.t. mmax,C. i. If 22 0 B, then
us(x)= Σ
(1) + Σ (1) <
Σ ())((z) + Σ
Epni-uua u(x) mi(x)(fc. +,.4).
JEC.
JES
jEC.
jES
Thus
(s(BB) = Σ /
iEC. meBBnnn us(z)dæ
Σ
(Pc. + + (
iEC. DEB,nn;
(pc. + +r,1)
Σ (. n0)) s +
iEC.
where in the last inequality we use the definition of 7, and the fact that (B. (2))) S 1. Thus by union bound
μs (B(Bs.c......)) (B( + ps(B.) 18K2.
46

---

Published as a conference paper at ICLR 2024
Proposition 32 (Absolute gradient difference bound (generalized version of Proposition 25 25 Fix
SC C. C Let S" =S²C.. For E S, let p. = PiPs and recall that μz( Liiss (i)4:(). Suppose P3 - á for E C. Leti: == St arg max (x). Suppose i E C C S" and
1. mx(x)= T 1 ()(+)
2. (1)x)= v. (y(ز) e C. where =7-88888
Let Gs(z) s [V((=)]]
then
4y Gz(z) P.
(Vg
Proof of Proposition 32 and Proposition 25
We prove Proposition 32 then Proposition 25 follows
immediately by setting C. = 0. For C' S S, let Pe = Eiecr Pi. By Proposition 6 we can write
VVs(2) - VVc(z) (cpc(r)Voolz)) + Pi
VVc(2)
ps(
VcVo(=)VVo(z)) +
VVc(2)
po)c(() PiH((()
(iH((x)
(VV((x) - VVo(z))
jESiC PCNc(x) (ilb(()
For j E 5¹ C,
pC)c(x) - Eresrc (x)
Dell(())
P: -
2
(z
Pj
and for j E C., using the upper bound on Pj and the assumption 14(2)) 2 7x 11 (x)
())c(x) Pr
P((((T)
P:7e
2 p
Djpg (x)
P)(((x)
Dj
Next, by Proposition 6
[Vc(x)]l s Gs(x) thus.
- -Vo(ll) =
Σ
D
+
4yGs(z)
(ES((CUC.)
Pi
jEC.
Kp;
The following is modified version of Lemma 1I
Lemma 17. Fix Crv, T E (0, 1/2), E 10. Fix Eies Pilt. Suppose for E S, p4 are a-strongly log-concave and B-smooth with 3 > 1.Let
= pe
and recall that ps
w; = arg min, Vi(x) and 2 5/ a as defined Lemma Suppose there exists 10D such
that for any i E S, 1|u uzll S L. Fix p. 0. Let S' {iE S Pa 2 Pa) and C. S S' Let
G = (S', E) be the graph S' with edge between i.j iff deg 8. Let
T 2Cp.,K
[nn( (
L In In 21n T
8a
and
g 3/2
5/2 CjyT
8'
10S 10 k3 In 3/2 (p. 3/2 Ba Lepy Inr-1
In 2.51 16d(31) erviba
Suppose maX Di 8 andfor all i.j in S' that are not in the same connected component of G. 8'.
For E Rd, let (X.' "izo denote the continuous Langevin diffusion with score VVs initialized at d Let S' be the unique connected component Gf containing imax, (z) = arg max μy (z).
P Pa-py (dr (L(X)- (x:), PC ()))).s((()) S <Tv]
47

---

Published as a conference paper at ICLR 2024
Proof. The proof is same Lemma I1 but replace Lemma 12 with Lemma 16 Proposition 25
with Proposition 32 and Proposition 21 with Proposition 22 Note that we use y
p.5r
100L,T
and By as defined in Lemma 16 to ensure that for & By, VV Cmoo. st (w) (v) VVs(y))l -
4y(0L (n(BLerir +T))
10yT so that we can bound the total variation distance between the
ETV
P.
continuous Langevin diffusions with scores VVs and VVC by erv/10.
Theorem 7. Fix CTV, (0.1/2). Fix S S Suppose for S. μ4 are a-strongly log-concave and 3-smooth with 3 2 1. Let u, arg ming (z( and D 2 5/ a. be defined in Lemma 5 Suppose there exists 2 10D such that for any j.j E S, ||4; - 1011- L. Let Usample be a set of M ii.d. sam- ples from sag and Usample be the uniform distribution over U Vample- Let (X, (Xpausi )a20 be the continuous Langevin diffusion with score ps initialized at Viample- For Z 10 10 K log(K= and
(LL (x)(K)) In 16d(3)) exp(20(K(13)
T T2 a
crya
7//33/2
then
Pu Un ldrv
[Usample); us)) S [rr]211 1-
Proof. For i E S, let P. = P&Ps As in Lemma 17 fix Po,* = K and let So = {i E S p
Po,+),Co Co.. = S \ S then Sy * 0. since there must be at least one i s.t. P: 2 By the same argument as proof of Theorem [ we take the sequence
50,0 80,
> 50, where we
use the notation òū,- to emphasizes its dependency on Po.. If max P4 60.x then Lemma 17 applies. More precisely, we will use Proposition 24 and the inductive argument on d0, as m the proof of Theorem 5 to show that the continuous Langevin diffusion initialized at M samples will converge to μa after a suitable time T defined by 60, If this is not the case, then we let P1,- = 6a.K and S = (i E S P: 2 }1,.} then |S|| 2 |S] + 1. In general, we inductively set Ps+1,- = K.K. If max,ec.. Pi S Ps+1, for some s < K - then we are done, else CK-1.* = use Theorem 5 In all cases, for p. 1x-1, the continuous
8
thus minkes P; 2 P,- and
Langevin diffusion initialized at samples converges to μ48 after time
T> θ a K2
O(a - exp (0((+))))
To justify the above equation, we lower bound p. = PK-1, and 6 -----
2/2
2. 3/2
Let Le
164 then rvve
suood((L))xxp(kk (p,,))
16arer)2
10 202d lnd
ervo
8 > 8,,K 2 (2((3/2)<11_)
(302
DE
Ps.*
with E 107d((0))exx((K In 164
3/2 3/2
2((3/2) and we can prove by induction on s that
Ps,* 2 K
1(x)(4
thus
6 K-1,K-1 E (PK-1,
3 (==m((49((+))) 7.00)/)))) .3-1
< E exp(12(K+1))
48

---

Published as a conference paper at ICLR 2024
Theorem 8. Suppose each μ4i is strongly-log-conee concave and 3-smooth for all with 3 2 1. Let 2 arg min V(( Set
Lu = = (nde
Let be a connected component of THI, where there is an edge between i, if - uyll I. Lo/ (KK). Let U sample be a set of M ii.d. samples from js and sample be the uniform distribution over U sample. Let (X X NEEN be the LMC with score and step size h initialized at sample Set
exp(20(
((xx))))))xx(((3 In 16d(BLo)
T a
crva
dry (Bta)=dT) p. Gry 72
Let the step size = O
Suppose ps Z R and s satisfies Definition
2/2 Vh
with Ewor S
I
Suppose the number of samples M satisfies M 2
TVKT
10 "VVKK K log KeTv log(T-))
then
U ldv (dr (C(X
Usampte): ps) S [TV] 2 --
Proof.
The proof is identical proof of Theorem 6 but we plug in T from Theorem 7 instead of
Theorem With the same setup as in proof Theorem 2 thus as long we assume ps 2 K
Eccore.u = 3p. (c ( +832 exp(- 80K
we can ensure that with our choice of L and Escores Escore,0
1/2 2g. Vh
Ps Cryy as required.
77
Corollary 2. Suppose μu, is a strongly-log-conee concave and B-smooth for all with 1. Suppose Let U Usample be a set of M ii.d. samples from and V Vample be the uniform distri- satisfies Definition [
bution over U sample- With T, h, 2 Looore as in Theorem and M 2 10 TTV K" log K KeTv) log( rT- Let (x "EE be the LMC with score and step size h initialized at Vsample then
Pu (f(x Maoooic
U Usmmpie) ). p)) S SErv] 11
Proof. This a consequence of Theorem and Proposition 33 Mo 10" 10 5 log(K KeTy) log (Kr
Here we apply Proposition 33 with
To remove dependency p., we will use the following variant of Proposition
31
Proposition 33. For set Usample S. Rd, let (X" be process initialized at the uniform distribution Veample over Usample- Consider distributions pe for C E C. Let μ =EecH with PC > O and LPC PC = 1. Suppose if pc 2 CTV there exists T > 0, erv E (0,1) s.1. with 8.C.. probability 2 10|c over the choice of UC consisting of M 2 Mo i.i.d. samples from H.C, drv (L(X)) C (UC. S crv/10 where VCC.samlle is the uniform distribution over Sappte Then, for M s/e > min,(Mo, 20c log((C)r-1)), with probability 2 - over the choice of Usmptt consisting of i.i.d. samples from μ. drv dTv(L(X) Mhaapu (usappe); ()) eTV
(L(X")
Proof of Proposition 33 spell out the differences between the two proofs. Let C' = {C E pc 2 sic }. We redefine the event E as
The proof is analogous to Proposition 31
We use the same setup and will
Ucl M
VC C'
pol S pC
and Eg as, for ve be the uniform distribution HC
YC C' drv( S eTV/10
Let Up
Usample \ UCEE C' Chen
Ug
Eoee |Vcl
$1
Σ
s CTV/4. Po(1 /8) < crv/8)(1 -100))8)11)))))) (
M
OEC'
49

---

Published as a conference paper at ICLR 2024
Suppose E and Eg both hold, which occur with probability by Chernoff's inequality. Let Wel Ecee M pC. By part 1 of Proposition 9
Ucl 1( Σ
[ecl M PC
drv ( (o (Usmpe) (2) = drv
M
Ucl
|Val M
1TVv110+ +
S < + 5
M
CEC
CEc
By part 2 of Proposition 9
Uccl M
Ucl
Pcl S
Σ
pCeTv/8 /8 Σ
max
.pc) s /8 + eTv/4 M
CEC
Cgc
By triangle inequality drv (L(X) (x (sample)) p1) S drv (drv([(()) (L(X) (Usample) (3) + drv (1),
$ <Tv /2 3eTv 10rvv8820 CTV
I ADDITIONAL SIMULATIONS
In this section we give some additional details about the simulations in the main text as well few supplementary ones.
For the simulation Figure of the main text, the estimated score function was learned from data by running 3 x 10 steps of stochastic gradient descent without batching, using fresh sample at each step with learning rate 10 The loss function was the vanilla score matching loss from Hyvärinen (2005). The neural network architecture used had single hidden layer with tanh nonlinearity and 2048 units. The stationary distribution shown in the rightmost subfigure was computed by numerical integration of the estimated score.
For the 32-dimensional simulation in Figure of the main text, to train the network we used ADAM with batch size of 256 examples, again generated fresh each time; used 200 batches per epoch and 300 epochs and we learned the vanilla score function using an equivalent denoising formulation in Vincent (01T). Figure is the same but the network we performed the same experiment as Figure 2 but we used Contrastive Divergence (CD) training Hinton (012),, which has been used by numerous experimental papers in the literature, instead of score matching as the mechanism to learn the approximate gradient. More precisely, we used CD (again trained over 300 epochs) learn distribution of the form (x)( where the potential was parameterized by 8192 unit one-hidden-layer neural network with tanh activations. Once this network is learned, V was used the approximate score function since this is the score function of the learned distribution. We also observed in Figure 5 that the score matching loss, which was explicitly trained in the other figures, is also monotonically decreasing over time under CD training. The fact that the behavior is somewhat similar under CD and score matching is morally in agreement with theoretical connections between the two observed by Hyvärinen (2007b). Note that in all three of these figures, the same random seeds were used so that colored trajectories will correspond each other.
trained for only 30 epochs. In Figure
50

---

Published as a conference paper at ICLR 2024
-0
-1
(a) 300
(b) 12000
(c) T 120000
Figure 3: Failure approximate the ground truth with less accurate score function. This is exact same simulation as Figure 2 except that the network estimating the score function was trained for 30 rather than 300 epochs. We that while the short time evolution is similar, moderate times (Figure (b)) the output of the dynamics have drifted away from the true distribution due to accumulation of errors and in particular one trajectory has escaped far right of the rightmost component.
(a) T = 300
(b) T = 12000
(c) = 120000
Figure 4: Variant of Figure where the approximate score function learned via Contrastive Diver- gence (CD) instead of directly trying to match the score function. We used the most basic/efficient version of CD, with only a single step of Langevin dynamics, and used larger step size of 0.05 when sampling in the training loop compensate for only taking single step. Qualitatively, the behavior seems similar to Figure - large times, while none these particular trajectories crossed between components, one trajectory escaped into low-density region left of the leftmost component.
Score matching loss
0.6
0.5
0.4
0.3
50
100
200
250
Epoch
Figure 5: Score matching training loss (preciscly the same loss used to train the models in Figures and 3) curve for the CD-trained model in Figure [ Although the score matching loss is not being explicitly optimized, see it goes down monotonically over the epochs of CD training nonetheless.
51


Reviews:
[{"review_id": "FguqQVEHzV", "reviewer": "Reviewer_94gx", "summary": "This work studies vanilla score matching in the context of mixtures of log-concave distributions, providing a recipe to learn multimodal distributions via vanilla score matching, a procedure that has provably failed in most multimodal settings: (1) data-based initialization for the Langevin Monte Carlo chain; and (2) early stopping of the diffusion. The work demonstrates substantive theoretical developments for the proposed method, along with a few toy examples to illustrate the effectiveness of empirical distribution initialization and early stopping in learning mixture of Gaussians.", "questions": "1. Could the authors comment on how the contributions in this work might help in improving diffusion models as a class of generative models?\n2. Can optimization techniques such as exponential decay learning rate schedule achieve similar results as early stopping, in the context of estimating vanilla score function of a multimodal distribution?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This work aims to tackle a widely accepted issue of vanilla score matching that motivated the usage of annealed langevin dynamics in learning multimodal distributions (diffusion models as a class of generative models) — it has the potential to inspire new algorithms for generative modeling.\n2. Code for the toy examples is provided via **Supplementary Material** to facilitate reproducibility.", "weaknesses": "1. Experiment results do not appear to be convincing enough:\n* The ground truth distribution is not plotted in Figure 1 (b); by comparing to Figure 1(c), it’s not hard to tell that the weight of the component on the right is not learned very well — one has a density around $0.15$, while the other around $0.125$. Meanwhile, there is no numerical computation on the learned mean and variance of each component, and how they compare to the ground truth.\n* Similar to the issue in Figure 1, the values of the learned projected mean, variance and weight of each component, and their comparisons with the ground truth distribution, are not reported for the experiment presented in Figure 2.\n2. It’s not clear how or where early stopping is proposed as a solution throughout the theoretical development.\n3. Some minor issues in writing:\n* Page 1, first bullet point of positive aspects: “a simple closed form solution <when> the class of models”\n* Page 3, the line above **Theorem 1**: “samplling”\n* Page 3, strange expression: “Note in particular that we have can draw as many samples as we like”. Perhaps remove “have”?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WmF3oD1Soi", "reviewer": "Reviewer_vctH", "summary": "The paper analyzes Langevin sampling with approximate scores, given some samples of the target distribution are provided.  It is shown that the scheme initialized from a uniform distribution over the available data points generates a sample close to the target in TV distance when stopped at a finite time T. The considered targets are mixtures of strongly log-concave measures and the paper's focus is on showing that with data based initialization, it is possible to remove the dependence on the LSI constant of the whole mixture in Theorem 2.1 of [1] which studied the same scheme.\n\n---\n[1] Lee, Holden, Jianfeng Lu, and Yixin Tan. \"Convergence for score-based generative modeling with polynomial complexity.\" Advances in Neural Information Processing Systems 35 (2022): 22870-22882.", "questions": "- *Number of samples needed, Proposition 23 (and 24)*: From my understanding, for the approach to work, the available samples must have the correct weights of the components. Could the authors explain why the $M$ does not seem to depend on properties of $\\mu$ besides the number of components ?\n- *Samples to train and samples to initialize*: Presumably the approximate score is learnt from the same available samples $M$ used to initialize. This dependence could break some concentration arguments. Could the authors briefly discuss whether it is necessary to hold out some samples for initialization when learning the score ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "*The paper formalizes an intuitive result*: Sampling from mixtures is difficult because it is hard to transition in reasonable time from one component to another. If it was known where the mixtures were as well as their relatives weights, then no transitioning would be necessary and sampling could easily be achieved by initializing inside the components' typical sets. This intuitive natural idea (dismissed as too obvious/unrealistic in [1] sec 1.2)  is what is formalized in the paper. Although the result is not very surprising, the authors go through the laborious task of linking the components needed to establish the result: data based initialization with the existing analyses on approximate scores(or inexact langevin) and discretization of langevin diffusions. \n\n *A clear and easy to follow proof outline*: There is a nice simple setting that is detailed in the main text to understand the paper's strategy, which is quite useful since the paper's result requires lengthy combinations of several results.\n\n---\n[1] Lee, Holden, Andrej Risteski, and Rong Ge. \"Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering langevin monte carlo.\" Advances in neural information processing systems 31 (2018).", "weaknesses": "- *Structure and unconvincing arguments*: Some sections could be better restructured namely section 1.2. It jumps from motivation to related work to possible extensions. Some remarks can also feel a little unconvincing there. For example, computational hardness arguments are invoked in the motivation but the main idea of noised score learning is to have an annealing scheme where the denoising is only performed from one noise level to a slightly lower noise level. Annealing breaks down the difficulty of denoising, so the paragraph is criticizing an alternative that is never used. A further minor point: remark 5 is an excessively long paragraph to say the mean is not in the typical set in high dimensions.\n- *Log sobolev constant for well connected mixtures* : A contribution of the paper is extending the Poincare inequality through decompositions result of Madras & Randall (2002) to the log sobolev inequality. It would be very surprising if such an extension has not already been done as the result is old and functional inequalities are heavily researched. I would kindly ask the authors to check and possibly include references [1] to ensure that they are not missing prior work.\n- *On significance*: For the MCMC community this result will not be worthwhile as samples aren't available. For generative modeling where there is a dataset, the better modelling of what practitioners do uses time-varying score functions and so what is done in practice does not correspond to Langevin with a time independent score. The \"long line\" of experimental work that uses vanilla langevin is claimed to exist but never cited. The paper answers a small interesting curiosity related to data based initialization for sampling from mixtures with limited links with practice.\n---\n[1] Jerrum, M., Son, J. B., Tetali, P., & Vigoda, E. (2004). Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zxeTimoaqn", "reviewer": "Reviewer_7jZP", "summary": "This paper utilizes the vanilla score-matching to sample from multimodal distributions. They also show that initialization using data  can help the score matching the ground truth distribution.", "questions": "- How does it compare to other bounds? it seems like this bound provides this on average and not the worst-case. In addition, it is mentioned in previous work: \"in high dimensions, it will not be anywhere close to the ground truth distribution unless we have an exponentially large number of samples\", how is it not the same case in their paper as well?  Furthermore, What is the computational complexity?\n - The analysis starts with several idealized assumptions, including the exact knowledge of the score function and the assumption that the ground truth distribution is supported within a specific radius. These assumptions might not hold in real-world scenarios, limiting the practical applicability of the results. Could the author please elaborate on that? \n- The method relies on various parameters such as $\\delta$ (overlap parameter), $H$ (tuning parameter), $\\epsilon$ (error threshold), and step size $h$. How can one justify the generalization of the method across different datasets or scenarios due to the fact that sensitivity to these parameters could make the approach highly sensitive to the choice of initial conditions and hyperparameters, making it challenging? \n- As mentioned earlier,  the analysis focuses on an idealized scenario and might not directly translate to real-world applications. The conditions and assumptions required for the analysis might be too strict or unrealistic for practical use cases, limiting the method's applicability in real-world data analysis or machine learning tasks. How does this work can be applied in practice? How does it apply to high-dimensional data? Experimental results with high-dimensional data are required to show the efficacy of the procedure. \n- The analysis briefly touches upon the scenario where the score function is estimated from data. In practice, obtaining a precise score function estimation can be a challenging task and might introduce significant errors in the analysis.\n- The passage does not provide a comprehensive comparison with existing methods or techniques in the field. Without a clear comparison, it's challenging to assess the novelty and superiority of the proposed approach over existing state-of-the-art methods for similar tasks. The analysis primarily focuses on theoretical aspects and lacks empirical validation on real datasets.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Sampling from multimodal distributions is an extremely interesting problem.", "weaknesses": "- This paper is poorly written and very hard to read and follow. It constantly jumps around. It feels like you are reading lecture notes rather than a paper. The main contribution is hidden in many topics that can easily be moved to the appendix. \n\n- Lack of comprehensive experimental results and applications to real-world data and high dimensional data. \n\n- Lack of comparison to other bounds and theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hqln1YKXqA", "reviewer": "Reviewer_3d8a", "summary": "This is a theoretical work that addresses the problem, known from the literature, affecting vanilla score matching approaches to learn multimodal distributions from data.\nThe key idea is to rely on vanilla score matching, and prove that a Langevin diffusion process with early stopping, appropriately initialized at the empirical distribution, successfully generates multimodal distributions.\nThis result builds on several empirical works that show ways of overcoming the difficulty of using vanilla score functions for the estimation of multimodal distributions, and has the merit of being theoretically sound and -- to some extent -- practical.", "questions": "Besides asking authors to provide comments, explanations and eventually additional details for the three main weaknesses discussed above, I have the following question:\n\n* A recent paper [2] studies discrete Langevin processes with approximate scores, and (very informally speaking) also finds that the approximation quality of the distribution obtained by the Langevin process can ``drift away'' in KL terms, from the true distribution if the simulation time $T$ is too large. Do you think there are connections that your work could draw to improve the discussion on the early stop mechanism you devise?\n\n[2] Kaylee Yingxi Yang and Andre Wibisono, Convergence of the Inexact Langevin Algorithm and Score-based Generative Models in KL Divergence, arXiv 2211.01512\n\n** Post rebuttal feedback **\nThe authors engaged in discussions about my concerns and made an effort to improve their paper. For these reasons I raised my score.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* I really liked the pedagogical structure of the paper, which is akin to a different kind of literature such as applied mathematics, or conferences on learning theory. The main result is stated, a positioning of the work with respect to both theory and practice is clearly outlined, and open questions are discussed, in a succinct manner. Then, the bulk of the article revolves around the proof strategy used to arrive at the main theorem in the paper.\n\n* I think there are nice connections with recent work such as [1], which deal with methods to factorize the data distribution into a product of conditional probability distributions that are strongly log-concave. Ultimately, the goal is to discover ways of using the vanilla score matching to sample from simpler distributions whereby the noise injection that is typical for score-based generative models is not needed.\n\n* To the best of my understanding, the technical strategy used to prove the main result is correct, well developed and clearly exposed (in the main paper)\n\n[1] Florentin Guth and Etienne Lempereur and Joan Bruna and Stéphane Mallat, Conditionally Strongly Log-Concave Generative Models, ICML 2023", "weaknesses": "* I think there is some room for improvement in the overall narrative and exposition of the paper (there are a few typos, easy to fix and not problematic for the technical understanding).\nFirst of all, the assumption that the score is easy to compute and, in particular for some data distributions it can be analytically available, should be emphasized more. Essentially, this work side-steps the problems of learning the score function alltogether: despite citing the seminal work from Hyvarinen 2005, the authors chose not to bring to the readers' attention the fact that in practical cases, even the vanilla score can be hard to compute, as it can require costly computations of the trace of the Hessian of the parametric score, which derives from a rewrite of the Fisher divergence. So, I think it is important to mention that the parametric score function does not come for free in general settings.\n\n* The main results in the paper requires very important ``ingredients'':\n1. An early stop mechanism, to set the Langevin Monte Carlo process evolution to stop at a very well defined diffusion time. There is no discussion about the practical implications of the tight bound on $T$ derived in Theorem 1, which is exponential in the data complexity (in the case of the paper, this takes the form of the number of mixture components $K$)\n\n2. The tight bound on step size for the simulation of discrete-time Langevin dynamics decreases exponentially with the data complexity. Although this is not surprising, the more complex the data, the finer-grained your simulation should be, I think a discussion on practical implications is in order.\n\n3. The quality of the approximation of the parametric score function is an assumption that is, in my opinion, very strong, and hardly achievable in practice. This is not a problem in the ``simple'' setting of this work, where data is assumed to be a mixture of $K$ log-concave, smooth components, which is needed to come up with a feasible proof strategy. However, in reality, parametric score functions can only approximate the true score.\n\n4. The number $M$ of i.i.d. samples required to define the initial condition of the discrete Langevin process is not discussed appropriately. From Theorem 1, it seems to me that we need a fairly large number of samples, but I must confess I had a hard time finding the impact of $M$ on the proof strategy outlined in Section 2 of the paper. \n\n* Experiments are weak. Of course we are not talking about using the typical datasets that the current literature on score-based generative modeling. As an example, the results displayed in Figure 2 could have been commented more in the optic of explaining the relation to the above 4 points. Some hints are available in Appendix I, such as details on the learning procedure for the vanilla score network, but I still find it hard to relate such technical details to the hypothesis required for Theorem 1 to be valid.\n\n* [minor weakness] The editorial format of the paper is somehow unconventional. There is no conclusion, and a large fraction of the real-estate available on the 9 pages is dedicated to material that often is given a prime spot in the appendix. If on the one hand I like this presentation style, as it is really helpful to go through the proof strategy detail, the downside is that it substract space to provide more insights on experiments, outline conclusion and compare to prior (albeit experimental) work upon which the authors have drawn inspiration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)