Sqrt(d) Dimension Dependence of Langevin Monte Carlo
Authors: Ruilin Li
Hongyuan Zha
Molei Tao
Venue: ICLR 2022 Poster (2022)
Keywords: unadjusted Langevin algorithm / Langevin Monte Carlo
non-asymptotic sampling error in Wasserstein-2 distance
optimal dimension dependence
mean square analysis

Abstract: This article considers the popular MCMC method of unadjusted Langevin Monte Carlo (LMC) and provides a non-asymptotic analysis of its sampling error in 2-Wasserstein distance. The proof is based on a refinement of mean-square analysis in Li et al. (2019), and this refined framework automates the analysis of a large class of sampling algorithms based on discretizations of contractive SDEs. Using this framework, we establish an $\tilde{O}(\sqrt{d}/\epsilon)$ mixing time bound for LMC, without warm start, under the common log-smooth and log-strongly-convex conditions, plus a growth condition on the 3rd-order derivative of the potential of target measures. This bound improves the best previously known $\tilde{O}(d/\epsilon)$ result and is optimal (in terms of order) in both dimension $d$ and accuracy tolerance $\epsilon$ for target measures satisfying the aforementioned assumptions. Our theoretical analysis is further validated by numerical experiments.

Published as a conference paper at ICLR 2022
SQRT(D) DIMENSION DEPENDENCE OF LANGEVIN MONTE CARLO
Ruilin Li
Hongyuan Zha
Georgia Institute of Technology ruili 1 1i@gatecc edu
School of Data Science Shenzhen Institute of Artificial Intelligence and Robotics for Society The Chinese University of Hong Kong, Shenzhen zhahy@ cuhk, edu. en
Molei Tao
Georgia Institute of Technology mtao@gatech.edd
ABSTRACT
This article considers the popular MCMC method of unadjusted Langevin Monte Carlo (LMC) and provides a non-asymptotic analysis of its sampling error in 2- Wasserstein distance. The proof is based on refinement of mean eeeane analysis in Li et al. (2019), and this refined framework automates the analysis of large class sampling algorithms based on discretizations of contractive SDEs. Using this framework, establish O vale) mixing time bound for LMC, without
conditions, plus a growth condition on the 3rd-order derivative of the potential of target measures. This bound improves the best previously known Ô (4/e) result and optimal (in terms of order) in both dimension d and accuracy tolerance for target measures satisfying the aforementioned assumptions. Our theoretical analysis is further validated by numerical experiments.
start, under the common log-smooth and log-strou bog-strongly-come
INTRODUCTION
The problem of sampling statistical distributions has attracted considerable attention, not only in the fields of statistics and scientific computing, but also in machine learning (Robert & Casella al.] 2003 Liu (008); for example, how various sampling algorithms scale with the dimension of the target distribution is popular recent topic in statistical deep learning (see discussions below for references). For samplers that can be viewed as discretizations of SDEs, the idea is to use ergodic SDE whose equilibrium distribution agrees with the target distribution, and employ an appropriate numerical algorithm that discretizes (the time of) the SDE. The iterates of the numerical algorithm will approximately follow the target distribution when converged, and can be used for various downstream applications such as Bayesian inference and inverse problem (Dashti & Stuart 2017). One notable example is the Langevin Monte Carlo algorithm (LMC), which corresponds to an Euler-Maruyama discretization of the overdamped Langevin equation. Its study dated back least the 90s (Roberts al. 1996) but keeps on leading important discoveries, for example, on asympttttss and dimension dependence, which are relevant to machine learning (e.g.. Dalalyan 22017 b): Cheng et al.) (2018a); Durmus al. (2019) Durmus & Moulines (2019); Vempala Riou-Durann Durand (2020); Li et al. (2019): Erdogdu & Hosseinzadeh (e.g..Mandt alternative SDEs and/or different discretizations (c.g.. Dalalyan & Khou-Durand (2020); Ma et al. (202 I); Mou et al. (2021); Li et al. (2020): Roberts & ( (998); Chewi al. (2021): Shen & Lee (2019)).
& Wibisono (2019) Dalalyan & Riou-
(2021) y. Mou et al. (2019): Lehec (2021). )). LMC closely related to SGD too (e.g.. Mandt al.
(2017)). ). Many other examples exist, based
Rosenthal
Quantitatively characterizing the nom-asympoo sampling еттоr of numerical algorithms is usually critical for choosing the appropriate algorithm for specific downstream application, for providing practical guidance on hyperparameter selection and experiment design, and for designing improved samplers. A powerful tool that dates back to (Jordan et al. 1998) is paradigm of aompasympo

---

Published as a conference paper at ICLR 2022
error analysis, namely to view sampling as optimization in probability space, and it led to many
important recent results (e.g.. Liu & Wangl (2016); Dalalyan 2017a);; Wibisono (01 8); Zhang et al.
(2018); Frogner& & Poggio (2020): Chizat & Bach (2018); Chen al. (2018) ; Ma et al. (2021);
Erdogdu & Hosseinzadeh (2021)) It works by choosing an objective functional, typically some statistical distancces/divereenees and showing that the law of the iterates of sampling algorithms converges in that objective functional. However, the choice of the objective functional often needs to be customized for different sampling algorithms. For example, KL divergence works for LMC (Cheng & Bartlett 2018), but a carefully hand-crafted cross term needs to be added to KL divergence for analyzing KLMC (Ma et al.) 202T). Even for the same underlying SDE, different discretization schemes exist and lead to different sampling algorithms. and the analyses of them had usually been case by case (e.g.. Cheng et al. (20T8b); Dalalyan & Riou- Durand (2020); [Shen & Lee (2019)) Therefore, it would be desirable complement to have unified, general framework to study the non-asymptotic error of based sampling algorithms. Toward this goal, an alternative approach to analysis has recently started attracting attention, namely to resort to the numerical analysis of SDE
integrators (e.g.. Milstein& & Tretyakov (2013); Kloeden & Platen (1922) and quantitatively connect the integration error to the sampling error. One remarkable work in this direction is Li al. (2019).
which will be discussed in greater details later on.
The main tool of analysis in this paper will be a strengthened version (in specific aspects that will be clarified soon) of the result in Li et al. (2019). Although this analysis framework is rather general and applicable to a broad family of numerical methods that discretize contractivd"SSDE SDEs, the main innovation focuses on a specific sampling algorithm, namely LMC, which is widely used in practice. Its stochastic gradient version is implemented in common machine learning systems, such as Tensorflow (Abadi et al. 2016), and is the fff-the-shelf algorithm for large scale Bayesian inference. With the ever-grove ver-growing size of parameter space, the con-asymptotic error of LMC is of central theoretical and practical interest, in particular, its dependence on the dimension of the sample space.
The best current known upper bound of the mixing time in 2- Wasserstein distance for LMC is Ō (*)
DDurmus& & Moulines 2019). Motivated by a recent result (Chewi al. 2021) that shows better dimension dependence for Metropolis-Adjusted improvement of LMC, we will investigate if the current bound for (unadjusted) LMC tight, and not, what is the optimal dimension dependence.
Our contributions
The main contribution of this work is improved δ Vdl mixing time upper bound for LMC in
2- Wasserstein distance, under reasonable regularity assumptions. More specifically, we study LMC for sampling from Gibbs distribution du x exp (=f(w)) dx. Under the standard smoothness and strong-convexity assumptions, plus an additional linear growth condition on the third-order derivative of the potential (which also shares connections to popular assumptions in the frontier literature),
our bound improves upon the previously best known ① ( result (Durmus & Moulines, 2019)
in terms of dimension dependence. For a comparison, note it was known that discretized kinetic Langevin dynamics can lead to vd dependence on dimension (Cheng & Bartlett 2018 Dalalyan & Riou-Durand] (020) and some believe that it is the introduction of momentum that improves the dimension dependence, but our result shows that discretized overdamped Langevin (no momentum)
can also have mixing time scaling like vd. In fact, it is important to mention that recently shown was that Netropolis-Adjuste Euler-Maruyama discretization of overdamped Langevin (i.e., MALA)
has an optimal dimension dependence of Ô Vdd (Chewi et al. 2021), while what we analyze here is the unadjusted version (i.e., LMC), and it has the same dimension dependence (note however that our dependence is not as good that for MALA; more discussion in Section 4 We also
constructed an example which shows that the mixing time of LMC is at least Q2 VVa
Hence, our
mixing time bound has the optimal dependence on both d and e, in terms of order, for the family of target measures satisfying those regularity assumptions. Our theoretical analysis is further validated by empirical investigation of numerical examples.
A minor contribution of this work is the error analysis framework that we use. It is based on the classical mean-squar analysis (Milstein & Tretyakov 2013) in numerical SDE literature, however extended from finite time to infinite time. It is a minor contribution because this extension was
"possibly after a coordinate transformation
2

---

Published as a conference paper at ICLR 2022
already pioneered in the milestone work of Li et al. (2019), although we will develop refined version. Same as in classical mean-square analysis and in Li et al. (2019), the final (sampling in this case) error is only half order lower than the order of local strong integration error (p2). This will
lead to Ö (Cr=-a/e /
mixing time upper bound in 2- Wasseerstein distance for the family of
algorithms, where is a constant containing various information of the underlying problem, e.g.. the dimension d. Nevertheless, the following two are new to this paper: (i) We weakened the requirement on local strong and weak errors. More precisely. Li et al. (2019) requires uniform bounds on local errors, but this could be nontrivial requirement for SDE integrators; the improvement here only requires non-uniform bounds (although establishing the same result consequently needs notably more efforts, these are included in this paper too). (ii) The detailed expressions of our bounds are not the same as those in Li et al. (2019) (even if local errors could be uniformly bounded), and as we interested in dimension-deeenddnee of LMC, work out constants and carefully track their crimension-dependenece designed for tightly tracking dimension dependences, as the focus their seminal paper was more on e dependence; consequently, its general error bound only led to a Oddeddepenee in mixing time when applied LMC (see Example in Li et al. (2019). whereas our result leads O(vd).
Bounds and constants in Li et al. (2019) might not be specifically
2 PRELIMINARIES
Notation Use symbol æ to denote d-dim. vector, and plain symbol x to denote a scalar variable. |<||| denotes the Euclidean vector norm. A numerical algorithm is denoted by A and its k-th iterate by Tg. Slightly abuse notation by identifying measures with their density function w.r.t. Lebesgue measure. Use the convention O (.) O()) log (-) and S2 (-) 22() log ()) i.e., the Ô (-)/)())
notation ignores the dependence on logarithmic factors. Use the notation ?+-) similarly. Denote
E 2- Wasserstein distance by (2((),)2) = (inl(x,)) E - Y11)
& -
where IT( U2) is the set of couplings, i.e. all joint measures with X and Y marginals being μ1, and U2. Denote the target distribution by μ and the law of a random variable X by Law(X). Finally, denote the mixing time of an sampling algorithm A converging to its target distribution μ in 2- Wasserstein distance by Tiix (e; A) = inf (Ik 2 OJW2 (Taw (Taw(axx) (1) S e)-
SDE for Sampling
Consider a general SDE
dx. = b(t, at) + (t,
(1)
where b E Rd is drift term, a E Rdxl is diffusion coefficient matrix and B, is l-dimensional
Wiener process. Under mild condition (Pavliotis) 2014 Theorem 3.1), there exists a unique strong solution 2, to Eq. (.. Some SDEs admit geometric ergodicity, so that their solutions converge exponentially fast to a unique invariant distribution, and examples include the classical overdamped and kinetic Langevin dynamics, but not limited to those (e.g..Mouu Mou et al. (2021): Li et al. (2020). Such SDE are desired for sampling purposes, because one can set the target distribution to be the invariant distribution by choosing an SDE with an appropriate potential, and then solve the solution Ie of the SDE and push the time to infinity, so that (approximate) samples of the target distribution can be obtained. Except for a few known cases, however, explicit solutions of Eq. ( are elusive and we have to resort to numerical schemes to simulate/integrate SDE. Such example schemes include, but are not limited to Euler Marryaaa method, Milstein methods and Runge-Kutte method (e.g., Kloeden & Platen (1992); Milstein& & Tretyakov (2013)) With constant stepsize h and at k-th iteration, a typical numerical algorithm takes a previous iterate Tg-1 and outputs a new iterate T& as an approximation of the solution Φ; of Eq. [ at time & == kh.
Langevin Monte Carlo Algorithm
LMC algorithm is defined by the following update rule
a = - -M01--VV((2111 + V2h k = 1,2, ...
(2)
where (Ex)eez,o are i.i.d. standard d-dimensional Gaussian vectors. LMC corresponds to an Fuler- Maruyama discretization of the continuous overdamped Langevin dynamics dæ; = -V f / B,, which converges an equilibrium distribution f (x))-
3

---

Published as a conference paper at ICLR 2022
Dalalyan 2017b) provided a non-asymplotic analysis of LMC. An δ - mixing time bound in
W2 for log-smoothe and log-strongly-comme target measures (Dalal 201 7
Cheng et al.) 2018a
Durmus et al. 2019) has been established. It was further improved to O d under an additional
Hessian Lipschitz condition (Durmus & Moulines, 2019). Mixing time bounds of LMC in other statistical distancessddierrgences have also been studied, including total variation distance (Dalalyan)
2017b
Durmus & Moulines 2017) and KL divergence (Cheng & Bartlett 2018).
Classical Mean-Square Analysis A powerful framework for quantifying the global discretization error of a numerical algorithm for Eq. i..... ex = { ||at # is mean-square analysis (e.g.. Milstein & Tretyakov (2013)). Mean-square analysis studies how local integration error propagate and accumulate into global integration error, in particular, if one-step (local) weak error and strong error (both the exact and numerical solutions start from the same initial value x) satisfy
|| SCi (1 (1+ ((=e1))))))
E ET
IP" (local weak error)
E ||2 -000-aal ) SC₂ 1 + =1 $ hea (local strong error)
over a time interval [0, Kh] for some constants C₁, C2 > 0. p2 2 and 2 P2 + + then the
$ hP2
global error is bounded by ex C (10011))) dependent on Kh.
k == 1,,., K for some constant C' >>> 0
Although classical mean-square analysis is only concerned with numerical integration error, sampling error can be also inferred. However, there is a limitation that prevents its direct employment in analyzing sampling algorithms: the global error bound only holds in finite time because the constant C' can grow exponentially as K increases, rendering the bound useless when K - 00.
3 MEAN-SQUARE ANALYSIS OF SAMPLERS BASED ON CONTRACTIVE SDE
We now review and present some improved results on how to use mean-square analysis of integration error quantify sampling emror. A seminal paper in this direction is Li et al. (2019). What is known / new will be clarified. In all cases, the first step is to lift the finite time limitation when the SDE being discretized has some decaying property that local integration errors do not amplify with time.
The specific type of decaying property we will work with is contractivity (after coordinate transfor- mation). It is sufficient condition for the underlying SDE to converge to statistical distribution. Definition 3.1. A stochastic differential equation is contractive if there exists a non-singular constant matrix A E dddd constant 3 > O, such that any pair of solutions of the SDE satisfy
E |||A(x -
(ote---))))) u))l") < { (x - -)1i)) cxp(-3t).
(4)
where Tt, are two solutions, driven by the same Brownian motion but evolved respectively from initial conditions x and y.
Remark. As long as b and a in ( are not explicitly dependent on time, it suffices to find an arbitrarily small to > and show (4) holds for all < to-
Remark. Sometimes contraction is not easy to establish directly, but can be shown after an appro- priate coordinate transformation, see Daaaalan & Riou- (horanD 2020 Proposition 1) for such treatment for kinetic Langevin dynamics. The introduction of A permits such transformations.
In particular, overdamped Langevin dynamics, of which LMC is a discretization, is contractive when is strongly convex and smooth.
We now use contractivity to remove the finite time limitation. We first need a short time lemma.
Lemma 3.2. (Milstein & Treryakov 2013 Lemma 1.3) Suppose b and in EI Lipschitz
continuous. For two solutions Tt, yr of Eq. ① starting from x, respectively, denote z (x, y) :=
(x. x) (y: y). then there exist Co > 0 and he > 0 such that
E. (11 v) < Co ||= 1- Vx, y. 0 t S ho-
(5)
4

---

Published as a conference paper at ICLR 2022
Then we have sequence of results that connects statistical property with integration property. We will see that a non-asye -on-asymtooiic sampling eπror analysis only requires bounding the orders of local weak and strong integration errors (if the continuous dynamics can be shown contractive).
Theorem 3.3. (Global Integration Error, Infinite Time Version) Suppose Eq. ① is contractive with rate 3 and with respect to a non-singular matrix A E Bdxd, with Lipschitz continuous b and o, and there is a numerical algorithm A with step size h simulating the solution o; of the SDE, whose iterates are denoted by Tyg 0, 1,.... Suppose there exists 0 < hg S 1, C1, C2 > 0, D₁, D2 z O, Pr 2 1, 2 < P2 S P1 such that for any O < h S ha, the algorithm A has, respectively, local weak and strong error of order p1 and p2, defined as
B (on =1)] s
C1 (G++DVV DI DIVE hi:
(6)
E 1,0 21 2011p)
3 (02 D3E hp=
where Fh solves Eq. 1 with any initial value and कo is the result of applying A to x for one step.
If the solution of SDE and algorithm A both start from vo. then for 0 h h1 the global ervor ey is bounded as P2
min
hos 43
1
vB
P2
ek cx:= [BllERh -
SCh
k= =0,1,2,...
where
C1++ (2U + CoD2) + C2 + V2D.U
C= V3" AiA
(8)
VB
Co is from Eq. (5) KAA is the condition number of matrix A and U A 4E | 2 + 6E,, ||=0|
Remark (what's 's new). Thhm[3.3] refines the seminal results in Li et al. (2019) in the sense that it only requires non-uniform bounds the local error (6) whereas Li et al. (2079) requires uniform bounds, ie.. Dj = D2 = 0 in (6. Therefore, the refinement we present has wider applicability.
In general, local errors tend depend the current step's 's value, i.e. DI + 0, D2 + O. Allowing local error bounds to be non-unifon non-uniform enabled applications such as proving the vanishing bias of mirror Langevin algorithm (Li et al. [202]] For simpler illustration, consider LMC for 1D standard Gaussian target distribution, then we have
[T [Ex, - ăz)ll (e-h + h)R
2 + ohh One can see that the local error does depend on æ and is not uniform. Meanwhile,
our non-uniform condition still holds because (A22 2 + +oh2)) E||a||| S ( + o(h?)) / (and
thus p1 2). Note the discretization does converge to neighborhood of the target distribution, is possible that |2 and/or E.|a:|| become bounded near the convergence, and in this case the Dr. D2 parts can be absorbed into C1 and Cz; however, this 'if" clause exactly what we' 'd like to prove.
Nevertheless, we state for rigor that the convention 1/o= oc is used when D1 D2 = O. Another remark is, even this case, our bound has a different expression from the seminal results. We will carefully work out, track, and combine dimension ianeesioonddeeedeence of constants using our bound.
Following Theorem 3.3 we obtain the following non-asymptotic bound of the sampling error in Wz:
Theorem 3.4. (Non-Asymptotic Sampling Error Bound: General Case) Under the same assump- tion and with the same notation of Theorem 3.3 we have
Wy((aa(@x).H) p) < -8kh (Law(zo), 4)) + Ch
V0 < h S h1.
A corollary of Theorem 3.4 is bound on the mixing time of the sampling algorithm:
Corollary 3.5. (Upper Bound of Mixing Time: General Case) Under the same assumption and
with the same notation of Theorem 3.3 we have
1
1
20
P2-
2W, (Law (Zo). p.)
(ei 42 < max
log
3h1
3
5

---

Published as a conference paper at ICLR 2022
In particular, when high accuracy is needed, i.e., e < 20h/ we have
(2C)
2W (
(cm B
Timxx (c; -
log
(9)
B
1 cP2-3
Corollary 3.5 states how mixing time depends on the order of local (strong) error (i.e.. P2) of a numerical algorithm. The larger is. the shorter the mixing time of the algorithm is, in term of the dependence on accuracy tolerance parameter c. is important to note that for constant stepsize discretizations that are deterministic on the filtration of the driving Brownian motion and use only its increments, there is a strong order barrier, namely P2 S 1.5 (Clark & Cameron 1980 Rüemelin 1982); however, methods involving multiple stochastic integrals (e.g.. Klooden & Platen (992);
Milstein & Treryakov (2013); Rööler (2010)) can yield a larger P2, and randomization (e.g., Shen &
Lee (2019) can possibly break the barrier too.
The constant C defined in Eq. 7 typically contains rich information about the underlying SDE, c.g. dimension, Lipschitz constant of drift and noise diffusion, and the initial value Do of the sampling algorithm. Through C, we can uncover the dependence of mixing time bound on various parameters, such the dimension d. This will be detailed for Langevin Monte Carlo in the next section.
is worth clarifying that once Thm 333 is proved, establishing Theorem 3.4 and Corollary 3.5 is relatively easy. In fact, analogous results have already been provided in Li al. (2019), although they also required uniform local errors as consequences of their Thm. 1. Nevertheless, we do not claim novelty in Theorem? 3.4 and Corollary 3.5 and they are just presented for completeness. Our main refinement is just Thm 3.3 over 1 in Li et al. (2119) and the non-triviality lies in its proof.
4 NON-ASYMPTOTIE ANALYSIS OF LANGEVIN MONTE CARLO ALGORITHM
We now quantify how LMC samples from Gibbs target distribution 1 ~ exp (=)()) that has a finite second moment, i.e., fae ||=l| du < Assume without loss of generality that the origin is a local minimizer of f. i.e. Vf(0)= = O: this is for notational convenience in the analysis and can be realized via simple coordinate shift, and it is not needed the practical implementation. In addition, we assume the following two conditions hold:
1. (Smoothness and Strong Convexity) Assume f C2 and is L-smooth and m-strongly-conver. i.e. there exists 0 < m S L such that mJa- < V < Lla, Va E Rd.
Denote the condition number of f by & L. The smoothness and strong- assumption is the standard assumption the literature of analyzing LMC algorithm (Dalalyan 2017a Cheng & Bartleu 2018; Durmus et al., 2019: Durmus & Moulines) 2019).
2. (Linear Growth of the 3rd-order Derivative) Assume f E C and the operator ((Af) grows at most linearly, ie., there exists constant G > such that [(AA(())) s (1 |=]l)-
Remark. The linear growth (at infinity) condition on A is actually not as restrictive as it appears, and in some sense even weaker than some classical condition for the existence of solutions to SDE. For example, a standard condition for ensuring the existence and uniqueness of a global solution to SDE is at most a linear growth (at infinity) of the drift (Pavliotis) 2014 Theorem 3.1). If we consider monomial potentials, i.e., f(x)= = =x² . E N4, then the linear growth condition on V is met when p S whereas the classical condition for the existence of solutions holds only when p S 2.
Remark. Another additional assumption, namely Hessian Lipschitz, condition, is commonly used in the literature (e.g., Durmus& & Moulines (2019); Ma et al. (2021)). )) requires the existence of a constant L, such that [ - L x1|. It can be shown that smoothness and Hessian Lipschitzness imply A2 Meanwhile, examples that satisfy 42bu are not Hessian Lipschitz exist, e.g.. fx) z², and thus 12 not necessarily stronger than Hessian Lipschitzness.
Remark. Same as L and m in A7 we implicitly assume the constant G introduced in A2 be independent of dimension. Meanwhile, it is important note examples for which G depends on the dimension do exist, and this is also true for other regularity constants including not only L and m but also the Hessian Lipschitz constant L. This part of the assumption is a strong one.
Remark. AZ together with Ito's lemma, helps establish an order pt of local weak error for LMC (see Lemma D.2b, which enables us obtain the Vd dependence.
6

---

Published as a conference paper at ICLR 2022
To apply mean-square analysis to study LMC algorithm, will need to ensure the underlying Langevin dynamics contractive, which we verify in Jection/Candll work out all required constants determine the C' in Eq. [xxphiity in the appendix. With all these necessary ingredients, we now invoke Theorem 3.4 and obtain the following result:
the appendix. In addition,
Theorem 4.1. (Non-Asymptotic Error Bound: LMC) Suppose Assumption 1 and hold. LMC
iteration #s+1 = 3g hV f(*)) + 22hx, satisfies
1 KEN 4xL
(V((Law(=x)).) Se -mhh W2 (Vaw(Lw))))))) (D) Cluch,
0 0<
(10)
where CLMC 10(22+G)
/ 2d
[ [B|aza 1| + 11 = O(va).
Corollary 3.5 combined with the above result gives the following bound on the mixing time of LMC:
Theorem 4.2. (Upper Bound of Mixing Time: LMC) Suppose Assumption 7 and hold. If running LMC from Vo, we then have
2CLMC 1 4x
2W 2W2(Law(Zo):1)
Tmix (e: W2; LMC) & max
log
m
6
where CLMC is the same in Theorem 4.1
When high accuracy is needed, i.e. S
we have 2mx
CLace
2CIMC
1
2 =Ō Vdl
Tiix (e: LMC)
I
log
m
E
The δ vd
mixing time bound in W2 distance improves upon the previous ones (Dalalyan 2017 7
Cheng & Bartlet 2018 Durmus & Moulines 2019 Durmus et al. 2019) in the dependence
and/or c. If further assuming G (I.²), we then have CLMC = O /my/ d) and Thm 4.2 shows
the mixing time Ö
Vd
which also improves the x dependence some previous results
Dallalan 2017a Cheng & Bartleti 2018) in the m S regime. A brief summary is in Table
Table 1: Comparison of mixing time results in 2- Wassertein distance of LMC with L-smooth and m--trrogglycoonvex potential. Constant step size is used and accuracy tolerance is small enough.
mixing time
Additional Assumption
Dalalyan 2017a
Theorem 1)
x²
N/A
m
Cheng & Bartlet
2018
Theorem
①
A²
N/A
m
Durmus et al.
2019
Corollary 10)
0
N/A
m
DDumuus & Moulines,
2019
Theorem 8)
2 f(x)
V2 f(y)) < L |
yl
This work (Theorem 4.2
Ld
Assumption 2 and G O(L2)
vmm
Remark (more comparison). The seminal work of Li et al. (2019) provided mean-square analysis (their Thm.1) and obtained Ö { mixing time bound for LMC (their Example 1) under smoothness, strong convexity and Hessian Lipschitz conditions, consistent with that in Durmus & Moulines (2019). By using our version (Thm 3.3 and tracking down constants' dimension- dümension-deeendencee dependeece, we are able to tighten it to Ö Vd Worth clarifying is, dimension- dependdeee might not be the focus of Li et al. 2019); instead, considered e- --dependence and other discretizations, and showed for example that 1.5 SRK discretization has improved mixing time bound of δ 2:3 The dimension dependence of this discretization, for example, can possibly be improved by our results too.
'The dependence on x is not readily available from Theorem in Durmus & Moulines 2019
Thh G = (I.²² assumption is only for x, m dependence. Removing it doesn't i affect d, e dependence.
7

---

Published as a conference paper at ICLR 2022
Optimality In fact, the δ Vd
mixing time of LMC has the optimal scaling one can expect. This in terms of dependence d and e, over the class of all log-smooth and fog-strongly-convex target measures. To illustrate this, consider the following Gaussian target distribution whose potential is
d
2d Σ
m = 2 ==1
f(æ)
with m 1, 2 4m.
(11)
x=++1
We now establish a lower bound on the mixing time LMC algorithm for this target measure. Theorem 4.3. (Lower Bound of Mixing Time) Suppose
LMC for the target measure defined in Eq. from Th = 12d, then for any choice of step size h >> 0 within stability limit, we have
Vd Vd
d
Tmix (E; W2; LMC)
2
log
8
Combining Theorem 4.2 and 4.3
we see that mean- square analysis provides a tight bound for LMC is the optimal scaling of LMC for target measures satisfying Assumptions and
and ① Vd
Note that the above optimality results only partially, but not completely, close the gap between the upper and lower bounds of LMC over the entire family of log-smooth and log-stronglyyconver target measures, because of one limitation of our result- - A(ssumption) 2 is. despite of its close relation to the Hessian Lipschitz condition frequently used in the literature, still an extra condition. We tend to believe that A2 may not be essential, but rather an artifact of our proof technique. However, at this moment we cannot climinate the possibility that the best scaling one can get out of Assumption ! only (no A2 is worse than Ö (vd/e).
We'd like to further investigate this in future work.
Discussion Besides Li et al. (2099) (see the previous Remark), let's briefly discuss three more important sampling algorithms related to LMC. Two of them are Kinetic Langevin Monte Carlo (KLMC) and Randomized Midpoint Algorithm (RMA), both of which are discretizations of kinetic Langevin dynamics. The other is Metropolis-Adjuste Langevin Algorithm (MALA) which uses the one-step update of LMC as a proposal and then accepts/rejects it with Metropolis Metropolis-Hastinnss.
The δ v mixing time in 2- 2-Wasserttein distance of KLMC has been established for log-smooth
and log-strongly-coree convee target measures in existing literature (Cheng et al.) 2018b) Dalalyan & Riou- Durand, 2020) and that was milestone. Due to its better dimension dependence over previously best known results of LMC, KLMC understood to be the analog of Nesterov's accelerated gradient method for sampling (Ma et al. T02T). Our findings show that LMC is able to achieve the same mixing time, although under an additional growth-at-infinigg condition. However, this does not say anything about whether/how KLMC accelerates LMC, as the existing KLMC bound may still be not optimal. We also note KLMC has hetter condition number dependence than our current LMC result, although the dependence in bound may not be tight.
RMA (Shen& & Lee 2019) is based on a brilliant randomized discretization of kinetic Langevin dynamics and shown to have further improved dimension dependence (and other pleasant properties). From the perspective of this work, we think it is because RMA is able to break the strong order barrier due to the randomization, and more investigations based on mean- -quare analysis should be possible.
For MALA, a recent breakthrough (Chewi et al. 2021 establishes Ö (vd) mixing time in W2
distance with warm start, and the dimension dependence is shown to be optimal. We see that without the Metropolis adjustment, LMC (under additional assumptions such A2) can also achieve the same dimension dependence as MALA. But unlike LMC, MALA only has logarithmic dependence on L. With warm-start, it possible/how improve the dependence of for LMC,, from polynomial to logarithmic? This question is beyond the scope of this paper but worth further investigation.
5 NUMERICAL EXAMPLES
This section numerically verifies our thcoretical findings for LMC in Section 4 with a particular focus on the dependence of the discretization enror in Theorem 4.1 4.Ton on dimension d and step size h.
8

---

Published as a conference paper at ICLR 2022
To this end, we consider two target measures specified by the following two potentials:
Ji (x) - || + log
Σ 1=1
e
and f2(2) - 22 ||00|
cos (diz:).
(12)
2d
==1
It is not hard to see fi is 2-smooth and 1-strongly convex, f2 is -smooth and 1-strongly-convex and both satisfy Assumption 2 fz is also used in (Chewi et al. 2021 to illustrate the optimal dimen- sion dependence of MALA. Explicit expression of 2- 2-Wasserstein distance between non-Gaussian distributions is typically not available, instead, we use the Euclidean norm of the mean error as surrogate because | 1 I WL(Law(#x),
due to Jensen's inequality. To obtain an accurate estimate of the ground truth, run 10t independent LMC realizations using tiny step size (h = 0,001), each till a fixed, long enough time, and use the empirical average to approximate a,,.v.
To study the dimension dependence of sampling error, fix step size h 0.1, and for each E {1,2, 5, 10, 20, 50, 100, 200, 500, 1000), we simulate 10 independent Markov chains using LMC algorithm for 100 iterations, which long enough for the chain to be well-mixed. The mean and the standard deviation of the sampling error corresponding to the last 10 iterates are recorded.
To study step size dependence of sampling error, fix d 10 and experiment with step size E 2,, 3, 4, 5, 6, 7,8, 8,9, 10} x 10-1 We run LMC till T = 20, i.e., [ iterations for each h. The procedure is repeated 10a times with different random seeds to obtain independent samples. When the corresponding continuous time kh > 10, we see from Eq. (TO) that LMC is well converged and the sampling error is saturated by the discretization error. Therefore, for each h, we take the last iterates and record the mean and standard deviation of their sampling error.
llf X Kla
olval
Kla
O(vd)
O(h)
4.00
O(h)
LMC
LMC
LMC
LMC
case
Euu X
Dimension 17
Dimension
127
Step
Step size
(a) fa: d dependence
(b) f2: d dependence (c) fi: / dependence
(d) fz: h dependence
Figure 1: Dependence of the sampling егrог of LMC on dimension d and step size h for f1 and fz- Both axes in Fig Ta Th are log scale. Shaded areas in Fig Ta & Tb represent one std. of the last 10 iterations. Shaded areas in Fig Ic & represent one std. of the last 1o iterations.
Results shown in Fig 1 are consistent with theoretical analysis of the sampling error. Both linear dependence Vd and can be supported by the empirical evidence. Note results with smaller h less accurate because one starts to see the error of empirical approximation due to finite samples.
6 CONCLUSION
Via refined mean -quare analysis of Langevin Monte Carlo algorithm, obtain improved and optimal δ (va%.) bound on its mixing time, which was previously thought to be obtainable only with the addition of momentum. This was under the standard smoothness and strongly-convexin assumption, plus an addition linear growth condition on the third-order derivative of the potential function, similar to Hessian Lipschitz condition already popularized in the literature.
Here some possible directions worth further investigations. (i) Combine mean-square analysis with stochastic gradient analysis to study SDE-based stochastic gradient MCMC methods; (ii) Is still possible to obtain v /d-dependence without A2 i.e., only under log-smooth and log-strongly- convex conditions? (iii) Applications of mean-
analysis to other SDEs and/or discretizations; (iv) Motivated by Chewi et al. (2021). it would be interesting to know whether the dependence on can be improved to logarithmic, for example if LMC is initialized at warm start.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors thank Andre Wibisono, Chenxu Pang, anonymous reviewers and area chair for suggestions that significantly improved the quality of this paper. MT was partially supported by NSF DMS- 1847802 and CCCS-1136776. This work was initiated when HZ was a professor and RL was a PhD student at Georgia Institute of Technology.
REFERENCES
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: system for large-scale machine learning. In / /2th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pp. 265-283, 2016.
Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael I Jordan. An introduction to meme for machine learning. Machine learning, 50(1):5-43, 2003.
Changyou Chen, Ruiyi Zhang, Wenlin Wang, Bai Li, and Liqun Chen. A unified framework for scalable bayesian sampling. In The Conference on Uncertainty in Artificial Intelli- gence, 2018.
Xiang Cheng and Peter L Bartlett. Convergence of langevin meme kl-divergence. PMLR 83, (83): 186-211, 2018.
Xiang Cheng, Niladri S Chatterji, Yasin Abbasi- Yadkori, Peter L. Bartlett, and Michael I Jor- dan. Sharp convergence rates for langevin dynamics in the nonconvex setting, arXiv preprint arXiv:1805.01645 2018a.
Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped langevin meme: A non-asymptotic analysis. Proceedings of the 31st Conference On Learning Theory, PMLR, 2018b.
Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. Optimal dimension dependence of the metropolis metropolis-adjusted adjusted langevin algorithm. COLT, 2021.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. In Advances in neural information processing systems, pp. 3036- 3046, 2018
John MC Clark and RJ Cameron. The maximum rate of convergence of discrete approximations for stochastic differential equations. In Stochastic differential systems filtering and control, pp.
162-171. Springer, 1980.
Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. Conference Learning Theory, pp. 678-689, 2017a.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and lon-cve densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 79(3): 651-676, 2017b.
Arnak S Dalalyan and Lionel Riou-Durand. On sampling from log-concave density using kinetic Langevin diffusions. Bernoulli,
2020.
Masoumeh Dashti and Andrew M. Stuart. The Bayesian Approach Inverse Problems, pp. 311 111- 428. Springer International Publishing, Cham, 2017. ISBN 978-3-319-12385-1 doi: 10. 1007/ 978-3-319-123855 7.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. Annaly of Applied Probability, 15531175 2017.
10

---

Published as a conference paper at ICLR 2022
Alain Durmus and Eric Moulines. High- High-dimensional bayesian inference via the unadjusted langevin algorithm. Bernoulli, 25(4A):2854-285) 2882, 2019.
Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis of langevin monte carlo via
convex optimization. Journal of Machine Learning Research, 20:73-1, 2019.
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of langevin monte carlo: The interplay between tail growth and smoothness, COLT, 2021.
Charlie Frogner and Tomaso Poggio. Approximate inference with wasserstein gradient flows. In International Conference on Artificial Intelligence and Statistics, 2020.
Richard Jordan, David Kinderlehrer, and Felix Out. The variational formulation of the fokker-planck equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
Peter E Kloeden and Eckhard Platen. Numerical solution of stochastic differential equations. Springer, 1992.
Joseph Lehec. The langevin monte carlo algorithm the non-smooth log-concave case. arXiv preprint arXiv:2101.10663 2021.
Ruilin Li, Hongyuan Zha, and Molei Tao. Hessian-free high-resolution nesterov acceleration for sampling. arXiv preprint arXiv:2006.000 09230, 2020.
Ruilin Li, Molei Tao, Santosh S Vempala, and Andre Wibisono. The mirror langevin algorithm converges with vanishing bias. arXiv preprint arXiv:2109.12077 2021.
Xuechen Li, Denny Wu, Lester Mackey, and Murat A Erdogdu. Stochastic Runge-Kutte accelerates Langevin Monte Carlo and beyond. NeurIPS, 2019.
Jun S Liu. Monte Carlo strategies in scientific computing. Springer Science & Business Media, 2008.
Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in neural information processing systems, pp. 2378 2386, 2016.
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. doi: 10.3150/20-B BE2200-.-
Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1-35, 2017.
Grigori Noah Milstein and Michael Tretyakov. Stochastic numerics for mathematical physics.
Springer Science & Business Media, 2013.
Wenlong Mou, Nicolas Flammarion, Martin J Wainwright, and Peter L Bartlett. Improved bounds for discretization langevin diffusions: Ncar-optimal rates without convexity. arXiv preprint arXiv:1907.11331 2019.
Wenlong Mou, Yi-An Ma, Martin J Wainwright, Peter L Bartlett, and Michael Jordan. High-order langevin diffusion yields an accelerated meme algorithm. Journal of Machine Learning Research, 22(42):1 2021.
Grigorios Pavliotis. Stochastic processes and applications: diffusion processes, the Fokker-Planck and Langevin equations, volume 60. Springer, 2014.
Christian Robert and George Casella. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
Gareth Roberts and Jeffrey S Rosenthal. Optimal scaling of discrete approximations to langevin diffusions. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 60(1): 255-268, 1998.
Gareth O Roberts, Richard L Tweedie, et al. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363, 1996.
11

---

Published as a conference paper at ICLR 2022
Andreas Rößler. Runge kutta methods for the strong approximation of solutions of stochastic differential equations. SIAM Journal on Numerical Analysis, 48(3):922-95,, 2010.
W Rüemelin. Numerical treatment of stochastic differential equations. SIAM Journal on Numerical Analysis, 19(3):04-611,, 1982.
Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems, pp. 2098-2100 2019.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, pp. 6092-8104, 2019.
Andre Wibisono. Sampling optimization in the space of measures: The langevin dynamics composite optimization problem. In Conference On Learning Theory, pp. 2093-3027, 2018.
Ruiyi Zhang, Changyou Chen, Chunyuan Li, and Lawrence Carin. Policy optimization as wasserstein gradient flows. In International Conference on Machine Learning, pp. 5737-5746, 2018.
12

---

Published as a conference paper at ICLR 2022
A PROOF OF RESULTS IN SECTION 3
A.1 PROOF OF THEOREM 3.3 (GLOBAL INTEGRATION ERROR, INFINITE TIME VERSIoN)
Proof. We write the solution of an SDE by Fta. (lo + t) when the dependence on initialization needs highlight. Denote fx = kh and Dt2- = 2 for better readability.
We will first make easy observation that contraction and bounded 2nd- mad-moment of the invariant distribution lead to bounded 2nd-moment the SDE solution for all time: let yo be random variable following the invariant distribution of Eq. 1 i.e., Yo ,4, then y, ja and
E x
11
22E
V,
2E 11
<2E
DD Yoll exp( 25t) + 2E |//l
<4B [|zo + 11 12) exp( + 2E 1 11
44 |col| exp( 2336) + (2 4xp( Ey ||
<BB | 2 / || du & U²
and then it follows that
E |xx|l 1 < 21E | æx11 + 21E | s 2E + 2
(13)
Denote (x. y) (Ax, Ay). | ||Ax/|| and
- =x1 1/2
(14)
where A is the non-singular matrix from Equation (4). Also denote that largest and smallest singular values of by maax and mins respectively, and the condition number of by KA umin
dmax
Recall
Ex = E ar - #xll. easy to see that
Mmin Ek S fx maaxkk.
(15)
Further, we have the following decomposition
0x+1 $x+1ll 1 12
Dea Din m (lx+1) Tte an (1++1) + ar mz (1++1) Be++ |
E
De (t641) Dtc. an (tx+1) 11
+ p as (f++1) Dz+1 13
= E
(16)
+ 2 (EAA Dannsryy (1x+1) - Bty s (1a+1)) A (wr, (lx+1) - xk+1))
Term 1 is taken care of the contraction property
12 A
E
De (tx+1) - Des (t++1)
5 f2 exp(-28h).
(17)
Term dealt with by the bound on local strong error
Dr (1++1) - Tx 112 < o (c+ + +DDBB xx.13²) 1,2ps
(18)
13

---

Published as a conference paper at ICLR 2022
Term 3 requires more efforts cope with, and by the decomposition in Eq. we have
B( ar (1k+1) az (tx+1); Tt2. (t++1) I*+1)A
-B Tk Vie des (1++1) - xf++) A + (2 (1yss Fx), , Bee. (1x+2) #x+1)A
@ (xx Ds. Blare, on (1++1) t + FRl) A + IB (2Es BR), Be (1x+1) - xx++1)
(40)
S fk [E El (tR+1) Tx++1 Fis ((a) 3/ + E (z)) +x)) (E 10 (tx+1) xx+1 (1a)
(6))
+ max (R||zA ( tx )13) (R. 1llesen (1x+1) B 1|/²)
[E EE (lx+1) Tetil 1
I maxxs
(10)
I mmaxfx (G- DIV h + Ma
C2 + D2y D2y
E | 1
(0)
S max (C1 + CoC2)egh + KAA (D1 + CoDD) E | I1 fih
(19)
where (1) uses the tower property of conditional expectation and F& is the filtration at k-th iteration, (it) uses Cauchy-Schward inequality, (λε)) is due to the relationship between eg and fk. (tv) is due to local weak error, local strong error and Eq. (5), and (v) is due to 2 p2 + and 0 < h S ho S 1.
Now plug Eq. 17
18) and 19 in Eq. 16), obtain
Fuz SK exp( 1 28h) + max
(C2 D T 11²)
22 + max + CaC))aahtt
+ KAAmaxx (D1 + CoD2)
E | | fuh
2 1 -
7 31)
R + o
1m2 + KAA + CGC3))ahhhtt (c2 + D|3Bl
+ m (D1 + CoD2)
E " fah
(1))
7 8h) Ph + KAATux (c: + CoC2 22U(D) + + fih 22ffhmn
1 - 8
(D1 (D + foD to (c2 22322)) 2,222
(80)
7
f + KATmax (C+ CCI+ + (D) + CoDz)) fal 38
1 $
8h
8 fhh
+ σ umxx
(02
+ +233U2 1222
1
f2 + KKA (C1+ (C1+C0C2 + 22U + +GDD2) fah
1
8h
2
+ -
(C² + 223 1222
R3 o (cI C,C2 + (2 + CoD2)) 2 122p2
((u)
1 1 Bh
f2 + 7 p +
2
B
+ σ nax
(02 + 223 1222
(2U (G++C02+V22UU), (D(DDiCCooD) CoDD))²
= 1 4 Bh f2 + 22
+3 + 2D3U22
1222
B
where (i) is due the assumption 0 h <
1 and e- < 1
2 for < x
43
(wi) is due to the upper bound on | in Eq.
(13 (iil) holds provided when h <
14

---

Published as a conference paper at ICLR 2022
min ity.
P2
8
22 2
and (iv) is due to Cauchy-Schwarz inequal-
(D)
Unfolding the above inequality gives us
(G (G+ CbC2 (2U(D) V2U ( +oDD)) +02 2D222 h2pa-1
4 Am200 fett S nniioiax
B
Taking square root on both sides and using v Va² + 5a V yields
fk+1 S
vB KA
2
maxx
Ci C C CoC2 + 22U CoD2)
C2 + V2DzU AP-
vB
Finally using the relationship between eg and fk. obtain
2
C1 (1+ CoC2 + /2 V2+ CoD2)
+C2 + v2DgU 122
/B RA
vB
A.2 PROOF OF THEOREM 3.4 NYON-SYYPPOOTH SAMPLING ERROR BOUND: GENERAL CASE)
Proof. Let Yo ~ μ and (æo, Yo) are coupled such that TE || yoll2 W (Law (xa)) Denote the solution of Eq. [1 starting from zo. Yo by Tt. U, respectively, and l kh. We have
Wa(Law(Tx), 1)) <W2 (Law( (Tx)) Law(xr),) + (2(
S - xta 11
|000 xe. ycc
Sc + 11:0 yoll exp (-23tk) =6 + exp (-Sta) W2 (Law(x))) 14)
where (i) is due the contraction assumption Eq. completes the proof.
1 Invoking the conclusion of Theorem 3.3
A.3 PROOF OF COROLLARY 3.5 (UPPER BOUND OF MIXING TIME: GENERAL CASE)
Proof. Given any tolerance > 0, we know from Theorem 3.4 that if & large enough and is
small enough such that
exp (-
(-kh)) 3kh) (LaWaa(D)).)) S 2
(20)
Ch <
(21)
we then have (Z)La)(Z;),.)) < Solving Inequality 20 yields
2Wz (Wawa((z))).)) & k*
2W
k z 3h log
(22)
To minimize the lower bound, we want pick step size as large as possible. Besides h S h1, Fq. poses further constraint on h, hence we have
P2-
h < min
h1,
20
15

---

Published as a conference paper at ICLR 2022
Plug the upper bound of h in Eq.
22 have
1
2C
P2
2W₂ (Law(zo),
k- max
log
Bh1²
c
When high accuracy is needed, i.e.,
2Ch1 po
& have
k- (20)
P2
2W₂ (Law(zo).
(
log
3
E P2
B PROOF RESULTS SECTION 4
B. PROOF THEOREM COON-ASYPPOOTIC ERROR BOUND: LMC)
Proof. From Lemma C.I know that Langevin dynamics is member of the family of contractive SDE, and with a contraction rate of strong-convexity coefficient / = m (w.rt. identity matrix Taxa).
Next, will need to work out the constants Co; C1, D1, D2, C2 needed in Theorem 3.3
We have
Co 2 implied from Lemma C.3
The local strong error and local weak error are bounded in Lemma D. and D.2 respectively. Note that the coefficient C₁/C₂ in the bound for local strong/weak error depends initial value, which changes from iteration to iteration. Combined with Lemma D.3] we would obtain C1 and C2, namely
Č s 22(2+++
( 4xL
d + |00l1 + 7m
8d
+1)
s 22( + +2(L²+ +VV
2d m
+ E |20 ? + Ci
and
1/4
C2 s 2L
d + m
E
[
8d
2d 2L 2L
+ E ||co 12 + C2.
7m
We collect all constants here in the proof for easier reference
1 4k
Co v m
= Taxd: KA = 1,8= = m, ho
2
G = 2(I2 + v)y 2dd
+ E |xclo|
+ 1, D1 =
m
2d
C = 21
+ E |00l 2 +1, D2 = 0.
m
Then the constant in Theorem
3.3
LMC algorithm simplifies to
2
C1+ C6C2 c.).
C
VB
VB
10 + G)
2d
(R 1x00 +1) CINC-
m
Assuming L, m. G are all constants and independent of d, then clearly CLMC O(Vi). Then applying Theorem 3.4 LMC, we have
Wg(Law(zx). 4) Se- -mkh (LLW((EZ))))) u)) CiMch
(23)
for 0 < h < T.I
n
16

---

Published as a conference paper at ICLR 2022
B.2 PROOF OF THEOREM 4.3 (LOwER BOUND OF MIXING TIME)
Proof. If we start from
12d and run LMC for the potential function in Eq.
we then have
(1 (x0) + 2h (1-111-mmpp
(1- 1 isisd
(ax) =
(1
22h (1- d+ 2d
and hence
N (1 mh)*
mm(2-mh) (1- (1 (1-(1=hh)2n)
2
mh)22) isisd
(Ix);
N (11 Th)* LA] (h)aa))) d+lsis 2d
2
Clearly, stability requires h < -.
The squared 2- 2-Wasserstein distance between the law the k-th iterate of LMC and target distribution is
2
(Law(())) =d(1 - m/)33k +
1/2 mh V (1 ml)22 -
2
+d(1 Lh) + Lh V (1 -h)22 1)
Suppose W₂ Wa(Law(āxs, 1) S e, we then must have
d(1 mh) 2k sea
(24)
2
V2 2 mh
(1 - mh)2k -
SE?
(25)
m
A necessary condition of Eq.
25 is that
+
V
2
V 11-111mm
mh)22
(1)
2 mhh V
2
2²
(26)
Vd
mh
where (i) is due to Eq.
24 It follows from Eq.
26 and
that
4e
(27)
Vd
Vd
Revisiting Eq. 24 yields
26
(1)
(2mh)²
(18)
2 d(1
mh)2k
2
2mh +
2 de- Ambh
1 log
Vd
(28)
2hm
where (1) is due to mh
<
2 and (ii) due to 6- 11 x
2 < 11
Combine Eq. 27 and
28 we then obtain lower bound of the mixing time
Vd 8mc
Vd
Vd Vd
Vd
log
log
8c
17

---

Published as a conference paper at ICLR 2022
C SOME PROPERTIES OF LANGEVIN DYNAMICS
C.I CONTRACTION OF LANGEVIN DYNAMICS
Lemma C.1. Suppose Assumption Thols. Then two copies of overdamped Langevin dynamics have the following contraction property
E lv. -0-12=111)
x0ll3]
E 1ly 2]12] exp(-mt)
where are the initial values of xe, Vr-
Proof. First assume æ, y deterministic. Suppose æt, Mr respectively the solutions
dx, f(,))) + V2dB
dy. = dt + v2dB
where B, is standard d-dimensional Brownian motion. Denote L. = JE ||y, x.1l² and take time derivative, obtain
d L, = -Ey, Tt. Vf((,) fmx))) 2 -m AmmE/. - x2112 2 dt
where (i) is due to the strong-convexity assumption made f. We then obtain L. S Lo eexp(22mb) and it follows by Gronwall's inequality that
x=1l2]
E y.
zell s ly
x exp( -mt).
When æ. y are random, by the conditioning version of the above inequality and Jensen's inequality, we have
1
E 1 x01 eexp(=2mm) }&8
E El1 x1|²} & exp(-mt).
E
E
y:
zel12
x.
C.2 GROWTH BOUND OF LANGEVIN DYNAMICS
Lemma C.2. Suppose Assumption 7 holds, then when 0 < h < Langevin dynamics æ, satisfies
ANT the solution of overdamped
1
x < 6((2+ m 1|]1) h
E 2
where x is the initial value at f 0.
18

---

Published as a conference paper at ICLR 2022
Proof. We have
(xt + V2 L dB.
Tb x=|² =E
hh dBB
<2B
V VS(ax)
+ +4B
(1 2E
Vf(xs)
+ +hh
27
[V[(())) V di + /''' |
<2R
4hd
<2E
L || - x=|| + ++][(((())]]
+ 4hd
L %0 ||0, x dt 1² [
41
4hd
(16)
/" TE ox x= dt
- 4hd + 4
[=<))] + +1.2%
where (i) is due Ito's isometry, (ii) is due to Cauchy- Scwwarw By Gronwall's inequality, we obtain
ar 2²1² S 4h d ME [(()))] exp {1L21)).
Since | = [x(x) [S(0)) < T. ||=/|| when 0 < h S ant. we finally reach at
1
((at
E | x 4 (a+ |<=) h 6 d mh
E |,21(²) h.
2
C.3 BOUND ON EVOLVED DEVIATION
Lemma C.3. Suppose Assumption T holds. Let 24, V, be two solutions of overdamped Langevin
dynamics starting from x, y respectively, for TeI. we have the following representation
Un = +
with
E ||12| I m
E || 2112 h.
4
Proof.
Let x
(xh
4%h)
(x 3) 0o Vf(x.) ff(y,)ds Ito's lemma readily implies
that
yn 12 =E x y1 2E
(x. V. vf(x.) V (yy.))ds
Jn
E x vI 2 2m
E [ v.1l ds
<
x yll 2
19

---

Published as a conference paper at ICLR 2022
where (1) is due to strong-conveent ctonei-covvxxity of f. We then have that
E ||
(f(x)s) V.
B (((x.)) - vf(va)] ds
1s
18 [V]((z))) vf(y.)] ds
<h
E V - vf(y,)11* ds
LE 1111,, 121l" ds
<LP ||00 yl 211 1/
(1 m
$ E x y h
4
where (1) is due to h S aNT.
I
D SOME PROPERTIES OF LMC ALGORITHM
D.1 LOCAL STRONG ERROR
Lemma D.1. Suppose Assumption holds. Denote the one-step iteration of LMC algorithm with step size h by Tn and the solution of overlamped Lungevin dynamics at time = h by Th- Both the discrete algorithm and the continuous dynamics start from the same initial value x. If0 S S akL. then the local strong error LMC algorithm satisfies
E |1= - mm1l2] - CCh
with E₂ = 2T d + m T 11)))
Proof. We have for 0 < h <
1
Int.
11 =F // [((x))) V ((()ds
E
|
<
|| V[(x)) vf(x) ds
1.PE
||ar - arl ds
(1)
E
||ac, 2012 ds
(6)
3LL
d++ m E ||00| 3
2
where (i) is due to Cauchy-Schree Schwartz inequality and (ii) is due to Lemma C.2 on both side completes the proof.
Taking square roots
20

---

Published as a conference paper at ICLR 2022
D.2 LOCAL WEAK ERROR
Lemma D.2. Suppose Assumption andd hold. Denote the one-step iteration of LMC algorithm with step size h by 3n and the solution of overdamped Langevin dynamics at time I = h by wh- Both the discrete algorithm and the continuous dynamics start from the same initial value x. If 0 S h S s then the local weak error of LMC algorithm satisfies
hold.
| Exa. S G₂h²
with = + G) ()(G)) TAL + B + +1)
Proof.
By Ito's lemma, have
fV:() -V==--V/( //aa/// +/2 1 VeJ(a)))B.
It follows that
|aa Exr
E
-V/ + v2 f L ('V'fca))dBBds
E
1
E
/
/ //) / E [[((Af(x))))
E
drds+ +
drds
30
drds + 1/² J E ([V(((() drds
17 9
E E
(
| drds G h2
(I2 G)
h
/-
h2 E |20||
G z
5(1 + G)
E ||a,, x drds
h2
(1)
h
1."
h2 E axl
G h2
S (T2 G)
V E. Iar, mn12 drdddd
+
(18)
L
h
G 2 h²
(I.2 G)
6
d
E
|00
rdrds
E ||
+
=(1.2 + G)
4V6
d
+
m
E
|,01|3)
1e
1
||2|||
1.2
+
G h?2
15
2
2
(10)
S (L2 G)h?
V
d+ m
||=1||
2
||
12
2
(
d
5(L² + GNN'
+ + |000
+
-12
4n.T.
2
(V
d + ||00011 + 1
s(12 + ())
Vanl
+1
d
52(1.2 + GG)
+ + E |001
12
4kt.
21

---

Published as a conference paper at ICLR 2022
where (x) is due Assumption (ti) is due to Jensen's inequality, (iti) is due to Lemma C.2
(iv) is
1 It is worth noting in the third equation due to va vb v v2va² + b and (v) is due to h Σ dxL
that the Ito's correction term V can also be written AV/ as the two operators commute for Ca functions.
D.3 BOUNDEDNESS OF LMC ALGORITHM
Lemma D.3. Suppose Assumption holds. Denote the iterates of LMC by Th. 1f0 S S T=Z we then have the iterates of LMC algorithm are uniformly upper bounded by
E ax 1| =
+
vk 20 0
7m
Proof. We have
V 22 k-11 1|
E
=B
E
|
E
f( + 2hd 2 vf(zz))
||
||
[())/ 2hd 2h Vf(())))
(9)
- E |
+ 1
الا|ا 2 + 2hd - 2h vf()a))
(40)
E 1| 2122
+ 1
| 1| + 2hd 2mhB | 1
(10)
1
(147mb)
mh
[x
2hd
where (i) is due to the independence between Ex+1 and Tg. (ii) is due Assumption the property of hi-strongly-conva functions, (V fV)) fx()), x) 2 m mly x Vx, y E Rd. and (tv) uses the assumption AxL
| (iti is due to
Unfolding the inequality, we obtain
7 B 2 < (1 3 mh 'E | + 2hd (1 mh + + 7 (mt))--))
+ 8d
S
SE _E1120011
7m
22


Reviews:
[{"review_id": "ryFRIp4LHS", "reviewer": "Reviewer_WTWj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The first result of the paper extends the already significant analysis of [Li et al. (2019)](https://proceedings.neurips.cc/paper/2019/hash/7d265aa7147bd3913fb84c7963a209d1-Abstract.html) and, in particular, only requires the local errors to be bounded by $C + D\\text{ }\\mathbb{E}[||\\boldsymbol{x}||^2]^\\frac{1}{2}$ – which is in line with the classical mean-square analysis of SDEs. Since it is not necessary to establish global $L^2$ bounds of the numerical solution to apply Theorem 3.3, I believe this framework would be particularly helpful for more complicated SDEs and numerical schemes, which seem to becoming more prevalent in the literature.\n\nThe second result is also considerable as it establishes the first $\\mathcal{O}(\\sqrt{d}h)$ 2-Wasserstein bound for ULA. The addition smoothness requirement, namely linear growth of $||\\nabla(\\Delta f)||$ allows $f$ to grow like $x^p$ with $p\\leq 4$ and is less restrictive than the usual Lipschitz assumption on $\\nabla^2 f$. It is also immediately clear in the proof why the term $\\nabla(\\Delta f)$ is important (it comes from Itô's lemma).\n\nThe paper and its appendix are clearly written and the analysis looks mathematically correct. Although the results of the paper are heavily based on previous works, I believe they are novel, provide significant improvements and would be of great interest to the community. For example, I can envision plenty of future research that would use Theorem 3.3 to analyse new SDE-based sampling algorithms. For ULA specifically, the condition A.2. looks appealing and it would be interesting to see which sampling problems have $f$ satisfying it. Thus, I believe this is a strong theory-based paper and would recommend it for acceptance into ICLR.\n\nI could not identify any major weaknesses of the paper, and only have the following minor points / typos to discuss:\n\n### Minor points\n* In the numerical examples, it would also be nice to see how $\\mathbb{E}[||\\bar{\\boldsymbol{x}}_k - \\boldsymbol{x}_T||_2^2]^\\frac{1}{2}$ scales with $d$ and $h$. This would require simulating $\\bar{\\boldsymbol{x}}$ and $\\boldsymbol{x}$ with the same Brownian paths, but would result in the paper demonstrating the complexity of both upper and lower bounds for $W_2\\big(Law(\\bar{\\boldsymbol{x}}_k), \\mu\\big)$.\n\n* I think it should be made clear that the $p_2 \\leq 1.5$ barrier for \"increment only\" methods is not the case in general. For general SDEs, the barrier is $p_2\\leq 1$ (I think this was first shown in [Clark and Cameron (1980)](https://link.springer.com/content/pdf/10.1007/BFb0004007.pdf)). If one allows methods to also use the integral of Brownian motion against time, then the barrier becomes $p_2 \\leq 2$ for additive noise SDEs ([Rößler (2010)](https://epubs.siam.org/doi/abs/10.1137/09076636X) gives very efficient stochastic Runge-Kutta methods for such SDEs). However the underdamped Langevin SDE considered by [Shen & Lee (2019)](https://papers.nips.cc/paper/8483-the-randomized-midpoint-method-for-log-concave-sampling) has special structure that allows for $p_2 > 2$ (for example, the schemes in [Sanz-Serna et al. (2021)](https://arxiv.org/abs/2104.12384) and [Foster et al. (2021)](https://arxiv.org/abs/2101.03446) have $p_2 = 2.5$ and $p_2 = 3.5$ respectively). In general, I'm not sure if randomization on its own leads to higher order convergence rates. For the randomized midpoint method, I believe it is the use of stochastic integrals that gives $p_2 = 2$, whilst the randomization allows for $p_1 = 3$ with just Lipchitz regularity of $\\nabla f$. (pages 6 and 8)\n\n* I feel that $\\boldsymbol{z}$ should be written with a time dependence, i.e. $\\boldsymbol{z}_t := (\\boldsymbol{x}_t - \\boldsymbol{x}) - (\\boldsymbol{y}_t - \\boldsymbol{y})$. It should also be clear how $\\boldsymbol{z}$ is defined in equation (19) as $\\boldsymbol{y}$ isn't used there. (pages 4 and 13)\n\n* Perhaps say \"it follows by Grönwall's inequality\" instead of \"it follows that\" on page 17?\n\n* In the proof of Lemma D.2, I think it would be worth mentioning that the Laplacian $\\Delta$ and gradient $\\nabla$ operators commute for $\\mathcal{C}^3$ functions since Itô's lemma would ordinarily have $\\Delta(\\nabla f)$ in the correction term. (page 20)\n\n### Typos\n* \"corresponds to an Euler-Maruyama discretization\" instead of “corresponds to Euler-Maruyama discretization\" (page 1)\n* \"distances/divergences\" instead of \"distances/diverges\" (page 1)\n* $\\frac{h^2}{2} + o(h^2)$ could use be in larger brackets (page 5)\n* \"$W_2(Law(\\boldsymbol{x}_0), \\mu)$ instead of \"$W_2(Law(\\boldsymbol{x}_0\\mu)$\"  (page 5)\n* Some equations are missing full stops or commas (pages 5, 6, 15,16 and 18). On page 15, the \"$C \\leq\\ldots$\" line is not aligned with the \"$C =\\ldots$\" line above\n* $\\max$ and $\\min$ could use larger curly brackets (pages 7,14 and 15)\n* $\\widetilde{\\Omega}$ appears in Theorem 4.3 on page 8 but $\\widetilde{\\Theta}$ is used in its proof on page 16. In any case, I think it should be explained what this notation means in Section 2.\n* \"$W_2$\" instead of \"W2\" (page 8)\n* \"error. Both\" instead of \"error.Both\" (page 9)\n* \"SDE-based\" instead of \"SDE-basd\" (page 9)\n* \"$L_t \\leq L_0\\exp(-2mt)$rea\" (page 17)\n* \"by the conditioning version of\" instead of \"by conditioning version of\" (page 17)\n* $\\mathbb{E}||\\boldsymbol{x}||^2$ instead of $||\\boldsymbol{x}||^2$ (page 20)\n* $1-\\frac{7}{4}mh$ could use large brackets (page 21)", "summary_of_the_paper": "The paper is concerned with the non-asymptotic analysis of SDE-based sampling algorithms and has two main contributions. Firstly, it improves upon the general framework of [Li et al. (2019)](https://proceedings.neurips.cc/paper/2019/hash/7d265aa7147bd3913fb84c7963a209d1-Abstract.html) and, in particular, does not require uniform boundedness assumptions for the local strong/weak errors. This means their first result, Theorem 3.3, is easier to apply to numerical schemes for contractive SDEs and can already be seen to unify previous works (such as the analysis of KLMC in [Dalalyan et al. (2020)](https://projecteuclid.org/journals/bernoulli/volume-26/issue-3/On-sampling-from-a-log-concave-density-using-kinetic-Langevin/10.3150/19-BEJ1178.short)). Secondly, the authors consider the Unadjusted Langevin Algorithm (ULA) and derive a 2-Wasserstein bound of $\\mathcal{O}(\\sqrt{d} h)$, which has optimal dependence on both the dimension $d$ and step size $h$. To achieve this, they impose an additional smoothness condition on $f$ that is less restrictive than having the Hessian $\\nabla^2 f$ Lipschitz continuous. The authors support this theory with numerical examples, where they demonstrate that a lower bound on the 2-Wasserstein error scales as $\\mathcal{O}(\\sqrt{d})$ and $\\mathcal{O}(h)$.", "summary_of_the_review": "The two main theoretical contributions of the paper are novel, well presented and improve upon previous results. The general mean-square analysis framework is likely to be applicable to a wide variety of SDEs / numerical schemes, and thus would aid future research in SDE-based sampling algorithms. The new $2$-Wasserstein bound on ULA scales optimally with dimension and step size, whilst requiring a smoothness assumption on $f$ that is weaker than the standard Lipschitz Hessian condition. Overall, I believe this is a strong theory-based paper and would recommend it for acceptance into ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lrlqzYXHkmY", "reviewer": "Reviewer_XyDg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I think this is a good piece of improvement but can benefit from reorganisation and clarification of the results.\n\nThe main result of this paper is the improved complexity bound, i.e., it is established that in order for LMC to attain $\\epsilon$ error, the number of iterations scale $\\mathcal{O}(\\sqrt{d})$, not $\\mathcal{O}(d)$ as proved in previous works. This closes the gap between second-order methods like underdamped Langevin Monte Carlo which are claimed to be better in this sense -- this paper effectively shows that this claim is not correct (at least in terms of dimension).\n\nHere are my suggestions.\n\n1) I think the paper can benefit from a clean organization, i.e., stating the main results in Section 2, instead of leaving them to Section 4. It must be also clarified in this sense why the mean-square analysis is precisely useful for $W_2$ (as the mean square error upper bounds $W_2$). I think Section 2 must be devoted to main results and especially the non-standard assumption made in this paper to attain this result.\n\n2) The authors should clarify in a remark how precisely A2 helps to get the result. In other words, which part of the proof fails if this assumption is dropped? Is it possible to use the \"mean-square analysis\" without this assumption and get $\\mathcal{O}(d)$ dependence anyway?\n\n3) It is nice to have the empirical demonstrations and seeing the scaling $\\mathcal{O}(\\sqrt{d})$ in practice. However, does A2 hold for these examples? It has to be shown that the analysis is valid for these simple examples. Another alternative, if this is not possible, is to provide a more complicated example where the scaling still can be observed.", "summary_of_the_paper": "This paper derives an error bound for the LMC that's improved in dimension compared to earlier bounds, at the cost of an extra assumption.", "summary_of_the_review": "This is a good paper that can benefit from a clarification and improvements.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9fUjQUflAK-", "reviewer": "Reviewer_LMTg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I thank the authors for their article, which addresses the important topic of analytically understanding the convergence of the unadjusted Langevin Monte Carlo (LMC) algorithm.\n\n\nOriginality: The authors improve upon existing work to obtain a 2-Wasserstein mixing time bound of O(d^0.5/\\epilson) for LMC, and show this is optimal. This is an original and significant contribution.  \n\nClarity: The article could be better written. For example, incorporating some of the remarks into the main text may read better. \n\nOther than presentation, I do not have any other direct comments about the paper. Note: I have looked through the proofs, but not in great detail. ", "summary_of_the_paper": "The manuscript considers the unadjusted Langevin Monte Carlo (LMC) algorithm, and performs non-asymptotic analysis of its convergence with respect to the 2 Wasserstein distance. The main contribution is a mixing time bound of O(d^0.5/\\epilson), which improves upon the existing O(d/\\epsilon) bound of Durmus and Moulines. The O(d^0.5/\\epilson) is also shown to be optimal for the classes of probability distributions considered. ", "summary_of_the_review": "The manuscript establishes new improved non-asymptotic O(d^0.5/\\epilson) convergence rates for the unadjusted Langevin Monte Carlo (LMC) algorithm. This is a significant contribution and will be of interest to the ICLR community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5fMhaaWEMV", "reviewer": "Reviewer_uCPh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The main strength of the paper is to get sqrt(d) dependence on a dimension with not very restrictive assumptions.\nIn my opinion, the linear growth condition of the third derivative could be discussed in more detail, to improve the presentation of the results.\n", "summary_of_the_paper": "The authors provide new non-asymptotic bounds for the Langevin Mont Carlo algorithm in the strongly convex settings with additional growth conditions for third-order derivatives. The additional assumption allows to get sqrt(d) dependence on the dimension, which is optimal since it meets the exact value for the Gaussian case.", "summary_of_the_review": "I found the paper interesting and I recommend accepting it. I think that a deeper  discussion on assumptions could help readers to better understand main results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a near-optimal analysis of the unadjusted Langevin Monte Carlo (LMC) algorithm with respect to the W2 distance. The main statement is that the mixing time is ~ d^{1/2}/eps under standard assumptions. The authors also give a nearly matching lower bound under these assumptions. The reviewers agreed that this is an interesting contribution obtained via non-trivial techniques. The consensus recommendation is to accept the paper.
Decision: Accept (Poster)