Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo
Authors: Ruilin Li
Hongyuan Zha
Molei Tao
Venue: NeurIPS 2021 Submitted (2021)
Keywords: mean-square analysis
SDE-based sampling algorithm
Langevin Monte Carlo
dimension dependence
non-asymptotic error analysis

Abstract: Sampling algorithms based on discretizations of Stochastic Differential Equations (SDEs) compose a rich and popular subset of MCMC methods. This work provides a general framework for the non-asymptotic analysis of sampling error in 2-Wasserstein distance, which also leads to a bound of mixing time. The method applies to any consistent discretization of contractive SDEs. When applied to Langevin Monte Carlo algorithm, it establishes $\widetilde{\mathcal{O}}\left(\frac{\sqrt{d}}{\epsilon}\right)$ mixing time, without warm start, under the common log-smooth and log-strongly-convex conditions, plus a growth condition on the potential of target measures at infinity. This bound improves the best previously known $\widetilde{\mathcal{O}}\left(\frac{d}{\epsilon}\right)$ result and is optimal in both dimension $d$ and accuracy tolerance $\epsilon$ for log-smooth and log-strongly-convex target measures. Our theoretical analysis is further validated by numerical experiments.

Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo
Anonymous Author(s)
Affiliation
Address
email
Abstract
Sampling algorithms based on discretizations of Stochastic Differential Equations (SDEs) compose a rich and popular subset of MCMC methods. This work pro- vides a general framework for the non-asymptotic analysis of sampling error 2-Wasserstein distance, which also leads to bound of mixing time. The method applies to any consistent discretization of contractive SDEs. When applied to
3
5
Langevin Monte Carlo algorithm, establishes Ô (vá/e) mixing time, without conditions, plus a growth condition on the potential of target measures infinity. This bound improves the best previously known O (d/e) result and is optimal both dimension d and accuracy tolerance for log- oog-shooth and Nog-sstoonlyycomee target measures. Our theoretical analysis is further validated by numerical experiments.
warm start, under the common log-smooth and log-strongly-comy
8
11
Introduction
12
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 and Casella,
14
15 2013; Andrieu al., 2003; Liu, 2008); for example, how various sampling algorithms scale with
16 the dimension of the target distribution is popular recent topic in statistical deep learning (see
17 discussions below for references). For samplers that be viewed as discretizations of SDEs, the
18 idea is to use an ergodic SDE whose equilibrium distribution agrees with the target distribution,
19 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 Bayesian inference and inverse problem (Dashti and Stuart, 2017). One notable example is the Langevin Monte Carlo algorithm (LMC), which corresponds to Maruuaaa discretization of overdamped Langevin equation. Its study dated back to at least the 90s (Roberts et al., 1996) but keeps on leading to important discoveries, for example, on non-asymptootics and dimension dependence, which are relevant to machine learning (e.g., Dalalyan (2017a,b); Cheng et al. (2018a) (20 Durmus et al. (2019a.b); Vempala and Wibisono (2019); Dalalyan and Riou-Durand (2020); Erdogdu and Hosseinzadeh (2020); Mou al. (2019)).
20
21
22
23
24
25
26
27
LMC is closely related to SGD too (e.g., Mandt et al. (2017)). Many other examples exist, based (2020); Ma et al. (2021): Mou et al. (2021); Li al. (2020); Roberts and Rosenthal (1998); Chewi et al. (2020); Shen and Lee (2019)).
28
29
on alternative SDEs and different discretizations (c.g., Dalalyan and
31
32 Quantitatively characterizing the non-asymptotic sampling error of numerical algorithms is usually
33 critical for choosing the appropriate algorithm for specific downstream application, for providing
34 practical guidance hyperparameter selection and experiment design, and for designing improved
35 samplers. A powerful tool that dates back to (Jordan et al., 1998) is a paradigm of non-asymptotic enror analysis, namely to view sampling as optimization in probability space, and it led to many
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37
important recent results (e.g,, Liu and Wang (2016); Dalalyan (2017a): Wibisono (2018); Zhang al. (2018); Frogner and Poggio (2020); Chizat and Bach (2018); Chen et al. (2018); Ma al. (2021); Erdogdu and Hosseinzadeh (2020)). It works by choosing an objective functional, typically some statistical distances/diverges,, 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 and Bartlett, 2018), but a carefully hand-crafted cross term needs to be added to KL divergence for analyzing KLMC (Ma et al., 2021). 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. (2018b); Dalalyan and Riou-Durand (2020); Shen and Lee (2019)). Therefore, it would be desirable complement to have unified, general framework to study the non-asymptotic error of SDE-based sampling algorithms.
38
39
40
41
42
43
44
46
48
49 As an important member of the family of SDE-based sampling algorithms, Langevin Monte Carlo is widely used in practice. Its stochastic gradient version implemented in common machine learning systems, such as Tensorflow (Abadi et al., 2016), and is the off shellf algorithm for large scale 52 Bayesian inference. With the ever-growing size of parameter space, the non-asymptotic error of LMC
50
51
53 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
54
LMC is δ ( (Durmus al., 2019b). Motivated by recent result (Chewi et al., 2020) that shows
55
56
improvement of LMC, we wonder if the current bound for (unadjusted) LMC is tight, and if not, what the optimal dimension dependence?
better dimension dependence for Metropolis-Adjiee
57
Our contribution We study broad family of numerical algorithms that discretize SDEs that have a contraction property (possibly after a coordinate transformation). For this type of problems, we revisit the classical mean-square analysis (Milstein and Tretyakov, 2013) in numerical SDE literature and extend its the global error bound from finite time to infinite time. Same as in classical mean-square analysis, we show the global error is only half order lower than the order of local strong
59
61
62
63
error (p2). We further obtain a θ C
1
mixing time upper bound in 2- Wassersstein
64
distance for the family of algorithms, where C' is a constant containing various information of the underlying problem, e.g., the dimension d.
65
66
As an application of the general mixing time result, we study the widely used Langevin Monte Carlo algorithm (LMC) for sampling from a Gibbs distribution μ xx exp (=f(z)), which is an Marrr-Ma discretization of Langevin dynamics. Under the standard smoothness and strong- convexity assumptions, plus an additional linear growth condition on the third-order derivative of f.
67
68
69
we obtain a Ö mixing time in 2- 2-Wasserstein distance, which improves upon the previously best
70
known δ d result (Durmus et al., 2019b). For a comparison, note was known that discretized
71
kinetic Langevin dynamies can lead to vd dependence dimension (Cheng and Bartlett, 2018; Dalalyan and Riou-Durand, 2020) 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 it was recently shown that Cetropolis-Adjuster Muler-Maruyama discretization of overdamped Langevin
73
74
76
(i.e., MALA) has an optimal dimension dependence of δ (Vd) (Chewi et al., 2020), 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 as that for MALA; more discussion in Section 4). We
77
78
79
80 also constructed an example that shows that the mixing time of LMC is at least Q [ Hence, our mixing time bound has the optimal dependence on both d and e. Our theoretical analysis is further validated by empirical investigation of numerical examples.
81
82
2
Preliminaries
83
84 Notation Use the symbol x to denote a d'dimensiionl vector, and the plain symbol x to denote a scalar variable. Use ||>||| to denote the Euclidean norm of vector A numerical algorithm is denoted
2

---

86 by A and its k-th iterate is denoted by Zt. We slightly abuse notation by identifying measures with their density function w.r.t. Lebesgue measure. We use the convention O (-) O.) log ()))) (-).
86 ie., the O (-) notation ignores the dependence on logarithmic factors. We use the notation 22(-)
89 similarly. Denote 2-Wasserstein distance by p2) (inf(x, ( E Y11 2
where 11(M1, (12) is the set of couplings, i.c. all joint measures with X and Y marginals being 91 Nn and Uz. Denote the target distribution by f 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 f in
93 2- Wasserstein distance by Tmix (c; W2;A) inf 2 ( 11) I c}.
94
SDE for Sampling Consider a general SDE
dr. b(1, an dt + (1, r.)dB
(1)
where be E Rdd is drift term, a E Rdxi 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 22 to Eq. (I). 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 are not limited to those (e.g., 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
96
97
98
99
100
101
102
I, of the SDE and push the time to infinity. so that (approximate) samples of the target distribution
103
can be obtained. Except for a few known cases, however, explicit solutions of Eq. (1) are elusive and
104
we have to resort to numerical schemes to simulate/integrate SDE. Such example schemes include, but are not limited to Maruyaaa method, Milstein methods and Runge- Kutta method (e.g.. Kloeden and Platen (1992); Milstein and Tretyakov (2013)). With constant stepsize h and at k-th iteration, a typical numerical algorithm takes a previous iterate Øx-1 and outputs a new iterate T& as an approximation of the solution æ; of Eq. (1) at time & = kh.
105
107
109
Langevin Monte Carlo Algorithm
LMC algorithm is defined by the following update rule
c = 0 - \ + v2hE,, A = 1,2, ...
(2)
110
where (Ex)eez,s are i...d standard d-dimensional Gaussian vectors. LMC corresponds to an Euler- Maruyama discretization of the continuous overdamped Langevin dynamics dx, = VV fxx)ddt
112
v Bd which converges an equilibrium distribution fr (x)(-
Dalalyan (2017b) provided non-asympiotic analysis of LMC. An δ ($) mixing time bound in
113
114
W2 for log-smooth and geg-ssoonll-conwee target measures (Dalalyan, 2017a; Cheng et al., 2018a; Durmus al., 2019a) has been established. It was further improved to Ō under additional Lipschitz assumption on the Hessian of f (Durmus et al., 2019b). Mixing time bounds of LMC in other statistical distances/divergennces have also been studied, including total variation distance (Dalalyan, 7b; Durmus et al., 2017) and KL divergence (Cheng and Bartlett, 2018).
115
116
117
118
Classical Mean-Square Analysis A powerful framework for quantifying the global discretization
error of a numerical algorithm for Eq. (1), i.e., ex = {E || . is mean-square analysis (c.g.. the monograph of Milstein and Tretyakov (2013)). Mean-square analysis studies how local integration error propagate and accumulate into global integration error; in particular, if one-step
120
121
122
123
(local) weak error and strong error (both the exact solution D. and the numerical approximation start from the same initial value x) satisfy
$ hpt (local weak error)
Ex ET, 11 SC1
( [1+B|=])))
(3)
E 1|00 - x1 11) SC2 1 + | } h02,, (local strong error)
over a time interval [0, Kh) for some constants C2, C2 0. P2 2 and p1 2 P2 + 1, then the
125
126 global error can be bounded by ek S C (1 [1+ E El
1)) $ 1= + k 1,2 2, ... K for some constant
C' 0 dependent on Kh.
3

---

128
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 directly employing mean- -quure analysis in the non-asympiotic analysis of sampling algorithmss The bound of global error only holds in finite time because the constant C' can grow exponentially as K increases, rendering the bound useless when K + 0o.
129
130
131
132
3 Mean-Square Analysis of Samplers Based on Contractive SDE
133
In order to prepare for the analysis of sampling error, we first show that the finite time limitation of integration error analysis can be lifted the SDE being discretized is contractive.
135
138
More precisely, one bottleneck that prevents the results of classical mean-square analysis from extending to infinite time horizon, is the fact that the solution of general SDE may not be bounded, and neither is its discretization. Note that local error (Eq. (3)) depends on the initial value. To go from local to global error, these 'initial' values correspond iterates of numerical algorithms, which change from iteration to iteration and can be unbounded, hence when accumulated together, it is possible that the global error may blow up.
137
138
139
141
142
Samplers considered here, on the other hand, are based on stochastic differential equations, each of which weakly converges to a limiting distributions. The solution of the underlying converging SDE, as it converges to the invariant measure, gradually inherits boundedness properties from the target measure. Thus, as long as the target measure has bounded 2nd-moment, a sampling algorithm based on a reasonable discretization of the SDE should also have bounded 2nd-moment. Motivated by this observation, we will assume the sampling algorithms we study are based on contractive SDEs, which is a sufficient condition to ensure the underlying SDE converges to a statistical distribution.
143
144
145
146
147
148
Definition 3.1. A stochastic differential equation is contractive if there exists a non- non-sirgular constant matrix A E TR. xdd a constant |3 >> O, such that any pair of solutions of the SDE satisfy
150
E [
w))lr)& (x))= <I|A(x
b) exp(-
(4)
where Tt; Yt are two solutions, driven by the same Brownian motion but evolved respectively from initial conditions x and y-
152
153
Remark. As long as b and a in (1) are not explicitly dependent on time, it suffices to find an arbitrarily small to > and show (4) holds for all t to.
154
155
Remark. Sometimes contraction is not easy to establish directly, but can be shown after an appro- priate coordinate transformation, see (Dalalyan and Riou-Durand, 2020, Proposition 1) for such treatment for kinetic Langevin dynamics. The introduction of A permits such transformations.
157
156 We now use contractivity to remove the finite time limitation. We will first need a lemma, which is a local (short time) result.
160
Lemma 3.2. (Milstein and Tretyakov, 2013, Lemma 1.3) Suppose b and a in Eq.(1) are Lipschitz
161
continuous. For two solutions Te; Yt of Eq. (1) starting from x. y respectively, denote z :=
182
(x) x) - (y: - y), then there exist Co > 0 and hg > such that
|| < Co æc y/|² i, Vx, y, <<I S ho-
(5)
163
Then we will have sequence of results that connects sampling error (a statistical property) with local integration error (a simulation property). This justifies our generic produce for non-asymptotie sampling error analysis, which only requires bounding the orders of local weak and strong integration errors (in addition to establishing contractivity of the continuous dynamics).
164
165
186
167
Theorem 3.3. (Global Integration Error, Infinite Time Version) Suppose (1.(1) is contractive with rate 3 and with respect to a non-singular matrix A E Rdxdd with Lipschitz continuous b and o, and there is a numerical algorithm A with step size h simulating the solution x, of the SDE, whose
188
169
170
iterates are denoted by Tg.k = 0, l,.... Suppose there exists 0 < hy S 1, Ci, > 0, D1, D2 Z 2.25 < P2 S P1 7 such that for any 0- < h S ho, the algorithm A has, respectively, local weak and strong error of order pr and p2, defined as
0.P1 > 1,
172
E (2r a1)ll s
E ||1111 hP: C1 DI
(6)
E |
2111²)
1
C3 D3 1 h0,,
4

---

173 where Ty solves (1) with any initial value and T1 is the result of applying A to a for one step.
174 If the solution of SDE Dt and algorithm A both start from Vo. then for 0 < s h1 &
175 min- hos 13
vB
B
the global error ex is bounded as
176
ek == [B|azAn - )tll() S ChP
== 0,,,1,2,
177
where
C1+
CoD2) + C2 + v2DAU
C C= V3" x2 A
VB
Co is from Eq. (5), KiA is the condition number of matrix A and U - 4 ||o0|| 301 + 5 ||=||
178
Remark. We use the convention 1/0- oc when D1 D2 O. This is pertinent when numerical
180
algorithm A, e.g. LMC (Lemma D)3), produces bounded iterates. such cases, the initial value in
Eq. (6) are iterations of A and will be bounded, it then can be absorbed into C1, C2 and we may set D1 = D2=02 =0 O.
182
Following Theorem 3.3, we obtain the following non non-as con-asympottic bound of the sampling error in W2:
184
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
185
W2(Law(Ts)) S V2e- TBe-SkhWe W2 1)) + 22CPP-3 4O < S hn-
188
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
188
with the same notation of Theorem 3.3, we have
1 3h1
20
P2-
2V2W2(Law(a))
Tmix W2; S max
log
In particular, when high accuracy is needed, i.e., e < hCh1 -= we have
189
log 2) C²2-3 (
(2C)
Tiix (e; A2; 5
3
B
e -2
Corollary 3.5 states how mixing time depends on the order of local (strong) error (i.e., P2) of numerical algorithm. The larger P2 is, the shorter the mixing time of the algorithm is, term of the dependence on accuracy tolerance parameter It 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 strong order barrier, namely P2 1.5 (Rüemelin, 1982); however, methods involving multiple stochastic integrals (e.g., Kloeden and Platen (1992); Milstein and Tretyakov (2013)) and randomization (e.g., Shen and Lee (2019)) can yield a larger P2-
191
193
195
197
The constant C defined in Eq. (7) typically contains rich information about the underlying SDE, e.g. dimension, Lipschitz constant of drift and noise diffusion, and the initial value Eg 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 exemplified with Langevin Monte Carlo in the next section.
198
199
4 Non-Asymptotic Analysis of Langevin Monte Carlo Algorithm
202
This section quantifies how LMC samples from Gibbs target distribution μ ~ exp (-f(x)) that has finite second moment, i.e., Saa ||= du oc. Assume without loss of generality that the origin is local minimizer of f. i.e. V/(0) = 0; this is for notational convenience in the analysis and can 205 be realized via simple coordinate shift, and it is not needed the practical implementation. In
addition, assume the following two conditions hold:
5

---

207 A (Smoothness and Strong Convexity) Assume f E C² and is L-smooth and cosee, i.e. there exists m such that mla & f() & Lla. Va R
208
Denote the condition number of f by the standard assumption in the literature of analyzing LMC algorithm (Dalalyan, 2017a.b; Cheng and Bartlett, 2018; Durmus et al., 2019a.b).
The smoothness and strong- assumption is
210
(Linear Growth of the 3rd-order derivative) Assume f E C³ and the operator V(Af) grows at most linearly, i.e. there exists constant G such that [((f(()))] G |æ]l).
212
213
214
Remark. The linear growth (at infinity) condition on V is actually not as restrictive as 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). we consider monomial potentials, i.e., f(z) = x², E 14, then the linear growth condition on V f is met when whereas the classical condition for the existence of solutions holds only when p S 2.
215
216
217
218
219 p S
220 To apply mean square analysis to study LMC algorithm. we will need to ensure the underlying
I Langevin dynamics is contractive, which we verify in Section and D in the appendix. In addition,
222
we work out all required constants to determine the in Eq. 7 explicitly in the appendix. With all
these necessary ingredients, we now invoke Theorem 3.4 and obtain the following result:
224
Theorem 4.1. (Non-Asymptotic Error Bound: LMC) Suppose Assumption and hold. LMC
225
iteration Tk+1 3g hV fzxx) + v 2 satisfies
1 KEN (10) 4KL
Wu(Law(zz),, S V2e muk W2 12 W2(La((zo) p4) 22CMch, 0chs
where LLMC= 10(L++G) m
2d m (1z01l (1z001++1)= =(Vd). (
228
227
Corollary 3.5 combined with the above result gives the following bound on the mixing time of LMC:
228
Theorem 4.2. (Upper Bound of Mixing Time: LMC) Suppose Assumption I and 2 hold. If running
229
LMC from VG, we then have
Tmi 22; LMC) S max{(n2, 2CIMC 1 m log
2V2W2
E
230
where LasC is the same in Theorem 4.1. When high accuracy is needed, i.e. e S
CimE we have 2m
m Taix LMC) < 2CLMC 1 - log 2/22g(Law(za)).) Ō
V
The Ō (vv)) mixing time bound in 2- 2-Wasserstein distance improves upon the previous ones (Dalalyan, 2017a; Cheng and Bartlett, 2018; Durmus et al., 2019b,a) in the dependence of and/or e.
232
233 If further assuming G = O(L)), we then have CLMC = O /mv d) and Thm.4.2 shows the mixing time is δ vd which also improves the x dependence in some previous results (Dalalyan, 2017a; Cheng and Bartlett, 2018) in the regime m < 1. A brief comparison is summarized in Table 1.
234
Optimality In fact, the δ mixing time of LMC has the optimal scaling one can expect. This is in tenms of the dependence on and e, over the class of all log- smooth and log-strongly-conwe target measures. To illustrate this, consider the following Gaussian target distribution whose potential
296
238
239
2d Σ
= m Σ 2
((x)
with m 11 L 2 4m.
(11)
:=1
(=++1
We now establish lower bound the mixing time of LMC algorithm for this target measure. Theorem 4.3. (Lower Bound of Mixing Time) Suppose we run LMC for the target measure defined
241
242
in Eq. (11) Bo = 1 then for any choice of step size h > O within stability limit, we have
Vd log
Vd
VV
Tmix W3: LMC)= 2
=
8E

---

Table 1: Comparison of mixing time results in 2- 3-Wassertein distance of LMC with L-smooth and m-strongly-convex potential. Constant step size is used and accuracy tolerance is small enough.
mixing time
Additional Assumption
(Dalalyan, 2017a, Theorem 1)
N/A
m
(Cheng and Bartlett, 2018, Theorem
x²
N/A
m
(Durmus al., 2019a, Corollary 10)
N/A
m
(Durmus al., 2019b, Theorem 8)
| V> S L || yl
This work (Theorem 4.2)
va
Assumption 2 and G (
Combining Theorem 4.2 and 4.3, we that mean-square analysis provides tight bound for LMC.
244
However, there is one limitation of our result- Assumption 2, which is, although mild, still extra to the standard setup. Therefore, the gap between the upper bound and the lower bound of LMC algorithm over the entire family of log-smooth and log-strongly-cone closed. We tend to believe that Assumption 2 may not be essential, but rather than artifact of our proof technique. We hope to lift this restriction in future work.
246
target measures not completely
248
Comparison At least sampling algorithms are closely related LMC. One is Kinetic Langevin Monte Carlo algorithm (KLMC), which is discretized kinetic/underdamped Langevin dynamics, and the other is Metropolis- Adjusted Langevin Algorithm (MALA) which uses the one-step update of LMC as proposal and then accepts/rejects them with a Metropolis-Hastingg algorithm.
250
252
The δ vd mixing time in 2- Wasserssenin distance of KLMC has been established for log-smooth
253
254
and log-strongly-convee target measures in existing literature (Cheng et al., 2018b; Dalalyan and Riou-Durand, 2020). Due to better dimension dependence over previously best known results of LMC, KLMC is understood to be the analog of Nesterov's 's accelerated gradient method for sampling
255
256
257
(Ma al., 2021). Our findings show that LMC is able achieve the same mixing time, albeit under condition. However, this does not say anything about whether/how KI MC accelerates LMC,, as the optimality of KLMM bound is not yet clear. We also note KLMC has better condition number dependence, although the dependence in our bound may not be tight.
258
an additional
259
In terms of MALA, a recent work (Chewi et al., 2020) establishes a Ô (vd mixing time in 251
Wasserstein distance with warm start, and the dimension dependence is shown to be optimal. We see that without the Metropolis adjustment, LMC can also achieve the optimal dimension dependence as MALA. But unlike LMC, MALA only has logarithmic dependence on 1. Under warm-start condition, possible/how to improve the dependence of 1 for LMC, from polynomial to logarithmic? This question is beyond the scope of this paper but worth further investigation.
263
285
256
5
Numerical Examples
This section numerically verifies our theoretical findings for LMC in Section 4, with a particular focus on the dependence of the discretization error in Theorem 4.1 dimension d and step size h. 270 To this end, we consider two target measures specified by the following two potentials:
268
d Σ
d
(z) = ||00| + log
and fz(x) = 5 ||=||
Σ cos (dtz:). (12)
2d
It is not hard see that f1 is 2-smooth and 1- 1-strongly convex, fo is 3 smoohh and 1-strongly- 272 convex. fo is also used in (Chewi et al., 2020) to illustrate the optimal dimension dependence of MALA. Explicit expression of 2- 2-Wasserstein distance between non-Gaussian distributions is
I 'The dependence on x is not readily available from Theorem in Durmus et al. (2019h). "hh G = OLL?) assumption is only for K, m dependence. Removing it does not affect d, c dependence.
7

---

274
typically not available, instead, we use the Euclidean norm of the mean error as a surrogate because 275 [E ,0 I W2(Law(@x), (i) due to Jensen's 's inequality. To obtain an accurate estimate the ground truth, we run 10a independent LMC realizations using a tiny step size (h 0.001), each till a fixed, long enough time, and use the empirical average to approximate E,,,
276
278
To study the dimension dependence of sampling error, we fix step size h 0.1, and for each d E {1.2, 5, 10, 20, 50, 100, 200, 500, 1000), we simulate 10* independent Markov chains using
279
280
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.
281
To study step size dependence of sampling error, dimension is fixed to be d = 10. We experiment with step size E {1. 2, 3, 4, 5, 6, 7, 8, 9, 10) x 10-1. We fix a continuous time T = 20, and run LMC algorithm for f: iterations for each h. The procedure is repeated 10* times with different random
283
284
seeds to obtain independent samples. When the corresponding continuous time = kh >> 10, from Eq. (10) that LMC is well converged and the sampling error is saturated by the discretization emoo. Therefore, for each h, take the last
286
287
π
iterates and record the mean and standard deviation
288
of their sampling error.
8005
X x
Olv d')
| 2 5/l
olv )
O(h) LMC
O(h)
LMC
LMC
LMC
Dimension
1P Dimension
Step
61
Step size
(a) fi: d dependence
(b) fz: d dependence
(c) f1: lt dependence
(d) fz: fa dependence
Figure I: (a) Dependence of the sampling error of LMC on dimension d and step size h for f1 and fa- Both axes in Figure la and Ib are in log scale. The shaded areas in Figure la and 1b represent one standard deviation of the last 10 iterates. The shaded areas in Figure I and Id represent one standard deviation of the last 10 iterations.
The experiment results shown in Figure are consistent with theoretical analysis of the sampling arror.Both linear dependence on vd and h can be identified in and supported by the empirical evidence. Note results with smaller h are less accurate because one starts to see the error of empirical approximation due finite samples. Experiments were conducted machine with 2.20GHz (Rt Xeon(R) E5-2630 v4 CPU and an Nvidia GeForce GTX 1080 GPU.
281
293
Conclusion
294
295
This paper extends the mean-square analysis framework for analyzing the integration error of SDE to analyzing the sampling error in 2- 2-Wasserstein distance. Corresponding mixing time bound unveils how a high-order numerical algorithm can help improve dependence on accuracy tolerance e, and potentially other parameters, such as the dimension. When applied to Langevin Monte Carlo algorithm, it obtains an improved and optimal ① (valc) bound, which was previously thought to be obtainable only with the addition of momentum.
296
297
298
299
300
301
Here are some possible directions worth further investigations. (i) In data-intensive applications, stochastic gradients are typically used for better scalability. It seems natural to apply the square analysis framework to study SDE-basd stochastic gradient MCMC methods; (ii) Assumption is
303
likely be an artifact of our analysis; how establish the optimal mixing time bound in the standard
305
setup is still an open question; (ii) Motivated by the recent result of MALA (Chewi et al., 2020), it would be interesting know whether the dependence on
smotth and log-strongly-come
307
can be improved to logarithmic, for example if LMC is initialized at a warm start.
8

---

References
308
309
Abadi, M.. Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., Kudlur, M., Levenberg, J., Monga, R., Moore, S., Murray, D. G., Steiner, B., Tucker, P., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., and Zheng, X. (2016). Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 265-283.
311
313
314
Andrieu, C.. De Freitas, N., Doucet, A., and Jordan, M. I. (2003). An introduction to meme for machine learning. Machine learning, 50(1):5-43,
315
316
Chen, C., Zhang, R., Wang, W., Li, B., and Chen, I., (2018). unified particle-otimmizaionn frame- work for scalable bayesian sampling. In The Conference on Uncertainty in Artificial Intelligence.
317
Cheng, X. and Bartlett, P. L. (2018). Convergence of langevin meme in kl-divergence. PMLR 83, 186):186-211.
319
320
Cheng, X., Chatterji, N. S., Abbasi- Yadkori, Y., Bartlett, P. L., and Jordan, M. I. (2018a). Sharp con- vergence rates for langevin dynamies in the nonconvex setting. arXiv preprint arXiv: 1805. 01648.
322
Cheng, X., Chatterji, N. S., Bartlett, P. L., and Jordan, M. (2018b). Underdamped langevin meme: A non-asymptotic analysis. Proceedings of the 31st Conference On Learning Theory, PMLR.
323
324
Chewi, S., Lu, C., Ahn, K., Cheng, X., Gouic. T. L., and Rigoliet, P. (2020), Optimal dimension dependence of the metropolis-adjuster langevin algorithm. arXiv preprint arXiv:2012./28/11
325
326
Chizat, and Bach, F. (2018). On the global convergence of gradient descent for over-parameterized models using optimal transport. In Advances in neural information processing systems, pages 3046-
328
329
Dalalyan, A. S. (2017a). Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. Conference Learning Theory, pages 678-689.
331
Dalalyan, A. S. (2017b). Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 79(3):651-676.
332
333
334
Dalalyan, A. S. and Riou-Durand, L. (2020). On sampling from a log-coneave density using kinetic Langevin diffusions. Bernoulli, 26(3):195611988
335
Dashti, M. and Stuart, A. M. (2017). The Bayesian Approach to Inverse Problems, pages 311-428. Springer International Publishing, Cham.
337
338
Durmus, A., Majewski. S., and Miasojedow, B. (2019a). Analysis of langevin monte carlo via convex
339
optimization. Journal of Machine Learning Research, 20:73-1.
340
Durmus, A., Moulines, E., al. (2017). Nonasymptotic convergence analysis for the unadjusted
341
langevin algorithm. Annals of Applied Probability, 275):15551
342
Durmus, A., Moulines, E., al. (2019h). High-dimensional bayesian inference via the unadjusted langevin algorithm. Bernoulli, 25(4A):2854 2882.
343
344
Erdogdu, M. A. and Hosseinzadeh, R. (2020). On the convergence of langevin monte carlo: The interplay between tail growth and smoothness. arXiv preprint 1339.
Frogner, C. and Poggio, T. (2020). Approximate inference with wasserstein gradient flows. In International Conference on Artificial Intelligence and Statistics.
347
348
Jordan, R., Kinderlehrer, D., and Otto, F. (1998). The variational formulation of the fokker-planck equation. SIAM journal on mathematical analysis, 29(1):1-17.
349
350
Kloeden, P. E. and Platen, E. (1992). Numerical solution of stochastic differential equations. Springer.
351
Li, R., Zha, H., and Tao, M. (2020). Hessian-free high-resolution nesterov acceleration for sampling. arXiv preprint ar Ttt::200000930.

---

353 Liu, S. (2008). Monte Carlo strategies in scientific computing. Springer Science & Business Media.
Liu, Q. and Wang. D. (2016). Stein variational gradient descent: general purpose bayesian inference algorithm. Advances in neural information processing systems, pages 2378-2386.
355
356
Ma, Y.A.,, Chatterji, N. S., Cheng, X., Flammarion, N., Bartlett, P. L., and Jordan, M. (2021). Is there analog of Nesterov acceleration for gradient-based MCMC? Bermoulli, 27(3):1942 1992.
Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent approximate bayesian inference. Journal of Machine Learning Research, 18(13)):1-35.
359
380
Milstein, G. N. and Tretyakov, M. V. (2013). Stochastic numerics for mathematical physics. Springer
361
Science & Business Media.
362
Mou, W. Flammarion, N., Wainwright, M. J., and Bartlett, L. (2019). Improved bounds for
discretization of langevin diffusions: Near-optimal rates without convexity. arXiv preprint 1rXiv:1907.113:
364
365
Mou, W., Ma, Y.AA., Wainwright, M. J., Bartlett, P. L., and Jordan, M. I. (2021). High-order langevin diffusion yields accelerated meme algorithm. Journal of Machine Learning Research, 22(42))1-41,
367
388
Pavliotis, G. A. (2014). Stochastic processes and applications: diffusion processes, the Tokker-Plance and Langevin equations, volume 60. Springer.
389
370
Robert, C. and Casella, G. (2013). Monte Carlo statistical methods. Springer Science & Business Media.
Roberts, G. O. and Rosenthal, J. S. (1998). Optimal scaling of discrete approximations to langevin
373
diffusions. Journal of the Royal Statistical Society: Series (Statistical Methodology), 60(1):255- 268.
Roberts, G. O., Tweedie, R. L., al. (1996). Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363.
376
377
Rüemelin, W. (1982). Numerical treatment of stochastic differential equations. SIAM Journal on Numerical Analysis, 19(3):604-613
378
379
Shen, R. and Lee, Y. (2019). The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems, pages 2098-2109
Vempala, S. and Wibisono, A. (2019). Rapid convergence of the unadjusted langevin algorithm:
382
Isoperimetry suffices. In Advances Neural Information Processing Systems, pages 8092-8104
383
Wibisono, A. (2018). Sampling as optimization in the space measures: The langevin dynamics as
384
composite optimization problem. In Conference On Learning Theory, pages 2093-3027.
385
Zhang, R., Chen, C., Li, C., and Carin, L. (2018). Policy optimization as wasserstein gradient flows. In International Conference on Machine Learning, pages 5737-5746.
386
10

---

Checklist
387
388
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
390
contributions and scope? [Yes]
381
(b) Did you describe the limitations of your work? [Yes] Limitation is discussed in the paragraph below Table I.
392
393
(c) Did you discuss any potential negative societal impacts of your work? [N/A] To the best of our knowledge, this work does not have any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
396
397
2. If you are including theoretical results...
398
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are fully, clearly stated in theorems.
399
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs of all theoretical results are provided in supplementary materials.
401
402
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] All are provided in supplementary materials.
404
408
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Our experiments do not need training. We specify all the hyperpa- rameters needed run the experiments.
407
408
409
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure 1.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We report the hardware used to run our experiments.
412
413
4. If you using existing assets (e.g., code, data, models) or curating/releusing new assets...
415
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
417
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
418
419
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
420
421
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
422
5. If you used crowdsourcing conducted research with human subjects...
424
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
425
426
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
429
11


Reviews:
[{"review_id": "tsOugZ5MKwb", "reviewer": "Reviewer_j2p5", "summary": "This paper introduces a framework for analyzing the discretization of SDEs such as the Langevin diffusion. Within this framework, once the discretization error incurred by the algorithm in a single iteration is controlled, it automatically yields a mixing time bound in Wasserstein distance for the algorithm. Importantly, this framework only applies to contractive SDEs which essentially requires the target distribution to be strongly log-concave (in particular, it cannot accommodate common weakinings of this condition, such as a log-Sobolev inequality). This framework is then applied to the standard Langevin Monte Carlo algorithm and under strong log-concavity, log-smoothness, and a condition on the third-order derivative of the potential, a mixing time bound of d^{½}/ε is obtained; this bound is shown to be tight on Gaussian targets. Prior bounds (using different third-order conditions) obtained at best d/ε.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "This work is interesting; certainly the idea of reducing the problem of proving mixing time bounds to a simple computation of one step of discretization is quite appealing. However, I do not find the results in this paper entirely convincing. Without a higher-smoothness condition, the approach of this paper does not improve upon prior analyses of Langevin (in fact, the proof technique appears to be more brittle since it relies heavily on contractivity). The main new result claimed in this paper is an improved dimension dependence under third-order smoothness condition, but it is possible that the third-order smoothness parameter hides some dimension dependence (see further comments below).\n\nSpecific Comments:\n- Abstract should be modified from “a growth condition on the potential of target measures” to “a growth condition on the third derivative of the potential of target measures”.\n- No attempt is made to compare the third-order derivative condition used in this paper with the Hessian Lipschitz condition used in prior works. Although it may not be possible to compare these conditions in full generality, there should at least be some discussion of it. The Hessian Lipschitz condition at least has the nice property that it “tensorizes”, in the sense that if f(x) = sum_i f_i(x_i) is coordinate-wise separable, with each f_i satisfying the Hessian Lipschitz condition with constant L, then the function f does too with the same constant L (and hence it is a “dimension-independent” condition); this is not true for the third-order condition in this paper. From this it is not difficult to build examples where the constant G in this paper is much larger than the Hessian Lipschitz constant. For example, we can take the coordinate-wise separable function f where each f_i is of the form f_i(x) = (x^2 + sin x)/2, and then the Hessian Lipschitz constant is O(1) whereas the parameter G of this paper scales as d^{½}. These considerations make the claim of “optimal dimension dependence of Langevin Monte Carlo” rather unclear.\n- In the vein of the above two comments, it seems premature to compare the dimension dependence of LMC with underdamped Langevin and MALA, both of which attain their dimension dependence without third-order conditions. The authors seem to think that the third-order condition is a technical artefact which can be removed, but this is simply speculation at this point (it is possible that in the future we may see a lower bound construction which shows that the O(d) mixing time of LMC using only strong log-concavity and log-smoothness is in fact tight).\n- On Thm. 4.3 (lower bound on mixing time): Since m is set to 1 and L is set to 4, introducing the variables m and L makes the proof unnecessarily confusing (e.g. going from eq. (26) to (27) where all the m’s disappear). As another note, an alternative way to deduce (27) would be to use the expression for the bias of Langevin (computed in e.g. Example 2 of https://arxiv.org/abs/1802.08089) and to deduce that the step size cannot be set too large; this should hopefully simplify the calculation to the point where the lower bound can capture some dependence on the condition number (by considering a potential whose potential has d-1 eigenvalues which are m and 1 eigenvalue which is L), which would be interesting.\n- The experiments are not convincing since they do not plot the Wasserstein distance but rather the difference in means, which seems like an especially poor proxy for the Wasserstein distance. Is it possible to at least plot an approximation of the Wasserstein distance, e.g. entropically-regularized Wasserstein distance?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "FrLHoqYjhwb", "reviewer": "Reviewer_DVEg", "summary": "This paper first gives an analysis framework for controlling 2-Wasserstein distance of sampling algorithms coming from discretizing a continuous Langevin dynamics.\nThis is achieved by first considering the bias (local weak error) and mse (local strong error) of single step update. \nThe multi-step error accumulate exponentially, but together with the contraction guarantee, the maximum sampling error after arbitrary steps could be controlled.\nNext, this paper introduces an assumption on the linear growth of the 3rd-order derivative which is shown to improve the convergence rate in terms of dependency of dimension.\nThe convergence analysis is carried out based on the general analysis framework.", "questions": "", "limitations": "", "rating": 5, "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": "This paper is mostly well written and easy to follow.\n\nThe analysis framework is general and easy to use but the proof is not novel.\nMany researchers working  on the problem of sampling have already had this idea and internalized this method in their numerical analysis of special sampling algorithms.\nHowever, given that none of them have managed to convert it into a general framework, there is indeed novelty in this framework.\n\nThe improvement of dependency of dimension relies on the assumption on linear growth of the 3rd-order derivative.\nHas similar assumption been introduced in sampling or optimization algorithm analysis before? If the author could comment on this, it may be helpful in appreciating the novelty here.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is recommended to amend the discussion around line 249 or introduction to consider various relevant works on the dependency of dimension with different assumptions. The randomized midpoint method is of particular relevant because it requires weaker assumptions but achieves lower dependency of dimension in convergence rate (and same dependency of dimension in 2-Wasserstein error).\n\nFor LMC, an information-based argument implies that at least $O(\\sqrt{d})$ dependency of dimension in 2-Wasserstein error is optimal, therefore the dependency in this paper cannot be improved by introducing new assumptions. However, it is still not clear whether the new assumption is necessary for achieving acceleration. More specifically, we haven't rule out the existence of one potential that satisfies standard smooth and strongly convex condition but requires higher order dependency of dimension. Therefore, it is better to clarify in what sense the analysis and algorithm is optimal or use the word \"optimal\" sparingly.\n\nPOST REBUTTAL: I thank the authors for the response. The theoretical result is novel and I think the possible extension to the randomized midpoint method makes the analysis framework even more interesting. I will raise my score from 6 to 7.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 day"}, "extra_text": {}}, {"review_id": "DfJwlmlJOG7", "reviewer": "Reviewer_LgVW", "summary": "This paper derives an improved 2-Wasserstein convergence bound for the Langevin algorithm (ULA). As noted in the paper, the folk wisdom is that the previously known error bound for the ULA is O(d/epsilon), compared to the underdamped MCMC O(sqrt{d}/epsilon). The paper claims to improve the ULA bound in W-2 distance, matching the case of the underdamped bound. See my detailed comments for questions.", "questions": "", "limitations": "", "rating": 5, "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": "1) Looking at Theorem 4.1, the main result for the LMC, the authors establish an O(\\sqrt{d}) error bound. They claim that this bound improves the best known O(d) bound established in several references. However, looking at Theorem 8 of Durmus et al (2019b) (as referenced in Table 1), the error bound is derived in that paper is in terms of **squared** Wasserstein-2 (W_2^2) rather than Wasserstein 2 as in Theorem 4.1 of this paper. Taking square roots in Theorem 8 of Durmus et al (2019b) gives a O(sqrt{d}) bound. This is also confusing regarding the claims that underdamped MCMC is better than ULA. I would really appreciate the clarification regarding this point and why the bound derived in this paper is better than Theorem 8 of Durmus et al (2019b) once a square root is taken. Since this is the main claim of the paper, if this is incorrect, then the whole story needs to be rewritten. My final evaluation will mostly depend on this and I am open to increase it given a clear rebuttal.\n\n2) An obvious question is the verifiability of A2, i.e., for the examples considered, can you verify A2 and prove that it holds for simple scenarios, e.g., the one considered in Sec. 5?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9M2d031YDVe", "reviewer": "Reviewer_8SkQ", "summary": "This paper introduced a mean-square analysis to study the converge rate of overdamped Langevin dynamics to the Gibbs stationary distribution. In particular, the authors proved that the convergence in $W_2$ norm is of order $\\sqrt{d}/\\varepsilon$ which is also optimal. This is the same order as the underdamped Langevin equation, and beats all the previous rates. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "This paper deals with convergence rate for a class of stochastic differential equations -- contractive SDE (based on coupling). This technique allows for analyzing the discretization error at arbitrarily large times. As an application, the authors showed that the overdamped Langevin equation converges in $W_2$ norm at rate $\\sqrt{d}/\\varepsilon$, and this rate cannot be improved. This beats all the previously established rate for overdamped Langevin sampling, which is the same as the status of the art underdamped sampling rate. This result is interesting, novel and important with also applications to optimization (e.g. simulated annealing).\n\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n\nAfter AC's comment on a previous work \"Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond.\" Advances in Neural Information Processing Systems 32 (2019): 7748-7760, I think the results of the paper is less strong than what I initially judge. I would change my score from 7 to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "45 min"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a good paper, but unfortunately authors missed an important reference [Thm 1, Li et. al., 2019], and proved a result that is almost identical to the one in that paper. 

Comparing [Thm 1, Li et. al., 2019] and Thms 3.3, 3.4 and Cor 3.5 in the current paper, one notices that the results are almost identical, with very minor differences. Authors were made aware of this work, and they acknowledged missing the reference in their sincere response. Authors' main contributions rely on Thms 3.3, 3.4, and given [Thm 1, Li et. al., 2019], it decreases the novelty of this paper significantly.

All the reviewers and the AC think this paper makes important contributions, but they also think adapting the paper to this missed reference from Neurips 2019 would require a major revision of their Section 3, and invalidates some of the novelty claims made in the paper. 

When the authors revise their paper and resubmit to the next conference, I would not hesitate to accept the revised version should it be assigned to me.
Decision: Reject