The Poisson Midpoint Method for Langevin Dynamics:  Provably Efficient Discretization for Diffusion Models
Authors: Saravanan Kandasamy
Dheeraj Mysore Nagaraj
Venue: NeurIPS 2024 poster (2024)
Keywords: Langevin Monte Carlo
Diffusion Models
MCMC
Primary area: diffusion_based_models
TL;DR: We introduce Poisson Midpoint Method which provably speeds up SDE based sampling and apply it to diffusion models

Abstract: Langevin Dynamics is a Stochastic Differential Equation (SDE) central to sampling and generative modeling and is implemented via time discretization. Langevin Monte Carlo (LMC), based on the Euler-Maruyama discretization, is the simplest and most studied algorithm. LMC can suffer from slow convergence - requiring a large number of steps of small step-size to obtain good quality samples. This becomes stark in the case of diffusion models where a large number of steps gives the best samples, but the quality degrades rapidly with smaller number of steps. Randomized Midpoint Method has been recently proposed as a better discretization of Langevin dynamics for sampling from strongly log-concave distributions. However, important applications such as diffusion models involve non-log concave densities and contain time varying drift. We propose its variant, the Poisson Midpoint Method, which approximates a small step-size LMC with large step-sizes. We prove that this can obtain a quadratic speed up of LMC under very weak assumptions. We apply our method to diffusion models for image generation and show that it maintains the quality of DDPM with 1000 neural network calls with just 50-80 neural network calls and outperforms ODE based methods with similar compute.

The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models
Saravanan Kandasamy' Department of Computer Science
Dheeraj Nagaraj
Google DeepMind
Cornell University sk3277@cornell edu
mueerajnagaraj@goggee
Abstract
Langevin Dynamics is Stochastic Differential Equation (SDE) central to sampling and generative modeling and is implemented via time discretization. Langevin Monte Carlo (LMC), based on the Euler-Men Maller-aa discretization, the simplest and most studied algorithm. LMC can suffer from slow convergence requiring a large number of steps of small step-size to obtain good quality samples. This becomes stark in the case of diffusion models where large number of steps gives the best samples, but the quality degrades rapidly with smaller number of steps. Randomized Midpoint Method has been recently proposed as a better discretiza- tion of Langevin dynamics for sampling from strongly log-concave distributions. However, important applications such as diffusion models involve non-log concave densities and contain time varying drift. We propose its variant, the Poisson Mid- point Method, which approximates a small step-size LMC with large step-sizes. We prove that this can obtain a quadratic speed up of LMC under very weak as- sumptions. We apply our method diffusion models for image generation and show that it maintains the quality of DDPM with 1000 neural network calls with just 50-80 neural network calls and outperforms ODE based methods with similar compute.
Introduction
The task sampling from target distribution central to Bayesian inference, generative modeling, differential privacy and theoretical computer science [48 20
17 25 Sampling algorithms, based on the discretization of stochastic differential equation (SDE) called the Langevin Dynamics, are widely used. The straightforward time discretization (i.c., Euler Maruyama discretization) of Langevin dynamics, called Langevin Monte Carlo (LMC), is popular due to its simplicity. The convergence properties of LMC have been studied extensively in the literature under various conditions the
53 5]. LMC can suffer from slow convergence to the target distribution, and often requires a large number of steps with very fine time discretization (i.e., small step-size), making it prohibitively expensive.
target distribution g 12
11
45
15
33
7
9 16, 30
The Poisson Midpoint Method introduced in this paper approximates multiple steps of small step-size Maler-Maruyama discretization with one step larger step-size stochastic approximation. In the case of LMC, we show that method (called PLMC) converges the target as fast as LMC with much smaller step-size without any additional assumptions such as isoperimetry or strong log concavity (up to small additional error term). This is variant of the Randomized Midpoint Method (RLMC) studied in the literature 40 18 50 (see Section [.1 for comparison).
* TTii work done when SK student researcher at Google Research.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Diffusion models are state-of-the thet in generating new samples of images and videos given samples 20 4 34. These start with Gaussian noise vector and evolve through the time-reversal of
the SDE called the
process. The time reversed process can be written as an
SDE (Langevin Dynamies with a time dependent drift) or as an ODE (see Section 2). The DDPM scheduler [20], which discretizes the SDE, obtains the best quality images with small step-size and a large number of steps (usually 1000 steps). However, its quality degrades with larger step-sizes and small number of steps (say 100 steps). Schedulers such as DDIM ((42)) DPM-Solver (128) (29). PNDM ((27) which solve the ODE via numerical methods perform much better than DDPM with a small number of steps. However, it is noted that they do not match the performance of DDPM with 1000 steps over many datasets ([42 28 )) Poisson Midpoint Method gives a scheduler for the rime-reversed SDE which maintains the quality of DDPM with 1000 steps, with just 50-80 steps.
1.1 Prior Work
Euler Maruyama discretization of SDEs is known to be inefficient and many powerful numerical integration techniques have been studied extensively [23] [2 26)). However, higher order methods such as the Runge-Kutta method require the existence and boundedness of higher order derivatives of the drift. The Randomized Midpoint Method for LMC (RLMC) was introduced for strongly log- concave sampling [40] and was further explored in 18). It was shown that RLMC, under certain conditions, can sample with a larger step size for fewer steps compared to Euler Maruyama and yet obtain the same accuracy. RLMC is popular due to its simplicity, and ease of implementation and does not require higher order bounded derivatives of the drift function. However, the current theoretical results are restricted to the case of strongly log-concave sampling, whereas non-log-concave sampling is of immense practical interest.
1.2 Our Contributions
Midpoint Method which discretizes SDEs by approximating K K-steps of Euler-Maruyama discretization with step-size & by just one step with step-size We show a strong error bound between these two processes under general conditions in Theorem (no assumption on mixing, smoothness etc). This is based Central Limit Theorem (CLT) based method in [10 to analyze stochastic approximations of LMC.
(1) We design the Poisson
(2) We apply our method to LMC to obtain PLMC. We show that it achieves speed-up in sampling for both Overdamped LMC (OLMC) and Underdamped LMC (ULMC) whenever LMC mixes, without additional assumptions such as isoperimetry or strong-log concavity.
(3) When the target obeys the Logarithmic Sobolev Inequalities (LSI), we show that PLMC achieves a quadratic speed up for both OLMC and ULMC. Prior works on midpoint methods [40] [8] [5] only considered strongly log-concave distributions. We also show an improvement in computational complexity for ULMC from 1
22/3 to 1 to achieve errof
v2
(4) Empirically, we show that our technique can match the quality of DDPM Scheduler with 1000 steps with fewer steps, achieving up to 4x gains in compute. Over multiple datasets, our method outperforms ODE based schedulers such as DPM-Solver and DDIM in terms of quality.
1.3 Notation:
Xor denotes (Xt)osiST and Xx(o.T) denotes (Xik) )osesT. I denotes identity matrix over R whenever & is clear from context. For any vector x E IR* |x|| denotes its Euclidean norm. For any a, b E Z and > b, we take the Σt to be 0, and the product I to be 1. Underdamped Langevin Dynamics happens in R22d Here, we take vectors named X (along with subscripts and superscripts) as X = [U' VJT where U, V E IRd also carry the same subseripts and superscripts (e.g: X2 corresponds to Ü4, V2). In this case I represents identity matrix in 2ddx2d and I, denotes the identity matrix in ddd For any random variable X, we let Law(X) denote its probability measure.
By TV( v) and KL (z(lp) we denote the total variation distance and KL divergence (respectively) between two probability measure μ, V. O, θ are standard Kolmogorov complexity notations
'The prior works considered the compexity for Wasserstein distance W2 (output, target) S e whereas we consider TV S c. This is a standard comparison in the sampling literature [53].

---

whereas Ö, θ are same as O,Ω, θ up to poly-logarithmic factors in the problem parameters such as a K, T, d.
2 Problem Setup
Given a random vector Xu E Re, consider an iterative, discrete time process (X)))eN)()) over R with step-size a > 0 given by:
X AaX, + ta) + aT
Where Aa; Ga Ta are d x d matrix valued functions of the step-size and (Z))20 iid (/ b IRd - Rd is the drift. Call this process S(A, G,T, a.). We consider Overdamped Langevin Monte Carlo (OLMC), Underdamped Langevin Monte Carlo (ULMC) and DDPMs as key examples.
Overdamped Langevin Monte Carlo: Consider Overdamped Langevin Dynamics for some F: Rd R:
dx, (FF(X))ds + V2dB,
Here B, is the standard Brownian motion in R Under mild conditions F and Xo. Law(XX, T-000 I' where nT" (XX x (pp(-(()) is the stationary distribution.
Picking A, = I, G. = aI, r 22 and b(x, ta) FVF((x in Equation ① gives us Euler- Maruyama discretization of Overdamped Langevin Dynamics: X, in (I) approximates X [8 35
OLMC is the canonical algorithm for sampling and has been studied under assumptions such as log-concavity of n² g 12 11
or that x satisfies isoperimetric inequalities 45 15
33 7
Underdamped Langevin Monte Carlo occurs in 2d dimensions. We write X₁ = U V.jT E Rd
where U2 Rd is the position and Vg E Rd is the velocity. Fix a damping factor 7 > 0. We take:
Ia
>4 La
GA == + (h (1 -------he 1)
of (a),,ta= = VF(U))
A
0
0
- {/) + 2 (1- -1- 2 La
1 - 2 h + -2 Lt
r
(1 - -
(1-e 27 La
This choice of An, Th, Gn, b(,) in Equation ① gives the Euler-Maruyama discretization of Un- derdamped Langevin Dynamics (a.k.a the Kinetic Langevin Dynamics) studied extensively in Physics| 14)
dü, V,d;;
=v V
+
The stationary distribution the SDE is given by n² VU, x
IIVI 139
ULMC is
2
popular in the literature and has been analyzed in the strongly log-concave setting
6 16 and under
isoperimetry conditions [30 53
We refer to (53 for complete literature review.
Denoising Diffusion Models:
In this case the stochastic differential equation is given by:
dx, = (X, + 2V log P- (X + V
(4)
This also admits an equivalent characteristic ODE given below:
dx,
X- + V log (X+)
(5)
dr
See 43 5 4 for further details. Here pr is the probability density of e + v1 - ee-21 Z where X" is drawn from the target and Z is drawn from A I) independently. The drift V log Pr learned via neural networks for discrete time instants To. .o..... Tn-1 (usually
1000). In practice, the iterations are written in the form F. X1+1 = ogX; + 6, V log Pr, (Xt) + Ug where at, b,, o; are chosen for best performance. Aside from the original choice in 20). many others have been proposed (2) Since Ag, Ga. r in Equation ( are time independent, we provide a variant of the Poisson Midpoint Method to suit DDPMs in Section A. along with few other optimizations.
TThe time convention in the DDPM literature is reverse: Xt-1 a:X: + be V log Po,pP..-1,(A (Xt) + o.Lr
3

---

2.1 Technical Notes
Scaling Relations: We impose the following scaling relations on the matrices An. GR, for every h E Rt n E N, which are satisfied by both OLMC and ULMC. Whenever b(-) is constant function, these ensure that K steps of Equation (T in distribution.
with step-size a K the same as 1 step with step-size a
(An)* Anni
(A, Gian'
(AAT t=0
2=0
Randomized Midpoint Method and Stochastic Approximation We first illustrate the Random- ized Midpoint Method 40 18 50 by applying it to OLMC (to obtain RLMC) to motivate our method (the Poisson Midpoint Method) and explain why we expect a quadratic speed up shown in satisfies:
Section 3 Overdamped Langevin Dynamics
(t+1)a
((+1)a Xea
VF(X,)ds + V2( BLG))
(6)
Lt
Taking X, as the approximation to X LMC approximates the integral Jia ((+1)a F(XX))ds with (V,)) giving a 'biased' estimator to the integral (conditioned on X₂ = Xta). This gives the LMC updates X2+1 = X2 - vVX,) + 22a2;; Z: ~ (O, RLMC chooses a uniformly random point in the interval [ta, (t + 1)a] instead of initial point to as described below:
Let ~ (n, 1)), Zr,1, Z, ~ -N I) be independent and define the midpoint Xttn := X
(xVF((X)) + 22 (notice Xetu is an approximation for ((+taaa). The RLMC update is:
X = X₁ X -V-aaFF(XXX) + 2uaZ 22 u)aZ222
Notice that 2ua + /2(1 - 2), I), and ([aVF((x(=u)/X) Zr,1 Zr,21 =
So F(X which is better approximation of the integral than FVF)( Therefore RLMC provides a nearly unbiased approximation to the updates in Equation 6
Intuitively, we expect that reducing the bias leads to quadratic speed-up. Let 2, 2' ~ NoO, 1)
and independent. For small enough it is easy to show that, KL (Law( 7 + +) /// (Z) = O whereas KL (Law(Z ZZ [Laa| 22) () We hypothesize that Z, error integral is closer to (O I) when the eиτor term has small mean and a large variance (as in RLMC) than when has a large mean but variance (as in LMC). However, rigorous analysis of RLMC has only been done under assumptions like strong log-concavity of the target distribution. This is due to the fact that Z, dependent on the error the integral, disallowing the argument above.
Our method, PLMC, circumvents these issues by considering discrete set of midpoints {0, : K-1) instead of [0, 1]. picks each midpoint with probability к independently, al- lowing us to prove results under more general conditions using the intuitive ideas described above. Thus, our method a variant of RLMC which amenable to more general mathematical analysis. The OPTION 2 of our method (see below) makes this connection clearer. PLMC is naturally suited to DDPMs since the drift function is trained only for a discrete number of timesteps (see Section 2).
2.2 The Poisson Midpoint Method
We introduce the Poisson
Midpoint Method (PLMC) which approximates K steps of S 6, with step-size &h with one step of which has a step-size a. We denote this by PS G, K) and let its iterates be denoted by (Xex )120 or (XP) ) Suppose Hr E {0, 1} be any binary sequence and Zi be sequence of i.i.d. (0, N (O) we define the interpolation:
i K - 1. Given N.x.
XIK4I Aye Xex + Gz b(Xex, ta) +
A A I' ZiK+j
K
1=0

---

Note that this interpolation is cheap since every one of XIK+; can be computed with just one evaluation of the function b(). We then define the refined iterates for 0 I i K for a given i as:
Xic+41== = a Xec+s + C R
b(xxx, (a) + KH,,, (A*+i)))
- b(Xex, kai))
r Zix+i
(8)
We pick Hi, based on the following two options, independent of ZiK+i,
OPTION 1: Hr, are i..d. Ber( #))
OPTION 2: Let ue Unif (fo...,,K ii.d. and : 1(u =i).
Remark 1. We call our method Poisson Midpoint method since in OPTION I the set of midpoints
oz {at K H4, = 1} converges to a Poisson process over [at, aft + 1)] as K + cc.
The Algorithm and Computational Complexity The algorithm PS(A, G, G,T, b, a, K) computes X Xk(+) given X K in one step by unrolling the recursion given in Equation (8). For the sake of clar-
ity, we will relabel X, to X. to stress the fact that it the 1-th iteration of PS(A, G, T, b, a, K).
Step 1: Generate I
(n S (O..... K -1} such that H 1 iff i 4, Let ij < in ... < iN hold, When 0, we take this to be the empty set.
Step 2: Let Mo == 0 and let Wi, be a sequence of i.d. (N, random vectors. For k =
1. N, N + I, we take:
MR Aact i 1) MA-1 Paly-1a 1) We,
We the convention that in 0, iN+1 K - 1, Ao and To =
Step 3: For k L....,,,, compute X1K+iz Aoy Xp + Goy b(XP, at) + Mr
Step Corr == K E G GiK-1-ija (b(Rixtt (K+s)aa) b(xp atl)
K
K
Step 5: X.+1 = G M
That is, the algorithm first generates the random mid-points Hi,6- computes the interpolation X only when H and then computes b(Xex+s: ((K+))a) for these points. These computations K
are then combined to compute X(+1xx- In most applications. it is computationally easy to generate Gaussian random vectors and perform vector operations such as summation. However, the evaluation of the drift function b() is expensive. Therefore, in this work, we consider the number of evaluations of the drift function as the measure of computational complexity. The following proposition establishes that each iteration of PLMC requires 2 evaluations of 6() in expectation.
Proposition 1. When the scaling relations hold (Section 2.1. the trajectory (X. ):20 in Equation (
has the same joint distribution as the trajectory (Xex )r20 given in Equation ( In expectation, one
step of PS(A A, G,T,b, b, K) requires two evaluations of the function b(.).
We call a, as PLMC whenever S(A,G,I, x) is either OLMC or ULMC.
3 Main Results
Theorem I gives an upper bound for the KL divergence of the trajectory generated by PS(A, G, b, a, K) to the one generated by S(A, G,T, b, )). We refer to Section C for its proof. We note that Theorem I does not make any mixing or smoothness assumptions on b(-) and that can handle time dependent drifts. We refer to Section 4 for proof sketch and discussion.
Theorem 1. Let X, be the iterates of S(A, G,T.b, K and X. be the iterates of PSP A, G,T.G, K)
with OPTION Suppose that XP Xo. Let X.K+s be the iterates Equation 8 Define random variables:
BiK+1 r a [6(X.K t 12) b(8xx x
K
BoK+ -
Ib( )) b(8ex, to)]l K
K
5

---

Then, for some universal constant C' and any r >> 1:
KL (Law(X [a
PaK+i
PkKt
PaKti
B P
B B
CEE
+
(10)
K2
K3
K2
We now apply Theorem I to the case of OLMC and ULMC under additional assumptions, with the proofs in Sections E and respectively.
Assumption 1. F
FR Rd is L-smooth (i.e., V is L-Lipschitz). x" is its global minimizer. Assumption 2. The initialization Xo such that EE] [ - x x=1
Onii
The assumptions above are very mild and standard in the literature. Specifically, Assumption shows that the initialization is close to global optimum by O(ve) up to 14th moments. For instance, this satisfied when the initialization
standard Gaussian variable with mean 14 satisfying ||e || O(vd). Specifically this is true when μ 0 and ||x*|| O(Vd). This is a weak assumption which is implied from common initialization assumptions in the literature as listed below. can replaced with the assumptions 53 Appendix and Lemma 27] which considers Gaussian initializations with the right variance and mean. The original randomized midpoint method work (4) considers initializing at whereas 45 considers a Gaussian initialization with the right variance at a local minimum of F.
We do not make any assumptions regarding isoperimetry of the target distribution '. (x) x exp(-F(x)).
Theorem (OLMC). Consider the setting of Theorem ! with OLMC under Assumptions 7 and
There exists constants C1, C2 > such that whenever aL < and a LTT < 02 then:
KL (La.(XX.7T)) (|laall (ara)
S CL of (B(F((X) - F(x*))+1)
+ +O(CI'a'Kd"T
(11)
Remark 2. There are lower order terms hidden in the 00) notation. These are explicated in Equation (40) in the appendix. The next theorem gives similar guarantee for ULMC and the lower order terms are explicated in Equation 60 in the appendix.
Theorem 3 (ULMC). Consider the setting of Theorem | with ULMC under Assumptions 7 and Suppose that x" is the global minimizer of F. There exist constants C1, C1, C2 such that whenever
CIVI. ary < <1,, T.a
co
KL (Law(X (orrT) (laor)))/Lw((/xn)
< Ca
EF(U0 1/ F(x)) 21 [//+++1 +1]
0 L'T2 (d log K)²)
(12)
7
OLMC and ULMC are sampling algorithms which output approximate samples (Xr and UT re- spectively) from the distribution with density π x
Given > 0. prior works give upper function of achieve guarantees such as
bounds T and the corresponding step-size
KL (Law(Xy) [[ < 2 or TV(Law(XT)) m²) I By Pinsker's inequality TV < 2KL therefore guarantees for KL S 2 to those for TV S as common in the literature.
Quadratic Speedup Let - ((1a/)) as is standard. Choosing K = = (()aa) our method applied
to OLMC achieves a KL divergence of O(a²) to OLMC with step-size a². Similarly, our method applied to ULMC achieves a KL divergence of O(a*) ) to ULMC with step-size a², Whenever the KL divergence of OLMC (resp. ULMC) output n², with step-size 17 is Q(()) (resp ((n))) Theorem (resp. Theorem 3 demonstrates a quadratic speed up.
To show the generality of our results, we combine Theorems and with convergence results for OLMC /ULMC in the literature (455 (53) when π² satisfies the Logarithmic Sobolev Inequality with constant À (A-LSI). We obtain convergence bounds for the last iterate of PLMC to x² under the same conditions. X-LSI is more general than strong log-concavity (A-strongly log-concave "² satisfies X-LSI). It is stable under bounded multiplicative perturbations of the density (2]) and Lipschitz mappings. X-I.SI condition has been widely used to study sampling algorithms beyond log-concavity. We present our results in Table I and refer to Section for the exact conditions and results.

---

Table 1: Comparison of LMC and PLMC guarantees. LMC complexity is the upper bound on the number of drift (6() evaluations to achieve the eπror guarantee in the referenced work. PLMC complexity the corresponding upper bound for PLMC. PLMC obtains a quadratic improvement in and improved dependence on 5.d. The bounds hold to poly-log factors.
Algorithm Reference
Conditions
LMC complexity
PLMC complexity
1,8ab x²C
(4) (4) dis Ve
ULMC
33
X-LSI, Assumptions
for TV
Se
for TV Se
OLMC
X-LSI, Assumptions
L'd for KL S²2
LådE for TV Sc
A².
Proof Sketch
Sketch for Theorem T For the proof of Theorem 1 we follow the recipe given in 10] in order to analyze the stochastic approximations of LMC where only an unbiased estimator for the drift function is known. The bias variance decomposition in Lemma [ shows that the iterations of PS(A, G, can be written the same form of as the iterations of S(A,G,,, x):
NIK+it1 = Aa XIK+i + [[(8or+0] + a 2ik+s K
K
Where ZiK+: == ZeK+i- + BiK+I SiK+i, BeK++ the 'bias' with non-zero conditional mean, and S is the variance with O conditional mean (conditioned on xek+;). They are independent of Zuk+s conditioned on X Note that the sequence (Zik+s)e. is neither i.i.d. nor Gaussian. If was sequence of i.idd. N NN I), then this is exactly same I,,, x):
The main idea behind the proof of Theorem i that due to data- processinn inequality, it sufficient to show that (Z,K+) +x)+, is close
sequence of i..dd. Gaussian random vectors KL.-divergence, The bias term can be shown to lead to an error bounded by Ex, EE] BiK++ I13,, which roughly corresponds to the KL. divergence between N M(Bi+ii. I) and W(0, I). We then show that Zek++ + Zo: close in distribution to ((, I). In order to achieve this, we first modify the Wasserstein CLT established in (51) show that Zex+i S.K+i is close in distribution to AN + Ex,s) when
conditioned on ZoaK++i-1 where Ex,; is the conditional covariance of SiK+i- This CLT step gives us 2
the error of the form ΣT= Σ -K11 CI
199 8
Theorem
K
We then use the standard formula for KI. divergence between Gaussians to bound the distance between (N I E,,)) to NN I). This accounts for the fact that the Gaussian noise considered has a slightly higher variance than I. This leads the leading term CE
P=
K
Sketch for Theorem
2 Applying Theorem I to OLMC, note that the term 3.k, depends on how far the coarse estimate X,K+i is from the true value A.K Indeed, under the smoothness assumption
on F we show that: 22 I LLaa ) suposisk-1 X X - X2 Thus:
B| S L " K"B "P 2
Therefore, the proof reduces to bounding Σt V ( We observe that X((+1)K
İA al (VF((Xx))) Ar) + 2e where A, is a small error term appearing due to Poisson Midpoint Method. Notice that this is approximately stochastic gradient descent on F with a large noise /2a. Therefore, using the taylor approximation of F, we can show that:
BF (F( EF(Xx)) S -a] V/( MII + ad o(ad)
BIVF(X(N)) F(Xo) inf F(x) LTd ((..Td)
The following sophisticated bound derived in this work is novel to the best of our knowledge:
[[I 1.-1p (F(Xo) infx F(x))² T1 (1 (aIT)P-1
7

---

Sketch for Theorem This is similar Theorem 2 but requires us to bound E E, Vix 2 and
E F 20 We track the decay of two different entities across time: (1) Vix I| and (2) F(UIX + E2K). Our proof shows via a similar taylor series based argument that PLMC does not allow either [Vxx 1 or F(UIx E(x) to grow too large. Letting Vr := U.K + Fxx we show (roughly):
7e ||]]6|| + F(X*)) + 2 + (7aT))- d Σ EI]F
Bl EI]VKl 40
x
Bl]bb| +B(((V))) - F(x")1*
+T
20 7. + (7777701 d
5 Experiments
We now present experiments to evaluate Poisson Midpoint Method as a training-free scheduler for diffusion models. We consider the Latent Diffusion Model (LDM) [39] for CelebAHQ 256, LSUN Churches, LSUN Bedrooms and FFHQ datasets using the official (Py Torch) codebase and checkpoints. We compare the sample quality of the Poisson Midpoint Method against established methods such as DDPM, DDIM and DPM-Solver, varying the number of neural network calls (corresponding to the
drift b(x, t)) used to generate single image.
To evaluate the quality, we generate 50k images for each method and number of neural network calls and compare it with the training dataset. We use Fréchet Inception Distance (FID) [99] metric for
LSUN Churches and LSUN Bedrooms. For CelebAHQ 256 and FFHQ, we use Clip-FID, a more suitable metric it is known that FID may exhibit inconsistencies with human evaluations datasets outside of Imagenet 24 We refer to Section A.3 in the appendix for further details.
We refer to the ODE based sampler with 17 0 (see [2] setting as DDIM and use the implementation in [39]. We generate images for number of neural network calls ranging from 20 to 500. For DPM- Solver, we port the official codebase of (28) to generate images for different numbers of neural network calls ranging from 10 to 100 using MulSistepDPMSolver and tune the hyperparameter "order' _iiinermi_ormm 'time_ quadratic' } for each instance to obtain the best possible FID score. This ensures that the baseline is competitive.
over (2, 3} and 'skip_ tipppt_tpe over ("logSNR',
For the sake of clarity. we will call all SDE based methods, including DDIM with n > 0 (see 42) as DDPM. The DDPM scheduler has many different proposals for coefficients ae, b,, ct (see Section 2 42 D. apart from the original proposal in the work of [20] Based on these proposals, we consider three different variants of DDPM in our experiments (see Section A.5 for exact details). This choice can have significant impact on the performance (See Figure [ in the Appendix) for
given number of denoising diffusion steps. For the Poisson Midpoint Method, we implement the algorithm shown in Section for number of diffusion steps ranging from 20 to 500, corresponding to 40 to 750 neural network calls (see Section (A.)). This approximates K steps of the 1000 step DDPM with a single step. For both Poisson Midpoint Method and DDPM, we plot the results from the best variant in Table for a given number of neural network calls and refer to Section A.5 for the numbers of all variants. Poisson Midpoint Method incurs additional noise in each iteration due to the randomness introduced by H, This can lead to a large error when K is large. When K is large, we reduce the variance of the Gaussian noise to compensate as suggested in the literature (see Covariance correction in 10 and 31 Equation 9I). We refer to Section A.5 for full details.
5.1 Results
We refer to the outcome of our empirical evaluations in Table 2 The first column compares the performance against DDPM. We see that for all the datasets considered, Poisson Midpoint Method can match the quality of the DDPM sampler with 1000 neural network calls with just 40-80 neural network calls. Observe that for CelebA, LSUN-Churer and FFHQ datasets, the performance of DDPM degrades rapidly with lower number of steps, showing the advantage our method in this regime. However, limitation of our work is that the quality of our method degrades rapidly at around 40-50 neural network calls. We believe this because our stochastic approximation breaks down with larger step-sizes and further research is needed to mitigate this.
8

---

The second column compares the performance of our method against ODE based methods. It is known in the literature that DDPM with 1000 steps outperforms DDIM and DPM-Solver in terms of the quality for a large number of models and datasets 41 42 Thus, in terms of quality, Poisson midpoint method with just 50-80 neural network calls outperforms ODE based methods with similar amount of compute. Note that we optimize the performance of DPM-Solver over 6 different variants as mentioned above to maintain a fair comparison. However, the very low compute regime (-10 steps), DPM-Solver remains the best choice.
6 Conclusion
We introduce the Poisson Midpoint Method, which efficiently discretizes Langevin Dynamics and theoretically demonstrates quadratie speed up over Euler-Maruyame discretization under general conditions. We apply our method to diffusion models for image generation, and show that our method maintains the quality of 1000 step DDPM with just 50-80 neural network calls. This outperforms ODE based methods such as DPM-Solver in terms of quality, with a similar amount of compute. Future work can explore variants of Poisson midpoint method with better performance when fewer than 50 neural network calls are used. An interesting theoretical direction would be to derive convergence bounds for algorithms such as DDPM which have a time dependent drift function. Future work can also consider convergence rates of PLMC under conditions such as the Poincare Inequality and whenever F Hölder continuous instead of Lipschitz continuous.
7 Societal Impact
Our work considers an efficient numerical discretization schemes for making diffusion model infer- ence more efficient. Publicly available, pre-trained diffusion models are very impactful and have significant risk of abuse. In addition to theoretical guarantees, our work considers empirical experi- ments to evaluate the inference efficiency on publicly available, widely used diffusion models over curated datasets. We do not foresee any significant positive negative social impact our work.

---

Table 2: Empirical Results for the Latent Diffusion Model 39 comparing the Poisson midpoint method with various SDE and ODE based methods.
Dataset
vs. SDE Based Methods
vs. ODE Based Methods
Latent Diffusion Model (CelebAHQ 256)
Latent Diffusion Model (CelebAHQ 256)
DDPM
DDIK ETA-0
Poisson Midpoint (Ours)
Paisson Midpaint (Ours)
DPM 3PM-Solver
Ciip-ID
Clip-FID
CelebAHQ 256
Number of Neural Network Calls
Number of Neural Network Calls
Latent Dilfusion Model (LSUN Churches)
Latent Diffusion Model (LSUN Churches)
DDPM
Polsson Milspoint (Ours)
00-
Poisson Midpoint (Ours)
DPM-Solivr
LSUN Churches
30-
150 3000
203 Number Neural Network Calls
Number Neural Network Calls
Latent Diffusion Model (LSUN Bedrooms)
Latent Diffusion Model (LSUN Bedrooms)
DDPM
DDIM ETA=C
Poisson Mispoint (Durs)
Poisson Midpoint (Ours)
DPM Solver
LSUN Bedrooms
8
200
900
750
3000
320
300
Number of Neural Network Calls
Number of Neural Network Calls
Latent Diffusion Model (FFHQ 256)
Latent Diffusion Model (FFHQ 256)
DDPM
Poisson Midpoint (Curs)
Poisson Midpaint (Ours)
DPM-Salver
Olp-FID
Clip-FID
FFHQ 256
2.
20
100
200
750 1003
20
300
220
75c
Number of Neural Network Calls
Number of Neural Network Calls
10

---

Acknowledgments and Disclosure of Funding
We thank Prateek Jain for helpful comments during the course of this research work. This work was done when SK was student researcher at Google Research.
References
[1] Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards theory of non-log-concave canpling:first-rdee stationarity guarantees for langevin monte carlo. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2896-2923, PMLR, 02-05 Jul 2022.
[2] Fan Bao, Chongxuan Li, Jun Zhu, and Bo Zhang. Analytic-dpm: an analytic estimate of the optimal reverse variance in diffusion probabilistic models. In International Conference on Learning Representations, 2022.
[3] Kevin Burrage, PM Burrage, and Tianhai Tian. Numerical methods for strong solutions of stochastic differential equations: an overview. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 460(2041)::73-4022, 2004.
[4] Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. Advances in Neural Information Processing Systems, 36, 2024.
[5] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations, 2023.
[6] Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped langevin meme: A non-asymptotic analysis. In Conference on learning theory, pages 300-323. PMLR, 2018.
[7] Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of langevin monte carlo from poincare log-sobolev. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1-2. PMLR, 02-05 Jul 2022.
[8] Arnak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(3):651-676, 2017.
[9] ARNAK S DALALYAN and LIONEL RIOU-DURAND. On sampling from a log-concave density using kinetic langevin diffusions. Bernoulli, (643):956-1988 2020.
[10] Aniket Das, Dheeraj Nagaraj, and Anant Raj. Utilising the elt structure in stochastic gradient based sampling: Improved analysis and faster algorithms. arXiv e-prints, pages arXiv-2206, 2022.
[11] Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of langevin monte carlo via convex optimization. The Journal of Machine Learning Research, ):2666227111, 2019.
[12] Alain Durmus and Éric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1551 1587, 2017.
[13] Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Couplings and quantitative contraction rates for langevin dynamics. The Annals of Probability, 47(4):1982-22)
2019.
[14] Albert Einstein. Über die von der molekularkinetischen theorie der wärme geforderte bewegung von in ruhenden flüssigkeiten suspendierten teilchen. Annalen der physik, 4, 1905.
[15] Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of langevin monte carlo: The interplay between tail growth and smoothness. Conference on Learning Theory, pages 1776-1822. PMLR, 2021.

---

[16] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via rényi divergence analysis of discretized langevin meme. Advances in Neural Information Processing Systems, 33:7222-7233, 2020.
[17] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Conference on Learning Theory, pages 1948-1989, PMLR, 2022.
[18] Ye He, Krishnakumar Balasubramanian, and Murat A Erdogdu. On the ergodicity. bias and asymptotic normality of randomized midpoint sampling method. Advances in Neural Informa- tion Processing Systems, 13776667377, 2020.
[19] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 6629 6640, Red Hook, NY, USA, 2017. Curran Associates Inc.
[20] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models, Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[21] Richard Holley and Daniel Stroock. Logarithmic sobolev inequalities and stochastic ising models. Journal of Statistical Physics, 46:1 159-1194, 1987.
[22] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for improved quality, stability, and variation. CoRR, abs/1710.10199 2017.
[23] Peter E Kloeden, Eckhard Platen, Peter Kloeden, and Eckhard Platen. Stochastic differential equations. Springer, 1992.
[24] Tuomas Kynkäänniemi, Tero Karras, Miika Aittala, Timo Aila, and Jaakko Lehtinen. The role of imagenet classes in fréchet inception distance. The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
(25) Yin Tat Lee and Santosh S Vempala. Convergence rate of riemannian hamiltonian monte carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1115-1121, 2018
[26] Xuechen Li, Yi Wu, Lester Mackey, and Murat A Erdogdu. Stochastic runge-kutta accelerates langevin monte carlo and beyond. Advances in neural information processing systems, 32, 2019.
[27] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao. Pscudo numerical methods for diffusson models on manifolds. arXiv preprint arXiv: 2202.00700 2022.
(28) Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural Information Processing Systems, 35:5775-5787, 2022.
[29] Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Dpm- solver++: Fast solver for guided sampling of diffusion probabilistic models. arXiv preprint arXiv:2211.01095. 2022.
[30] Yi-An Ma, Niladri S Chatterji, Xiang Cheng, Nicolas Flammarion, Peter Bartlett, and Michael I Jordan. Is there an analog of nesterov acceleration for gradient-based meme? Bernoulli, 27(3), 2021.
[31] Yi-An Ma, Tianqi Chen, and Emily Fox. A complete recipe for stochastic gradient meme. Advances in neural information processing systems, 28, 2015.
[32] Grigori N Milstein and Michael V Tretyakov. Stochastic numerics for mathematical physies, volume 39. Springer, 2004.
[33] Wenlong Mou, Nicolas Flammarion, Martin J Wainwright, and Peter L Bartlett. Improved bounds for discretization of langevin diffusions: Near-optimal rates without convexity. Bernoulli, 1873):1577-1611 2022.
12

---

[34] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International conference on machine learning, pages 8162-8171. PMLR. 2021.
[35] Bernt Oksendal. Stochastic differential equations: an introduction with applications. Springer Science & Business Media, 2013.
[36] Ingram Olkin and Friedrich Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48:257-263, 1982.
[37] Gaurav Parmar, Richard Zhang, and Jun- Yan Zhu. On aliased resizing and surprising subtleties in gan evaluation. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages I 11400-11410 1410, 2022.
[38] Gareth O Roberts and Richard L Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pages 341 341-363, 1996.
[39] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684-10695, June 2022.
[40] Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. Advances in Neural Information Processing Systems, 32, 2019.
[41] Andy Shih, Suneel Belkhale, Stefano Ermon, Dorsa Sadigh, and Nima Anari. Parallel sampling of diffusion models. Advances in Neural Information Processing Systems, 36, 2024.
[42] Jiaming Song. Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2020.
[43] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:201 1. 13456, 2020.
[44] Ramon Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
[45] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[46] Santosh S. Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems 32: NeurlPS 2019, pages 6092-8104, 2019.
[47] Cédric Villani al. Optimal transport: old and new, volume 338. Springer, 2009.
[48] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681-688 2011.
[49] Fisher Yu, Yinda Zhang, Shuran Song, Ari Seff, and Jianxiong Xiao. LSUN: construction of large-scale image dataset using deep learning with humans in the loop. CoRR, abs/1506.03365, 2015.
[50] Lu Yu, Avetik Karagulyan, and Arnak Dalalyan. Langevin monte carlo for strongly log-concave distributions: Randomized midpoint revisited. arXiv preprint arXiv:2306. 08449, 2023.
[51] Alex Zhai. A high-dimensional elt in _2 w distance with near optimal convergence rate. Probability Theory and Related Fields, 170:821-845, 2018.
[52] Alex Zhai. A dige-dimensional clt in w __ w distance with near optimal convergence rate. Probability Theory and Related Fields, 170:821-844 -425, 2018.
[53] Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu. Improved discretization analysis for underdamped langevin monte carlo. In The Thirty Sixth Annual Conference Learning Theory, pages 36-71. PMLR, 2023.
13

---

A Details of Empirical Evaluations
A.1 Pseudocode
The Algorithm Let dt b, and o, be the coefficients the DDPM denoising step at time as per Section [ Let N denote the number of train steps. The main paper used notations and conventions based on the LMC literature. Here we follow different conventions and notations to connect with the diffusion model literature.
1. We take the dynamics to go backward in time (i.e., compute X from X₂)
2. We use b(Xt,t) instead of b(X,, at) to denote the neural network estimate of V llg (X1).
DDPM scheduler samples XN-1~ IO, and iteratively computes Xo X,-1 axX, (2, o,Z4; Ze (O,
We take . 1000 is standard in the literature. The Poisson Midpoint Method approximates K steps of the iteration above, with a single step. That is, it obtains an approximation for X,-K directly from X, The number of iterations deployed by Poisson Midpoint Method sample X, is N/K. K. We compute the number of neural network calls required in Section A.2 The exact description of Poisson Midpoint Method is given below.
PoisonnMidponntMeehood ,X,,, K, b(, OPTION):
1. Let (Ax, BR, Cx) +- InterpolationConstants// k), for every k E [K].
2. If OPTION
Define H; ~ Ber(1/K) i.i.d for every i E KK 15-1]
Define K.
If OPTION 2:
Define H; +- (u = i) where u ~ Unif((1,.... 13) i.d.
Define p = K 1.
3. For every i E [K], Z, I)..)).
4. Perform the update:
X,- Ax+
Σ BKi b b(X,tt)
Ck.iZ
+ Σ
Br b(x t))
1=1
where
X A,
Σ Brd b(Xe,t) Σ CrK--t+1bbll
Vr E [K 1].
5. Return X,-K. K.
InterolationnConstattee k)):
1. A di a:11 ar-k+1.
a1-k41-' .. a.- bb-141 if k
2. BR,
for each [k]].
bi
i = k
41-+11- ... ae-s 00-1+11
if i < k
3. Ck.
for each i [A]]
10-
if k
4. Return (Ak, BR, Ck).
Remark In the theoretically analyzed algorithm given in Section
2.2 we take the midpoints be K {0, K..... KK""" K-1). But here, we take the midpoints to be { ...., K
since the X, X., making the correction term pH, B.BBBB...bB.. (b(X, 1) b(Xe, t)) 0 when i 0.
14

---

A.2 Number of Neural Network Calls
While each step of Poisson Midpoint Method approximates K steps of DDPM. can use more than one neural network calls. Since neural networks calls are the most computationally expensive parts of diffusion models (4 orders of magnitude larger FLOPs compared to other computations), we compute the number of neural network calls for the Poisson Midpoint Method given K, N for both OPTION I and OPTION 2.
For OPTION 1, b(X,, i) is always computed. b ((x-i+1: -i+ needs to be computed iff H, = 1. is easy to show that E E [K 1] H, = 1}| K-1 Thus, the expected number of neural network calls per step is 2 k. The total number number of neural network calls is N
K
K (2 k)
OPTION 2 always computes evaluates b() twice per step. Therefore, the number of neural network
calls is 2NV K
A.3 FID Evaluation Details
FID scores between two image datasets can vary greatly depending on the image processing details which do not have much bearing on visual characteristics (such png jpeg) [37]. Thus, we utilize the standardized Clean-FID codebase [37] to compute the scores for all the datasets. As is standard, generate 50k images for all our evaluations. For CelebAHQ 256, evaluate the CLIP-FID scores against the combined 30k training and validation samples of the CelebA 1024x 1024 dataset [22), where the CLIP-FID is invoked by using the flags model name clip vir b 32 and mode clean (37. For FFHQ 256, we utilize the precomputed statistics of 337 on the 1024 resolution trainval70k split with the flags dataset_splic
trainfull and modezclean. As for LSUN Churches [49), we utilize the precomputed statistics of [37] with the flags dataser_split = trainfull and mode=clean to calculate the FID. And for LSUN Bedrooms [49], we downloaded the training split of [39] which consists of 3,033,042 images and used the codebase of [37 to compute the FID between two folders.
A.4 Hardware Description and Execution Time
For our experiments, utilized nigh-performance computational setup consisting of 8 NVIDIA A A100-SXM4 GPUs, each with 40 GB of VRAM, an Intel Xeon CPU with 96 cores operating at 2.2 GHz, and 1.3 TiB of RAM. The experiments take about 16 hours generate 50k images with 1000 neural network calls per image and batch size of 50. The time is proportionally lower when fewer neural network calls are used.
A.5 DDPM Variant Details
We describe 3 different variants for DDPM, based on different choices coefficients a,, b,, o, used in Section A.1 Our observations indicate that each variant performs optimally for different datasets and for different ranges of the diffusion steps. For example, consider the DDPM variants of LSUN Churches in Figure 1b Note that, Variant 3 outperforms Variant 2 for all steps less than or equal to 125 and vice versa for larger steps. Similar phenomenon can be observed for CelebAHQ 256 as shown in Figure La] Variant 2 outperforms the rest of the variants for steps smaller than 125, while Variant 1 achieves the best performance for larger steps. For FFHQ 256, similar phase transitions can be observed in Figure Iclat at around 50-100 steps. For LSUN Bedrooms, we observed that Variant outperforms 1 and 3 on all the regimes. Our experiments were carried out on all the variants and on all the steps, and the best scores are considered for comparison with Poisson Midpoint Method in Table Let ay; Br, ā, be as defined in 20).
Variant 1: The first variant uses the following closed form expression to perform the update.
(1-var) ar) Var(1 (11-a) a.)
(1 -
Br
X
Va X, 2.
b(X,,t) a 7, where of 1- 3,
(13)
Variant 2: The second variant of DDPM uses the default coefficients of DDIM provided in the codebase of (39), with 7 = 1 and of
(1-
(1- )
Variant 3:
The third variant of DDPM also uses the default coefficients of DDIM with 7 = 1,
uses modified lower variance of (1 a.) B
15

---

Latent Diffusion Model (CelebAHQ 256)
Latent Diffusion Model (LSUN Churches)
DUPM Var ant
DDPM Var ant
DDPM Var
DDPM Var ant
DDPM Var ant
ClipFF
RID
20
20
100
200
500
750 1000
50
100
200
500
750 1000
Number Neural Network Calls
Number of Neurol Network Calls
(a) CelebAHQ 256 DDPM Variants
(b) LSUN Churches DDPM Variants
Latent Diffusion Model (FFHQ 256)
DII-M Variant
DDPM Variant 2
Clip-FID
Number of Neural Network Call
(c) FFHQ 256 DDPM Variants
Figure 1: Comparison of different variants of DDPM
Poisson Midpoint Variant
Number of Diffusion Steps Number of Neural Network Calls
OPTION 2
OPTION
20
25
40 /
50 /
100
125 /
200
250
500 /
40
80
97.5
190
234.375
360
437.5
750
Variant la
14.57
3.29
2.24
2.21
2.26
2.28
2.31
2.30
2.29
Variant lb
11.85
2.75
2.47
2.15
2.48
2.54
2.52
2.50
2.44
Variant lc
9.65
2.44
2.74
2.27
2.76
2.80
2.85
2.86
2.77
Variant Id
7.72
2.40
3.13
2.45
3.11
3.15
3.21
3.19
3.12
Variant 2
12.34
2.90
2.53
2.23
2.52
2.55
2.61
2.59
2.47
Variant
12.99
3.27
2.56
2.60
2.55
2.51
2.49
2.47
2.38
Table 3: CelebAHQ 256 Comparison Poisson Midpoint Variants
A.6 Poisson Midpoint Variant Details
Similar to DDPM, perform experiments for different choice of coefficients a, by, dg. Variants and 3 Poisson Midpoint are defined with the same coefficients of the corresponding DDPM variants 2 and 3. Poisson Midpoint Method introduces additional noise due to the randomness present in H,. This becomes very large whenever K large. Hence we reduce this randomness by reducing the variance of the Gaussian suggested by [0] Specifically, for Variant consider four sub-variants la, 1b, Ic, 1d that respectively correspond to variances of 1+1-9, for == (-1,0, 1,2), with the rest of the coefficients a, by defined as Note that the variance inversely proportional to i.
16

---

Poisson Midpoint Variant
Number Diffusion Steps Number Neural Network Calls
OPTION 2
OPTION
20
25
40 /
50 /
100 /
125 /
200
250
500 /
40
50
80
100
200
250
360
437.5
750
Variant la
12.44
9.18
6.04
5.30
4.12
4.14
4.07
4.05
4.41
Variant lb
12.60
9.52
6.38
5.50
4.47
4.31
4.24
4.27
4.69
Variant lc
12.66
9.92
6.76
5.99
4.79
4.61
4.61
4.58
4.94
Variant ld
13.04
10.39
7.22
6.45
5.09
4.91
4.93
4.85
5.27
Variant
11.18
8.21
5.45
4.75
3.81
3.77
3.77
3.75
4.22
Variant
3.59
3.33
3.58
3.65
3.75
3.71
3.77
3.84
4.45
Table 4: LSUN Churches Comparison of Poisson Midpoint Variants
Poisson Midpoint Variant
Number of Diffusion Steps Number Neural Network Calls
OPTION 2
OPTION
20
25
40 /
50 /
100 /
125
200 /
250
500
40
50
80
100
200
250
360
437.5
750
Variant la
54.92
16.87
6.01
5.31
5.14
5.21
5.36
5.33
5.61
Variant lb
47.03
13.46
4.98
4.78
4.69
4.79
4.72
4.81
4.97
Variant lc
38.58
9.67
4.73
4.73
4.87
4.91
4.85
4.87
4.96
Variant ld
31.33
7.57
5.07
5,47
5.58
5.65
5.50
5.58
5.57
Variant 2
46.52
12.47
4.69
4.46
4.52
4.51
4.56
4.56
4.81
Variant
39.82
9.17
4.39
4.40
4.55
4.60
4.66
4.65
4.98
Table 5: LSUN Bedrooms Comparison of Poisson Midpoint Variants
We observe that lower variance leads faster convergence when the number of diffusion steps is small. However, higher variances yield slightly better scores at higher steps, better quality at the expense of increased neural network evaluations. This phenomenon can be observed in Tables 3 and the optimal score for each step-size/neuraa network calls is highlighted in bold. Therefore, we evaluate samples on all of the above mentioned variants and choose the best variant for every number of steps/neural network calls. We see that whenever K is small (2-4), then OPTION 1 uses fewer neural network calls than OPTION 2. However, the without replacement sampling technique in OPTION incurs lower variance error in the updates, allowing better convergence with lower number of steps (See Section A.2). Thus, we use OPTION for smaller number of steps and OPTION for larger number of steps.
B DPM-Solver Variant Details
For unconditional image generation of high-resolution images, third order (order=3) Multistep DPM- Solvers with uniform time steps are recommended. To ensure competitive benchmark, we evaluate the DPM-Solver on different settings by tuning the parameters 'order" and 'skip_type'. Our evaluations are shown in Table 7 where the best score for every setting, highlighted in bold, are chosen in our plots for comparison. We use the official code of (37] with parameters 'algorithm_ree type dpmsolver' 'method multistep' and vary the parameters 'order' and 'skip_tyy hippttye'' accordingly.
17

---

Poisson Midpoint Variant
Number of Diffusion Steps Number Neural Network Calls
OPTION 2
OPTION
20
25
40 /
50 /
100 /
125 /
200
250
500 /
40
50
80
100
200
250
360
437.5
750
Variant la
16.08
5.27
2.96
2.82
2.83
2.82
2.89
2.90
2.97
Variant lb
13.26
4.31
2.79
2.77
2.81
2.80
2.82
2.85
2.91
Variant lc
11.07
3.53
2.80
2.88
2.90
2.95
2.94
2.95
3.01
Variant ld
9.39
3.21
3.04
3.15
3.22
3.24
3.21
3.18
3.24
Variant
13.79
4.44
2.66
2.63
2.63
2.65
2.66
2.64
2.79
Variant
13.65
4.11
2.64
2.65
2.76
2.78
2.80
2.82
2.98
Table 6: FFHQ 256
Comparison of Poisson Midpoint Variants
C Proof of Theorem
The proof relies on the Wasserstein CLT based approach introduced [0] to compare two discrete time stochastic processes. For the sake of clarity we consider the drift function b(x, to be b(x) (i.e., time invariant). However, the proof goes through for time varying drifts as well.
C.1 The Variana Decomposition:
In the Lemma below, will rewrite the update equations for XIK++ given in Equation (8) in the same form as the update equations for S(4, G,T, r, x) given in Equation T The lemma follows by re-arranging the terms in Equation (8)
Lemma 1, We can write
NIK+H+1 A NIK- + Ga [M(Xxxtt) + T 7.K+i K
Where 7 = ZaK+i BLC+ + SiK+i such that "bias" BeC+i is defined as
BuK+ = r G [b(((t+)) - b(Xxx+)]]
K
and the variance SiK+s +s is defined as:
: K(H,, - I A (BBB(AKK)))) 6(8xk)
C.2 Random Function Representation
By Equation I]. the iterates of S(A, satisfy:
Xek+i+1 A XIK+1 G [((ek+)) To ZiK+i
(14)
K
By Lemma write down the interpolating process
XiK+it1 Aa X,x + Go [o(XuKtt) + + Zikti
(15)
Note that while ZeK+s are i...d. A/ I) vectors, ZiK-i can be non-Gaussian and non-i.i.d. Below we will show that the KL divergence between the joint laws of (Xek4i)ts and (Ker+))t, can be bounded by bounding the KL divergence between (Zik+i)t.s and (ZKK+)i, We state the following standard results from information theory.
Lemma 2 (Chain Rule for KL divergence). Let p, q.q be probability distributions over X x Y where X and y are polish spaces. Let Pa: Qu denote their respective marginals over X and let Pyler 2y1z denote the conditional distribution over conditioned on E X. Then,
KL (pll9) KL (p=lllgw) Euwp, KL (po1zellgjja)
18

---

Table 7: Comparison of DPM Solver Variants
CelebAHQ 256
Order
Order =3
Neural Network
Calls
Uniform
logSNR
Quadratic
Uniform
logSNR
Quadratic
10
3.06
4.05
4.58
3.07
3.44
4.31
15
2.90
3.13
3.35
2.79
2.82
3.16
20
2.78
2.83
2.99
2.64
2.66
2.84
25
2.72
2.70
2.83
2.60
2.62
2.72
50
2.57
2.56
2.60
2.57
2.55
2.56
100
2.53
2.53
2.55
2.55
2.50
2.55
LSUN Churches 256
Order 2
Order=3
Neural Network Calls
Uniform
logSNR
Quadratic
Uniform
logSNR
Quadratic
I0
3.72
8.92
7.62
3.67
7.31
7.60
3.42
5.99
5.60
3.48
5.24
5.33
20
3,44
5.09
4.84
3.55
4.56
4.64
3.52
4.64
4.62
3.63
4.29
4.33
50
3.88
4.16
4.19
3.64
4.06
3.97
100
4.03
4.07
4.06
3.65
3.99
4.04
LSUN Bedrooms 256
Order = 2
Order =
Neural Network
Calls
Uniform
logSNR
Quadratic
Uniform
logSNR
Quadratic
I0
5.85
10.90
9.58
6,40
9.50
9.36
15
5,80
7.07
6.82
5.91
6.44
6.50
20
5.78
6.07
5.90
5.51
5.63
5.64
25
5,65
5,68
5.55
5.35
5.31
5.33
50
5,40
5,07
5,08
5,02
4.95
5,01
100
5.13
4.98
4.98
4.82
4.93
4.93
FFIQ 256
Order 2
Order =
Neural Network Calls
Uniform
logSNR
Quadratic
Uniform
logSNR
Quadratic
10
4.41
4.62
6.05
4.19
4.12
5.73
15
4.23
3.77
4.48
3.80
3.62
4.26
20
4.03
3.55
3.98
3.61
3.44
3.78
25
3.93
3.49
3.77
3.53
3.43
3.61
3.68
3.40
3.47
3.37
3.38
3.43
100
3.50
3.37
3.40
3.28
3.37
3.37
We refer 44
Lemma 4.18] for proof.
Lemma 3 (Data Processing Inequality). Let F: + R be any measurable function. Let P, be any probability distributions over Rtt, Then, the following inequality holds:
KL (F+ KL (PllQ)
The lemma below follows from the fact that Equation and Equation form.
15 have the same functional
19

---

Lemma 4. Suppose S(A, GIT, R) and PS(A,G a. K) are initialized at the same point Xo. That is, Xo Xo. Then, there exists a measurable function FT such that the following hold almost surely.
= (X-(os-s=FFi(X> Zo..... Zr-1)
and
(X+)os-ST = (x, Zo...., 71
By Lemma
and Lemma
4 we have:
KL (Law (X((XX)))sss))))
)os=s)))
KL (Law(X) (Na,(Xo 1o.r-1) Xo, Zo:r-1)
Exx KL (Law( Zo Xo) (o) +
Σ 11) KL Law
Xo)
(16)
In the last step, have used the chain rule (Lemma
C.3 Controlling KL Divergence via Wasserstein Distances
now seek to control the individual KL--divergences the RHS of Equation (66 via Wasserstein distances. We re-state (TO) Lemma 26]:
Lemma 5. Suppose ~ N(O, I)). Let A and B be random variables independent Z. Then,
KL (Law(ZZ La]lLaw(Z + B)) 20 W (A.B)
The Lemma below follows from the triangle inequality for Wasserstein distance.
Lemma 6. Let A, B, be random vectors over R& with finite second moments. Then,
(2(Law(A), Law(B + C)) S (2(Law(A), LB)(B)) + /EI|CI|2
From Lemma we show that 2, = Z, + B, + S,. Conditioned on Zo.r-1, Xo. Z, ~ NNO,, I) and independent of S, now use Gaussian splitting: if A1, A2 ~ ~N i.i.d, then 4
v2 N I). Therefore, letting 2, 2r be i.i.d from N I) independent of 2o Xos S, B,, we can write:
KL (Law(Z,1Zo.rr Xo)l|(a(Z)
< W3 (Law( (-2) ) Law(
Zra
+ S + B, Zo.r-1, Xo) v2
1 wg (Law(Z+.)) Law Z + V2(S, B,) [a)))Zu.-111 Xx))
S W3 Law( 12,, + 2E 21
(17)
In the second step, we have used the inequality in Lemma 5 In the third step we have used Lemma 6
C.4 Bounding the Error Along the Trajectory:
In Equation [17] we note that Zr is Gaussian but S, need not be Gaussian (but has zero mean). In
the lemma stated below, show that Zr,2 v2s, 77 -1, Xo is close Gaussian of the same variance by adapting the arguments given in the proof of [5] Lemma 1.6]. The proof is defered to
Section D
Lemma 7. Suppose N is random vector such that the following conditions are satisfied:
20

---

1. |N S 3 almost surely, EN = 0 and ENNT = E.
2. N takes its value in a one dimensional sub-space almost surely.
Suppose I), is independent of N. Let P LLL 2 and Q Law(Z N). Denoting v = Tr( Then,
(W₂ (P, (P) & 3(1 13 + 3222 exp( 339
(18)
We also have the crude bound:
(W₂ (P) < 2v
(19)
The next lemma demonstrates the convexity of the Wasserstein distance, which is a straightforward consequence of the Kantorovich duality [47]
Lemma 8 (Convexity of Wasserstein Distance). Suppose μ is a measure over RR and Q(::)) be kernel over F with respect to some arbitrary measurable space Q and let M be a probability measure over Q. That is (.,w) is probability distribution over Rdd for every ws E S2
W/ n, / ((. =
Ws (14, Q(,,)) dM(w)
Lemma 9 (Wasserstein Distance Between Gaussians, (36]
E.) E2)) = Tr(E, + E2 - E,
Lemma 10. Let
: Law (awt22))))) =N
Q = Law Zkttt2
v2(Sk(+:)| + Zo. 2o:k++-1)
Define the random variable
B |KT G [((ee+t) b(Xxx)ll
K
( CE
kT
g+
K
+
K²
g0
+
8""
K
1Z.
(20)
Proof. Note that
E[ VV 25 2o XXo
Now, define the random variable
B |KT Ga
(6 ((ex=.)) 110---8(80 b(xxx)ll
(21)
K K
Clearly, 3 is measurable with respect to the sigma algebra of Zo.Kiti-1, Ko-K-ti1,, Xg. By the definition of S.k+i. is clear that +|l < 3 almost surely. Define the conditional covariance (only in this proof) to be:
Σ: 2E,2 10 1,
(22)
Thus, almost surely:
Tr(E) < 2,32 K
V2SIK= takes its values in a one-dimensional sub-space almost surely when conditioned on Zo.Keti-1, Zo.keti-1, Xo It is independent of ZiK+i conditioned on Zo.kiti-1- -o. Xo-
Let us now define the following random probability distributions measurable with respect to the sigma algebra of Zo.K
1. Q = Law(Zker12 + V28K41 Zo.ketr-1,
21

---

2. P Law
Eoa Zo,
First, note that by Lemma
8 and Jensen's inequality, we have:
W (P.Q) I E[W2 (P,Q) 1ux s 2 (P. W (P, Q) 2 Kttii Xol
(23)
First consider W (P, P). Conditioned on 2u:K++i-1: Zu kttiii Xu. E has at-most non-zero eigenvalue. Without loss of generality, Lemma we conclude that:
take Σ vejel for the calculations below. From
W (P,P) S Tr(21 + - 2 2)
2 レレレ 20- D²
(24)
In the last step, we have used the following inequality which follows from the mean-value theorem: v 2 1 //2 g. We check that the conditions for Lemma hold for P, Q (almost surely conditioned on 10.keti-1, Xo) and v K
n²
z²
to conclude:
2,32
W (P.Q) 5
920 K
8 K
exp
38
)1(3) 1)+
1 >
82
0
g00 KJ
g K
1
- 1)
1(3 1)
(25)
K
Combining this with Equation
24
we conclude that for any r 2 1:
()(P,Q)
SC
g4
6
11)
T4 1( 11
K
KJ
K
C
K2
+
K3
K2 1(3>1)
C
+ 320
86
93r
(26)
R
K
K
K
C.5 Finishing The Proof
We combine Equations (16) and 11 with Lemma 10 to conclude the result Theorem
D Proof of Lemma 7
The crude bound in Equation 19 follows via naive coupling argument. We will now sketch a proof Equation (18) in Lemma by showcasing how to modify the proof of [52] Lemma 1.6]. Our proof deals with a specialized case compared to [51] Lemma 1.6]. This allows us to derive stronger result. In this section, by 'original proof", we refer the proof in (52).
Since N is supported on a single dimensional sub-space almost surely, we take this direction to be ei almost surely without loss of generality. We thus take the covariance matrix of N to be Σ velcl.
We generate jointly distributed random vectors Z, Z' E Rd as follows:
Let (Z, eÿ) are i.i.d. standard normal random variables for j =,, -,.... and (Z', e,) (Z, almost surely. We generate (Z', en) to be standard normal independent of ((Z, ez)) Let (N, be independent of Z'. We draw
(Z, e1) to be standard normally distributed and Wasserstein-2 optimally coupled to
(Z' (N.es) and vI+v
independent of all other random variables mentioned above. We can easily check that (VI EZ, N) as defined above is coupling between P.Q.
22

---

Via this coupling, we conclude that:
(2. & VE(VI+u(Zze) (Z - G))2
=vi+ (Z,e1), (Z',e) e + (N,e))
(27)
vI+
Let 21 (Z, e1) and Z == (Z' 01). N1 == 6)) We define m proof that a value of infinity can be easily handled). We see that
1+ 1 (and note throughout the
4 /
L
4 +
J
N₁
vT+0
f instead of Note that / N is denoted by Y in the original proof and the bound is |||| ||N] & 8 in this proof.
Consider the function f(x), which denotes the ratio of density function of Zi-Ni point x.
vI+v to that of Zi at the
Ef(Z))² = E exp (NV + (NT))) + 2mNNN
r(m))
(28)
2(m +
2(m² 1)
Where N/ is an i.i.d copy of Nı and r(n) 21n log(1 -ー
Define Q1 = (NN+ (N))))2 + 2(m2-1) r(m). We modify the estimates in Lemma 4.4 and ((m+l)
Lemma 4.5 in the original proof in the following:
Lemma 11. 1. 1Q1l <
N
+ 6
m+1 2(m2-1) almost surely
m+1
2. [[Q1] = 21m (mm)
3. [[Q <
m +2m
2(m"-1)
Proof.
1. Note that r(m) S Tmm=11j By triangle inequality, we have:
M|NNN
8²
1Q
+ 2(m² 1)
(29)
+
m
1
2. A direct calculation shows the identity for EQ1
3. Now, consider EQA. We follow the proof of 52 Lemma 4.5), to conclude the following inequalities. Since EQ1 S 0 and 2(m r(m) 2 O, we have:
1
EQ$ < E(Q1
+ r(m))²
2(m² 1)
m²
1
EN (N
B(N + (2
(m 1)2
4(m 1)a
m²
1
E(N? + (2))
(m² - 1)
4(m + 1)2
mfB² + 2m²
(30)
2(m² - 1)2
Note that the parameter found in the original proof satisfies a; -1 in proof. We now proceed
with the proof of Lemma Define R(Q) exp(Q) Q q²
From the original proof, we
conclude via the Talagrand transport inequality that: 2
23

---

W3 (Z,e1)
(Z' .e1) + (N, (N,
VI+ V
e1)
22 {
1] = E[Qi] + 1 [[Q + (31)
From Lemma
and using the fact that r(m) 2 0, we note that:
1 B[QR
3 + m33²
[[Q1] + 2
4(m² 1)²
Now, let bound ER((1)). Via a straightforwwrd application of the taylor series, we have almost surely:
R(Q1)= S Q exI((x)()))))
(32)
6
From Lemma 11
we conclude that [Q1l S 3² 21m Since S B8, we must have 1+
2
1 + 1. 3zz
Thus, we have 1Q1l $
3.9 2
almost surely. Using this in Equation 32) we have:
ER(Q1) SE exp
E11.
382 2
6
B²
30
4 exp( 2
mf²* + m2 82
339
exp
(33)
4(m² 1)2
In the last step, we have used item 3 of Lemma along with the fact that m33² 2 1. Combining these estimates with Equation 31
we conclude:
(ws (2,ei (Z,e). Z +))
+ (N, c1) (.
)
14 + m²
30a exp(
3 m1322
VI+
2(m
1)2
2
+
2(m² 1)2
Now, we use the fact that m = 1 + 1. which implies
m²-1 S (m-
S v2. Thus, we have:
Wa (Z, e1); (z) (N,
(VZ,
1 (NN
g4y3
BBn27
3r B
3
exp(
(34)
V1+
2
2
Using the fact that 3 > we have: 3w
< 23 Thus, 2(1 + 223332 < 2,82 + 284
2(1 + (3 + B1v3). Plugging this into Equation (27). we conclude the result.
E Overdamped Langevin Dynamics
In this section, we will prove Theorem 2 after developing some key results regarding OLMC. Recall that this case 7) Fx)) for some Rdd R. G Ca - and r a = V
22.. Let
K
K
N₂ Σÿ= H. Throughout this section, we assume that F is T-LLipschizz. We will assume that T is power of 2 in this entire section, which useful apply Lemma 26 The results hold for any T by considering the closest power of 2 above instead.
Recall Bi from Theorem I Instantiating this for Overdamped Langevin Dynamics, we conclude that for any i E (0) and siik - 1, we must have:
L'a
B
sup 0sisk-1
|ixetss
11
(35)
2K
24

---

Here, we have used the fact that VF is L-Lipschitz. Now, consider +s in Theorem
For any p 1,4, NU (0) and 0 sis K have:
PIK+i S [aak y
sup 0Sisk-1
|| Xix|12p
(36)
In order to apply Theorem we will now proceed to bound the quantities the RHS of Equations (35 and (36
E.1 Bounding the Moments
The following lemma gives us almost sure control over quantities of interest. We refer to Section for the proof.
Lemma 12. Suppose the stepsize aL < Let M = V R suposick Ei Zok+sll. Then the following hold almost surely for every 0 v k - K
1.
|iitH Nexl & <a]VF((Xxx)] +,,
sup 0sick-1
2.
|8 Xextill aLN, sup isk-1
[|ae+t X
sup ugict
3.
B[M[K] S ((p)
We will now prove the following growth estimate for the trajectory İ.K. We refer to Section I.2 for its proof.
Lemma 13. Letp be fixed. There exists a large enough constant Op which depends only p such that whenever t aLC,' have:
E EI 12
s 30 - ((]FF))) Cp add(s - t)
sup tShS
We apply Lemma 26 along with Lemma 13 to conclude the following result which proved in
Section [.4
Lemma 14. There exists constant ep such that whenever aL S Cp. have:
I
((()((()))1 S C,I'LTT + C,(a-) E
IVF((x))
(37)
While Lemma 14 controlled Etn B BIVF )1 in terms of Ein |V (| in the Lemma
below we control E (VF(xx)) We refer to Section L.5 for its proof.
Lemma 15. Suppose p 2 1 be arbitrary. There exists Co > small enough such that whenever aL < Cpi we have for some constant Cp 0 depending only on p.
[VF(Xx)) < (FE((((X)) F(XKT)) + 1 2
E
(V((xx))1
oR
Cp ap
C,IPTTT
(38)
We combine the results of Lemma 14 and Lemma
15 to conclude the following result:
25

---

Lemma 16. Given p 2 1 arbitrary, there exists a constant cp > 0 depending only such that
whenever al < Cp and - 1.0-111--177-11 < Cp. we must have:
CpI BI(F(Xo) - (F(xX)))((
E (X (
(aLT))+)
Lemma 17. 1.
CTAa3
[[ + CTA K
But+ll+ S
d
K
2.
BP Ikt
S Cp K
2 2
Proof.
1. Using Equation 350.
we have:
Lda
E| Bik+ill
E
sup
[[itt] - X1K+zl1
2K
osisk-1
L'
L
[|Eexee - 8ex|1
<
EN?
sup
2K
0SisK-1
Laa
18ek+j= 1
E
sup
K
0Sisk-1
CL 3
[2
ad)
(39)
K
2. We use Equation 36 and proceed as in item! 1.
E.2 Finishing The Proof
For p 2 1, we define A (P) == (X,) - Fx)))p) Let < denote I up to a universal positive
multiplicative constant the RHS. We now combine Lemma r == 7) to conclude the following bound:
Lemma 15 with Theorem (taking
KL
+1)
+ (aa +
+
+ "T=""
(40)
F Underdamped Langevin Dynamics
In this section, we will prove Theorem 3 after developing some key results regarding ULMC. We will assume that 7 is power of in this entire section, which useful apply Lemma 26 The results hold for any T by considering the closest power of 2 above instead. Recall that in the case of ULMC, we have:
La
(1 sh
- - (1 (1---1-pp - of b(Xi)
VF(U))
A
GA
0
e
7h 7 La
) e
h
2 e -hh + 1 (1 - e 2xt)) La
11 2e 7h 27
T
7
1 (1 - 2e + E 27h Lt
(1 e -27 Lt
26

---

With some abuse of notation, we Throughout this section, we assume that VF(()) is L-Lisshitz. We let N₁ == Σi= Hr, We let II
Ia 0
be the projector to the first d-dimensions in the standard basis. That is, 11 :=
0
The 2d dimensional space can be decomposed into position (sub-space spanned by the first d standard basis vectors) and velocity (sub-space spanned by the last standard basis vectors) sub-spaces. We
V
use the convention that X E IR22d is such that X
where E IRd the position and R is
U
the velocity. Throughout this section, we implicity let X, =
let = ILX and V = (I-Ii) x)..
The following lemma collects some useful bounds on A,e GA and Th, and is proved in Section I.6 Lemma 18.
C (Chexpt2rhi
GT 3
For all 0,i K 1,
3a²
IITA G
exp(
30 K
R
2K
Analogous to the analysis of Overdamped Langevin Dynamics, consider the following dynamics.
F1 Bounding the Moments:
Using the scaling relations Section 2.1 we write down the iteration of PS(A, G,T, 6, a, K) for Underdamped Langevin Dynamics as:
Xat1jK A. + Gab(Kek) aa. +r..
(41)
kK1 KHIA a(K-A)(--- Ga -(XxKH))((8eR) and T.Y. =
Where,
ad:
K
Σj=o Aa(K-1-1) Pa lik+s.
K K
Applying the triangle incquality, conclude the following lemma.
Lemma 19. Suppose that || Ilany is any semi-norm over Rd. Then the following hold almost surely
for every 0 S l: S K
1.
LiKti - Xexllany S 11A - 1)Xxxlla + ||G b(Xxx)
K
1-1
A a((i1-1))
Da Zektsllany K
/=0
K
2.
11 & Σ
KH3 (1-1-ja Ga (b(Xex<s)) b(xxx)))l llany
Define :0:=Upp UKe + VKa, d/,
The following Lemma, proved in Section 1.7 gives the time evolution of
7.
Lemma 20.
K-1 H.a - W.
0'r+1 - v -===((((x)) ?
Σ
Where U ~N(, 2a)) is independent of Xax but not necessarily indepependent of Ü.Kas for i >>> 0.
27

---

Lemma 21. Consider the seminorm given by | = I
Let MrK ==
sup 11 | a(1-1-1) l' Z lm.. For any 0 Sis K 1.
K
1.
(42)
2.
F(W+41)-
-1 Bo )| V( -V -V((t))VV((())).) V.)
S
a
47
3L
3aL Vix 1?
+ (VF(U)), (.) +
1 +
2
27d
+ NtaL²
1+ 27
3aL)
sup 0sisK-1
|lie+: Uex1 12
(43)
3. For any 2 1, we have:
pya E )r (d + log K)
EMEx S Cexp(
2
We refer to Section 1.8 for the proof. Analogous to Section
E for any 2 1, we define (V) Ets ||V (2 = (VF The following lemma, proved in Section 1.9
bounds the moments of these quantities.
Lemma 22. There exists a constant cu such that whenever ya < 1, al < Then the following relationships hold:
1.
((S2
C E 12g
6
((S)(VF)) C2(T log K)
7a)
ya
L
2TT Pa²
12T pa
(V))
ESS [FF)
(44)
72
72
2.
1
2 (F(VV) +(P
CI2
(E(S2 Cp [T(dd + log KYT + 2]
x2
C,T a2a
(ES (
p I -
1
2ES (VF)) (45)
Suppose additionally that y 2 CuVL for some large enough universal constant Co. Then, the bounds above imply the following inequalities:
1.
((S)(V)))
1
2
E
C (F(Vo) - F(Ur))+11
ya
ya
(SS 1/2
+ CCp(T(d log K) + 1)
72
LTT L'T'-
7
+
[ (F))
(46)
72
28

---

2.
C7
C7 [B)(F(W)) F(
(FF)))
B vol 201
+ [[d log K)T 31
+ LL'2' (V) + C2T² - L 1ES [ES)) (47)
The following lemma gives a growth bound for Overdamped Langevin dynamics, We give the proof Section 1.10
Lemma 23. Let 8, t NU (0) such that > There exists constant cp > 0 such that whenever
al(s-t) S Cp. a> t) S cp and a² L(s t) S Cp. the following statements hold:
| Unk U1x s 8a(s - 8) |EI |P] rsh
8a(s (t(s 1) [IVF(UR))
sup
d+ log K + Ccp
(48)
L
sup t
E Vik
VuxIp]
8ra(s
ElIViK IP]
8a(s t)E [IVF(UU))P]]
d log K +pp
(49)
L.
We combine Lemma with Lemma 26 to conclude:
Lemma 24. Let be given. There exists cp 0 such that for any N which satisfies the following conditions:
1. is an integer power of and N T.
2. S Cyp N S ep and a²2 LN Cp
The following satements hold:
1.
2
ESyp C,(LaN))"SS,, + C,TL" log
NP-1 B(S2(VF)))
(50)
2.
2 (d+log
2"
(V) S Ea (VF) + T (d + log K)
+ N E(S((V)) (51)
Proof. We consider a, == (F(Ú b, = 1)k- Let N satisfy the condition in the Lemma.
Since T is power of 2, clearly, N divides T. Let Tu = {(k 1)N + L..... kN} be as defined in Lemma 26 Consider the following upper bound derived using the results of Lemma 23
T/N Σ
2
22p+1
Σ
Blla, - df1100 < 2 + C
ES2, (VF)
722
1=1 JJ f'2j
+ G,NTIP (d log K)P
(52)
29

---

Applying Lemma 26
we conclude:
2" ((S) (53)
2 VF) S (y
log log
Similarly, we have:
T/N Σ
Σ
Blbb, - - < a 1 (V) + N (VF)
1=1 j.feT f'2j
+ CGNT 2p
(d + log K)P
(54)
L
Applying Lemma 26 we conclude:
722 - (d + log K) ) + B(S())))
2F
ES (V) & (VI +
(55)
T,
Combining Lemmas 24 and 22 gives the following theorem.
Theorem 4. Fix 2 1. There exist constants Cp- Cp. Cp > O such that whenever: 7 2 CpVT.
000-1'0-11 1,20 7p4
07 Cp.
Eyp the following results hold:
2p-1
Sep VF) Cp
E Val
2p + EF( F(Ur))++++
C,T
Ap D
( (d + log KY
(V) $ Cp
1
20 ((F(Vo)) F(P + +1]
7a
(xaT)=1 (d + log log KYP 222
C,T
Le
F.2 Bounding the Bias:
Now, consider the following term in the statement of Theorem
B T G' [6((k++)) - b(Xxx+))
K
Using Lemma 18 and under the conditions of Theorem holding with 1, we have:
1 < al1
| Uix+il12
sup usisk-1
Ky
LLLAN? Ky
1iiK+s - Üex|1
sup ogisk-1
(56)
In the second step, we have used item of Lemma 19
alonn with the bounds in Lemma 18
30

---

Applying item from Lemma 21 and Theorem we conclude:
C.
B
BiK+ill
ENİE
sup osisk-1
||0ett1 - -ie
1=0
i=0
t=
Ca
T-1
E
sup 0gisK-1
|0iKti- - U2
Ca T
< 11 + + EM,xx] +
La
(a'ES2(V) -ES + Tha (d + kog
L 72
S LCa log K) +
E + - F(UT))+ +
(57)
In the first step we have used the fact that N₂ is independent of suPosisk-1 llúx+t Ün Il? and the second step follows from the fact that EN? 2. In the third step have used item 1 from Lemma 21 In the fourth step, we have used item of Lemma 21 the final step we have used
Theorem 4
F.3 Bounding the Variance:
Now consider BiK+i KT a G
Gal((ik)) ((xx)]l- Using Lemma 18 and item of K
Lemma 21
we have:
Bik+i S CKal?
1 - 02x12
sup
7
0sisk-1
CKaL²
[a21 + + Ma,x]
(58)
Therefore, we note that for any p 2 1, under the assumptions of Theorem 4 we must have:
T- K-1
KP+1ap 1,2p" T
Σ
2p
tK-i S Cp
a 2PTR VIx | + 4PR) V (F( + EM
7p
1=0
1=0
KP+1ap1 11
< Cp
[n 1222 (V) +
ES VF) + TTpa (d log KY
7p
1p-t1ap-1111
< C
gpt1
KP+la" 3
(72p
+ (7aT)=11 ) (d + log K)"
+ Cp 7
(59)
TP
F.4 Finishing the Proof
For p 2 1, define A (p) E(F + Vo) - P By LHS S RHS we denote
LHS < C.RHS for some universal positive constant We now apply Theorem (with r 7) along
with the bounds in Equations 57 and (59)
31

---

KL (Law( (wwwa (AKe)oCIST)
(X
96
Pak+
<BllBaK
CE
Pakti
PsK+i
K²
K3
K²
K
K
12
KT A
A
(3)
A
72
73
7/
76
7
Ka²L"T
Ca L3 log K) Ka 22 (2 log 1og
(d + log K)²
12 log k)2 k
(d + log KY²²
K K 1 T + log K)s
29 1,107
(d + K) K² I log
7 2T L
(d log K)
(60)
G Convergence Under Isoperimetry Assumptions
We now prove the results concerning convergence under the assumption that n' satisfies the Logarith- mic Sobolev Inequalities (LSI). We first define the LSI by following the discussion in [46] and refer this work for further details.
Definition 1. We say that measure 't" over R& satsifies X-LSI for some X 0, ffr every smooth g Rd + R such that Ex g2() < oc, the following inequality is satisfied:
E. log g² E.. log E. g² S E. Voll2
We note that whenever the density (x) = e F(x) and F is À strongly convex, then nt satisfies the X-L.S. It is well known that X-LSI implies the Poincare inequality (PI) with parameter À defined below:
Definition 2. We say that measure nt over Id satsifies X-PI for some X > O, for every smooth g RRd + R such that Ex g2 (X) oc, the following inequality is satisfied:
1 E, V|
E 2² (Em
X
We note the following useful lemma:
Lemma 25. Let xTxxxx (x) x exp(-F (xx)) satisfy X-PI or X-LSI and let F' be L-smooth. Then, L 2 A.
Proof. Let X" X n² be i.i.d. Applying integration by parts, we have: EVF(X) = 0 and E(X, VF(X)) d. Note that LSI implies PI and under X-PI, must have for any unit vector E Rd:
var((X,v) 1 X
Let E be the covariance of X (it exists due to the assumption of PI). Therefore,
= E(X - X', VF(X) VF(X')
L 2dL
Tr
< 2 - - 22
<
(61)
d
In the second step have used the fact that whenever F is L-smooth, then F(x) F(y) (VF(y), y) + f| y for all x, e Rd
<
32

---

We now state 44 Theorem 1] (adapting to our notation) which gives convergence guarantees for OLMC under the assumption of A-LSI.
Theorem S. Suppose n" (x) exp(-F(x)) satisfies the X-LSI and that F is L-smooth. Consider
OLMC with set size n which satsifies 0 17 S 242. Then, LMC satisfies:
KL (Law(Xw)]lss S - (Law(Xo)]l<**) + 8d..2
X
Where Xo..... XN are the iterates of OLMC.
2KL (Lom(Xo)|
Whenever S 1, we take
a
de² T6dT.
T
1 log
With the suggested
ax
initialization in 45 i. Xo (x,, t) for any stationary point x of P we have KL (Law (Law(X)]l|=*) S
(d)). Now, take Co min
e LEdd
)
.T
(i) and aLvd'
L
Let Xo...., XTK be the iterates of OLMC with step-size K with the parameters as chosen above. Applying Theorem we conclude: KL (Law(Xrk))l S 2
Let X² ......... .f be the iterates of PS(A, a, K) with A, G.T corresponding to OLMC. Apply-
ing Theorem (with the explicit lower order terms given in Equation (40),, we conclude that:
KL (X)))X/a((WXXr)))) S S.
Now, by Pinsker's inequality and the triangle inequality for TV distance, have:
TV(Law(XXF (f), x²* & 2KL (Law(X,) (x.) (Laa(X/))|laa((((( [|Laa(XX))) + /2KL (Law(Xrx))le (| Sc
(62)
This proves the result in Table OLMC
We now consider the analogous result for ULMC below. The following result is re-statement of Theorem 7J. We note that CLsI in this work is I in our work.
53
Theorem 6. Let Xo...., XN be the iterates of ULMC with step-size n. We make the following assumptions:
1. F is L-smooth and that n² satisfies X-LSI.
2. Suppose x be any stationary point of F. Initialize Xo such that Uo. Vo are independent with Uo N(x, ÇI) (S as given in (53)) and Vo N200 I).
3. F(x) - F(x*) = (d) and Eu,v~ | < (dd.
Let S 1. Then, we let 17 Lyd
ō( (V
T 0 /7 then, x=c
TV(Law(UN), x*) Se
Let "h....,Xxx be the iterates of ULMC with step-size -. We take: a = =
K 0 3 and N é Y We now consider x X to be the iterates of PS(A, a, K) with A, G, I' corresponding ULMC, such that X and F satisfy the same assumptions in Theorem Applying Theorem 3 alongg with Pinsker's inequality, we conclude that:
2
TV(Law(X ((P) Law((aa)) < 2
Now, using Theorem 6 along with the triangle inequality for TV, we conclude:
TV(Law(X:(P) x²) Se
This proves the bounds for ULMC in Table I
33

---

H Some Technical Results
We state the following technical lemma which will be proved in Section 1.3
Lemma 26. Let a1....,00 be random vectors in R Consider the partitioning {I....,T} =
U Then, we have:
Th where Tk = {(I 1)N + 1, +...... min(kN, T)}. Assume that N divides T and 2 N.
T Σ
2 X
2
P-1
BlJaj 1
E
|a
j=1
JET
S'ET バ'3
Lemma 27. Let Zi..... ZT be i..dd standard Gaussian random variables, and a sequence of random vectors 91..... 9r such that 9r is independent of Zi.... Zr. Then,
T
E
Us Z.) S Cpp
13)r
Proof. Let À R. Consider the random variable M, exp 2=== M/ge. Z,)
Al11..11 M, is
super martingale and hence, we have: E[Mr] s Applying the Chernoff bound, we conclude that for anly A, x > 0 we must have:
T
T
P(
9.
2,1
Σ
+ h 1g.11
x) eexp(-1).
==1
T
T
P( Σ ga. Za>l > CaA.( Σ
|1 +1)) (exp))=2xx((CxxxX CCphp)
a=1
Now, for any variable X, P(X+ > h) P(X > h) whenever 2 Now using the fact that:
EX < EE++ 50x P(X+ > hidh, and taking X = Σ.= (90, 2.) CGA 13)p:
11..113pp + [ 2 eexp( 2exp(-cpAhrjdl S CRAPE(
Cp
E
(g.. Z.) < CPPPE
1 +
AP
We conclude the result by choosing A BET
la. 1)
Lemma 28. Let K be any positive integer. Consider G ~ Bin(K, k) Then for any 1, we must
have: EGT S Cp for some constant depending only on p.
Proof. The proof is simple for K = Assume K 2 2. For any 0 S n S K, let = P(G = n). Then,
nlp, -1- 1 Kn K!
Kn(K - nn)
< (1 1 k 1) -
In the second step we have used the inequality (1 4)" < - and the fact that K 2 2.
Note that en! is the probability that the standard poisson random variable n (denote this by P.))
Therefore, we must have: Pn. 2ph. Thus, we must have;
BGP
2n 2nPri Ph S Cp
BEN
34

---

I Proofs of Technical Lemmas
I.1 Proof of Lemma 12
Proof.
1. This follows by applying the triangle inequality to the definition of NIK+..
2. Consider:
1|ie+t - Xix+ill S a
Σ
H
(F(( VF(Xx,)
1=0
i-1
H - Xexl1
j=0
1iiKts- - Xxxl1
S aN, 0sjsk-1
sup
(63)
3. This follows by direct application of Doob's 's inequality.
1.2
Proof of Lemma 13
Proof. We will use b() and VF() interchangeably in the proof. Consider the update
N Nex + (ab((xx)= + as, + V20Y..
Where y,= 1 ΣK-1 ts and A, -K-1 H.(b(Xex(+)) -((xk)) VR
Therefore, we have for any 8
İ.K X.x =
Σ
ab( xb(( + aad + 2ahn
h=t
a(s t)b(Xik) + Σ
- -((xx) aDn V2a% (64)
In this proof only, for any random variable U, we let Mp(U)- = (B(10))(***) Using the triangle inequality for Mp. we conclude:
Mp(8ak - - + -(MM
-(Xxx) + a.M)AAn)
h=t
+ V2nMMp h=0
Yn)
aass 1)(l6(Xee)) + a Σ
LMM Xxx) + MD(AN)
Cp / 22ddss -t
(65)
35

---

Now, consider An Ei= - ((xxx)) We must have
K-1
Mp(An) Mp
1.H, 1.H:||xnK++ XaKlI) S Mp(LNN E
sup osigk-1
18akti Xakl1)
==
1LaKti- Xnkll)
sup osisk-1
([(xaM(((((XXxx]) + LCpMp(AM.k)
- (Cgall((EEK)) + M'C,aM,(XXKX' Xik) + LC2
(66)
In the second line, we have used the fact that N₂ independent of suposisk-1 || X and the fact that (N,) I Cp for some constant C (Lemma 28 In the third step we have applied item from Lemma 12
Putting this back in Equation 65
conclude:
Mp(X.K - Xik) S a(s () + +IGG) + + +b,C,)
Σ
Ma(Xixx - 8(x))
h=t
Cp(La Vdls - t) + 2ad(s - t))
(67)
Therefore, we must have:
sup Mp(NnK ESh$s
1)(1 + alCp)
[M(xxx)l
sup ISNSs
Mp(X Xec)
3 (s + 2ad(s -t) + Cp(LVVd2
(68)
Now, supposing 8 - 1 5 C, for some large enough constant C which depends only on p. This ensures that (L () + aLCp) S in the equation above. Thus, we have:
Mp - Xex) s 3al(s - 1) [1b(Xxx)] + Cp dals - 1)
sup tshs
L
1.3 Proof of Lemma 26
Proof. 0s = [aal EjET, Consider the following quantity:
1.
T
||al 3p = ΣΣ 11,
1=1
1: JET
(2 101; 22 + 20-1 1
JET2
2
(1la; - ax 200 + 2P-1 'N Σ
|| 2p
k JET
< 2
Σ Σ
(1lay ax 20 2P 2 X 12)²
(69)
JETE
Now, by Jensen's 's inequality, we must have:
| < 1 Ejer, ||a.112. Therefore, we conclude:
[To]
36

---

T
T
a 20 - -" 2--11
ΣΣm
(Ila;
āx 20) + 20-2111 N\-P6
|| )
(70)
h JET
/=1
Now, consider
Σ
axl 2x
BBIa ay 11
JETA
JETN JTETa
2
Σ
Σ
Bila, - ay a 1|
(71)
JET زーンj
Using this with Equation 770 conclude the statement of the lemma.
1.4 Proof of Lemma 14
Proof. We now apply Lemma with = (((((-))x) Whenever al. S Cp for some small enough constant Cp. we can take N be the largest integer power of 2 lower than afC for large enough constant C2p such that the result of Lemma 13 with
S N. Applying Lemma 13 conclude:
ΣΣ J'T
Blla, - 051100 2
Σ E(3aLN + CppVadN)
JETN
S (aI
Blaay
(72)
JETA
Applying Lemma 26
Σ Bl 20 20 1 Ca(aNN) 2p
Σ Σ
E||ay||
20 20
20
N
||
JET
(73)
Note that whenever the constant Czp defining N above is large enough, this implies
T
T
[||ae|1 2p SCI.P'' + C,
1)p
(74)
1.5 Proof of Lemma 15
Proof. Since VF is I. Lipschitz, we have:
F(( F((x)) & ( xxk) + -
(75)
Also note that:
X = X.x aVF(E()) + as, + V2aY..
Where Y, 1 K-1
-K11 ZiK+i and A, = -K K-1 Hr, (F((x))) -
VP(Xk)))
VR
Thus, summing Equation 775) from = to T - 1, conclude:
37

---

T-1
T-1 L
(NTk)-F(AA S Σ ((+1)
- +
Σ
[[(+))x Xex!
2
1=0
1=0
3la²
VF((ik); X X(k)
[I|FF(X,x] )l + 1|1+,1111 + 3L
[a 1 3م |A 112 3La|I
(F( Yn)
V( Aall 3La||Y/l| + V2 Yi)
(76)
In the last step, have used the fact that 2 (VF(X()) A. S VV )12 + || and the assumption that aL S Cp for some small enough constant Cp.
Therefore, we conclude:
[VF(Xx))))) S
So o0
-
T-1 Σ
| + C,L
T-1
|
(F((
(77)
The properties of Gaussians show that: BΣ |
S C,T'd'
By Lemma 27 and the AM-GM inequality, we conclude that for any 0 arbitrary, we have:
Cp
T
E
(VF(
E
[VF(K1))
Q0/2
QP/2
t=
RCp
Cp E 2k
T-1
[VF(Xx))13
(78)
2n0
E(
1 p < T
E|| |1 2p
$ 7
EE(N.) 29 L
sup oSisk-1
||
Xxx 20
T-1
S C
L P
sup 0SisK-1
[
2
(79)
t=0
In the first step, have used Jensen's inequality. In the second step we have used the fact that F is L-Liisheitzz and that N, is independent of XiK+t for 0 < < K - 1. In the last step, we have used the fact that 22, < Cp for some constant Cp (Lemma 28
By Lemma
we have:
E sup osisk
DIK- NIK 1p <
(F dr
Plugging all of these bounds, and taking x in Equation
78 to be large enough, we conclude:
38

---

E
()P( (F((()))) F(XxT))* + 1,70-11,300 2 a
V VF((x))
Cp a
+ CT
(80)
1.6
Proof of Lemma 18
Proof. For the sake of clarity, define 1 - exp(->h). (1-x)²
(h 21--)) + 11 22
1(1-22)
29
Algebraic manipulations show that:
(1 (1-r)3 x/)3
p
(81)
2(1 + x) (7h - (1 x)
(1-x)²
2
Now note that yh log(1 (1 x)) = Ei (1x)
Therefore, we conclude: 7h (1 - x)
(1 m
(1 x))
3 + (1-x)² Therefore,
2
2(1 + x) (1 1
(82)
V 2infre (1 t) 1
Now, we note that for scalars A, B > and p E [0, 1]. we have:
A
pABLa B
[A L 0
pABII
B²(1-p)LA - LIla
Thus, we conclude from the above computations that:
h -
21- ex1--xp(->1)) + _/4 exp(-22111) La
0
r 2
(1 ex-exp(- exp--(22)1
2 अ
(1 exp(-7h))
0 1.
(83)
(1 (1- exp((22xhh))
We have used the fact that:
h 2 (1
2 3-2
exp(-<h) (1 exp(-22th)
2 (1 -ex((-hh)3
? 7
24
Using the fact that for PSD matrices A, B A < B implies B-1 x A- we have:
[ (hexp(22M) La
G. 3 G.T.T
(84)
0
The second inequality follows easily by elementary manipulations.
39

---

1.7
Proof of Lemma 20
Proof. Explicit computations show that:
th+1 the [F((Uk)+
+
1/ A +
It [L
7 ray
Now, note that La
L An
La
and
Id
Le 7
Gn
1. L 0]
Therefore, from the
7
definition of A we conclude that:
K
la
L 7
A =
H1a
V VF(Uix)
7
0m
A straight forward calculation shows that: V :=
Ia
I
Ta Ye M(0, La))
L88
Proof of Lemma 21
Proof.
1. Note that
ÜIKH+ Ü.K 11
-I)X,X + 11G ia b(Xek)
(llAa(i--s)) I' Likts
K
K
j=0
We bound each of the terms separately.
[I(A 1) s ia |ixlll s allV/
K
a²t |F(Úk))
< a²
|G ia b(Xxx)
VF((k))
2K
K
Plugging these inequalities gives the result.
2. Since VF is I--pipschitz, we have:
L
F(1(+1) F( < (FF(D)). vi) |10141 -b2l22
2
((VF(())-F((CC M441 2b) + (VF(( 24 - -ba) + 2
- 111141 - 2/212
(85)
40

---

Using Lemma 20 to evaluate th Uh, we conclude:
(VF(U()) M441 V2) = |VF(Ux))] (VF(U.))
K H1
-VF((()
= ?
+ 4.
NaL (VF(ÚIK)
|[ikti U.K
sup osisk-1
$
a
K,)
[VF(Ux)) + NiaL?
a
sup 1l0Ktt - U2K
+
27
27
Osick-1
(FF(UK)) ((F(U,)) K,)
27
NtaL²
- 0ix|?
+
sup 0SiSK-1
(86)
24
In the second step, we have use the fact that VF is L-Lipschitz along with the Cauchy- Schwarz inequality. In the third step, we have used the AM-GM inequality which states that for any a, b 2 O, we have 2ab S + 1s2
Similarly, we note that:
S aL |F(U (VF())) VF(ÜkK), (.)
(VF(v)) A
NiLL
|V
||úK4t U.KI
sup
7/2
0SisK-1
30IZIIVVK 12
< (V((
(VF(b)) - VF(ŪK)),
273
Ntal?
|1úi - 12x11
sup
(87)
27
DSigK-1
We have again used the AM-GM inequality in the second step above. Convexity of x implies:
x²
3L a VFFÜ
Nta2L2
|1 -
12
|ÍiKTi - Ü2x11 11 ||
2
72
sup osigk-1
(88)
Plugging these upper bounds into Equation
85
we have:
F(#++1) F(w)) S
α
| 2112 (VF(1)) VF(Ūk)), V.))
47
3L
3aL? VeK
+ (VF(U.), V.)) +
2
2y3
NtaL²
3aL
| Ú.x
1+
sup oSiSK-1
(89)
2n
3. Using the scaling relations (Section 2.1 it is easy to show that for any such that 0 < <
K - 1, Ei IIA mni -iiii----00 1- 1) r a Zik +j is Gaussian with covariance matrix E, such that
K
Σ; 2exp(1a)7a 14.
41

---

Applying Gaussian concentration for Σj= IIA a(i a(i-1-1) K
P Zik+s along with the union
bound over all 0 S i K - 1, we conclude:
P(M,K exp (
Vlog s exp(-32/12
We conclude the moment bounds by integrating tail probabilities.
1.9
Proof of Lemma 22
Proof.
1. Let = Then, we have:
V(H1)KK gVex - 1 1- VF(ÚKK) + +(I-1)(aA, +TaY)
(90)
Now, consider:
(1=
|
|VF((()) - [I)(A, -|0]]],, +Iak)]²
72
-2
(I- 1I) +lak))
7
- -2 (1-9)
(1 (L-9) g)
$ gg[Vxx|12
+ 1| +T.Y)|
()
72
+ +2g (I - (I)a(aa, +raYi)
-2 (1- 9) (VF(UiK): ) -I- (I- + Pa)ii)
2(1 - g)
Vo
|FF(UK)) 1- vg
|II [I-
72
+ 2 - 11) 11). 11)1 + 2g(Ve. (I- 8r))
(1- (VF(((()) (I- (T)))))))))
(91)
the second step, we have use the fact that 2 (VF Pix) g(1
9) |F(0 + g(1 - g) V)x( 12_ In the third step, we have used the fact that: Vg<V (I I)JA,) s (V9 - V)]l [ I1-M),
1-v9 2(1-)) (VF(Ür)) (I
I1)a,)) < + +1 (I) - 12 -)) and [[(I (I) + +T.1)]2 S
2I - (T)aa))) + (I &.1.
With extention notation, ler (I-II1))) Dtd
ΣT- - I 2111.. Using Equation 991). we conclude:
11
Vix 1
4
S2(V)
(VF)
-I-
V9
72
(1 vg)²
+ 1 Vg
2Sp( (I
II).
T-1
Σ
2
9
(u,, (I - 1-)((T())i))
1=0
(1-9) g)
(I
(92)
71 Vg)
42

---

Note that (I - a) ~ (1- By properties of Gaussians, it is clear that
for any p 2 1, we must have E (S)((I)))aa)) I Cp(raT')". By Lemma 27 we conclude:
E
(Vx, (I- < /
<Cp(ra) sCpro ((()
E
By L smoothness of F, we have: (a),))) & LaNsssuossis 11xK Uxx1
Using the result in Lemma 21 we conclude:
T-1
(I-
& C.L P
a
+ + + N?
T-1
B
Ap N Vix 2D + a 2 E N M
t=
< 2Ppp2
(V) + C,T 1 PS VF) + 2 5p (d log K (93)
In the second step, we have used jensen's 's inequality to show that ( E. at) - T In the third step, have used the fact that N, is independent of X and that EN Cp for some constant Cp (Lemma 28).
1 Σ 44
We now use the fact that for any two random variables X, Y such that E Y < xc, E|| + YIM < E
X| $
|| Using the bounds established above and applying
them to Equation
91 we conclude:
[VS((V))
<
E 2m
+
4
((S
CI - I))A))) (1- -g)²
V9
7
Ta
7a ((S2(V))
α + Cpp
+ Cp 1
+ CCp
((S2(VF)))
Vg
1- V
C
4
[(S)))))) C(B(S)(( - 1))
2202
70
((S2(V)))] 28
+ +G,Td+ Cp
#CrV (FF))())))
Vya
C <
(())
-BB116611271 + 72
((S(()) + C,Td+
70
V7a
1. pa"
12T pa
1
Cp
(V)} + Cp
(SP)((FF)
72
72
+ C,
a + log K)
a Opp
((S((V))))
(94)
7
43

---

Here, we have used that fact that 1 - v 2 Cyaa whenever ya < 1. We now use the AM-GM inequality to show that
[V)) ((S2(())))
C
C2
70
7/0
Similarly, we have:
1 Cp / [(S))))))) <
( [
yaaa.
27
Applying this to the RHS of Equation (4) and re-arranging, we conclude the statement of the lemma.
2. Using similar methods as in item I above, we apply Lemma 27 and collect the following moment bounds:
L
E
( VF(U))) u.)l Cp
(B(S
32
1=0
7
a
(VF(Ui)), ". Cp
V ((S2(VF))
722
By a calculation similar to that in item 1, we have:
NtaL2
3aL
E
Σ
1
sup
7
27
0SigK-1
L
S C2Tr-1
(a (V) + a 5p 2p (F) + Ta 40 2 log KYJ
(95)
yp
Summing item of Lemma over t T - 1 and applying the triangle inequality for p-th moments, we have:
((S < a
+G I
CL¹
7 ((S
+ C,LT + log K)
GTT "120" + C,T' EES
(,TrL3a log
s ([I(F(()) - F
+P1 + -
Col / ((S マ2 ((()))))) + C,LT log K)
CL2
c,T P (V) + C,T 2 (VF))
(96)
In the last step, we have use the fact that aa < and La < c.. Applying AM-GM inequality
Cp (VF))) and CpLy I (V)))) 20 similar to item 1, we conclude the result.
44

---

I.10
Proof of Lemma 23
Proof.
X.K KIK (Ac(o-t)- 1)xxx +
Cab(Xnk) + aas + +TaYi Σ Aa( k=t
In this proof only, for any random variable W and any projection operator P over IRdd we let (W(WP)) == [[IIPW/"IXXx]]]] We use the convention that Mp(W) (E||WI)) Using the triangle inequality for Mp. we conclude:
Mp(Xsk 1I),11= Mpp((A((--1) - 1)X,K, II) + E-ppAdus---GGGo(Xik
h=t
5-1
Mylda(6--nnaahhh II) + Mp E Ao (97)
Similarly, we have:
1-1 I-I) Mp(Xsx - -XcK, I-K,I-I s (p - I) I II + -M
h=t
Mp(A Cab
h=t
Mp
Ac h PaY I-
(98)
By scaling relations given in Section 2.1 we have: Σi=t ILA ILAa(s NO0 ( III)
and Σ A1) Y, No,, (I -I)
II)). Notice that II ( ل| z
4a(s
0 0 27a(s -t) t)
0
and (I - (T2 (() (I- IT
0
Therefore, we conclude:
da(s t)
Mp Da Tav MT) Cp
7
Mp
11) Cp dd -t)
Notice that |I (A(A-)))) X)xx <a(s - Vxxl and || (I)-I)AA - 1)Xxxl s sa7(s
E)]l V. This implies:
- -I) 11) s a(s t).M,(vex)
Mp((An(e-1) I) I- 11) s ar(s (Vik((ii))
45

---

Notice that: GGDD((a) & (UIV)(U)))]
and II (D-n((---1jGa((Xxk))
al|VF(Ünx)]] This implies:
Mplaaat- > M,((F((nk)) at Mp(Xnx-Xuu XIK, II)+ a "p
7
My(Aalt-n- I-II) & (.,((VF(Ukk)) S SaLM,(XAK XIK, (
Notice that: |[AAnto Σ aLN, suposigk lŪNKHi - ÜnKll and |[
-n)- I sLNh.spossss-- llUKk- ÜnKlI. Applying item in Lemma 21 we
conclude:
[AA Ca?LN
|| + Ca
CaLNN
(F(Unk)]]
MaK
(99)
7
7
Therefore, conclude:
Mp My I Ip Mp((kk)++ + G MM Mp(V(((kk)) + Spal, M Mp(Mnk)
7
Cpa'LL Mp(lix)+ Gpa"L
(V((((((()) + L2 Mp(Xix- -Xns;
Cpab Mp(Max)
+
Mp(Vix)+ C Mp((F((Uk) + G2a
Mp(Xix Kne,
CpaåIv (d log
VT
C Mp(X eK I I- II) + GzazL M, - I-
II) + CpasL M - (VF((((x)))
7
G2ad12 Mp(Xix NAK, IT) C (d + log K) ?
(100)
V/ In the first step, we have used the triangle incquality for MM along with the fact that N,, is independent of Ma k and XAx and the fact that its p-th moment is bounded by constant Cp. In the second step, have controlled the norm of V F with that of V F(Ú,k) using Lipschitzness. In the third step, we have invoked item 3 of Lemma 21 to bound the moments of Mr, In the fourth step, we have controlled the norm VA in terms of X and XIX- SAx. Similarly, have:
I- II) S I-
+ LCaaLLM + C, II),
(d (d +
log K)
(101)
Applying the estimates derived above Equation 97 along with the assumption that aL(s-t) < Cp-
an(s t) S c and a L(s t) I for some small enough constant co which depends only on we conclude:
sup Mp Nex, II) s 20(s - MX,, I- + sup M,(Xix - NAK, I- II) SShS
eShs
20(8 (1(8--1)M,
(d ldglog K)
+C/
(102)
7
46

---

Similarly considering Equation 98 we have:
sup Mn(XAK - NeK, I- II) = 20y(s - (X IT) + 2a(ss (VM
rshsa
+ log K
2aL(s t) sup iSKis
Mp(Xnx-
Xik, I1) -xe, Car
(103)
From Equations 1022 and (033 we conclude:
sup Mp(XnK - Xxx, IT) 80(s - -1),M IT) 8a(s-1) Mp((F((Uk))
IShis
d log K
+pp +
(104)
sup MM(Xnx - NIx, I-x, II) < 8yaass - (X + 8a(s M) (VF((x)
sShS
d doloo K
+ +C7VV
(105)
47

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contents of the paper match the claims made in the abstract and introduc- tion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in separate section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
48

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We explicitly reveal all the hyperparameters and open source models necessary to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
49

---

Answer:
[No]
Justification: We do not have institutional approval for code release. We provide detailed descriptions of the algorithms and hyype--arametter
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/guides/Codest Saapeeee/oooeSSSmiiiiiiooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
wttp:/liiggiie////eee htt.://guuddeeeeeSSuutute ssionpolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: It common in image generation literature to compute FID over 50k generated images, without reporting error bars since the fluctuations are usually negligible.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
50

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details regarding the GPU, CPU and the RAM are provided in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw..aaaoo.oooo/oooo/ooaaa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is purely technical and we do not foresee any societal impact due to this.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
51

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We use already open sourced models and datasets, widely used in the research community.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
52

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "xFcaDq3qzl", "reviewer": "Reviewer_F8sy", "summary": "Based on the Randomized Midpoint Method (RMM) proposed for simulating the Langevin Dynamics numerically, the authors proposed a variant called the Poisson Midpoint Method (PMM). Theoretical analysis is performed to bound the deviation between the continuous dynamics and the discretized dynamics. Moreover, when PMM is applied to simulate the Langevin Dynamics, the authors have shown that PMM can accelerate both the Overdamped Langevin Monte Carlo (OLMC) and the Underdamped Langevin Monte Carlo (ULMC) under additional assumptions like isoperimetry. Furthermore, numerical experiments on image generation with DDPM are conducted to illustrate the effectiveness of the proposed method.", "questions": "One major concern of the reviewer is that one assumption in the paper seems to be too strong. Specifically, Assumption 2 in the paper bounds the 14-th moment of the distance between the starting point and the global minima. To the best of the reviewer's knowledge, such assumption seems to be uncommon in sampling literature. Would it be possible for the authors to elaborate a bit more on why this assumption is essential here? It seems that this assumption essentially restricts the starting point to be a warm start, which makes the sampling task easier.", "limitations": "A few typos (the list is probably incomplete) in the current version of the manuscript are also listed below:\n\n1. From line 179-180, the two phrases \"to OLMC\" and \"to ULMC\" appeared twice. The two sentences probably need to revised.\n2. In line 206, the subtitle should be \"Sketch for Theorem 3\". Moreover, the following sentence should be \"This is similar to Theorem 2\".", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper is technically solid with a complete list of related work. The contributions are stated in a clear way. Also, a complete set of numerical experiments on diffusion models is included to illustrate the effectiveness of the proposed method.", "weaknesses": "The presentation of this paper can be potentially improved from a few aspects. Firstly, it seems a bit weird to use the phrase \"lower order terms\" (see for instance, line 167-168, 172-173, 205-206) in mathematical equations and derivations. One possible alternative is to replace it via the big O notation. Secondly, the authors might consider clarifying the differences between Langevin Dynamics and the backward SDE in diffusion model. One important thing that probably needs to stated clearly is that PMM is a method for simulating general time-dependent SDE (like the reversed SDE in diffusion models), but this paper only provides theoretical analysis for the case when PMM is applied to simulate Langevin Dynamics. Furthermore, it seems that the authors didn't discuss potential topics for future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the great review, which has helped us improve our work. Our responses to the questions and concerns raised are given below. \n\n### The Main Concern:\nThis is regarding the 14th moment assumption (i.e, Assumption 2) for the initialization. Below we discuss the validity of our assumption and demonstrate that such assumptions are common in the sampling literature (and implied by the assumptions made). \n\nSuppose $x^*$ is the global minimum of the potential function $F$ and note that $x^*$ is the mode of the target distribution. The assumption is that the initial iterate satisfies $\\mathbb{E}\\|x_0 - x^*\\|^{14} = O(d^7)$. It is reasonable to assume $\\|x^*\\| = O(\\sqrt{d})$ (for example this happens when each coordinate of $x^* $ is $O(1)$). In this case, a standard Gaussian initialization satisfies Assumption 2 since all its moments exist and the $2k$-th moment is of the order $d^{k}$.  Assumption 2 is used to bound $\\mathbb{E} [(F(x_0)- F(x^*))^7]$, and this can be replaced with any of the alternative assumptions as in the literature (see Examples 1 and 2 below).\n\nIt is common in the literature to consider well crafted Gaussian initializations with the mean being a local minimum/ global minimum of the potential function, along with an appropriate covariance, which then satisfy the $14$-th moment assumption. We discuss 4 such examples from recent works. We can provide more references with similar assumptions/elaborate the details mathematically if required. \n\n\n**Example 1:** For ULMC, see Appendix D and Lemma 27 of [1, COLT 2023 version]. This work considers $0$ to be a local minima of $F$ and the function value at $F(0)-F(x^*) = O(d)$. The initialization is a Gaussian centered at $0$ with an appropriate variance.  We note that [1] achieves the best known analysis for ULMC in the literature. This assumption can in fact replace our Assumption 2. (We are happy to elaborate more on this connection if required). Similar considerations are also used in [5, Appendix A].  \n\n**Example 2:** For OLMC, see discussion below Theorem 2  in [2, NeurIPS 2019 version], where the initialization is a Gaussian centered at a local minimum of $F$. \n\n**Example 3:** The original paper on the Randomized Midpoint Method considers starting the algorithm from exactly the global minimum of F (see [3, Theorem 3]). \n\n**Example 4:** Consider the case of image generation with pixel values in the range $[0,1]$ as considered in [4], which uses Langevin dynamics to generate these samples. Here it is reasonable to assume that it is reasonable to assume that $\\|x^{*}\\| = O(\\sqrt{d})$. The initialization is a uniform distribution which satisfies our assumption.\n\n**Regarding Warm-Start:**\n\nWe also respectfully disagree that this is a warm-start. In the sampling literature see [6,7,8], warm start means an almost sure upper bound on the radon nikodym derivative of the initial distribution with respect to the target. Our condition is much weaker than a warm start. A simple counter example would be if the initial distribution is a Gaussian $\\mathcal{N}(0,2\\mathbf{I}_d)$ and the target distribution $\\mathcal{N}(0,\\mathbf{I}_d)$. This satisfies our initialization condition whereas this does not satisfy the warm-start condition. \n\n[1] Improved discretization analysis for underdamped Langevin Monte Carlo, Zhang et al, COLT 2023\n\n[2] Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices, Vempala and Wibisono, NeurIPS 2019\n\n[3] The randomized midpoint method for log-concave sampling. Shen and Lee, NeurIPS 2019. \n\n[4] Generative modeling by estimating gradients of the data distribution., Song and Ermon , NeurIPS 2019\n\n[5] Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev,  Chewi, et al. Foundations of Computational Mathematics (2024)\n\n[6] Geometric random walks: a survey.  Santosh Vempala. Combinatorial and computational geometry  (2005)\n\n[7] Nonconvex sampling with the Metropolis-adjusted Langevin algorithm. Oren and Vishnoi COLT, 2019.\n\n[8] Random walks in a convex body and an improved volume algorithm. Lovász and Simonovits. Random structures & algorithms (1993)\n### Discussion of  Future work and  Langevin Dynamics vs Backwards SDE in DDPM: \n\nWe have discussed future work very briefly in lines 255-256, where we call for investigation of numerical approximations which work below 50 steps of DDPM. An interesting theoretical direction could be to derive bounds for time dependent SDE based sampling algorithms such as DDPM and with conditions such as the Poincare inequality or weak smoothness of the $F$ instead of smoothness (that is $\\nabla F$ is Holder continuous instead of Lipschitz). We will elaborate on this discussion and also discuss the differences between Langevin Dynamics and Backwards SDE in DDPM in the revision, along with the required references. Since we will have one more page for the revised version, we can add a more detailed discussion as pointed out by the reviewer in order to make the presentation of the material clearer. \n\n### Regarding “Lower Order Terms”:\n\nThanks for noting the confusion caused by using “Lower Order Terms” instead of the O() notation. We mainly wanted to convey the existence of other explicit terms (given in the appendix), with varied dependencies on the problem parameters. We can switch to the O() notation in the revision.\n\n### Conclusion:\nWe will address all the minor typos and other points raised by the reviewer in the revised version. We believe we have addressed the main concern of the reviewer (the 14-th moment assumption) and hope the reviewer can revise their rating.", "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": "OlOsogRGfj", "reviewer": "Reviewer_HMqT", "summary": "In this work, the authors draw inspiration from the randomized midpoint method for Langevin dynamics and design a new method called the poisson midpoint method. They establish guarantees for this method relative to the EM discretisation with thinning, and discuss theoretical and practical applications to sampling.", "questions": "1. What is $p_{\\tau}$ in Eq. (4)?\n2. As mentioned in Page 2, $A_\\alpha$, $G_\\alpha$, $\\Gamma_\\alpha$ are time independent, and so DDPM doesn't fall under the model in (1) right? How is DDPM relevant to the scheme (1) in that case?\n3. The scaling relations part of Section 2.1 could perhaps be placed later on? It's difficult to understand its purpose since it seems disconnected from the rest of the main draft.\n4. In Line 109, \"speed up\" is usually a computational term. Is this alluding to the \"speed up\" discussed later in Section 3 (in which case it might help to reference it here)?\n5. Since RLMC is also relatively complex (in comparison to a standard forward EM discretization), it would help to remark on how this is implemented, even if briefly. As written, it is essentially a combination of two discretizations: one forward, and one backward, and the backward discretization is the harder one to implement.\n6. The section of text between Lines 118--123 is very hard to follow. Since it is essential to the intuition, I would recommend that it be reworded suitably to be more formal and less colloquial. What is $\\mathrm{law}(Z + \\epsilon)$ and $\\mathrm{law}(Z + \\epsilon Z')$?\n7. I feel like the claim of \"replacing K steps with one step\" is not quite true, since eqs (7), (8) are each performing K steps each right?\n8. In eq (7), could the authors perhaps give some intuition about the summation on the RHS, and what the cheap interpolation is actually performing? A diagram would help greatly, but it is understandable if this is difficult to provide.\n9. In (8), what is the purpose of H_{t,i}? Why don't the $\\Gamma$, $A$, $G$ terms not have a \"i\" scaling like in the cheap interpolation?\n10. Why does $I_t$ have $N$ elements, and what is $N$ here? Initial conditions / conventions for the recursion in step 2 would be better off being stated apriori. What is $\\mathrm{Corr}$ in Step 4?\n11. Where is the computational complexity discussed in the paragraph on the top of page 5?\n12. How is there no dependence on the $\\{X_{t}\\}$ sequence in Eq. 10?\n13. Why is this strange dependence on 14th moment in Assumption 2 present?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "### Originality and Significance\n\nThe idea is quite interesting, and binning the unit interval to perform a randomized midpoint discretization is novel in my view. This clearly is not a straightforward innovation despite seeming like one. The theoretical statements also help characterize the benefits of this new strategy, which appear to be shown under weaker conditions than those required for sampling. Practically, this is also very appealing as the computational costs for the applications to generative modelling is lower than now-standard techniques when fixing the requirement (i.e., low FID).\n\n### Quality and Clarity\n\nThe idea is well-motivated, but I feel like the paper could be a lot more clearly presented, especially to be accessible to broader audiences. Please see the weaknesses / questions section below.", "weaknesses": "The writing of the paper can be definitely improved. It appears a bit rushed in multiple key areas, and several definitions and procedures are stated without much consideration towards the readability of those portions. Since there is a new method being proposed, it would help if intuition for this method is proposed, not just for the idea, but also the design of the method itself. Additionally, when certain complex steps (relative to other methods described in the paper like LMC) are mentioned (see the Algorithm and Computational complexity paragraph on Page 5), it would help to explain each (or a subset of them) in layman's terms to connect them to method (the two equations (7) and (8) on the previous page). The theoretical result in Section 3, specifically theorem 1 has inconsistent terminology ($B$ is the Brownian motion, $\\mathsf{S}(...)$ and $\\mathsf{PS}$ are lacking a $b$, $B$, $b$, $\\beta$, the role of $r$ and the randomness of the expectation is unclear. In the next theorems, the authors state \"Lower Order Terms\" instead of a small-O notation would have seemed more appropriate. The paragraph on quadratic speedup is also quite hastily presented in my opinion, because it is still not clear to me how the speedup is represented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments about the paper. We will improve the typos and the inconsistent notations in the revised manuscript. Since the revised version allows for an additional page, we hope to have enough space for a detailed discussion of every aspect pointed out by the reviewer. We will also replace the “Lower Order Terms” with the O() notation. \n\n\n### General Discussion of the Algorithm: \nBefore we delve into responses to specific questions, we add some discussion which can help answer questions 7,8,9 below. Consider\n\nA1: The dynamics S with step size $\\frac{\\alpha}{K}$ performed for $K$ steps.\n\nA2: The dynamics S with step size $\\alpha$ performed for $1$ step. \n\nO1: Our method PS with step size $\\alpha$, which approximates A1 with one step.\n\nA1 outperforms A2 since it has a finer time discretization and evaluates the drift function $b()$ a total of $K$ times. The drift evaluation is the most expensive part of the computation and is essentially the bottleneck for the computations. In case of DDPMs, it involves neural networks with $O(10^9)$ parameters. Like most of the sampling literature, we consider computational complexity in terms of number of evaluations of the drift function. We will clarify this in the revised version. \n\nO1 is obtained by adding a randomized correction term to A2, so that in expectation (with respect to the randomization in the correction) K steps of A1 approximately matches one step of A2. However, such a randomized correction cannot involve $K$ evaluations of the drift $b()$ since that is expensive. Thus, we evaluate the drift at a random set of midpoints given by $I_t$ and rescale it. The construction of the random midpoint set $I_t$ is via the random variables $H_{t,i}$ which are i.i.d. $\\mathsf{Ber}(1/K)$. That is, the i-th point for A1 is included in $I_t$ if and only if $H_{t,i} =1$. Note that $\\mathbb{E}|I_t| = 1$. Thus, we only need to do one additional drift function evaluation in expectation. \n\n### Responses to Specific Questions:\n\n\n1. Here $p_\\tau$ is the probability density function $X_{\\tau}$. This is explained in the linked references to the DDPM, but we will add a short discussion in the revised version. Thank you for pointing this out. \n2. We refer to lines 103-105 in the manuscript where we have discussed this. We chose $A_{\\alpha},B_{\\alpha},\\Gamma_{\\alpha}$ to be time independent for the sake of clarity, but give a similar algorithm applicable to DDPMs in Appendix A.1.\n3. We will relocate the scaling relations to a later section in the revised version. \n4. This indeed refers to the results in Section 3. We will clarify the computational aspects of this in the revised version. Also refer to the general discussion above. \n5. We will add a discussion of RLMC implementation in the appendix in the revised version. \n6. $\\mathsf{law}(X)$ for a random variable $X$ refers to its probability measure. This notation is defined in Section 1.3. We will make the said part clearer. The technical statement we wanted to make was that a Gaussian with mean 0 and variance $1+\\epsilon^2$ is closer to a standard Gaussian than a Gaussian with mean $\\epsilon$ and variance $1$. \n7. Eventhough (7) and (8) are mathematically $K$ steps (the equations being useful in the theoretical analysis), we refer to lines 141 to 153 where we algorithmically implement this much more efficiently. More precisely, we generate the random midpoint set $I_t$, and update the iterations only at the midpoints. Moreover, $I_t$ is such that $\\mathbb{E}|I_t|  = 1$. Since lines 141-153 give our main algorithm $\\mathsf{PS}$, we believe that this does approximate $K$ steps with just one step. \n8.  Please refer to the general discussion above.\n9.  Please refer to the general discussion above.\n10. Please refer to the general discussion above. The term $\\mathsf{Corr}$ is defined in step 4. The notation $:=$ means that the LHS is defined as RHS.\n11. This has been discussed in Proposition 1 in page 5. This shows that one step of $\\mathsf{PS}()$ requires two evaluations of the drift $b()$. As discussed above, the notion of computational complexity in the sampling literature is the number of evaluations of the drift function. We will make this clear in the revised version. \n12. We compare the distributions of $X$ and $\\tilde{X}$ via the KL divergence with the distribution of $X$ being the base measure. The expectation with respect to $\\tilde{X}$ is a consequence of the chain rule for KL divergence (Lemma 2 in the appendix):  Let $p$ and $q$ be the joint distributions over $\\mathbb{X}\\times \\mathbb{Y}$ and $p_x,q_x$ be the marginals over $\\mathbb{X}$ and $p_{y|x}, q_{y|x}$ be the respective conditional distributions over $\\mathbb{Y}$ given $x \\in \\mathbb{X}$. The chain rule states that:\n\n$$\\mathsf{KL}(p||q)  = \\mathsf{KL}(p_x||q_x) + \\mathbb{E}_{x \\sim p_x} \\mathsf{KL} (p(y|x)||q(y|x))$$\n\n\nThe second term is the expected KL divergence between conditionals where the conditioning variable is derived from $p_x$ rather than from $q_x$. In our case $p$ corresponds to $\\tilde{X}$ and $q$ corresponds to $X$. \n\n\n\n13. The 14th moment assumption is very mild since prior works consider Gaussian initializations which have all moments. We have explained this point in detail in the response to Reviewer F8sy. To understand why this shows up, we look at Equation (10) in Theorem 1. Here we take r = 7 and that requires us to bound $\\mathbb{E} \\beta_{tK+i}^{2r}$. By Lipschitzness assumption on $b()$, this reduces to bounding the 14th moment of $\\tilde{X}_{tK+i}$, which in turn can be controlled via the initialization.  \n\n\n### Conclusion\nThe reviewer agrees that the paper is very well motivated, and has strong theoretical and empirical results. We have answered the reviewer's technical concerns above and we will improve the presentation in the next version of our manuscript. We hope that the reviewer can reconsider their score in this light. We are happy to answer any further technical questions.", "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": "0c9XhXSCEK", "reviewer": "Reviewer_p2Nt", "summary": "The paper proposes a novel, multi-step discretization method for SDEs, with particular applications to the Langevin diffusions (overdamped and underdamped) and the denoising diffusion model SDE. The rates obtained are better than any other known guarantees in KL divergence.", "questions": "Although the notation in Section 2 is necessary to capture all the cases considered in this work, it is a bit cumbersome and makes the results difficult to parse. Perhaps for the proof sketch, only the OLMC case could be presented.\n\nThe final rates have some somewhat strange dependence on the key parameters; for instance, the dependence on dimension is $d^{5/12}$ for the underdamped PLMC. Do the authors have any intuition whether the rates obtained in their analysis are close to optimal for this discretization, and whether it would be possible to improve it with slight algorithmic modifications?\n\nIs the method extendible to the case where the tail growth of the potential is of order $|x|^\\alpha$, for $\\alpha < 2$? Or the case of weak smoothness?\n\nMinor:\n\n59: stochastic approximations LMC -> \"stochastic approximations of LMC\"\n\n70: denotes identity -> denotes the identity\n\n108 \"Motive\" -> \"motivate\"\n\n206: Theorem 1; I believe this is meant to refer to Theorem 3.\n\nMany equations/inline formulas are missing punctuation. For instance Eq. 6, Steps 3-5 (ll 145-149).", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The discretization proposed appears to be completely novel, and the analytic framework (using CLT type arguments) has not appeared before in this context.\n\nThe rates are state of the art in KL, clearly surpassing the previous best known discretizations in KL without any caveats.\n\nThe experimental evidence is thorough and appears to suggest that this discretization is indeed better than a naive one, for the diffusion model setting.", "weaknesses": "The algorithm as described in the paper is somewhat cumbersome to read. Perhaps some simpler exposition or visualization may be helpful.\n\nThe rates obtained are worse than those of the randomized midpoint discretizations (noting that these latter rates are only valid in Wasserstein distance).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the great feedback and multiple interesting possibilities for extension. We will improve the exposition and readability of the paper in the revision based on your comments. We address the questions raised by the reviewer below. \n\n\n**The main weakness** pointed out by the reviewer is that our rates are worse than prior works on randomized midpoint discretizations. We respectfully disagree with this claim. Our rates are better than the prior works. To elaborate: The literature on sampling compares $\\mathcal{W}_2 \\leq  \\epsilon$ to $\\mathsf{TV} \\leq \\epsilon$ to $\\mathsf{KL} \\leq \\epsilon^2$ (due to the information transportation inequality and the Pinsker's inequality). The number of steps required by our algorithm to achieve $\\mathsf{TV} \\leq \\epsilon$ is $O(\\frac{1}{\\sqrt{\\epsilon}})$ for ULMC (see table 1 in our manuscript) whereas prior works (see [1, Theorem 3]) require $O(1/\\epsilon^{2/3})$ to achieve $\\mathcal{W}_2 \\leq  \\epsilon$. Please let us know in case we misunderstood your comment.\n\n[1] Shen, Ruoqi, and Yin Tat Lee. \"The randomized midpoint method for log-concave sampling.\" Advances in Neural Information Processing Systems 32 (2019).\n\n### Questions:\n\n1. **Strange problem parameter dependencies and explanation:** We use a Wasserstein CLT based analysis (based on results from Zhai et al). Based on results of Theorem 1, this requires controlling the moments $\\mathbb{E}\\|\\nabla F(\\tilde{X}_t)\\|^{2k}$. Since we focus on convergence under very general conditions, we control these moments using smoothness of $F$ only as described in Section 4. This leads to a multitude of complex terms which finally leads to the said bound. It is not intuitively clear to us why factors such as $d^{5/12}$ make sense. However, we note that the dependence on $\\epsilon$ has a clear explanation given in Section 2. \n\nWe believe the results can be further improved with stronger assumptions such as strong log-concavity. Here numerous nice properties such as step by step contractive coupling can allow us to control the higher order terms precisely. We have not been able to design a better algorithm in this setting to overcome the said dependencies. We leave these further investigations for future work.\n\n2. **Extensions to other tail growth conditions and weakly smooth potentials:**\n\nBased on the comments by the reviewer, we surveyed the literature to check if this is possible. We believe these results are extendible to settings where the Poincare inequality holds. This corresponds to a tail decay of the form $e^{-\\|x\\|}$ (since the Poincare inequality implies sub-exponential concentration). \n\nSpecifically, we can combine the guarantees for LMC when the target satisfies PI (such as [2]) and obtain guarantees for our algorithm PLMC based on Theorem 2. Extension to other types of tails should be possible if results similar those in [2] are available in such settings for LMC. However, we do not know if sub-exponential (or stretched exponential type tails) are sufficient for fast convergence of LMC and additional isoperimetry type assumptions might be required.\n\nWe checked that we can extend the results of Theorems 2 and 3 to consider weakly smooth potentials, with some modifications to the proof. These modifications, along with off the shelf results for LMC given in works such as [3] can allow us to consider weakly smooth potentials as well. \n\n\n[2] Balasubramanian, Krishna, et al. \"Towards a theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo.\" Conference on Learning Theory. PMLR, 2022.\n\n[3] Chewi, Sinho, et al. \"Analysis of langevin monte carlo from poincare to log-sobolev.\" Foundations of Computational Mathematics (2024): 1-51.\n\n### Conclusion\nWe believe that we have addressed all the technical questions posed by the reviewer. We will fix the exposition in our next revision. Our work is novel theoretically, and we demonstrate the superior performance of our method with large scale image generation tasks. We hope the reviewer can reconsider their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for valuable feedback and have responded to the key technical concerns in our individual rebuttals. We are committed to enhancing the clarity and comprehensiveness of the paper by incorporating additional details, as suggested.

The reviewers unanimously recognize the novelty of the proposed algorithm, the rigor of its theoretical analysis, and the effectiveness demonstrated through empirical evaluation with diffusion models. Based on our past experience with NeurIPS, a paper exhibiting these strengths is generally regarded as a significant contribution to the field. We respectfully request the reviewers reconsider their scores in light of this.

Meta-review: This paper considers Poisson Midpoint Method, which is an alternative to Randomized Midpoint Method. Authors prove that the proposed scheme can achieve quadratic speed up of LMC. Authors demonstrate the performance via numerical studies.

This paper was reviewed by three reviewers with the following Scores/Confidence: 5/3, 7/3, 5/4. I think the paper is studying an interesting topic and the results are relevant to NeurIPS community. The following concerns were brought up by the reviewers:

- Theorem statements are quite convoluted and should be improved.
    
- Proof sketch can be more user friendly for the broader audience.
  
- Poor presentation should be improved in a few places. See reviewers' comments for details.

- The condition on initialization is certainly not restrictive but should be clarified.

Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the NeurIPS 2024 program.
Decision: Accept (poster)