Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

The 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.

One 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.

#################################################################################
TLDR

Pros:
Generalizes Langevin within Gibbs and achieves convergence guarantees.

Cons:
Not outperforming (sometimes even underperforming) current methods.

Related work:
Please 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.
review_title: Review of "Random Coordinate Langevin Monte Carlo"

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

The 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.  

Xu 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).

The 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. 

In 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?

In 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. 

review_title: A nice algorithm! Analysis may have some issue.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Post rebuttal update:
I 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.

%%%%%%%%%%%%%%%%%%%%%%%%%

The 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.

In 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.

In 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.

The 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).

Finally, 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.

Concerning 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.
review_title: Interesting upper and lower bounds of Random Coordinate LMC under various smoothness assumptions

final_score: rating: 6: Marginally above acceptance threshold
review_content: $\textbf{Post rebuttal update}$

I 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.
*****************

$\textbf{Description of the contributions}$

The paper studies the problem of sampling from a smooth multivariate density defined via a strongly 
convex potential function. The main focus is on the analysis of a version of the Langevin Monte Carlo
algorithm in which the computation of the full gradient at each iteration is replaced by the computation
of a randomly selected partial derivative. The main results of the paper are theoretical guarantees 
formulated in terms of the Wasserstein distance between the sampling distribution and the target 
distribution.

$\textbf{Evaluation}$

I find the results very interesting and worth being published. However, the current version of the paper
suffers from some shortcomings that have to be repaired. The most important shortcomings are listed below,
the others are provided as specific remarks.

P1. The most important problem is the way the proof of $\textbf{Prop A.1}$ is written. I believe the result is true, however
the arguments provided in the proof should be clarified (Please refer to point 8vin the list below). In particular,
it is more appropriate to refer to the conditional distribution of $X_{r^m}(t)$ given all the other coordinates, rather
than to the marginal distribution.  

P2. The second shortcoming, slightly less important, is that the paper contains no concrete example of potential 
for which the results of this paper (for instance, $\textbf{Theorem 4.2}$) improves on the previously available results. 

P3. An important part of the supplementary material is devoted to the proof of the second claim of $\textbf{Theorem 4.1}$.
My impression is that this second claim, which provides exponential ergodicity of the Markov chain, is of little 
interest and does not really fit the framework of the paper. Indeed, while all the remaining results come with
explicit dependence of the constants on the dimension and the condition number, the constants involved in (20)
are not specified at all. My suggestion is to remove the second claim of $\textbf{Theorem 4.1}$ (starting from "Furthermore, 
if ... ").

$\textbf{Specific remarks}$
 
1. Page 2: "d-dimensional Brownian motion with independent components" a Brownian motion has always independent components, no need to additionally underline this property. 
2. 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. 
3. 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". 
4. Page 2: "with LMC depends strongly" -> "with LMC depend strongly"
5. 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.
6. Page 4: "When we compare (5) with the classical LMC (1), we see that in the updating formula, the gradient
is 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.
On a related note, in equation (7), the dimension d of the Brownian motion does not match with dimension 1 of the left-hand side.  
7. 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$.
8. 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 
of 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$.
Another 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.    
review_title: All the theoretical results of the paper are inetersting and worth being published. However, the proofs as presented in the current version are flawed and require non negligible additional technical arguments.  

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