Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors analyzed an Euler type discretization of diffusions, in particular the Langevin diffusion, on a large class of Riemannian manifolds. The authors provided a one-step discretization error bound, which leads to a sampling guarantee when discretizing the Langevin diffusion. The authors also extended these results to the stochastic gradient setting. 

Given the challenging nature of studying discretizations of diffusions on general manifolds, I believe any results should be welcomed, even if it is not ultimately the best error and sampling bounds possible. I would encourage the area chair and the other reviewers to not penalize the paper for not achieving the best possible sampling bound, as it is still a significant step towards understanding sampling on manifolds. 
strengths_and_weaknesses: # Strengths 
1. The authors provided the first (to the best of my knowledge) discretization error bounds for diffusions on a large class of manifolds in Lemma 1. In particular, the discretization is computable (i.e. not a Brownian motion increment on the manifold), and the assumptions on the manifold is significantly weaker than existing work. 

2. The authors provided one of the first sampling complexity bounds on a large class of manifolds in Theorem 1, with Gatmiry and Vempala (2022) - the only other work I know of - taking a different approach and therefore should not be directly compared. 

# Weaknesses 
1. It is likely that the sampling bound in Theorem 1 can still be improved in terms of other factors such as $d, m, \mathcal{R}, L_{\text{Ric}}$ etc. 
questions: I have several technical questions that I would like to clarify with the authors. I believe these are due to the technical nature of the paper, and therefore should not affect my score, but I would still prefer to understand them in detail since we have a discussion period. 

# On Lemma 1 - Discretization Error Bound 

On a separate note, I just want to say the diagram is actually really helpful to understanding the steps of the proof, as the notation is quite heavy. 

1. On line 204, summing the bounds give an exponential factor of $\exp( O( L_R d \delta^i ) )$ and there a recursion over $k$ as well, which would compound this to the exponent $2^i$. My question is, does $\delta$ then need to be chosen in a way to remove the exponential factor here? 

2. On a higher level, I'm surprised that the authors did not have to work with stochastic parallel transport along a Brownian path, which I personally found quite difficult. Can the authors comment on which part of the construction that allowed the authors to avoid this technical difficulty? I'm speculating here, but is it due to the construction of $x^i(t)$ such that the realized paths are always geodesics and not Brownian? 

# On Theorem 1 - Langevin Sampling Bound 

1. Can I interpret the assumption of $m - L_{Ric}/2 > 0$ as morally a Bakry--Emery type criterion (especially if $\mathcal{R}=0$)? 

2. In a similar spirit, can I also interpret the factor $exp( -(q+L_{Ric}/2) \mathcal{R}^2 )$ in the convergence rate $\alpha$ as a Holley--Stroock type perturbation? 
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper is concerned with convergence analysis of the Langevin MCMC algorithm on a Riemannian manifold. This is extension of the results on the Euclidean space to the manifold setting. It provides error rates between the continuous-time stochastic process that solves the Langevin eq. on the manifold and its Euler-Murayama discretized version (which represents the algorithm). The discretization error combined with convergence rate of the continuous process  provides error bounds for the output of the algorithm: number of iterations scales with $\tille O(\epsilon^{-2})$ for $\epsilon$ error. The convergence analysis is also extended to the case where only unbiased random estimate of the gradient are available. The error bounds hold on the dissipativity assumption on the drift outside a ball (which includes gradient of non-convex functions) and lower bounds on the Ricci curvature of the manifold. The second result for stochastic gradients require dissipativity everywhere. 
strengths_and_weaknesses: Strength:
- Well-written paper given its technical nature
- Well discussion of related literature and connection to previous results
- Important and useful theoretical results and their discussion 
- Explicit convergence rate in terms of  constants 
- Generality of the assumptions 


Weakness: 
- minor clarifications on details 

questions: Minor:

1- Line 28: by $g(x)$ do you mean the Riemannian metric? 

2- Line 97: item ii): do you also mean almost surely? 

3- What is the Euclidean counterpart of assumption 2? I think including it would make the assumption easier to understand.  

4- Sketch proof of Lemma 1: Equation after 172: I think it would be better to clarify the relation between $\zeta^i_k$ for different $i$ by including their definitions there, rather than after 4.1. Then it is easier for the reader to understand Figure 1 and the following two steps in connection with the definition.  

5- I did not understand the remark following line 276: "under assumption 3, $\beta$ satisfies assumption 2"? Do you mean $q\leq L'_\beta$ 

6- I think $\mathcal R$ should not appear in the result of Theorem 2. 
 


limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors show theoretically that under some assumptions, sampling from a distribution on a Riemannian manifold using the associated discretized SDE provides a good approximate solution. In particular, it is shown that the error of the discretization can be bounded and that the final density is close to the true density under the Wasserstein metric.
strengths_and_weaknesses: - Originality: I am not an expert in the topic of sampling, but it seems to me that the current work is novel and differs from the related works, which seem to be properly discussed.

- Quality: The technical part of the paper seems to be correct and sound. Of course, I could not read carefully all the theory, but the analysis seems reasonable.

- Clarity: I think that the clarity of the paper can be improved such that to help non-expert readers. I acknowledge that the authors tried to simplify parts of their analysis to make it accessible, but some parts perhaps is possible to be improved. For example:
	1. Some toy examples of the method can be provided to allow the reader become familiar with the topic. For example, a distribution on an appropriate Riemannian manifold together with the associated algorithm/results.
	2. Some additional images could help the reader understand parts of the theory and the proofs. Figure 1 helps a lot in understanding, and I think more figures in the same spirit would have been very beneficial.
	3. In a related manner, I am not sure if it is possible to simplify some technical parts even further. Maybe some parts of the sketch-proofs can be moved in the appendix and instead provide the gist with graphical examples?

- Significance: The theoretical results seem to be interesting and useful, and as it is claimed by the authors their analysis improves upon previous approaches. I think that the provided guarantees can be potentially taken into account when practical models are developed. However, the downside is that it is not easy to verify if and when the assumptions holds, while the authors do not seem to provide some examples. Also, even if the main target group of the paper seems to be readers very familiar with the associated topics, I believe non-expert readers could be benefited if parts of the paper become more accessible for them.
questions: - The SDE that is analysed is used to generate samples from a stationary distribution. In practice, this means generating a "long enough" chain such that the collected samples to represent the associated density. I think when such approaches are used, due to the discretization there is an implicit bias which is tackled using an acceptance ratio scheme. Is this necessary in your sampling scheme? How the geometry influences the behaviour due to the discretization?
- In your analysis the expmap operations seem to take place in the ambient space, so I assume that the parameters $\beta$ and $\zeta$ are tangent vectors in the ambient space (Eq. 1.2)?
- The results related to the Wasserstein distances imply that empirical distribution of the collected samples with the discretized SDE, is close to the true distribution? And the closeness is measured with the Wasserstein distance using the geodesic distance as the distance measure in the associated integral?
- In Lemma 1 the $\zeta$ that is used for the Expmap is used as the initial condition for the true solution $x(t)$ of the SDE?
- For the Theorem 1 to hold, it seems that the starting point $x_0$ must be close enough to a mode $x^*$. If this is the case, then I suppose that the generated samples from the discretized SDE are a good approximation of the density but only locally near the mode? In contrast, the Lemma 1 holds even if the $x_0$ is not near a mode $x^*$, is this correct?
- Are there any simple synthetic examples that satisfy the assumptions?
limitations: Some limitations of the analysis are discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper under review studies the Langevin diffusion on Riemannian manifold. The SDE (overdamped Langevin dynamic) is defined as the the intrinsic diffusion process on the manifold with the drift term given as the gradient (Levi-Civita sense) of the potential function. The discrete scheme is given as the exponential map at each iteration. The error are studied in the Geometric Euler-Murayama setting. The convergence analysis is conducted in various cases under different assumptions of the curvature tensor and the drift vector fields.
strengths_and_weaknesses: The presentation is clean and neat. The requirement of allowing the Ricci curvature tensor to be negative is quite impressive if there is no extra Lyapunov functions are used. 
The appendix seems to be well organized, but it is too long. (I have to say that I cannot read all of the appendix). 

The results seems to be interesting, however the application is not thoroughly discussed and there are no experiments in the work.  The key idea of the main results (proof) should be made clear, like why the negative Ricci curvature lower bound is Okay. (From the reviewer's experience, Lyapunov function shall play a role in such situations, if this is not the case in the current work, this definitely deserve some space.)

questions: 1. The general setting of the paper is to generalize the over-damped Langevin to Riemannian manifold. Although the foundation and the setup is clear, it is not clear how the non-convex problem could be solved in this case. In the Euclidean setting, there are various methods to tackle the non-convex problem. Is it possible to say anything how the Riemannian manifold could contribute in the non-convex setting? 

2. The negative Ricci curvature and convex/ non-convex of the vector field should be discussed together, in the sense that which type of combination could be solved and which combinations are not. 

3. In the Euclidean setting, the target distribution is just $e^{-h(x)}$. In the Riemannian setting, one need to consider the extra $d vol_g(x)$ term. One should make it clear, in application why $e^{-h}d vol_g(x)$ is the interesting target distribution, can the author provide any examples ?

4. Could the author explain briefly how is the two-sided curvature bound and the negative lower Ricci curvature bound used explicitly in the results and proof? This could make the contribution straightforward without looking into the long appendix.

limitations: N/A
review_title: null

Meta-review: metareview: This paper focus on the problem of sampling from a distribution on a large class of Riemannian manifolds. Authors study an Euler-type discretization in this context, for the Langevin diffusion. The paper establishes a control over the one-step discretization error, which is then iterated to obtain a sampling guarantee for the discrete algorithm. Several extensions are also discussed, e.g. the stochastic gradient setting.

Sampling on Riemannian manifolds is a challenging and active area of research. Given that the paper can cover a wide range of manifolds, I also agree with the reviewers, that the contributions of this paper are solid. I strongly recommend accepting this paper.
confidence: Certain
Decision: Accept