Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
Authors: Lu Yu
Avetik Karagulyan
Arnak S. Dalalyan
Venue: ICLR 2024 poster (2024)
Keywords: Markov Chain Monte Carlo
Kinetic Langevin
Langevin algorithm
Midpoint method
Mixing rate
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: We revisit the problem of sampling from a target distribution that has a smooth strongly log-concave density everywhere in $\mathbb{R}^p$. In this context, if no additional density information is available, the randomized midpoint discretization for the kinetic Langevin diffusion is known to be the most scalable method in high dimensions with large condition numbers. Our main result is a nonasymptotic and easy to compute upper bound on the $W_2$-error of this method. To provide a more thorough explanation of our method for establishing the computable upper bound, we conduct an analysis of the midpoint discretization for the vanilla Langevin process. This analysis helps to clarify the underlying principles and provides valuable insights that we use to establish an improved upper bound for the kinetic Langevin process with the midpoint discretization. Furthermore, by applying these techniques we establish new guarantees for the kinetic Langevin process with Euler discretization, which have a better dependence on the condition number than existing upper bounds

Published as a conference paper at ICLR 2024
LANGEVIN MONTE CARLO
FOR STRONGLY RANDOMIZED
LOG-CONCAVE DISTRIBUTIONS: MID-POINT REVISITED
Lu Yu CREST, ENSAE, IP Paris
Avetik Karagulyan KAUST
fr
kvetik.kkragulyaaaae edu. sa
Arnak Dalalyan CREST, ENSAE, IP Paris arnak. dala yaalaalyaneeese... fr
ABSTRACT
We revisit the problem of sampling from a target distribution that has smooth strongly log-concave density everywhere in R". In this context, if no additional density information is available, the randomized midpoint discretization for the kinetic Langevin diffusion is known to be the most scalable method in high dimensions with large condition numbers. Our main result a nonasymptotic and easy to compute upper bound on the W2-error of this method. To provide more thorough explanation of our method for establishing the computable upper bound, we conduct an analysis of the midpoint discretization for the vanilla Langevin process. This analysis helps to clarify the underlying principles and provides valuable insights that we use to establish an improved upper bound for the kinetic Langevin process with the midpoint discretization. Furthermore, by applying these techniques we establish new guarantees for the kinetic Langevin process with Euler discretization, which have better dependence on the condition number than existing upper bounds.
INTRODUCTION
The task of sampling from target distributions with smooth, strongly log-concave densities has been a long-standing challenge in various fields such as statistics, machine learning, and computational physics (Andrieu al., 2003; Krauth, 2006; Andrieu et al., 2010). Over the years, researchers have developed several algorithms to tackle this problem, and one prominent approach are the Langevin algorithms (Rogers & Williams, 2000; Oksendal, 2013; Robert et al., 1999). Langevin algorithms leverage the Langevin equation to design efficient and effective sampling algorithms. These methods generate Markov chain by iteratively updating the position of a particle based on the Langevin equation. By simulating the particle's 's motion over time, these algorithms explore the target distribution and eventually converge samples that approximate the desired distribution (Robert et al., 1999).
The canonical sampling algorithm, Langevin Monte Carlo (LMC) (Roberts Tweedie, 1996; Dalalyan, 2017; Durmus & Moulines, 2017; Erdogdu & Hosseinzadeh, 2021; Mousavi-Hossein al., 2023; Raginsky et al., 2017; Erdogdu et al., 2018; Mou et al., 2022: Erdogdu et al., 2022), is Markov chain Monte Carlo (MCMC) method that simulates the dynamics of fictitious particle moving through a potential energy landscape defined by the target distribution. Formally, Euler-Maruyama discretization of an SDE known as the Langevin diffusion. The underlying idea can be traced back to the early 20th century when Paul Langevin introduced a stochastic differential equation (SDE) describe the motion of particle in fluid (Langevin, 1908). This SDE, combines deterministic and random components to model the particle's 's behavior under the influence of both a deterministic force and random noise.
the

---

Published as a conference paper at ICLR 2024
One popular variant of the Langevin Monte Carlo is based on discretizing the kinetic Langevin diffusion, which introduces a friction term to control the the sampling process (Einstein, 1905; Von Smoluchowski, 1906). According to Nelson (1967),
trade-off during
the Langgvvnn diffusion is the rescaled limit of the kinetic Langevin diffusion. Its ergodicity and mixing-time properties studied in Eberle al. (2019); Dalalyan & Riou-Durand (2020). Euler-Maruyama time discretization of this SDE, called kinetic Langevin Monte Carlo (KLMC), is prevalent in the sampling literature (Cheng et al., 2018b; Dalalyan & Riou-Durand, 2020; Shen & Lee, 2019; Ma et al., 2021; Zhang et al., 2023).
The randomized midpoint discretization method, as an alternative the Maler-Maruyama scheme for KLMC, is proposed by Shen & Lee (2019). They demonstrate the superior performance of this method in terms of both tolerance and condition number dependency. More recently, He et al. (2020) analyze probabilistic properties of the randomized midpoint discretization method for the (kinetic) Langevin diffusion. In this work, we undertake a comprehensive and thorough analysis of the randomized midpoint discretization scheme for the kinetic Langevin diffusion under strongly log-concavity. To achieve this, we introduce a novel proof technique relying on summation by part, which helps establish improved non-asymptotic and computable upper bounds the discretization error for this method. Our contributions can be summarized as follows.
To lay the groundwork for our analysis, we initially delve into the midpoint discretization technique applied to the vanilla Langevin process. In this context, we introduce our novel proof technique, which plays pivotal role in our study. Notably, in Theorem 1, we provide the convergence guarantees for RLMC in W2-distance with explicit constants and a transparent reliance on the initialization. These guarantees are competitive with the best available results for LMC, and could be leveraged to derive an improved upper bound specifically tailored for RKLMC.
We further extend these techniques to RKLMC, and provide the corresponding convergence guarantees in W2-distance in Theorem 2. Compared to the previous works, our bound a) contains small constants and the explicit dependence on the initialization, b) does not require the initialization to be at the minimizer of the potential, c) and is free from the linear dependence on the sample size, which serves as a crucial step towards the method applied to non-convex potentials.
Employing the same techniques, we finally examine the convergence behavior of the KLMC algorithm with the Euler- Marlyy-a discretization. In Theorem 3, we provide upper bound on the accuracy of this scheme in Wy-distance with improved dependence on the condition number.
We offer systematic and unified treatment of the variants of LMC, which empowers us to derive enhanced upper bounds for the W2-error associated with RKLMC, RLMC, and KLMC algorithms. Furthermore, our techniques facilitate the determination of explicit constants and the dependence on initialization, providing us with a clearer basis for choosing the step size and comparing the convergence rates across these methods.
Notation. Denote the p-dimensional Euclidean space by RP. The letter 0 denotes the deterministic vector and its calligraphic counterpart denotes the random vector. We use Ip and O, to denote, respectively, the p X p identity and zero matrices. Define the relations A & B and B >> A for two symmetric p X p matrices A and B to mean that B A is positive semi-dcfinite. The gradient and the Hessian of function f : RRP IR are denoted by V f and V2 respectively. Given any pair of measures μ and v defined on (IRP, ((TP)) the Wasserstein-22 distance between ja and v is defined as
W2(u ( inf / (ET(M.)) JRP where the infimum is taken over all joint distributions & that have j and v/ as marginals.
1 0' ())))))))
1/2
2 UNDERSTANDING THE RANDOMIZED MIDPOINT DISCRETIZATION: THE VANILLA LANGEVIN DIFFUSION
The goal is to sample random vector in RP according to a given distribution π of the form (0) x
0 E RR,
2

---

Published as a conference paper at ICLR 2024
with function f Rº - E. referred as the potential. Throughout the paper, assume that the potential function f is M-smooth and m-strongly convex for some constants 0 < m & M < co.
Assumption The function f RP IR is twice differentiable, and Hessian matrix V satisfies
mIp x 22 f(0) x MIp.
40 E..
Let 9g be random vector drawn from distribution RP and let W : 0) be p-dimensional Brownian motion independent of dp. Using the potential f. the random variable do and the process W, one can define the stochastic differential equation
= =- dt + v2dW,
t 0,
L do.
(1)
This equation has a unique strong solution, which is a continuous-time Markov process, termed Langevin diffusion. Under some further assumptions on such strong convexity dissipativity, the Langevin diffusion is ergodic, geometrically mixing and has as its unique invariant distribution (Bhattacharya. 1978). Furthermore, the mixing properties of this process can be quantified. For instance, if satisfies the Poincaré inequality with constant Op, then (see e.g. Chewi et al. (2020)) the distribution un of L satisfies
(2 R)) & 2Cpx/C//CCxx"vll
At 3 0.
These results suggest that we can sample from the distribution ı by using a suitable discretization of the Langevin diffusion. The Langevin Monte Carlo (LMC) method is based on this idea, combining the aforementioned considerations with the Euler discretization. Specifically, for small values of h 0 and A, W, With W,, the following approximation holds
L = L. (I(L + V2 W, s D -VS(L V A,W.
By repeatedly applying this approximation with a small step-size h, we can construct a Markov chain (OLMC) N) that converges the target distribution as h goes to zero. More precisely, OLMC LLD for & N, given by
x+1 = LLMC hV ((OLMM)))))) + v2 (W (K+1)A WAn).
This method is computationally efficient and has been widely used in statistics and machine learning for sampling from -inensiinnsii distributions (Gal & Ghahramani, 2016; Izmailov al., 2020; 2021). To assess the discretization error, consider the case where L is drawn from the invariant distribution æ and note that
h V (f(L ds (VLMC)
LLD LLMC LLD (b+1)A
OLMC
LLD
@LMC
(V ()(O)M))) Ck.
(2)
where ÇR = St (Vf - (D) ds is a zero-mean random "noise" vector. Previous
work on LMC demonstrated that the squared L2 norm of && is order M2h3p, whereas the term LLD LLMC h (V)(LL)) v M(OLMC) satisfies the contraction inequality
LLC
(V ([(OLMM)) <1 - mh m
9LMC -
(3)
we denote by T3 the correlation between Ç3 and L.D .LMMC and by Err, the error L we infer from equation and equation 3 that
LLMC
Em & - (1-mhh)mrr C.MTR hp CMP
some universal constant C. we were able to check that mn is small enough so that the second term of the hight-hand side can be neglected, we would get Em (1 ? C, 2 which would eventually lead Em?.1
mh)2kEm; (22
(p/m). This would amount to
1rkl <
Em & (1 (1)mh)* Em, CsMhyp/m.
3

---

Published as a conference paper at ICLR 2024
Unfortunately, without any additional conditions on f. the correlation r4 cannot be shown to be small, and one can only deduce from equation 3 that E & (1- mh)Err, + CMhyph, which eventually yields
Fx *
Em & (1-mhh) Em + Ca(M/m))pl.
(5)
This inequality is established under the standard assumption Mh < 1, which implies that the last term in equation 4 is significantly smaller than equation 5. To get such error deflation, need the correlations тæ to be small. While this is not guaranteed for the Euler discretization, we will see that the randomized midpoint method allows to achieve such a reduction.
Let U be random variable uniformly distributed in [0, 1] and independent of the Brownian motion W. The randomized midpoint method exploits the approximation
L = LD I (f(LL)) ds + V2 W, ~ LP - AVS(L + V2 W.
The noise counterpart of Ça in this case is c - fo V ds - Vf LD kh+uh) It is clearly centered and uncorrelated with all the random vectors independent of U such L OLMC and the gradient of f evaluated at these points.
The explanation above provides the intuition of the randomized midpoint method, and hint to why is preferable to the Euler discretization, but it cannot be taken as a formal definition of the method. The formal definition of the randomized midpoint method for the Langevin Monte Carlo (RLMC) is defined as follows: at each iteration & = 1,2,....
1. we randomly, and independently of all the variables generated during the previous steps, generate pair of random vectors (S): {2² and random variable U3 such that
Uk is uniformly distributed [0, 1] and independent of (E%-5))
(Ei, <k) are independent (0, I.))
2. set & VUR E vI Uy and define the (k 1)th iterate @RLMC by
ØRLM RRLMC k+U BRLMC hU, V ( + 2hUE E/
(6)
RRMMC GRLMC KV f @
RLMC) K+U + /2h Ek-
With small step-size h and large number of iterations the distribution of @RLMC can closely approximate the target distribution и. In smooth and strongly convex setting, it is even possible to obtain a reliable estimate of the sampling error, demonstrated in the following theorem (the the proof included in the supplementary material).
If the step-size h is small and the number of iterations is large. the distribution of @RLMC is close to the target и. Interestingly, the smooth and strongly convex setting is possible to get good evaluation of the error of sampling as shown in the next theorem (the proof is deferred to the supplementary material).
Theorem Assume the function f RR + satisfies Assumption Let be such that M + /K (Mh)3/2 & 1/4 with M/m. Then, every n 2 the distribution U RLMC of @RLMC satisfies
W2(1 RLMC < 1.11e mL..ee-mh//W. T) + (2AVVMM + 1.77) Mh p.m.
(8)
Prior to discussing the relation of the above error estimate to those available in the literature, let us state consequence of it.
Corollary 1. Let E (0,1) be small number. If we choose h > 0 and n E N so that
3k
3.8r4/3
[oog(20/)) + log (m WW x)))
Mh 1.5 + (33
and n n
g2/3
then' we have (2 RLMC T) & &
This follows from the fact that (6x/s) + 4.2 222 2n/(Mh) 2/mh.
4

---

condition). The full details are deferred the Published as a conference paper at ICLR 2024
Our results can be compared to the best available results for the Langevin Monte Carlo (LMC) under Assumption (Durmus et al., 2019, Eq. 22). We recall that LMC is defined by recursive relation of the same form equation 7. with the only difference that ff(0++)) is replaced by V f(0x). The tightest known bound for LMC is given by
LMC TT) < (1 mh) - - W2(v, T) + /2Mhp/m, (2
with Mh 1. By choosing 2M (19/20) and
2.22 (x22
{ 12g(20/=) + log ( (7
we can ensure that (2 TT) & EV p/m. Therefore, the complexity bound of Corollary derived from our result for RLMC is better than the best-known complexity bound for LMC in the regime of s of smaller order than e-4
To the best of our knowledge, the first results on the error analysis of RLMC have been obtained in (He et al., 2020). They derived an upper bound on the discretization error (the second term on the right-hand side of equation 8) under the assumption that the initial point of the algorithm is the minimizer of the potential function f. Their bound takes the form C(VRM ((V/Mh++))me MMMM-ttMMhh/// /p/m/x mmhh, where is a universal but unspecified constant. Compared to our bound, the one obtained in He et al. (2020) has an additional factor vmnh. While this factor may not be very harmful in the case of geometric ergodieity where the number of iterations is chosen such that nmh goes infinity at the logarithmic rate log(1/2) removing it can be an important step toward extending these results to potentials that are not strongly convex.
While the proof of this theorem is deferred to the supplementary material, we can outline the main argument that allowed us to remove the factor / vnmh from the error bound. To convey the main idea, let us consider three positive sequences an bn. On satisfying, for every n E N.
On+1 < (1 a)an, + bn.
Ca+1 < Cn - bn + +
(10)
with some a E (0, 1) and C>> for proving the convergence of convex optimization algorithms, one can infer from equation 10 that
>>
Using the standard telescoping sums argument, frequently employed
bn
E co- cnt1 + nC & co + nc.
(11)
km
On the other hand, it follows from equation 9 that
am+11 & (1 a) mttoo= + > R
k=0 (1 a>)=>bbb.
(12)
Upper bounding (1 = by one, and using equation 11, arrive
an+1 < (1-a) (1=a) on Co + nC.
(13)
This type of argument, used in previous papers on RKLMC (Shen & Lee, 2019), is sub-optimal and leads to the extra factor Vnmh.. A tighter bound can be obtained by replacing the telescoping sum argument by the summation by parts. More precisely, one can check that equation 10 and equation 12 yield
k=0 On+1 & (1 - (1-a)att) a)attaa ao + Σn (1 --) - -k+1) + C E
(1 a))
k=n
(1-a) ao + +1 (1- + En (1-a)a
(14)
The upper bound provided by equation 14 has two advantages as compared to equation 13: the term nC is replaced by C/a, which is generally smaller, and the dependence on the initial value (1 a²" co instead of co- This comes also with a challenge consisting in upper bounding the sum present in the right-hand side of equation 14, which we managed to overcome using the strong convexity (or, more precisely, the Dolyak-Lojasiesn supplementary material.
"The condition o(E is obtained by simple algehra from the condition ///3/62/3 o(H//²)).
5

---

Published as a conference paper at ICLR 2024
3 RANDOMIZED MIDPOINT METHOD FOR THE KINETIC LANGEVIN DIFFUSION
The randomized midpoint method, introduced and studied in Shen & Lee (2019), aims at providing discretization of the kinetic Langevin process that reduces the bias of sampling compared to more conventional discretizations. Recall that the kinetic Langevin process L KKLD is a solution to a second-order stochastic differential equation that can be informally written as
IILDD + LKKDD V + W
(15)
with initial conditions LO KLD do and L vo- In equation 15, 7 W standard p-dimensional Brownian motion and dots are used to designate derivatives with respect to time & e 0. This can be formalized using Itô's calculus and introducing the velocity field VKLD so that the joint process (LKLD, VKLD) satisfies
dL V.KLD dt; LdV, -VVKLD (V((KLD)) dt v2dW..
(16)
Similar to the vanilla Langevin diffusion equation 1, the kinetic Langevin diffusion (IKLD, V/KL) is Markov process that exhibits ergodic properties when the potential f is strongly convex (see (Eberle et al., 2019) and references therein). The invariant density of this process is given by
p- (0,v) exp(-s(0) - 111])
for all 0, u E R..
Note that the marginal of p. corresponds coincides with the target density x. However, unlike the vanilla Langevin diffusion, the kinetic Langevin is not reversible. It is interesting to note that the distribution of the process L KLD approaches that of the vanilla Langevin process as 7 approaches infinity (see e.g. (Nelson, 1967)). Therefore, LLD and LLD are often referred to as the overdamped and underdamped Langevin processes, respectively (where increasing the friction parameter y is characterized as damping).
The kinetic Langevin diffusion L KLD is particularly attractive for sampling because its distribution rKLD converges to the invariant distribution exponentially fast. This is especially true for strongly convex potentials, as proven in (Dalalyan & Riou-Durane 2020, Prop. 1), where is shown that the following inequality holds:
(c
VKLD
c
Vo Lo
v 9
I
W2
KLD
C
8
& e
W2
C
C
=
p IIp
for every > 0, provided that y e m + M.
To discretize this continuous-time process and make it applicable to the sampling problem, Shen & Lee (2019) proposed the following procedure: at each iteration k = 1,2....,
1. randomly, and independently of all the variables generated the previous steps, generate random vectors (Ei, -..'&"))) and random variable UR such that
Uk is uniformly distributed in [0, 1]. conditionally to Up u, S% e- B1 5->h ye >h Gh), where B is p-dimensional Brownian motion and G; = = hh dB..
S/i Skick)) has the same joint distribution as (B,,
2. set (x)) (1 - -- 1/x and define the (k 1)th iterate of @RKLMC by
9 k+U 0z UUhb(? - Uh(1 ((Uhh)) + 2
- 2 k+1 0z (o
22hg
Uh+1 = é 7 Uk - The - + 2 c.
Although the sequence RKRKLM @RKLMC) approximates KLD LKL)). it is not immediately apparent. The supplementary material clarifies this point. We state now the main result of this paper, providing a simple upper bound for the error of the RKLMC algorithm.
&h
Forr the sake of the self-comtainedness of this paper, reproduce the proof of this inequality in Proposition I deferred to the Appendix.

---

Published as a conference paper at ICLR 2024
Theorem 2. Assume the function f : R R satisfies Assumption 1. Choose and h so that y > 5M and yh & 0.1k 1/6, where & = M/m. Assume that úg is independent of vo and that 20 ~ (0, rIp). Then, for any n 2 1, the distribution in FRKMC of @FKLMMC satisfies
W2(U RKLMC T) < 1..6" T) + + + - -(00))/mm
+0.2(?h)) V kppmm 10(rh)3/2 vp/m,
where @ = exp(-mhh) and 0, arg mingerr f(0).
This result has several strengths and limitations, which discussed below, after the corollary providing the number required iterations to attain a predetermined level of accuracy.
Corollary 2. Let ε E (0, 1) be a small constant. ! 5.M, do 02 and we choose and E N so that
2//3
7h + x+0,(E2xx\//6
-e/k////-300 and 3 KE (25 + 3((2x))//6) log(20/E),
then we have (1
RKLMC .7)
p/m.
The corollary presented above gives the best-known convergence rate for the number of gradient evaluations required to achieve a prescribed error level in the case of gradient Lipschitz potential, without any additional assumptions on its structure or smoothness. This rate, KE 2/3 (1 (E²x) was first discovered by Shen & Lee (2019) (see also (He et al., 2020)). By employing our proposed proof technique described in Section the result in Theorem 2 gets rid of the factor nunh from the discretization error, which was present in the previous upper bounds of the sampling error Furthermore, our bound contains only small and explicit constants. Finally, our result does not require the RKLMC algorithm to be initialized at the minimizer of the potential, which is important for extending the method to non-convex potentials.
On the downside, the condition > 5MM is stronger than the corresponding conditions used in prior work on the KLMC (without randomization). Indeed, these prior results generally require y > 2.M. Having proof of Theorem that reduces the factor 5 in y > 5.M would lead to significant savings in running time.
IMPROVED ERROR BOUND FOR THE KINETIC LANGEVIN WITH EULER DISCRETIZATION
The proof techniques presented in the previous section can be used to derive an upper bound on the error of the kinetic Langevin Monte Carlo (KLMC) algorithm. KLMC is discretized version of KLD equation 16, where the term V fL,,) is replaced by ff(La)) on each interval [kh, (k + 1)h). The resulting error bound, given in the following theorem, exhibits a better dependence on k than previously established bounds.
Theorem 3. Let f TRP + IR. satisfy mI, & (2)(0) < MI, for every f E R Choose and h so that 7 5M and / 0.1, where M/m. Assume that &n is independent of vo and that Vo (0, 7I,). Then, for any n the distribution v KLMC of OKLMC satisfies
(LMC x) & W2 m) / where @ = exp(-mh), and 0, arg minger: f(0).
(0.))/ 0.94h 0.97h/kp/mm
Bounds on the error of KLMC under convexity assumption, other related conditions, can be found in recent papers (Cheng et al., 2018b; Dalalyan & Riou-Durand, 2020; Monmarché, 2021; Monmarché, 2023). Our result has the advantage of providing an upper bound with the best known dependence on the condition number and having relatively small numerical constants, as shown in the next corollary.
Corollary 3. Let E (0, 0.1). Y 5M. Or 0. and choose h 0 and n E N that
7h SK -1/2 and 5x 3/2 log(20/s)
then have (LLUKMM -)) & e/p/m.

---

Published as a conference paper at ICLR 2024
It is worth noting that our error bounds, along with the other bounds mentioned previously under strong convexity, rely on the synchronous coupling between the KLMC and the KLD. However, in the case of the vanilla Langevin, it has been shown in Durmus et al. (2019) that the dependence of the error bound on к can be improved by considering other couplings (in their case, the coupling is hidden in the analytical arguments). We conjecture that the dependence Monte Carlo algorithm can also be improved through non-synchronous coupling. Specifically, we conjecture that the number of iterations required to achieve a W2-error bounded by & & //pm should scale as k/ce rather than 3/22
in the kinetic Langevin
///////. /s, obtained in previous work and in Theorem 3.
5 NUMERICAL EXPERIMENTS
In this section, we compare the performance of LMC, KLMC, RLMC, and RKLMC algorithms. We apply the four algorithms the posterior density of penalized logistic regression, defined by with the potential function
т (1) x
Ddata
S(0) = 2
||01|
log(1 + exp(-y;ar) 0)),
Adata
1=1
where À > 0 denotes the tuning parameter. The data (ai, Vi 1 composed of binary labels yi E ind
{-1, } and features 2; E R" generated from Ta, ~ No0 N0, 5), and (0, 10), corresponding the plots from left right, respectively. In our experiments, we have chosen X 1/ 1/100, p and dadaaa = 100.
Figure/ shows the W2-distance measured along the first dimension between the empirical distributions of the samples from the four algorithms and the target distribution", with different choices of h. These numerical results confirm our theoretical results. Indeed, we see that the randomized midpoint versions of LMC and KLMC perform better than their vanilla counterparts when the condition number not too large (the leftmost plot). This order changes when becomes large, in the rightmost plot, where KLMC outperforms the other algorithms.
(log
115
LMC KLMC
-0.00
.25
220
RKLMC
0.66
-55
5.0e-05
7.5e-06
1.0e:0
2:5e006
5:0e-06
7.5e06
1.0005
5.0e-66
1.0e:55
size
stop
slep
Figure 1: Error of (L.RI.KI.RKII,MCC with different choice of step size.
6 DISCUSSION OF ASSUMPTIONS AND LIMITATIONS
The results presented in this paper provide easily computable guarantees for performing sampling with assured accuracy. These guarantees are conservative, implying that the actual sampling error may be smaller than even if the upper bounds stated in our theorems are larger than e. However, these bounds represent the most reliable technique available in the existing literature. The importance of having such guarantees is further emphasized by the lack of reliable practical measures to assess the quality of sampling methods. To better understand the computational complexity implied by our bounds for various Monte Carlo algorithms, present in Table I the number of gradient evaluations required to achieve the accuracy of e m/m for different combinations of (s, n))
Strong convexity The assumption of strong convexity is often seen as too restrictive. In our theorems, strong convexity is used for three purposes: (a) to ensure the contraction of the continuous-tin time
'erre execute the LMC algorithm with small step size over extended duration to approximate the truc distribution.
8

---

Published as a conference paper at ICLR 2024
Table The number iterations that are sufficient for the algorithms (L.RL.KL.KL)MMC achieve an error
in W2 distance bounded by s //p/m, provided that they are initialized the minimum of the potential f-
(c,a)
(0.1², 10²)
109)
(0.1², 109)
(0.1², 10")
(0.1², 10")
(0.1². 1
LMC
1.2 x 10
1.2 10
1.2 10
1.2 x 1010
1.2 x 10
1.2 1014
3.6 10a
10
10
2.0 10
9.3 x 1013
4.3 10
KLMC
8.4 10a
8.4 x 10
6,4 10
6.4 x 1012
8.4 1018
8.4 10te
RKLMC
1.0 104
10
10
1.3 x 1020
2.2 x 1012
4.2 1024
(5.8)
(0.19.
100)
(0.19. 109)
(0.19,
(0.19, 10")
(0.19. 1011)
LMC
2.2 10"
10
10
2.2 1014
2.2 1016
2.2 10
RLMC
x.8 x 10
6.8 x 107
2.0 1610
6.4 x 10
3.8 x 1616
1.7 x 1018
KLMC
1.6 10
x 10
1.x 10t2
1.6 1026
1.6 10l8
1.8 x 1021
RKLMC
4.5 x 10
4.5 107
4.5 x 10
4.5 x 10
4.7 1013
8.7 1015
(c,m)
(0.19, 103)
(0.19, 102)
(0.1", 109)
(0.19.
(0.19,
(0.1², 10"!)
LMC
3.2 16
3.2 10
3.2 10'6
3.2 x 10th
3.2 x 10
x 1022
107
10
1011
3.0 100
1.2 10
5.5 10
KLMC
2.3 x 10
2.3 10
2.3 x 1614
2.3 x 10
2.3 x 1020
2.3 1022
RKLMC
107
x.6 10
10t1
1.5
1.6. 1046
1.5 10
Langevin dynamics. (b) to relate the potential's values to its gradient through the Polyak-LLojssewwig condition [()](? > (m( - f(e)) (Polyak, 1963; Lojasiewicz. 1963), and (c) to provide the following simple upper bound on the 2- Wasserstein distance W2(6e.. T) & vp/mm (Durmus & Moulines, 2019, Prop. 1). The last two inequalities can be satisfied for many non-convex functions, but the same is not true for the contraction of the Langevin dynamics.
Alternatively, we can assume that the function is only strongly convex outside ball of radius R > whereas within the ball it is smooth but otherwise arbitrary. This approach requires an additional factor of order e M Rt in the number of iterations necessary to achieve a specified error level (Cheng et al., 201 8a; Ma al., 2019). We can also assume that the Markov semi-group has spectral gap and use this gap in the risk bounds. However, this approach goes against the spirit of our paper, which aims to provide guarantees that are easy to interpret and verify.
Another important point to note is that the results obtained under the assumption of strong convexity can be used as ready-made results in other frameworks as well. For instance, this is applicable to weakly convex potentials potentials supported on compact set (Dalalyan et al., 2022; Dwivedi et al., 2018; Brosse et al., 2017).
Smoothness Smoothness of f is critical assumption for the results obtained in this paper. However, in statistical applications, this assumption may not hold, such as when using a Laplace prior. In such cases, various approaches have been proposed, mainly involving gradient approximation techniques, as explored in the literature (Durmus et al., 2018; Chatterji et al., 2020). Our results open the door for similar extensions of the randomized midpoint method for such scenarios.
It should also be stressed that if the potential is more than twice differentiable with a bounded tensor of higher-order derivatives, then it is possible to design Monte Carlo algorithms that perform better than the LMC and the KLMC (Dalalyan & Karagulyan, 2019; Dalalyan & Riou-Durand, 2020; Ma al., 2021). The same is true if the function has some specific structure (Mou et al.. 2021).
Functional inequalities Functional inequalities such as the Poincaré and the log-Sobolev inequalities provide convenient framework for analyzing sampling methods derived from continuous-time Markov processes. This line of research was developed in a series of papers (Chewi et al., 2020; Vempala & Wibisono, 2019; Chewi et al., 2022). Extending the techniques of this paper from strong log-concavity to the framework of distributions satisfying one of the aforementioned functional inequalities is a non-trivial task.
Other distances The W distance, utilized in this paper, serves as a natural metric for measuring the error in sampling due to its connection with optimal transport. However, it is worth noting that recent literature on gradient-based sampling has explored other metrics such as total variation distance, KL divergence, and x2 divergence (Ma et al., 2021; Vempala & Wibisono, 2019; Durmus et al., 2019; Chewi et al., 2020; Balasubramanian al., 2022; Zhang et al., 2023). An interesting direction for future research involves establishing error guarantees for the randomized midpoint method with respect to these alternative distances.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was partially supported by the grant Investissements d' Avenir (ANI:11-DDEX0005//abee Ecode//ANR-I--AAX---00 and the center Hi! PARIS.
REFERENCES
Christophe Andrieu, Nando De Freitas, Araad Doucet, and Michael I Jordan, An introduction to meme for machine learning. Machine learning, 50:5 43, 2003.
Christophe Andrieu, Arnaud Doucet, and Roman Holenstein. Particle markov chain monte carlo methods. R. Stat. Soc. B, 72())269-342, 2010.
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards theory of non-log-concave sampling: first-order stationarity guarantees for Langevin monte Carlo. In Conference on Learning Theory, pp. 2896-2923. PMLR, 2022.
R. N. Bhattacharya. Criteria for recurrence and existence of invariant measures for multidimensional diffusions. Ann. Probab., 6(4):541-553, 08 1978.
N. Brosse, A. Durmus, É. Moulines, and M. Pereyra. Sampling from log-concave distribution with compact support with proximal Langevin Monte Carlo. In COLT 2017, 2017.
Niladri Chatterji, Jelena Diakonikolas, Michael Jordan, and Peter Bartlett. Langevin monte carlo without smoothness. In AISTATS 2020, 2020.
Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi- Sharp convergence rates for Langevin dynamics in the nonconvex setting. CoRR, abs/1 0tbs/1805.00 805.01648. 2018a.
Abbasi-Yadkort Yadkori, Peter L. Bartlett, and Michael Jordan.
Xiang Cheng, Niladri Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped Langevin MCMC: A non-asymptotic analysis. In COLT 2018, 2018b.
Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin J. Stromme. Exponential ergodicity of mirror-Langevin diffusions. NeurlPS 2020, 2020.
Sinho Chewi, Murat Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincare Log-Soholev. In COLT 2022, 2022.
Amak Dalalyan. Theoretical guarantees for approximate sampling from a smooth and log-ccne density. J. R. Stat. Soc. B, 79:651 676, 2017.
Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 2019.
Arnak S Dalalyan and Lionel Riou-Durand, On sampling from log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956-1988. 2020.
Arnak S Dalalyan, Avetik Karagulyan, and Lionel Riou-Durand, Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets. J. Mach. Learn. Res., 23(235):1338 2022.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. Ann. Appl. Probab., 155))1551-1587, 06 2017. doi: (0.1114/6-AAP1238.. URL http::/ //tp://xxx./ doi. /rg//00/... 11114//111AA12.....
Alain Durmus and Éric Moulines. High dimeediimeiionall Bayesian inference via the unadjusted Langevin 2019. doi: 131150/1--BJJ100 URL https:
algorithm. Bernoulli, 25(4A):2854-288) / wwwg/rrro..... /0/110..3 0..1..150000 10/10011500 8-BEJ1017
Alain Durmus, Éric Moulines, and Marcelo Pereyra. Efficient Bayesian Computation by Proximal Markov Chain Monte Carlo: When Langevin Meets Moreau. SIAM J. Imaging Sci., 11(1), 2018.
URL https:/ / /hal 1.
10

---

Published as a conference paper at ICLR 2024
Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. J. Mach. Learn. Res., 20:73-1, 2019.
Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis-Hasting algorithms are fast! COLT 2018, 2018.
Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Couplings and quantitative contraction rates for Langevin dynamics. Ann. Probab., 47(4): 1912)))1992-21000 07 2019.
Albert Einstein. Über die von der molekularkinnttishhnn theorie der wärme geforderte bewegung von in ruhenden flüssigkeiten suspendierten teilchen. Annalen der physik, 4, 1905.
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of langevin monte carlo: The interplay between tail growth and smoothness. In COLT 2021, 2021.
Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. NeurIPS 2018, 2018.
Murat A Erdogdu, Rasa Hosseinzadeh, and Shunshi Zhang. Convergence of langevin monte carlo in chi-squared and rényi divergence. In AISTATS 2022, 2022.
Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In /CML 2016, 2016.
Ye He, Krishnakumar Balasubramanian, and Murat Erdogdu. On the ergodicity, bias and asymptotic normality of randomized midpoint sampling method. In NeurIPS 2020, 2020.
Pavel Izmailov, Wesley J Maddox, Polina Kirichenko, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Subspace inference for Bayesian deep learning. In UAI 2020, 2020.
Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are Bayesian neural network posteriors really like? In ICML 2021, 2021.
Werner Krauth. Statistical mechanics: algorithms and computations, volume 13. OUP Oxford, 2006.
Paul Langevin. Sur la théorie du mouvement brownien. Compt. Rendus, 146:530- -333, 1908.
Stanislaw Lojasiewicz. A topological property of real analytic subsets. Equ. Derivees partielles, Paris 1962, Colloques internat. Centre nat. Rech. sei. 117, 87-89 (1963)., 1963.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):20881-2068 2019.
Yi-An Ma, Niladri S. Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael I. Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3): 1942 1992, 2021.
Pierre Monmarché. High-dimensional MCMC with standard splitting scheme for the underdamped Langevin diffusion. Electronic Journal of Statistics, 15(2)411774166, 2021.
Pierre Monmarché. Almost sure contraction for diffusions on Rd Application to generalized Langevin diffusions. Stochastic Processes and their Applications, 161:316-3499 2023.
Wenlong Mou, Yi-An Ma, Martin Wainwright, Peter Bartlett, and Michael Jordan. High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm. J. Mach. Learn. Res., 22(42): 2021. URL http: / fmir. org wwwpppapppppaaaaaaaaaaaaaapaaaae html.
Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Peter L Bartlett. Improved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity. Bernoulli, 28(3):
1577-1601, 2022.
Alireza Mousavi-Hosseini, Tyler Farghly, Ye He, Krishnakumar Balasubramanian, and Murat A Erdogdu. Towards Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality. arXiv preprint 23X3v22333.03589 2023.
11

---

Published as a conference paper at ICLR 2024
Edward Nelson. Dynamical Theories of Brownian Motion. Department of Mathematics. Princeton University, 1967.
Bernt Oksendal. Stochastic differential equations: an introduction with applications. Springer Science & Business Media, 2013.
B. Polyak. Gradient methods for the minimisation of functionals. Zh. Vychisl. Mat. Mat. Fiz., 643-653, 1963. ISSN 0044-4669.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In COLT 2017, 2017.
Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
G. O. Roberts and Tweedie. Exponential convergence Langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363, 1996.
Leonard CG Rogers and David Williams. Diffussons, Markov processes, and martingales: Volume 1, foundations, volume 1. Cambridge university press, 2000.
Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In NeurlPS 2019, 2019.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In NeurlPS 2019. 2019.
Marian Von Smoluchowski. Zur kinetischen theorie der brownschen molekularbeweegnng und der suspensionen. Annalen der physik, 326(14) (26(14):756-70, 1906.
Matthew Zhang, Sinho Chewi, Mufan Bill Li, Krishnakumar Balasubramanian, and Murat Erdogdu. Improved Discretization Analysis for Underdamped Langevin Monte Carlo. arXiv preprint arXiv:2302.08049, 2023.
12

---

Published as a conference paper at ICLR 2024
CONTENTS
The proof of the upper bound on the error of RLMC
14
A.1 Proof of Theorem
14
A.2 Proof of technical lemmas
15
A.2.1 Proof of Lemma 1 (one-step mean discretisation emror)
16
A.2.2 Proof of Lemma 2 (Discounted sum squared gradients)
16
The proof of the upper bound the error of KLMC
19
B.1 Exponential mixing of continuous-time kinetic Langevin diffusion
19
B.2 Proof of Theorem
20
B.3 Proof of Proposition (discounted sums of squared gradients and velocities)
22
B.4 Proof of Lemma (one-step discretization error)
24
B.5
Proofs of the technical lemmas used in Proposition 2
25
B.5.1
Proof of Lemma 5
25
B.5.2
Proof of Lemma 6
26
B.5.3
Proof of Lemma 7
................................
27
B.5.4
Proof of Lemma 8
27
C The proof of the upper bound the error of RKLMC
28
C.1 Some preliminary results
28
C.2 Proof of Theorem 2
................................
31
C33 Proofs of the technical lemmas
33
C.3.1 Proof of Lemma 9
33
C33.2 Proof of Lemma 10
34
C.3.3 Proof of Lemma 11
35
13

---

Published as a conference paper at ICLR 2024
A THE PROOF OF THE UPPER BOUND ON THE ERROR OF RLMC
This section is devoted to the proof of the upper bound on the error of sampling, measured in Wg-distance, of the randomized mid-point method for the vamilla Langevin Langevin diffusion. Since no other sampling method is considered in this section, without any risk of confusion, we will use the notation 9 instead of @RLMC to refer to the k-th iterate of the RLMC. We will also the shorthand notation
fx f(On)
V = (+)),,
and
Vf+u vf(Kkt)).
A.1 PROOF OF THEOREM 1
Let 0g ~ Mo and Lo и be two random vectors in IR defined on the same probability space. At this stage, the joint distribution of these vectors is arbitrary; we will take an infimum over all possible joint distributions with given marginals at the end of the proof. Note right away that the condition Mh+ (M < 1/4 implies that Mh - (Mh) < 1/4, which also yields Mh & 0.18.
Assume that on the same probability space, we can define Brownian motion W, independent of (9o, Lp), and an infinite sequence of iid random variables, uniformly distributed in [0, 1]. Up, .I.... independent of (9o. Lo, W). We define the Langevin diffusion
L Lo 1 Vf(L.)ds w2W.
(17)
We also set
Ox+u = 0x - --UUUU + V2 ( (K+U)) - WKR)
1x+1 0r AV + v2 (W (K+1)) Wkn).
One can check that this sequence {0A} has exactly the same distribution as the sequence defined in equation 6 and equation 7. Therefore,
W TT) < [E[ [[|] ((++ [2] == |0++1 L(K+2)A == xf+11
We will also consider the Langevin process the time interval [0, hl given by
= 1-- / (f + v2 (W kh+t WWn),
I/2 Ur.
Note that the Brownian motion is the same as in equation 17.
Let us introduce additional notation, the average of 4x+1 with respect to Uk.
0u+1 B[0++1 kr, W, Lo)-
Since 1jk 1jh is independent of Us. is clear that
x = |1 - 0x+1l1?2 + 11 Lx++1aal
Furthermore, the triangle inequality yields
1 1y & || Kh,,, + 1|'2, - L(k+
From the exponential ergodicity of the Langevin diffusion (Bhattacharya, 1978), we get
I L Li+tiall
<
- I - Lun = -m - Len l1, = e mh Tk-
Therefore, get
x 2 < |1 2 02+Il12, + (110++1 - L' 1/l +e -2mh xx)
= (m- xx 110 1/lle,)) 1|0 Setz 112
(18)
The last term of the right-hand side can be bounded as follows
1 - O = f - Ey (V fxtulll,,
W v
Using the definition of Oktu, we get
0++1 O1t & (Mh)² (MM))(()3)))))))))) (1/3))²IV4Ии + hp)
(19)
We will also need the following lemma, the proof of which is postponed.
14

---

Published as a conference paper at ICLR 2024
Lemma 1. If Mh & 0.18, then ||0x+1 I/ < (MM) 1.2/hp}.
One can check by induction that if for some A E [0, and for two positive sequences {Bx} and
}Ck} the inequality oi+11 < {{1 A)zx Ck B holds for every integer & > 0. then'
n
1/2
Zin < am
Σ
A) Cr
E A)2(n Bb
(20)
In view of equation 20, equation 18, equation 19 and Lemma I, for = e-m, we get
In < p0 + (Mh)²
*0.77 /V/ll,,//il,, + 112//hp)
1/2
+ Mh
8) (1/3)>"1V< + hp)
hhhh/p
< p0 + 0.7(Mh)²th
V + 1.32
2
1/2 - 0.92 //mm p/m. b) [f(0)))
(21)
We need a last lemma for finding suitable upper bound on the right-hand side of the last display. Lemma 2. If Mh & 0.18 and k > 1, then the following inequalities hold
(V(())) & L.7Mhp"|lool,, + 44Mh(p/m) < 0.31p" + 0.8(p/)).
The claim of this lemma and together with equation 21 entail that
Mh²
- } }"a
En < 20 + 0.7(Mh) Σ pa P +
2
v3
k=
+ + kM + 0.92) p/m
1/2
$ p0000 30 + R0.7VKRMh+00 + Mh 122
+ +L.32V h/h/p/m 7/
< p no + (0.42V k0. + 0.33)
2 /2 IL, + (1.98V<MM) + 1.44) Mh p/m.
Assuming that h is such that (VxMl,, 1)Mh < 1/4 and noting that 00ll1, & W2(uo, + v ppm. we arrive at the desired inequality.
A.2 PROOF OF TECHNICAL LEMMAS
In this section, we present the proofs of two technical lemmas that have been used the proof the main theorem. The first lemma provides upper bound on the error of the averaged iterate 0 and the continuous time diffuuson L' that starts from 9 and runs until the time h. This upper bound involves the norm of the gradient of the potential f evaluated 0g. The second lemma aims at bounding the discounted sums of the squared norms of these gradients.
Thii an extension of (Dalalyan & Karagulyan, 2019, Lemma 7). essentially relies on the elementary Vaa + b)² c & ta VP + ct, which should be used prove the induction step.
15

---

Published as a conference paper at ICLR 2024
A.2.1 PROOF OF LEMMA (ONE-STEP MEAN DISCRETISATION ERROR)
We have
O2 - y [Vxtu]] 1/ + /'" V.((E)) ds
11 6+1
| IV fu+U - V
Mill - Liualen
=Mill - ULAVI - I' + Ueh
V
Uch (VI(E.) Vsa) ds
Mhh
< Mh [VS(L Viulli, ds
[[] vf(())) ds. Mh
(22)
Ls define (1l)= = |[V V (Z) 111. Using the Lipschitz continuity of V and the definition of L', we arrive at
(tt) E M2 {1 / ()(E') ds
+ +2tp|
M² /elV /, /1ITFEE - V ds + 2tp
M2
{ 1/- |VS(Z') - ds + /PIVSAIEE + 21p
2
or, equivalently,
=(1) < M I (()) PIVSAI + 2lp.
Using the Grönwall inequality, we get
p(t) M /IIVELE + 2tp.
Combining this inequality with the bound obtained in equation 22, and using the inequality Mh 1.2, we arrive at
11++1 Lhlls & 1.2M2h L." 1 seliiull, + 2sp ds
1.2MA/T 1-' (s + 2sp) ds
1/2
(22 + 11pp 1/2
This completes the proof.
A.2.2 PROOF OF LEMMA (DISCOUNTED SUM OF SQUARED GRADIENTS)
We have
M 1 10+11
fx+1 < fA + V (0x+1 0x)
Iall2
M
< fa SV V v En +
V2
2
M
< fx A MA 0 R+U 0x112
V2V
En, + 2 | fK+UU V2
(23)
16

---

Published as a conference paper at ICLR 2024
One checks that 0 - 0xIlL. h22 UU IL, + 2hpPiU] = (h² /3]1 + hp & 0.011
VV
+ hp
M
and, therefore,
V - 21112 < (0.011 (5 1/2
< 0.105| V full. + 4
< 0.105 V +.82MMp
Furthermore,
[IV V2 < I/V V2 + AIV falli
F hp MA|OO=U 1x
S IL,, + +hp+ 0..1II M2hp
< 12 II + hp + / + h.182hp
implying that
M J - 12 < (137)2/|V/xIIB 1.4hp)
M
2
< 0.124 V. + 0.7Mhhp
Combining these inequalities with equation 23, we get [[ & B[ʃx] - 0.771 V + 1.52Mhp.
(24)
Set Sx) Ek f/ and (v Σm -" V I Using Lemma 3, we get
10 [[[n+1] p" B[oo pS) S.(f) 0.77 + 1.52Mhp
1-p
Since mh > 1 > 0.915mh,, we get
O,
+ (1-)))))+++)) < < + (") 1.67kp
+ 1.67kp
where the last line follows from the Polyak-Lojasiewiczz inequality. Rearranging the terms, we get inesssealiiiiiuuuaitttt.... (V 3.7p" 6.2kp
(25)
Note that equation 25 is obtained under the Polyak-Lojasiewiee condition, without explicitly using the strong convexity f. However, using the latter property, we can obtain a similar inequality with slightly better constants.
Indeed, equation 24 yields
hE V & [F(( B[fk+1]) + 1.98Mhp.
(26)
In what follows, without loss of generality, we assume that f(0*) = ming f(0) 0. In view of equation 26, we have
& (VS(0)) < 1.3
1.98Mhp
Σ p M (B(((O)) - (0000-((00+1))0) f(0 + I-e-mh
j=
< 1.3(p' E(fe+1]) +13 Σ x ())[[(()) 2.1xp
k
& 1.3p E()(0) 1.3(1 p)
Σ
k-
(()))) + 2.1kp
1=0
1.3M
1.3
x+1
00l
+
M(1 p)
Σ
kー
0 112 2.1xpp
2
2
1=0
17

---

Published as a conference paper at ICLR 2024
We have, in addition
10 = =110; - AV Il, + 2hp & (1 m1)3110x112 + +hp.
Therefore,
2hp
1.1p
Delli (1 mh) 1 +
< (1 mh)2 1olll,, +
2mh (mh)²
m
Using this inequality in conjunction with the fact that 1 - vch & we arrive
h )( &
1.3M
110 +
1.3
M 2* BollE, + 2.9kp.
2
This completes the proof of the lemma.
18

---

Published as a conference paper at ICLR 2024
B THE PROOF OF THE UPPER BOUND ON THE ERROR OF KLMC
The goal of this section is to present the proof of the bound on the error of sampling of the "standard" discretization the kinetic Langevin diffusion. With a slight abuse of language, we will call Balle-Maruyama discretized kinetic Langevin diffusion, or kinetic Langevin Monte Carlo (KLMC). To avoid complicated notation, and since there is no risk of confusion, throughout this section 2y and KLMC respectively. We will also use the following shorthand notation: 24 will refer to @KLMC and Us
fn (()), gn - Vnn vs(O)), 7 = yh, M, 14-M/1 M/7.
The advantage of dealing with y instead of h is that the former is scale-free.
Note that the iterates of KLMC satisfy
8 #x+l = (1 - un) - an + 2 g
(27)
2 n+1 In ~n(,, Bngn. 22n
(28)
where
1 1
8 e - 1+ (0, 1/2),
(0,
1
112
0² - 2n
0²= 2(1 - 2n + 2nj² - e 22) E (0. 1/3)
E (0,
2n
(2n)3
and En, En are two NV 1000,,,, I,) -distributed random vectors independent of (0n, vn)-
Since assume throughout this section that 2M < 0.1, 7 2 2M and 10, have
exp(-n) > 0.95, and mh Mh Mh 1
7]
10
200
The latter, in particular, implies the following bound for g:
1 - -hhh- < === -mh < - 0.99mh = 0.99mn/7.
(29)
For any sequence = (wn))en of real numbers, we denote by (w) the p-discounted sum Ek-o p² pn- Below we present a simple lemma for the function S,,()) that we will use repeatedly in this proof.
Lemma 3 (Summation by parts). Suppose w = (Wn)neN is sequence of real numbers and define S (w) = Ei= e" ww+11 -n=wkkt Then, the following identity is true
St (w) Wn+1 n+1 wo + oSn (w).
Proof.
The proof is based simple algebra:
7
St (w) = Wn+1 +
j+ W/ wht1 + (Sx(ww) w"wo)-
j=1
B. EXPONENTIAL MIXING OF CONTINUOUS- -IMEE KINETIC LANGEVIN DIFFUSION
Consider the kinetic Langevin diffusions
d.,, Ve dt
dV,=-vV, - -f (L. + V22 dW,
(30)
Proposition 1. Let Vo. Lo and L' be random vectors in RP. Lel (V., L.) and (V/, L.) be kinetic Langevin diffusions defined in equation 30 driven by the same Brownian motion and starting from (Vo, Lo) and (Vi, L') respectively. It holds for any > 0 that
c
V, V E
< (mA(T-M))
C
Vo V Lo
||
with C=
I 0 I
L
I,
19

---

Published as a conference paper at ICLR 2024
Proof of Proposition 1. Set Y, Vi V/ (L, L1), Z V2 Vi' that is
Ze Y,
V: V.¹ L 1
C
We note that by the Taylor expansion, we have
vf(L.) Vf(()) H. -
where H. = f2 rL,, [,)) dr. By the definition of (V,, L&) and (V,, E,), we find
di (V. Vi + L)) = --, - L()
= --H,(Y, - Zi).
Similarly, we obtain
V1 V,) = -V - -V;) - (H, It)
dt
=-> HH,YY - Zi).
This implies
d क [| + + = -2,," H,Y, + H,Z,) 22, (->Z: - H.Y. + H,Z,)
< 2 |Yll 7 1 +M +
2( A - M1) [ |
Invoking Gronwall's inequality, we get
Z, Y
2n Yo
& exp (-ImA( (
desired.
B.2 PROOF THEOREM 3
Let 2n. Un be the iterates of the KLMC algorithm. Let (L,, V,) be the kinetic Langevin diffusion, coupled with (1n,, v,) through the same Brownian motion (W; t 3 0) and starting from a random point (Lo, Vo) exp(- f(y) 2, ||ll such that V, vy- This means that
=mne-n-yf -7 (- (VV)(0.)) + 227 /'' (- dW,
Pat1 = Dre = 17
0
dnt1 On + f"' 1he--h-- L- e (m- d3 dsv)((0)) v2, 1 e--(u-=) dw, du.
We also consider the kinetie Langevin diffusion, (L', V'), defined [0, h) with the starting point (Dn, v,) and driven by the Brownian motion (Wat+* Wanit E [0, h)). It satisfies
7 1 (f /27 1' exll--)) aw.
V/' Une one -
L 0,, + /" v'ds.
Our goal will be bound the term nn defined by
c
02 Vnh
I 0p C=
In
9n
Lnh
with
Lp
{Ip!
(31)
L
20

---

Published as a conference paper at ICLR 2024
The triangle inequality yields
UR V i
V Vah L
1n+1
L,
+ c
Lah
11
1.
C
Un
+ 2
2 22 ||
VAlLL, + + L Ealle
(32)
where the second inequality follows from Proposition (see also the proof of (Dalalyan & Riou-Durand, 2020, Prop. I)), while the third inequality is a consequence of the elementary inequality Va² (a b)2 & V2a b for b > 0.
The next lemma gives an upper bound on the terms appearing in the right-hand side of equation 32.
Lemma 4. If f is M-Lipschitz continuous, then for every step-size -h and every 7 the following holds
1n+1 VilLL, /2/27mm + 3 gl M, M
7111nn+1 - Lill,, < ( (0.6 + |1,,11,, + 0.25m|19n1l1, + M,, ) MM,
where My = M/7.
For 1) 0.2 and y > 2M, Lemma 4 implies
||0+11 - Vill,, & 0.r |, +.17
7110 - Lnlla, & (.rr00.0.66/7700.0777.... + 0.0437
Therefore.
V2 Uu+1 VAlLL, + 0 L, & (0 + 0.25m|19m|11.)
(33)
Combining equation 32 and equation 33, we get
Tn+1 Qon Myn² (0p
0.25n|lgn|ltz)
From the last display, we infer that
R-1
In < 0 + Mnn
Σ 0
m-1-
(0.23/p0.. 0.74| 0.25mll g ll..)
This implies that
0.23M,,12 Fn e0xx
+ +.744M, "1
me (110%-1112 0.331 (3:3)119x111111)
1 1-e
0.23M VYp 0.74M,n²
1/2
gxx0 20
0" (1|12- 11, +0.33/
1-8
VI-2
e & 1 0.99mm9999/ / and In view of equation 2
1/2
< 00 + 0.233 + 0.74M.m
2
k (1exil + 0 (1aa) 0
mg
k=n
Proposition 2. Assume that Un ~ N(0 xI)) is independent 0n. 1f 3 5M, K 2 10 and 1 & 1/10
then
< [[422"nEEfo] + 1.1172p
+ 1.98(xx, + 0T9
0=0
1.87=2p + +.2 (I, + 0.96
0
| 112 <
E.
k=0
21

---

Published as a conference paper at ICLR 2024
We apply Proposition 2 and e > 0.998 infer that
?
1.87^2p 3.98g">
+ +3.25 In + 0.96/>p)) ()
1/2
In < e0 + 0/233
'7
+
mg
m
< 5 + 4 0.74M
3.99 [[ 1.88y2p
+ 1+3.26(5,,
+ +..96 / ")
1/2
1.54M < <00 + +0.233k77
1.887"p
3
1/2
[ +.622/ 0.74M
mm
m²
m
1.54M Vm
/ MI
< < 0.620
(0.233 + 0.74v1.94
Therefore, under the condition van 0.1,
En & 1.070" x0 + 1.65M e
1.35Mm/1p
vm
m
Finally, one check that 2x,, > -21 1n > T). This completes the proof of the theorem.
22 .)) and =>1100
Lolli,
B.3 PROOF OF PROPOSITION (DISCOUNTED SUMS OF SQUARED GRADIENTS AND VELOCITIES)
To ease the notation, we set 2n == E(u,, gn] and define
Sn(z) = Σ e" zko
Sn( =
k=
k=0
Sa(f) = 0"
E[fa],
Sn((²)
2k 11
Throughout the proof, we will need some technical results that will be stated lemmas and their proof will be postponed to Appendix B.5.
Lemma 5. for some M > O, the gradient f is M-Lipschitz continuous, then for every step-size and every 7 >> it holds for the KLMC iterates defined in equation 28 that
1nt1 (1 - an) Zn + an11gn. 112
< (M
+ 112llgnl + 1mp 6m2.)
for some positive number öm & 0.14.
Since My 1/5 and 1) 0.1, we have
M₂T²² >
- -1- 1 > 10(1 - e e-01)- - g0.1 > 0.94.
Therefore, rewrite the claim of Lemma 5 with the notation 3 =nMaä ā as follows:
Zn+1 < (1 om 3,) + -.2.n| v. l2,, + 0.67 0.94n 0.94n|lgnlii 1g 1122
Lemma 6. Let 3 < 0.014 and 1) E 0..0. If zu = and the sequences { } C IR, {uu) C IR and
{gn} C Re satisfy the inequality
Tn+ < (e - Bn) + 0.2n|| v. I1, + 0.677pmm 0.94n/1gn112
(34)
then for every e E [0, 1] such that @ 2 n it holds that
Sn(r²) < (S. 0.213,, 0.73mmP 1.072n+1
(35)
1-
1)
where (Sn(=))- (0, is the negative part of Sn(z) and a (1 - -
22

---

Published as a conference paper at ICLR 2024
In order to get rid of the last term in equation 35, need bound on (=)) To this end, the smoothness of the function f. in conjunction with equation 28, to infer that
2yB[fnt1 fn] & 2, 0n+1 0,,)] + M, (7 02, Ill, + M, 2,2 // + "p
< 2am(1 - /M, am Bx/²
< 2000//n - 0.96r/ 91 12 + +.011827| on li: + 1/
with ag = a(1 3M,1²) 3 a(1 - 0.1 x 0.13) > 0.999a.
Lemma 7. Let 00,, 7, > 0. If the sequences [Fn} R. {gn} Rp and {vn] R2p satisfy Fn 2 0 and
2(F Fr) < 20 + 0.0182g/|ennl + 1p
(36)
then, for every o (0, 1), it holds that
(z)))n(22)- Fo (1- (F), (000022))))))
15(1 - 2)
In view of the strong convexity of the potential function and the assumption that f(0.) 0, the Polyak- Lojasiewwii inequality
fn 2m 1g
holds true. This implies that (1 - (f) & (n/7)mS,,(f) & ((n)))).(9)). Combining this inequality with the claim of Lemma applied to F, >E(fn), we get
0.999a(S.(z))- < [[]] (.5. 0.01822.)))))) 0.14my²p
(37)
"
Let us now combine equation 35 and equation 37:
1.10"7 [[ 0.555,. + 0.025, (v²)
0.16Gn2p
Sa(g²) <
17
0.7372p
1.07 zn+1l
+ 0.2135 (v²) +
7
1.10" [ + 0.55., (g²) + 0.2235,, (v²) + 0.75y²p
1.07|2n411
Subtracting (g555,(g)) from both sides and dividing by 0.45, we obtain
Sx(gg) E[foll + O.²5
1.772p 2.38|
(38)
"
m
Let now derive bound for S. (wP)).. We start with the following property, which is a direct consequence of the definition of 12+1:
| 1l2, 12, < -an(22 an)ll I2, - 20m(1 an) + a²112 gl....l 11, + +1yp.
Using the same technique as before and applying Lemma 3, we deduce the following:
(e - (v") 2'llvoll' (o (1²) -">p
2077
< -am(( S.) 20m(1 a2?
Therefore, since 0 0>1- 1- 7
2.02172p
(2a - a²n m "")n < -2am(1 - (n) + S.n)" +
m
Since a = (1 - -- / with < 0.1, from the last display, we infer that
1.137'p mn
S,(2²) < 1.02a (.02a(S, 0.51
23

---

Published as a conference paper at ICLR 2024
Combining this inequality with equation 37, implies
Sn((²) < 1.03g"? [ + 0,562,, + (v019 + 0.2m²
+ 0.5L 1.13>Pp
m
mm
1.03g" 0.625,,, 0.0195,,
1.13y2p
min
Therefore, subtracting 0.0195, (v²) and dividing by (1 - 0.019), we get
S,(v²) & 1.10" fo + (.644S
1.16y2p
(39)
mu
Combining equation 38 and equation 39, we arrive at
1.1g²1
1.1672p
2.45g"7
1.77²p
2.38 2n+1
S,
[ +
0.664
+[fo] (v²) +
+
11
mn)
7)
m
n
2.67g"7
1.277Pp
1.53
2x+1
Jo
+
+ --.325,
ma)
Therefore, subtracting 0.32S,,, (v²) and dividing by (1 -0.32, we get
3.93g"7 fo + 1.8772p 2.25 2n
(,()²) <
"
mry
"
Once again, combining with equation 38, get S. S,,gg)) <
2.45g">
3.930"
fo + 1.87 mn
+ 2.25 e25/2
1.732p +
2.38 zn+1
E[ful + 0.5
"
that leads to
4.420" (a(g²) <
BiJo + 1.11-22
3.51 3511zn+1|
(40)
mm
1
The last lemma we need is the one providing an upper bound on |zn+|l- Lemma 8. For every rj & 0.1 and 7 3 5M, we have
|za41| (1.19x, + 1.147p)²
where nn given by equation 31.
Using Lemma 8 in conjunction with equation 39 and equation 40, we arrive at the inequalities stated in Proposition
B.4 PROOF OF LEMMA 4 (ONE-STEP DISCRETIZATION ERROR)
We the notation
vo(()= = (1) - -t
vi2 E- - 7t
7
and note that
(1) 1t, 2/2(1) 0.5
Furthermore,
| Vill,,
c - (Vf(L)) vf(0.)) ds
(h Vf(E.) - vf(0.))le) ds
M7 /") [L' On 11, ds.
(41)
24

---

Published as a conference paper at ICLR 2024
where the last implication is due to the M-smoothness of the potential function f. On the one hand, for every $ E [0, hl. we have
L O2 / Vi du
{ E -- (V](L) VS(O,)) d'du 1/2(0) go.
= =s)(s) Un
22 e ((a-t) dw
= -b1(s) (2(5) gn + V2y /'" di())
1 Vi(s (V - vS(O,)) de.
Therefore,
I' Onlli & & 0.5yy² 11 21 2ps/33 My [ (s- ()-D)/E; 0mlles dc.
The last inequality combined with t & h allows to the Grönwall lemma, which implies that
|| In 12, < (sllual + 0 l lL, + (2233)p 78 Me)
(s|1unllz, + 0.5ys² 1 11, + (22/3)ps 78) 0.5M7h?
(42)
Combining the last display with equation 41, we get
Un+1 Villa, < ( 1, + nllgnn + YY3) M
e. + dnnllgnll Inll,, + 0.33 0 e
This completes the proof the first inequality. To prove the second one, we again use the update rules of pn+1 and L':
=7 1/" 1. "--2-- - Vs((.)) ds dade
|0+t1 Eallia
< 1,- h (' |V](E.) - VS(O.) ds
h
I ||' On I|, ds dt.
M
The last term can be bounded using equation 42. This yields
>||0nt1 1hll1, 2 (-' 1 (s (s|vaillz + 0.5 1lg + (2/3)pp5 7) ds dt
< e, M,, (1 Pellle + Iellnlli + +0.1 < (1/6) M.n (1 + 0.25m/ + 0.6
as desired.
B.5 PROOFS OF THE TECHNICAL LEMMAS USED IN PROPOSITION 2
B.5.1 PROOF OF LEMMA
Since 2, = Elg,T vn), we have
1zn+1 2n E[gg (Vn+1 vn)ll [ gn) T
(43)
25

---

Published as a conference paper at ICLR 2024
On the one hand, definition equation 27 of Ux+1 yields
Elgn (Un+1 v,)] -n Un] onllenlia
(44)
On the other hand, the Schwartz inequality implies
B[(g++1 [n)]ln+))) < 9h-1 - gn sulle, Untiille
M @n+1 On lio Nntilles
Similarly, using update rules equation 27 and equation 28 of the KLMC, and the triangle inequality we get
7 1 - 0n llls < 1 ll.. + gnlli - 2n + 33""> | 12 < ll ll2, + 1211gn11.. - 2an(1 - -on)en + 21mp.
Hence,
(r/n) n+1 - -in1li, + 1| 1l22
01 1
nn ll. + 2112119. 12 - am(3 + 1 an) + 3mp.
(45)
Therefore, combining equation 43, equation 44 and equation 45, we get
2n+1 (1 11-a0 an + am an 1x & nM (1 + 1 11 12, + 3 mmp))
17² Mr alB 1 om)) 2n.
with om & an1(1.5 on7) & 0.14, as desired.
B.5.2 PROOF OF LEMMA
We apply inequality equation 34 for every index &o & n multiply each side by gntkk:
3n))"=*>> sk+1 - + 0.20- //| 112 + 0.677 0.94ne" 1g
Summing over k. applying Lemma 3 and taking into account that 20 0, we get
xnt1 + (S((2) < - (2.2,, 0.67 0 0.94n8,.(9)
1-
0.68n/ax 0.94n)8n(s)))
< - (3) + 1
This implies that
0.94m)nn(9) & (e -0- ( 0.6877xp
1
Note that p-c- -n and c - - < - & 1.02(e 11) 1.020m. Therefore,
0.681)²
0.94nS..(9)) < 1.02am (x) (22
1nt1
1- 0
Dividing both sides of the last display by 0.949, we get
0.73myp
1.072n+1 1-
< 1.099 (.
n
This completes the proof of the lemma.
26

---

Published as a conference paper at ICLR 2024
B.5.3 PROOF OF LEMMA
We write inequality equation 36 for all indices k and multiply both sides of it by g" Summing the obtained inequalities and applying Lemma 3, we obtain the following:
2170xp
2 (). - Fo & s 20on5, + (.0 + 15(1 1 2)
where the left-hand side is obtained using Lemma and the fact that F > 0. Rearranging the terms and dividing by obtain
2p 15(1 2) +
< ()
Since the right-hand side of the last display is nonnegative, we infer that
20p²pp (F) (1-) (0..125))).....1))s + 15(1 Ø)
(n)))S(:))) < d" +
which coincides with the claim of the lemma.
B.5.4 PROOF OF LEMMA
In view of Lemma 5, we have
|n++|| (e " + 0.3r)
|2a| 0.3r72)(221)
7 gulli, + (0.2//umn1, + 0.2172 Il. + 0.027mmp)
< 0.56(ll9al11, + |/ || )1, + 0.00277p
0l.6 V (L,))))l + 1, Vanilla, + Mp vP)) 0.0027
where we have used the facts V (VL())))l.. = fIV di & Mp (Dalalyan & Karagulyan, 2019, Lemma 3) and [[[]| VnA | = yp. Finally, one can note that
llgn (S(En)))le + | Vaalle < 0.5y|| Lnn Tnn + 1| Vnallia
< 0.5| Un Vnn + r(On Lnn))li, + 1.5llun. Vna
< 55/2
Therefore,
|zn+1| < (1.19x,, + /70)/77)) + 0.0027"p & (1.19x, + +.144/pp)
This completes the proof of the lemma.
27

---

Published as a conference paper at ICLR 2024
C
THE PROOF OF THE UPPER BOUND ON THE ERROR OF RKLMC
Consider the underdamped Langevin diffusion
dLe- = V, d6,
where dV, = - (L, di + v2y dW;
(46)
for every é 3 O, with given initial conditions Lo and Vo. Throughout this section, we assume that Vo NN, 7Tp)) independent of Ly, and the couple (Vo; Lo) is independent of the Brownian motion W. We also assume that Lo is drawn from the target distribution и, this implies that the
process (L,, Vi) stationary.
In the sequel, we use the following shorthand notation
= yh,
Vf.
fn = f(O,),
9n. = g(0n),
9n+U = g(0
M, M/7.
The randomized midpoint discretization proopos and studied in (Shen Lee, 2019) of the kinetic Langevin process equation 51, can be written as
1 n+t 0n + 1
Un
Uh
(1 - - ds VIn v2 (0( (1 (1- dW,
Th
Va
0
1 n
vn+u + V2 1/) (1 e (0--))) dW
On+1 = On +
Un
Un+1 Un " me Y(h Ubh V Vn + V27 1" e- aw,
(47)
where W Wnh+s W nh. We rewrite these relations in the shorter form
1 Un+u = 0r + 'n "UaVu, - U3 gn + U / (0
(48)
0 n+ = 0r + -1 U2 -1/32 Intu 22m
(49)
U = Un - n02u 21Bagn+u 02
(50)
where ãi, B1, 32, Bg and の are positive random variables (with randomness inherited from U only)
satisfying
ā < 1,
31 1/2,
B3 < 1/2.
of < 1/3
and [[]]] e [0.468, 0.5). Similarly, āg, 32 and 0g are positive real numbers depending on ? and
such that
02 & 1,
2 1/3,
o3 < 1.
We define
6,41 Ey Eu(vn+t)
0n+1 Ey [v
The solution to SDE equation 46 starting from (v,, f,)) at the n-th iteration at time h admits the following integral formulation
L = U, + fo d'ds
V e e rt -2 f x x(- VfLL) ds + V2n L' e - dWhh4s
(51)
These expressions will be used in the proofs provided in the present section. Furthermore, without loss of generality, we assume that the f(0.) = minger> f(Ø) = 0.
C.1 SOME PRELIMINARY RESULTS
We start with some technical results required to prove Theorem 2. They mainly assess the discretisation well discounted sums of squared gradients and velocities.
28

---

Published as a conference paper at ICLR 2024
Lemma 9 (Precision of the mid-point). For every h > 0, it holds that
[n++ Loull, < e /2 (0.065nll + (1/6)]|vmlla + v Mmp/54)
Lemma 10 (Discretization error). Let , Vi) be the exact solution of the kinetic Langevin diffusion starting (in, vn)) 7 3 M and h > 0, holds that
(0.065nll9ull1, + (1/6)||e/llz, + VIND/5A) M
711 - 1/ x
v3
r7²
7110n+1 - Intilliz & Mar (0.26 Un 11, + 0.1066/777) + v3
(0122M, + +1) 1)119nl11
0.065mll9lllzz + (1/66||umllza |0+41 Villia < Man E x
1 + vmpp54
|1a+11 Bnt1lli, & M (0.82 u. lh, + 0..41 +
(0.55.M.1) + 1) gm 11.
v3
Corollary 4. If > 2M and n $ 1/5, it holds that
0110,+1 - 1/, & M3ny (0.038
9. 21 0.098| 0, v, + 0.084/777))
y An11 dn+1l Lا < n/² 0.578
9 + 0.02 0, 11, 0.005//77P)
|8,+1 Vi & nf 0.066n
9, 0.168 0, +0.37
|1 Bptillis &
n2( 0.591 | 0.164| 0.082 /1Tp)
Proposition 3. 1f > 5M and 17 & 1/5, then, for any
any n E N. the iterates of the RKLMC satisfy
0" * u 12 < 18.80*;E|fol + 3. + 1/5/)p)² + 10.6>2p
m
11.2?2p p
+ 1,5 + e |g ll. < 211.7"">B[fo) + +
m
where e exp(-mh) and n, (Il2, - V. + +1 Vnn + 70,, Lnnt) 112
Proof of Proposition 3. We use the same shorthand notation as in the previous proofs and assume without loss of generality that 0. = O. Let us define 24 E[e, gk]. and
(2 = 0" Zk
Sn(g²)
Σ
0²
11g
11
0=
k=0
Sn()) = Σ E[fa],
Sn(x2)
*|| 1|
We will need the following lemma, the proof of which is postponed.
Lemma 11. For any 7 0 and h > 0 satisfying > 5M and any & 1/5, the iterates of the randomized midpoint discretization of the kinetic Langevin diffusion satisfy
|u 12 <(1 - ll 12,2-
28.nB g 2n²
12 ll,, 2.122mp
(52)
Elv, T 19++1 <
0.51 v, 12, (1 Elv g. 0.97m|
gm 11,, + 0.9m">p
(53)
[ fu] <
0.28,)||1,,111...
[2n 9.) 0.46, gm 11 0.000'²p
From the first inequality equation 52 in Lemma 11, we infer that (t²) < (1 - 1.47)) (w²) - 20 Sa (z) + S, (g)) + 2.12 In view of Lemma 3 and the fact that || I2, pp, this implies that ( + (z) < Sn(v²) ( 2,23, 2.1272pp/m ppm < (1 (1²) + 25 + 2.127 2p/ppp//mmm//mm +
29

---

Published as a conference paper at ICLR 2024
Note that 1 mm 7
< 0.02t.. Therefore, obtain
(1.47 - 0.02),,,,) (z) & 2n 2.147Pp
mir
that is equivalent to
1.48>2p
Sn(v²) & 1.38 1.38r/S., (.33// +
(54)
mor
The second step is to use the second inequality equation 53 of Lemma 11. Note that mn/7 & 1/500 implies e 0.998ma//7. then follows that
(2) = (1 - (2 0.97 (5 + 0.51nS,.,²)) +.55)...)))+
p.9
This inequality, combined with Lemma 3, yields
0.97m)S, < (022) + e- (=) + 0.51 + 2x+1 + 0.90m2pp/m
(2) 0.51n/S. (v²) + | 0.9tm)2p/m
This can be rewritten as
Sn(g²) < 1.03025, + (133555 + 1.03 2n+1 0.93~2p
(55)
"
Let us now proceed with a similar treatment for the last inequality of Lemma 11. Applying Lemma 3, get S (f) > a5, g" 'E[fol (1 mn/r)5, - 1 Bifol, which leads to
Sm) & -+ +
0.46672 0, (o + 0.09
m
From this inequality, and the PolyakkLLojasievizzzooiiiiiiiii conditton one can infer that
n2p
(z) < - " 0.28% 400
0.09
(56)
Combining equation 56 with equation 54, we get
(:003--00))),,))++000 +.09 "r2p
Sn < 1.38 Bl 0.25,, + (0.5
+ 1.387/ 1.48~2p
mn)
Since 7) & 0.2, it follows then
S,(u²) < 0.8 (0") + 1.8e" 7
2:²D)
E[ful +
(57)
mm1
Similarly, combining equation 56 and equation 55, we get
+ 0.09 "r²p
(a()²) < 1.03 (o 0.28 + (0.5 - 0.467)S..(9))
+ 0.53S, + 1.03| 2
0.93-²p
"
Since & 0.2, it follows then
Sa(g²) (v3) 1.94e"
1.94/zn41
0.94>2p
B[fo] +
(58)
17
m
Equations equation 57 and equation 58 together yield
S. & 0.84 Sx(g2) + 1.8g" [EJo] + 20²p> +
1.940"
1.94
1.94|zn41
Zn+1
0.94-2p
E[So]
mn
7
"
m
3.460²
[ + 1.94 =n+
1.7872p
0.84S,
mn
30

---

Published as a conference paper at ICLR 2024
Hence, get
21.7g"y
12.2 12.2/2n+1
11.2y²p
(g)
B[
mmn
Using once again equation equation 57, we arrive at (v 0.8
2
12.2|
11.27
1.8g
21²2)
[[ +
+
Elfol +
"
mm
mnn
which is equivalent to
18.80" 9.8|2.411
10.672p
Sn (1²)
[ +
myn
To complete the proof of the proposition, it remains to establish the suitable upper bound on |zn+1/- To this end, we note that
9 11, < M Iniili, + Mp
0.2 0.2 Int 0.2yp
0.3(In + +1.5v7p)
| 12, < 00 - Vahlle, + 7PP
00 Vallle, + VTP
+ VTp.
Then, following the same steps as those used in the proof of the second inequality of Lemma 11, one can infer that
1zn+1l
|2al + 0.97m 9. ll., + 0.51n//e,,1 11,, 0.09m)n<
|g.l|1. |,,11,, 0.1 .x 11, 0.051 0, Il,, 0.001>p
1.1/lgh 11, + 0.301| I12, + 0.001yp
< 0.099 + 1.5 + 0.301 (z, + 1.1 2
00.4 + 1.5
This completes the proof of the proposition.
C.2 PROOF OF THEOREM 2
Let Un+ in+1, Un+1 be the iterates of Algorithm. Let (L,, V/) be the kinetic Langevin diffusion, coupled with (0,, vn)) through the same Brownian motion and starting from random point (Lo, Vo) x exp(-f(0) - w such that Vo = ug. Let (L,, V/) be the kinetic Langevin diffusion defined on J0, hi] using the same Brownian motion and starting from (0,,, 8,)-
Our goal will be to bound the term Hn, defined by
C
Un In
Vnh Lun
I Og Ip
In
with C=
IIp
La
To this end, define
G.+1 = Ey (vn+t,
Hn+1 = Eyy (2n+1]]
Since (Vi+1)) L(n41)h) are independent U, we have
C
Un+t -
c
0nt1 Vin+ijh
2
+
0n+1
0,+1
0at1 L(nti)
L2
31

---

Published as a conference paper at ICLR 2024
Using the triangle inequality and Proposition 1 (See also Proposition 1 from (Dalalyan & Riou-Duram 2020)), we get
Un+1 Vi+ti) Cc
aat1
V(n+i [n+
C
c
Ont1 [(n+))
x+1
Ln_
L
12
Lz
L2
%
1n+1-
BFn
L2
where g = e Combining these inequalities, we get
2 & (exn + vn-1)² + 2n111
where
c
Un-1 V.
2n+1 = C
Unt1 Unt1
2
ya+1
1n+3
[n
1 On+1 2 Dn+1]
L22
122
This yields
1/2
In
E 00xo0 +
n +
yk
2n k)
2k
k=1
k=1
1/2
1/2
g" xo +
yk
2( k)
2 2k
where the second inequality follows from the Cauchy-Schwarz Schwarz incquality and the formula of the sum of geometric progression. Using the fact that [C[a, b] 1 = +Ia 7611 & 3||a||2 + 21b12. we arrive at
w & 3| - VilLE, + 27 1 - 1
2+ & 3| 1 112, + 2 -n+1lll 11
We then have
(3 6% VillL, + 2/ L' (12.))) (1.0017
1/2
In & 6"20 +
min
1/2
0 (k Exlli, + +2,2110x &21l2s))
(59)
By Corollary 4, we find
1 V
< M² (0.0666l) g 0.100 + 0.137
< 0.2" x (.0511((721 + | 11 + mp,,
2
0g 1i, <
0.09 0.084
< 0.2 M, x 0.0002 + || 22 + mp))
و + + 1,,, 0.082 2
|/0 - 0x 12, < 17
< n 0.39 (1 12 + 0/ 12 + mm),
2
22100 - -Gx 12, < 17 0.578 9
0.02| 1 |L, + 0.005
< 1)² x 0.32 gh 1 12, + | 112 + mr))
6One can check by induction, that if for some sequences Nn, Vn. 2n and some @ E (0.1) it holds that
- & (pa,, 2 + 2 then necessarily vn & d²x0 + Dn 6 R= k e ((n-k)=2) 2////2 for
every E N.
32

---

Published as a conference paper at ICLR 2024
Therefore, infer from equation 59 that
1/2
In E 20xot
0.2 M,n x 0.0310"~*"1"" ll, llullii + myp)
mm k=
b) 11 l2 + 11 + myp) 1/2
Σ
1.82n (>
From Proposition it then follows that
10.8
(1721l 11 I2, + 11 77p) < 18.9 + 3.97(
m
k=0
2n b) 11 12. + -l + typ)) 40.5g"m + 8.8(2, + / + 21.97²p
k=0
This yields
Fu < (0 3.97(xn 1p) 10.872p 1/2
m
+1/3/ 16(xn + 1p) + 4072p> 1/2
0 (000+
(0.167) v 8.7m 3/2 2 o" 6.41) 3/2 / p/m.
/6 < 0.1, which implies that We assume that vpc 1/6
Tn e 30 + 0.072xr, 0.16v e 0.12 " ///////////// kp/m //4
rv p/m.
Rearranging the display leads
< 1.08g"xx zo + 0.18 e"> + 0.12m hkpmm 6.9r p/m.
Finally, we use the fact that Zo = >W2(M,. 7) and on 3 ?Wz(Un, to get the claim of the theorem.
C.3 PROOFS OF THE TECHNICAL LEMMAS
We now provide the proofs of the technical lemmas that we used in this section.
C.3.1 PROOF OF LEMMA
By the definition of OutU, we have
Uh
10,-0 L'uull <
(1-e (U-e) 10-)
0
Uh
(11 - ((Un (V V
<
Uh (' (1-e c1-e-Uni - ()(EE) V)(L dt
<Mhnu J (1 (1-t)]l 1))l[b L'uell dt,
33

---

Published as a conference paper at ICLR 2024
where in the last inequality we have used the Lipschitz property of f and the inequality 1
e-Un(1-t) < Un(1 1). By taking the expectation wrt to U, we get
T4 {
(1 - --/b/ - L'ynell ll dt 21
Eu In+U 11 & 12
Eu
2
U² L
EU
IL/- ---uueell dt
3
1²h2n1
/
Eu EUIU
|| L'pel 2t. dt.
3
Hence, we obtain in view of eq. (42)
12
!
1
||0++u I/un li
11
Ihelli dt
12
M 1
S.'
272p(h1)3
+ ht et,le,, + 7(1))
[V ) de
12
3
2
9 2M MM Myn
2
(2233)mmP + 1/3l// + vo.05>h
12
Taking the square root of the two sides of the inequality, we get the claim of the lemma.
C.3.2 PROOF OF LEMMA 10
By the definition of 2 we have
1/¹² (1-e -1- ds
10++1 1/1l = EB [1(1 - -
Eu [n(1 e -h- U1b) ( V - hBu (1- (1-0- (oh--e / (((
< NBv (1 - E - (1 -
< "u (1
Ui] -'uall
where in the last inequality follows from the smoothness of function f and the fact that 1 Uhh) < 7(1 Uhh. Using the Cauchy-Sehwer inequality, we get
|| - 1 < MZ Bvl(1 U) EE [||0 - L'u
M²n 4 Bu [110 1..
3
By Lemma 9, we then obtain
Mar?
|0 Ih,le, <
10++ L'ullea
v3
M
(0.065m + (1/6)||e,/lz, + (1/7)//)))
V3y
This completes the proof of the first claim.
Using the definition of & n 1, and the fact that the mean minimizes the squared integrated error, we get
|1++1 n+ -0n11li, = 11|| -e- V Eu [[1 - --h((1--)) V fntuilla
h --hhl-U1) Eu 1 V
34

---

Published as a conference paper at ICLR 2024
Recall that Ü 1 U, combining this with the last display and the triangle inequality yields
||0 Intilll < 1n|(( c-
( (Vatv Vin) |1, 10|| < M ( Smllla + hnl 1ntallltal
fel(e-n Efe E(e-
(60)
In view of equation 48, we get
[101 u+n++ 0n)lli,
E (1-U))²((1)))
U)² (11(1/)))))
(2)3))))
122 Un lif
1/11gn lli
n'p
+
15y2
210y
90y
In addition, ||1 U1 v v13.. Therefore, infer from equation 60 that
|| - Int1ll12 MaT'
TYP
7
Mnn
+
1
1
V15
90
210
v3
Numerical computations complete the proof the second claim.
By the definition equation 50 of Un+1; have
By [he T(h--(h) V fntu] - 1/' e->(e- V[(
ii+1 - Vill,,
> he
((h-U()) Un) UNN Sn+u he V 7(h Shh
< Mrhlllnnt - LUNlLe By Lemma 9, we obtain the third claim of the lemma.
In view of equation 47, and the fact that the expectation minimizes the mean squared error, we have
|0+11
G 1 = 7/
7h(1 ( U
By [e 7hh(1 (1(1111100 U fn+t
< 7/1
- Eu ( 1h V
The last display, the notation Ü 1 U and the triangle inequality imply that
||u++1 op+ 11l.,2 & rhlle n0 (Vin+v V.nm + >/ (e Berle- V)
W/rh||0n+4 - -01l1,, +
n/²
< Mrhl| -0nl1, + v3
In Il..
(61)
In view of equation 48, we get
| 2 0
E =E[1(n/>)(U - U +2/3)
2n 2 ll.,
11 12,
n7'
+
+
3x2
10y2
6y
The last claim of the lemma follows from the previous display and equation 61.
C.3.3 PROOF OF LEMMA 11
From equation 48, equation 49 and equation 50, it follows that
?2110n+u -0,11 < |Unāvv 3 11, + (1/6))²np (2n /32 on I2, + (11t110) + (12/6)pp
(62)
and
7||0,41 -Onl1., < 1///v//la. + 0.5v) |n 11,, + /(2/3)m7²ツ
< <nll,lli, + 0.57 0.5 + 0.5.M, 1 - - + (2/3))77
1.0017/|w.ll1, 0.501 ll, 00.671p2p
(63)
35

---

Published as a conference paper at ICLR 2024
where in the last step we have used equation 62 and the fact that M2n & n//8 < 1/200. A bit more precise computations also yield
7110n+1 Qulli, < (mll/enli 1111| 11,,)² 1) 1/2
11²
In+U 9ullis
(nl v. lt, + 3/ | l|t,)) 2
+ {
1/2
M
10 - -On 11
2
< (fllonn Illn (1,,))
2 }mmppp
1/2
+
10
1
1 On - -nnlLL.
Taking the squares of this inequality, we get
12 - -nlli < (ullenllza + 3 (lllmnlle) 112))) 3 - 1/ - -
+ 1 fellanles + 3/ ( 3 p] 1/2
10 - -uull1,
< (1 ) (1 lt. + J/ (llnnltz)) 2 + 7mp + 7 - 0mll2s
< 1.017 (1 + V3llenn |L,) + 3mp + 0.17 1 - 0ullia)
-
< (0.687/(31|ee,, l2. + 19 + mp))
(64)
This implies that for 7 > 5M and 1) < 1/5, we have
/u.tall2 < (1 - -(2)) | li. 4n ( gn+c] 7 129 + 21y
+ 21 2 gg+t - In
< (1 -ā2n)² | 11, - 41 - ā22)) T gn+ul 1 gn 2mp
+ 2M, 2 > (0n+U 1t,
< (1 - n)āz)² | I1, - 4n/(1 - nā ((1))113221 T gn+el + gn+ulll, + 2.1mpp
+ 20( m) |n ( N+ - 11
< (1 -2n))² | 12, 2) 1 nā: E U, 9n1 + 1.17 | 12, 2.1mpp
+ 2M (1 (0n+U 0,,, 31 (0 In).L.
< (1 1u, 26 - El,
+211mp
+ 1| 11, + 0,) +
(M, - 1,,
< (1 -2n) 11, 2 11, 2ū [ 22n)
1.117 1,,77 2.1177p
+ 0.2.M, || 5.4M 11 - I...
Since for 17 & 0.2 we have 02 0.9, we get (1 2²7)² + 0.2M, 5.4M, & (1
0.9r)) 2 + 0.0087 + 0.16n < 1 - 1.477. Therefore,
W 12,, < (1 - 1.477) 11..1 2ā - nāz nā²) F g..1 + 1.127² 1. + 2.12mpp.
The next step is to get an upper bound on Ei Ei In+1l E gml in order to prove equation 53. To this end, we first note that
|eotillis & 11 + + + 2177
< || + 1 + M, 0n)lle, + 22mpp
< (..004(12.,) + 7/lgglll., Ill + 22mp)
(65)
From equation 63 and equation 65, we also infer that
pll || 1 0nlli, & /11000 + 0.501 + 0.34) (1/ + 1 +2mp))
2.2n + 1111 + 2/71)).
36

---

Published as a conference paper at ICLR 2024
Therefore, this bound and some elementary computations yield
E B 19++1
< E gm 110 (g g.). + E un))
vn)) gnl
< M
+
0n)llia - a2n/b/0 gnl - gntul
< (1 -
+
-0)lli - 1illgnlie
+ 1.
& (1 aunn) - + 2.2.2 (1
722 Il + + 19 2mpp) + ,, (1 + , + pmm)) 1/2
< (1 22
+ +2.2M, li; 12 lli 2mm1)
+ 0.5.M,m33 |0..li,, 1 mmp).
Grouping the terms, and using the fact that M, < 1/25, we arrive at
E T 1(r4+19nt1) & (1 (2 gn] 0.97m 9. 12, Ml..M, + 4.5M,mm'²
(1 a21) 9m| 0.97m 9m. 12 0.51n||e,,12, 0.9rm/p
Similarly, using the Lipschitz property of V and equation 64, we get
yE[fn+1 ful < /Elg (0n+1 ...) + (MG12))11(00+11111 0m11l
E.g. (a27/0
11, + + 11 + tpp)
< a2n gm] - 11 1 |1 -0,)lTa
1g, +0.111:(Onn- 0x,)lE.
+ -7 .
< [, - 0.468/ I2, + 0.1 1l 112
+0.07 n, li, + 0.017 12, 0.02n)²> -3.077 2. + + + mpp)
Grouping the terms, and using the fact that M,, < 1/50, we arrive
[l fm] & ā2nBiu, gm] 0.46. 11 + (0,28,/11u,,,1 + 0.09m"'7p.
This completes the proof of the lemma.
37


Reviews:
[{"review_id": "vZG3Io3Xra", "reviewer": "Reviewer_Y55L", "summary": "This paper revisits the problem of sampling from strongly log-concave continuous distributions in high dimensions. A classical sampling algorithm for this task is the “Langevin Monte Carlo”  MCMC method which uses Langevin diffusion, a stochastic differential equation (SDE) that models the motion of a particle in a fluid. This paper provides an improved analysis of the randomized discretization scheme called “randomized midpoint method” for the aforementioned SDE. The results rely on the assumption that the magnitude of the eigenvalues of the potential function (i.e logarithm of the distribution’s density function) is both upper and lower bounded, while the ratio $\\kappa$ between these upper and lower bounds appears in the bounds presented. Specifically, faster convergence of the randomized midpoint method for Langevin diffusion is shown for sufficiently small ratio $\\kappa$. Similarly, the authors analyze the randomized midpoint method for the kinetic Langevin Monte Carlo method to obtain improved bounds, although with some slightly stronger conditions and with the advantage of not having to find a minimizer of the potential function for initialization.", "questions": "Do you an example application of the improved analysis do get better results for a specific problem?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "This is a well written paper that provides improved results on existing algorithms for Langevin sampling, which can be potentially applicable in a wide range of problems.", "weaknesses": "Some of the results are potentially still not optimal as the authors also suggest. It would also be nice to see how the improved bounds can be applied to some more concrete problems even for theoretical results. \n\n\nMinor comments:\n-Page 2, line 8: “strongly”->”strong”\n-Page 2, line 22: “at”->”a”\n-Page 2, “notation” paragraph, line 4: “semi-definite positive”->”positive semi-definite”\n-Page 6, line 5: “designatex”->”designate”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i2mMFQ2cy5", "reviewer": "Reviewer_4YVq", "summary": "This paper considers the randomized midpoint discretization for the kinetic Langevin diffusion for sampling from a target distribution with smooth and strongly log-concave density. A non-asymptotic upper bound on the W_2 error of this discretization is obtained. A bound on Euler discretization for the kinetic Langevin process is also obtained.", "questions": "In the second paragraph after (7), \"a close\" might be \"close\"?\n\nWould the qualitative behavior of numerical experiments change when the dimension p increases?\n\nIt seems that two notations d and p are used for dimension in Section 5.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides strong error bounds on randomized midpoint discretization for the kinetic Langevin diffusion for sampling from a target distribution with smooth and strongly log-concave density. The bounds substantially improve upon earlier results, have explicit constant and transparent reliance on the initialization, and don't require starting at the minimizer of the potential. The proof technique is novel and is based on summation by part.", "weaknesses": "It would be nice if some simulations in higher dimensions p could be included in Section 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oGQF9m24lF", "reviewer": "Reviewer_FzXn", "summary": "The paper is an in-depth study on the randomized Langevin algorithms, particularly emphasizing the Randomized Midpoint technique in LMC. It is claimed that the bounds are superior to those previously established in the literature.", "questions": "Can you provide any empirical evidence that the current algorithm improves in real world?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper consider widely-used randomized midpoint discretizations, offering notable enhancements over current standards, particularly in terms of condition number dependency and the stability of bounds. A key advantage of these bounds is their explicit numerical constants. The Randomized Midpoint is important  to achieve optimal convergence rates in first-order algorithms. The potential of extending this technique to other domains also presents an intriguing avenue for exploration.", "weaknesses": "While the paper presents some intriguing results, most of them primarily offers incremental advancements in the field. It applies the Randomized Midpoint technique to lessen discretization errors, which in turn marginally enhances the rate of convergence. However, the mathematical methods employed are not particularly interesting or surprising.\n\nThe empirical evidence looks weak to justify the criticality of the Randomized Midpoint in standard LMC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5irkWxbvSh", "reviewer": "Reviewer_gtQ6", "summary": "The authors considered Langevin Monte Carlo method in the problem of sampling from a target distribution that has a smooth strongly log-concave density. Specifically, the authors developed a novel proof technique that led to nonasymptotic $W_2$ error bounds for the randomized midpoint method for the Langevin Monte Carlo (RLMC) and the randomized midpoint method for the kinetic Langevin Monte Carlo (RKLMC). The upper bounds are competitive with the best available results for LMC and are free from a term that’s linearly dependent on the sample size. The authors also provided a nonasymptotic $W_2$ error bounds for the kinetic Langevin Monte Carlo (KLMC) algorithm that has an improved dependence on the condition number. Numerical experiments were conducted.", "questions": "Please see the weakness part. In particular, how would the extension to non-convex or non-strongly convex potentials depend on the authors’ proposed methods?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-organized and clearly written. The authors did a good job discussing backgrounds and intuitions. The proposed error bounds improved upon existing results, and the novel proof technique itself has the potential to be used to re-examine other existing analyses. The paper includes sufficient comparison with and reference to related results/literature. The authors also addressed several limitations.", "weaknesses": "A major part of this paper’s contribution is removing the (square root of) $mnh$ for the error bounds of RLMC and RKLMC, yet I’m not clear on how important this is. The removal of this term, claimed by the authors, is an important step toward extending these results to potentials that are not strongly convex. Similarly, in the comments for the result for RKLMC, the authors claimed that not requiring the algorithm to be initialized at the minimizer of the potential is important for extending the method to non-convex potentials. However, as the authors pointed out in the discussion, strong convexity seems to be an essential assumption for these results. Therefore, I’m a bit unclear on the significance of this paper’s contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)