Random Coordinate Langevin Monte Carlo
Authors: Zhiyan Ding
Qin Li
Jianfeng Lu
Stephen Wright
Venue:  (2021)
Keywords: Random coordinate descent
Langevin dynamics
Monte Carlo sampling

Abstract: Langevin Monte Carlo (LMC) is a popular Markov chain Monte Carlo sampling method. One drawback is that it requires the computation of the full gradient at each iteration, an expensive operation if the dimension of the problem is high. We propose a new sampling method: Random Coordinate LMC (RC-LMC). At each iteration, a single coordinate is randomly selected to be updated by a multiple of the partial derivative along this direction plus noise, and all other coordinates remain untouched. We investigate the total complexity of RC-LMC and compare it with the classical LMC for log-concave probability distributions. When the gradient of the log-density is Lipschitz, RC-LMC is less expensive than the classical LMC if the log-density is highly skewed for high dimensional problems, and when both the gradient and the Hessian of the log-density are Lipschitz, RC-LMC is always cheaper than the classical LMC, by a factor proportional to the square root of the problem dimension. In the latter case, our estimate of complexity is sharp with respect to the dimension. 

Under review as a conference paper at ICLR 2021
RANDOM COORDINATE LANGEVIN MONTE CARLO
Anonymous authors
Paper under double-blind review
ABSTRACT
Langevin Monte Carlo (LMC) popular Markov chain Monte Carlo sampling method. One drawback is that it requires the computation of the full gradient at each iteration, an expensive operation if the dimension of the problem high. We propose a new sampling method: Random Coordinate LMC (RC-LMC). At each iteration, a single coordinate is randomly selected to updated by a multiple the partial derivative along this direction plus noise, and all other coordinates re- main untouched. We investigate the total complexity of RC-LMC and compare it with the classical LMC for log-concave probability distributions. When the gra- dient of the log- density is Lipschitz, RC-LMC is less expensive than the classical LMC if the log-density is highly skewed for high dimensional problems, and when both the gradient and the Hessian of the log-density are Lipschitz, RC-LMC al- ways cheaper than the elassical LMC, by a factor proportional the square root of the problem dimension. In the latter case, our estimate of complexity is sharp with respect to the dimension.
INTRODUCTION
Monte Carlo sampling plays an important role in machine learning (Andrieu et al.] 2003) and Bayesian statistics. applications, the need for sampling is found in atmospheric science (Fabian) 1981), epidemiology (Li et al. 2020), petroleum engineering (Nagarajan et al. 2007). in the form of data assimilation (Reich) 2011). volume computation <Vempalal 2010) and bandit optimiza- tion (Russo et al. 2018).
In many of these applications, the dimension of the problem is extremely high. For example, for weather prediction, in the air, before running the Navier-Stokes equations into the near future (Evensen) (009). In a global numerical weather prediction model, the degrees of freedom in the air flow can be as high as 10 Another example is from epidemiology: When a disease is spreading, one measures the everyday new infection cases infer the transmission rate in different regions. On county-level modeling, one treats 3, 141 different counties in the US separately, and the parameter to be inferred has dimension of least 141 et 2020).
measures the current state temperature and moisture level, to infer the flow
In this work, we focus on Monte Carlo sampling of log-concave probability distributions on IRd meaning the probability density can be written as p(x) x e-((x) where a f(x) is a convex function. The goal is to generate (approximately) i.i.d. samples according to the target probabil- ity distribution with density p(x). Several sampling frameworks have been proposed in the lit- erature, including importance sampling and sequential Monte Carlo (Geweke 1989 Neal 2001 Del Moral et al., 2006); ensemble methods (Reich) 2011 Iglesias et al. 2013); Markov chain Monte Carlo (MCMC) (Roberts and Rosenthal 2004), including Metropolis Hastopp based MCMC (MH-
MCMC) (Metropolis et al. 1953; Hastings) 1970, Roberts and Tweedie 1996); Gibbs samplers
(Geman and Geman 1984 Casella and George 1992); and Hamiltonian Monte Carlo (Neal) [993]
Duane et al. 1987). Langevin Monte Carlo (LMC) (Rossky et al.) 1978 Parisi 1981 Roberts and
Tweedie 1996) is popular MCMC method that has received intense attention in recent years due to
progress the asymptotic analysis of its convergence properties (Durmus and Moulines 2017
Dalalyan 2017: Dalalyan and Karagulyan 2019 Durmus et al. 2019).
Denoting by x the location of the sample at m-th iteration, LMC obtains the next location as follows:
m+1 th
(x 22hgn

---

Under review as a conference paper at ICLR 2021
where h is the time stepsize, and 5 is drawn i..d from NV Ia), where La denotes identity matrix of size x d. LMC can be viewed as the Buler-Maruyann discretization of the following stochastic differential equation (SDE):
dx2- = VV) di + v
where Bi a d-dimensional Brownian motion. It is well known that under suitable conditions, the distribution of X, converges exponentially fast to the target distribution (see e.g., (Markowich and Villani 1999]. Since (I) approximates the SDE (2) with an (h) discretization error, the probabil- ity distribution of x" produced by LMC (T) converges exponentially to the target distribution up to a discretization error (Dalalyan and Karagulyan| 2019).
A significant drawback of LMC is that the algorithm requires the evaluation of the full gradient at each iteration. This could be potentially very expensive most practical problems. Indeed, when the analytical expression of the gradient is not available, each partial derivative component in the gradient needs to be computed separately, either through finite differencing or automatic differentiation (Baydin et al. 2017), that the total number of such evaluations can be as many as d times the number of required iterations. In the weather prediction and epidemiology problems discussed above, f stands for the map from the parameter space of measured quantities via the underlying partial differential equations (PDEs), and each dimensional partial derivative calls for one forward and one adjoint PDE solve. Thus, 2d PDE solves are required in general at each iteration. Another example comes from the study of directed graphs with multiple nodes. Denote the nodes by N = {1, ....... d} and directed edges by & C. {(i.j) : i.j N). and suppose there is scalar variable associated with each node. When the function f has the form f(z) EoSEE feg(2,, 2ty,, the partial derivative of f with respect to 2; is given by
{1,
as = Σ Oz. (OLI)E
2z) + O5u Oz,
0hu Oz,
Σ E(,,)E
(z1,
Note that the number of terms in the summations equals the number of edges that touch node i, the expected value of which is about 2/d times the total number of edges in the graph. Meanwhile, evaluation of the full gradient would require evaluation of both partial derivatives of each fig for all edges in the graph. Hence, the cost difference between these operations is factor of order d.
In this paper, we study how to modify the updating strategies of LMC to reduce the numerical cost, with the focus reducing dependence on d. In particular, we will develop and analyze a method called Random Coordinate Langevin Monte Carlo (RC-LMC). This idea is inspired by the random coordinate descent (RCD) algorithm from optimization (Nesterov 2012 Wright 2015). RCD is a version of Gradient Descent (GD) in which one coordinate (or a block of coordinates) is selected at random for updating along its negative gradient direction. In optimization, RCD can be significantly cheaper than GD, especially when the objective function is skewed and the dimensionality of the problem is high. In RC-LMC, we use the same basic strategy: At iteration m, a single coordinate of x is randomly selected for updating, while all others are left unchanged.
Although each iteration of RC-LMC is cheaper than conventional LMC, more iterations are required to achieve the target accuracy, and delicate analysis is required to obtain bounds on the total cost. Analogous to optimization, the savings of RC-LMC by comparison with LMC depend on the struc- ture of the dimensional Lipschitz constants. Under the assumption that there is a factor-of-d differ- ence in per-iteration costs, we compare our results with current results for classical LMC (Dalllyan and Karagulyan| 2019 Durmus et al. 2019) and conclude the following:
1. (Theorem When the gradient of f is Lipschitz but the Hessian is not, RC-LMC costs ( /e) to get an e-accurate solution. Therefore, RC-LMC outperforms LMC, in terms of the computational cost, if f is skewed and the dimension of the problem is high, as discussed in Remark 4.1 The optimal numerical cost in this setting is achieved when the probability of choosing the 7-th direction is proportional to the i-th directional Lipschitz constant.
2. (Theorem 4.2 When both the gradient and the Hessian of f are Lipschitz, RC-LMC requires ((83/2/e) iterations to achieve e accuracy. On the other hand, the currently available result indicates that the classical LMC costs (a²2 (c). Thus, RC-LMC saves a factor of at least d regardless of the stiffness structure of f, as discussed in Remark 4.2
2

---

Under review as a conference paper at ICLR 2021
3. (Proposition 4.2) The ((d%/2 /e) complexity bound for RC-LMC is sharp when both the gradient and the Hessian of f are Lipschitz.
(The notation Ö()) omits possible log terms.) We make three additional remarks. (a) Throughout the paper we assume that one element of the gradient is available at expected cost of approximately 1/d of the cost of the full gradient evaluation. Although this property is intuitive, and often holds in many situations (such as the graph-based example presented above), it does not hold for all prob- lems (Wright 2015). (b) Besides replacing gradient evaluation by coordinate algorithms, one might also improve the dimension dependence of LMC by utilizing more rapidly convergent method for the underlying SDEs than (2). One such possibility is to use underdamped Langevin dynamics, e.g.. (Rossky et al. 1978 Dalalyan and Riou-Durand 2018 Cheng et al.] [2018] [Eberle et al.) 2019 Shen and Leel 20 19) Cao et al. 2019), which can also be combined with coordinate sampling. For the clarity of presentation, we will focus only LMC in this work and leave the extension to underdampped samplers to a future work. (c) It is also possible to reduce the cost of full gradient evaluation using stochastic gradient (Welling and Teh 2011) or MALA-in -iii--i-ibbbs sampling (Tong et al. 2020). However, both methods require specific forms of the objective function that are not considered in our work.
The paper is organized as follows. We present the RC-LMC algorithm in Section 2 Notations and assumptions on I are listed in Section 3 where we also recall theoretical results for the classical LMC method. We present our main results regarding the numerical cost in Section and numerical experiments in Section Proofs of the main results are deferred the Appendix.
RANDOM COORDINATE LANGEVIN MONTE CARLO
We introduce the Random Coordinate Langevin Monte Carlo (RC-LMC) method in this section. At each iteration, one coordinate chosen at random and updated, while the other components of unchanged. Specifically, denoting by r' the index of the random coordinate chosen at m-th iteration, we obtain + according to a single-coordinate version of ( and set m++1 = x for i * yM
The coordinate index nT can be chosen uniformly from {1,2.... 2,,,,...dd, dd; but we will consider more general possibilities. Let Φ; be the probability of component being chosen, we denote the distribu- tion from which TT is drawn by hb where
==
where o; > 0 for all i and Σi =1 1.
(3)
The stepsize may depend on the choice of coordinate; we denote the stepsizes by {h1, h2.... hd and assume that they do not change across iterations. this paper, we choose h; to be inversely dependent on probabilities o; as follows:
h
i- 1,
(4)
where > is a parameter that can be viewed as the expected stepsize. In Section 4.2 will find the optimal form of & under different scenarios. The initial iterate x." is drawn from distribution go. which can be any distribution that easy to draw from (the normal distribution, for example). We present the complete method in Algorithm |
4.3 we
When we compare (5) with the classical LMC I per iteration, meaning:
we see that only one random coordinate updated
fx(=²) + 0,. (x= )em, -
- e,m
where e, is the unit vector for i-th direction and 5Th is drawn from (0, 1). Define the elapsed time m-th iteration
372
m
hym and 7
(6)
then for f E (Tm, [mm] the updating formula 5 can be viewed as the Euler approximation to the following SDE:
Xym (t) = Xpm (I I"
2pm f(X(s)) V2 Tm dB.
v2/"
pm 7
(x(()= =x,(

---

Under review as a conference paper at ICLR 2021
Algorithm Random Coordinate Langevin Monte Carlo (RC-LMC)
Input: Coordinate distribution +b
{0i. ,....,,,.llll dat; parameter h 0 and stepsize set
(h1, bg,..., h defined in
M (stop index).
Sample 20 from initial distribution Qo
for m = 0, 1, 1.2,..... ... M do
1. Draw pd E (1, ...., d) according to probability distribution Φ;
2. Draw 5rh from (V, 1);
Update x=+ by
2
m
2
h,0,5(a²*) + 22h cm = rm
(5)
2
+ pm
end for return x.M
where B, a 1-dimensional Brownian motion. We will show in Section 4.1 that the SDE preserves the invariant measure, that is, (t) p for any > 0f (() p, and it is ergodic. The invariant measure of RC-LMC, which can viewed as a discretized version the SDE, is not exactly p. due to the unavoidable discretization error.
NOTATIONS, ASSUMPTIONS AND CLASSICAL RESULTS
We unify notations and assumptions in this section, and summarize and discuss the classical results on LMC. Throughout the paper, to quantify the distance between two probability distributions, we the Wasserstein distance defined by
W ( inf (X.)))
E|X- -1)) 1/2
where [(u, v) the set of distribution of (X E 2d2d whose marginal distributions, for X and Y respectively, and v. The distributions in I' I'( v/) are called the couplings of μ and v. Due to the use of power 2 in the definition, this is sometimes called the Wasserstein-2 distance. Here and in the sequel, we use |-| to denote the Euclidean norm of vector.
We assume that f is strongly convex, so that p is strongly log-concave. We obtain results under two different assumptions: First, Lipschitz continuity of the gradient of f (Assumption 3.1 and second,
Lipschitz continuity of the Hessian of í (Assumption together with Assumption B.1.
Assumption 3.1. The function I is twice differentiable, f is utsttnnglyy convex for some μ > 0 and its gradiens f is L-Lipschitz. That is, for all x' E Rdd we have
f(x) ((x')=VV(C))
x')
/
4
x112
(8)
2
and
- r'1.
It is elementary consequence of that
(Vf(z²) V (z'-x)2 n/20 x12 for all x e Rd.
(10)
Since each coordinate direction plays distinct role in RC-LMC, we distinguish the Lipschitz con- stants in each such direction. When Assumption 3.1 holds, partial derivatives in all coordinate directions are also Lipschitz. Denoting them as L, for each i 1,2, d, we have
|0,((z + te,) - 0.f(x) < [
(11)
for any & E Rd and any E R. We further denote T.ax = max; L2 and define condition numbers follows:
L/p21, R = Li/p 1, Kmax = max Ki
(12)
4

---

Under review as a conference paper at ICLR 2021
As shown in (Wright 2015), we have
L; S Limax L dlmaxx Kj S Kmax S K S drimax.
(13)
These assumptions together imply that the spectrum of the Hessian is bounded above and below for all x, specifically, pla 3 f²r(x) 3 Lla and [V*]( L, S Lmax for all Rd.
Both upper and lower bounds of L in term of Lmxx in 13 tight. If V f is diagonal matrix, then Lmax = L, both being the biggest eigenvalue of v Thus, Kimx = k: in this case. This the case in which all coordinates are independent of each other, for example f E, ALa On the other hand, if f e where E R satisfies = 1 for all i, then L dL and dKmax- This a situation in which f is highly skewed, that is, f = I; 22))
The next assumption concerns higher regularity for Assumption 3.2. The function f is three times differentiable and f is H-Lisschitz, that is || f(z) f f(r') I H| æ'1, for all x, x' Rd.
(14)
When this assumption holds, we further define H; to satisfy
[a + le:) 0x]((r)) S H:|l],
(15)
for any i == 1.2..... d, æ E Rd, and all E R. where 0.. [ I (1))] the (i, diagonal entry of the Hessian matrix V
We summarize existing results for the classical LMC the following theorem.
Theorem 3.1 (Durrmus al. 2019, Theorem 9), (Dalalyan and Karagulyan 2019] Theorem 5)). Let Im the probubility distribution of the m-th iteration of LMC (1. and p be the target distribution.
Using the notation Wm := W (gm=22 P), we have the following:
Under Assumption
3.1
let I/L, we have
Wm S exp (-phm/2) Wo + 2/xhd)
(16)
Under Assumptions
3.1 and 3.2 let h < 2/( L), we have
Hhd
Wm. I exp (-uhm) Wo +
+ 3 3/2 / 222
(17)
24
This theorem yields stopping criteria for the number of iterations M to achieve a user-defined accu- racy of When the gradient of f is Lipschitz, achieve e-accuracy, the right hand side (16) to be smaller than f/2, which occurs when
require both terms
(1 log ph
Wo (WW) (())) =
dn 2ce
Wo
h ( /ds). M M-G
log
(18)
leading to a cost of ((L (ue))) evaluations of gradient components (when we assume that each full gradient can be obtained at the cost of d individual components of the gradient). When both the gradient and the Hessian are Lipschitz, to achieve c-accuracy, we require all three terms on the right hand side of (17 to be smaller than e/3, Assuming d >>>>> and all other constants are O(1), we thus obtain
h = Olep((d + (2 M (H H + 1,32233/2
(
Wo
))
log
(19)
μ:ee
which yields a cost of O/ (n)²e) evaluations of gradient components. Here A = O(B) denotes cB A S CBB for some absolute constant and C.
MAIN RESULTS
We discuss the main results from two perspectives. In Section 4.1 examine the convergence of the underlying SDE (7). laying the foundation for the convergence in the discrete setting. We then build upon this result and show the convergence of the RC-LMC algorithm in Section 4.2 and 4.3
under two different assumptions. We show in Section 4.4 that when both Assumption and 3.2 satisfied, bound is tight with respect and
5

---

See proof in Appendix A Under some mild conditions, we can further prove that the solution to the SDE converges to the target distribution exponentially (Proposition|A..). Since x=", the samples generated by the algorithm can be viewed as discrete version of X" the algorithm then is expected to converge up to discretization error as well. This indeed shown in the upcoming two subsec- Under review as a conference paper at ICLR 2021
4.1 CONVERGENCE OF THE SDE 7
To study the convergence of we first let X = ((T") and denote the probability filtration by F {I", p"Sm, B.crm Then (X"m J== is a Markov chain and the following proposition shows its geometric ergodicity.
Proposition 4.1. Let X ((T") solve 7 If satisfies Assumption 3.1 and h then p(z) the stationary probability density of the Markov chain {X.
min de
4487 42254
Im=0"
tions, where we document the non-asymptotic convergence rate, and calculate the complexity of the algorithm.
4.2 CONVERGENCE OF RC-LMC. CASE 1: LIPSCHITZ GRADIENT
Under Assumption 3.1 we have the following result. The proof can be found in Appendix B
Theorem 4.1. Assume I satisfies Assumption 3.1 and h; tbe with h kminto.) Let qu be the probability distribution of xm computed W W (gm. p). Then we have
SL²
let be the target distribution, and denote
phm
5h
L Ø
W S exp
Wo
(20)
1
We make few comments here: (1) the requirement on h is rather weak. When both μ and L are
moderate (both (1) constants), the requirement essentially S 1/d. (2) The estimate (20)
consists of two terms. The first is an exponentially decaying term and the second comes from
variance of random coordinate selection. If we assume all Lipschitz constants L; are of O(1),
this remainder term roughly (l)/2d)) (3) The theorem suggests a stopping criterion: to have
WM S e, we roughly need < <²// /²/d,, and M = (dd /e2), assuming L; = ( In terms of and d dependence, this puts M at the same order as (18), as required by the elassical LMC.
Theorem 4.1 holds for all choices of {s..} satisfying (3) From the explicit formula (20) we can choose { minimize the right-hand side of the bound. Nesterov (2012) proposed distributions & that depend on the dimensional Lipschitz constants L;, i 1,2,.... from (II). For E R, we can let (a)) x LJ, specifically,
L and F(a) = (z))))))))).......)))))))))) (a(a))
Φ.(a) =
(21)
Σg
Note that when a = (0) 1/d for all i: the uniform distribution among all coordinates. When > 0, the directions that with larger Lipschitz constants have higher probability to be chosen. Since h; = h/ one uses smaller stepsizes for stiffer directions. (On the other hand, when a 0, the directions with larger Lipschitz constants are less likely to be chosen, and the stepsizes are larger in stiffer directions, a situation that is not favorable and should avoided.) The following corollary discusses various choices of and the corresponding computational cost.
Corollary 4.1. Under the same conditions as Theorem 4.1 with di = di(aa) defined in 21), (K2-aKa Ka log ( (Mo)). where 1²²
the number of iterations M required to attain WM S is M θ
K. = Ede Ng. This cost is optimized when for which we have
M M= ( (I log
Wo
(22)
1
See proof in Appendix We note that the initial error Wo enters through log term and essen- tially negligible.

---

Under review as a conference paper at ICLR 2021
We now compare the numerical cost of RC-LMC and LMC in Case 1. We separate the discussion on uniform sampling (o: = 1/d) and the optimal sampling (Ør x L,) below.
Remark 4.1.
Optimal sampling: According to Corollary 4.1 the optimal sampling strategy is achieved when 1, meaning Φ; x Li In this case, we compare (22) with (18). adjusting (18) by a factor of d to account for the higher cost per iteration. RC-LMC has more favorable computational cost if
dx 2
Σ Ki
Considering K4 S Kmax S KR S. drmmax as presented in (13), this is guaranteed ka In the regime when K. r dKmax this holds so long as d >> Kmaa meaning the dimension of the problem is high. And in the regime when Nmax K, RC-LMC still oupperfrms when fig decreases fast. One example is to set f(x) = dxद + Eimg with >>
-Uniform sampling: Uniform sampling means Φ, 1/d for all i, with a = in Corollary 4.1 Σ pe
This leads to a cost of that RC-LMC still has favorable computational cost if
log (M=)). Comparing with (18) adjusted by a factor of we see
d
Σ> R
As in the optimal case, this happens when f is highty skewed.
Our proof of Theorem follows from a coupling approach similar to that used by [aalalyan and Karagulyan| (0199) for LMC. We emphasize that for the coordinate algorithm, we need to overcome the additional difficulty that the process of each coordinate not contracting on the SDE ( level. This is different situation from the classical LMC (Dalalyan and Karagulyan 2019) whose corre- sponding SDE (2) already provides the contraction property and thus only the discretization error needs to be considered. Despite this, the algorithm RC-LMC still enjoys the contraction property that ensures that the distance between two different trajectories following the algorithm contract. However, this contraction property is not component- wise, wisely and take summation of every coordinate. The summation will also produce some extra terms, which need bound. Dalalyan and Karagulyan (2019) obtains estimate for the cost of the classical LMC of kd )[.c)).. Compared with this estimate, our estimate for the cost of RC- LMC is always cheaper (since x² 2 Kmaa).. The improved estimate of the cost of LMC (88) was obtained by Durmus et al. (2019) using a quite different approach based on optimal transportation. It is not clear whether their technique can be adapted to the coordinate setting obtain an improved estimate.
need to choose Young's constant
4.3 CONVERGENCE OF RC-LMC. CASE 2: LIPSCHITZ HESSIAN
We now assume that Assumption 3.1 and 3.2 hold, that is, both the gradient and the Hessian of f Lipschitz continuous. In this setting, we obtain the following improved convergence estimate. The proof can be found in Appendix C
Theorem 4.2. Assume I satisfies Assumptions/ 3.1 and 3.2 and let h h dr. with h < 1 ..min (b.).
81.2
Denoting by qm (2) the probability density function of x computed from (5) and by p the target distribution, and letting W == W (gm. p), have;
(- julm
Wo + 3h
H1?) /
Wm 5 exp
Σ
(23)
4
We see again two terms in the bound, an exponentially decaying term and a variance term. Assuming all Lipschitz constants are (11), ). the variance term is of (hd33/2) By comparing with Theorem see that error can be achieved with the looser stepsize requirement h. S 7572-
By choosing ( to optimize the bound in Theorem 4.2 obtain the following corollary.

---

Under review as a conference paper at ICLR 2021
Corollary 4.2. Under the same conditions as in Theorem 4.2
the optimal choice of { is to
(L) + H2)) 1/3
Φ1 EL (L + H2)
For this choice, the number of iterations M required to guarantee WMr S satisfies
[i (L) H3)
E (I) + H?) 1/3
1/2
Wo
=
log
(24)
1²cc
If Hr and H; all constants of O(1), then the total cost is O /c) regardless of the choice of {0i}-
Remark 4.2. We now compare RC-LMC with LMC in Case using Theorem and Corollary 4.2
We still separate the discussion on optimal sampling and uniform sampling strategy.
Comparing the cost shown in and the cost of LMC ( (19) adjusted by factor of d to account for the higher cost per iteration), see that RC-LMC always has a more favorable computational cost since
Optimal sampling: This is to set Ø; as stated in Corollary 4.2
24
d + 83/2 2 12)2/2
(Here we relaxed
24
using I4 5 L, H
S H.)
Uniform sampling: This is to set Φ; 1/d in
23
Then the total cost of RC-LMC is
E (L + H1
1/3
3/2
Wo
M
log
p2c
according to Corollary4.2 4.2 Comparing with (19) adjusted by a factor of d as the cost for LMC, and use the fact that L S L, He S H, is clear that RC-LMC always cheuper, similar to the optimal case.
Suppose L and are all constants of O1),, then the cost of RC-LMC is roughly O(8/2/e), while the classical LMC requires O(L fe), according to Dalalyan and Riou-Durand 20188) This represents savings factor of d2//2, regardless of the structure of J.
4.4 TIGHTNESS THE COMPLEXITY BOUND
When both the gradient and the Hessian are Lipschitz, we claim that estimate ((d3/2/e) obtained Corollary 4.2 is tight. An example is presented in the following proposition.
Proposition 4.2. Let d: for all i, and set the initial distribution and the target distribution to be:
(o(x)= (4 (4m) exp -1//44 e//44, p(x) = (2m)a/22 exp((1xx111)
(25)
where e E d satisfies e; = 1 for all i. Let qm be the probability distribution of am generated by Algorithm and denote Wm W (qm, p). Then we have
Vd.
1/2
Wm 2 exp (-2mh)
2 1.
(26)
3
6
In particular, to have WM one needs at least M = 0(63/2/0) /e).
See proof in Appendix D
8

---

Under review as a conference paper at ICLR 2021
5 NUMERICAL RESULTS
We provide some numerical results this section. Since it is extremely challenging to estimate the Wasserstein distance between two distributions in high dimensions, we demonstrate instead the convergence of estimated expectation for given observable. Denoting by (x(").), Ta=1 the list of N samples, with each of them computed through Algorithm Algorithmnnndeepnnnee Iideppendenly with M iterations, we
define the error follows:
E,ToUM,N =
Σ N ==1
(2x()MM) Fx (+b)
(27)
where & is matrix function and (+b) is the expectation of de under the target distribution p. As h - 0 and Mh - 0o, have WM + O, and (0. can be regarded as approximately sampled from According the central limit theorem, we have 1im Errоr O(1/vN).
In this example, we set the target and initial distributions to be Gaussian p(x) x Pı (x)p2(()) and (x) x p1 pi(( ()) with
(i(x) exp (-2x (d/10)z)* (T+ (d/10)1)x*) P2 exp (d/100)))
where (21, P2.-..,, F10) ee (1, 1)T TR.0, 7 is the identity matrix and T is random matrix with each entry i.i.d. drawn from (0, We run the simulation with N = =10%, and we compute Error with (xx)) xx This measures the spectral norm of the covariance matrix of the first 10 entries.
The results are shown in Figure We run RC-LMC with time stepsize h 10-5 and 1. following (2I). It is unclear what stepsize h to choose for LMC to yield fair comparison. Bearing 100 in this example, so that the per-iteration cost of LMC 100 times of that
in mind that of RC-LMC, we try first h = 10-3, It is clear that RC-LMC, presented by the purple dashed line, achieves lower error than LMC the same cost, before achieving the error plateau. Next, we try smaller choices of h in LMC. The choices h .0008 and h .0005 yield slower decay rates (see the red (star) and yellow (circle) lines, respectively), but lower error plateaus as well, meaning that the saturation error is smaller. However, computation required to reach these plateaus is longer, and the plateaus are still higher than for RC-LMC.
10
LMC, h=10-3
100
LMC, h=8*10
LMC, h=5+10-4
Emor
RC-LMC, h-10
10
10"4
2000
4000
6000
8000
10000
12000
14000
Cost
Figure 1: The decay of error with respect to the cost (number of 0f calculations).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andrieu, C., Freitas, N., Doucet, A., and Jordan, M. (2003). An introduction to MCMC for Machine Learning. Machine Learning, 50:5-43.
Baydin, A. G., Pearlmutter, A., Radul, A. A., and Siskind, M. (2017). Automatic differentiation in machine learning: A survey. J. Mach. Learn. Res., 18(1)559555637.
Cao, Y., Lu, J., and Wang. L. (2019). On explicit L'-converee rate estimate for underdamped langevin dynamics. arXiv preprint arXiv:1908.044 04746.
Casella, G. and George, E. I. (1992). Explaining the gibbs sampler. The American Statistician, 46(3):167-174.
Cheng, X., Chatterji, N., Bartlett, P., and Jordan, M. (2018). Underdamped Langevin MCMC: A non-asymptotic analysis. In Proceedings of the 31st Conference On Learning Theory, volume 75, pages 300-323.
Dalalyan, A. (2017). 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.
Dalalyan, A. and Karagulyan, A. (2019). User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278 5311..
Dalalyan, A. S. and Riou-Durand, L. (2018). On sampling from a log-concave density using kinetic langevin diffusions. arXiv, abs/1807 018800077....
Del Moral, P., Doucet, A., and Jasra, A. (2006). Sequential monte carlo samplers. Journal of the Royal Statistical Sociery: Series B (Statistical Methodology), 68(3):411-43)
Duane, S., Kennedy, A., Pendleton, B. J., and Roweth, D. (1987). Hybrid monte carlo. Physics Letters B, 195(2):216- 222.
Durmus, A., Majewski, S., and Miasojedow, B. (2019). Analysis of langevin monte carlo via convex optimization. Journal of Machine Learning Research, 20:73:1-73:46.
Durmus, and Moulines, É. (2017). Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm. Ann. Appl. Probab., 27(3):1551-1587,
Eberle, A., Guillin, A., and Zimmer, R. (2019). Couplings and quantitative contraction rates for Langevin dynamics. Annals of Probability, 47(4):
Evensen, G. (2009). Data Assimilation: The Ensemble Kalman Filter. Springer-Verlag Berlin Heidelberg.
Fabian, P. (1981). Atmospheric sampling. Advances in Space Research, 1(11):17
Geman, S. and Geman, D. (1984). Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell., 6:721-741.
Geweke, J. (1989). Bayesian inference in econometric models using Monte Carlo integration. Econometrica, 5716)133
Hastings, W. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97-109.
Iglesias, M., Law, K., and Stuart, A. (2013). Ensemble Kalman methods for inverse problems. Inverse Problems, 255000.
Li, R., Pei, S., Chen, B., Song. Y., Zhang, T., Yang, W., and Shaman, J. (2020). Substantial undoc- umented infection facilitates the rapid dissemination of novel coronavirus (sars-cov-2). Science, 368(6490):489-433,
10

---

Under review as a conference paper at ICLR 2021
Markowich, P. and Villani, C. (1999). On the trend equilibrium for the Fokker-Plance equa- tion: An interplay between physics and functional analysis. In Physics and Functional Analysis, Matematica Contemporanea (SBM) 19, pages 1-29.
Mattingly, J., Stuart, A., and Higham, D. (2002). Ergodicity for sdes and approximations: locally lip- schitz vector fields and degenerate noise. Stochastic Processes and their Applications, 101(2):185 232.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6);
Nagarajan, N., Honarpour, M., and Sampath, K. (2007). Reservoir-fuid sampling and characteriza- tion - key to efficient reservoir management. Journal of Petroleum Technology, 59.
Neal, R. M. (1993). Probabilistic inference using Markov Chain Monte Carlo methods. Technical Report CRG-TR-93-I, Dept. of Computer Science, University of Toronto.
Neal, M. (2001). Annealed importance sampling. Stutistics and Computing, 1 11:125-139.
Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems. on Optimization, Sournal 22(2):341-365
SIAM Journal
Parisi, G. (1981). Correlation functions and computer simulations. Nuclear Physics B, 180(3):378- 384.
Reich, S. (2011). A dynamical systems framework for intermittent data assimilation. BIT Numerical Mathematics, 51(1):235-249.
Roberts, G. and Rosenthal, (2004). General state space Markov chains and MCMC algorithms. Probability Surveys, 1.
Roberts, G. and Tweedie, R. (1996). Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4):34
Rossky, P. J., Doll, J. D., and Friedman, H. L. (1978). Brownian dynamics as smart monte carlo simulation. The Journal of Chemical Physics, 69(10))4628 4633.
Russo, D., Roy, B., Kazerouni, A., Oshand, I., and Wen, (2018). A tutorial on Thompson sam- pling. Foundations and Trends in Machine Learning, 11(1):1-96.
Shen, R. and Lee, Y. T. (2019). The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems, pages 2100-2111.
Tong, X. T., Morzfeld, M., and Marzouk, Y. M. (2020). MALA-within-Gibe samplers for high- dimensional distributions with sparse conditional structure. SIAM Journal on Scientific Comput- ing. 4273):A1765-11777
Vempala, S. (2010). Recent progress and open problems in algorithmic convex geometry. In JARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 8, pages 42-64.
Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I1), pages 681 - 688.
Wright, S. J. (2015). Coordinate descent algorithms. 151(1)33-34.
Mathematical Programming, Series B,
Xu, P.. Chen, J.. Zou, D., and Gu, Q. (2018). Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems 31, pages 3122-3133.
11

---

Under review as a conference paper at ICLR 2021
A
PROOF OF PROPOSITION 4.1
We recall the SDE
f" Xpm (t) = (I - 0pm f(X ds + v2 Tm Tm X,(t) = (x(t) Vi *f
dB.,
(28)
where pm is randomly selected from I....,d. d. Moreover, recall that X = X (Imtt) is Markovian process. We denote its transition kernel by E, meaning that
X E(
Moreover, we denote =" the n-step transition kernel. following Proposition.
Proposition
4.1
is consequence of the
Proposition A.1. Denote I1 the probability distribution of XT and II be the probability distribu- tion induced by p(z), then under the conditions of Proposition 4.1 we have
II is the stationary distribution of the Markov chain (xm Dc
m==0'
If the second moment of II is finite and X is drawn from II., then there are constants R > 0 and >> 1, independent of m, such that for any m 2 0 we have
drv (II II) dx S Rrm
(29)
Remark A.1. According to Mattingly el al.) (2002), the constants R and do not depend on m, but their dependence on other parameters such as h, d, and L is hard to trace. This contrasts with the results in Dalalyan and Karagulyan (2019) for the classical Langevin dynamics, which are built upon the contraction property. The new complication comes mainly from the complicated coordinate selection process, making the contraction property no longer available. Nor can we claim sharpness of the theorem. In fact, unlike in Dalalyan and Karagulyan (2019); (uu et (2.188) where the authors directly studied LMC, we discuss here only convergence of the SDE, the continuous version of RC-LMC. The explicit dependencies of the convergence rate here unimportant, and we allow the results to be loose. Non-asymptotic convergence results of the algorithms are presented in Section an2
To prove Proposition A. we need to introduce the following lemma:
Lemma A.1. Under conditions of Theorem 4.1 there are constants Rí > 0, > 1, such that for any 20 E Rd
Emd (2", / p(x) dx < (120 -124-1112- + Riri"
sup AEB(R()
(30)
where x² is the minimal point of fz) and E is the transition kernel for {X* yo m=
We postpone the proof of Lemma A.I to Section A. Now, we are ready to prove the proposition.
Proof of Proposition A.7 (Proposition 4.7). To prove the first bullet point of Proposition A.1 we
assume the distribution of X is II and we need to prove:
For any choice of Th the conditional distribution of X is also IL.
Without loss of generality, we consider mm = 1. Under this condition, we have the following.
The distribution of X25)şa(t) between [T | 1m preserved.
12

---

Under review as a conference paper at ICLR 2021
For fixed 22, 2z. ................................ 2d. the stationary density of SDE
de f2, 22, 23, ................................ 2a) dt v2dB.
(31)
is expl expl--(lan ((pl-f((itzmmaa) This implies that the conditional distribution of Xi(() with fixed X2gjsa(t) (t) is also preserved.
Combining these two points, find that under condition yd 1, the conditional distribution of Xm+1 is II, which further proves that II is the stationary distribution and Proposition 4.1 holds.
To show (29). take the expectation of (30) using II", then obtain that for any A E Bg hat
(A) - IT(A))
!
Err (Emd (,, ()) -Ero (/s ((oo) (x)
(1T)
Er [ (z, / p(x) dæ
(1I
2²12 S RiTi / 112-20 + go(2) dz < Cori",
where we use X d End :) and II(A) = SA p(x) dx in (4), 11 is non-negative measure in (IT) and (30) in (IIT). Since this is true for all Byd, we have
(I III = sup
I (4) - I1T (A) < CorT"
(32)
A
By using 28 with Itô's formula, we have
dE) N, (1)1
2E (0pm f(X mm ()) (t)) + +2 2 2 f(X, (t))1+ + E, (t) 2 + Tm E. X (1) - x. E, (1) < 1m BJ x (1)) C2
dt
where C1,rm and C2,rm are constants that depend only on x² and Lpm. From Grönwall's inequality, we obtain
E (1x:++1121)) i) s exp((i,:ht) B(I (3) + C2.chi), for all 1, 2, d. Then, if E, Xm oc, we have for any = 1, 2, .,, that
1 ب (Ix: pm =i) + (1- (1xxet112) +i)
1 exp(Cr, [E(XTT)) + C2 + (1- R( [(( < 00,
< d
which implies x1 < oo. Therefore, if 11 has finite second moment, then IIf all have finite second moments for l,....d d 1. Suppose the initial data drawn from 1I2 for then taking the expectation of (30) and using (32). we obtain
(I II) Crri"
where C. is a constant. This bound holds true for all 0 s i S d - 1, we set R = =mmax; C₁)rı and 1/d
ri to obtain (29).
A. PROOF OF LEMMA
Before prove the Lemma, first recall result from (Mattingly et al. 2002) for the convergence of Markov chain using Lyapunov condition together with minorization condition.
Theorem A.I. MMattingg et 2002 Theorem 2.5)] Let {X") denote the Markov chain on ddd with transition kernel = and filtration F Let {X" "") jo satisfy the following two conditions:
13

---

Under review as a conference paper at ICLR 2021
Lyapunov condition: There is function L I2 - [1, oo), with lim L(x) cc, and real numbers a E (0, 1). and B E [0, 00) such that
E (L(x S al(X")+ +
Minorization condition: For L from the Lyqpumov condition, define the set C C R follows:
C C= C=<EER" L(x) - 7 -
2,3
(33)
for some E (a2/221), Then there exists an 1j > and a probability measure M supported on C (that is, M(C) = 1), such that
(l,,A)2M((L AA E B(R"), ZEC.
Under these conditions. the Markov chain {X"] In=o has unique invariant measure Further- more, there are constants E (0,1) and R E (0, 00) such that, for any 20 E Rd, we have
sup AEB(Rd)
E A) (A)l - Rer
(34)
To use this result to prove Lemma A.1 we will consider the d-step chain of {X") and verify the two conditions, in the following two lemmas for the Lyapunov function and the minorization over a small set, respectively.
Lemma A.2. Assume satisfies Assumption
and
[
(35)
8I. + 32T,4
where L is the Lipschitz constant defined in 99 Let the Lyapunov function be L(x) = 1x =x=-="12 then we have:
+
E (L(X
Fm) ar L(x + Bı
(36)
with
01 1- ph, B1 (24 120L +1)h.
Lemma A.3. Under conditions of Lemma
A.2 with L(x) 1=1=x112 22+,,,, let 3 denote the transition
kernel. Define the C TRd in 33 for some 1/2 1). Then there exists an 1) and
probability measure M with M(C) = such that
Ex,, A) 2 mM(A),
AA E B(R"), IE
(37)
Lemma A.I follows easily from these results.
Proof of Lemma A.7
It suffices to show d-step chain {_xmd] m satisfies the conditions in Theo- af and d31, and is induced by p. We apply (36)
rem A.1 with L(x)
Jar 1²
from Lemma A.2 iteratively, d times, to obtain
E (x((+))d))
) FFmd) S of (xmi) + d31,
which implies that md 0e J mm=0 satisfies Lyapunov condition in Theorem A. with a af More- over, Lemma A.3 directly implies that the d-step transition kerel satisfies the minorization condi- tion. Therefore, by Theorem A.
we have
= mdd (z", - +(A)] < L(=")Rr-"
sup AEB(R4)
which concludes the proof of the lemma when we substitute (AA) SAP(D) p(x) dr.
14

---

Under review as a conference paper at ICLR 2021
Proof of Lemma A.2 We assume without loss of generality that x" = 0 E R (so that L(x)
|x| 1) and drop the filtration Fm in the formula for simplicity of notation. Then
E (I = Σ B (L (I =1)
(38)
Since
L (x = 1x = - + (Xm+1 - x²) +
=x + (x - X x - xm11
we have
E (L (Xm+t)) =1) =1 (x 2I [xTT (X.rt1 x-")
(39)
+ (x:
X pm =
To deal with second term and third term in 339. we first note that, under condition ym
T Th +hi
+he
X X
0.f(X(s)) ds + v2
dB,
(40)
Tm
Tm
This means
2E
[x] (xm++1 =
th;
= 2E
X
Orf(X(s)) ds T
Tm
(41)
=-
2hxxx"' - 2F
x
- ds dm
m
We further bound the second term (41)
T
- do d
Tm
X.n
sup
(1)
2 2h X,mm1 2
(0,((((1)) 00
sup The TmSisTT4h
(42)
(1)
21/1Xm11 + 21,7
(i(1) X.m1 x
sup TmSIST"th
(mT)
< 21 1 16h 410. 60
(IV)
< (2 + 162, 16L,)
60h
where we used Young's 's inequality in (I), the Lipschitz condition in (II), Lemma A.4 below (specif-
ically, inequality 45 in (III), and the Lipschitz condition again in (IV). This, when substituted into 41), gives
21
[x:" (x (T" = s -2h,X, Ox")) + (4+ 32L p 2 + 120h,
15

---

Under review as a conference paper at ICLR 2021
To bound the third term in (39). again for the case r.hh
(40)
again for:
(x
x:
T th
2
(x)( V2 dBs
m
pm
(1)
(x:S(X(1))1 .T =1) 4TE
T th,
2
TT
sup TmsIITTmH
1
dBg
y
=
(43)
(x.f(X(t))) yT =1) the
=2h²E
sup TT
(II)
I Sh 88h L3 4h,
(m))
8T 1 24h;
where we used Young's inequality in (I), Lemma A.4 below (specifically, inequality 44 in (II),
and Lipschitz continuity in (III), together with 88h L 20 by (35).
Finally, we have E (L
= S (X"" 22, 24
By summing according
38 and using and S for all 1, ... d. obtain
E (L (x
Σ è (L (x++1) =i)
L (X 2h (xmm, Vf((")) + (4 4 8T.2 32T.1) h
min(ó.} (X - 1) - (24 + 120L
Finally, using (X m vf(x")) 2 (X 1) (from 10 with x'
X and x 0) and
35
we obtain 366
Proof of Lemma To prove 37 we construct new Markov process Xm. Defining X = x
we obtain X from X by running the following process:
hir
70 = 0. Z(0) = x
i=1
Then for 7 S/5 n and n S d, let
Zn)( = Zn [in11
Fin- 2n (2(s)) ds + V2 dB..
(i(t)= = // (m-11) i i n,
and set m (Td) Denote the transition kernel by E.y (corresponding to one round of cyclic version of the coordinate algorithm). We then have the following properties:
For any C' and ((Rd)) we have
=d (sr A) 1, (21, A) 0.
Eey possesses a positive jointly continuous density.
According to (Mattingly et al.
2002 Lemma 2.3), since Egye has a positive jointly continuous den-
sity, there exists an 1f and
probability measure M with M(C) 1, such that
Esye (2., A) (AM, AA B E C,
16

---

Under review as a conference paper at ICLR 2021
which implies
(xx A) 2 IT: i= 0i Eeyc (I, A) Ti=IosnMMA)) VAEB(R)),ECG EEC.
This proves 37 by setting 1/ i= 1
In the proof of Lemma A.2, we used several estimates in inequalities 42 and 43 estimates in the following lemma.
We prove these
Lemma A.4. Suppose that the assumptions of Lemma A.2 hold, and let X, evolve according to 40
Then we have the following bounds:
E
sup
4(0.((x'')) (.f(((())1 3
44h,L?
(44)
T SISSTT thi
sup T mIn
[i(()) - X((1)-Xm1? s {1 30h,
(45)
Proof. To obtain
we have
(0.f(X(t)))²
E
sup
T'm STsT h
(10:((x*')| La (x(()) - X,m)2
<
sup
(46)
T TnsisTnth
< Oxf"( +L,
{i((t) X
sup Tm
To bound the second term, we use
40 again:
(x(() - x
sup T' TmhttsTmhh
I' 0. (X(s)) ds - V2 f fm
=B
sup T TmS
ds-
dB,
I
(47)
[ dB,
2
<2h;E
(0.f(((t))P) + +4E
sup (
sup
Tm
(0.f(X(t)))) + 16hs, T SI
sup
where we use Young's inequality and
I dBg
< 4E ( dB,
E
sup
4h
by Doob's s maximal inequality. By substituting 47 into 46). we obtain
E
sup TmSiSTT4h
(x,((((1))1
<A
0. (.f(X(t)))) + 2|0.f(XX') 32h,
sup
TT
Using Li S 1. we move the first term on the right the left to obtain
E
sup
(.f(((t)))?
2(a,f(X'')) + L2
TmSisTT4h
leading to Then we obtain
(45) by plugging this in 47) and using the fact that 88h L? < 14h;
by 35
17

---

Under review as a conference paper at ICLR 2021
B PROOF OF THEOREM 4.1
The proof of this theorem requires us to design reference solution to explicitly bound (gm. p). Let 5 be random vector drawn from target distribution induced by p. that W2 p) [E| =013. We then require à to solve the following SDE: for E (T Tm with T defined in
JT a, f(((f ds v2 l dB..
3n 3, (T
(48)
at( 2z (T
i r
If we use the same Brownian motion as in ( have
im+1 5m
f ds + 2h, c
e,m
(49)
where e,.m is the unit vector in y.m direction. Since the --tth marginal distribution of z(t) is preserved in each time step according (48). the whole distribution of =(t) is preserved be p for all t. Therefore, by the definition Wm. W (qm. p), we have
W m2
E x
where
x
(50)
This means bounding Wm amounts to evaluating A 22 Under Assumption 3.1 we have the following result.
Proposition B.1. Suppose the assumptions of Theorem 4.1 are satisfied and let {x {ā }. and
{Am) be defined in 48 and (50). respectively. Then, have
hy 2
10h2
d
L2
22 <
E
(51)
The proof of this result appears in Appendix B.1
The proof for Theorem 4.1 is now immediate.
Proof of Theorem
4.1 By iterating (T.. we obtain
h4p
20h
1
E A <
E
Σ
Ø
1=1
and since hu/2 E (0, 1), we have
uhm
20h
L3
2
2 < exp
(52)
122
By construction, we have W (90.p)
2 p)
E 1 and 3 p) < E By taking the square
root of both sides and using a² < 12 + 2 S + e for any nonnegative a, b, and e, we arrive at 20
The proof for Corollary 4.1 is also obvious.
Proof of Corollary 4.1 To ensure that Wm S e, we set the terms on the right hand side of (20)
to be smaller than e/2, which implics that
2W,
h= 0
and
log
(53)
100
Ed d
ph
o.(a)
By using the definition of (a)) according to
21
we obtain
d
L?
d Σ 1=1
= 12
K2
(a)
1=1
18

---

Under review as a conference paper at ICLR 2021
which implies that Ō ((K2-aKa) ((K2-aaa)/(Hc))) Furthermore, because:
1 gives the optimal cost,
2
K2-aKa=
k
Σ Ki
K1
due to Hölder's inequality.
B. PROOF OF PROPOSITION B.1
We prove the Proposition by means of the following lemma.
Lemma B.I. Under the conditions of Proposition B. for m 2 0 and i = 1, 1, ...,,...d .d, we have
1/2122
B B <
1 + 11+hp+
E
E
2h (0,f(""") 0,f(x")))
Φi
(54)
3/2
2h L3 pof
8h
1 ( 0xf(=
pcd.
Proof. In the m-th time step, we have
P(r = 1) Φi: PP(r + 1) = Φ5.
so that
E
3, (1 -.ر -1= (
t +1 r #
(55)
&. (1A," -T -1)
We now analyze the first term on the right hand side under condition p = i. By definition of A m++1 we have
A m+1 = AT + (a:
3:Th) (x) x²
h.
( 1T
= AT +
O.f()(s)) ds + /22i5m
O.s(x") ds + v 221mm
Tm
T +h;
A
(O.f(ā(s)) (z((x ds
T
A
m
(0:1(f(s)) - O,5( + - ds
Tm
Th (0.((5(s)) ()"("²))) ds
A h; (ā 0x](x²"))
Im
= A h: (z.) 0zf(x² - vm
(56)
where we have defined
+h;
Vm
- ds.
(57)
Tm
By Young's 's inequality, we have
E [IAm+1p m =i) + v vmn n =)
E (IA A
(1 a) E (1Am-- m nm = i) + (1+
1+
1
E ""
(58)
where > 0 is parameter to be specified later.
For the first term on the right hand side of (58) we have
E (IAm +1 + T 2 TT = i)
= =E m h: (3: (x²')) 12
E| - 2 [A (a:f(am) O, ff (xx² 1 -..(
(59)
19

---

Under review as a conference paper at ICLR 2021
Note that the second term will essentially become the second line in (54), and the third term will become the third line in (54) (upon the proper choice of a). For very small h, this term is negligible.
For the second term the right-hand side of (58), recall the definition 57 and obtain
the
E (IVT)2
i)
v hi
E ((0.f(((()) 0, 3, 1 pm = ds
(
+hs
(ī())) - xtm - P/pm =i) ds
h
E
Tm
m thi
2 pm = ds ( O,s(T(()) di v2(B, Brm))
T
(1))
2h
thi
E (m =1) dt css
Tm
Tm
+h,
+ 4h L?
E ds
T
m h: LEE (10,f(Em)) PP) + 4h
1 10:11 + Th S 1 + +h,
(60)
where (II) comes from L-Lipschitz condition (TI. (I) and (III) come from the use of Young's 's in-
equality and Jensen's 's inequality when we move the -. 112 from outside to inside of the integral, and (IV) and (V) hold true because (tt) p for all In (VI) we use Epla,f? I L; using (Dalalyan
and Karagulyan 2019 Lemma 3).
By substituting (59) and (60) into the right hand side of 58) obtain
(IA mmmm+ 1 TT =)
< (1 + a D) 2h, (1+(1+)))11 (0.f(im)-00)
(M. 0xf(x))) + - (-)
+ (1+ 2 (1. + +1h
(61)
By substituting (61 into 55). we have
E| Am++12
< (1 + ac.)) ) E AT 2 22(1 + a)hE A (0:J(***) - Oz](1=
+ (1 + h
1) a)
h T.
4h
E Ela.f(² - 0,f(x²) )2 + 1+
+
(62)
Φ
where we have used hach = h.
Now, we need to choose a value of > 0 appropriate to establish formulas, we see the need to set
54p
By comparing the two
hp
aΦi
hyp
a huj4 S.
since h < min miin(o)//u. It follows that 1 +
2d bys
By substituting into 622
we obtain
E JA++1
mm+1+
(1 + h4) 12 2hE An ((0t(("")=0((=="))
2h 1
2h2
E
(AT (0, 0, (x'
-
0,
Φ4
Φ1
21
L
8h-
(63)
HØ:
We conclude the lemma by using the following Bauchy-Schwarde inequality to control the third term on the right hand side of this expression:
2h P E "A (0.(("T) 0,f(x")))
h²p²
h2
2
-EO.((>>)) - a.( L
6i
Φ;
Φ
20

---

Under review as a conference paper at ICLR 2021
Proposition B.1
obtained by simply summing all components in the lemma.
Proof of Proposion B.1 Noting
A
we bound the right hand side by
(54) and get
h² h²2²
+ hyp
24E T
VS(T")
()(a))))
min
(64)
3h
2h d
L
8h
d
L3
+
V vf(x') +
The second and third terms on the right-hand side can be bounded terms of A
By convexity, we have
E E
(65)
As the gradient L-Lipschitz, we have
E VVV(("")
()= S T.
(66)
By substituting (65) and 66 into 64
and using μ S L, we obtain
4h
2h d
8h
13
hy + min m
EA 2 +
(67)
If we take h sufficiently small, the coefficient in front of E E| Th |2 is strictly smaller than ensuring the decay of the error. Indeed, by setting h < pminfor) we have
SL
22
hpp
hL,
< 1
and
$
min [
2
8L.
which leads to the iteration formula (51)
C PROOF OF THEOREM 4.2
Theorem 4.2 is based on the following proposition.
Proposition C.1. Suppose the assumptions of Theorem 4.2 and let {x" tTth,, and {Am} be
defined as in 5. 48 and (50), respectively. Then we have
E EA < (1
hi44
4h
(L H1?)
(1-2
E
T
(68)
We prove this result in Appendix C.1 The proof of the theorem is now immediate.
Proof of Theorem
4.2
Use
68
iteratively, we have
hu
8122
d
[L3 +
H?)
m
< (
22
11
i=1
pum
8h
d
[T3 + H?
< exp
E
0
2
1
1=1
Using 122 p) = 2 and ( p) & E
A
m
2 we take the square root on both sides, we
obtain 23
21

---

Under review as a conference paper at ICLR 2021
The proof of Corollary 4.2 is also immediate.
Proof of Corollary 4.2
Use 23 to ensure Wm S we set two terms on the right hand side of 23
be smaller than e/2, which implies that
c/p
2Wo
h 0
log
(69)
(1++
wh
0f
To find optimal choice of oi. need to minimize
( + H3)
of
under constraint Σ Φ; = and di > 0. Introducing a Lagrange multiplier À R, define the Lagrangian function as follows:
(L H
F(bi, 02. ... da A)
+
Σ di
-1
By setting OF/06; 0 for all i, and substituting into the constraint
Σ di
1 to find the appro-
priate value of X, we find that the optimal (Ø1, $2,..., 0a) satisfies
[L + H2) 1/3
Φi
1= .d
Σ (L) H2)
By substituting into 669
we obtain
24
C.1 PROOF OF PROPOSITION
The strategy of the proof for this proposition is almost identical that of the previous section. The reference solution ă is defined as in (48). We will use the following lemma:
Lemma C.1. Under the conditions of Proposition
C.1
for m 2 and = 1,2,...,. ..,,,,,, d, we have
E A
hu
E
E|TT
24 (0. (x
Φi
3h2
4h (L + H?)
+ E
0,f
(70)
Φi
oi
Proof. In the m-th time step, we have
P(r" = 1) 0b; P(r + Φs.
meaning that
EA 0,E (1 TT + ) E (IA (1 1 +1)
(71)
= E (|Am m+ +1 ) E A m
To bound the first term in (55 we use the definition of Am+ Under the condition y. = i, we have, with the same derivation in (56):
A vo
ATh m h2 (a.f("") 0, 0zf(x"))
Tm (0.f(E(s)) ax"("")) ds (72)
m hs (0.(( 0 (x²²)) Vm
where we denoted Vm = 1m (B:s(((s)) ))m( ds.
22

---

Under review as a conference paper at ICLR 2021
However, different from (60). since f has higher regularity, find tighter bound for the integral. Denote
+h
U
@.f(E(()) - 0.f(fmm v2 v2 Tm
anf(ā(z)) ds
(73)
Tm
and
Tm [ (uf( dB,
s 2
(74)
Tm
Then 72
can be written as
A Am+i
A h (0rf(i"m 0xf(x"))) Th U
(75)
which implies, according to Young's 's inequality, that, for any
E
i) E (1 + U 1 =
<(1 + a a (IA!++
+ - i) + 1 (16
(76)
Both terms on the right-hand side of 76 are small. We now control the first term. Plug in the definition 775.. we have:
E (IAT+L + 1 1rhh =1)=)--- =1) =I (1A,T he (0: 0.f(x"))) -- = i) (77)
Noting that
EE ((A Th
14 (O.](im) 0.s(x."))) TT))
T th,
[ (A,Th h4 (0.5(amm) 0.f(x"))) - ds
2
T'm
because
[ (A." hy (0. (.(x"")))) (d)() =0,
E
according to the property of Itô's integral, we can discard the cross terms with 4t in to obtain
E (IAm m+1 + U r = -E EA, (Oif(i") )zf(x))))
E - 0f ( (mmm)
(78)
For the last term of (78.. we have the following control:
th;
[ Ou (āf(((()) dB, ds
E (1 i) = E
r rm =
Tm
T thi
(F +h
fte Oxf(f(z))
< 2E
ds
dB,
ds
r =
Tm
Tm
Tm
T
(1 Oad Oaf(
2h
E
pm -i=
=i ds
m
T -ba
(
2h
E
(10.f((())))
dz ds
N.
where Hölder's inequality in I and ā(t) p for all i in III. In II, the following property of Itô's integral:
m = = =f" (1am) =1) dz.
()))
mm
23

---

Under review as a conference paper at ICLR 2021
By substituting into (7). obtain
(1Am++) + UTP [2 n = S 12 14," (0.s("=") - 0,f(x")))
+ h (0: 8. (z + 1
(79)
To bound the second term on the right-hand side of (76), we first note that f is three times con- tinuously differentiable, and (15) implies [|0rzf llo 8 S H, Take dt on both sides of (48) under
condition r i, we first have
(t) = - (z((ss ds + v2dB..
(80)
According to Itô's formula, obtain
f.f()(t)) (af(tt))a.ffFt)) 0.f(z")) f auf ( + S" auf( ds.
(81)
Substituting (80) into [11) we have
a.((((1)) - 0,5(1")) v2 L"
Oul (a)
Tm
(82)
+ + (mn
Tm
By substituting into
73
we obtain
E
(1Um
n = ds - - v2 [ 0u Sz)
hi
thi
(fr (-0.s((((2))) + (dx))) de
2 r =1 m=== ds
E
(IIT)
+hi
2
E (1a.
dz
Tm
Tm
(IV)
T
I 2h²
E ((0.0((((t)))05(((())))) = dz ds
Tm
+he
[ E (()a Tm
+ +2hh
dz ds
Tm
h (L + M!)
(83)
In the derivation, (II) comes from plugging in (82). and (I) and (III) come from the use of Jensen's inequality, (V) comes from the use of Lipschitz continuity in the first and the second derivative ((1)) and (15) particular), and the fact that z(t) p for all Note also 12, < L, by (Dalalyan
and Karagulyan 2019 Lemma 3).
By plugging (79) and (83) into (1) and 76). we obtain
A P1Am++p m+
< (1 + aΦ))
IE AT 2(1 + a)hE |AT (0.((a") 0xf(x")))]
+ (1 + h2
E El,f(3²*) - - + (1 + a)h3
1)
h (L + H??)
1
+
aa)
Φi
d3
(84)
where we use h.g, = h. Comparing with 70). we need to set
hy < 1,
haj =
Φi
where we use h
e min (dil This leads to 1 I
2d:
By substituting into (62) we obtain
812
122212 Φi
E m m++12 2
<
1 + hy +
E EAT
2hE (0.f(am) - fx
3h2
L
21 (Lg + H!?)
E
di
oip
24

---

Under review as a conference paper at ICLR 2021
Noting Li/p> >
conclude the lemma.
The proof of Proposition C.1 is obtained by summing up all components and applying Lemma
Proof of Proposition C.1 Noting that
d B A
E A
m
=
substitute using 77 to obtain
1:2 12
E 1
hpp +
B|A 24 (A m Vf(**) V)(x²'))
min min(0:) xx:
3h2
V + 4h
(L + H?)
+
(f("))
(85)
f
of
The second and third terms in the right-hand side of this bound be controlled by E|A m12 as follows. By convexity, we have
EA"" Vf(==m) - vf(x=")) 2 /E 11
(86)
By the L-Liischitz property, we have
ff(")) - V f )am)) - 1
(87)
By substituting 86) and into 64 and using < L,, we have
4h2
413
(L) + H
B m1*++1
12
1 hy
E A
+
Σ
(88)
min(ó.}
H i=1
0f
Since h pimundd SL*
we obtain (68)
D PROOF OF PROPOSITION
Proof of Proposition 4.2 For this special target distribution p, the objective function is f(x)
Σd
1,, 2 With = 0 and Φ; = 1/d, we have: x. = =x;" for all i & r and
m++ 1 = (1 - dh) + 22dhem m
Therefore for all i = 1, 2,
d. we have
E (1 1- + (1-2) 1 E (1r I f i)
m+1 12 E E
d
1
E (1(1 dh dd) 22dhem =i) + (1 (1- 2 B (1TTP)
d
(1 2h + dh?) E|a?" + +2
(89)
where we use Eg
x. dhat + v 2d = (1 - dh)) + 2dh in the last equation. By
summing 89 over we obtain
El m1 (1 2h + dh²) E/ + 2dh.
Using it iteratively, and considering 0| 3d, we have:
E m22 2
3d (1 2h + dhh) m + (1 (1 2h + dhz)) m) d
2dh
2h dhi
= d d1 - 2h + dh?)
+ 2 dh
2d
+ 2d
(1- (1- 2 - dh )
(1 )
2h + dh?)
2d
2
- 2d-12hh)" dh
25

---

Under review as a conference paper at ICLR 2021
where we use dh in the last inequality. Since
W (gm. p) 2 (f |x|| qm dx) )z))
(ʃ (Il)
1/2 = 1 dr)
1/2
Vd.
have
W (gm p) 2 (f (m))))()))d))
d(1 2h) m + 2-
2d
vdz
v dd 2h)"
+ 2-dh
2d
+ vd
vd
d3/2h
(1 2h)
6
Vd_
/
2 exp
(-2mh)
3
where in the last inequality we use
2d
d
2h)
+ 33vd.
2 dh
Therefore, we finally prove 26
26


Reviews:
[{"review_id": "moVB59VNzVL", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post rebuttal update:\nI read the other reviewers' responses, and, although I am still positive about this paper, I agree with R2 and R4 that safely fixing the theoretical proofs would require a full revision. For this reason, I am lowering my score to 6.\n\n%%%%%%%%%%%%%%%%%%%%%%%%%\n\nThe authors propose a variant of Unadjusted Langevin Algorithm by replacing the full gradient of the log-density by the gradient of a single coordinate selected at random according to some chosen probability distribution phi. When the log-density of the target distribution is gradient Lipschity and strongly convex, and the step size for updating a coordinate is inversly proportional to the probability of selecting it, the authors show approximate convergence in 2-Wasserstein distance of Random Coordinate LMC (RC-LMC) to the target distribution. The convergence guarantees, in terms of cost, match the ones of classical LMC in terms of dimension and accuracy dependence.\n\nIn the case where all dimensional Lipschitz constants are known, the authors propose a new choice of coordinate selection probability distribution phi and step sizes that yield similar convergence guarantees, but with d^2 kappa dependence replaced by (sum_i kappa_i) where kappa is the global condition number, and kappa_i's are the dimensional condition numbers. Hence, this yields improved convergence guarantees in the case of high dimensional and highly skewed log-density.\n\nIn the case where, in addition, the log-density has a Lipschitz Hessian, and under a proper choice of the coordinate selection distribution phi and step sizes depending on the dimensional gradient and Hessian Lipschitz constants, the authors show convergence of RC-LMC in 2-Wasserstein distance with rate O(d^3/2 epsilon), improving upon the best known rate for this setting.\n\nThe authors show a lower bound for RC-LMC in the gradient and Hessian Lipschitz case, matching the previously shown upper bound. Such a lower bound is appreciated, especially in the literature of Langevin dynamics based sampling algorithm where convergence upper bounds are plentiful and not much is known about lower bounds (especially in the deterministic gradient setting).\n\nFinally, the authors perform a numerical experiment in which they estimate the expectation of some test function of some randome variable following a skewed Gaussian distribution from N samples. They demonstrate that RC-LMC, with our without the knowledge of the dimensional Lipschitz constant, converge faster than classical LMC.\n\nConcerning this experiment, the various methods converge to different saturation thresholds. However, since the objective is strongly log-concave, all methods should converge arbitratily close to the target distribution when choosing the step size small enough (or using a decaying step size). The only limitant factor should then only be due to N being finite, which is common to all methods. Could you please mention and argue upon the choice of step sizes for each method? It would also be nice to plot the optimal saturation threshold for estimating the expecation of the test function from N samples, which should be computable exactly for a Gausian target distribution.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MU5a6Cl1xD7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "$\\textbf{Post rebuttal update}$\n\nI am still positive about the paper and believe that it deserves to be published. However, I agree with Reviewer 2 that some non-trivial rewriting is necessary. The flaws are most likely not very hard to be repaired but it will require substantial additional work and the new version needs to be carefully checked. This is the main reason why I downgraded my score from 7 to 6.\n*****************\n\n$\\textbf{Description of the contributions}$\n\nThe paper studies the problem of sampling from a smooth multivariate density defined via a strongly \nconvex potential function. The main focus is on the analysis of a version of the Langevin Monte Carlo\nalgorithm in which the computation of the full gradient at each iteration is replaced by the computation\nof a randomly selected partial derivative. The main results of the paper are theoretical guarantees \nformulated in terms of the Wasserstein distance between the sampling distribution and the target \ndistribution.\n\n$\\textbf{Evaluation}$\n\nI find the results very interesting and worth being published. However, the current version of the paper\nsuffers from some shortcomings that have to be repaired. The most important shortcomings are listed below,\nthe others are provided as specific remarks.\n\nP1. The most important problem is the way the proof of $\\textbf{Prop A.1}$ is written. I believe the result is true, however\nthe arguments provided in the proof should be clarified (Please refer to point 8vin the list below). In particular,\nit is more appropriate to refer to the conditional distribution of $X_{r^m}(t)$ given all the other coordinates, rather\nthan to the marginal distribution.  \n\nP2. The second shortcoming, slightly less important, is that the paper contains no concrete example of potential \nfor which the results of this paper (for instance, $\\textbf{Theorem 4.2}$) improves on the previously available results. \n\nP3. An important part of the supplementary material is devoted to the proof of the second claim of $\\textbf{Theorem 4.1}$.\nMy impression is that this second claim, which provides exponential ergodicity of the Markov chain, is of little \ninterest and does not really fit the framework of the paper. Indeed, while all the remaining results come with\nexplicit dependence of the constants on the dimension and the condition number, the constants involved in (20)\nare not specified at all. My suggestion is to remove the second claim of $\\textbf{Theorem 4.1}$ (starting from \"Furthermore, \nif ... \").\n\n$\\textbf{Specific remarks}$\n \n1. Page 2: \"d-dimensional Brownian motion with independent components\" a Brownian motion has always independent components, no need to additionally underline this property. \n2. Page 2: \"under mild conditions, the SDE converges exponentially fast to the target distribution\" First, conditions are not really mild. Second, it is not the SDE that converges, but the distribution of its solution at time t. \n3. Page 2: The sentence \"One main drawback of LMC is that its dependence on the problem dimension d is rather bad.\" is too strong. The dependence in the strongly convex case is linear in d, which can hardly be qualified as \"rather bad\". \n4. Page 2: \"with LMC depends strongly\" -> \"with LMC depend strongly\"\n5. Page 2: the authors claim that \"RC-LMC [...] is cheaper than the classical LMC\" This claim should be carefully reformulated. What the results of this paper imply, under the most favorable interpretation, is that the obtained result for RC-LMC is better than the best known result for the LMC. It might very well happen that the result for the LMC is improvable and that the LMC is as fast as the RC-LMC.\n6. Page 4: \"When we compare (5) with the classical LMC (1), we see that in the updating formula, the gradient\nis replaced by a partial derivative in a random direction $r_m$\" I am not sure that this claim is true. It would be correct if the authors were adding the Gaussian noise term to all the coordinates, but this is not done in the current definition.\nOn a related note, in equation (7), the dimension d of the Brownian motion does not match with dimension 1 of the left-hand side.  \n7. Section 3: It might be that I missed something, if not, it would be useful to highlight that the notation $|v|$ is used for the Euclidean norm of $v$.\n8. The proof of Theorem 4.1 is not valid. Indeed, the fact that $p(x)$ is the invariant distribution of the Markov chain is not correctly proved. Even if we admit that the (questionable) argument with the EDS is correct, it only proves that the marginal distribution \nof one coordinate and the joint distribution of the remaining coordinates coincide with those of $p$. This does not imply that the entire distribution coincides with that of $p$.\nAnother flaw in the proof of the theorem concerns line 8 of the proof. This inequality should further justified. I see very well how to prove it in the case when the Markov kernel is absolutely continuous wrt to the Lebesgue measure. However, I am not quite sure that the Markov kernel used in this theorem is indeed abs-cont.    ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GCCRbRwfTUB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies Langevin Monte Carlo (LMC) in the high dimensional regime. To reduce the computational cost, the authors proposed the Random Coordinate LMC (RC-LMC) algorithm that only updates one of its coordinates randomly at each iteration. Despite the fact that only one coordinate is updated, the authors prove that RC-LMC still converges fast to the stationary distribution. Given some nice properties of the log-density functions, the total cost of RC-LMC could be smaller than LMC especially when the function is highly skewed in a high dimension space. This paper is well written and clearly presented. The experiment is somewhat limited since the dimension of the problem is not high to me. It would also be nice if we could see how the proposed algorithm performs on real datasets of Beyesian sampling problems. I also have some comments on the technical analysis of this paper as follows. \n\nThe non-asymptotic analysis of LMC is also studied in Xu et al. (2018), which develops a quite different analysis from other works by directly showing the ergodicity of the Markov chain generated by LMC. It seems that the analyses in that paper and the current submission are closely related.  \n\nXu P, Chen J, Zou D, Gu Q. Global convergence of Langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems 2018 (pp. 3122-3133).\n\nThe cost in Theorem 4.2 depends on the sampling probability for choosing the coordinate. It should be noted that if some \\phi_i is significantly smaller than 1/d, the total cost may have a worse dependence on dimension. \n\nIn the proof of the ergodicity of the Markov chain X^m, is it true that both r and R are constants independent of the problem dimension?\n\nIn Theorem 4.1 and Proposition A.1, the authors claim that the stationary distribution of Markov Chain X^m is p(x). I am not sure whether this is correct. Note that p(x) is the stationary distribution of the Markov chain X_t defined by the SDE in (2). We know that X^m is a discretized chain based on X_t. Therefore, as long as the step size is not zero, there will be some discrepancy between these two Markov chains. Thus their stationary distribution could not be the same. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AIaCOKT9z13", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper generalizes the Langevin within Gibbs sampler to be able to put different frequencies over different coordinates. The idea is cute. The result, however, is not convincingly better than the vanilla Langevin algorithm.\n\nThe convergence rate for the current method for strongly convex and Lipschitz smooth case scales as O(d^2/\\epsilon^2) in Wasserstein 2 distance, where every step requires partial derivative in one coordinate. This is to be compared to O(d/\\epsilon^2) gradient computations required for the vanilla Langevin algorithm to converge. Although in terms of number of partial derivatives, they are comparable to each other, current computation infrastructure has made gradient computation a lot cheaper than d number of sequential  partial derivative computations.\n\nOne possible use case, as the authors mentioned, might be that certain dimensions are more stiff than the others, calling for more careful exploration. In practice, however, the stiff dimensions change with the state and it is challenging to detect these stiff directions on the fly.\n\n#################################################################################\nTLDR\n\nPros:\nGeneralizes Langevin within Gibbs and achieves convergence guarantees.\n\nCons:\nNot outperforming (sometimes even underperforming) current methods.\n\nRelated work:\nPlease also check the related work: MALA-within-Gibbs samplers for high-dimensional distributions with sparse conditional structure, X. T. Tong, M. Morzfeld, Y. M. Marzouk, 2019.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new sampling method named Random Coordinate LMC (RC-LMC), which integrates the idea of randomized coordinate descent and Langenvine dynamic. The authors prove the total complexity of RC-LMC for log-concave probability distributions, which are better than that of LMC under different settings. The idea of this paper is very neat and the reviewers are in general positive about it. However, as pointed out by one of the reviewers and seconded by the other reviewers, the proof in the original submission is flawed, and the fix needs some substantial work. The new version needs to be carefully checked before publication, which is far beyond the review process of ICLR. Therefore, I encourage the authors to carefully revise the paper and submit it to the next conference. 
Decision: Reject