Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this work the authors study the convergence of mirror descent langevin dynamics -- Langevin dynamics which have been transformed appropriately to satisfy certain constraints or evolve according to a specific non-euclidean geometry.   The dynamics can be characterised in various forms, including as a riemannian manifold overdamped langevin process with a specific choice of metric tensor -- but also as an SDE in the dual (unconstrained space) which is projected onto the original state space.

The paper considers the convergence to equilibrium of the mirror descent Langevin dynamics -- both for the original continuous time process, but also for various discretisations of the scheme.  This is done under the assumption of a Logarithmic Sobolev Inequality, thus generalising common convergence analysis which typically require strong-log-concavity assumptions.

It is demonstrated that the choice of discretisation plays a key role in achieving consistency under vanishing step-size for constraints which involve non-smooth contributions (e.g. constraint to lie within a box, etc), ultimately presenting a backward discretisation scheme which is far more stable to sudden changes in the geometry underlying the constraint.

These results are illustrated through a straightforward numerical example.




main_review: I found the paper generally well written, to the best of my ability in understanding the details.  The general arguments are familiar from other works, but this pulls them together to provide analysis for an important problem.  Based on this I believe the work demonstrates significance, particularly in identifying the role of the smoothness of the geometric induced by the constraint.  

The main issue I find with this work is the lack of convincing numerical examples to demonstrate this -- the single presented example is important as a toy illustrative example, but is trivial in many senses.  Perhaps one could find an opportunity to demonstrate more complex forms of constraints, e.g. e.g. constraints to simplex and another geometric constraints.  What about employing this methodology simply for accelerating unconstrained sampling using Newton-type updates based on the hessian of the objective?   These could've been addressed as  examples.

Minor comments:

l14: shapes

l20: isoperimetric

l26: continuous

l35: legendre has an accent

l53:'It is evident (and reminiscent of the classical Langevin algorithm) that the discretized algorithm will converge to a biased limit' --> there are many well-known examples where the EM discretisation of a Langevin SDE will not even have a long-time limit.  So without further assumptions, it's an open question whether a limit even exists, biased or not.

l99: is the Hessian stability condition correct -- what are $x$ and $x'$ here?

l105: What is $|| \cdot ||_{[\nabla^2 \phi(x)]^{-1}}$ ?  Has this been defined?

I also highlight some important works which don't appear to have been cited/considered in this work

Wang, Xiao, Qi Lei, and Ioannis Panageas. "Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev." arXiv preprint arXiv:2010.05263 (2020) which really follows the approach of Vempala & Wibiscono 2019, 

Lamperski, Andrew. "Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning." arXiv preprint arXiv:2012.12137 (2020).
limitations_and_societal_impact: Limitations have been adequately addressed -- societal impacts have not been mentioned, though I certainly cannot envisage any.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies discretized mirror Langevin diffusions under the assumption of mirror-log Sobolev inequalities as well as relative smoothness assumptions. In particular, they show that a new backward method obtains perhaps the best dependence in terms of finite sample guarantees in this setting. On the other hand, Euler-Maruyama discretization has an irreducible bias and a different forward discretization has an exponential dependence on the diameter of the mirror set.
main_review: Upsides:

+ This paper gives new upper bounds for discrete mirror Langevin dynamics.
+ The upper bounds on these three different discretizations of mirror Langevin dynamics allow one to compare them theoretically.
+ The work proposes a new backward discretization that has the best guarantees.  
+ This work tackles the analysis of an important generalization of Langevin dynamics, that may hold the key to more efficient sampling algorithms.
+ The paper is generally well written and highlights the differences in the upper bounds obtained.
+ The assumption of weaker relative smoothness is interesting.

Downsides: 

- The methodology and assumptions have mostly been used before, with the exception of the weaker relative smoothness and the new discretization.
- Proposition 1 appears to be a restatement of in Chewi et al. 2020. Theorem 1. (since Poincare is weaker than log Sobolev *edit due to typo)
 - Experiments do not enlighten differences between the forward discretization of Ahn and Chewi versus the new backward discretization. For example, the difference in dependence on $M$ for the forward versus backward schemes is in terms of upper bounds rather than lower bounds, and it would be nice to see experiments that illustrate this difference. Also, it is unclear how different (12) versus (16) is in terms of hardness to solve. (*edit: this should be (11) versus (17), as the authors point out)
- It is unclear how tight the analysis in Theorem 1 and Proposition 3 are. In particular, does Theorem 1 necessarily imply that the bias is non-vanishing? Are the bounds in Proposition 3 in some sense tight?
- The performance of EM in Figure 1 is strange in light of Figure 3 in Chewi et al. 2020. What is the difference in implementation here?
- The comment at the bottom of page 8 is not clear. Why is mini batching equivalent to adding Gaussian noise?

(edit fixed a few typos)

---

After considering the authors' response and discussion with the other reviewers, I am raising my score to 6 and recommending acceptance based on the theoretical merit of the paper, although I do not give a higher score due to the weaker practical details.
limitations_and_societal_impact: Limitations are not explicitly discussed. In particular, the analysis done is all in terms of upper bounds, which may not be optimal. Furthermore, the performance of the forward and backward schemes are not thoroughly explored in practice, and in particular, the differences in solving (12) versus (16).
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper under review mainly studies different discretization schemes for mirror Langevin dynamics. The main assumption is the non-asymptotic convergence/long time convergence behavior to the target invariant measure. The main feature of this type Langevin dynamic is that they have non-gradient drift and variable diffusion matrix. The author try to covey the importance of the underlying geometry which is introduced by the variable diffusion matrix. 
main_review: Positive.

1. The logic of the paper is easy to follow, and the several discretization schemes are presented with complete derivation. 

2. The idea of introducing new  discretization schemes seems to be valid for more general variable diffusion Langevin dynamics. 

limitations_and_societal_impact: Negative.

1. The Mirror Langevin dynamics presented in this paper is a special case of a series paper for general Langevin dynamics.  e.g. [Q. Feng and W. Li] Hypoelliptic entropy dissipation for stochastic differential equations. The dynamics (3) is simply by choosing $a(X_t)=[\nabla^2\phi(X_t)]^{-1}$ and $\gamma=0$ for the dynamics (1) in  [Q. Feng and W. Li].  The Fokker-Planck equation is also derived there together with the entropy decay result Proposition 1. (Note here the LSI is assumed to be true in the current paper, thus the decay of KL seems to follow naturally.)

2. The assumption of the current paper claims to be weaker comparing to the existing ones [23]. The reviewer is quite curious about the verification of Assumption 2. In the aforementioned paper [Q. Feng and W. Li], the existence of the LSI for a general variable diffusion Langevin dynamic follows from the Ricci curvature lower bound. Can the author verify that Assumption 2 is indeed true for certain classes of the mirror map $\phi$. It would very interesting to see such examples where global in time and space LSI is established for non-convex f.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper gives a discretization analysis of the mirror-Langevin Monte Carlo algorithm, which is the analogue of mirror descent for MCMC. The prior works studying discretization of mirror-Langevin are as follows:

[1] Zhang et al., who studied the Euler-Maruyama discretization. They used stochastic calculus coupling techniques in the vein of works by e.g. Dalalyan.

[2] Ahn and Chewi, who introduced and studied an alternate discretization which simulates the diffusion step more faithfully. Their analysis uses Wasserstein calculus in the vein of Durmus, Majewski, and Miasojedow.

A key difference between these two works is that the result of [1] has a non-vanishing bias (even with vanishing step size), whereas the discretization of [2] does not.

This paper studies both the Euler-Maruyama and Ahn-Chewi discretizations, and introduces a third one which combines the Ahn-Chewi discretization with a proximal step to obtain better guarantees. The results obtained have non-vanishing bias for the Euler-Maruyama discretization, and vanishing bias for the latter two discretizations, which is in line with previous work. The techniques are inspired by the discretization analyses of Wibisono, who is inspired by the interpretation of sampling as composite optimization in Wasserstein space. Moreover, this paper emphasizes the use of a mirror-log-Sobolev inequality as the condition ensuring rates of convergence, which allows for treating examples of non-convex potentials (which are not handled by the prior two works).

The main contributions can be summarized thus: (1) by obtaining a similar dichotomy between the bias of Euler-Maruyama vs. Ahn-Chewi, it sheds further light on the effect of discretization of the diffusion in the presence of non-isotropic diffusions; (2) it shows how to adapt a third type of discretization analysis to the mirror-Langevin setting; (3) it introduces a proximal mirror-Langevin algorithm which had previously not been considered and gives guarantees.
main_review: Evaluation: This paper is a good contribution to the sampling literature in light of the main contributions listed above. Since it is more challenging to handle the non-isotropic diffusion than the study of vanilla Langevin, understanding discretization analysis for mirror-Langevin is an important problem.

My main concern with this work is that it is not straightforward to find examples in which the mirror log-Sobolev inequality holds (besides when the mirror map is quadratic, in which case it reduces to the usual log-Sobolev inequality). For example, the usual log-Sobolev inequality is implied by strong convexity, and besides there are many identified situations where it holds (e.g. convolution of a measure with bounded support with a Gaussian). On the other hand, relative strong convexity w.r.t. a mirror map is not enough to imply a mirror LSI; for instance, as discussed in the paper of Chewi et al. on mirror-Langevin, when the mirror map equals the potential then relative strong convexity trivially holds, but a mirror LSI does not hold without further assumption on the potential/mirror map (see the reference to Bobkov-Ledoux therein). It is important therefore to find further examples in which the mirror LSI holds to assess whether this is indeed a useful assumption.

Specific Comments:
- On pg. 3, after Assumption 2, it is claimed that the assumption of a mirror LSI is “strictly weaker” than that of relative strong convexity, but this is false as discussed above. Rather, it would be better to include somewhere in the paper a more thorough comparison of the two sets of assumptions.
- Last display equation on pg. 4 should have \nabla_x rather than \nabla x.
- On pg. 6, it is claimed that “the simplest EM discretization exhibit [sic] an irreducible bias”. It is not clear what exactly is meant by this statement: after all, Thm. 1 (as well as the prior work by Zhang et al.) merely provide upper bounds on the bias, and it is not yet proven if the EM discretization indeed exhibits bias or not.
- On the subject of the bias of EM discretization: the O(d^2) bias is quite large. For comparison purposes, what is the size of the relative entropy at initialization under the same assumptions, for a sensible choice of initialization (e.g. Gaussian with appropriate variance)? Is it clear that this bias term O(d^2) actually constitutes an improvement over the initialization? If not, then the EM result seems almost vacuous to me.
- Lemma 6 in the appendix is surely wrong; the relative entropy of ρ_0 w.r.t. to π is only finite if ρ_0 is absolutely continuous w.r.t. π, and this cannot hold if ρ_0 is taken to be a Dirac mass. It means that Thm. 1 which initializes (4) at a Dirac mass is incorrect as stated (or at least the proof has to be modified to show that the relative entropy becomes finite after finitely many iterations).
- Throughout the paper there are a number of minor grammatical errors, and the paper would benefit from an extra round of proofreading.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper studies discretization schemes for the mirror-descent version of Langevin dynamics, under a mirror log-Sobolev inequality (LSI). We thank the authors for a lively discussion. We have decided to recommend acceptance, because the theoretical contribution is of interest to the community. That being said, we still had concerns about 1) knowing when mirror LSI is likely to hold, and 2) the thinness of the experimental section. We thus encourage the authors to update the paper before the final version, so as to include:
* a paragraph on when mirror LSI holds, or might hold, following the discussion that was held during the reviewing process.
* More quantitative experiments that illustrate the theoretical results on the various discretization schemes. Please also make the figure labels more readable.
Decision: Accept (Poster)