Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: null
review_content: In light of the new comments by AC and the authors, I have revised my score from 6 to 4. Although there are still novel aspects of this submission (as the authors point out), the reality is that accounting for this missed reference will require substantial rewriting, not just in Section 3, but throughout the entire paper in order to reframe the scope of the contributions as well as to provide technical comparisons with Li et al. For such a large-scale revision, it does not make sense to accept the paper to this conference without providing further feedback to the authors in the form of follow-up reviews. Therefore, I recommend that the authors carefully revise the paper and resubmit to another venue.
review_title: Updated score in light of AC statement and author response

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper first gives an analysis framework for controlling 2-Wasserstein distance of sampling algorithms coming from discretizing a continuous Langevin dynamics.
This is achieved by first considering the bias (local weak error) and mse (local strong error) of single step update. 
The multi-step error accumulate exponentially, but together with the contraction guarantee, the maximum sampling error after arbitrary steps could be controlled.
Next, 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.
The convergence analysis is carried out based on the general analysis framework.
main_review: This paper is mostly well written and easy to follow.

The analysis framework is general and easy to use but the proof is not novel.
Many researchers working  on the problem of sampling have already had this idea and internalized this method in their numerical analysis of special sampling algorithms.
However, given that none of them have managed to convert it into a general framework, there is indeed novelty in this framework.

The improvement of dependency of dimension relies on the assumption on linear growth of the 3rd-order derivative.
Has 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.
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).

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

POST 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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

2) 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?
limitations_and_societal_impact: No societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
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).

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

After 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.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

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

Specific Comments:
- 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”.
- 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.
- 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).
- 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.
- 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?
limitations_and_societal_impact: Yes.
review_title: null

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